操作系统教学03.pptx

第三章 处理机调度与死锁第三章 处理机调度与死锁3.1 处理机调度的层次3.2 调度队列模型和调度准则3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 3.1 3.1 处理机调度的层次处理机调度的层次n在多道程序系统中，一个作业从提交到执行，通常都要经历多级调度如高级调度、低级调度、中级调度以及IO调度等n系统的运行性能在很大程度上取决于调度如吞吐量的大小、周转时间的长短、响应的及时性等n调度是多道系统的关键n CPU资源管理多道程序设计面临的挑战批处理系统：如何安排内存中多个作业的运行顺序？交互式系统：如何更好应对不同的交互式请求？实时系统：如何保证实时服务的高质量？n 进程调度有效的管理CPU资源When：何时进行进程调度？How：遵循何种规则完成调度？What：调度过程中需要完成哪些工作？n 进程调度的级别高级调度：也称宏观调度，决定哪些程序可以进入系统中级调度：也称内存调度，决定内存中程序的位置和状态低级调度：也称微观调度，决定CPU资源在就绪进程间的分配3.1.1 高级调度l 又称作业调度或长程调度，其主要功能是按照某种原则从磁盘某些盘区的作业队列中选取作业进入主存，并为作业做好运行前的准备工作和作业完成后的善后工作。l 其调度对象是作业作业作业n作业（JOB）是用户在一次算题过程中或一次事务处理中，要求计算机系统所做的工作的集合n作业是比进程更广泛的概念，不仅包含了通常的程序和数据，而且还配有一份作业说明书，系统根据作业说明书对程序运行进行控制。在批处理系统中，以作业为单位从外存调入内存n用户为了让计算机完成某个特定任务，首先编写成源程序，然后提交给计算机通过编译或汇编、连接、装配、运行等步骤，最终由计算机送出用户所需要的运行结果。从计算机管理的角度看，上述一系列的一系列的由计算机执行的任务的集合就是作业由计算机执行的任务的集合就是作业。中国民航大学计算机科学与技术学院$END$RUNData for program$LOADFortran program$FORTRAN$JOB,10,429754CherryChen作业步作业步编辑编译或汇编连接装入运行n计算机完成作业是通过执行一系列有序的工作步骤进行的，每个步骤完成作业的一部分特定工作n把计算机系统完成一个作业所需的一系列有序的相对独立的工作步骤称为作业步n作业的各个作业步虽然功能相对独立，但它们之间相互关联，往往是一个作业步的执行需要使用上一个作业步的执行结果。n若干个作业进入系统后，被依次存放在外存上，形成输入的作业流；在操作系统控制下，逐个作业进行处理，形成处理的作业流作业流作业流作业控制块作业控制块u作业提交给系统进入后备状态后，系统将为每个作业建立一个作业控制块JCB。u JCB在作业的整个运行过程中始终存在，并且其内容与作业的状态同步地动态变化。只有当作业完成并退出系统时，JCB才被撤消。可以说，JCB是一个作业在系统中存在的惟一标志，系统根据JCB才感知到作业的存在u 作业控制块JCB中包含了对作业进行管理的必要信息，JCB中的信息一部分是从用户提供的作业控制卡或作业说明书中得到，另一部分是记录作业运行过程中的动态信息u JCB的具体内容因系统不同而异作业名作业名资源要求预估的运行时间最迟完成时间要求的内存量要求外设类型、台数要求的文件量和输出量资源使用情况进入系统时间开始运行时间已运行时间内存地址外设台号类型级别控制方式作业类型优先级状态用户账户作业控制块 作业调度作业调度u主要功能u根据JCB，审查系统能否满足用户作业的资源需求u按一定算法，从外存后备队列中选取某些作业调入内存u为它们创建进程、分配必要资源u将新创建的进程插入就绪队列，准备执行作业调度作业调度u 用户希望自己作业的周转时间尽可能少u 系统希望作业的平均周转时间尽可能少u 执行作业调度，必须做两个决定：1）决定接纳多少个作业 2）决定接纳哪些作业u 先来先服务（FCFS）u 短作业优先（SF）u 优先级高优先（HPF）u 响应比高者优先（RPF）作业调度作业调度l主要用于批处理系统。其设计目标是最大限度地发挥各种资源的利用率和保持系统内各种活动的充分并行l 对资源需求不同的作业进行合理搭配。科学计算往往需要占用大量的CPU时间，属于CPUCPU繁忙型作业繁忙型作业，对于I/O设备的使用程少；而数据处理恰恰相反，它们要求占用较少的CPU时间，但要求大量I/O时间，属于I/OI/O繁忙型作业繁忙型作业；另外有些递归计算，产生大量中间结果。需要很多内存单元存放它们，这属于内存繁忙型作业内存繁忙型作业。如果能把它们搭配在一起。例如程序A在使用处理机，程序B在利用通道l，而程序C恰好利用通道2等，这样一来，A、B和C从来不在同一时间使用同一资源，每个程序就好像单独在一个机器上运行l 按用户自然提交作业的顺序，可能出现对资源需求“一边倒”的情况。所以，批处理系统中要收容大量的后备作业，以便从中选出最佳搭配的作业组合l又称进程调度或短程调度，其主要功能是按照某种原则将将处处理理机机分分配配给给就就绪绪进进程程。执行低级调度功能的程序称为进程调度程序，由它实现处理机在进程间的转换。它必须常驻主存，是操作系统内核内核的主要部分l实际上，进程调度程序主要是完成一台物理的CPU转变成多台虚拟(或逻辑)的CPU的工作l在多道批处理、分时和实时系统中都必须配备3.1.2 低级调度进程调度程序的主要功能n保存现场。当前运行的进程调用进程调度程序时，即表示该进程要求放弃CPU(因时间片用完或等待I/O等原因)。这时，进程调度程序把它的现场信息，如程序计数器及通用寄存器的内容等保留在该进程PCB的现场信息区中n挑选进程。根据一定的调度算法(如优先级算法)，从就绪队列中选出一个进程来，并把它的状态改为运行态，准备把CPU分配给它n恢复现场把处理器分配给进程。为选中的进程恢复现场信息，并把CPU的控制权交给该进程,它接着上次间断的地方继续运行进程调度中的三个基本机制n排队器。将就绪进程按一定方式排成队列n分派器（分派程序）。把进程调度程序选定的进程，从就绪队列中取出，进行上下文切换，把处理器分配给它n上下文切换机制。保存当前进程上下文，装入分派程序上下文，分派程序运行；移出分派程序，装入新选进程上下文进程调度方式1 1非抢占方式非抢占方式(Non-Preemptive Mode)(Non-Preemptive Mode)u一旦处理机分配，便让进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其它进程u优点：实现简单、系统开销小，适用于大多数的批处理系统环境u缺点：难于满足需要立即执行的紧急任务，在要求比较严格的实时系统中不宜采用u在采用非抢占调度方式时，可能引起进程调度的因素：u正在执行的进程执行完毕，或因发生某事件而不能再继续执行 u执行中的进程因提出I/O请求而暂停执行u在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等2 2抢占方式抢占方式(Preemptive Mode)(Preemptive Mode)u允许调度程序停止正在执行的进程，将已分配给该进程的处理机，重新分配重新分配给另一进程u抢占的原则有u 时间片原则u 优先权原则u 短作业(进程)优先原则u 优点：可防止长进程长时间占有处理机，为多数进程提供公平服务u 缺点：系统开销较大进程调度方式u 中级调度又称中程调度(Medium-Term Scheduling)u 引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量u 使那些暂时不能运行的进程不再占用宝贵的内存资源，将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态u 当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的那些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度u 对换(存储器管理)u 短期调整系统负荷，平顺系统操作3.1.2 中级调度调度类型调度类型运行频率运行频率运行时间运行时间算法复杂性算法复杂性进程调度进程调度高高短短低低中程调度中程调度中等中等较短较短中等中等作业调度作业调度低低长长高高三级调度比较三级调度比较三级调度的相互比较三级调度的相互比较 高级调度中级调度低级调度外存到内存内外存互换内存中批处理实时分时运行频率高运行频率适中运行频率低第三章 处理机调度与死锁3.1 处理机调度的层次3.2 调度队列模型和调度准则3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 n高级调度、中级调度、低级调度，都将涉及到作业或进程队列，共有三种类型的调度队列模型。3.2 3.2 调度队列模型和调度准则调度队列模型和调度准则 3.2.1 3.2.1 调度队列模型调度队列模型仅有进程调度的调度队列模型仅有进程调度的调度队列模型分时系统通常仅设置进程调度。每个进程执行都可能出现三种情况：(1)任务在该时间片内已完成，释放CPU进入完成状态；(2)任务在本次时间片内尚未完成，OS便将该任务放在就绪队列的后面；(3)执行期间，进程因某事件而被阻塞，放人阻塞队列。具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型实例：批处理操作系统(1)引入了作业调度：从外存的后备队列中选择选择一批作业调入内存，为之创建进程后送入就绪队列。最常用的是优先权队列。(2)设置多个阻塞队列，每个对应一种阻塞原因。同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型n在OS中引人中级调度后，就绪状态分为：内存就绪和外存就绪两种状态；阻塞状态分成：内存阻塞和外存阻塞两种状态。内存紧张换出时，内存就绪转变为外存就绪、内存阻塞转变为外存阻塞；在中级调度的作用下，又可使外存就绪转为内存就绪。3.2.2选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则n取决于操作系统的类型和目标n不同的操作系统，有不同的调度方式和算法n有面向用户的准则，也有面向系统的准则面向用户的准则面向用户的准则n周转时间周转时间短（批处理系统）n响应时间快（分时系统）n截止时间的保证（实时系统）截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。n优先权准则（批处理、分时、实时）让某些紧急的作业得到及时的处理。在要求较严格的场合可采用抢占调度方式。u周转时间，是指从作业提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)，它包括：(1)作业在外存后备队列上等待(作业)调度的时间；(2)进程在就绪队列上等待进程调度的时间；(3)进程在CPU上执行的时间；(4)等待IO操作完成的时间。平均周转时间平均周转时间短会有效地提高资源利用率，且可使大多数用户感到满意。短会有效地提高资源利用率，且可使大多数用户感到满意。平均周转时间可描述为：平均周转时间可描述为：若系统为作业提供的实际服务时间为若系统为作业提供的实际服务时间为TsTs，W=TW=TTsTs称为带权周转时间，称为带权周转时间，平均带权周转时间平均带权周转时间可表示为：可表示为：u响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说直到在屏幕上显示为止的一段时间间隔。它包括：(1)从键盘输入的请求信息传送到处理机的时间；(2)处理机对请求信息进行处理的时间；(3)将所形成的响应回送到终端显示器的时间面向系统的准则面向系统的准则1系统吞吐量高（批处理）吞吐量是指在单位时间内所完成的作业数。2处理机利用率好大、中型多用户系统，CPU昂贵，处理机的利用率成为衡量系统性能的重要指标3各类资源的平衡利用第三章 处理机调度与死锁3.1 处理机调度的层次3.2 调度队列模型和调度准则3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 3.3 调度算法n在OS中，调度的实质是资源分配。n调度算法是指：根据系统的资源分配策略所规定的资源分配算法。n不同的系统和系统目标，采用不同的调度算法。先来先服务调度算法短作业优先调度算法高优先权优先调度算法基于时间片的轮转调度算法先来先服务调度算法先来先服务调度算法n最简单的调度算法。n既可用于作业调度作业调度，也可用于进程调度进程调度。n每次调度都是选择一个或多个最先进入队列的作业或进程，为它们分配资源，创建进程或分配CPU，使之投入运行。先来先服务调度算法(FCFS)的特点l作业调度和进程调度均可，最简单简单，本质上属非剥夺方式l有利于长作业/进程，不利于短作业l有利于CPU繁忙型的作业(如通常的科学计算)，而不利于IO繁忙的作业/进程（如大多数的事务处理)例例短作业短作业(进程进程)优先调度算法优先调度算法n短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。分别用于作业调度和进程调度作业调度和进程调度n短作业作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行n短进程进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度例例图 3-4 FCFS和SJF调度算法的性能 nSJ(P)F调度算法有利于短作业，与FCFS算法相比，大大降低短作业的周转时间，平均周转时间短，系统吞吐量高nSJ(P)F调度算法对长作业不利。甚至可能导致长作业(进程)长期不被调度，发生“饥饿”现象n该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理n此外，由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度 短作业短作业(进程进程)优先调度优先调度的特点的特点3.3.2高优先权优先调度算法高优先权优先调度算法n既可用于作业调度作业调度，也可用于进程调度进程调度。n为照顾紧迫性作业，使之进入系统后获得优先处理，引入最高优先权优先调度算法。n按照进程的优先级大小来调度，使高优先级进程得到优先的处理的高度策略称为优先权调度算法。n在许多采用优先级调度的系统中，通常采用动态优先数策略。进程的优先级不是固定的，往往随许多因素的变化而变化。尤其随作业（进程）的等待时间、已使用的处理机时间或其它资源的使用情况而定。优先级调度方法又可分为：非抢占的优先级调度法：即一旦某个高优先级的进程占有了处理机，就一直运行下去，直到由于其自身的原因而主动让出处理机时(任务完成或等待事件)才让另一高优先级进程运行。主要用于批处理批处理系统系统中；也可用于某些对实时性要求不严的实时系统实时性要求不严的实时系统中。可抢占的优先级调度法：任何时刻都严格按照高优先级进程在处理机上运行的原则进行进程的调度。常用于要求比较严格的实时要求比较严格的实时系统系统中，以及对性能要求较高的批处理和分时系统对性能要求较高的批处理和分时系统中。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)静态优先权。静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变确定进程优先权的依据有如下三个方面：确定进程优先权的依据有如下三个方面：(1)(1)进程类型进程类型 (2)(2)进程对资源的需求进程对资源的需求(3)(3)用户要求用户要求 2)动态优先权。在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能 例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高a)若所有的进程都具有相同的优先权初值相同的优先权初值，则显然是最先进入就绪队列的进程，将因其动态优先权变得最高而优先获得处理机，此即FCFS算法b)若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机c)当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机3.高响应比优先调度算法高响应比优先调度算法n短作业优先算法的不足之处是长作业的运行得不到保证n为每个作业引入动态优先权，使长作业在等待一段时间后，有机会分配到处理机n主要用于作业调度由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：(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.2.多级反馈队列调度算法多级反馈队列调度算法n不必事先知道各进程所需执行时间，可满足各种进程需要，是目前被公认较好的调度算法。适用于进程调度n设置多个就绪队列，每个队列赋予不同的优先级。队列按FCFS原则排列n各队列时间片不同时间片不同n当一个新进程进入内存后，首先放在第一队列尾，按FCFS原则调度；如果该时间片内未结束，转入第二队队列尾转入第二队队列尾；直到最后的第N队列，在第N队列采取按时间片轮转方式调度n仅当第当第I I队列空闲时队列空闲时，才调度第i+1队列n如有新进程进入优先级较高的队列，则剥夺CPU执行新进程，旧进程放入原队列尾例如，若一个进程总共需运行例如，若一个进程总共需运行100100个时间片个时间片l 初始时指定它在优先级最高的进程组中，很快就会在CPU上运行一个时间片，之后优先级也降低一个级别l 当它第二次有机会在CPU上运行时，它将运行2tl 以后它将在CPU上运行的时间长度依次是4，8，16，32和64个t，最后一次运行时，只须64个t中的37个 t 就可完成l 总共需总共需调度调度7 7次。次。比较单纯的轮转法，节省了93次切换时间练习题练习题 有下述五个进程，按照多级反馈调度算法进行调度。每个进程的到达时间和服务时间如下表所示。分别描述当时间片长度P=1和P=时，各个时间片的执行情况，并计算每个进程的结束时间、周转时间和带权周转时间。3.3.多级反馈队列调度算法的性能多级反馈队列调度算法的性能 (1)(1)终端型作业用户终端型作业用户：在第一队列中完成，作业短，交互型；(2)短批处理作业用户短批处理作业用户：周期时间较短，通常三个队列即可完成；(3)长长批批处处理理作作业业用用户户：依次在前n个队列中执行，然后再按轮转方式运行。第三章 处理机调度与死锁3.1 处理机调度的层次3.2 调度队列模型和调度准则3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 3.4 3.4 实时调度实时调度n实时进程或任务，用来反应或控制某个外部事件，带有某种程度的紧迫性，对调度提出了特殊要求特殊要求。3.4.1 3.4.1 实现实时调度的基本条件实现实时调度的基本条件1.1.提供必要的信息（向调度程序提供）提供必要的信息（向调度程序提供）(1)就绪时间(2)开始截止时间和完成截止时间(3)处理时间(4)资源要求(5)优先级 2.2.系统处理能力强系统处理能力强 l 实时系统中通常都有着多个实时任务l 若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果l 假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：3.4.1 3.4.1 实现实时调度的基本条件实现实时调度的基本条件3.3.采用抢占式调度机制采用抢占式调度机制 l 当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。这种调度机制比较复杂l 对于一些小的实时系统，如果能预预知知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，简简化化调度程序和对任务调度时所花费的系统开销。但在设计这种调度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界区后，能及时地将自己阻塞起来，以便释放出处理机，供调度程序去调度那种开始截止时间即将到达的任务 3.4.1 3.4.1 实现实时调度的基本条件实现实时调度的基本条件4.4.具有快速切换机制具有快速切换机制 该机制应具有如下两方面的能力：(1)对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)(2)快速的任务分派能力。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销3.4.1 3.4.1 实现实时调度的基本条件实现实时调度的基本条件3.4.2 3.4.2 实时调度算法的分类实时调度算法的分类 实时任务性质的不同硬实时调度算法软实时调度算法调度方式的不同非抢占调度算法抢占调度算法调度时间的不同静态调度算法动态调度算法多处理机环境集中式调度算法分布式调度算法1.1.非抢占式调度算法非抢占式调度算法 (1)非抢占式轮转轮转调度算法常用于工业生产群控系统，可获得数秒至数十秒的响应时间常用于工业生产群控系统，可获得数秒至数十秒的响应时间(2)非抢占式优先优先调度算法。可获得数秒至数百毫秒的响应时间可获得数秒至数百毫秒的响应时间2.2.抢占式调度算法抢占式调度算法 (1)基于时钟中断的抢占式优先权抢占式优先权调度算法。较好的响应效果，调度延迟降为几十毫秒至几毫秒较好的响应效果，调度延迟降为几十毫秒至几毫秒(2)立即抢占立即抢占(Immediate Preemption)的优先权调度算法。非常快的响应，调度延迟降为几毫秒至非常快的响应，调度延迟降为几毫秒至100100微秒微秒3.4.3 3.4.3 常用的几种实时调度算法常用的几种实时调度算法1.1.最早截止时间优先级最早截止时间优先级EDF(Earliest Deadline First)EDF(Earliest Deadline First)算法算法 u 根据任务的开始截止时间开始截止时间确定任务的优先级u 截止时间越早，优先级越高u 实时任务就绪队列按开始截止时间排序u 可用于抢占式调度，也可用于非抢占式调度1 1）非抢占式调度方式用于非周期实时任务）非抢占式调度方式用于非周期实时任务 图图 EDF EDF算法用于非抢占调度方式算法用于非抢占调度方式 2 2）抢占式调度方式用于）抢占式调度方式用于周期实时周期实时任务任务 B2B10102030405060708090100时间t/msA1A2A3A4A5A1最后期限A2最后期限A3最后期限A4最后期限B1最后期限B2最后期限A5最后期限到达时间执行时间最后期限B2 B1B2 B1A1A2A3A4B2A5固定优先级固定优先级调度（A优先级高）B1错过 B1B2B12 2）抢占式调度方式用于周期实时任务）抢占式调度方式用于周期实时任务 0102030405060708090100时间t/msA1A2A3A4A5A1最后期限A2最后期限A3最后期限A4最后期限B1最后期限B2最后期限A5最后期限到达时间执行时间最后期限A1错过A2A3A5固定优先级固定优先级调度（B优先级高）B2A4错过B2 B1 B1 B2B2B12 2）抢占式调度方式用于周期实时任务）抢占式调度方式用于周期实时任务 0102030405060708090100时间t/msA1A2A3A4A5A1最后期限A2最后期限A3最后期限A4最后期限B1最后期限B2最后期限A5最后期限到达时间执行时间最后期限A2A3最早截止时间优先A1A4A52.2.最低松弛度优先级最低松弛度优先级LLF(Least Laxity First)LLF(Least Laxity First)算法算法 根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高。松弛程度=必须完成时间-运行时间 例如，一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100 ms之前调度执行，该任务的紧急程度(松弛程度)为100 ms。一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。主要用于可抢占调度方式可抢占调度方式中。图图 A和和B任务每次必须完成的时间任务每次必须完成的时间 假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。实例分析实例分析 图图 利用利用ELLFELLF算法进行调度的情况算法进行调度的情况 小结进程调度的考量标准n 响应时间响应时间进程自进入就绪队列开始至进程占用CPU之间的时间间隔n 周转时间周转时间进程自进入就绪队列开始至进程结束之间的时间间隔n CPUCPU吞吐量吞吐量单位时间内运行结束的进程个数进程调度的原则n 公平性原则公平性原则：应保证每个进程获得合理的CPU份额n 有效性原则有效性原则：CPU资源应得到最大限度的利用n 友好性原则：响应时间快友好性原则：响应时间快与用户（人）交互的时间应尽可能的短n 快捷性原则：周转时间短快捷性原则：周转时间短批处理作业的处理时间尽可能的短n 广泛性原则：吞吐量大广泛性原则：吞吐量大单位时间内完成的作业尽可能的多时间片轮转调度n 核心思想：每个进程运行固定的时间片，然后调入下一个进程n 实现机理：维护就绪进程队列，采用FIFO方式一次读取n 特殊控制：时间片内发生阻塞或结束，则立即放弃时间片n 优缺点分析优点：绝对公平缺点：公平即合理吗？时间片如何设计才能保证效率？优先级调度n 核心思想：为每个进程赋予不同级别的优先级，越高越优先n 实现机理：维护一个优先级队列，自顶向下依次读取n 特殊控制：静态优先级与动态优先级概念n 优缺点分析优点：响应时间快，易于调整。最通用的方法缺点：死规则，如何保证周转时间和吞吐量？最短作业优先n 核心思想：保证响应时间最快、平均周转时间最短n 实现机理：依据先验信息，将进程按照运行时间增序调度n 特殊控制：如何确定最短作业？（老化算法）n 优缺点分析优点：保证了CPU的利用效率缺点：无法通用，约束条件多n 实时调度实时调度针对于专用领域和专用应用目的必须具备前提条件才能进行实时调度特点：系统规模小、中断时间短、进程切换快、OS管理深度高 nFCFS（先来先服务）：只考虑等待时间；nSJF（短作业优先算法）：只考虑执行时间；nHRRN（高响应比优先算法）nRRRR（时间片轮转算法）：机会均等，都能享有；nFBFB（多级反馈队列调度算法）nEDFEDF（最早截止时间优先算法）nLLFLLF（最低松弛度优先算法）吞吐吞吐量量系统系统开销开销响应响应时间时间反思：如何实现进程调度？n 调度机制不同调度算法适用于不同环境和不同目的调度算法一旦固定，则其最优、最坏情况均无法避免如能根据具体情况动态调整，则效果更佳n 调度策略为用户提供改变调整调度机制的渠道实现方法提供系统调用，能够改变调度机制第三章 处理机调度与死锁3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 死锁问题(deadlock)OS中重点之一1.Newton,G.:”Deadlock Prevention,Detection,and Resolution:An annotated Bibliography,”Operating Systems Review,vol.13,pp.33-44,April 1979.2.Zobel,D.:”The Deadlock Problem:A Classifying Bibliography,”Operating Systems Review,vol.17,pp6-16,Oct.1983.3.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.从一个例子开始n早期的操作系统对申请某种资源的进程，若该资源尚未分配时，立即将该资源分配给这个进程。n对资源不加限制地分配不加限制地分配可能导致进程间由于竞争资源而相互制约以至于无法继续运行的局面，人们把这种局面称为死锁(deadlock)。n死锁问题在1965年由Dijkstra 发现，并随着计算机技术的发展，逐渐成为人们关心的问题。n什么是死锁？其确切的定义是什么？死锁是怎么产生的？用什么方法来解决死锁？这些正是今天我们要讨论的问题。显然各路车队等待的事件都不会发生(假设它们都不改变行车方向)。这样若不采用特殊方法，它们将永远停留在这“井”字形的路上，而处于死锁状态。在计算机系统中，进程发生死锁与上述事例实质上是一样的。进程是因相互竞争资源而导致死锁的，与四路车队(可视为进程)竞争路口(可视为资源)类似。计算机系统中有各种资源，如外设、数据、文件、程序等。3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件死锁举例进程A：获得CD-ROM使用权，申请打印机进程B：获得打印机使用权，申请CD-ROM死锁：此时进程A、B均被阻塞，无法运行进程A进程B打印机CD-ROM n教材定义：所谓死锁,是指多个进程在运行过程中因争夺资源而造成的一种僵局（Deadly-Embrace），当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。n更规范的定义：如果一个进程集合中的每个进程都在等待只能由该组进程中的其他进程才能引发的事件，那么，该组进程是死锁的。现代操作系统，Andrew S.Tanenbaum 竞争资源：系统资源不足 进程间推进顺序非法3.5.1 产生死锁的原因1.竞争资源引起进程死锁 n永久性资源：可以被多个进程多次使用（可再用资源）n可剥夺资源：可从拥有它的进程中剥夺而不会产生任何副作用。n不可剥夺资源：从拥有它的进程中剥夺会产生错误。n临时性资源：只可使用一次的资源（可消耗性资源,如一个进程产生、被另一进程使用一短暂时间后便无用的资源）1)资源分类 图 I/O设备共享时的死锁情况 2)竞争非剥夺性资源 在系统中所配置的非剥夺性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在运行过程中，因争夺这些资源而陷入僵局图图 3-13 进程之间通信时的死锁进程之间通信时的死锁 3)竞争临时性资源临时性资源，是指由一个进程产生，被另一个进程使用一短暂时间后便无用的资源，故也称之为消耗性资源，它也可能引起死锁。推进方式1P1：Release(S1)；Request(S3)；P2：Release(S2)；Request(S1)；P3：Release(S3)；Request(S2)；推进方式2P1：Request(S3)；Release(S1)；P2：Request(S1)；Release(S2)；P3：Request(S2)；Release(S3)；造成死锁造成死锁2.进程推进顺序不当引起死锁 Q进程进程释放释放A释放释放B获得获得A获得获得BA申请申请B申请申请P 和和 Q申请申请 AP 和和 Q申请申请 BP进程进程获得获得A释放释放A获得获得B释放释放BA申请申请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)鸵鸟算法n思想：不采取任何措施，对死锁视而不见。n实例：UNIX系统、Windows（还有其它许多系统）。n由于不预防、避免死锁，故系统中可能发生死锁。而发生时又无法知道（因不检测），造成系统崩溃，需要重启。n之所以被某些系统采用，是因为死锁不常发生。第三章 处理机调度与死锁3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 l 通过破坏死锁存在的(4个)必要条件来防止死锁发生。l 我们不妨把死锁的四个必要条件记做C1，C2，C3，C4，把死锁记做D，则有逻辑公式：DC1C2C3C4，由离散数学公式推导得：C1C2C3C4D 式中的“”表示“蕴含”；“”表示“与”；“”表示“或”；“”表示“非”。l 由上式可知，只要