第03章 处理机调度与死锁.ppt

第三章 处理机调度与死锁 3.1 处理机调度的层次 3.2调度队列模型和调度准则 3.3调度算法 3.4实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测和解除 第三章 处理机调度与死锁 在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。 这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。 分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。 进程调度要解决的问题 WHAT：按什么原则分配CPU —进程调度算法 WHEN：何时分配CPU —进程调度的时机 HOW： 如何分配CPU —CPU调度过程（进程的上下文切换） 3.1 处理机调度的层次 处理机是计算机系统中的重要资源 处理机调度算法对整个计算机系统的综合性能指标有重要影响 可把处理机调度分成三个层次： 高级调度 中级调度 低级调度 3.1.1　高级调度 高级调度（作业调度、长程调度、接纳调度） 决定哪些作业可参与竞争CPU和其他资源，它的调度对象是作业; 将外存作业调入内存，创建PCB等，插入就绪队列; 一般用于批处理系统，分/实时系统一般直接入内存，无此环节。 1．作业和作业步 (1)作业(Job) 作业由一组统一管理和操作的进程集合构成，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书。 作业可以是完成了编译、链接之后的一个用户程序，也可以是用各种命令构成的一个脚本。 1．作业和作业步 (2) 作业步(Job Step)。 在作业运行期间，经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，我们把其中的每一个加工步骤称为一个作业步。 (3) 作业流。 若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。 2．作业控制块JCB(Job Control Block) 每个作业进入系统时由系统为其建立一个作业控制块JCB（Job Control Block)，其中保存了系统对作业进行管理和调度所需的全部信息. 3．作业调度 作业调度功能： 1.记录已进入系统的各作业的情况（JCB，Job Control Block）； 2.按一定的调度算法，从后备作业中选择一个或几个作业进入系统内存； 3.为被选中的作业创建进程，并且为其申请系统资源； 4.作业结束后作善后处理工作。 3．作业调度 3．作业调度 每次执行作业调度时，都须做出以下两个决定 　1) 决定接纳多少个作业 作业调度每次要接纳多少个作业进入内存，取决于多道程序度(Degree of Multiprogramming)， 　2) 决定接纳哪些作业 应将哪些作业从外存调入内存，这将取决于所采用的调度算法。 3.1.2 低级调度 通常也称为进程调度、微观调度或短程调度 调度的对象是进程(或内核级线程)。 进程调度是最基本的一种调度，在三种OS中都有。 1．低级调度的功能 低级调度的任务是控制协调进程对CPU的竞争。 (1) 保存处理机的现场信息。 (2) 按某种算法选取进程。 (3) 把处理器分配给进程。 2．进程调度中的三个基本机制 为了实现进程调度，应具有如下三个基本机制： (1) 排队器。将系统中所有的就绪进程按照一定的方式排成一个或多个队列。 (2) 分派器。将处理机分配给从就绪队列中选定的进程 (3) 上下文切换机制。当对处理机进行切换时，会发生两对上下文切换操作。 3．进程调度方式 进程调度可采用下述两种调度方式。 非抢占方式(Nonpreemptive Mode) 调度因素： 正在执行的进程执行完毕，或因发生某事件而不能再继续执行； 执行中的进程因提出I/O请求而暂停执行； 在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。 3．进程调度方式 2) 抢占方式(Preemptive Mode) 抢占的原则有： 优先权原则：优先权高的可以抢占优先级低的进程的处理机。 短作业（进程）优先原则：短作业（进程）可以抢占长作业（进程）的处理机。 时间片原则：各进程按时间片运行，一个时间片用完时，停止该进程执行重新进行调度。 3.1.3 中级调度 中级调度又称为交换调度或中程调度（Medium-Term Scheduling）。 为提高系统吞吐量和内存利用率而引入的一内------外存对换功能（换出时，进程为挂起状态） 运行频率：低中高。 3.1 高级、中级和低级调度 3.2 调度队列模型和调度准则 3.2.1　调度队列模型 1．仅有进程调度的调度队列模型 1．仅有进程调度的调度队列模型 每个进程在执行时都