《操作系统》第3章处理机调度与死锁

第三章处理机调度与死锁重点掌握进程调度算法，各适用于何种情况理解常用的几种实时调度算法理解产生死锁的原因掌握银行家算法避免死锁难点多道程序设计中的各种调度算法响应比高者优先调度算法的计算过程银行家算法第三章处理机调度与死锁知识点处理机调度及调度算法多处理机环境下的进程（线程）调度方式产生死锁的原因和必要条件预防死锁的方法，死锁的检测与解除银行家算法第三章处理机调度与死锁处理机是计算机系统中的重要资源在多道程序环境下，进程数目通常多于处理机的数目系统必须按一定方法动态地把处理机分配给就绪队列中的一个进程处理机利用率和系统性能（吞吐量、响应时间）在很大程度上取决于处理机调度WHAT：按什么原则分配CPU—进程调度算法WHEN：何时分配CPU—进程调度的时机

HOW：如何分配CPU—CPU调度过程（进程的上下文切换）第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.2作业与作业调度3.3进程调度3.4实时调度3.5死锁描述3.6预防死锁3.7避免死锁3.8死锁的检测与解除3.1.1处理机调度的层次高级调度(HighScheduling)

作业调度或长程调度（Long-TermScheduling）按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业分配内存、输入/输出设备等必要的资源，并建立相应的进程，放入就绪队列，以使该作业的进程获得竞争处理机的权利。也称为接纳调度（AdmissionScheduling）时间尺度：通常是分钟、小时或天。3.1.1处理机调度的层次低级调度

进程调度或短程调度（Short-TermScheduling）按照某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它。常见调度方式非抢占式；抢占式。时间尺度：通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效。3.1.1处理机调度的层次中级调度(Intermediate-LevelScheduling)

中程调度(Medium-TermScheduling)引入目的提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待。交换过程按照给定的原则和策略，将处于外存对换区中的重又具备运行条件的就绪进程调入内存，或将处于内存就绪状态或内存阻塞状态的进程交换到外存对换区。3.1.1处理机调度的层次进程调度的运行频率最高，在分时系统中通常是10～100ms便进行一次进程调度，因此把它称为短程调度。为避免进程调度占用太多的CPU时间，进程调度算法不宜太复杂。作业调度往往是发生在一个(批)作业运行完毕，退出系统，而需要重新调入一个(批)作业进入内存时，故作业调度的周期较长，大约几分钟一次，因此把它称为长程调度。由于其运行频率较低，故允许作业调度算法花费较多的时间。中级调度的运行频率基本上介于上述两种调度之间，因此把它称为中程调度。3.1.2处理机调度算法的目标处理调度算法的共同目标资源的利用率公平性平衡性策略强制执行3.1.2处理机调度算法的目标基本术语到达时间作业进入后备作业队列或新创建进程进入就绪队列的时刻；服务时间作业（进程）占用处理机的时间开始时间作业被创建进入就绪队列或进程首次占有处理机的时刻完成时间用户获得作业执行结果的时刻。3.1.2处理机调度算法的目标批处理系统的目标平均周转时间短周转时间，指从作业被提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)。它包括四部分时间：作业在外存后备队列上等待(作业)调度的时间；进程在就绪队列上等待进程调度的时间进程在CPU上执行的时间；进程等待I/O操作完成的时间。注意：此三项在一个作业的处理过程中可能会发生多次。周转时间=完成时间-到达时间3.1.2处理机调度算法的目标批处理系统的目标平均周转时间短平均周转时间带权周转时间：进程（或作业）的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS

。平均带权周转时间带权周转时间=周转时间/服务时间3.1.2处理机调度算法的目标批处理系统的目标系统吞吐量高吞吐量指单位时间内系统所完成的作业数作业调度的方式和算法对吞吐量的大小有较大影响处理机利用率高各类资源的平衡利用使内存、外存和I/O设备的利用率高3.1.2处理机调度算法的目标分时系统的目标响应时间快响应时间，从用户通过键盘提交一个请求开始，直至系统中首次产生响应为止的时间交互式系统用周转时间衡量不是最佳均衡性系统响应时间的快慢与用户所请求服务的复杂性相适应。3.1.2处理机调度算法的目标实时系统的目标截止时间保证截止时间，某任务必须开始执行的最迟时间或必须完成的最迟时间截止时间是实时系统中的重要指标可预测性数据的到达或将要处理任务的要求是可预测的。3.1.2处理机调度算法的目标问题的本质周转时间短响应时间快截止时间保证批处理系统分时系统实时系统等待时间短优先级3.1.2处理机调度算法的目标目标实现等待时间短等待时间，在就绪队列中等待所花的时间调度算法并不影响进程运行和执行I/O的时间量；只影响进程在就绪队列中等待所花费的时间优先级准则在批处理、实时和分时系统中都可以选择优先级准则，以便让紧急任务先处理有时还选择抢占式调度方式3.2作业与作业调度3.2.1批处理系统中的作业3.2.2作业调度的主要任务3.2.3先来先服务和短作业优先调度算法3.2.4优先级调度算法和高响应比调度算法3.2.1批处理系统中的作业作业和作业步作业(Job)。用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等。作业步(JobStep)。通常，在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。例，一个典型的作业可分成三个作业步：①“编译”作业步；②“链接装配”作业步；③“运行”作业步。3.2.1批处理系统中的作业作业控制块（JobcontrolBlock,JCB）作业在系统中存在的标志；包括作业标识、用户名称、用户账号、作业类型（CPU繁忙型、I/O繁忙型、批量型、终端型）、作业状态、调度信息（优先级、作业运行时间）、资源需求（预计运行时间、要求内存大小）、资源使用情况。3.2.1批处理系统中的作业作业运行的三个阶段和三种状态一个作业进入系统到运行结束，一般需要经历收容、运行、完成三个阶段，与之相对应的是作业的三种状态后备状态运行状态完成状态3.2.1批处理系统中的作业作业状态间转换运行状态后备状态完成状态就绪阻塞执行I/O完成I/O请求时间片完作业注册作业调度进程调度终止作业3.2.2作业调度的主要任务作业调度的主要功能根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。接纳多少个作业即允许多少个作业同时在内存中运行，取决于多道程序度（DegreeofMultiprogramming）作业太多服务质量下降作业太少资源利用率低3.2.2作业调度的主要任务接纳哪些作业取决于作业调度算法先来先服务短作业优先作业优先级调度响应比调度多道程序度：即允许多少个作业同时在内存中运行。周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。吞吐量：是指在单位时间内系统所完成的作业数。3.2.3先来先服务和短作业优先算法先来先服务(FCFS)/先进先出(FIFO)调度算法按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业/进程最简单的调度算法，既可用于作业调度，也可用于进程调度3.2.3先来先服务和短作业优先算法进程名到达时间服务时间开始时间完成时间周转时间带权周转时间平均04A13B25C32D44E044476先来先服务（先进先出）：712101214111418141225.53.592.8AAAABBBCCCCCDDEEEE05101518t3.2.3先来先服务和短作业优先算法先来先服务（先进先出）优缺点比较有利于长作业（进程），而不利于短作业（进程）有利于CPU繁忙型作业（进程），而不利于I/O繁忙型作业（进程）用于批处理系统，不适于分时系统3.2.3先来先服务和短作业优先算法先来先服务（先进先出）等待时间：J1=0;J2=0;J3=100；J4=100平均等待时间：(0+0+100+100)/4=50平均周转时间：(1+100+101+200)/4=100.5平均带权周转时间：(1+1+101+2)/4=26.25作业到达时间服务时间开始时间完成时间周转时间带权周转时间J101J21100J311J4210001110110110210220211100110110120023.2.3先来先服务和短作业优先算法先来先服务（先进先出）等待时间：J1=0;J2=1;J3=0；J4=100平均等待时间：(0+1+0+100)/4=25.25平均周转时间：(1+1+101+200）/4=75.75平均带权周转时间：（1+1+1.01+2）/4=1.2525作业到达时间服务时间开始时间完成时间周转时间带权周转时间J101J311J21100J421000112210210220211111011.0120023.2.3先来先服务和短作业优先算法短作业(进程)优先调度算法SJ(P)F按运行时间长短进行调度，即先启动要求运行时间最短的作业（进程）短作业优先(SJF)的调度算法：从后备队列中选择一个或若干个估计运行时间最短的作业，调入内存运行；短进程优先(SPF)调度算法：从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。3.2.3先来先服务和短作业优先算法作业名到达时间服务时间开始时间完成时间周转时间带权周转时间平均04A13B25C32D44E0441短作业/短进程优先（SJF/SPF）：4631.56982.6791392.251318163.282.1AAAABBBCCCCCDDEEEE05101518t3.2.3先来先服务和短作业优先算法SJ(P)F调度算法的缺点对长作业不利。严重的是，由于调度程序总是优先调度短作业(进程)，将导致长作业(进程)长期不被调度——饥饿不能保证紧迫性作业(进程)会被及时处理；不一定能真正做到短作业优先调度。由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间。优先级调度算法对于先来先服务算法，作业的等待时间就是作业的优先级，等待时间越长，优先级越高。对于短作业优先算法，作业的长短就是作业的优先级，作业所需时间越短，其优先级越高。在优先级算法，根据作业的紧迫程度，由外部给予作业不同的优先级，然后根据优先级调度3.2.4优先级和高响应比优先调度算法高响应比优先调度算法（HRRN）FCFS和SJF的结合，克服了两种算法的缺点调度策略：响应比最高的作业优先启动因等待时间+服务时间=该作业的响应时间，故该优先级又相当于响应比RP。据此，又可表示为3.2.4优先级和高优先比优先调度算法优先级=等待时间+要求服务时间要求服务时间Rp=等待时间+要求服务时间要求服务时间

响应时间要求服务时间=3.2.4优先级和高优先比优先调度算法对HRRN的小结等待时间相同的作业，则要求服务的时间愈短，其优先级愈高，要求服务的时间相同的作业，则等待时间愈长，其优先级愈高，长作业，优先级随等待时间的增加而提高，其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机，是一种折衷，既照顾了短作业，又考虑了作业到达的先后次序，又不会使长作业长期得不到服务。缺点：要进行响应比计算，增加了系统开销——对短作业有利——先来先服务——对长作业有利优先级=

等待时间+要求服务时间要求服务时间

响应时间要求服务时间=优先级=

等待时间+服务时间服务时间当前时间-到达时间+服务时间服务时间=作业名到达时间服务时间响应比开始时间完成时间周转时间带权周转时间平均04A13B25C32D44E04411418143.54762914122.479638.42.38高响应比优先，非抢占式21.41.51231.752.42.253.53.2.4优先级和高优先比优先调度算法作业到达时间要求服务时间开始执行时间完成时间周转时间带权周转时间J18.02.0J28.60.6J38.80.2J49.00.5平均①②③④⑤⑥8.08.69.09.69.210.111.39.63.31.651.01.670.42.01.12.2/9.2/8.81.451.88/10.1⑦高响应比优先，抢占式3.2.4优先级和高优先比优先调度算法3.3进程调度3.3.1进程调度的任务、机制和方式3.3.2轮转调度算法3.3.3优先级调度算法3.3.4多队列调度算法3.3.5多级反馈队列调度算法3.3.6基于公平原则的调度算法3.3.1进程调度的任务、机制和方式进程调度的任务保存处理机的现场信息。将正在运行进程的上下文保存到PCB及相应的数据结构中。按某种算法选取进程。控制、协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选中一个进程。把处理器分配给进程。把CPU的使用权交给被选中的进程，并装入选中进程的上下文。3.3.1进程调度的任务、机制和方式进程调度机制

根据预定的算法，将系统中所有的就绪进程排成一个或多个队列，以便调度程序能最快地找到它。分派程序把由进程调度程序所选定的进程，从就绪队列中取出该进程，然后进行上下文切换，将处理机分配给它。①OS保存当前进程的上下文，装入分派程序的上下文；②将移出分派程序，把新选进程的CPU现场信息装入到处理机的各个相应寄存器中。3.3.1进程调度的任务、机制和方式进程调度方式非抢占方式(Non-preemptiveMode)抢占方式(PreemptiveMode)3.3.1进程调度的任务、机制和方式进程调度方式——非抢占方式进程正在处理机上执行时，新就绪的进程进入就绪队列，该进程仍继续执行，直到其完成或发生某种事件而进入完成或阻塞状态时，才转让处理机。引起进程调度的因素正在执行的进程执行完毕，或因发生某事件而不能再继续执行执行中的进程因提出I/O请求而暂停执行；在进程通信或同步过程中执行了某种原语操作，如wait、Block、Wakeup原语优点：算法简单，系统开销小缺点：紧急任务不能及时响应；短进程到达要等待长进程运行结束进程调度方式——抢占方式进程正在处理机上执行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程抢占式调度原则优先级原则允许高优先级的新到进程抢占当前进程的处理机短作业(进程)优先原则允许执行时间短的新到进程抢占当前进程的处理机时间片原则时间片用完后停止执行，重新进行调度，适用于分时系统优点：适于时间要求严格的实时系统缺点：调度算法复杂，系统开销大3.3.1进程调度的任务、机制和方式3.3.2轮转调度算法轮转法的基本原理系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便停止该进程的执行，并将其放就绪队列尾；然后，再把处理机分配给就绪队列中新的队首时间片的大小从几ms到几百ms缺点：紧迫任务响应慢。UNIX中采用：时间片+优先级3.3.2轮转调度算法进程切换时间任务在给定时间片内已完成，则将它标记为终止状态，立即激活调度程序进行调度；任务在时间片内未完成，计时器中断处理程序被激活，则将进程进入就绪队列末尾，启动调度程序调度；3.3.2轮转调度算法时间片大小的确定时间片选择问题固定时间片可变时间片与时间片大小有关的因素系统响应时间就绪进程个数CPU能力

基于时间片的轮转调度算法进程名到达时间服务时间开始时间完成时间周转时间带权周转时间平均ABCDEABCDEABCEACEC05101518t04A03B05C02D04E01234912151718153.75124183.694.5174.2514.24.02若到达时间为0、1、2、3、4，又如何？基于时间片的轮转调度算法进程名到达时间服务时间开始时间完成时间周转时间带权周转时间平均ABACBDAECBDAECECEC05101518t04A13B25C32D44E01357111012171812393163.284133.2511.63.293.3.3优先级调度算法优先级调度算法的类型非抢占式特点：系统一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去，直至完成，或因发生某事件使该进程放弃处理机时，系统才将处理机重新分配给另一优先级最高的进程主要用于批处理系统中，也可用于某些对实时性要求不严的实时系统中3.3.3优先级调度算法优先级调度算法的类型抢占式把处理机分配给优先级最高的进程，在执行期间，只要出现另一个优先级更高的进程，则进程调度程序就立即停止当前进程的执行，并将处理机分配给新到的优先级最高的进程只要系统中出现一个新的就绪进程，就进行优先级比较能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中3.3.3优先级调度算法优先级的类型静态优先级静态优先级在创建进程时确定，且在进程的整个运行期间保持不变。一般地，优先级是利用某一范围内的一个整数来表示的，例如，07或0255，又把该整数称为优先数确定进程静态优先级的依据进程类型:系统进程，用户进程进程对资源的需求用户要求问题：用户将优先级设的较高，对其他进程不利！！短进程优先对长进程不利！！3.3.3优先级调度算法动态优先级随进程的推进或随其等待时间的增加而改变。例，在就绪队列中的进程，优先级随等待时间的增长，以某一速率提高；相同优先级初值的进程，则最先进入就绪队列的进程，优先获得处理机，即FCFS算法各不相同的优先级初值的就绪进程，则优先级初值低的进程，在等待了足够的时间后，其优先级便可能升为最高，从而可以获得处理机当采用抢占式优先级调度算法时，如果再规定当前进程的优先级以某一速率下降，则可防止一个长作业长期地垄断处理机。进程到达时间服务时间开始时间完成时间周转时间带权周转时间P107P215P323P432P544平均等待时间：(14+5+0+2+7)/5=5.6平均周转时间：(21+10+3+4+11）/5=9.8平均带权周转时间：(3+2+1+2+2.75）/5=2.15①⑤②④③⑥⑦012557/7111115/15212131023142112.753.3.3优先级调度算法——实例抢占式短进程优先SPF调度3.3.3优先级调度算法——实例进程名到达时间服务时间静态优先级开始时间完成时间周转时间带权周转时间平均静态优先级，非抢占式（1为最高优先级）04A413B225C332D544E104414841811103.331116142.81618157.59.42.93考虑一下抢占式，情况如何？进程名到达时间服务时间静态优先级开始时间完成时间周转时间带权周转时间平均高优先级优先调度算法04A413B225C332D544E101616448411431813112.21618157.59.83.14静态优先级，抢占式（1为高优先级）ABBBEEEECCCCCAAADD05101518tBAACDEACD3.3.4多队列调度算法单一就绪队列→多个就绪队列例，将就绪进程分别进入前台和后台就绪队列前台就绪队列是交互性作业的进程，通常采用时间片轮转。后台的就绪队列是批处理作业的进程，通常采用优先级或短作业优先算法。调度方式有两种：优先调度前台，若前台无可运行进程，才调度后台。分配占用CPU的时间比例，如：前台80%，后台20%3.3.5多级反馈(multilevedfeedback)队列调度算法调度机制

设置多个就绪队列，各个队列赋予不同的优先级第一个队列的优先级最高，第二个队列次之，其余各队列的优先级逐个降低各个队列中进程执行时间片的大小也各不相同，在优先级愈高的队列中，为每个进程所规定的执行时间片就愈小。例，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍就绪队列13.3.5多级反馈队列调度算法就绪队列2就绪队列3就绪队列nS1S2S3至CPU至CPU至CPU至CPU(时间片：S1＜S2＜S3)调度方式高低优先级时间片小大Sn按FIFO原则排队等待调度尚未完成转入第二队列的末尾，按FIFO原则等待调度采取按时间片轮转的方式运行因等待而放弃CPU后，进入阻塞队列，一旦等待的事件发生，则回到原来的就绪队列3.3.5多级反馈队列调度算法多级反馈队列调度算法注意仅当第1~(i-1)队列均空时，才会调度第i队列中的进程运行第i队列中某进程正在运行时，又有新进程进入优先级较高的队列(第1~(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，调度程序把正在运行的进程放回到第i队列的末尾第i队列中某进程正在运行时，该进程因等待事件发生而进入阻塞队列，等待事件发生后，调度程序把进程放回到第i队列的末尾3.3.5多级反馈队列调度算法调度算法的性能终端型作业用户提交的作业多属于交互型作业，通常较小，系统只要能使这些作业在第一队列所规定的时间片内完成即可短批处理作业用户若在第1队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间如在第一个队列中不能完成，只需在第2、3队列中各执行一个时间片长批处理作业用户长作业将依次在第1，2，3…，n队列中执行，最终按轮转方式运行3.3.6基于公平原则的调度算法保证调度算法向用户做出明确的性能保证易实现的算法：处理机分配的公平性当工作时已有n个用户登录在系统，则将获得CPU处理能力的1/n。类似的，在一个有n个进程运行的用户系统中，每个进程将获得CPU处理能力的1/n。实现方法OS应记录及计算,各个进程在一定时间段内,已经使用的CPU时间和应该得到的CPU时间,二者之比小者优先级高3.3.6基于公平原则的调度算法公平分享调度算法每个用户分配到CPU时间的一部分，而调度程序以一种强制的方式选择进程。这样，如果两个用户都得到获得50%CPU时间的保证，那么无论一个用户有多少进程存在，每个用户都会得到应有的CPU份额。例，用户1有4个进程A、B、C和D，而用户2只有1个进程E。如果采用轮转调度，一个满足所有限制条件的可能序列是：AEBECEDEAEBECEDE…3.3.6线程调度OS只调度核心级线程；用户级线程必须映射到内核线程才能运行；本地调度（进程竞争范围，PCS）线程库决定如何将哪个线程调度到有效的LWP上。M::M，M::O全局调度（系统竞争范围，SCS）内核决定调度那一个线程到CPU上运行。O::O仅采用SCSPCS根据优先级完成，由程序员设置。线程调度API#include<pthread.h>#include<stdio.h>#defineNUM_THREADS5intmain(intargc,char*argv[]){ inti,scope; pthread_ttid[NUM_THREADS]; pthread_attr_tattr; /*getthedefaultattributes*/ pthread_attr_init(&attr); /*settheschedulingalgorithmtoPROCESSorSYSTEM*/ pthread_attr_setscope(&attr,PTHREAD_SCOPE_SYSTEM); /*settheschedulingpolicy-FIFO,RT,orOTHER*/ pthread_attr_setschedpolicy(&attr,SCHED_OTHER);线程调度API /*createthethreads*/ for(i=0;i<NUM_THREADS;i++) pthread_create(&tid[i],&attr,runner,NULL); /*nowjoinoneachthread*/ for(i=0;i<NUMTHREADS;i++) pthread_join(tid[i],NULL);}/*Eachthreadwillbegincontrolinthisfunction*/void*runner(void*param){ printf("Iamathread\n"); pthread_exit(0);}3.4实时调度3.4.1实现实时调度的基本条件3.4.2实时调度算法的分类3.4.3最早截止时间优先算法3.4.4最低松弛度优先算法3.4.5优先级倒置3.4.1实现实时调度的基本条件提供必要的信息就绪时间。开始截止时间和完成截止时间。处理时间。资源要求。优先级。3.4.1实现实时调度的基本条件系统处理能力强假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件，系统才是可调度的：

3.4.1实现实时调度的基本条件系统处理能力强提高系统的处理能力的途径采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间；采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件改为：

3.4.1实现实时调度的基本条件采用抢占式调度机制在含有硬实时任务的实时系统中，广泛采用抢占机制。存在的问题：调度机制比较复杂。解决策略：对于一些小型实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制。关键：应使所有的实时任务都比较小，并在执行完关键性程序和临界区后，能及时地将自己阻塞起来3.4.1实现实时调度的基本条件具有快速切换机制对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)。快速的任务分派能力。在完成任务调度后，应进行任务切换。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当地小，以减少任务切换的时间开销。3.4.2实时调度算法的分类非抢占式调度算法非抢占式轮转调度算法工业生产的群控系统，由一台计算机控制若干个相同的(或类似的)对象，为每一个被控对象建立一个实时任务，并将它们排成一个轮转队列。调度程序每次选择队列中的第一个任务投入运行。当该任务完成后，便把它挂在轮转队列的末尾，等待下次调度运行，而调度程序再选择下一个(队首)任务运行。可获得数秒至数十秒的响应时间，可用于要求不太严格的实时控制系统中。3.4.2实时调度算法的分类非抢占式调度算法非抢占式优先调度算法要求较为严格(响应时间为数百毫秒)的任务，采用非抢占式优先调度算法为这些任务赋予较高的优先级。当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后才能被调度执行。做了精心的处理后，有可能获得仅为数秒至数百毫秒级的响应时间，因而可用于有一定要求的实时控制系统中。3.4.2实时调度算法的分类抢占式调度算法基于时钟中断的抢占式优先级调度算法在某实时任务到达后，如果该任务的优先级高于当前任务的优先级，这时并不立即抢占当前任务的处理机，而是等到时钟中断到来时，调度程序才剥夺当前任务的执行，将处理机分配给新到的高优先级任务。能获得较好的响应效果，其调度延迟可降为几十毫秒至几毫秒。因此，此算法可用于大多数的实时系统中。3.4.2实时调度算法的分类抢占式调度算法立即抢占(ImmediatePreemption)的优先级调度算法要求操作系统具有快速响应外部事件中断的能力。一旦出现外部中断，只要当前任务未处于临界区，便立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。能获得非常快的响应，可把调度延迟降低到几毫秒至100微秒，甚至更低。3.4.3最早截止时间优先EDF(EarliestDeadlineFirst)算法实现方法优先级确定：根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。实时任务就绪队列：按各任务截止时间的早晚排序；具有最早截止时间的任务排在队列的最前面。调度顺序：总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。适用范围：既可用于抢占式调度，也可用于非抢占式调度方式中。3.4.3最早截止时间优先EDF算法非抢占式调度方式用于非周期实时任务例

任务到达时间开始截止时间完成时间

A013B2101C242D364任务名到达时间服务时间开始截止时间开始时间完成时间截止与完成差是否能保证03A121B1022C434D603C>A是91035D>C是59B>D是AA0359tBCD3.4.3最早截止时间优先EDF算法ADBBCCDDDB3.4.3最早截止时间优先EDF算法抢占式调度方式用于周期实时任务例，两个周期性任务，任务A的周期时间为20ms，每个周期的处理时间为10ms；任务B的周期时间为50ms，每个周期的处理时间为25ms。3.4.3最早截止时间优先EDF算法B1的截止时间到，未完成A1的截止时间到，未完成3.4.3最早截止时间优先EDF算法抢占式调度方式用于周期实时任务采用最早截止时间优先算法的时间图。3.4.4最低松弛度优先LLF(LeastLaxityFirst)算法实现方法松弛度=截止时间-任务执行时间-当前时间优先级的确定任务紧急(或松弛)的程度，紧急程度愈高，任务的优先级就愈高。实时任务就绪队列按松弛度排序，松弛度最低的任务排在队列最前面，调度程序总是选择队列中的队首任务执行。主要适用范围：可抢占调度也就是任务的，机动时间随着时间的推移：

就绪队列中任务的松弛度减少

执行任务的松弛度不变调度时机：松弛度为0，或新任务就绪，或当前任务完成3.4.4最低松弛度优先LLF算法例有两个周期性实时任务A和B，任务A要求每45ms执行一次，执行时间为15ms；任务B只要求每60ms执行一次，执行时间为40ms。由此可得知任务A和B每次必须完成的时间分别为：A1、A2、A3、…和B1、B2、B3、…。3.4.4最低松弛度优先LLF算法t1=0时，A1的松弛度=45-15=30msB1的松弛度=60-40=20ms注意：A1的松弛度<B1的运行时间t2=30时，A1的松弛度=45-15-30=0msB1的松弛度=60-10-30=20mst1B1t2A1t3=45时，A2的松弛度=90-15-45=30msB1的松弛度=60-10-45=5mst3B1t4A2t5B2t6A3t7B3t8A4t9B4与t1时类似注意：B1的松弛度>A1的运行时间被占用3.4.5优先级倒置（priorityinversionproblem）优先级倒置的形成申请使用被抢先等待（阻塞）3.4.5优先级倒置优先级倒置的形成例，有优先级为A、B和C三个任务P1，P2和P3，优先级A>B>C，任务P1和P3使用信号量S共享资源。3.4.5优先级倒置优先级倒置的解决方法优先级天花板(priorityceiling)当任务申请某资源时，把该任务的优先级提升到可访问这个资源的所有任务中的最高优先级。优点：简单易行，不必进行复杂的判断。优先级继承(priorityinheritance)当任务P1申请共享资源S时，如果S正在被任务P3使用，通过比较任务P3与P1的优先级，如发现任务P3的优先级小于P1的优先级，则将任务P3的优先级提升到P1的优先级，任务P3释放资源S后，再恢复任务P3的原优先级。3.4.5优先级倒置优先级倒置的解决方法例：优先级继承3.4.6操作系统实例Solaris调度WindowsXP调度Linux调度Java线程调度Solaris调度采用基于优先级的线程调度。根据优先级分为四类调度，分别为：实时系统分时交互每个类型有不同的优先级和调度算法。默认调度类型是分时，采用多级反馈队列动态地调整优先级和赋予不同长度的时间片。3.4.6操作系统实例Solaris调度3.4.6操作系统实例（cont.）Solaris调度优先级和时间片之间有反比关系（默认）优先级越高，时间片越小优先级越低，时间片越大交互进程通常具有更高的优先级。CPU型进程有更低的优先级。交互和时间共享线程的分配表WindowsXP调度基于优先级的、抢占调度算法来调度线程。调度程序处理调度一个被选定运行线程一直运行到被更高优先级的线程抢占终止时间片已到调用了阻塞系统调用3.4.6操作系统实例（cont.）WindowsXP调度调度程序使用32级优先级方案确定线程执行顺序。优先级分为两大类型：可变类型1~15级线程；实时类型16~31级线程0级线程用于内存管理。如果没有就绪线程，调度空闲线程。WindowsXP内核和Win32API的优先级数值之间有一个关系。3.4.6操作系统实例（cont.）WindowsXP调度Win32API定义了一个进程可能属于的一些优先级类型。包括：REALTIME_PRIORITY_CLASSHIGH_PRIORITY_CLASSABOVE_NORMAL_PRIORITY_CLASSNORMAL_PRIORITY_CLASSBELOW_NORMAL_PRIORITY_CLASSIDLE_PRIORITY_CLASS3.4.6操作系统实例（cont.）WindowsXP调度每个给定优先级类型的线程拥有相对优先级。相对优先级的值包括：TIME_CRITICALHIGHESTABOVE_NORMALNORMALBELOW_NORMALLOWESTIDLE3.4.6操作系统实例（cont.）WindowsXP调度线程的优先级=线程类型+相对优先级。基础优先级=每个类型中NORMAL相对优先级3.4.6操作系统实例（cont.）WindowsXP调度对于不同优先级类型的线程：时间片耗尽时，优先级降低，不低于基础优先级。当从Wait操作返回时，调度程序提高它的优先级：键盘I/O完成时，大幅度提高；磁盘I/O完成时，中等程度提高。对于交互性程序前台进程后台进程3.4.6操作系统实例（cont.）WindowsXP调度与线程调度有关的API函数及功能说明Suspend/ResumeThread挂起/激活一个正在/暂停运行的线程Get/SetPriorityClass读/设置一个线程的基本优先级类型Get/SetThreadPrority读/设置一个线程的基本优先级Get/SetProcessPriorityBoost读/设置当前进程优先级提升控制Get/SetThreadPriorityBoost读/设置暂时线程优先级状态：在可调范围内Get/SetProcessAffinityMask读/设置进程的默认处理器集合SetThreadAffinityMask设置线程的默认处理器集合SetThreadIdealProcessor设置线程的首选处理器，但不限制线程在该处理器SwitchToThread当前线程放弃一个或多个时间配额的运行Sleep使当前线程等待一个指定的时间段SleepEx使当前线程进入等待状态3.4.6操作系统实例（cont.）Linux调度采用基于优先级的、抢占调度算法。两个独立的优先级范围Real-time范围：0~99级Nice范围：100~140级每个处理器都有自己的运行队列：活动队列到期队列当所有任务耗尽时间片时，两个队列交换3.4.6操作系统实例（cont.）Linux调度实时任务分配静态优先级。其它的采用动态优先级：nice±5任务的交互性决定增加/减少5。任务的交互性决定于它在等待I/O时沉睡了多长时间。睡眠时间长=>更多交互=>-5重新计算时机：任务耗尽了时间片，被移至到期队列中。3.4.6操作系统实例（cont.）优先级和时间片长度的关系根据优先级编号的任务列表Java线程调度JVM采用基于优先级的、抢占式线程调度。如果多个线程具有同样的优先级采用FIFO队列。JVM调度一个线程运行，当当前运行线程退出runnable状态；高优先级线程到达runnable状态。注意：JVM并不通知线程的时间片是否耗尽。3.4.6操作系统实例（cont.）Java线程调度由于JVM不能保证时间片，可以采用yield()方法。

while(true){ //performCPU-intensivetask ... Thread.yield(); }yield()控制另一个相同优先级的进程。3.4.6操作系统实例（cont.）Thread优先级Java线程调度优先级

注释Thread.MIN_PRIORITY线程最小优先级Thread.MAX_PRIORITY线程最大优先级Thread.NORM_PRIORITY线程默认优先级Priorities可以通过setPriority()方法设置setPriority(Thread.NORM_PRIORITY+2);3.5死锁描述3.5.1资源问题3.5.2计算机中的死锁3.5.3死锁的定义、必要条件和处理方法3.5.1

资源问题死锁例子设系统有一台打印机(R1)一台扫描仪(R2)，两进程共享这两台设备。用信号量S1表示R1是否可用，用信号量S2表示R2是否可用，S1、S2初值为1。3.5.1

资源问题可重用性资源和消耗性资源可重用性资源，可重复使用多次的资源。性质每类资源的每个实例只能分配给一个进程使用，不能共享；资源使用模式：申请→分配→使用→释放；每个资源的实例数目有限，进程不能创建，也不能删除。3.5.1

资源问题可重用性资源和消耗性资源可消耗性资源，又称为临时性资源，只可使用一次；由一个进程产生，被另一进程使用后就再也无用的资源。性质每类资源的每个实例可以不断变化；进程在运行期间可以不断地创造资源的实例；进程在运行期间可以不断地消耗资源的实例。3.5.1

资源问题可抢占（剥夺）资源和不可抢占（剥夺）资源可抢占（剥夺）资源：进程在获得这类资源后，该资源可以再被其他进程或系统剥夺，如处理机、内存等不可抢占（剥夺）资源：当系统把这类资源分配给某个进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等3.5.2计算机系统中的死锁竞争不可抢占性资源

由于数量有限而不能满足进程运行的需要，进程在运行过程中因争夺这些资源而限入僵局竞争可消耗性资源共同点：形成环路！！R1R2P1P2分配分配请求请求I/O设备共享S2P1S3P3S1P2P1产生P2产生P3产生要求接收要求接收要求接收进程之间通信3.5.2计算机系统中的死锁进程推进顺序不当引起死锁P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④D不安全区3.5.3

死锁的定义、必要条件和处理方法死锁的定义多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，此现象称为进程死锁，该组进程就称为死锁进程。3.5.3

死锁的定义、必要条件和处理方法关于死锁的一些结论参与死锁的进程最少是两个参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。3.5.3

死锁的定义、必要条件和处理方法产生死锁的必要条件互斥

进程对所分配到的资源进行排它性的使用请求和保持

进程已经至少保持了一个资源，但又提出了新的资源请求，而该资源又已被其他进程占有不可抢占

进程已获得的资源在未使用完之前不能被剥夺循环等待在发生死锁时，必然存在一个进程--资源循环等待的环形链3.5.3

死锁的定义、必要条件和处理方法处理死锁的方法预防死锁通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止发生死锁。避免死锁不采用各种限制措施去破坏产生死锁的必要条件，防止系统进入不安全状态，只需在事先加以较弱的限制条件。检测与解除死锁允许系统在运行过程中发生死锁。一旦检测到死锁，常用的实施方法是撤消或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。3.6预防死锁3.6.1破坏“请求和保持”条件3.6.2破坏“不可抢占”条件3.6.3破坏“循环等待”条件3.6.1破坏“请求和保持”条件非请求所有进程在开始运行之前必须一次性的申请整个运行过程所需的全部资源优点：简单、易于实现、安全缺点：资源浪费严重进程延迟运行3.6.1破坏“请求和保持”条件非保持申请其他资源之前，必须释放其现在已分配的所有资源。优点：资源利用率高；减少进程发生饥饿的可能性。缺点：需要资源协调工作时，可能无法实现。3.6.2破坏“不可抢占”条件可抢占进程逐个地申请所需资源当一个已经保持了某些资源的进程申请新资源而不能得到满足时，必须放弃所有已保持的资源缺点实现复杂、代价高昂延长了进程的周转时间，还增加了系统开销，降低了系统的吞吐量3.6.3破坏“循环等待”条件顺序等待系统将所有资源按类型分配序号并排队；所有进程申请资源必须按序号递增的顺序。优点资源利用率和系统吞吐量较高。序号资源1输入机2打印机3磁带机进程需求资源P1打印机磁带机P2磁带机打印机例子3.6.3破坏“循环等待”条件3.6.3破坏“循环等待”条件存在问题资源所分配的序号，必须相对稳定，这就限制了新设备类型的增加。进程使用各资源的顺序，与系统规定的顺序不同，造成对资源的浪费。按规定次序申请资源的方法，必然会限制了用户简单、自主地编程。3.7避免死锁3.7.1系统安全状态3.7.2利用银行家算法避免死锁3.7.3利用资源分配图法避免死锁3.7避免死锁提前获取“进程申请资源的附加信息”最简单且有效的模型要求每个进程事先声明它所需要的每种资源的最大数量。动态检查资源分配状态，以保证不存在循环等待的条件。资源分配状态通过可用资源数量、已分配资源数量，及进程最大申请数量来定义。3.7.1系统安全状态安全状态安全序列：进程序列<P1,P2,…,Pn>，如果对于每个Pi，Pi申请的资源小于当前可用资源加上所有进程Pj（其中j<i）所占有的资源。安全状态：存在安全序列的系统状态；不安全状态：不存在安全序列的系统状态；结论如果系统是安全的，则不会死锁；如果系统不安全，可能会发生死锁；3.7.1系统安全状态避免死锁的实质允许进程动态地申请资源，但在进行资源分配时，如果不会导致系统进入不安全状态，则分配资源给进程，否则，令进程等待。关键：确保系统不会进入不安全状态。3.7.1系统安全状态安全状态之例假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：29P324P23510P1可用已分配最大需求进程415100109312存在安全序列：P2-P1-P3，系统处于安全状态。3.7.1系统安全状态由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。进程最大需求已分配可用P11053P242P39232404不安全状态

3.7.2利用银行家算法避免死锁银行家算法中的数据结构(1)可利用资源向量Available。一个有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。3.7.2利用银行家算法避免死锁银行家算法中的数据结构(2)最大需求矩阵Max。n×m的矩阵，系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i][j]=K，则表示进程i需要Rj类资源的最大数目为K。(3)分配矩阵Allocation。n×m的矩阵，每一类资源已分配给每一进程的资源数。如果Allocation[i][j]=K，表示进程i当前已分得Rj类资源的数目为K。(4)需求矩阵Need。n×m的矩阵，每一个进程尚需的各类资源数。如果Need[i][j]=K，则表示进程i还需要Rj类资源K个，才能完成其任务。Need[i][j]=Max[i][j]–Allocation[i][j]3.7.2利用银行家算法避免死锁银行家算法设Requesti是进程Pi的请求向量，如果Requesti[j]=K，进程Pi需要K个Rj类型的资源。当Pi发出请求后，按下述步骤进行检查：(1)若Requesti[j]≤Need[i][j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)若Requesti[j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。3.7.2利用银行家算法避免死锁银行家算法(3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

Available[j]=Available[j]-Requesti[j];Allocation[i][j]=Allocation[i][j]+Requesti[j];Need[i][j]=Need[i][j]-Requesti[j];(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。3.7.2利用银行家算法避免死锁安全性算法(1)设置两个向量：①Work:可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available;②Finish:是否有足够的资源分配给进程，使之运行完成。初值Finish[i]=false;当有足够资源分配给进程时，令Finish[i]=true。3.7.2利用银行家算法避免死锁安全性算法(2)从进程集合中找到一个能满足下述条件的进程：①Finish[i]=false;②Need[i][j]≤Work[j]；若找到，执行步骤(3)，否则，执行步骤(4)。(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j]=Work[i]+Allocation[i][j];Finish[i]=true;

转step2;(4)如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。3.7.2利用银行家算法避免死锁假定系统中有五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如下表。CB01001B32223C32025B04P439P223307P022P323P1AAAAvailableNeedAllocationMaxCB21200C110233102446701A3.7.2利用银行家算法避免死锁(1)T0时刻的安全性：truetruetruetruetrueFinish77532C54443B02210C10010B30112C40312B75322C44433B100710P07047P45213P110367P27205P3AAAAWork+AllocationAllocationNeedWork存在安全序列：P1-P3-P4-P2-P0，系统在T0时刻处于安全状态。P4P2P0P3P1NeedCB110233102446701AP4P2P0P3P1NeedCB110233102446701A3.7.2利用银行家算法避免死锁(2)P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查：①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available1(3,3,2)MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P44330024313.7.2利用银行家算法避免死锁③系统先假定可为P1分配资源，并修改Available,Allocation1和Need1向量。Request1(1，0，2)2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMax3220000323.7.2利用银行家算法避免死锁④再利用安全性算法检查此时系统是否安全。truetruetruetruetrueFinish75532C55443B20212C01010B03110C04312B55320C54433B10367P27047P45302P17077P07205P3AAAAWork+AllocationAllocationNeedWork存在安全序列：P1-P3-P4-P0-P2，系统处于安全状态，可以满足P1资源分配请求。3.7.2利用银行家算法避免死锁(3)P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：①Request4(3,3,0)≤Need4(4,3,1);②Request4(3,3,0)≤Available(2,3,0)，让P4等待。MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P44330024313.7.2利用银行家算法避免死锁(4)P0请求资源：P0发出请求向量Request0(0，2，0)，系统按银行家算法进行检查：①Request0(0,2,0)≤Need0(7,4,3);②Request0(0,2,0)≤Available(2,3,0);MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P44330024313.7.2利用银行家算法避免死锁③系统暂时先假定可为P0分配资源，并修改有关数据。Request0(0，2，0)MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431723210030不安全状态3.7.2利用银行家算法避免死锁(5)P0请求资源：P0发出请求向量改为Request0(0,1,0)，系统按银行家算法进行检查：①Request0(0,1,0