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

1、第三章第三章 处理机调度与死锁处理机调度与死锁n重点重点n掌握掌握进程调度进程调度算法，各适用于何种情况算法，各适用于何种情况 n理解常用的几种理解常用的几种实时调度实时调度算法算法 n理解产生理解产生死锁死锁的原因的原因 n掌握掌握银行家算法银行家算法避免死锁避免死锁n难点难点n多道程序设计中的各种调度算法多道程序设计中的各种调度算法 n响应比高者优先调度算法的计算过程响应比高者优先调度算法的计算过程 n银行家算法银行家算法 第三章第三章 处理机调度与死锁处理机调度与死锁n知识点知识点n处理机调度及调度算法处理机调度及调度算法n多处理机环境下的进程（线程）调度方式多处理机环境下的进程（线程）

2、调度方式n产生死锁的原因和必要条件产生死锁的原因和必要条件n预防死锁的方法，死锁的检测与解除预防死锁的方法，死锁的检测与解除 n银行家算法银行家算法第三章第三章 处理机调度与死锁处理机调度与死锁n处理机是计算机系统中的处理机是计算机系统中的重要资源重要资源n在多道程序环境下，进程数目通常多于在多道程序环境下，进程数目通常多于处理机的处理机的数目数目n系统必须按一定方法系统必须按一定方法动态地动态地把处理机把处理机分配给分配给就绪就绪队列中的一个进程队列中的一个进程n处理机处理机利用率利用率和和系统性能系统性能（吞吐量、响应时间）（吞吐量、响应时间）在很大程度上取决于处理机调度在很大程度上取决于

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 处理机调度的层次处理机调度的层次n高级调度高级调

4、度(High Scheduling)(High Scheduling) 作业调度作业调度或或长程调度（长程调度（Long-Term SchedulingLong-Term Scheduling）n按一定的原则对外存上处于后备状态的作业按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业进行选择，给选中的作业分配分配内存、输入内存、输入/ /输输出设备等出设备等必要的资源必要的资源，并，并建立建立相应的相应的进程进程，放入放入就绪就绪队列队列，以使该作业的进程获得竞争，以使该作业的进程获得竞争处理机的权利。处理机的权利。n也称为也称为接纳调度（接纳调度（Admission Schedul

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

6、效。高效。3.1.1 处理机调度的层次处理机调度的层次n中级调度中级调度( (Intermediate-Level SchedulingIntermediate-Level Scheduling) ) 中程调度中程调度(Medium-Term Scheduling)(Medium-Term Scheduling)n引入目的引入目的n提高提高内存利用率内存利用率和和系统吞吐量。系统吞吐量。使那些暂时不能使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待。调至外存上去等待。n交换过程交换过程n按照给定的按照给定的原则和策略原则和策略，

7、将处于外存，将处于外存对换区对换区中的中的重又具备运行条件的就绪进程重又具备运行条件的就绪进程调入内存调入内存，或将处，或将处于内存就绪状态或内存阻塞状态的进程于内存就绪状态或内存阻塞状态的进程交换到外交换到外存存对换区。对换区。3.1.1 处理机调度的层次处理机调度的层次n进程调度进程调度的运行频率最高，在分时系统中通常是的运行频率最高，在分时系统中通常是10100 ms便进行一次进程调度，因此把它称为便进行一次进程调度，因此把它称为短程调度。为避免进程调度占用太多的短程调度。为避免进程调度占用太多的CPU时间，时间，进程调度算法不宜太复杂。进程调度算法不宜太复杂。n作业调度作业调度往往是发

8、生在一个往往是发生在一个(批批)作业运行完毕，作业运行完毕，退出系统，而需要重新调入一个退出系统，而需要重新调入一个(批批)作业进入内作业进入内存时，故作业调度的周期较长，大约几分钟一次，存时，故作业调度的周期较长，大约几分钟一次，因此把它称为长程调度。由于其运行频率较低，因此把它称为长程调度。由于其运行频率较低，故允许作业调度算法花费较多的时间。故允许作业调度算法花费较多的时间。n中级调度中级调度的运行频率基本上介于上述两种调度之的运行频率基本上介于上述两种调度之间，因此把它称为中程调度。间，因此把它称为中程调度。3.1.2 处理机调度算法的目标处理机调度算法的目标n处理调度算法的共同目标处

9、理调度算法的共同目标n资源的利用率资源的利用率n公平性公平性n平衡性平衡性n策略强制执行策略强制执行3.1.2 处理机调度算法的目标处理机调度算法的目标n基本术语基本术语n到达时间到达时间n作业进入后备作业队列或新创建进程进入就绪队列作业进入后备作业队列或新创建进程进入就绪队列的时刻；的时刻；n服务时间服务时间n作业（进程）占用处理机的时间作业（进程）占用处理机的时间n开始时间开始时间n作业被创建进入就绪队列或进程首次占有处理机的作业被创建进入就绪队列或进程首次占有处理机的时刻时刻n完成时间完成时间n用户获得作业执行结果的时刻。用户获得作业执行结果的时刻。3.1.2 处理机调度算法的目标处理机

10、调度算法的目标n批处理系统的目标批处理系统的目标n平均周转时间短平均周转时间短n周转时间，周转时间，指从作业被提交给系统开始，到作业完指从作业被提交给系统开始，到作业完成为止的这段时间间隔成为止的这段时间间隔(称为作业周转时间称为作业周转时间)。它包。它包括四部分时间：括四部分时间：n作业在外存后备队列上等待作业在外存后备队列上等待(作业作业)调度的时间；调度的时间；n进程在就绪队列上等待进程调度的时间进程在就绪队列上等待进程调度的时间n进程在进程在CPU上执行的时间；上执行的时间；n进程等待进程等待I/O操作完成的时间。操作完成的时间。注意注意：此三项在一：此三项在一个作业的处理过程个作业的

11、处理过程中可能会发生多次。中可能会发生多次。周转时间周转时间=完成时间完成时间-到达时间到达时间3.1.2 处理机调度算法的目标处理机调度算法的目标n批处理系统的目标批处理系统的目标n平均周转时间短平均周转时间短n平均周转时间平均周转时间n带权周转时间：带权周转时间：进程（或作业）的进程（或作业）的周转时间周转时间T与系与系统为它统为它提供服务的时间提供服务的时间TS之比，即之比，即W=T/TS 。n平均带权周转时间平均带权周转时间niiTnT11niSiiTTnW11带权周转时间带权周转时间=周转时间周转时间/服务时间服务时间3.1.2 处理机调度算法的目标处理机调度算法的目标n批处理系统的

12、目标批处理系统的目标n系统吞吐量高系统吞吐量高n吞吐量吞吐量指单位时间内系统所完成的作业数指单位时间内系统所完成的作业数n作业调度的方式和算法对吞吐量的大小有较作业调度的方式和算法对吞吐量的大小有较大影响大影响n处理机利用率高处理机利用率高n各类资源的平衡利用各类资源的平衡利用n使内存、外存和使内存、外存和I/OI/O设备的利用率高设备的利用率高3.1.2 处理机调度算法的目标处理机调度算法的目标n分时系统的目标分时系统的目标n响应时间快响应时间快n响应时间响应时间，从用户通过键盘提交一个请求开，从用户通过键盘提交一个请求开始，直至系统中始，直至系统中首次首次产生产生响应响应为止的时间为止的时

13、间n交互式系统用周转时间衡量不是最佳交互式系统用周转时间衡量不是最佳n均衡性均衡性n系统响应时间的快慢与用户所请求服务的复系统响应时间的快慢与用户所请求服务的复杂性相适应。杂性相适应。3.1.2 处理机调度算法的目标处理机调度算法的目标n实时系统的目标实时系统的目标n截止时间保证截止时间保证n截止时间，某任务必须开始执行的最迟时间或必须截止时间，某任务必须开始执行的最迟时间或必须完成的最迟时间完成的最迟时间n截止时间是实时系统中的重要指标截止时间是实时系统中的重要指标n可预测性可预测性n数据的到达或将要处理任务的要求是可预测的。数据的到达或将要处理任务的要求是可预测的。3.1.2 处理机调度算

14、法的目标处理机调度算法的目标n问题的本质问题的本质n周转时间短周转时间短n 响应时间快响应时间快n 截止时间保证截止时间保证批处理系统批处理系统分时系统分时系统实时系统实时系统等待时间短等待时间短优先级优先级3.1.2 处理机调度算法的目标处理机调度算法的目标n目标实现目标实现n等待时间短等待时间短n等待时间等待时间，在就绪队列中等待所花的时间，在就绪队列中等待所花的时间n调度算法并不影响进程运行和执行调度算法并不影响进程运行和执行I/O的时的时间量；只影响进程在就绪队列中等待所花费间量；只影响进程在就绪队列中等待所花费的时间的时间n优先级准则优先级准则n在在批处理批处理、实时实时和和分时系统

15、分时系统中都可以选择优中都可以选择优先级准则，以便让紧急任务先处理先级准则，以便让紧急任务先处理n有时还选择抢占式调度方式有时还选择抢占式调度方式3.2 作业与作业调度作业与作业调度n3.2.1 批处理系统中的作业批处理系统中的作业n3.2.2 作业调度的主要任务作业调度的主要任务n3.2.3 先来先服务和短作业优先调度算法先来先服务和短作业优先调度算法n3.2.4 优先级调度算法和高响应比调度算法优先级调度算法和高响应比调度算法3.2.1 批处理系统中的作业批处理系统中的作业n作业和作业步作业和作业步n作业作业(Job)。用户在一次解题或一个事务处理过用户在一次解题或一个事务处理过程中要求计

16、算机系统所做工作的集合，包括用程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等。户程序、所需的数据及命令等。n作业步作业步(Job Step)。通常，在作业运行期间，每。通常，在作业运行期间，每个作业都必须经过若干个相对独立，又相互关个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。联的顺序加工步骤才能得到结果。n例，一个典型的作业可分成三个作业步：例，一个典型的作业可分成三个作业步： “编译编译”作业步；作业步； “链接装配链接装配”作业步；作业步； “运行运行”作作业步。业步。3.2.1 批处理系统中的作业批处理系统中的作业n作业控制块（作业控制块（J

17、ob control Block,JCB）n作业在系统中存在的标志；作业在系统中存在的标志；n包括作业标识、用户名称、用户账号、作业类包括作业标识、用户名称、用户账号、作业类型（型（CPU繁忙型、繁忙型、I/O繁忙型、批量型、终端繁忙型、批量型、终端型）、作业状态、调度信息（优先级、作业运型）、作业状态、调度信息（优先级、作业运行时间）、资源需求（预计运行时间、要求内行时间）、资源需求（预计运行时间、要求内存大小）、资源使用情况。存大小）、资源使用情况。3.2.1 批处理系统中的作业批处理系统中的作业n作业运行的三个阶段和三种状态作业运行的三个阶段和三种状态n一个作业进入系统到运行结束，一般需

18、要经历一个作业进入系统到运行结束，一般需要经历收容、运行、完成三个阶段，与之相对应的是收容、运行、完成三个阶段，与之相对应的是作业的三种状态作业的三种状态n后备状态后备状态n运行状态运行状态n完成状态完成状态3.2.1 批处理系统中的作业批处理系统中的作业n作业作业状态间转换状态间转换运行状态运行状态后备状态后备状态完成状态完成状态就绪就绪阻塞阻塞执行执行I/O完成完成I/O请求请求时间片完时间片完作业作业注册注册作业作业调度调度进程进程调度调度终止终止作业作业3.2.2 作业调度的主要任务作业调度的主要任务n作业调度的主要功能作业调度的主要功能n根据作业控制块中的信息，审查系统能否满足用户作

19、根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。分配必要的资源。n接纳多少个作业接纳多少个作业n 即允许多少个作业同时在内存中运行，取决于多道程即允许多少个作业同时在内存中运行，取决于多道程序度（序度（Degree of Multiprogramming）n作业太多作业太多 服务质量下降服务质量下降n作业太少作业太少 资源利用率低资源利用率低3.2.2 作业调度的主要任务作业调度的主要任务n接纳哪些

20、作业接纳哪些作业 n取决于作业调度算法取决于作业调度算法n先来先服务先来先服务n短作业优先短作业优先n作业优先级调度作业优先级调度n响应比调度响应比调度：即允许多少个作业同时在内存中运行。：即允许多少个作业同时在内存中运行。：从作业被提交给系统开始，到作业完成为：从作业被提交给系统开始，到作业完成为止的这段时间间隔。止的这段时间间隔。：是指在单位时间内系统所完成的作业数。：是指在单位时间内系统所完成的作业数。3.2.3 先来先服务和短作业优先算法先来先服务和短作业优先算法n先来先服务先来先服务(FCFS)/先进先出先进先出(FIFO)调度算法调度算法n按照作业按照作业/进程进入系统的进程进入系

21、统的先后次序先后次序进行调度，进行调度，先进入系统者先调度；即启动等待时间最长的先进入系统者先调度；即启动等待时间最长的作业作业/进程进程n最简单的调度算法，既可用于最简单的调度算法，既可用于作业调度作业调度，也可，也可用于用于进程调度进程调度3.2.3 先来先服务和短作业优先算法先来先服务和短作业优先算法进程名到达时间 服务时间 开始时间 完成时间 周转时间带权周转时间平均04A13B25C32D44E044476先来先服务（先进先出）：先来先服务（先进先出）：712101214111418141225.53.592.8A A A A B B B C C C C C D D E E E E0

22、5101518t3.2.3 先来先服务和短作业优先算法先来先服务和短作业优先算法n先来先服务（先进先出）先来先服务（先进先出）n优缺点优缺点n比较有利于比较有利于长作业（进程），长作业（进程），而不利于短而不利于短作作业（进程）业（进程）n 有利于有利于CPU繁忙型作业繁忙型作业（进程）（进程） ，而不利，而不利于于I/O繁忙型作业繁忙型作业（进程）（进程）n 用于用于批处理系统批处理系统，不适于，不适于分时系统分时系统3.2.3 先来先服务和短作业优先算法先来先服务和短作业优先算法n先来先服务（先进先出）先来先服务（先进先出）n等待时间：等待时间：J1 = 0; J2 =0; J3 = 10

23、0；J4=100n平均等待时间：平均等待时间：(0 + 0 + 100+100)/4 = 50n平均周转时间：平均周转时间：(1+100+101+200)/4=100.5n平均带权周转时间：平均带权周转时间：(1+1+101+2)/4=26.25作业作业到达到达时间时间服务服务时间时间开始时开始时间间完成完成时间时间周转周转时间时间带权周带权周转时间转时间J10 1J21100J31 1J42100011101101102102202 1 1100 1101 101200 23.2.3 先来先服务和短作业优先算法先来先服务和短作业优先算法n先来先服务（先进先出）先来先服务（先进先出）n等待时间

24、：等待时间：J1 = 0; J2 = 1; J3 = 0；J4=100n平均等待时间：平均等待时间：(0 + 1 + 0+100) / 4 = 25.25n平均周转时间：平均周转时间：(1 + 1 + 101 + 200）/4=75.75n平均带权周转时间：（平均带权周转时间：（1+1+1.01+2）/4=1.2525作业作业到达到达时间时间服务服务时间时间开始时开始时间间完成完成时间时间周转周转时间时间带权周带权周转时间转时间J101J311J21100J421000112 2102102202 1 1 1 1101 1.01200 23.2.3 先来先服务和短作业优先算法先来先服务和短作业

25、优先算法n短作业短作业( (进程进程) )优先调度算法优先调度算法SJ(P)FSJ(P)Fn按按运行时间长短运行时间长短进行调度，即先启动要求运行时进行调度，即先启动要求运行时间最短的作业（进程）间最短的作业（进程）n短作业优先短作业优先(SJF)(SJF)的调度算法：从后备队列中选择的调度算法：从后备队列中选择一个或若干个一个或若干个估计运行时间估计运行时间最短的作业，调入内最短的作业，调入内存运行；存运行；n短进程优先短进程优先(SPF)(SPF)调度算法：从就绪队列中选出一调度算法：从就绪队列中选出一估计运行时间估计运行时间最短的进程，将处理机分配给它，最短的进程，将处理机分配给它，使它

26、立即使它立即执行并一直执行到完成执行并一直执行到完成，或，或发生某事件发生某事件而被阻塞放弃处理机时，再重新调度。而被阻塞放弃处理机时，再重新调度。3.2.3 先来先服务和短作业优先算法先来先服务和短作业优先算法作业名到达时间 服务时间 开始时间 完成时间 周转时间带权周转时间平均04A13B25C32D44E0441短作业短作业/短进程优先（短进程优先（SJF/SPF）：）：4631.56982.6791392.251318163.282.1A A A AB B BC C C C CD DE E E E05101518t3.2.3 先来先服务和短作业优先算法先来先服务和短作业优先算法nSJ(

27、P)F调度算法的缺点调度算法的缺点n对对长作业不利长作业不利。严重的是，由于调度程序总是。严重的是，由于调度程序总是优先调度短作业优先调度短作业(进程进程)，将导致长作业，将导致长作业(进程进程)长长期不被调度期不被调度饥饿饥饿n不能保证不能保证紧迫性紧迫性作业作业(进程进程)会被会被及时处理；及时处理；n不一定能真正做到短作业优先调度。由于作业不一定能真正做到短作业优先调度。由于作业(进程进程)的长短只是根据的长短只是根据用户用户所提供的所提供的估计执行估计执行时间时间而定的，而用户又可能会而定的，而用户又可能会有意或无意有意或无意地地缩缩短短其作业的估计其作业的估计运行时间运行时间。n优先

28、级调度算法优先级调度算法n对于对于先来先服务先来先服务算法，作业的等待时间就是作算法，作业的等待时间就是作业的优先级，业的优先级，等待时间越长等待时间越长，优先级越高。，优先级越高。n对于对于短作业优先短作业优先算法，作业的长短就是作业的算法，作业的长短就是作业的优先级，作业所优先级，作业所需时间越短需时间越短，其优先级越高。，其优先级越高。n在优先级算法，根据作业的紧迫程度，由外部在优先级算法，根据作业的紧迫程度，由外部给予作业不同的优先级，然后根据优先级调度给予作业不同的优先级，然后根据优先级调度3.2.4 优先级和高响应比优先调度算法优先级和高响应比优先调度算法n高响应比优先调度算法（高

29、响应比优先调度算法（HRRN）nFCFS和和SJF的结合，克服了两种算法的缺点的结合，克服了两种算法的缺点n调度策略调度策略：响应比：响应比最高的作业优先启动最高的作业优先启动n因因等待时间等待时间+服务时间服务时间=该作业的该作业的响应时间响应时间，故，故该优先级又相当于该优先级又相当于响应比响应比RP。据此，又可表示。据此，又可表示为为3.2.4 优先级和高优先比优先调度算法优先级和高优先比优先调度算法优先级优先级= 等待时间等待时间+要求服务时间要求服务时间 要求服务时间要求服务时间Rp= 等待时间等待时间+要求服务时间要求服务时间 要求服务时间要求服务时间 响应时间响应时间要求服务时间

30、要求服务时间= 3.2.4 优先级和高优先比优先调度算法优先级和高优先比优先调度算法n对对HRRN的小结的小结n等待时间相同等待时间相同的作业，则的作业，则要求服务的时间愈短要求服务的时间愈短，其其优先级愈高优先级愈高，n要求服务的时间相同要求服务的时间相同的作业，则的作业，则等待时间愈长等待时间愈长，其其优先级愈高优先级愈高，n长作业，优先级长作业，优先级随等待时间的增加随等待时间的增加而提高，其而提高，其等待时间足够长时，其优先级便可升到很高，等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机，从而也可获得处理机，n是一种折衷，既照顾了短作业，又考虑了作业是一种折衷，既照顾了短作

31、业，又考虑了作业到达的先后次序，又不会使长作业长期得不到到达的先后次序，又不会使长作业长期得不到服务。服务。缺点：要进行响应比计算，增加了系统开销缺点：要进行响应比计算，增加了系统开销对短作业有利对短作业有利先来先服务先来先服务对长作业有利对长作业有利优先级优先级= 等待时间等待时间+要求服务时间要求服务时间 要求服务时间要求服务时间 响应时间响应时间要求服务时间要求服务时间= 优先级优先级= 等待时间等待时间+服务时间服务时间 服务时间服务时间当前时间当前时间-到达时间到达时间+服务时间服务时间 服务时间服务时间= 作业作业名名到达到达时间时间服务服务时间时间响应比响应比开始开始时间时间完成

32、完成时间时间周转周转时间时间带权周带权周转时间转时间平均04A13B25C32D44E04411418143.54762914122.479638.42.38高响应比优先，非高响应比优先，非抢占式抢占式21.41.51231.752.42.253.53.2.4 优先级和高优先比优先调度算法优先级和高优先比优先调度算法作业作业到达到达时间时间要求服务要求服务时间时间开始执行开始执行时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间J18.0 2.0J28.6 0.6J38.8 0.2J49.0 0.5平均平均8.08.69.09.69.210.111.39.63.3 1.651.0

33、 1.670.4 2.01.1 2.2/9.2/8.81.45 1.88/10.1高响应比优先，高响应比优先，抢占式抢占式3.2.4 优先级和高优先比优先调度算法优先级和高优先比优先调度算法3.3 进程调度进程调度n3.3.1 进程调度的任务、机制和方式进程调度的任务、机制和方式n3.3.2 轮转调度算法轮转调度算法n3.3.3 优先级调度算法优先级调度算法n3.3.4 多队列调度算法多队列调度算法n3.3.5 多级反馈队列调度算法多级反馈队列调度算法n3.3.6 基于公平原则的调度算法基于公平原则的调度算法3.3.1 进程调度的任务、机制和方式进程调度的任务、机制和方式n进程调度的任务进程调

34、度的任务n保存处理机的现场信息保存处理机的现场信息。将正在运行进程的上。将正在运行进程的上下文保存到下文保存到PCB及相应的数据结构中。及相应的数据结构中。n按某种算法选取进程按某种算法选取进程。控制、协调进程对。控制、协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选的竞争，即按一定的调度算法从就绪队列中选中一个进程。中一个进程。n把处理器分配给进程把处理器分配给进程。把。把CPU的使用权交给被的使用权交给被选中的进程，并装入选中进程的上下文。选中的进程，并装入选中进程的上下文。3.3.1 进程调度的任务、机制和方式进程调度的任务、机制和方式n进程调度机制进程调度机制 根据预定的算法，

35、根据预定的算法，将系统中所有的就绪进将系统中所有的就绪进程排成一个或多个队列，程排成一个或多个队列，以便调度程序能最快地以便调度程序能最快地找到它。找到它。分派程序把由进程调度程分派程序把由进程调度程序所选定的进程，从就绪序所选定的进程，从就绪队列中取出该进程，然后队列中取出该进程，然后进行上下文切换，将处理进行上下文切换，将处理机分配给它机分配给它 。 OS保存当前进程的保存当前进程的上下文，装入分派程序的上下文，装入分派程序的上下文；上下文； 将移出分派程序，将移出分派程序，把新选进程的把新选进程的CPU现场信现场信息装入到处理机的各个相息装入到处理机的各个相应寄存器中。应寄存器中。 3.

36、3.1 进程调度的任务、机制和方式进程调度的任务、机制和方式n进程调度方式进程调度方式n非抢占方式非抢占方式(Non-preemptive Mode)n抢占方式抢占方式(Preemptive Mode)3.3.1 进程调度的任务、机制和方式进程调度的任务、机制和方式n进程调度方式进程调度方式非抢占方式非抢占方式n进程正在处理机上执行时，进程正在处理机上执行时，新就绪新就绪的进程进入的进程进入就绪队列，就绪队列，该进程仍继续该进程仍继续执行，直到其完成或执行，直到其完成或发生某种事件而进入完成或阻塞状态时，才转发生某种事件而进入完成或阻塞状态时，才转让处理机。让处理机。n引起进程调度的因素引起进

37、程调度的因素n正在执行的进程执行完毕，正在执行的进程执行完毕， 或因发生某事或因发生某事件而不能再继续执行件而不能再继续执行n执行中的进程因提出执行中的进程因提出I/OI/O请求而暂停执行；请求而暂停执行；n在进程通信或同步过程中执行了某种原语操在进程通信或同步过程中执行了某种原语操作，如作，如waitwait、BlockBlock、WakeupWakeup原语原语优点优点：算法简单，：算法简单，系统开销小系统开销小缺点缺点：紧急任务不：紧急任务不能及时响应；短进能及时响应；短进程到达要等待长进程到达要等待长进程运行结束程运行结束n进程调度方式进程调度方式抢占方式抢占方式n进程正在处理机上执行

38、时，若有某个更为重要进程正在处理机上执行时，若有某个更为重要或紧迫的进程进入就绪队列，则或紧迫的进程进入就绪队列，则立即暂停立即暂停正在正在执行的进程，将处理机分配给这个更为重要或执行的进程，将处理机分配给这个更为重要或紧迫的进程紧迫的进程n抢占式调度原则抢占式调度原则n优先级原则优先级原则 允许高优先级的新到进程抢占允许高优先级的新到进程抢占当前进程的处理机当前进程的处理机n短作业短作业( (进程进程) )优先原则优先原则允许执行时间短的新允许执行时间短的新到进程抢占当前进程的处理机到进程抢占当前进程的处理机n时间片原则时间片原则 时间片用完后停止执行，重新时间片用完后停止执行，重新进行调度

39、，适用于分时系统进行调度，适用于分时系统优点优点：适于时间要：适于时间要求严格的实时系统求严格的实时系统缺点缺点：调度算法复：调度算法复杂，系统开销大杂，系统开销大3.3.1 进程调度的任务、机制和方式进程调度的任务、机制和方式3.3.2 轮转调度算法轮转调度算法n轮转法的基本原理轮转法的基本原理n系统将所有的就绪进程按先来先服务的原则排系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把成一个队列，每次调度时，把CPU分配给队首分配给队首进程，并令其执行一个时间片进程，并令其执行一个时间片n当执行的时间片用完时，由一个计时器发出当执行的时间片用完时，由一个计时器发出时时钟中断钟

40、中断请求，调度程序便停止该进程的执行，请求，调度程序便停止该进程的执行，并将其放就绪队列尾；然后，再把处理机分配并将其放就绪队列尾；然后，再把处理机分配给就绪队列中新的队首给就绪队列中新的队首n时间片的大小从几时间片的大小从几ms到几百到几百ms缺点：紧迫任务响应慢。缺点：紧迫任务响应慢。UNIX中采用：时间片中采用：时间片+优先级优先级3.3.2 轮转调度算法轮转调度算法n进程切换时间进程切换时间n任务在给定时间片内任务在给定时间片内已完成已完成，则将它标记为终，则将它标记为终止状态，立即激活调度程序进行调度；止状态，立即激活调度程序进行调度；n任务在时间片内任务在时间片内未完成未完成，计时

41、器中断处理程序，计时器中断处理程序被激活，则将进程进入就绪队列末尾，启动调被激活，则将进程进入就绪队列末尾，启动调度程序调度；度程序调度；3.3.2 轮转调度算法轮转调度算法n时间片大小的确定时间片大小的确定n时间片选择问题时间片选择问题n固定时间片固定时间片n可变时间片可变时间片n与时间片大小有关的因素与时间片大小有关的因素n系统响应时间系统响应时间n就绪进程个数就绪进程个数nCPUCPU能力能力 基于时间片的轮转调度算法基于时间片的轮转调度算法进程名进程名到达时间到达时间 服务时间服务时间 开始时间开始时间 完成时间完成时间 周转时间周转时间带权周带权周转时间转时间平均平均A B C D

42、E A B C D E A B C E A C E C05101518t04A03B05C02D04E01234912151718153.75124183.694.5174.2514.24.02若到达时间若到达时间为为0 0、1 1、2 2、3 3、4 4，又如，又如何？何？基于时间片的轮转调度算法基于时间片的轮转调度算法进程名进程名到达时间到达时间 服务时间服务时间 开始时间开始时间 完成时间完成时间 周转时间周转时间带权周带权周转时间转时间平均平均A B A C B D A E C B D A E C E C E C05101518t04A13B25C32D44E0135711101217

43、1812393163.284133.2511.63.293.3.3 优先级调度算法优先级调度算法n优先级调度算法的类型优先级调度算法的类型n非抢占式非抢占式n特点：系统一旦把处理机分配给就绪队特点：系统一旦把处理机分配给就绪队列中列中优先级最高优先级最高的进程后，该进程便的进程后，该进程便一一直执行直执行下去，直至完成，或因发生某事下去，直至完成，或因发生某事件使该进程放弃处理机时，系统才将处件使该进程放弃处理机时，系统才将处理机重新分配给另一优先级最高的进程理机重新分配给另一优先级最高的进程n主要主要用于批处理系统用于批处理系统中，也可用于某些中，也可用于某些对实时性对实时性要求不严的实时系

44、统要求不严的实时系统中中3.3.3 优先级调度算法优先级调度算法n优先级调度算法的类型优先级调度算法的类型n抢占式抢占式n把处理机分配给优先级最高的进程，在执行期把处理机分配给优先级最高的进程，在执行期间，只要出现另一个优先级更高的进程，则进间，只要出现另一个优先级更高的进程，则进程调度程序就程调度程序就立即停止立即停止当前进程的执行，并将当前进程的执行，并将处理机分配给新到的优先级最高的进程处理机分配给新到的优先级最高的进程n只要只要系统中系统中出现出现一个新的就绪进程，一个新的就绪进程，就进行就进行优优先级先级比较比较n能更好地能更好地满足紧迫作业满足紧迫作业的要求，故而常用于要的要求，故

45、而常用于要求比较严格的实时系统中，以及对性能要求较求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中高的批处理和分时系统中3.3.3 优先级调度算法优先级调度算法n优先级的类型优先级的类型n静态优先级静态优先级n静态优先级在创建进程时确定，且在进程的整静态优先级在创建进程时确定，且在进程的整个运行期间个运行期间保持不变保持不变。一般地，优先级是利用。一般地，优先级是利用某一范围内的一个整数来表示的，例如，某一范围内的一个整数来表示的，例如，0 0 7 7或或0 0 255255， 又把该整数称为又把该整数称为优先数优先数n确定进程静态优先级的依据确定进程静态优先级的依据n进程类型进

46、程类型: :系统进程，用户进程系统进程，用户进程n进程对资源的需求进程对资源的需求n用户要求用户要求问题：用户将优先级设的较高，对其他进程不利！问题：用户将优先级设的较高，对其他进程不利！ 短进程优先对长进程不利！短进程优先对长进程不利！3.3.3 优先级调度算法优先级调度算法n动态优先级动态优先级n随随进程的推进进程的推进或随其或随其等待时间等待时间的增加而改变。的增加而改变。n例，在例，在就绪队列中的进程就绪队列中的进程，优先级随，优先级随等待时间的等待时间的增长增长，以某一速率提高；以某一速率提高；n相同优先级初值相同优先级初值的进程，则的进程，则最先进入最先进入就绪队列就绪队列的进程，

47、的进程，优先优先获得处理机，即获得处理机，即FCFS算法算法n各不相同各不相同的的优先级初值优先级初值的就绪进程，则的就绪进程，则优先级优先级初值低初值低的进程，在的进程，在等待了足够的时间等待了足够的时间后，其后，其优优先级便可能升为最高先级便可能升为最高，从而可以获得处理机，从而可以获得处理机n当采用抢占式优先级调度算法时，如果再当采用抢占式优先级调度算法时，如果再规定当规定当前进程前进程的优先级的优先级以某一速率下降以某一速率下降，则可防止一个，则可防止一个长作业长期地长作业长期地垄断垄断处理机。处理机。进程进程到达到达时间时间服务服务时间时间开始开始时间时间完成完成时间时间周转周转时间

48、时间带权周带权周转时间转时间P10 7P21 5P32 3P43 2P54 4平均等待时间：平均等待时间：(14 + 5 + 0+2+7) / 5 = 5.6平均周转时间：平均周转时间：(21 + 10 + 3 + 4 + 11）/5=9.8平均带权周转时间：平均带权周转时间：(3+2+1+2+2.75）/5=2.15012557/7111115/152121 310 2 3 1 4 211 2.753.3.3 优先级调度算法优先级调度算法实例实例n抢占式抢占式短进程优先短进程优先SPF调度调度3.3.3 优先级调度算法优先级调度算法实例实例进程进程名名到达到达时间时间服务服务时间时间静态优静

49、态优先级先级开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间平均平均静态优先级，静态优先级，非抢占式非抢占式（1为最高优先级）为最高优先级）04A413B225C332D544E104414841811103.331116142.81618157.59.42.93考虑一下考虑一下抢占式抢占式，情况如何？，情况如何？进程进程名名到达到达时间时间服务服务时间时间静态优静态优先级先级开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间平均平均高优先级优先调度算法04A413B225C332D544E101616448411431813112.2161815

50、7.59.83.14静态优先级，静态优先级，抢占式抢占式（1为高优先级）为高优先级）A B B B E E E E C C C C C A A A D D05101518tB AA CDEA CD3.3.4 多队列调度多队列调度算法算法n单一就绪队列单一就绪队列多个就绪队列多个就绪队列n例，将就绪进程分别进入前台和后台就绪队列例，将就绪进程分别进入前台和后台就绪队列n前台前台就绪队列是交互性作业的进程，通常采用时间就绪队列是交互性作业的进程，通常采用时间片轮转。片轮转。n后台后台的就绪队列是批处理作业的进程，通常采用优的就绪队列是批处理作业的进程，通常采用优先级或短作业优先算法。先级或短作业优

51、先算法。n调度方式有两种：调度方式有两种：n优先调度前台，若前台无可运行进程，才调度后台。优先调度前台，若前台无可运行进程，才调度后台。n分配占用分配占用CPU的时间比例，如：前台的时间比例，如：前台80%，后台，后台20%3.3.5 多级反馈多级反馈(multileved feedback)队列调度算法队列调度算法n调度机制调度机制 n设置设置多个就绪队列多个就绪队列，各个队列赋予，各个队列赋予不同的优先级不同的优先级n第一个队列的优先级最高，第二个队列次之，第一个队列的优先级最高，第二个队列次之，其余各队列的优先级逐个降低其余各队列的优先级逐个降低n各个队列中进程执行各个队列中进程执行时间

52、片的大小也各不相同时间片的大小也各不相同，在在优先级愈高优先级愈高的队列中，为每个进程所规定的的队列中，为每个进程所规定的执行执行时间片就愈小时间片就愈小。例，。例，第二个第二个队列的时间片队列的时间片要要比第一个比第一个队列的时间片队列的时间片长一倍长一倍，第，第i i+1+1个个队列的时间片要比第队列的时间片要比第i i个队列的时间片长一倍个队列的时间片长一倍就绪队列就绪队列1 13.3.5 多级反馈队列调度算法多级反馈队列调度算法就绪队列就绪队列2 2就绪队列就绪队列3 3就绪队列就绪队列nS1S2S3至至CPU至至CPU至至CPU至至CPU( (时间片：时间片：S1 S2 S3) )v

53、调度方式调度方式高高低低优先级优先级时间片时间片小小大大Sn按按FIFO原则原则排队等待调排队等待调度度尚未完成转入第二尚未完成转入第二队列的末尾，按队列的末尾，按FIFO原则等待调原则等待调度度采取按时间片轮采取按时间片轮转的方式运行转的方式运行因等待而放弃因等待而放弃CPU后，后，进入阻塞队列，一旦进入阻塞队列，一旦等待的事件发生，则等待的事件发生，则回到原来的就绪队列回到原来的就绪队列3.3.5 多级反馈队列调度算法多级反馈队列调度算法n多级反馈队列调度算法多级反馈队列调度算法n注意注意n仅当第仅当第1(i-1) 队列均空时，才会调度第队列均空时，才会调度第i队列中的进队列中的进程运行程

54、运行n第第i队列队列中某进程正在运行时，又有中某进程正在运行时，又有新新进程进入进程进入优先优先级较高级较高的队列的队列(第第1(i-1)中的任何一个队列中的任何一个队列)，则此时，则此时新进程将抢占新进程将抢占正在运行进程的处理机，调度程序把正在运行进程的处理机，调度程序把正在运行的进程正在运行的进程放回到第放回到第i队列队列的末尾的末尾n第第i队列队列中某进程正在运行时，该进程因等待事件发中某进程正在运行时，该进程因等待事件发生而进入阻塞队列，等待事件发生后，调度程序把生而进入阻塞队列，等待事件发生后，调度程序把进程进程放回到第放回到第i队列队列的末尾的末尾3.3.5 多级反馈队列调度算法

55、多级反馈队列调度算法n调度算法的性能调度算法的性能n终端型作业用户终端型作业用户n提交的作业多属于提交的作业多属于交互型交互型作业，通常作业，通常较小较小，系统只要能，系统只要能使这些作业在第一队列所使这些作业在第一队列所规定的时间片内完成规定的时间片内完成即可即可n短批处理作业用户短批处理作业用户n若在第若在第1队列中执行队列中执行一个时间片一个时间片即可完成，便可获得与终即可完成，便可获得与终端型作业一样的响应时间端型作业一样的响应时间n如在第一个队列中不能完成，只需在第如在第一个队列中不能完成，只需在第2、3队列中各执队列中各执行一个时间片行一个时间片n长批处理作业用户长批处理作业用户n

56、长作业将依次在第长作业将依次在第1，2，3，n队列中执行，队列中执行，最终按轮最终按轮转方式运行转方式运行3.3.6 基于公平原则的调度算法基于公平原则的调度算法n保证调度算法保证调度算法n向用户做出明确的性能保证向用户做出明确的性能保证n易实现的算法：处理机分配的公平性易实现的算法：处理机分配的公平性n当工作时已有当工作时已有n个用户登录在系统，则将获得个用户登录在系统，则将获得CPU处理能力的处理能力的1/n。类似的，在一个有。类似的，在一个有n个进程运行的个进程运行的用户系统中，每个进程将获得用户系统中，每个进程将获得CPU处理能力的处理能力的1/n。n实现方法实现方法nOS应记录及计算

57、应记录及计算,各个进程在一定时间段内各个进程在一定时间段内,已经使已经使用的用的CPU时间和应该得到的时间和应该得到的CPU时间时间,二者之比小者二者之比小者优先级高优先级高3.3.6 基于公平原则的调度算法基于公平原则的调度算法n公平分享调度算法公平分享调度算法n每个用户分配到每个用户分配到CPUCPU时间的一部分，而调度程时间的一部分，而调度程序以一种强制的方式选择进程。这样，如果两序以一种强制的方式选择进程。这样，如果两个用户都得到获得个用户都得到获得50% CPU50% CPU时间的保证，那么时间的保证，那么无论一个用户有多少进程存在，每个用户都会无论一个用户有多少进程存在，每个用户都

58、会得到应有的得到应有的CPUCPU份额。份额。n例，用户例，用户1 1有有4 4个进程个进程A A、B B、C C和和D D，而用户，而用户2 2只只有有1 1个进程个进程E E。如果采用轮转调度，一个满足所。如果采用轮转调度，一个满足所有限制条件的可能序列是：有限制条件的可能序列是： A E B E C E D A E B E C E D E A E B E C E D E E A E B E C E D E 3.3.6 线程调度线程调度nOS只调度核心级线程；只调度核心级线程；n用户级线程必须映射到内核线程才能运行；用户级线程必须映射到内核线程才能运行；n本地调度（进程竞争范围，本地调度（

59、进程竞争范围，PCS）n线程库决定如何将哪个线程调度到有效的线程库决定如何将哪个线程调度到有效的LWP上。上。nM:M，M:On全局调度（系统竞争范围，全局调度（系统竞争范围，SCS）n内核决定调度那一个线程到内核决定调度那一个线程到CPU上运行。上运行。nO:O仅采用仅采用SCSnPCS根据优先级完成，由程序员设置。根据优先级完成，由程序员设置。线程调度线程调度API#include #include #define NUM_THREADS 5int main(int argc, char *argv ) int i, scope;pthread_t tidNUM_THREADS;pthre

60、ad_attr_t attr;/* get the default attributes */pthread_attr_init(&attr);/* set the scheduling algorithm to PROCESS or SYSTEM */pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);/* set the scheduling policy - FIFO, RT, or OTHER */pthread_attr_setschedpolicy(&attr, SCHED_OTHER);线程调度线程调度API/* create the thr