第三章_处理机调度与死锁.docVIP

第三章 处理机调度与死锁 3.1 处理机调度的基本概念 在多道程序系统中，一个作业被提交后，必须经过处理机调度后，方能因获得处理机而执行。 对于批量型作业而言，通常需要经历作业调度(高级调度)和进程调度(低级调度)两个调度过程后，方能获得处理机； 对于终端型作业，则通常只须经过进程调度。 在较完善的操作系统中，往往还设置了中级调度（交换调度）。 对于上述的每一级调度，又都可采用不同的调度方式和调度算法。 3.1.1 分级调度 一个作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历高级调度(High Scheduling)、中级调度(Intermediate-Level Scheduling)和低级调度(Low Level Scheduling)。 1. 高级调度 高级调度又称为作业调度或长程调度（Long-Term Scheduling），用于决定把外存上处于后备队列中的那些作业调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。因此，有时也把作业调度称为接纳调度(Admission scheduling)。 在每次执行作业调度时，都须做出以下两个决定： 1) 接纳多少个作业（取决于多道程序度）? 2) 接纳哪些作业（根据不同的算法来确定）? 在分时与实时系统中无作业的概念 在批处理系统中，作业进入系统后，是先驻留在外存上的，因此需要有作业调度的过程，以便将它们分批地装入内存。 然而在分时系统中，为了做到及时响应，用户通过键盘输入的命令或数据等，都是被直接送入内存的，因而无须再配置作业调度机制。类似地，在实时系统中，通常也不需要作业调度。 2. 低级调度 通常也把低级调度称为进程调度或短程调度(Short-Term Scheduling)，用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序(Dispatcher)执行把处理机分配给该进程的具体操作。进程调度是最基本的一种调度，在三种类型的OS中，都必须配置这级调度。 进程调度可采用下述两种调度方式：非抢占方式(Non-preemptive Mode)；抢占方式(preemptive Mode) 1) 非抢占方式 采用这种调度方式时，一旦某个进程得到处理后，便让它一直执行，直到进程完成或发生某个事件被阻塞，才允许把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。 在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个：① 执行； ②执行中的进程因提出I/O请求而暂停执行；③在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、block原语、wakeup原语等。 这种调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求，因而可能造成难以预料的后果。 在要求比较严格的实时系统中，不宜采用这种调度方式。 2) 抢占方式 这种调度方式，允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。 抢占的原则有: (1)优先权原则。通常是对一些重要的和紧急的作业，赋予较高的优先权。并允许优先权高的新到进程抢占当前进程的处理机。 (2)短作业(进程)优先原则。短作业(进程)可以抢占当前较长作业(进程)的处理机。 (3)时间片原则。各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。 3. 中级调度 中级调度又称中程调度(Medium-Term Scheduling)。引入主要目的是为了提高内存利用率和系统吞吐量。 为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程专重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。 中级调度实际上就是存储器管理中的对换功能 ，因此中级调度又被 称为交换(Swap)调度。 3.1.2 调度队列模型 当OS对作业和进程调度时，都必须按一定的规则将作业或进程排列，形成队列。 用于调度的队列模型有：仅有进程调度的队列模型；具有高级和低级调度的队列模型； 同时具有三级调度的队列模型 1. 仅有进程调度的队列模型 分时系统中，进程执行时，可能出现以下三种情况： ①任务在给定的时间片内已经完成，该进程便在释放处理机后进入完成状态； ②任务在本次分得的时间片内未完成，OS便将该任务再放入就绪队列的末尾； ③进程因为某事件而被阻塞后，被OS放入阻塞队列。 2. 具有高级和低级调度的队列模型 在批处理系统中，不仅需要进程调度，而且还需有作业调度。 它与上一模型的主要区别在于