计算机操作系统操作系统第3章.ppt

第三章处理机调度与死锁,3.1 处理机调度的层次3.2 调度队列模型和调度准则3.3 调度算法3.4 实时调度 3.5 产生死锁的原因和必要条件3.6 预防死锁的方法3.7 死锁的检测与解除,3.1处理机调度的层次,3.1.1高级调度1作业和作业步(1)作业(Job)。不仅包含通常的程序和数据，而且还配有一份作业说明书，系统根据说明书来对程序的运行进行控制。批处理系统以作业为单位从外存调入内存。,(2)作业步(Job Step)。每个作业的相对独立、又相互关联的加工步骤。例：一个典型的作业：“编译”作业步；“连结装配”作业步；“运行”作业步。,2作业控制块JCB(Job Control Block)作业控制块，保存系统对作业进行管理和调度所需的全部信息：作业标识、用户名称、用户帐户、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业已运行时间)、资源需求(预计运行时间、要求内存大小、要求I/O设备的类型和数量等)、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。,3作业调度根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。,3.1.2 低级调度调度的对象是进程(或内核级线程)。1低级调度的功能(1)保存处理机的现场信息。(2)按某种算法选取进程。(3)把处理器分配给进程。,2进程调度中的三个基本机制(1)排队器：就绪进程排成一个或多个队列。(2)分派器:从就绪队列中取出所选定进程，进行上下文切换，将处理机分配给所选进程。(3)上下文切换机制（两次）：A.保存当前进程上下文，装入分派器程序上下文，使分派器程序运行；B.移出分派程序，把新选进程的CPU现场信息装入到处理机的各个相应寄存器中。,3进程调度方式1)非抢占方式(Nonpreemptive Mode)把处理机分配给某进程后，直至该进程完成，自愿释放处理机，或发生某事件而被阻塞时，才再把处理机分配给其他进程。优点:实现简单，系统开销小。缺点：难以满足紧急任务的要求，可能造成难以预料的后果。,2)抢占方式(Preemptive Mode)优点：可防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是能满足对响应时间有着较严格要求的实时任务的需求。缺点：开销较大。实现原则：(1)优先权原则。(2)短作业(进程)优先原则。(3)时间片原则。,3.1.3 中级调度暂时不能运行的进程不再占用宝贵的内存资源，调至外存上去等待，此时进程状态称为就绪驻外存状态或挂起状态。即是存储器管理中的对换功能（第四章）。进程调度的运行频率最高，是短程调度。作业调度周期较长（几分钟一次），是长程调度。中级调度运行频率介于上述两种之间，称为中程调度。,仅具有进程调度的调度队列模型,3.2 调度队列模型和调度准则,2具有高级和低级调度的调度队列模型(1)常用的就绪队列形式是优先权队列。(2)设置多个阻塞队列。每个队列对应于某一种进程阻塞事件。,具有高、低两级调度的调度队列模型,3同时具有三级调度的调度队列模型OS中引入中级调度，把进程就绪状态分为内存就绪(表示进程在内存中就绪)和外存就绪(进程在外存中就绪)。把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。,具有三级调度时的调度队列模型,3.2.2选择调度方式和调度算法的若干准则1面向用户的准则(1)周转时间短。周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)。它包括四部分时间：作业在外存后备队列上等待(作业)调度的时间，进程在就绪队列上等待进程调度的时间，进程在CPU上执行的时间，以及进程等待I/O操作完成的时间。,系统平均周转时间:,带权周转时间:W=T/Ts T:作业周转时间 Ts:系统为作业提供服务的时间平均带权周转时间：,(2)响应时间快。响应时间，是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。它包括三部分时间：从键盘输入的请求信息传送到处理机的时间，处理机对请求信息进行处理的时间，以及将所形成的响应信息回送到终端显示器的时间。(3)截止时间的保证。截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。（实时系统）。(4)优先权准则。,2面向系统的准则(1)系统吞吐量高。吞吐量是指在单位时间内系统所完成的作业数。(2)处理机利用率好。（大、中型多用户系统）。对于单用户微机或某些实时系统，此准则不重要。(3)各类资源的平衡利用。,3.2.1先来先服务和短作业(进程)优先调度算法1先来先服务调度算法算法既可用于作业调度，也可用于进程调度。FCFS算法比较有利于长作业(进程)，而不利于短作业(进程)。,3.3调 度 算 法,FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业(进程)。,2短作业(进程)优先调度算法(SJF/SJP)SJF:从后备队列中选择一个或若干个估计运行时间最短的作业调入内存运行。SJP:从就绪队列中选出一个估计运行时间最短的进程，分配处理机。,FCFS和SJF调度算法的性能SJF调度算法能有效地降低作业的平均等待时间，提高系统吞吐量。,SJ(P)F调度算法缺点：(1)由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。(2)不能保证紧迫性作业(进程)会被及时处理。(3)由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。,3.3.2高优先权优先调度算法 1最高优先权优先(FPF)调度算法 1)非抢占式优先权算法系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；2)抢占式优先权调度算法进程执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。,2优先权的类型1)静态优先权静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。优先权用某一范围内的整数表示。如，07或0255中的某一整数。确定进程优先权的依据有如下三个方面：(1)进程类型。通常，系统进程优先权高于一般用户进程优先权。(2)进程对资源的需求。对要求少的进程赋予较高的优先权。(3)用户要求。这是由用户进程的紧迫程度及用户所付费用的多少来确定优先权的。,2)动态优先权创建进程时的优先权随进程的推进或随其等待时间的增加而改变。,3高响应比优先调度算法作业的优先级随着等待时间的增加而以速率a提高，作业在等待一定的时间后，必然有机会分配到处理机。,由于等待时间与服务时间之和就是系统对该作业的响应时间，故优先权又相当于响应比RP。可表示为：,结论：(1)如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，实现的是短作业优先。(2)当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，实现的是先来先服务。,3.3.3基于时间片的轮转调度算法1时间片轮转法 时间片大小的确定：小时间片有利于短作业，但系统开销大；长时间片使每个进程都能在一个时间片内完成，算法退化为FCFS算法，无法满足交互式用户的需求。一般情况，时间片取值略大于一次典型的交互所需要的时间。（大多数进程在一个时间片内完成。）,时间片q=1和q=4时，5个进程运行情况,q=1和q=4时进程的周转时间RR(Round Robin)表示轮转调度算法。,2多级反馈队列调度算法(1)设置多个就绪队列，第一个队列优先级最高，第二个队列次之。优先权愈高的队列时间片愈小。,多级反馈队列调度算法,(2)新进程进入放入第一队列末尾，按FCFS调度。如果它在一个时间片结束时尚未完成，将该进程转入第二队列末尾，再同样按FCFS原则调度 长作业(进程)从第一队列依次降到第n队列后，在第n队列中采取按时间片轮转的方式运行。,(3)仅当第一队列空闲，调度程序才调度第二队列中的进程运行；仅当第1(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。,3多级反馈队列调度算法的性能(1)终端型作业用户。作业通常较小，系统只要能使这些作业(进程)在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意。(2)短批处理作业用户。如果仅在第一队列中执行一个时间片即可完成，用户都感到满意。稍长的作业通常在第二队列和第三队列各执行一个时间片即可完成，周转时间仍然较短。(3)长作业依次在第1，2，n个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。,3.4实 时 调 度 简 介,3.4.1实现实时调度的基本条件1提供必要的信息(1)就绪时间。(2)开始截止时间和完成截止时间。(3)处理时间。(4)资源要求。(5)优先级。如果某任务的开始截止时间已经错过，就会引起故障，则应为该任务赋予“绝对”优先级；如果开始截止时间的推迟对任务的继续运行无重大影响，则可为该任务赋予“相对”优先级。,2系统处理能力强m个周期性的硬实时任务，处理时间：Ci，周期时间：Pi，单处理机情况下必须满足下面的限制条件：,例：6个硬实时任务，周期时间都是 50 ms，处理时间为 10 ms，系统是不可调度的。,多处理机系统，处理机数为N，限制条件为：,3采用抢占式调度机制含有硬实时任务的实时系统采用抢占机制。小型实时系统，如果能预知任务的开始截止时间，可采用非抢占调度机制，以简化调度程序和对任务调度时所花费的系统开销。4具有快速切换机制,3.4.2实时调度算法的分类1非抢占式调度算法1)非抢占式轮转调度算法工业生产的群控系统中，由一台计算机控制若干个相同的(或类似的)对象，为每一个被控对象建立一个实时任务，并将它们排成一个轮转队列。2)非抢占式优先调度算法高优先级实时任务到达时，安排在就绪队列的队首，等待当前任务自我终止或运行完成后才能被调度执行。,2抢占式调度算法1)基于时钟中断的抢占式优先权调度算法高优先级实时任务到达后并不立即抢占当前任务的处理机，而是等到时钟中断到来时，调度程序才剥夺当前任务的执行，将处理机分配给新到的高优先权任务。2)立即抢占(Immediate Preemption)的优先权调度算法一旦出现外部中断，只要当前任务未处于临界区，便立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。,3.5产生死锁的原因和必要条件,3.5.1产生死锁的原因(1)竞争资源引起死锁。(2)进程间推进顺序非法导致进程死锁。,1竞争资源引起进程死锁1)可剥夺和非剥夺性资源 CPU和主存均属于可剥夺性资源。例，优先权高的进程可以剥夺优先权低的进程的处理机。存储器管理程序把一个进程从一个存储区移到另一个存储区，即剥夺了该进程原来占有的存储区。不可剥夺性资源：系统把资源分配给某进程后，只能在进程用完后自行释放，如磁带机、打印机等。,I/O设备共享时的死锁情况,2)竞争非剥夺性资源当箭头从进程指向资源时，表示进程请求资源；当箭头从资源指向进程时，表示该资源已被分配给该进程。,3)竞争临时性资源 临时性资源：由一个进程产生，被另一进程使用一短暂时间后便无用的资源。消息通信按下述顺序进行不可能发生死锁：P1：Release(S1)；Reqaest(S3)；P2：Release(S2)；Request(S1)；P3：Release(S3)；Request(S2)；下述的运行顺序可能发生死锁：P1：Request(S3)；Release(S1)；P2：Request(S1)；Release(S2)；P3：Request(S2)；Release(S3)；,进程之间通信时的死锁（消息S1、S2和S3是临时性资源）（P1产生消息S1，从P3接收消息S3，),2进程推进顺序不当引起死锁1)进程推进顺序合法(曲线1、2、3)进程P1和P2并发执行时按下述顺序推进(曲线1)：P1：Request(R1)；Request(R2)；P1：Releast(R1)；Release(R2)；P2：Request(R2)；Request(R1)；P2：Release(R2)；Release(R1)；2)进程推进顺序非法（曲线4）,进程推进顺序对死锁的影响,3.5.2产生死锁的四个必要条件(1)互斥条件：一段时间内某资源只由一个进程占用。(2)请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。(3)不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。(4)环路等待条件：指在发生死锁时，必然存在一个进程资源的环形链。,3.5.3处理死锁的基本方法(1)预防死锁。设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个条件来预防发生死锁。(2)避免死锁。在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。(3)检测死锁。允许系统在运行过程中发生死锁，但可通过系统所设置的检测机构，及时地检测出死锁的发生，采取适当措施，从系统中将已发生的死锁清除掉。(4)解除死锁（检测死锁配套）。撤消或挂起一些进程回收资源。能使系统获得较好的资源利用率和吞吐量，实现上难度最大。,3.6预防死锁的方法,3.6.1预防死锁1摒弃“请求和保持”条件进程开始运行之前一次性地申请在整个运行过程所需的全部资源。只要有一种资源不能满足进程要求，即使其它所需的各资源都空闲，也不分配给该进程，而让该进程等待。（资源被严重浪费）2摒弃“不剥夺”条件（实现复杂，付出代价大）进程逐个地提出对资源要求。当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，摒弃了“不剥夺”条件。被迫释放可能会造成前段工作的失效。,3摒弃“环路等待”条件将所有资源按类型进行线性排队，并赋予不同的序号。例，输入机序号为1，打印机序号为2，磁带机为3，磁盘为4。所有进程对资源的请求必须严格按照资源序号递增次序提出。存在问题：1）系统中各类资源所分配的序号必须相对稳定，限制了新类型设备的增加。2）作业(进程)使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费。3）按规定次序申请的方法必然会限制用户简单、自主地编程。,3.6.2系统安全状态1安全状态系统进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。安全状态：是指系统能按某种进程顺序(P1，P2，Pn)来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。,2安全状态举例假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：,3由安全状态向不安全状态的转换在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。例如，再把其余的2台分配给P2，这样，在P2完成后只能释放出4台，不能满足P1、P3要求导致死锁。必须让P3一直等待到P1和P2完成，释放出资源后再将足够的资源分配给P3，它才能顺利完成。,3.6.3利用银行家算法避免死锁 1银行家算法中的数据结构(1)可利用资源向量(数组):Availablej=K，表示系统中现有R j类资源K个。(2)最大需求矩阵(nm)Max。Maxi,j=K，表示进程i需要Rj类资源最大数目为K。,(3)分配矩阵(nm):Allocationi,j=K，表示进程i当前已分得R j类资源数目为K。(4)需求矩阵(nm):Needi,j=K，表示进程i还需要R j类资源K个。上述三个矩阵的关系：Needi,j=Maxi,j-Allocationi,j,2银行家算法 设Request i是进程Pi的请求向量，Request ij=K，表示进程P i需要K个R j类型的资源。当P i发出资源请求后，系统按下述步骤进行检查：(1)如果Request ijNeedi,j，便转向步骤(2)；否则为出错。(2)如果RequestijAvailablej，便转向步骤(3)；否则，Pi等待。,(3)系统试探着把资源分配给进程Pi，并修改数值：Availablej:=Availablej-Request ij；Allocationi,j:=Allocationi,j+Request ij；Needi,j:=Needi,j-Request ij；(4)系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，将资源分配给进程Pi；否则，恢复原来的资源分配状态，让进程Pi等待。,3安全性算法(1)设置两个向量：工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目。执行安全算法开始时，Work:=Available Finish：开始时进程i：Finishi:=false；如果有足够资源分配给进程i，Finishi:=true。,(2)从进程集合中找到一个能满足下述条件的进程：Finishi=false；（还没有分配足够资源）Needi,jWorkj；若找到，执行步骤(3)，否则，执行步骤(4)。(3)当进程Pi获得资源后，可顺利执行完成，并释放出分配给它的资源：Workj:=Workj+Allocationi,j；Finishi:=true；go to step 2；,(4)如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。,4银行家算法举例假定系统中有五个进程P0，P1，P2，P3，P4和三类资源A，B，C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如下：,(1)T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析，在T0时刻存在着一个安全序列P1，P3，P4，P2，P0。,T0时刻的安全序列,(2)若P1请求资源，向量Request1(1，0，2)，系统按银行家算法进行检查：Request1(1，0，2)Need1(1，2，2)Request1(1，0，2)Available1(3，3，2)系统先假定可为P1分配资源，并修改Available，Allocation1和Need1向量，资源变化情况如图中的圆括号所示。,再利用安全性算法检查此时系统是否安全（安全）：,P1申请资源时的安全性检查,(3)接下来P4请求资源：Request4(3，3，0)，系统按银行家算法进行检查：Request4(3，3，0)Need4(4，3，1)；Request4(3，3，0)Available(2，3，0)，让P4等待。(4)P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查：Request0(0，2，0)Need0(7，4，3)；Request0(0，2，0)Available(2，3，0)；系统暂时先假定可为P0分配资源。,为P0分配资源后的有关资源数据,(5)进行安全性检查：可用资源Available(2，1，0)已不能满足任何进程的需要，系统进入不安全状态，此时系统不分配资源。,3.7.1死锁的检测1资源分配图(Resource Allocation Graph)一组结点N和一组边E组成:G=(N，E),3.7死锁的检测与解除,2死锁定理把资源分配图加以简化，检测系统是否为死锁状态:(1)在资源分配图中，找出一个既不阻塞又非独立的进程结点Pi。在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去pi所求的请求边和分配边，使之成为孤立的结点。,资源分配图的简化,简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。有关文献证明，所有的简化顺序，都将得到相同的不可简化图。同样可以证明：S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。称为死锁定理。,3.7.2死锁的解除解除死锁的两种方法：(1)剥夺资源。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。(2)撤消进程。最简单的撤消进程的方法是使全部死锁进程都夭折掉；稍微温和一点的方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。,