第5章 进程调度与死锁

第5章进程调度与死锁本章内容5.1进程调度的基本概念5.2进程调度的功能和原因5.3进程调度算法5.4死锁5.5Linux进程调度

本章学习目标了解进程调度的基本概念掌握进程调度的算法理解死锁的概念掌握产生死锁的原因和必要条件掌握银行家算法的使用方法45.1进程调度的基本概念进程调度的定义进程调度也称为处理机调度，它决定将处理机分配给就绪队列里的某个进程，并使之运行，从而协调和控制各进程对处理机的使用。相应的执行处理机分配的程序称为进程调度程序。

55.1进程调度的基本概念65.1进程调度的基本概念进程调度的方式非剥夺方式：在采用这种调度方式下，进程调度程序一旦把处理机分配给某个进程后，便让该进程一直执行，直到该进程运行完毕或发生某事件而阻塞时，才把处理机分配给另一个进程。

剥夺方式：在采用这种调度方式下，当一个进程正在运行时，系统可以基于某种原则，暂停该进程的执行，将分配给它的处理机重新分配给另一进程。75.2进程调度的功能和原因进程调度的功能记录系统中所有进程的执行情况。选择进程占用处理机。进行进程的上下文切换。85.2进程调度的功能和原因进程调度的原因正在执行的进程执行完毕。正在执行的进程提出I/O请求后被阻塞。执行中的进程调用了P原语操作，从而因资源不足而被阻塞；或调用了V原语操作激活了等待资源的阻塞进程。在剥夺调度方式中，当就绪队列中的某进程的优先级高于当前执行进程的优先级时，引起进程调度。在分时系统中时间片已经用完。95.3进程调度算法先来先服务调度算法

先来先服务（FCFS）算法以到达就绪队列的先后次序为标准来选择占用处理机的进程。每次调度都从就绪队列中，选择一个最先进入该队列的进程，为之分配处理机。一个进程一旦占有了处理机，便一直执行下去，直到正常结束或因等待某事件的发生而让出处理机。

105.3进程调度算法短进程优先调度算法

短进程优先（SPF）调度算法，是指对短进程优先调度的算法。该算法从就绪队列中选择一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行完成，直到正常结束或因等待某事件的发生而让出处理机，再重新调度。

115.3进程调度算法调度算法

进程情况进程名ABCDE平均到达时间01234服务时间43524FCFS(a)完成时间47121418周转时间461011149带权周转时间1225.53.52.8SPF(b)完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.1周转时间=完成时间-达到时间平均周转时间带权周转时间135.3进程调度算法优先级调度算法

该算法是一种常用的进程调度算法，它是指当发生进程调度时，将CPU分配给就绪队列中优先级最高的进程。该算法首要的问题就是系统必须为进程指定一个优先级来表示该进程所享有的调度优先权。

145.3进程调度算法优先级调度算法

为进程指定优先级的方法有两种，即静态优先级和动态优先级。

（1）静态优先级静态优先级是在进程创建时确定的，且在进程的整个运行期间保持不变。确定进程静态优先级的依据有：①进程的类型。根据是系统进程还是用户进程，赋予不同的优先级。通常系统进程的优先级高于一般用户进程的优先级。②进程对资源的需求。如进程的估计运行时间、内存需求量、I/O设备的需求数量等，对这些资源要求少的进程赋予较高的优先级。③用户申请的优先级。这是由用户进程的紧迫程度以及用户所付出费用的多少来确定优先级的。静态优先级调度算法虽然简单，系统开销小，但不能动态反映进程的特点，系统调度性差。在现代的操作系统中，大多采用动态优先级的调度算法。155.3进程调度算法优先级调度算法

为进程指定优先级的方法有两种，即静态优先级和动态优先级。

动态优先级动态优先级是指，在创建进程时所赋予的优先级，是可以随进程的执行或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，如果规定在就绪队列中的进程，其优先级随等待时间的增长以速率a增加。165.3进程调度算法时间片轮转调度算法

时间片轮转调度算法主要出现在分时操作系统中，该算法是将CPU的处理时间分成固定大小的时间片。如果就绪队列中的一个进程在被调度选中之后，在系统规定的时间片内没有运行完毕，那么该进程将被强迫释放处理机而插入就绪队列的末尾，等待下一次调度。同时，进程调度程序将会把CPU分配给就绪队列中第一个进程，使之投入运行。

175.3进程调度算法时间片轮转调度算法

时间片长短的确定原则是：既要保证系统各个用户进程及时得到相应，又不要由于时间片太短而增加调度的开销，降低系统效率。系统的响应时间和时间片的关系，可以表示为：T=Nq，其中T为系统的响应时间，q为时间片的大小，N为就绪队列中进程的数目。时间片的选择必须适当，通常为100ms。

185.3进程调度算法时间片轮转调度算法

时间片的长短通常由以下因素决定：（1）系统的响应时间。（2）就绪队列中进程的数目。（3）进程的转换时间。（4）计算机的处理能力，计算机的速度越高，时间片就可越短。195.3进程调度算法多级反馈队列调度算法

多级反馈队列调度算法是时间片轮转调度算法与优先级调度算法的结合。实行该算法时，系统将设置多个就绪队列，每个就绪队列具有不同的调度优先级，可以获得不同长度的时间片。从第一级就绪队列到最后一级就绪队列，调度优先级越来越低，所获得的时间片越来越长。205.3进程调度算法多级反馈队列调度算法

215.3进程调度算法多级反馈队列调度算法

具体的调度方法是：当一个新进程进入内存后，首先被插入到第一级就绪队列的末尾，按先来先服务原则等待调度。系统调度时，总是从第一级就绪队列开始，仅当第一级就绪队列为空时，才调度第二级就绪队列中的进程；如此下去，只有前面n-1级就绪队列都为空时，才去调度最后第n级就绪队列中的进程。225.3进程调度算法多级反馈队列调度算法

每一个被调度的进程如果在规定的时间片内运行完毕，则撤离系统；如果因提出I/O请求或等待某事件发生，则放弃处理机，进入相应阻塞队列；235.3进程调度算法多级反馈队列调度算法

如果在规定的时间片内没有运行完毕，则将被插入到下一级队列的末尾，等待调度。当有新进程进入到比当前运行进程所在就绪队列优先级更高的就绪队列时，进程调度程序将立即剥夺正在运行进程的处理机，将它插入到刚才所在就绪队列的末尾，重新进行处理机调度。

245.4死锁5.4.1死锁产生的原因和必要条件

5.4.2解决死锁的方法

255.4.1死锁产生的原因和必要条件死锁产生的原因

竞争资源。进程推进顺序不当。265.4.1死锁产生的原因和必要条件死锁产生的必要条件

互斥条件：并发进程所要求分配的资源是不能同时被两个以上进程使用的，进程对它所需要的资源进行排他性使用，即在一段时间内某资源只能由一个进程使用。请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放。不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，而只能在使用完时由自己释放。环路等待条件：存在一种进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。275.4.2解决死锁的方法预防死锁

破坏“请求和保持条件”：为破坏这一条件，系统要求所有进程在运行前一次性地申请其所需的全部资源。破坏“不剥夺条件”：该方法规定，一个已经获得了某些资源的进程，若新的资源请求不能立即得到满足，它必须释放其已占有的所有资源，以后再需要时重新申请。破坏“环路等待条件”：在该方法中，将系统中的所有资源按类型进行线性排队，并赋予不同的序号。

285.4.2解决死锁的方法避免死锁

避免死锁是指系统采用动态分配资源的策略，保证系统不进入可能导致系统陷入死锁状态的所谓不安全状态，以避免死锁的发生。为了避免死锁，系统在动态分配资源之前应先计算出此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。295.4.2解决死锁的方法避免死锁

银行家算法中的数据结构可利用资源向量Available。最大需求矩阵Max。分配矩阵Allocation。需求矩阵Need。

305.4.2解决死锁的方法避免死锁

银行家算法

(1)如果Requesti[j]≤Need[i,j]，则跳转到第2步；否则认为出错，因为进程Pi已经超过了它的最大需求量。(2)如果Requesti[j]≤Available[j]，则跳转到第3步；否则Pi必须等待，因为没有足够的资源。315.4.2解决死锁的方法避免死锁

银行家算法

(3)假定系统可以分配给进程Pi所请求的资源，并按如下方式修改数据结构中数值：

Available[j]＝Available[j]－Requesti[j]；

Allocation[i,j]＝Allocation[i,j]＋Requesti[j]；

Need[i,j]＝Need[i,j]－Requesti[j]；(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。325.4.2解决死锁的方法避免死锁

安全性算法

(1)设置2个向量：工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，执行安全性算法时，Work=Allocation；判断向量Finish，它表示系统是否有足够的资源分配给进程使之运行完成，开始时先使Finish[i]=0；当有足够资源分配给进程时，令Finish[i]=1。(2)从进程集合中找出一个能满足下列条件的进程：

Finish[i]==0&&Need[i,j]≤Work[j]若找到，则执行步骤③，否则执行步骤④。若找到，则执行步骤③，否则执行步骤④。335.4.2解决死锁的方法避免死锁

安全性算法

(3)当进程Pi获得资源后，便可顺利执行，直到运行完毕释放分配给它的资源，故应执行：

Work[j]＝Work[j]＋Allocation[i,j]；

Finish[i]＝1；gotostep2；(4)如果所有进程的Finish[i]都等于1，则表示系统处于安全状态，否则系统处于不安全状态。345.4.2解决死锁的方法检测死锁

死锁检测的任务就是确定系统中是否存在死锁，并试图找出陷入死锁的进程和资源。通常检测死锁的方式是通过资源分配图的化简来确定资源分时是否有循环等待现象。355.4.2解决死锁的方法解除死锁

资源剥夺法：由于死锁是由进程竞争资源而引起的，所以可从一些进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态。撤消进程法:按照某种顺序逐渐地撤消已经死锁的进程，直到获得为解除死锁所需要的足够可用资源为止。在极端的情况下，这种方法可能造成除一个死锁进程外其余的死锁进程全部被撤消。365.5Linux进程调度进程调度时机

Linux的调度程序是一个叫Schedule（）的函数，调度时机包括：(1)进程