第三章 处理机调度与死锁
目录
3.1 处理机调度的层次和调度算法的目标
在多道程序环境下，进程数目往往多于处理机数目。这就要求系统能够按某种算法，动态的把处理机分配给就绪队列中的一个进程，使之执行。
分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能，在很大程度上取决于处理机调度的性能。
因此，处理机(cpu)调度便成为OS设计的中心问题之一。
3.1.1处理机调度的层次
一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历下述三级调度。
1. 高级调度（High Scheduling）
又称为作业调度或长程调度（Long-Term Scheduling），用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后将新创建的进程排在就绪队列上，准备执行。
因此有时也称作业调度为接纳调度（Admission Scheduling）。
批处理系统中，因作业进入系统后先驻留在外存，故需要有作业调度。在分时系统中为做到及时响应，作业被直接送入内存，故不需作业调度。在实时系统中，通常也不需作业调度。
在每次执行作业调度时，都须作出两个决定：
接纳多少作业——每次接纳多少作业进入内存，即允许多少个作业同时在内存中运行---多道程序度。其确定应根据系统的规模、运行速度等情况综合考虑。
接纳哪些作业——应接纳哪些作业从外存调入内存，取决于所采用的调度算法。如先来先服务，短作业优先等，在§3.2中详细介绍。
2.低级调度（Low Level Scheduling）
通常也称为进程调度或短程调度（Short-Term Scheduling），用来决定就绪队列中的哪个进程应获得处理机， 然后再由分派程序把处理机分配给该进程。为最基本的一种 调度，三种OS中都有
进程调度可采用下述两种调度方式：
◼ 非抢占方式（Non-preemptive Mode）
一旦把处理机分配给某进程后，便让该进程一直执行， 直至该进程完成或发生某事件而被阻塞时，才把处理机分 配给其他进程，决不允许进程抢占已分配出去的处理机。
评价：实现简单、系统开销小；适用于大多数的批处理OS， 但在要求比较严格的实时系统中，不宜采用这种调度方式
◼ 抢占方式（Preemptive Mode）
允许调度程序根据某种原则，去暂停某个正在执行的进程， 将处理机重新分配给另一进程。 抢占的原则：
➢ 优先权原则：优先权高的可以抢占优先级低的进程的处理机。
➢ 短作业（进程）优先原则：短作业（进程）可以抢占长作业 （进程）的处理机。
➢ 时间片原则：各进程按时间片运行，一个时间片用完时，停止 该进程执行重新进行调度。
3. 中级调度（Intermediate-Level Scheduling）
又称中程调度（Medium-Term Scheduling）。引入目的是为了提高内存利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调之外存去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。
中级调度实际上就是存储器管理中的对换功能，将在§4.4中详述。
进程调度的运行频率最高，在分时系统中通常是10~100ms便进行一次进程调度，因而进程调度算法不能太复杂，以免占用太多的CPU时间。
作业调度是发生在一个作业运行完毕，退出系统，而需要重新调度一个作业进入内存时，故作业调度的周期较长，大约几分钟一次。因而也允许作业调度算法花费较多的时间。
中级调度的运行频率，基本上介于进程调度和作业调度之间。
不论高级、中级或者低级调度，都涉及到进程队列，由此形成了三种类型的调度队列模型：
1.仅有进程调度的调度队列模型
2.具有高级和低级调度的调度队列模型
3.同时具有三级调度的调度队列模型
作业调度 解决的是从后备作业中选择作业装入内存
调度算法 解决的是从内存中选择作业使用cpu
3.1.2 处理机调度的算法的目标
3.2 作业与作业调度
3.3 进程调度
3.4 实时调度
3.5 死锁的概述
3.6 预防死锁
3.7 避免死锁