文档介绍：第三章处理机调度与死锁 Processor Scheduling and Deadlock
处理机是最重要的计算机资源,提高处理机的利用率及改善系统性能,在很大程度上取决于处理机调度性能的好坏,因而,处理机调度成为操作系统设计的中心问题之一。
1
处理机调度的基本概念
调度算法
实时系统中的调度
多处理机系统
产生死锁的原因和必要条件
死锁的预防和避免
死锁的检测和解除
本章主要内容
2
作业的概念
作业(job):由用户提交给系统处理的一个计算任务,称为作业。它包括用户程序、数据,以及对程序运行进行控制和处理的有关信息。一般,可把作业分成批处理型作业和终端型作业两类。
作业从进入系统到运行结束,一般要经历进入、收容、运行、完成四个阶段。相应地,我们说此作业处于进入、后备、执行、完成四个不同的状态。
3
作业的状态
进入状态即提交状态,作业从输入设备进入输入井。
后备状态操作员把作业输入到直接存取的后援存取器后,为进入系统的作业建立作业控制块, 并把它加入到后备作业队列中,等候作业调度程序调度。这一过程也称为作业注册。
运行状态作业被作业调度程序选中,且分配了必要的资源,建立一组相应的进程后,该作业就进入了运行状态。它分为三种状态:即就绪状态、执行状态、阻塞状态。
完成状态当作业正常运行结束或因发生错误而终止时,作业进入完成阶段。
4
5
处理机调度的基本概念 The basic concepts of processor scheduling
一、处理机调度的层次
高级调度
中级调度
低级调度
创建
就绪态
运行态
等待态
挂起等待态
退出
挂起就绪态
6
1 高级调度(High Level Scheduling):作业调度/长程调度/接纳调度。
按一定调度算法,外存后备队列中选择作业调入内存,创建PCB等,插入就绪队列。
一般用于批处理系统,分/实时系统一般直接入内存,无此环节。
一个作业从提交开始,往往要经历三级调度:高级调度、低级调度、中级调度。
调度特性:
接纳作业数:取决于多道程序度。
作业多—影响服务质量(周转时间长);
作业少—资源利用率和系统吞吐量低。
接纳策略:即采用何种调度算法。
7
2 低级调度(Low Level Scheduling):进程调度/短程调度
在多道程环境下,进程数目往往多于处理机数目,致使它们争用处理机。这就要求系统能按某种算法,动态地把处理机分配给就绪队列中的一个进程,使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。
低级调度就是按某种原则,决定就绪队列中的某个进程获得处理机,由分派程序(Dispatcher)实施处理机分派。
8
进程调度要解决的问题
WHAT:按什么原则分配CPU
—进程调度算法
WHEN:何时分配CPU
—进程调度的时机
HOW: 如何分配CPU
—CPU调度过程(进程的上下文切换)
9
进程调度可有两种方式:非抢占方式、抢占方式。
1)非抢占方式(Non-Preemptive Mode)
优点:实现简单,系统开销小。
缺点:不能满足紧急任务的要求。
2)抢占方式(Preemptive Mode)
抢占原则:
(1)时间片原则(time-slice principle) ;
(2)优先权原则(priority principle) ;
(3)短进程优先原则(shortest job first principle) ;
10