操作系统教学03

,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第三章 处理机调度与死锁,第三章 处理机调度与死锁,3.1,处理机调度的层次,3.2,调度队列模型和调度准则,3.3,调度算法,3.4,实时调度,3.5,产生死锁的原因和必要条件,3.6,预防死锁的方法,3.7,死锁的检测与解除,3.1,处理机调度的层次,在多道程序系统中，一个作业从提交到执行，通常都要经历,多级调度,如高级调度、低级调度、中级调度以及,I,O,调度等,系统的,运行性能,在很大程度上取决于调度,如吞吐量的大小、周转时间的长短、响应的及时性等,调度是多道系统的关键,CPU,资源管理,多道程序设计面临的挑战,批处理系统：如何安排内存中多个作业的运行顺序？,交互式系统：如何更好应对不同的交互式请求？,实时系统：如何保证实时服务的高质量？,进程调度,有效的管理,CPU,资源,When,：何时进行进程调度？,How,：遵循何种规则完成调度？,What,：调度过程中需要完成哪些工作？,进程调度的级别,高级调度：也称宏观调度，决定哪些程序可以进入系统,中级调度：也称内存调度，决定内存中程序的位置和状态,低级调度：也称微观调度，决定,CPU,资源在就绪进程间的分配,3.1.1,高级调度,又称,作业调度,或长程调度，其主要功能是按照某种原则,从磁盘,某些盘区的作业队列中,选取作业进入主存,，并为作业做好运行前的准备工作和作业完成后的善后工作。,其,调度对象是作业,作业,作业（,JOB,）是用户在一次算题过程中或一次事务处理中，要求计算机系统所做的工作的集合,作业是比进程更广泛的概念，不仅包含了通常的程序和数据，而且还配有一份,作业说明书,，系统根据作业说明书对程序运行进行控制。在批处理系统中，以作业为单位从外存调入内存,用户为了让计算机完成某个特定任务，首先编写成源程序，然后提交给计算机通过编译或汇编、连接、装配、运行等步骤，最终由计算机送出用户所需要的运行结果。从计算机管理的角度看，上述,一系列的由计算机执行的任务的集合就是作业,。,中国民航大学计算机科学与技术学院,$,END,$,RUN,Data for program,$,LOAD,Fortran program,$,FORTRAN,$,JOB, 10,429754,Cherry Chen,作业步,编辑,编译或汇编,连接,装入,运行,计算机完成作业是通过执行一系列有序的工作步骤进行的，每个步骤完成作业的一部分特定工作,把计算机系统完成一个作业所需的一系列有序的相对独立的工作步骤称为,作业步,作业的各个作业步虽然,功能相对独立,，但它们之间,相互关联,，往往是一个作业步的执行需要使用上一个作业步的执行结果。,若干个作业进入系统后，被依次存放在外存上，形成,输入的作业流,；在操作系统控制下，逐个作业进行处理，形成,处理的作业流,作业流,作业控制块,作业提交给系统进入后备状态后，,系统将为每个作业,建立一个作业控制块,JCB,。,JCB,在作业的整个运行过程中始终存在，并且其内容与作业的状态同步地动态变化。只有当作业完成并退出系统时，,JCB,才被撤消。可以说，,JCB,是一个作业在系统中存在的惟一标志，系统根据,JCB,才感知到作业的存在,作业控制块,JCB,中包含了对作业进行管理的必要信息，,JCB,中的信息一部分是从用户提供的作业控制卡或作业说明书中得到，另一部分是记录作业运行过程中的动态信息,JCB,的具体内容因系统不同而异,作业名,资源要求,预估的运行时间,最迟完成时间,要求的内存量,要求外设类型、台数,要求的文件量和输出量,资源使用情况,进入系统时间,开始运行时间,已运行时间,内存地址,外设台号,类型级别,控制方式,作业类型,优先级,状态,用户账户,作业控制块,作业调度,主要功能,根据,JCB,，审查系统能否满足用户作业的资源需求,按一定算法，从外存后备队列中选取某些作业调入内存,为它们创建进程、分配必要资源,将新创建的进程插入就绪队列，准备执行,作业调度,用户希望自己作业的周转时间尽可能少,系统希望作业的平均周转时间尽可能少,执行作业调度，必须做两个决定：,1,）决定接纳多少个作业,2,）决定接纳哪些作业,先来先服务（,FCFS,）,短作业优先（,SF,）,优先级高优先（,HPF,）,响应比高者优先（,RPF,）,作业调度,主要用于,批处理系统,。,其,设计目标是最大限度地发挥各种资源的利用率和保持系统内各种活动的充分并行,对资源需求不同的作业进行合理搭配,。,科学计算往往需要占用大量的,CPU,时间,，,属于,CPU,繁忙型作业,，对于,I/O,设备的使用程少,；而,数据处理恰恰相反，它们要求占用较少的,CPU,时间，但要求大量,I/O,时间，属于,I/O,繁忙型作业,；,另外有些递归计算，产生大量中间结果。需要很多内存单元存放它们，这属于,内存繁忙型作业,。如果能把它们搭配在一起。例如程序,A,在使用处理机，程序,B,在利用通道,l,，而程序,C,恰好利用通道,2,等，这样一来，,A,、,B,和,C,从来不在同一时间使用同一资源，每个程序就好像单独在一个机器上运行,按用户自然提交作业的顺序，可能出现对资源需求“一边倒”的情况。所以，批处理系统中要收容,大量,的后备作业，以便从中选出最佳搭配的作业组合,又称进程调度或短程调度，其主要功能是,按照某种原则,将处理机分配给就绪进程,。执行低级调度功能的程序称为进程调度程序，由它实现处理机在进程间的转换。它必须常驻主存，是操作系统,内核,的主要部分,实际上，进程调度程序主要是完成一台物理的,CPU,转变成多台,虚拟,(,或逻辑,),的,CPU,的工作,在,多道批处理、分时和实时系统中,都必须配备,3.1.2,低级调度,进程调度程序的主要功能,保存现场。,当前运行的进程调用进程调度程序时，即表示该进程要求放弃,CPU(,因时间片用完或等待,I/O,等原因,),。这时，进程调度程序把它的现场信息，如程序计数器及通用寄存器的内容等保留在该进程,PCB,的现场信息区中,挑选进程。,根据一定的调度算法,(,如优先级算法,),，从就绪队列中选出一个进程来，并把它的状态改为运行态，准备把,CPU,分配给它,恢复现场,把处理器分配给进程,。,为选中的进程恢复现场信息，并把,CPU,的控制权交给该进程,它接着上次间断的地方继续运行,进程调度中的三个基本机制,排队器,。将就绪进程按一定方式排成队列,分派器（分派程序）,。把进程调度程序选定的进程，从就绪队列中取出，进行上下文切换，把处理器分配给它,上下文切换机制。,保存当前进程上下文，装入分派程序上下文，分派程序运行；移出分派程序，装入新选进程上下文,进程调度方式,1,非抢占方式,(Non-Preemptive Mode),一旦处理机分配，便让进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其它进程,优点：,实现简单、系统开销小，适用于大多数的批处理系统环境,缺点：,难于满足需要立即执行的紧急任务,，在要求比较严格的实时系统中不宜采用,在采用非抢占调度方式时，可能引起进程调度的因素：,正在执行的进程执行完毕，或因发生某事件而不能再继续执行,执行中的进程因提出,I/O,请求而暂停执行,在进程通信或同步过程中执行了某种原语操作，如,P,操作,(wait,操作,),、,Block,原语、,Wakeup,原语等,2,抢占方式,(Preemptive Mode),允许调度程序停止正在执行的进程，将已分配给该进程的处理机，,重新分配,给另一进程,抢占的原则有,时间片原则,优先权原则,短作业,(,进程,),优先原则,优点：可防止长进程长时间占有处理机，为多数进程提供公平服务,缺点：系统开销较大,进程调度方式,中级调度又称中程调度,(,Medium-Term Scheduling,),引入中级调度的主要目的，是为了,提高内存利用率和系统吞吐量,使那些,暂时不能运行,的进程不再占用宝贵的内存资源，将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或,挂起状态,当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的那些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度,对换,(,存储器管理,),短期,调整系统负荷,，平顺系统操作,3.1.2,中级调度,调度类型,运行频率,运行时间,算法复杂性,进程调度,高,短,低,中程调度,中等,较短,中等,作业调度,低,长,高,三级调度比较,三级调度的相互比较,高级调度,中级调度,低级调度,外存到内存,内外存互换,内存中,批处理,实时,分时,运行频率高,运行频率适中,运行频率低,第三章 处理机调度与死锁,3.1,处理机调度的层次,3.2,调度队列模型和调度准则,3.3,调度算法,3.4,实时调度,3.5,产生死锁的原因和必要条件,3.6,预防死锁的方法,3.7,死锁的检测与解除,高级调度、中级调度、低级调度，都将涉及到作业或进程队列，共有三种类型的,调度队列模型,。,3.2,调度队列模型和调度准则,3.2.1,调度队列模型,仅有进程调度的调度队列模型,分时系统,通常仅设置进程调度。每个进程执行都可能出现三种情况：,(1),任务在该时间片内已完成，释放,CPU,进入完成状态；,(2),任务在本次时间片内尚未完成，,OS,便将该任务放在就绪队列的后面；,(3),执行期间，进程因某事件而被阻塞，放人阻塞队列。,具有高级和低级调度的调度队列模型,实例：,批处理操作系统,(1),引入了作业调度：从外存的后备队列中,选择,一批作业调入内存，为之创建进程后送入就绪队列。最常用的是优先权队列。,(2),设置多个阻塞队列，每个对应一种阻塞原因。,同时具有三级调度的调度队列模型,在,OS,中引人中级调度后，,就绪状态分为：内存就绪和外存就绪两种状态；,阻塞状态分成：内存阻塞和外存阻塞两种状态。,内存紧张换出时，内存就绪转变为外存就绪、内存阻塞转变为外存阻塞；在中级调度的作用下，又可使外存就绪转为内存就绪。,3.2.2,选择调度方式和调度算法的若干准则,取决于操作系统的类型和目标,不同的操作系统，有不同的调度方式和算法,有面向用户的准则，也有面向系统的准则,面向用户的准则,周转时间,短（批处理系统）,响应时间,快（分时系统）,截止时间,的保证（实时系统）,截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。,优先权准则（批处理、分时、实时）,让某些紧急的作业得到及时的处理。在要求较严格的场合可采用抢占调度方式。,周转时间,，是指从作业提交给系统开始，到作业完成为止的这段时间间隔,(,称为作业周转时间,),，它包括：,(1),作业在外存后备队列上等待,(,作业,),调度的时间；,(2),进程在就绪队列上等待进程调度的时间；,(3),进程在,CPU,上执行的时间；,(4),等待,I,O,操作完成的时间。,平均周转时间,短会有效地提高资源利用率，且可使大多数用户感到满意。,平均周转时间可描述为：,若系统为作业提供的实际服务时间为,Ts,，,W=T,Ts,称为带权周转时间，,平均带权周转时间,可表示为：,响应时间,是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说直到在屏幕上显示为止的一段时间间隔。它包括：,(1),从键盘输入的请求信息传送到处理机的时间；,(2),处理机对请求信息进行处理的时间；,(3),将所形成的响应回送到终端显示器的时间,面向系统的准则,1,系统吞吐量高（批处理）,吞吐量,是指在单位时间内所完成的作业数。,2,处理机利用率好,大、中型多用户系统，,CPU,昂贵，,处理机的利用率成为衡量系统性能的重要指标,3,各类资源的平衡利用,第三章 处理机调度与死锁,3.1,处理机调度的层次,3.2,调度队列模型和调度准则,3.3,调度算法,3.4,实时调度,3.5,产生死锁的原因和必要条件,3.6,预防死锁的方法,3.7,死锁的检测与解除,3.3,调度算法,在,OS,中，调度的实质是资源分配。,调度算法是指：,根据系统的资源分配策略所规定的资源分配算法,。,不同的系统和系统目标，采用不同的调度算法。,先来先服务调度算法,短作业优先调度算法,高优先权优先调度算法,基于时间片的轮转调度算法,先来先服务调度算法,最简单的调度算法。,既可用于,作业调度,，也可用于,进程调度,。,每次调度都是选择一个或多个最先进入队列的作业或进程，为它们分配资源，创建进程或分配,CPU,，使之投入运行。,先来先服务调度算法,(FCFS),的特点,作业调度和进程调度均可，最,简单,，本质上属,非剥夺方式,有利于长作业,/,进程，,不利于短作业,有利于,CPU,繁忙型的作业,(,如通常的科学计算,),，而不利于,I,O,繁忙的作业,/,进程（如大多数的事务处理,),例,短作业,(,进程,),优先调度算法,短作业,(,进程,),优先调度算法,SJ(P)F,，是指对短作业或短进程优先调度的算法。分别用于,作业调度和进程调度,短,作业,优先,(SJF),的调度算法，是从后备队列中选择一个或若干个,估计运行时间最短的作业,，将它们调入内存运行,短,进程,优先,(SPF),调度算法，则是从就绪队列中选出一,估计运行时间最短的进程,，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度,例,图,3-4 FCFS,和,SJF,调度算法的性能,SJ(P)F,调度算法,有利于短作业,，与,FCFS,算法相比，大大降低短作业的周转时间，平均周转时间短，系统吞吐量高,SJ(P)F,调度算法,对长作业不利,。甚至可能导致长作业,(,进程,),长期不被调度，发生,“,饥饿,”,现象,该算法,完全未考虑作业的紧迫程度,，因而不能保证紧迫性作业,(,进程,),会被及时处理,此外，由于作业,(,进程,),的长短只是根据用户所提供的估计执行时间而定的，而,用户又可能会有意或无意地缩短其作业的估计运行时间,，致使该算法不一定能真正做到短作业优先调度,短作业,(,进程,),优先调度,的特点,3.3.2,高优先权优先调度算法,既可用于,作业调度,，也可用于,进程调度,。,为,照顾紧迫性作业,，使之进入系统后获得优先处理，引入最高优先权优先调度算法。,按照进程的优先级大小来调度，使高优先级进程得到优先的处理的高度策略称为,优先权调度算法。,在许多采用优先级调度的系统中，通常采用,动态优先数策略,。进程的优先级不是固定的，往往随许多因素的变化而变化。尤其随作业（进程）的等待时间、已使用的处理机时间或其它资源的使用情况而定。,优先级调度方法又可分为：,非抢占的优先级调度法,：即一旦某个高优先级的进程占有了处理机，就一直运行下去，直到由于其自身的原因而主动让出处理机时,(,任务完成或等待事件,),才让另一高优先级进程运行。,主要用于,批处理系统,中；也可用于某些对,实时性要求不严的实时系统,中。,可抢占的优先级调度法,：任何时刻都严格按照高优先级进程在处理机上运行的原则进行进程的调度。,常用于,要求比较严格的实时系统,中， 以及,对性能要求较高的批处理和分时系统,中。,1、优先权调度算法的类型,例：,I/O,繁忙型的进程，它们,大部分时间是在等待,I/O,操作完成,，对于这一类进程，当它们要求,CPU,运行时，应立即给予满足，以便让它们开始下一个,I/O,操作和其它计算型的进程并行工作。否则，这些,I/O,繁忙型的进程将长时间占据存储器，降低系统并行度。,一个行之有效的算法是在进程每次获取,CPU,运行后，重新指定该进程的优先级为 1/,f,。,这里的,f,表示进程上次在,CPU,上,实际运行时间与时间片之比,。例如，若时间片为100毫秒，进程上次在,CPU,上的实际运行时间为2毫秒，则它的优先级为50；若它上次实际运行时间为50毫秒，则它的优级为2。由于,I/O,繁忙型的进程每次在,CPU,上运行的时间很短,，依此算法，它们的优先级将较高，从而优先得到服务。,实际中，,优先权算法常和轮转法,结合使用，也就是按优先级将进程分组，,组间,采用优先级调度算法，而,组内,优先级相同的进程则按轮转法调度。显然，若优先级不动态地进行调整，则优先级低的就绪进程就可能饿死。,2.,优先权的类型,1),静态优先权。静态优先权是,在创建进程时确定的,，且,在进程的整个运行期间保持不变,确定进程优先权的依据有如下三个方面：,进程类型,(2),进程对资源的需求,(3),用户要求,2),动态优先权。在创建进程时所赋予的优先权，是可以,随进程的推进或随其等待时间的增加而改变,的，以便获得更好的调度性能,例如，我们可以规定，在就绪队列中的进程，,随其等待时间的增长，其优先权以速率,a,提高,若所有的进程都具有,相同的优先权初值,，则显然是最先进入就绪队列的进程，将因其动态优先权变得最高而优先获得处理机，此即,FCFS,算法,若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机,当采用抢占式优先权调度算法时，如果再,规定当前进程的优先权以速率,b,下降,，则可防止一个长作业长期地垄断处理机,3.,高响应比优先调度算法,短作业优先算法的不足之处是,长作业的运行得不到保证,为每个作业,引入动态优先权,，使长作业在等待一段时间后，有机会分配到处理机,主要用于,作业调度,由于等待时间与服务时间之和，就是系统对该作业的,响应时间,，故该优先权又相当于响应比,R,P,。据此，又可表示为：,(1),如果作业的,等待时间相同,，则要求服务的时间愈短，其优先权愈高，因而该算法,有利于短作业,。,(2),当,要求服务的时间相同,时，作业的优先权,决定于其等待时间,，等待时间愈长，其优先权愈高，因而它实现的是,先来先服务,。,(3),对于,长作业,，作业的,优先级可以随等待时间的增加而提高,，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机。,调度之前，计算响应比，增加系统开销！,1,时间片轮转调度算法（仅适用于进程调度）,本质：属于剥夺方式,分时系统中,无例外采用,(,为确保响应时间,),方法：每个进程依次按,时间片,q,轮流执行，,q,的大小从几,ms,到几百,ms,。时间片用完则计时器触发一中断，重新调度，在一给定的时间内，就绪进程均能获得一时间片的执行时间。,时间片大小是关键问题,1.,时间片,q,正比于响应时间，反比于就绪进程数目。,2.,计算机的处理能力。速度快，,q,可小些。通常,q,值是这样决定的：,分时系统：,q=T/Nmax T-,响应时间上限,Nmax-,最大进程数,3.3.3,基于时间片的轮转调度算法,练习题,有下述五个进程，按照时间片轮转法进行调度。每个进程的到达时间和服务时间如下表所示。时间片长度为,1,个单位,，请描述各个,时间片的执行情况,，并计算,每个进程的结束时间,、,周转时间和带权周转时间,。,时间片长度为,1,个单位,时间片长度为,4,个单位,2.,多级反馈队列调度算法,不必事先知道各进程所需执行时间，可满足各种进程需要，是目前被公认较好的调度算法。,适用于进程调度,设置多个就绪队列，每个队列赋予不同的优先级。队列按,FCFS,原则排列,各队列,时间片不同,当一个新进程进入内存后，首先放在第一队列尾，按,FCFS,原则调度；如果该时间片内未结束，,转入第二队队列尾,；直到最后的第,N,队列，在第,N,队列采取按时间片轮转方式调度,仅,当第,I,队列空闲时,，才调度第,i+1,队列,如有新进程进入优先级较高的队列，则剥夺,CPU,执行新进程，旧进程放入原队列尾,例如，若一个进程总共需运行,100,个时间片,初始时指定它在优先级最高的进程组中，很快就会在,CPU,上运行一个时间片，之后优先级也降低一个级别,当它第二次有机会在,CPU,上运行时，它将运行2,t,以后它将在,CPU,上运行的时间长度依次是4，8，16，32和64个,t,，,最后一次运行时，只须64个,t,中的37个,t,就可完成,总共需,调度,7次。,比较单纯的轮转法，节省了93次,切,换时间,练习题,有下述五个进程，按照多级反馈调度算法进行调度。每个进程的到达时间和服务时间如下表所示。分别描述当时间片长度,P=1,和,P=,时，各个时间片的执行情况，并计算每个进程的结束时间、周转时间和带权周转时间。,3.,多级反馈队列调度算法的性能,终端型作业用户,：在第一队列中完成，作业短，交互型；,(2),短批处理作业用户,：周期时间较短，通常三个队列即可完成；,(3),长批处理作业用户,：依次在前,n,个队列中执行，然后再按轮转方式运行。,第三章 处理机调度与死锁,3.1,处理机调度的层次,3.2,调度队列模型和调度准则,3.3,调度算法,3.4,实时调度,3.5,产生死锁的原因和必要条件,3.6,预防死锁的方法,3.7,死锁的检测与解除,3.4,实时调度,实时进程或任务，用来反应或控制某个外部事件，,带有某种程度的紧迫性,，对调度提出了,特殊要求,。,3.4.1,实现实时调度的基本条件,1.,提供必要的信息（向调度程序提供）,就绪时间,(2),开始截止时间和完成截止时间,(3),处理时间,(4),资源要求,(5),优先级,2.,系统处理能力强,实时系统中通常都有着多个实时任务,若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理， 从而导致发生难以预料的后果,假定系统中有,m,个周期性的硬实时任务，它们的处理时间可表示为,C,i,，周期时间表示为,P,i,，则在单处理机情况下，必须满足下面的限制条件：,3.4.1,实现实时调度的基本条件,3.,采用抢占式调度机制,当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而,令高优先权任务立即投入运行,，这样便可满足该硬实时任务对截止时间的要求。这种,调度机制比较复杂,对于一些小的实时系统，如果能,预知,任务的开始截止时间，则对实时任务的调度,可采用非抢占调度,机制，,简化,调度程序和对任务调度时所花费的系统开销。但在设计这种调度机制时，应,使所有的实时任务都比较小，,并在执行完关键性程序和临界区后，能及时地将自己阻塞起来，以便释放出处理机，供调度程序去调度那种开始截止时间即将到达的任务,3.4.1,实现实时调度的基本条件,4.,具有快速切换机制,该机制应具有如下两方面的能力：,(1),对外部中断的快速响应能力,。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机,(,其它紧迫任务,),(2),快速的任务分派能力,。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销,3.4.1,实现实时调度的基本条件,3.4.2,实时调度算法的分类,实时任务性质的不同,硬实时调度算法,软实时调度算法,调度方式的不同,非抢占调度算法,抢占调度算法,调度时间的不同,静态调度算法,动态调度算法,多处理机环境,集中式调度算法,分布式调度算法,1.,非抢占式调度算法,非抢占式,轮转,调度算法,常用于工业生产群控系统，可获得数秒至数十秒的响应时间,(2),非抢占式,优先,调度算法。,可获得数秒至数百毫秒的响应时间,2.,抢占式调度算法,基于时钟中断的,抢占式优先权,调度算法。,较好的响应效果，调度延迟降为几十毫秒至几毫秒,(2),立即抢占,(Immediate Preemption),的优先权调度算法。,非常快的响应，调度延迟降为几毫秒至,100,微秒,3.4.3,常用的几种实时调度算法,1.,最早截止时间优先级,EDF(Earliest Deadline First),算法,根据任务的,开始截止时间,确定任务的优先级,截止时间越早，优先级越高,实时任务就绪队列按开始截止时间排序,可用于,抢占式,调度，也可用于,非抢占式,调度,1,）非抢占式调度方式用于非周期实时任务,图,EDF,算法用于非抢占调度方式,2,）抢占式调度方式用于,周期实时,任务,B2,B1,0,10,20,30,40,50,60,70,80,90,100,时间,t/ms,A1,A2,A3,A4,A5,A1,最后期限,A2,最后期限,A3,最后期限,A4,最后期限,B1,最后期限,B2,最后期限,A5,最后期限,到达时间,执行时间,最后期限,B2,B1,B2,B1,A1,A2,A3,A4,B2,A5,固定优先级,调度（,A,优先级高）,B1,错过,B1,B2,B1,2,）抢占式调度方式用于周期实时任务,0,10,20,30,40,50,60,70,80,90,100,时间,t/ms,A1,A2,A3,A4,A5,A1,最后期限,A2,最后期限,A3,最后期限,A4,最后期限,B1,最后期限,B2,最后期限,A5,最后期限,到达时间,执行时间,最后期限,A1,错过,A2,A3,A5,固定优先级,调度（,B,优先级高）,B2,A4,错过,B2,B1,B1,B2,B2,B1,2,）抢占式调度方式用于周期实时任务,0,10,20,30,40,50,60,70,80,90,100,时间,t/ms,A1,A2,A3,A4,A5,A1,最后期限,A2,最后期限,A3,最后期限,A4,最后期限,B1,最后期限,B2,最后期限,A5,最后期限,到达时间,执行时间,最后期限,A2,A3,最早截止时间优先,A1,A4,A5,2.,最低松弛度优先级,LLF(Least Laxity First),算法,根据任务紧急,(,或松弛,),的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高。,松弛程度,=,必须完成时间,-,运行时间,例如，一个任务在,200ms,时必须完成，而它本身所需的运行时间就有,100ms,，因此，调度程序必须在,100 ms,之前调度执行，该任务的紧急程度,(,松弛程度,),为,100 ms,。,一个按,松弛度排序的实时任务就绪队列,，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。,主要用于,可抢占调度方式,中。,图,A,和,B,任务每次必须完成的时间,假如在一个实时系统中，有两个周期性实时任务,A,和,B,，任务,A,要求每,20 ms,执行一次，执行时间为,10 ms,；任务,B,只要求每,50 ms,执行一次，执行时间为,25 ms,。,实例分析,图 利用,ELLF,算法进行调度的情况,小结,进程调度的考量标准,响应时间,进程自进入就绪队列开始至进程占用,CPU,之间的时间间隔,周转时间,进程自进入就绪队列开始至进程结束之间的时间间隔,CPU,吞吐量,单位时间内运行结束的进程个数,进程调度的原则,公平性原则,：,应保证每个进程获得合理的,CPU,份额,有效性原则,：,CPU,资源应得到最大限度的利用,友好性原则：响应时间快,与用户（人）交互的时间应尽可能的短,快捷性原则：周转时间短,批处理作业的处理时间尽可能的短,广泛性原则：吞吐量大,单位时间内完成的作业尽可能的多,时间片轮转调度,核心思想：,每个进程运行固定的时间片，然后调入下一个进程,实现机理：,维护就绪进程队列，采用,FIFO,方式一次读取,特殊控制：,时间片内发生阻塞或结束，则立即放弃时间片,优缺点分析,优点：绝对公平,缺点：公平即合理吗？时间片如何设计才能保证效率？,优先级调度,核心思想：,为每个进程赋予不同级别的优先级，越高越优先,实现机理：,维护一个优先级队列，自顶向下依次读取,特殊控制：,静态优先级与动态优先级概念,优缺点分析,优点：响应时间快，易于调整。最通用的方法,缺点：死规则，如何保证周转时间和吞吐量？,最短作业优先,核心思想：,保证响应时间最快、平均周转时间最短,实现机理：,依据先验信息，将进程按照运行时间增序调度,特殊控制：,如何确定最短作业？（老化算法）,优缺点分析,优点：保证了,CPU,的利用效率,缺点：无法通用，约束条件多,实时调度,针对于专用领域和专用应用目的,必须具备前提条件才能进行实时调度,特点：系统规模小、中断时间短、进程切换快、,OS,管理深度高,FCFS,（先来先服务）：只考虑等待时间；,SJF,（短作业优先算法）：只考虑执行时间；,HRRN,（高响应比优先算法）,RR,（时间片轮转算法）：机会均等，都能享有；,FB,（多级反馈队列调度算法）,EDF,（最早截止时间优先算法）,LLF,（最低松弛度优先算法）,吞吐量,系统开销,响应时间,反思：如何实现进程调度？,调度机制,不同调度算法适用于不同环境和不同目的,调度算法一旦固定，则其最优、最坏情况均无法避免,如能根据具体情况动态调整，则效果更佳,调度策略,为用户提供改变调整调度机制的渠道,实现方法,提供系统调用，能够改变调度机制,第三章 处理机调度与死锁,3.1,处理机调度的基本概念,3.2,调度算法,3.3,实时调度,3.4,多处理机系统中的调度,3.5,产生死锁的原因和必要条件,3.6,预防死锁的方法,3.7,死锁的检测与解除,死锁问题,(deadlock),OS,中重点之一,Newton,G.:”Deadlock Prevention,Detection,and Resolution:An annotated Bibliography,” Operating Systems Review,vol.13,pp.33-44,April 1979.,Zobel,D.:”The Deadlock Problem: A Classifying Bibliography,”Operating Systems Review,vol.17,pp6-16,Oct.1983.,Karacali ,B., Tai,KC., and Vouk,M.A.:”Deadlock Detection of EFSMs Using Simultaneous Reachability Analysis,” Proc. Intl Conference on Dependable systems and networks(DSN 2000),IEEE,pp.315-324,2000.,从一个例子开始,早期的操作系统对申请某种资源的进程，若该资源尚未分配时，立即将该资源分配给这个进程。,对资源,不加限制地分配,可能,导致进程间由于竞争资源而相互制约以至于无法继续运行,的局面，人们把这种局面称为,死锁,(deadlock),。,死锁问题在,1965,年由,Dijkstra,发现，并随着计算机技术的发展，逐渐成为人们关心的问题。,什么是死锁？其确切的定义是什么？死锁是怎么产生的？用什么方法来解决死锁？这些正是今天我们要讨论的问题。,显然各路车队等待的事件都不会发生,(,假设它们都不改变行车方向,),。 这样若不采用特殊方法，它们将永远停留在这“井”字形的路上，而处于,死锁,状态。,在计算机系统中，进程发生死锁与上述事例实质上是一样的。进程是因,相互竞争资源,而导致死锁的，与四路车队,(,可视为进程,),竞争路口,(,可视为资源,),类似。计算机系统中有各种资源，如,外设、数据、文件、程序,等。,3.5,产生死锁的原因和必要条件,死锁举例,进程,A,：获得,CD-ROM,使用权，申请打印机,进程,B,：获得打印机使用权，申请,CD-ROM,死锁,：此时进程,A,、,B,均被阻塞，无法运行,进程,A,进程,B,打印机,CD-ROM,教材定义：,所谓死锁,是指多个进程在运行过程中因争夺资源而造成的一种僵局（,Deadly-Embrace,），当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。,更规范的定义：,如果一个进程集合中的每个进程都在等待只能由该组进程中的其他进程才能引发的事件，那么，该组进程是死锁的。,现代操作系统,，,Andrew S. Tanenbaum,竞争资源,：系统资源不足,进程间,推进顺序非法,3.5.1,产生死锁的原因,1.,竞争资源引起进程死锁,永久性资源：,可以被多个进程多次使用（可再用资源）,可剥夺资源：,可从拥有它的进程中剥夺而不会产生任何副作用。,不可剥夺资源：,从拥有它的进程中剥夺会产生错误。,临时性资源：,只可使用一次的资源（可消耗性资源,如一个进程产生、被另一进程使用一短暂时间后便无用的资源）,1),资源分类,图,I/O,设备共享时的死锁情况,2),竞争非剥夺性资源,在系统中所配置的非剥夺性资源，由于它们的,数量不能满足,诸进程运行的需要，会使进程在运行过程中，,因争夺这些资源而陷入僵局,图,3-13,进程之间通信时的死锁,3),竞争临时性资源,临时性资源,，是指由一个进程产生，被另一个进程使用一短暂时间后便无用的资源，故也称之为,消耗性资源,，它也,可能,引起死锁。,推进方式,1,P1,：,Release(S1),；,Request(S3),；,P2,：,Release(S2),；,Request(S1),；,P3,：,Release(S3),；,Request(S2),；,推进方式,2,P1,：, Request(S3),；,Release(S1),；,P2,：, Request(S1),；,Release(S2),；,P3,：, Request(S2),；,Release(S3),；,造成死锁,2.,进程推进顺序不当引起死锁,Q,进程,释放,A,释放,B,获得,A,获得,B,A,申请,B,申请,P,和,Q,申请,A,P,和,Q,申请,B,P,进程,获得,A,释放,A,获得,B,释放,B,A,申请,B,申请,3.5.2,产生死锁的必要条件,互斥条件：,某段时间内，某资源只能由一个进程使用；,请求和保持条件：,进程因请求资源而阻塞时，对已分配给它的资源保持不放；,不剥夺条件 ：,资源在未使用完前，不能被剥夺，由使用进程释放；,环路等待条件 ：,发生死锁时，有向图必构成一环路。,上述死锁的四个必要条件,不是彼此独立的,，比如条件,4,包含了前三个条件。将它们分别列出是为了方便我们研究各种防止死锁的方法。,Coffman,E.G.,Elphick,M.J.,and,Shoshani,A.:,“,System,Deadlocks,”,Computing,Suyveys,vol.3,pp.67-78,June,1971.,3.5.3,处理死锁的基本方法,顺其自然,：忽略此问题不做任何实际处理,(,鸵鸟策略,),设计无死锁的系统,先礼后兵,：允许系统出现死锁后排除之,斩草除根,：,死锁防止,(deadlock prevention),先发制人,：,死锁避免,(deadlock avoidance),死锁检测,(deadlock detection),死锁恢复,(deadlock recovery),鸵鸟算法,思想：不采取任何措施，对死锁视而不见。,实例：,UNIX,系统、,Windows,（还有其它许多系统）。,由于不预防、避免死锁，故系统中可能发生死锁。而发生时又无法知道（因不检测），造成系统崩溃，需要重启。,之所以被某些系统采用，是因为死锁不常发生。,第三章 处理机调度与死锁,3.1,处理机调度的基本概念,3.2,调度算法,3.3,实时调度,3.4,多处理机系统中的调度,3.5,产生死锁的原因和必要条件,3.6,预防死锁的方法,3.7,死锁的检测与解除,通过破坏死锁存在的,(4,个,),必要条件来防止死锁发生。,我们不妨把死锁的四个必要条件记做,C1,，,C2,，,C3,，,C4,，把死锁记做,D,，,则有逻辑公式：,D,C1,C2,C3,C4,，,由离散数学公式推导得：,C1,C2,C3,C4,D,式中的“”表示“蕴含”；“”表示“与”；“”表示“或”；“”表示“非”。,由,上,式可知，,只要系统中有一个必要条件不成立就能不出现死锁,，此即死锁防止的思想基础。,3.6.1,预防死锁,(1),破坏互斥条件,如果允许系统资源都能共享使用，则系统不会进入死锁状态。但这种方法,不是切实可行,的。因为有些资源若是共享使用，例如：打印机在多进程打印，不能每个进程打印一行，则无法保证其正确性。又如，对临界资源的访问就必须互斥进行。,(2),破坏“请求和保持”条件,方法：规定进程在执行前要,一次性地申请运行所需全部资源,。只有资源全部到手，进程方可运行，否则进程等待。,优点：简单、易于实现。,缺点：,1.,资源利用率低。,2.,进程运行被延迟。,例：,P1,申请,r1, r2, r3,，,而仅有,r3,。,这时,P2,申请,r3,；,则把,r3,给,P2,，,某一进程,Pi,又释放了,r1, r2,，,而,P1,又因无,r3,，,仍需等待直到饿死,P1,。,(3),破坏非剥夺性条件,方法：保持资源的进程申请新资源失败时，在转为阻塞状态之前，必须释放其占用的全部资源。而该进程自身则必须等到,重新获得原有资源,及新资源后，才能重新运行。,缺点：实现复杂，代价大。􀂾,适用范围：资源的状态能够很方便的保存和恢复，例如,CPU,寄存器和存储空间。,方法：将系统中所有资源赋予一个全局编号，进程申请资源时，必须按编号递增顺序进行。􀂾,缺点：,1.,限制了新类型设备的增加；,2.,找不出一种人人满意的编号顺序；,3.,仍存在资源浪费；,4.,用户编程受到限制。,(4),破坏循环等待条件,死锁, 四个必要条件,(4,个必要条件,)(,死锁,),4,个必要条件,死锁,(,不一定,),死锁防止是严格破坏,4,个必要条件之一，一定不出现死锁；而,死锁的避免是不那么严格地限制死锁必要条件的存在,，其目的是提高系统的资源利用率。万一当死锁有,可能,出现时，就,小心避免,这种情况的发生。,3.6.2,系统安全状态,1,安全状态,安全状态,：指系统能按某种顺序如,（称序列,为安全序列），来,为每个进程分配其所需资源,，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个安全序列，则称系统处于,不安全状态,。,避免死锁的实质：使系统在资源分配过程中，不进入不安全状态。,系统中有,12,台磁带机。由进程,P1,、,P2,和,P3,共享，运行一段时间后（假设此时为,T0,），情况如下表所示：,进 程,最 大 需 求,已 分 配,可 用,P,1,P,2,P,3,10,4,9,5,2,2,3,系统在,T0,时刻是否安全？,如果接下来系统把剩余,3,台其中的,1,台分配给,P3,，系统是否安全？,安全,不安全,2,安全状态之例,银行家算法：冒险的代价,仿照银行,发放贷款,采取的控制方式而设计的死锁避免算法,银行的目的是利润最大化，风险最低化。为控制风险，在给客户发放贷款之前，先,审核客户的信用额度,。信用额度由客户提出请求，银行审核后决定是否批准。批准后，客户对资金的,使用是按阶段,的。,假定所有客户信用良好，能够按期还款。银行审核考虑的因素就是银行是否有钱满足客户。即：只要客户的信用额度不超过银行的全部流动资产，即予以批准，否则拒绝。,面对客户请求，银行有两种可选策略：,1,）只要银行有钱就发放贷款；,2,）需考虑发放贷款后银行面临的风险。,例,假定某银行全部流动资金为,10000,元。客户,A,申请,4000,元的信用额度，予以批准；客户,B,申请,6000,元的信用额度，予以批准；客户,C,申请,10000,元的信用额度，予以批准；客户,D,申请,12000,元的信用额度，因为该额度超过银行的全部流动资金，予以拒绝。,1,、假定,A,、,B,、,C,向银行提出下列贷款申请：,A,要求贷款,2000,元,B,要求贷款,4000,元,C,要求贷款,2000,元,2,、假定,A,、,B,、,C,向银行提出下列贷款申请：,A,要求贷款,2000,元,B,要求贷款,4000,元,C,要求贷款,3000,元,3.6.3,利用银行家算法避免死锁,单种资源银行家算法,多种资源银行家算法,3.6.3,利用银行家算法避免死锁,1.,银行家算法中的数据结构,(1),可利用资源向量,Available,。,这是一个含有,m,个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，,其数值随该类资源的分配和回收而动态地改变。,如果,Available,j,=K,，则表示系统中现有,R,j,类资源,K,个。,(2),最大需求矩阵,Max,。,这是一个,nm,的矩阵，它定义了系统中,n,个进程中的每一个进程对,m,类资源的最大需求。如果,Max,i,j,=K,，则表示进程,i,需要,R,j,类资源的最大数目为,K,。,(3),分配矩阵,Allocation,。,这也是一个,nm,的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果,Allocation,i,j,=K,，则表示进程,i,当前已分得,R,j,类资源的数目为,K,。,(4),需求矩阵,Need,。,这也是一个,nm,的矩阵，用以表示每一个进程,尚需的各类资源数,。如果,Need,i,j,=K,，则表示进程,i,还需要,R,j,类资源,K,个，方能完成其任务。,Need,i,j,=Max,i,j,-Allocation,i,j,2.,银行家算法,3.,安全性算法,(1),设置两个向量, 工作向量,Work:,它表示系统可提供给进程继续运行所需的各类资源数目，它含有,m,个元素，在执行安全算法开始时，,Work=Available;, Finish:,它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做,Finish,i,=false;,当有足够资源分配给进程时， 再令,Finish,i,=true,。,(2),从进程集合中找到一个能满足下述条件的进程：,Finish,i,=false; Need,i,j,Work,j,； 若找到， 执行步骤,(3),， 否则，执行步骤,(4),。,(3),当进程,Pi,获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：,Work,j,=Work,j,+Allocation,i,j,;,Finish,i,=true;,go to step 2;,(4),如果所有进程的,Finish,i,=true,都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。,4.,银行家算法之例,假定系统中有五个进程,P,0, P,1, P,2, P,3, P,4,和三类资源,A, B, C,，各种资源的数量分别为,10,、,5,、,7,，在,T,0,时刻的资源分配情况如图,3-15,所示。,图,3-16,T,0,时刻的资源分配表,(1) ,T,0,时刻的安全性：,图,3-17,T,0,时刻的安全序列,(2),P,1,请求资源：,P,1,发出请求向量,Request,1,(1,，,0,，,2),，,系统按银行家算法进行检查：,Request,1,(1, 0, 2)Need,1,(1, 2, 2), Request,1,(1, 0, 2)Available,(3, 3, 2),系统先假定可为,P,1,分配资源，并修改,Available, Allocation,1,和,Need,1,向量，由此形成的资源变化情况如图,3-16,中的圆括号所示。, 再利用安全性算法检查此时系统是否安全。,图,3-18 P,1,申请资源时的安全性检查,(3) P,4,请求资源：,P,4,发出请求向量,Request,4,(3,，,3,，,0),，系统按银行家算法进行检查：,Request,4,(3, 3, 0)Need,4,(4, 3, 1);,Request,4,(3, 3, 0) Available(2, 3, 0),，让,P,4,等待,。,(4) P,0,请求资源：,P,0,发出请求向量,Requst,0,(0,，,2,，,0),，系统按银行家算法进行检查：,Request,0,(0, 2, 0)Need0(7, 4, 3);, Request,0,(0, 2, 0)Available(2, 3, 0);,系统暂时先假定可为,P,0,分配资源，并修改有关数据，如图,3-19,所示。,图,3-19,为,P,0,分配资源后的有关资源数据,(5),进行安全性检查：进入不安全状态，因此系统不分配资源。,Question,：若,P,0,发出的请求向量是（,0,，,1,，,0,），系统是否能将资源分配给它？如果能安全序列是什么？,系统中有三种资源（,A,，,B,，,C,）和,5,个进程,P1,P5,资源总数为（,17,，,5,，,20,），,T0,时刻系统状态如表所示，系统采用银行家算法实施死锁避免策略,最大资源需求量,已分配资源量,A,B,C,A,B,C,P1,5,5,9,2,1,2,P2,5,3,6,4,0,2,P3,4,0,11,4,0,5,P4,4,2,5,2,0,4,P5,4,2,4,3,1,4,请解答以下问题：,（,1,）,T0,时刻是否为安全状态？若是则给出安全序列,（,2,）在,T0,时刻,P2,请求资源（,0,，,3,，,4,），是否能够实施资源分配，为什么？,（,3,）在（,2,）的基础上，若,P4,请求资源（,2,，,0,，,1,），是否能够实施分配，为什么？,（,4,）在（,3,）的基础上，若,P1,请求资源（,0,，,2,，,0,），是否能够实施分配，为什么？,第三章 处理机调度与死锁,3.1,处理机调度的基本概念,3.2,调度算法,3.3,实时调度,3.4,多处理机系统中的调度,3.5,产生死锁的原因和必要条件,3.6,预防死锁的方法,3.7,死锁的检测与解除,当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供,检测和解除死锁,的手段。为此，系统必须：,保存有关资源的请求和分配信息,提供一种算法，,利用这些信息,检测系统是否进入死锁状态,3.7.1,死锁的检测,设立一个,检测进程,（平时处于睡眠状态）周期性地被唤醒去检查系统中有无进程处于死锁状态。,1.,资源分配图,RAG,（,Resource Allocation Graph,）,系统死锁可用资源分配图描述,图,3-20,每类资源有多个时的情况,资源分配图在系统中是,随时间变化,的。当进程,P,i,请求,r,j,时，将一条请求边(,P,i, r,j,),加在图中。若此请求被满足(分给,P,i,一个,r,j,类的资源)，则将这个请求边改成分配边(,r,j, P,i,),。,当进程,P,i,释放一个,r,j,时，便去掉分配边(,r,j, P,i,),。,1.,找只有分配边而没有请求边相连的进程结点，将其分配边删掉。,2.,找虽有请求边，但请求边可立即全部转化成分配边的进程结点，将其请求边转化为分配边，再将分配边删掉。,3.,经过,1,和,2