操作系统课件之第三章1.pptVIP

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