操作系统课件第3章调度与死锁.ppt
调度与死锁,内容提要,调度的类型及其功能调度的性能评价常用的调度算法死锁,调度的含义,调度就是选出待分派的作业或进程处理机调度的主要目的是为了分配处理机,调度的类型,高级调度：作业调度中级调度：存储对换低级调度：进程调度,进程的调度方式,非抢占方式抢占方式,进程调度的时机,现行进程完成或错误终止现行进程提出I/O请求，等待I/O完成时在进程通信中，执行中的进程执行了某种原语操作，如P操作、阻塞原语时，都可能引起进程调度在分时系统，按照时间片轮转，分给进程的时间片用完时优先级调度时，有更高优先级进程变为就绪时,进程调度的主要功能,保存让权进程的现场择优选出一个就绪进程为选中进程恢复现场，令其投入运行,作业调度和进程调度的区别,作业调度是宏观调度，进程调度是微观调度作业调度为进程的活动做准备，进程调度使进程真正活动起来作业调度执行次数较少，进程调度活动频繁作业调度可以不设，进程调度必不可少,仅有进程调度的调度队列模型,就 绪 队 列,阻 塞 队 列,CPU,事件出现,交互用户,时间片完,进程调度,等待事件,进程完成,常用的调度性能评价标准,CPU的利用率系统吞吐量周转时间响应时间就绪队列等待时间,周转时间,周转时间是指从作业提交给系统开始，到作业完成为止的时间通常把周转时间作为评价批处理系统性能、选择作业调度方式与算法的准则,平均周转时间与平均带权周转时间,平均周转时间可描述为：通常把周转时间作为评价批处理系统性能、选择作业调度方式与算法的准则,常用调度算法,对于不同的系统和系统目标，通常采用不同的调度算法。目前存在很多调度算法，有的适用于作业调度，有的适用于进程调度，有的两者都适用。,先来先服务调度算法,先来先服务（FCFS）算法的思想很简单：每次调度是从作业后备队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创建进程，然后放入就绪队列。,FCFS算法示意图,作业,T,作业1,作业2,作业3,0,1,2,24,27,30,表示作业到达时间,表示作业执行过程,FCFS算法性能分析,作业 到达时间 运行时间 开始时间 完成时间 周转时间 带权周转时间,平均周转时间 T=26 平均带权周转时间 W=6.33,1 0 24 0 24 24 1,2 1 3 24 27 26 8.67,3 2 3 27 30 28 9.33,FCFS的特征,较利于长作业或进程有利于占用CPU时间多的作业容易实现，但效率较低,短作业（进程）优先调度算法,短作业(SJF)调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行短进程(SPF)调度算法是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行,SJ(P)F调度算法的缺点,对长作业非常不利完全未考虑作业的紧迫程度由于作业（进程）的长短，只是根据用户估计的时间而定，致使算法不一定能真正做到短作业优先调度,时间片轮转调度算法,系统使每个进程依次按时间片轮流执行。在通常的轮转法中，系统将所有就绪进程按先来先服务原则，排成一个队列。每次调度时，把CPU分配给队首进程，并对其执行一个时间片。时间片的大小从几ms到几百ms。 时间片用完时，停止该进程的执行，并将其送入就绪队列的末尾。,影响时间片长短的因素,系统的响应时间就绪队列进程的数目进程的转换时间CPU运行指令速度,优先权调度算法,为照顾到紧迫型作业进入到系统后就能获得优先处理，引入最高优先权调度算法。当该算法用于作业调度时，系统将从后备队列中选择若干优先权最高的作业调入内存；当算法用于进程调度时，把处理机分配给就绪队列中优先权最高的进程。,算法分类,非抢占式优先权算法抢占式优先权算法,优先权的类型,静态优先权。确定依据为：进程类型、进程对资源的需求、用户要求动态优先权,多级队列调度,多级队列调度是根据作业的性质或类型不同，将就绪队列分成若干个子队列，每个作业固定属于某个队列。每个队列采用一种算法，不同队列可采用不同的调度算法。,多级反馈队列调度算法,多级反馈队列调度算法不必事先了解各进程所需的执行时间，而且还可满足各种类型进程的需要，是目前公认的比较好的进程调度算法。,多级反馈队列中就绪队列种类,刚刚被创建的进程等待进程调度已经被调度执行过，但还没有执行完，等待下一次调度正在执行的进程还未用完时间片，因请求I/O，等待I/O完成被迫放弃CPU，当等待原因解除后，进入就绪队列等待运行,多级反馈队列调度的实施过程,系统设置多个就绪队列，进程在其生命期内可能在多个队列中存在各个队列赋予不同的优先级。第一个队列的优先级最高，其余各队列的优先权逐个降低各个队列中进程执行的时间片大小也各不相同，在优先权越高的队列中，每个进程的执行时间片就越小,多级反馈队列调度的实施过程,新进程进入内存后，排在最高优先级队列的末尾，按FCFS原则等待调度。该进程执行时，如果它在一个时间片结束时尚未完成，调度程序便将该进程转入下一个较低优先级队列的队尾当一个长进程从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行,多级反馈队列调度的实施过程,调度时，总是先调度优先级高的队列。仅当该队列空时，才调度次高优先级队列，以此类推，第n个队列进程被调度时，必须是前n-1个队列为空如果处理机正在第i个队列中为某进程服务时，又有新进程进入优先权较高的队列，则此时新进程将抢占正在运行进程的处理机，由调度程序把正在运行的进程放回到第i个队列的末尾，把处理机分配给新到的进程,多级反馈队列调度算法示意图,至CPU,至CPU,至CPU,至CPU,S1,S2,S3,死锁,在多道程序系统中，虽可通过进程的并发执行改善系统的资源利用率和提高处理能力，但也可能引发一种危险死锁。 死锁(dead lock)，是指多个进程因竞争资源而造成的一种僵局。若无外力作用，这些进程将永远不能向前推进。,产生死锁的原因,竞争资源进程推进顺序非法,资源分配图,代表进程,代表资源,代表进程请求资源,代表资源已分配给进程,资源分配死锁举例,P1,P2,R1,R2,进程推进不当引发死锁举例,例如：两个进程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);,产生死锁的原因,互斥条件请求和保持条件不剥夺条件环路等待条件,处理死锁的基本方法,预防死锁避免死锁检测死锁解除死锁,预防死锁的方法,因产生死锁须四个必要条件。若能破坏其中的一个或几个条件，则死锁不发生。,摒弃请求和保持条件,系统要求所有进程一次性地申请整个运行过程中所需的全部资源。只要有一种资源要求不能满足，也让该进程等待该方法的优点是简单，容易实现，而且安全缺点是资源浪费严重，进程执行被延迟,摒弃不剥夺条件,系统要求一个已经保持了某些资源的进程，当它提出新的资源要求而不被满足时，必须释放它已经保持的所有资源，待以后再重新申请这种方法实现起来比较复杂，且要付出很大代价,摒弃环路等待条件,系统将所有资源按类型排成线性队列，并赋予不同的序号。所有进程申请资源时必须严格按资源序号递增的顺序提出。这种解决方法使资源利用率和系统吞吐量有明显改善。但对资源给予固定序号，将限制系统资源的扩充和程序编写的自由。,避免死锁的方法,该方法把系统的状态分为安全状态和不安全状态。只要能使系统处于安全状态，就可以避免死锁的发生。,安全状态,所谓安全状态，系统能按某种顺序如(P1, P2, , Pn)，称为安全序列，来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺利完成若系统不存在这样一个安全序列，则称系统处于不安全状态避免死锁的实质在于：如何使系统不进入不安全状态,银行家算法,最有代表性的避免死锁的算法，是Dijkstra提出的银行家算法。该算法因用于银行系统现金贷款的发放而得名。系统中必须设置若干数据结构。,银行家算法中的数据结构,可利用资源向量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=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，则表示系统处于安全状态；否则就是不安全状态,银行家算法举例,假定系统中有五个进程P0， P1， P2， P3， P4和三类资源A，B，C，各类资源的数目分别是10、5、7。,T0时刻的资源分配,银行家算法举例,利用安全性算法，T0时刻存在一个安全序列P1，P3，P4，P2，P0，故系统是安全的。P1请求资源，请求向量为Request1，0，2，则资源分配如下图,资源分配,银行家算法举例,P4请求资源，请求向量为Request3，3，0，系统按银行家算法进行检查，可用资源不能满足请求资源， P4等待。P0请求资源，请求向量为Request0，2，0 ，则资源分配如下图,资源分配,银行家算法举例,P4请求系统按银行家算法进行检查， P0分配资源后已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。,死锁的检测,保存有关资源的请求和分配信息提供一种算法，以利用这些信息来检测系统是否已进入死锁状态,死锁定理,在资源分配图中，找一个既不阻塞又非独立的进程结点P1P1释放资源后，可使P2获得资源继续运行经过一系列简化后，若所有进程都成为孤立结点，则称该图是可完全简化的，否则是不可完全简化的S为死锁状态的充分条件是，当且仅当S状态的资源分配图是不可完全简化的,资源分配死锁举例,P1,P2,R1,R2,死锁的解除,剥夺资源撤销进程,
