教学课件第5章 进程调度与死锁.ppt

《教学课件第5章 进程调度与死锁.ppt》由会员分享，可在线阅读，更多相关《教学课件第5章 进程调度与死锁.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第 5 章章进程调度与死锁进程调度与死锁本章内容本章内容p5.1 进程调度的基本概念进程调度的基本概念 p5.2 进程调度的功能和原因进程调度的功能和原因p5.3 进程调度算法进程调度算法p5.4 死锁死锁 p5.5 Linux进程调度进程调度 本章学习目标本章学习目标q了解进程调度的基本概念了解进程调度的基本概念q掌握进程调度的算法掌握进程调度的算法q理解死锁的概念理解死锁的概念q掌握产生死锁的原因和必要条件掌握产生死锁的原因和必要条件q掌握银行家算法的使用方法掌握银行家算法的使用方法45.1 进程调度的基本概念进程调度的基本概念 1. 进程调度的定义进程调度的定义q 进程调度也称为处理机

2、调度，它决定将处理机分进程调度也称为处理机调度，它决定将处理机分配给就绪队列里的某个进程，并使之运行，从而配给就绪队列里的某个进程，并使之运行，从而协调和控制各进程对处理机的使用。相应的执行协调和控制各进程对处理机的使用。相应的执行处理机分配的程序称为进程调度程序。处理机分配的程序称为进程调度程序。 55.1 进程调度的基本概念进程调度的基本概念 65.1 进程调度的基本概念进程调度的基本概念 2. 进程调度的方式进程调度的方式q 非剥夺方式非剥夺方式：在采用这种调度方式下，进程调度：在采用这种调度方式下，进程调度程序一旦把处理机分配给某个进程后，便让该进程序一旦把处理机分配给某个进程后，便让

3、该进程一直执行，直到该进程运行完毕或发生某事件程一直执行，直到该进程运行完毕或发生某事件而阻塞时，才把处理机分配给另一个进程。而阻塞时，才把处理机分配给另一个进程。 q 剥夺方式：在采用这种调度方式下，当一个进程剥夺方式：在采用这种调度方式下，当一个进程正在运行时，系统可以基于某种原则，暂停该进正在运行时，系统可以基于某种原则，暂停该进程的执行，将分配给它的处理机重新分配给另一程的执行，将分配给它的处理机重新分配给另一进程。进程。 75.2 进程调度的功能和原因进程调度的功能和原因 1. 进程调度的功能进程调度的功能 q 记录系统中所有进程的执行情况记录系统中所有进程的执行情况 。 q 选择进

4、程占用处理机选择进程占用处理机 。 q 进行进程的上下文切换。进行进程的上下文切换。85.2 进程调度的功能和原因进程调度的功能和原因 2. 进程调度的原因进程调度的原因 q 正在执行的进程执行完毕。正在执行的进程执行完毕。q 正在执行的进程提出正在执行的进程提出I/O请求后被阻塞。请求后被阻塞。q 执行中的进程调用了执行中的进程调用了P原语操作，从而因资源不原语操作，从而因资源不足而被阻塞；或调用了足而被阻塞；或调用了V原语操作激活了等待资原语操作激活了等待资源的阻塞进程。源的阻塞进程。q 在剥夺调度方式中，当就绪队列中的某进程的优在剥夺调度方式中，当就绪队列中的某进程的优先级高于当前执行进

5、程的优先级时，引起进程调先级高于当前执行进程的优先级时，引起进程调度。度。q 在分时系统中时间片已经用完。在分时系统中时间片已经用完。95.3 进程调度算法进程调度算法 1. 先来先服务调度算法先来先服务调度算法 q 先来先服务（先来先服务（FCFS）算法以到达就绪队列的先）算法以到达就绪队列的先后次序为标准来选择占用处理机的进程。每次调后次序为标准来选择占用处理机的进程。每次调度都从就绪队列中，选择一个最先进入该队列的度都从就绪队列中，选择一个最先进入该队列的进程，为之分配处理机。一个进程一旦占有了处进程，为之分配处理机。一个进程一旦占有了处理机，便一直执行下去，直到正常结束或因等待理机，便

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

7、 进程调度算法进程调度算法 调度算法调度算法 进程情况进程情况进程名进程名A B C D E平均平均到达时间到达时间0 1 2 3 4 服务时间服务时间4 3 5 2 4FCFS( a )完成时间完成时间4 7 12 14 18周转时间周转时间4 6 10 11 149带权周转时间带权周转时间1 2 2 5.5 3.52.8SPF( b )完成时间完成时间4 9 18 6 13周转时间周转时间4 8 16 3 98带权周转时间带权周转时间1 2.67 3.1 1.5 2.252.1q周转时间周转时间=完成时间完成时间-达到时间达到时间q平均周转时间平均周转时间q带权周转时间带权周转时间135.

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

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

10、. 优先级调度算法优先级调度算法 为进程指定优先级的方法有两种，即静态优先级为进程指定优先级的方法有两种，即静态优先级和动态优先级。和动态优先级。 q 动态优先级动态优先级q 动态优先级是指，在创建进程时所赋予的优先级动态优先级是指，在创建进程时所赋予的优先级，是可以随进程的执行或随其等待时间的增加而，是可以随进程的执行或随其等待时间的增加而改变的，以便获得更好的调度性能。改变的，以便获得更好的调度性能。q 例如，如果规定在就绪队列中的进程，其优先级例如，如果规定在就绪队列中的进程，其优先级随等待时间的增长以速率随等待时间的增长以速率a增加。增加。 165.3 进程调度算法进程调度算法 4.

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

12、配给就绪队列中第一个进程，使之投入运行。运行。 175.3 进程调度算法进程调度算法 4. 时间片轮转调度算法时间片轮转调度算法 时间片长短的确定原则是：既要保证系统各时间片长短的确定原则是：既要保证系统各个用户进程及时得到相应，又不要由于时间片太个用户进程及时得到相应，又不要由于时间片太短而增加调度的开销，降低系统效率。短而增加调度的开销，降低系统效率。 系统的响应时间和时间片的关系，可以表示系统的响应时间和时间片的关系，可以表示为：为：T=Nq，其中，其中T为系统的响应时间，为系统的响应时间，q为时间为时间片的大小，片的大小，N为就绪队列中进程的数目。为就绪队列中进程的数目。 时间片的选择

13、必须适当，通常为时间片的选择必须适当，通常为100ms。 185.3 进程调度算法进程调度算法 4. 时间片轮转调度算法时间片轮转调度算法 q 时间片的长短通常由以下因素决定：时间片的长短通常由以下因素决定：q （1）系统的响应时间。）系统的响应时间。q （2）就绪队列中进程的数目。）就绪队列中进程的数目。q （3）进程的转换时间。）进程的转换时间。q （4）计算机的处理能力，计算机的速度越高，）计算机的处理能力，计算机的速度越高，时间片就可越短。时间片就可越短。195.3 进程调度算法进程调度算法 5. 多级反馈队列调度算法多级反馈队列调度算法 q 多级反馈队列调度算法是时间片轮转调度算法与

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

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

16、法 5. 多级反馈队列调度算法多级反馈队列调度算法 每一个被调度的进程如果在规定的时间片内运行每一个被调度的进程如果在规定的时间片内运行完毕，则撤离系统；完毕，则撤离系统； 如果因提出如果因提出I/O请求或等待某事件发生，则放弃请求或等待某事件发生，则放弃处理机，进入相应阻塞队列；处理机，进入相应阻塞队列；235.3 进程调度算法进程调度算法 5. 多级反馈队列调度算法多级反馈队列调度算法 如果在规定的时间片内没有运行完毕，则将被插如果在规定的时间片内没有运行完毕，则将被插入到下一级队列的末尾，等待调度。入到下一级队列的末尾，等待调度。 当有新进程进入到比当前运行进程所在就绪队列当有新进程进入

17、到比当前运行进程所在就绪队列优先级更高的就绪队列时，进程调度程序将立即优先级更高的就绪队列时，进程调度程序将立即剥夺正在运行进程的处理机，将它插入到刚才所剥夺正在运行进程的处理机，将它插入到刚才所在就绪队列的末尾，重新进行处理机调度。在就绪队列的末尾，重新进行处理机调度。 245.4 死锁死锁 q 5.4.1 死锁产生的原因和必要条件死锁产生的原因和必要条件 q 5.4.2 解决死锁的方法解决死锁的方法 255.4.1 死锁产生的原因和必要条件死锁产生的原因和必要条件 1. 死锁产生的原因死锁产生的原因 q 竞争资源。竞争资源。q 进程推进顺序不当。进程推进顺序不当。265.4.1 死锁产生的

18、原因和必要条件死锁产生的原因和必要条件 2. 死锁产生的必要条件死锁产生的必要条件 q 互斥条件：并发进程所要求分配的资源是不能同互斥条件：并发进程所要求分配的资源是不能同时被两个以上进程使用的，进程对它所需要的资时被两个以上进程使用的，进程对它所需要的资源进行排他性使用，即在一段时间内某资源只能源进行排他性使用，即在一段时间内某资源只能由一个进程使用。由一个进程使用。q 请求和保持条件：当进程因请求资源而阻塞时，请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放。对已获得的资源保持不放。q 不剥夺条件：进程所获得的资源在未使用完毕之不剥夺条件：进程所获得的资源在未使用完毕之前，

19、不能被其他进程强行剥夺，而只能在使用完前，不能被其他进程强行剥夺，而只能在使用完时由自己释放。时由自己释放。q 环路等待条件：存在一种进程循环链，链中每一环路等待条件：存在一种进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。个进程已获得的资源同时被下一个进程所请求。275.4.2 解决死锁的方法解决死锁的方法 1. 预防死锁预防死锁 q 破坏破坏“请求和保持条件请求和保持条件”：为破坏这一条件，系：为破坏这一条件，系统要求所有进程在运行前一次性地申请其所需的统要求所有进程在运行前一次性地申请其所需的全部资源。全部资源。q 破坏破坏“不剥夺条件不剥夺条件”：该方法规定，一个已经获：

20、该方法规定，一个已经获得了某些资源的进程，若新的资源请求不能立即得了某些资源的进程，若新的资源请求不能立即得到满足，它必须释放其已占有的所有资源，以得到满足，它必须释放其已占有的所有资源，以后再需要时重新申请。后再需要时重新申请。q 破坏破坏“环路等待条件环路等待条件”：在该方法中，将系统中：在该方法中，将系统中的所有资源按类型进行线性排队，并赋予不同的的所有资源按类型进行线性排队，并赋予不同的序号。序号。 285.4.2 解决死锁的方法解决死锁的方法 2. 避免死锁避免死锁 q 避免死锁是指系统采用动态分配资源的策略，保避免死锁是指系统采用动态分配资源的策略，保证系统不进入可能导致系统陷入死

21、锁状态的所谓证系统不进入可能导致系统陷入死锁状态的所谓不安全状态，以避免死锁的发生。不安全状态，以避免死锁的发生。q 为了避免死锁，系统在动态分配资源之前应先计为了避免死锁，系统在动态分配资源之前应先计算出此次资源分配的安全性。若此次分配不会导算出此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。否则，令进程等待。295.4.2 解决死锁的方法解决死锁的方法 2. 避免死锁避免死锁 银行家算法中的数据结构银行家算法中的数据结构q 可利用资源向量可利用资源向量Available。q 最大需求矩阵最大需求矩阵

22、Max。q 分配矩阵分配矩阵Allocation。q 需求矩阵需求矩阵Need。 305.4.2 解决死锁的方法解决死锁的方法 2. 避免死锁避免死锁 银行家算法银行家算法 q (1)如果如果Requesti jNeedi,j，则跳转到第，则跳转到第2步步；否则认为出错，因为进程；否则认为出错，因为进程Pi已经超过了它的最已经超过了它的最大需求量。大需求量。q (2)如果如果Requesti jAvailablej，则跳转到第，则跳转到第3步；否则步；否则Pi必须等待，因为没有足够的资源。必须等待，因为没有足够的资源。315.4.2 解决死锁的方法解决死锁的方法 2. 避免死锁避免死锁 银行家

23、算法银行家算法 q (3)假定系统可以分配给进程假定系统可以分配给进程Pi所请求的资源，所请求的资源，并按如下方式修改数据结构中数值：并按如下方式修改数据结构中数值： AvailablejAvailablejRequesti j； Allocationi,jAllocationi,jRequesti j； Needi,jNeedi,jRequesti j；q (4)系统执行安全性算法，检查此次资源分配后系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资，系统是否处于安全状态。若安全，才正式将资源分配给进程源分配给进程Pi，以完成本次分配；否则，将本，以完成本次分配

24、；否则，将本次的试探分配作废，恢复原来的资源分配状态，次的试探分配作废，恢复原来的资源分配状态，让进程让进程Pi等待。等待。325.4.2 解决死锁的方法解决死锁的方法 2. 避免死锁避免死锁 安全性算法安全性算法 q (1)设置设置2个向量：工作向量个向量：工作向量Work，它表示系统，它表示系统可提供给进程继续运行所需的各类资源数目，它可提供给进程继续运行所需的各类资源数目，它含有含有m个元素，执行安全性算法时，个元素，执行安全性算法时，Work= Allocation；判断向量；判断向量Finish，它表示系统是否，它表示系统是否有足够的资源分配给进程使之运行完成，开始时有足够的资源分配

25、给进程使之运行完成，开始时先使先使Finishi=0；当有足够资源分配给进程时，；当有足够资源分配给进程时，令令Finishi=1。q (2) 从进程集合中找出一个能满足下列条件的进从进程集合中找出一个能满足下列条件的进程：程： Finishi= =0 & Needi,jWorkj 若找到，则执行步骤，否则执行步骤。若找到，则执行步骤，否则执行步骤。 若找到，则执行步骤，否则执行步骤。若找到，则执行步骤，否则执行步骤。335.4.2 解决死锁的方法解决死锁的方法 2. 避免死锁避免死锁 安全性算法安全性算法 q (3)当进程当进程Pi获得资源后，便可顺利执行，直到获得资源后，便可顺利执行，直到

26、运行完毕释放分配给它的资源，故应执行：运行完毕释放分配给它的资源，故应执行： WorkjWorkjAllocationi,j； Finishi1； go to step 2；q (4)如果所有进程的如果所有进程的Finishi都等于都等于1，则表示系，则表示系统处于安全状态，否则系统处于不安全状态。统处于安全状态，否则系统处于不安全状态。345.4.2 解决死锁的方法解决死锁的方法 3. 检测死锁检测死锁 q 死锁检测的任务就是确定系统中是否存在死锁，死锁检测的任务就是确定系统中是否存在死锁，并试图找出陷入死锁的进程和资源。通常检测死并试图找出陷入死锁的进程和资源。通常检测死锁的方式是通过资源

27、分配图的化简来确定资源分锁的方式是通过资源分配图的化简来确定资源分时是否有循环等待现象。时是否有循环等待现象。355.4.2 解决死锁的方法解决死锁的方法 4. 解除死锁解除死锁 q 资源剥夺法：由于死锁是由进程竞争资源而引起资源剥夺法：由于死锁是由进程竞争资源而引起的，所以可从一些进程那里强行剥夺足够数量的的，所以可从一些进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态。资源分配给死锁进程，以解除死锁状态。q 撤消进程法撤消进程法:按照某种顺序逐渐地撤消已经死锁按照某种顺序逐渐地撤消已经死锁的进程，直到获得为解除死锁所需要的足够可用的进程，直到获得为解除死锁所需要的足够可用资源为

28、止。在极端的情况下，这种方法可能造成资源为止。在极端的情况下，这种方法可能造成除一个死锁进程外其余的死锁进程全部被撤消。除一个死锁进程外其余的死锁进程全部被撤消。365.5 Linux进程调度进程调度 1. 进程调度时机进程调度时机 q Linux的调度程序是一个叫的调度程序是一个叫Schedule（）的函（）的函数，调度时机包括：数，调度时机包括：q (1)进程要调用进程要调用sleep（）或（）或exit（）等函数进行（）等函数进行状态转换，这些函数会主动调用调度程序进行进状态转换，这些函数会主动调用调度程序进行进程调度；程调度；q (2)由于进程的时间片是由时钟中断来更新的，由于进程的时

29、间片是由时钟中断来更新的，因此，这种情况和时机因此，这种情况和时机4是一样的。是一样的。q (3)当设备驱动程序执行长而重复的任务时，直当设备驱动程序执行长而重复的任务时，直接调用调度程序。在每次反复循环中，驱动程序接调用调度程序。在每次反复循环中，驱动程序都检查都检查need_resched的值，如果必要，则调用的值，如果必要，则调用调度程序调度程序schedule()主动放弃主动放弃CPU。375.5 Linux进程调度进程调度 2. 调度策略调度策略 q 在在 Linux有三种调度策略有三种调度策略:q SCHED_ORHER:普通进程，基于优先级进行调普通进程，基于优先级进行调度。度。

30、q SCHED_FIFO：实时进程，实现一种简单的先：实时进程，实现一种简单的先进先出的调度算法。进先出的调度算法。q SCHED_RR：实时进程，基于时间片的：实时进程，基于时间片的SCHED_FIFO,实时轮流调度算法。实时轮流调度算法。385.5 Linux进程调度进程调度 3. 调度算法调度算法 q 就绪队列就绪队列 runqueue：runqueue 是是 调度器的关调度器的关键技术所在键技术所在,它用于存放特定它用于存放特定 CPU 上的就绪进程上的就绪进程队列信息队列信息,其中包含每个其中包含每个 CPU 的调度信息。的调度信息。 q task_struct 结构：结构：Linux内核使用内核使用 task_struct 结构来表示进程。结构来表示进程。 q 优先级数组：每个处理器的就绪队列都有两个优优先级数组：每个处理器的就绪队列都有两个优先级数组（先级数组（acitve数组和数组和expired数组）数组）,它们是它们是 prio_array 类型的结构体。类型的结构体。