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

1、调度与死锁内容提要调度的类型及其功能调度的性能评价常用的调度算法死锁调度的含义调度就是选出待分派的作业或进程处理机调度的主要目的是为了分配处理机调度的类型高级调度：作业调度中级调度：存储对换低级调度：进程调度进程的调度方式非抢占方式抢占方式进程调度的时机现行进程完成或错误终止现行进程提出I/O请求，等待I/O完成时在进程通信中，执行中的进程执行了某种原语操作，如P操作、阻塞原语时，都可能引起进程调度在分时系统，按照时间片轮转，分给进程的时间片用完时优先级调度时，有更高优先级进程变为就绪时进程调度的主要功能保存让权进程的现场择优选出一个就绪进程为选中进程恢复现场，令其投入运行作业调度和进程调度的

2、区别作业调度是宏观调度，进程调度是微观调度作业调度为进程的活动做准备，进程调度使进程真正活动起来作业调度执行次数较少，进程调度活动频繁作业调度可以不设，进程调度必不可少仅有进程调度的调度队列模型就 绪 队 列阻 塞 队 列CPU事件出现交互用户时间片完进程调度等待事件进程完成常用的调度性能评价标准CPU的利用率系统吞吐量周转时间响应时间就绪队列等待时间周转时间周转时间是指从作业提交给系统开始，到作业完成为止的时间通常把周转时间作为评价批处理系统性能、选择作业调度方式与算法的准则平均周转时间与平均带权周转时间平均周转时间可描述为：通常把周转时间作为评价批处理系统性能、选择作业调度方式与算法的准则

3、常用调度算法 对于不同的系统和系统目标，通常采用不同的调度算法。目前存在很多调度算法，有的适用于作业调度，有的适用于进程调度，有的两者都适用。先来先服务调度算法 先来先服务（FCFS）算法的思想很简单：每次调度是从作业后备队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创建进程，然后放入就绪队列。FCFS算法示意图作业T作业1作业2作业3012242730表示作业到达时间表示作业执行过程FCFS算法性能分析作业 到达时间 运行时间 开始时间 完成时间 周转时间 带权周转时间平均周转时间 T=26 平均带权周转时间 W=6.331 0 24 0 24 24 12 1 3

4、 24 27 26 8.673 2 3 27 30 28 9.33FCFS的特征较利于长作业或进程有利于占用CPU时间多的作业容易实现，但效率较低短作业（进程）优先调度算法短作业(SJF)调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行短进程(SPF)调度算法是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行SJ(P)F调度算法的缺点对长作业非常不利完全未考虑作业的紧迫程度由于作业（进程）的长短，只是根据用户估计的时间而定，致使算法不一定能真正做到短作业优先调度时间片轮转调度算法 系统使每个进程依次按时间片轮流执行。在通常的轮转法中，系统

5、将所有就绪进程按先来先服务原则，排成一个队列。每次调度时，把CPU分配给队首进程，并对其执行一个时间片。时间片的大小从几ms到几百ms。 时间片用完时，停止该进程的执行，并将其送入就绪队列的末尾。影响时间片长短的因素系统的响应时间就绪队列进程的数目进程的转换时间CPU运行指令速度优先权调度算法 为照顾到紧迫型作业进入到系统后就能获得优先处理，引入最高优先权调度算法。当该算法用于作业调度时，系统将从后备队列中选择若干优先权最高的作业调入内存；当算法用于进程调度时，把处理机分配给就绪队列中优先权最高的进程。算法分类非抢占式优先权算法抢占式优先权算法优先权的类型静态优先权。确定依据为：进程类型、进程

6、对资源的需求、用户要求动态优先权多级队列调度 多级队列调度是根据作业的性质或类型不同，将就绪队列分成若干个子队列，每个作业固定属于某个队列。每个队列采用一种算法，不同队列可采用不同的调度算法。多级反馈队列调度算法 多级反馈队列调度算法不必事先了解各进程所需的执行时间，而且还可满足各种类型进程的需要，是目前公认的比较好的进程调度算法。多级反馈队列中就绪队列种类刚刚被创建的进程等待进程调度已经被调度执行过，但还没有执行完，等待下一次调度正在执行的进程还未用完时间片，因请求I/O，等待I/O完成被迫放弃CPU，当等待原因解除后，进入就绪队列等待运行多级反馈队列调度的实施过程系统设置多个就绪队列，进程

7、在其生命期内可能在多个队列中存在各个队列赋予不同的优先级。第一个队列的优先级最高，其余各队列的优先权逐个降低各个队列中进程执行的时间片大小也各不相同，在优先权越高的队列中，每个进程的执行时间片就越小多级反馈队列调度的实施过程新进程进入内存后，排在最高优先级队列的末尾，按FCFS原则等待调度。该进程执行时，如果它在一个时间片结束时尚未完成，调度程序便将该进程转入下一个较低优先级队列的队尾当一个长进程从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行多级反馈队列调度的实施过程调度时，总是先调度优先级高的队列。仅当该队列空时，才调度次高优先级队列，以此类推，第n个队列进程被调度时

8、，必须是前n-1个队列为空如果处理机正在第i个队列中为某进程服务时，又有新进程进入优先权较高的队列，则此时新进程将抢占正在运行进程的处理机，由调度程序把正在运行的进程放回到第i个队列的末尾，把处理机分配给新到的进程多级反馈队列调度算法示意图就绪队列1就绪队列2就绪队列3就绪队列4至CPU至CPU至CPU至CPUS1S2S3死锁 在多道程序系统中，虽可通过进程的并发执行改善系统的资源利用率和提高处理能力，但也可能引发一种危险死锁。 死锁(dead lock)，是指多个进程因竞争资源而造成的一种僵局。若无外力作用，这些进程将永远不能向前推进。产生死锁的原因竞争资源进程推进顺序非法资源分配图 代表进

9、程 代表资源 代表进程请求资源 代表资源已分配给进程资源分配死锁举例P1P2R1R2进程推进不当引发死锁举例例如：两个进程P1，P2 共享两个系统资源R1和R2合法顺序为：P1: Request(R1); P1: Request(R2);P1: Release(R1); P1: Release(R2);P2: Request(R2); P2: Request(R1);P2: Release(R2); P2: Release(R1);非法顺序为：P1: Request(R1); P2: Request(R2);P1: Request(R2); P2: Request(R1);产生死锁的原因互斥条

10、件请求和保持条件不剥夺条件环路等待条件处理死锁的基本方法预防死锁避免死锁检测死锁解除死锁预防死锁的方法 因产生死锁须四个必要条件。若能破坏其中的一个或几个条件，则死锁不发生。摒弃请求和保持条件系统要求所有进程一次性地申请整个运行过程中所需的全部资源。只要有一种资源要求不能满足，也让该进程等待该方法的优点是简单，容易实现，而且安全缺点是资源浪费严重，进程执行被延迟摒弃不剥夺条件系统要求一个已经保持了某些资源的进程，当它提出新的资源要求而不被满足时，必须释放它已经保持的所有资源，待以后再重新申请这种方法实现起来比较复杂，且要付出很大代价摒弃环路等待条件系统将所有资源按类型排成线性队列，并赋予不同的

11、序号。所有进程申请资源时必须严格按资源序号递增的顺序提出。这种解决方法使资源利用率和系统吞吐量有明显改善。但对资源给予固定序号，将限制系统资源的扩充和程序编写的自由。避免死锁的方法 该方法把系统的状态分为安全状态和不安全状态。只要能使系统处于安全状态，就可以避免死锁的发生。安全状态所谓安全状态，系统能按某种顺序如(P1, P2, , Pn)，称为安全序列，来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺利完成若系统不存在这样一个安全序列，则称系统处于不安全状态避免死锁的实质在于：如何使系统不进入不安全状态银行家算法 最有代表性的避免死锁的算法，是Dijkstra提出的银行家算法。该算

12、法因用于银行系统现金贷款的发放而得名。系统中必须设置若干数据结构。银行家算法中的数据结构可利用资源向量Available最大需求数组Max分配矩阵Allocation需求矩阵Need上述三个矩阵间存在下述关系： Needi,j=Maxi,j Allocationi,j银行家算法的步骤设Requesti是进程Pi的请求向量。(1)如果RequestiNeedi，则转向步骤(2)；否则报错(2)若RequestiAvailable，转向步骤(3)；否则Pi等待(3)系统试探把资源分配给进程Pi，并修改下面的数值： Availablei=Availablei-Requesti Allocationi

13、=Allocationi+Requesti Needi=Needi-Requesti(4)执行安全性算法安全性算法的步骤(1)设置两个向量：工作向量Work和完成向量Finish(2)从进程集合中找到一个满足以下条件的进程Pi： 1. Finishi=False 2.NeediWorki 若能找到，执行步骤(3)；否则执行步骤(4) 安全性算法的步骤(3)当进程Pi顺利完成，并释放资源，可执行： Worki=Worki+Allocationi Finishi=true go to step (2)(4)若所有的Finishi=true，则表示系统处于安全状态；否则就是不安全状态银行家算法举例

14、假定系统中有五个进程P0， P1， P2， P3， P4和三类资源A，B，C，各类资源的数目分别是10、5、7。T0时刻的资源分配MaxA B CAllocationA B CNeedA 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银行家算法举例利用安全性算法，T0时刻存在一个安全序列P1，P3，P4，P2，P0，故系统是安全的。P1请求资源，请求向量为Request1，0，2，则资源分配如下图资源分配MaxA B

15、CAllocationA B CNeedA B CAvailableA B CP0 P1 P2 P3 P47 5 33 2 29 0 22 2 24 3 30 1 03 0 23 0 22 1 10 0 27 4 30 2 06 0 00 1 14 3 12 3 0银行家算法举例P4请求资源，请求向量为Request3，3，0，系统按银行家算法进行检查，可用资源不能满足请求资源， P4等待。P0请求资源，请求向量为Request0，2，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 27 2 30 2 06 0 00 1 14 3 12 1 0银行家算法举例P4请求系统按银行家算法进行检查， P0分