操作系统课件第3章调度与死锁.ppt

1、调度与死锁调度与死锁内容提要内容提要调度的类型及其功能调度的类型及其功能调度的性能评价调度的性能评价常用的调度算法常用的调度算法死锁死锁调度的含义调度的含义调度就是选出待分派的作业或进程调度就是选出待分派的作业或进程处理机调度的主要目的是为了分配处理处理机调度的主要目的是为了分配处理机机调度的类型调度的类型高级调度：作业调度高级调度：作业调度中级调度：存储对换中级调度：存储对换低级调度：进程调度低级调度：进程调度进程的调度方式进程的调度方式非抢占方式非抢占方式抢占方式抢占方式进程调度的时机进程调度的时机现行进程完成或错误终止现行进程完成或错误终止现行进程提出现行进程提出I/OI/O请求，等待请

2、求，等待I/OI/O完成时完成时在进程通信中，执行中的进程执行了某在进程通信中，执行中的进程执行了某种原语操作，如种原语操作，如P P操作、阻塞原语时，操作、阻塞原语时，都可能引起进程调度都可能引起进程调度在分时系统，按照时间片轮转，分给进在分时系统，按照时间片轮转，分给进程的时间片用完时程的时间片用完时优先级调度时，有更高优先级进程变为优先级调度时，有更高优先级进程变为就绪时就绪时进程调度的主要功能进程调度的主要功能保存让权进程的现场保存让权进程的现场择优选出一个就绪进程择优选出一个就绪进程为选中进程恢复现场，令其投入运行为选中进程恢复现场，令其投入运行作业调度和进程调度的区别作业调度和进程

3、调度的区别作业调度是宏观调度，进程调度是微观作业调度是宏观调度，进程调度是微观调度调度作业调度为进程的活动做准备，进程调作业调度为进程的活动做准备，进程调度使进程真正活动起来度使进程真正活动起来作业调度执行次数较少，进程调度活动作业调度执行次数较少，进程调度活动频繁频繁作业调度可以不设，进程调度必不可少作业调度可以不设，进程调度必不可少仅有进程调度的调度队列模型仅有进程调度的调度队列模型就就 绪绪 队队 列列阻阻 塞塞 队队 列列CPU事件出现事件出现交互用户交互用户时间片完时间片完进程进程调度调度等待等待事件事件进程完成进程完成常用的调度性能评价标准常用的调度性能评价标准CPUCPU的利用率

4、的利用率系统吞吐量系统吞吐量周转时间周转时间响应时间响应时间就绪队列等待时间就绪队列等待时间周转时间周转时间周转时间是指从作业提交给系统开始，周转时间是指从作业提交给系统开始，到作业完成为止的时间到作业完成为止的时间通常把周转时间作为评价批处理系统性通常把周转时间作为评价批处理系统性能、选择作业调度方式与算法的准则能、选择作业调度方式与算法的准则平均周转时间与平均带权周转时间平均周转时间与平均带权周转时间平均周转时间可描述为：平均周转时间可描述为：通常把周转时间作为评价批处理系统性通常把周转时间作为评价批处理系统性能、选择作业调度方式与算法的准则能、选择作业调度方式与算法的准则常用调度算法常用

5、调度算法 对于不同的系统和系统目标，通常对于不同的系统和系统目标，通常采用不同的调度算法。目前存在很多调采用不同的调度算法。目前存在很多调度算法，有的适用于作业调度，有的适度算法，有的适用于作业调度，有的适用于进程调度，有的两者都适用。用于进程调度，有的两者都适用。先来先服务调度算法先来先服务调度算法 先来先服务（先来先服务（FCFSFCFS）算法的思想）算法的思想很简单：每次调度是从作业后备队列中很简单：每次调度是从作业后备队列中选择一个或多个最先进入该队列的作业，选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创将它们调入内存，为它们分配资源，创建进程，然后放入就绪队列

6、。建进程，然后放入就绪队列。FCFSFCFS算法示意图算法示意图作业作业T作业作业1作业作业2作业作业3012242730表示作业到达时间表示作业到达时间表示作业执行过程表示作业执行过程FCFSFCFS算法性能分析算法性能分析作业作业 到达时间到达时间 运行时间运行时间 开始时间开始时间 完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间平均周转时间平均周转时间 T=26 平均带权周转时间平均带权周转时间 W=6.331 0 24 0 24 24 12 1 3 24 27 26 8.673 2 3 27 30 28 9.33FCFS的特征的特征较利于长作业或进程较利于长作业或进程有利

7、于占用有利于占用CPUCPU时间多的作业时间多的作业容易实现，但效率较低容易实现，但效率较低短作业（进程）优先调度算法短作业（进程）优先调度算法短作业短作业(SJF)(SJF)调度算法是从后备队列中选调度算法是从后备队列中选择一个或若干个估计运行时间最短的作择一个或若干个估计运行时间最短的作业，将它们调入内存运行业，将它们调入内存运行短进程短进程(SPF)(SPF)调度算法是从就绪队列中选调度算法是从就绪队列中选出一估计运行时间最短的进程，将处理出一估计运行时间最短的进程，将处理机分配给它，使它立即执行机分配给它，使它立即执行SJ(P)FSJ(P)F调度算法的缺点调度算法的缺点对长作业非常不利

8、对长作业非常不利完全未考虑作业的紧迫程度完全未考虑作业的紧迫程度由于作业（进程）的长短，只是根据用由于作业（进程）的长短，只是根据用户估计的时间而定，致使算法不一定能户估计的时间而定，致使算法不一定能真正做到短作业优先调度真正做到短作业优先调度时间片轮转调度算法时间片轮转调度算法 系统使每个进程依次按时间片轮流系统使每个进程依次按时间片轮流执行。在通常的轮转法中，系统将所有执行。在通常的轮转法中，系统将所有就绪进程按先来先服务原则，排成一个就绪进程按先来先服务原则，排成一个队列。每次调度时，把队列。每次调度时，把CPUCPU分配给队首分配给队首进程，并对其执行一个时间片。时间片进程，并对其执行

9、一个时间片。时间片的大小从几的大小从几msms到几百到几百msms。时间片用完时，停止该进程的执行，时间片用完时，停止该进程的执行，并将其送入就绪队列的末尾。并将其送入就绪队列的末尾。影响时间片长短的因素影响时间片长短的因素系统的响应时间系统的响应时间就绪队列进程的数目就绪队列进程的数目进程的转换时间进程的转换时间CPUCPU运行指令速度运行指令速度优先权调度算法优先权调度算法 为照顾到紧迫型作业进入到系统后为照顾到紧迫型作业进入到系统后就能获得优先处理，引入最高优先权调就能获得优先处理，引入最高优先权调度算法。当该算法用于作业调度时，系度算法。当该算法用于作业调度时，系统将从后备队列中选择若

10、干优先权最高统将从后备队列中选择若干优先权最高的作业调入内存；当算法用于进程调度的作业调入内存；当算法用于进程调度时，把处理机分配给就绪队列中优先权时，把处理机分配给就绪队列中优先权最高的进程。最高的进程。算法分类算法分类非抢占式优先权算法非抢占式优先权算法抢占式优先权算法抢占式优先权算法优先权的类型优先权的类型静态优先权。确定依据为：进程类型、静态优先权。确定依据为：进程类型、进程对资源的需求、用户要求进程对资源的需求、用户要求动态优先权动态优先权多级队列调度多级队列调度 多级队列调度是根据作业的性质或多级队列调度是根据作业的性质或类型不同，将就绪队列分成若干个子队类型不同，将就绪队列分成若

11、干个子队列，每个作业固定属于某个队列。每个列，每个作业固定属于某个队列。每个队列采用一种算法，不同队列可采用不队列采用一种算法，不同队列可采用不同的调度算法。同的调度算法。多级反馈队列调度算法多级反馈队列调度算法 多级反馈队列调度算法不必事先了多级反馈队列调度算法不必事先了解各进程所需的执行时间，而且还可满解各进程所需的执行时间，而且还可满足各种类型进程的需要，是目前公认的足各种类型进程的需要，是目前公认的比较好的进程调度算法。比较好的进程调度算法。多级反馈队列中就绪队列种类多级反馈队列中就绪队列种类刚刚被创建的进程等待进程调度刚刚被创建的进程等待进程调度已经被调度执行过，但还没有执行完，已经

12、被调度执行过，但还没有执行完，等待下一次调度等待下一次调度正在执行的进程还未用完时间片，因请正在执行的进程还未用完时间片，因请求求I/OI/O，等待，等待I/OI/O完成被迫放弃完成被迫放弃CPUCPU，当，当等待原因解除后，进入就绪队列等待运等待原因解除后，进入就绪队列等待运行行多级反馈队列调度的实施过程多级反馈队列调度的实施过程系统设置多个就绪队列，进程在其生命系统设置多个就绪队列，进程在其生命期内可能在多个队列中存在期内可能在多个队列中存在各个队列赋予不同的优先级。第一个队各个队列赋予不同的优先级。第一个队列的优先级最高，其余各队列的优先权列的优先级最高，其余各队列的优先权逐个降低逐个降

13、低各个队列中进程执行的时间片大小也各各个队列中进程执行的时间片大小也各不相同，在优先权越高的队列中，每个不相同，在优先权越高的队列中，每个进程的执行时间片就越小进程的执行时间片就越小多级反馈队列调度的实施过程多级反馈队列调度的实施过程新进程进入内存后，排在最高优先级队新进程进入内存后，排在最高优先级队列的末尾，按列的末尾，按FCFSFCFS原则等待调度。该进原则等待调度。该进程执行时，如果它在一个时间片结束时程执行时，如果它在一个时间片结束时尚未完成，调度程序便将该进程转入下尚未完成，调度程序便将该进程转入下一个较低优先级队列的队尾一个较低优先级队列的队尾当一个长进程从第一队列依次降到第当一个

14、长进程从第一队列依次降到第n n队列后，在第队列后，在第n n队列中便采取按时间片队列中便采取按时间片轮转的方式运行轮转的方式运行多级反馈队列调度的实施过程多级反馈队列调度的实施过程调度时，总是先调度优先级高的队列。调度时，总是先调度优先级高的队列。仅当该队列空时，才调度次高优先级队仅当该队列空时，才调度次高优先级队列，以此类推，第列，以此类推，第n n个队列进程被调度个队列进程被调度时，必须是前时，必须是前n-1n-1个队列为空个队列为空如果处理机正在第如果处理机正在第i i个队列中为某进程个队列中为某进程服务时，又有新进程进入优先权较高的服务时，又有新进程进入优先权较高的队列，则此时新进程

15、将抢占正在运行进队列，则此时新进程将抢占正在运行进程的处理机，由调度程序把正在运行的程的处理机，由调度程序把正在运行的进程放回到第进程放回到第i i个队列的末尾，把处理个队列的末尾，把处理机分配给新到的进程机分配给新到的进程多级反馈队列调度算法示意图多级反馈队列调度算法示意图就绪队列就绪队列1就绪队列就绪队列2就绪队列就绪队列3就绪队列就绪队列4至至CPU至至CPU至至CPU至至CPUS1S2S3死锁死锁 在多道程序系统中，虽可通过进程在多道程序系统中，虽可通过进程的并发执行改善系统的资源利用率和提的并发执行改善系统的资源利用率和提高处理能力，但也可能引发一种危险高处理能力，但也可能引发一种危

16、险死锁。死锁。死锁死锁(dead lock)(dead lock)，是指多个进程因，是指多个进程因竞争资源而造成的一种僵局。若无外力竞争资源而造成的一种僵局。若无外力作用，这些进程将永远不能向前推进。作用，这些进程将永远不能向前推进。产生死锁的原因产生死锁的原因竞争资源竞争资源进程推进顺序非法进程推进顺序非法资源分配图资源分配图 代表进程代表进程 代表资源代表资源 代表进程请求资源代表进程请求资源 代表资源已分配给进程代表资源已分配给进程资源分配死锁举例资源分配死锁举例P1P2R1R2进程推进不当引发死锁举例进程推进不当引发死锁举例例如：两个进程例如：两个进程P P1 1，P P2 2 共享两

17、个系统资源共享两个系统资源R R1 1和和R R2 2合法顺序为：合法顺序为：P P1 1:Request(R:Request(R1 1);P);P1 1:Request(R:Request(R2 2););P P1 1:Release(R:Release(R1 1);P);P1 1:Release(R:Release(R2 2););P P2 2:Request(R:Request(R2 2);P);P2 2:Request(R:Request(R1 1););P P2 2:Release(R:Release(R2 2);P);P2 2:Release(R:Release(R1 1););非

18、法顺序为：非法顺序为：P P1 1:Request(R:Request(R1 1);P);P2 2:Request(R:Request(R2 2););P P1 1:Request(R:Request(R2 2);P);P2 2:Request(R:Request(R1 1););产生死锁的原因产生死锁的原因互斥条件互斥条件请求和保持条件请求和保持条件不剥夺条件不剥夺条件环路等待条件环路等待条件处理死锁的基本方法处理死锁的基本方法预防死锁预防死锁避免死锁避免死锁检测死锁检测死锁解除死锁解除死锁预防死锁的方法预防死锁的方法 因产生死锁须四个必要条件。若能因产生死锁须四个必要条件。若能破坏其中的一

19、个或几个条件，则死锁不破坏其中的一个或几个条件，则死锁不发生。发生。摒弃请求和保持条件摒弃请求和保持条件系统要求所有进程一次性地申请整个运系统要求所有进程一次性地申请整个运行过程中所需的全部资源。只要有一种行过程中所需的全部资源。只要有一种资源要求不能满足，也让该进程等待资源要求不能满足，也让该进程等待该方法的优点是简单，容易实现，而且该方法的优点是简单，容易实现，而且安全安全缺点是资源浪费严重，进程执行被延迟缺点是资源浪费严重，进程执行被延迟摒弃不剥夺条件摒弃不剥夺条件系统要求一个已经保持了某些资源的进系统要求一个已经保持了某些资源的进程，当它提出新的资源要求而不被满足程，当它提出新的资源要

20、求而不被满足时，必须释放它已经保持的所有资源，时，必须释放它已经保持的所有资源，待以后再重新申请待以后再重新申请这种方法实现起来比较复杂，且要付出这种方法实现起来比较复杂，且要付出很大代价很大代价摒弃环路等待条件摒弃环路等待条件系统将所有资源按类型排成线性队列，系统将所有资源按类型排成线性队列，并赋予不同的序号。所有进程申请资源并赋予不同的序号。所有进程申请资源时必须严格按资源序号递增的顺序提出。时必须严格按资源序号递增的顺序提出。这种解决方法使资源利用率和系统吞吐这种解决方法使资源利用率和系统吞吐量有明显改善。量有明显改善。但对资源给予固定序号，将限制系统资但对资源给予固定序号，将限制系统资

21、源的扩充和程序编写的自由。源的扩充和程序编写的自由。避免死锁的方法避免死锁的方法 该方法把系统的状态分为安全状态该方法把系统的状态分为安全状态和不安全状态。只要能使系统处于安全和不安全状态。只要能使系统处于安全状态，就可以避免死锁的发生。状态，就可以避免死锁的发生。安全状态安全状态所谓安全状态，系统能按某种顺序如所谓安全状态，系统能按某种顺序如(P1,P2,(P1,P2,PnPn)，称为安全序列，来为，称为安全序列，来为每个进程分配其所需资源，直至最大需每个进程分配其所需资源，直至最大需求，使每个进程都可顺利完成求，使每个进程都可顺利完成若系统不存在这样一个安全序列，则称若系统不存在这样一个安

22、全序列，则称系统处于不安全状态系统处于不安全状态避免死锁的实质在于：如何使系统不进避免死锁的实质在于：如何使系统不进入不安全状态入不安全状态银行家算法银行家算法 最有代表性的避免死锁的算法，是最有代表性的避免死锁的算法，是DijkstraDijkstra提出的银行家算法。该算法因提出的银行家算法。该算法因用于银行系统现金贷款的发放而得名。用于银行系统现金贷款的发放而得名。系统中必须设置若干数据结构。系统中必须设置若干数据结构。银行家算法中的数据结构银行家算法中的数据结构可利用资源向量可利用资源向量AvailableAvailable最大需求数组最大需求数组MaxMax分配矩阵分配矩阵Alloc

23、ationAllocation需求矩阵需求矩阵NeedNeed上述三个矩阵间存在下述关系：上述三个矩阵间存在下述关系：Needi,jNeedi,j=Maxi,jMaxi,j Allocationi,jAllocationi,j 银行家算法的步骤银行家算法的步骤设设RequestRequesti i是进程是进程P Pi i的请求向量。的请求向量。(1)(1)如果如果RequestRequesti iNeedNeedi i，则转向步骤，则转向步骤(2)(2)；否则报错否则报错(2)(2)若若RequestRequesti iAvailableAvailable，转向步骤，转向步骤(3)(3)；否则

24、否则P Pi i等待等待(3)(3)系统试探把资源分配给进程系统试探把资源分配给进程P Pi i，并修改下，并修改下面的数值：面的数值：AvailableAvailablei i=AvailableAvailablei i-Request-Requesti i AllocationAllocationi i=AllocationAllocationi i+Request+Requesti i NeedNeedi i=NeedNeedi i-Request-Requesti i(4)(4)执行安全性算法执行安全性算法安全性算法的步骤安全性算法的步骤(1)(1)设置两个向量：工作向量设置两个向量：

25、工作向量WorkWork和完成向和完成向量量FinishFinish(2)(2)从进程集合中找到一个满足以下条件的从进程集合中找到一个满足以下条件的进程进程P Pi i：1.1.FinishiFinishi=False=False 2.Need 2.Needi iWorkWorki i 若能找到，执行步骤若能找到，执行步骤(3)(3)；否则执行步骤；否则执行步骤(4)(4)安全性算法的步骤安全性算法的步骤(3)(3)当进程当进程P Pi i顺利完成，并释放资源，可执行：顺利完成，并释放资源，可执行：WorkWorki i=WorkWorki i+Allocation+Allocationi i

26、 FinishiFinishi=true=true go to step(2)go to step(2)(4)(4)若所有的若所有的FinishiFinishi=true=true，则表示系统处于，则表示系统处于安全状态；否则就是不安全状态安全状态；否则就是不安全状态银行家算法举例银行家算法举例 假定系统中有五个进程假定系统中有五个进程PP0 0，P P1 1，P P2 2，P P3 3，P P4 4 和三类资源和三类资源AA，B B，CC，各类资源，各类资源的数目分别是的数目分别是1010、5 5、7 7。T T0 0时刻的资源分配时刻的资源分配MaxA B CAllocationA B C

27、NeedA B CAvailableA B CP0 P1 P2 P3 P4 7 5 33 2 29 0 22 2 24 3 30 1 02 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 2银行家算法举例银行家算法举例l 利用安全性算法，利用安全性算法，T T0 0时刻存在一个安全序时刻存在一个安全序列列PP1 1，P P3 3，P P4 4，P P2 2，P P0 0，故系统是安全的。，故系统是安全的。l P P1 1请求资源，请求向量为请求资源，请求向量为Request1Request1，0 0，22，则资源分配如下图则资源分配如下图资源分配资

28、源分配MaxMaxA B CA B CAllocationAllocationA B CA B CNeedNeedA B CA B CAvailableAvailableA B CA B CP0P0 P1 P1 P2 P2 P3 P3 P4 P47 5 37 5 33 2 23 2 29 0 29 0 22 2 22 2 24 3 34 3 30 1 00 1 03 0 23 0 23 0 23 0 22 1 12 1 10 0 20 0 27 4 37 4 30 2 00 2 06 0 06 0 00 1 10 1 14 3 14 3 12 3 02 3 0银行家算法举例银行家算法举例l P

29、 P4 4请求资源，请求向量为请求资源，请求向量为Request3Request3，3 3，00，系统按银行家算法进行检查，可用资源不系统按银行家算法进行检查，可用资源不能满足请求资源，能满足请求资源，P P4 4等待。等待。l P P0 0请求资源，请求向量为请求资源，请求向量为Request0Request0，2 2，0 0，则资源分配如下图，则资源分配如下图资源分配资源分配MaxA B CAllocationA B CNeedA B CAvailableA B CP0 P1 P2 P3 P47 5 33 2 29 0 22 2 24 3 30 3 03 0 23 0 22 1 10 0

30、27 2 30 2 06 0 00 1 14 3 12 1 0银行家算法举例银行家算法举例l P P4 4请求系统按银行家算法进行检查，请求系统按银行家算法进行检查，P P0 0分分配资源后已不能满足任何进程的需要，故配资源后已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资系统进入不安全状态，此时系统不分配资源。源。死锁的检测死锁的检测保存有关资源的请求和分配信息保存有关资源的请求和分配信息提供一种算法，以利用这些信息来检测提供一种算法，以利用这些信息来检测系统是否已进入死锁状态系统是否已进入死锁状态死锁定理死锁定理在资源分配图中，找一个既不阻塞又非在资源分配图中，找一个既不阻塞又非独立的进程结点独立的进程结点P1P1P1P1释放资源后，可使释放资源后，可使P2P2获得资源继续运获得资源继续运行行经过一系列简化后，若所有进程都成为经过一系列简化后，若所有进程都成为孤立结点，则称该图是可完全简化的，孤立结点，则称该图是可完全简化的，否则是不可完全简化的否则是不可完全简化的S S为死锁状态的充分条件是，当且仅当为死锁状态的充分条件是，当且仅当S S状态的资源分配图是不可完全简化的状态的资源分配图是不可完全简化的资源分配死锁举例资源分配死锁举例P1P2R1R2死锁的解除死锁的解除剥夺资源剥夺资源撤销进程撤销进程