搜索
第三章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除第三章处理机调度与死锁第三章处理机调度与死锁3.1处理机调度的基本概念在多道程序环境下，内存中有多个进程，其数目往往多余处理机数目，这要求系统需要按照某种算法，将处理机分配给就绪队列中的一个进程，分配处理机的任务是由处理机调度程序完成的。处理机调度是操作系统设计的中心问题之一。第三章处理机调度与死锁3.1.1高级、中级和低级调度1.高级调度(HighScheduling)2.低级调度(LowLevelScheduling)3.中级调度(Intermediate-LevelScheduling)第三章处理机调度与死锁图3-1仅具有进程调度的调度队列模型就绪队列阻塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完1.仅有进程调度的调度队列模型第三章处理机调度与死锁图3-2具有高、低两级调度的调度队列模型就绪队列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件2出现……等待事件n事件n出现后备队列……2.具有高级和低级调度的调度队列模型主要区别:就绪队列的形式设置多个阻塞队列第三章处理机调度与死锁图3-3具有三级调度时的调度队列模型就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现3.同时具有三级调度的调度队列模型主要区别:增加就绪挂起队列和阻塞挂起队列第三章处理机调度与死锁3.3调度算法3.3.1先来先服务（FCFS）和短作业优先调度算法（SJF）3.3.2高优先权优先调度算法（HRF）3.3.3时间片轮转调度算法第三章处理机调度与死锁3.3.2高响应比优先调度算法优先权调度算法：在作业调度或者是进程调度时，将处理机分配给就绪队列中优先权最高的进程。进一步划分：1、非抢占式优先权算法2、抢占式优先权算法第三章处理机调度与死锁3.3.2高响应比优先调度算法优先权如何确定：1、静态优先权创建进程时，确定此进程的优先权，且在整个运行期保持不变。确定优先权的依据1）进程类型（用户/系统）2）进程对资源的需求（多/少）3）用户要求（紧迫程度）静态优先权简单易行，但不够精确，因此仅在要求不高的系统中才使用静态优先权第三章处理机调度与死锁3.3.2最高优先权优先调度算法（优先数的确定）2动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。那么对于优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机。第三章处理机调度与死锁高响应比优先调度算法引入了动态优先权策略的优先调度算法第三章处理机调度与死锁高响应比优先调度算法要求服务时间要求服务时间等待时间优先权+=优先权的变化规律可描述为：由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当该作业（进程）的响应比RP据此，又可表示为：要求服务时间响应时间要求服务时间要求服务时间等待时间=+=要求服务时间=1+等待时间第三章处理机调度与死锁(1)如果作业的等待时间相同，则要求服务的时间愈短，其优先权(响应比)愈高，因而该算法有利于短作业。(2)当要求服务的时间相同时，作业的优先权(响应比)决定于其等待时间，等待时间愈长，其优先权(响应比)愈高，因而它实现的是先来先服务。(3)对于长作业，作业的优先级(响应比)可以随等待时间的增加而提高，当其等待时间足够长时，其优先级(响应比)便可升到很高，从而也可获得处理机。该算法既照顾了短作业，又考虑了作业到达的先后次序不会使长作业长期等待得不到服务，是一种比较算法。第三章处理机调度与死锁高响应比优先调度算法•每次调度时，计算每个后备作业的响应比Rpi，然后挑选响应比最高者，使其投入运行。作业提交时间运行时间开始时间完成时间TiWi18.02.08.010.02.01.028.50.510.110.62.14.239.00.110.010.11.111.049.50.210.610.81.36.5•调度顺序：1→3→2→4•T=1.625•W=5.675作业1结束时：Rp2=1+1.5/0.5=4Rp3=1+1.0/0.1=11Rp4=1+0.5/0.2=3.5调度作业3作业3结束时：Rp2=1+1.6/0.5=4.2Rp4=1+0.6/0.2=4调度作业267第三章处理机调度与死锁练习高响应比优先调度算法进程到达时间服务时间完成时间周转时间带权周转时间A03B26C44D65E82平均周转时间：带权平均周转时间：第三章处理机调度与死锁3.3.3基于时间片的轮转调度算法1)时间片轮转法（RoundRobin）在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行进程的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。第三章处理机调度与死锁3.3实时调度3.3.1实现实时调度的基本条件3.3.2实时调度算法的分类3.3.3常用的几种实时调度算法第三章处理机调度与死锁3.3.1实现实时调度的基本条件在实时操作系统中存在若干个实时进程，这种进程带有某种程度的紧迫性，因而对实时系统中的调度提出了某些特殊要求，前面介绍的调度算法并不能很好地满足系统对调度的要求，为此引入一种新的调度，即实时调度。第三章处理机调度与死锁3.3.1实现实时调度第三章处理机调度与死锁3.3.3常用的几种实时调度算法1.最早截止时间优先即EDF(EarliestDeadlineFirst)算法该算法是根据任务的开始截止时间来确定任务的优先级，开始截止时间越早，其优先级越高，调度程序在选择任务时，总是选择开始截止时间最早的任务，为之分配处理机。最早截止时间优先算法即可用于抢占式调度，也可用于非抢占式调度。第三章处理机调度与死锁3.3.3常用的几种实时调度算法1.非抢占式最早截止时间优先算法图3-7EDF算法用于非抢占调度方式1342开始截止时间任务执行任务到达12341342t第三章处理机调度与死锁3.3.3常用的几种实时调度算法2.抢占式最早截止时间优先算法周期任务是指计算机系统按一定周期到达并请求运行，下例中A,B在0秒同时到达。第三章处理机调度与死锁A1A2A3A4A6A5A7B1B1B2B3红色标注代表任务到达时间，白色为开始截止时间第三章处理机调度与死锁3.3.3常用的几种实时调度算法(续)2.最低松弛度优先即LLF(LeastLaxityFirst)算法•该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。•例如，一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100ms之前调度执行，该任务的紧急程度(松弛程度)为100ms。•又如，另一任务在400ms时必须完成，它本身需要运行150ms，则其松弛程度为250ms。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。•该算法主要用于可抢占调度方式中。第三章处理机调度与死锁练习•对于下面的5个非周期性实时任务，按最早开始截止时间优先调度算法应如何进行调度？进程到达时间执行时间开始截止时间A1020110B202020C402050D502090E602070第三章处理机调度与死锁0102030405060708090100110到达时间开始截止时间ABCDEBCEDA第三章处理机调度与死锁3.5产生死锁的原因和必要条件3.5.1死锁的概念和产生死锁的原因3.5.2产生死锁的必要条件3.5.3处理死锁的基本方法第三章处理机调度与死锁1.死锁的概念•所谓死锁(Deadlock)，是指多个进程因竞争资源而造成的一种僵局(Deadly-Embrace)，若无外力作用，这些进程都将永远不能再向前推进。2.产生死锁的原因•竞争资源•进程间推进顺序非法3.5.1死锁的概念和产生死锁的原因第三章处理机调度与死锁1)2)竞争非剥夺性资源3)竞争临时性资源1.竞争资源第三章处理机调度与死锁图3-12I/O设备共享时的死锁情况（竞争永久资源）R1R2P1P2P1:拥有R1;请求R2;P2:拥有R2;请求R1;第三章处理机调度与死锁图3-13进程之间通信时的死锁（竞争临时资源）S2P1S3P3S1P2P1:接收S3;发送S1;P2:接收S1;发送S2;P3:接收S2;发送S3;第三章处理机调度与死锁2.进程推进顺序不当引起死锁1)进程推进顺序合法2)第三章处理机调度与死锁1)进程推进顺序合法P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③D第三章处理机调度与死锁若并发进程P1和P2按曲线④所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R1,P2保持了资源R2,系统处于不安全状态。因为，这时两进程再向前推进，便可能发生死锁。例如，当P1运行到P1:Request(R2)时，将因R2已被P2占用而阻塞；当P2运行到P2:Request(R1)时，也将因R1已被P1占用而阻塞，于是发生了进程死锁。2)进程推进顺序非法第三章处理机调度与死锁DP2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④2)进程推进顺序非法第三章处理机调度与死锁(1)互斥条件(2)请求和保持条件(3)不剥夺条件(4)环路等待条件3.5.2产生死锁的必要条件第三章处理机调度与死锁(1)预防死锁(2)避免死锁(3)检测死锁(4)解除死锁3.5.3处理死锁的基本方法第三章处理机调度与死锁3.6预防死锁的方法3.6.1预防死锁3.6.2系统安全状态3.6.3利用银行家算法避免死锁第三章处理机调度与死锁3.6.1预防死锁1.摒弃“请求和保持”条件静态资源分配法2.摒弃“不剥夺”条件需要使请求，得不到满足则释放已保持的资源实现复杂，代价大3.摒弃“环路等待”条件有序资源分配法不足之处：资源序号应相对稳定，增加设备不易使用与申请顺序不一致，资源浪费不方便用户第三章处理机调度与死锁3.6.2系统安全状态1.安全状态2.安全状态之例3.第三章处理机调度与死锁1.安全状态在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。所谓安全状态，是指系统能按某种进程顺序〈P1,P2,…,Pn〉(称〈P1,P2,…,Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。不安全：可能死锁；安全：可避免死锁第三章处理机调度与死锁2.安全状态之例我们通过一个例子来说明安全性。假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：进程最大需求已分配（需求）可用P1P2P310495（5）2（2）2（7）3（1