单处理器调度

1、单处理器调度Chapter 9主要内容主要内容 处理机管理的工作是对处理机管理的工作是对CPU资源进行合理的分配使用，资源进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源。以提高处理机利用率，并使各用户公平地得到处理机资源。这里的主要问题是处理机调度算法和调度算法特征分析。这里的主要问题是处理机调度算法和调度算法特征分析。n处理器调度类型及概念处理器调度类型及概念n长程、中程、短程长程、中程、短程n调度算法调度算法n调度准则调度准则n调度策略调度策略n公平共享调度公平共享调度n教学重点与难点教学重点与难点n进程调度算法进程调度算法处理机调度处理机调度 对资源进行有效的调度

2、是非常必要的，我对资源进行有效的调度是非常必要的，我们生活中也会经常遇到，如：调度银行出纳们生活中也会经常遇到，如：调度银行出纳员服务顾客请求问题等。员服务顾客请求问题等。 CPUCPU是计算机系统中的一个十分重要的资是计算机系统中的一个十分重要的资源，对它进行高效的调度是操作系统设计的源，对它进行高效的调度是操作系统设计的中心问题之一。中心问题之一。 处理器调度处理器调度n选择内存中的就绪进程，并分配处理器给选择内存中的就绪进程，并分配处理器给其中之一其中之一n处理器调度可能发生在当一个进程：处理器调度可能发生在当一个进程：1)从运行转到等待从运行转到等待2)从运行转到就绪从运行转到就绪3)

3、从等待转到就绪从等待转到就绪4)就绪转到运行就绪转到运行5)终止运行终止运行调度程序n调度程序负责将对调度程序负责将对CPUCPU的控制权转交给由的控制权转交给由CPUCPU调度调度程序，包括程序，包括: :nswitching contextswitching context（切换上下文）（切换上下文）nswitching to user modeswitching to user mode（切换到用户态）（切换到用户态）njumping to the proper location in the jumping to the proper location in the user prog

4、ram to restart that programuser program to restart that program（跳（跳转到用户程序的适当位置并重新运行之）转到用户程序的适当位置并重新运行之）n调度时间调度时间 调度程序终止一个进程的运行并启调度程序终止一个进程的运行并启动另一个进程运行所花的时间动另一个进程运行所花的时间. .处理器调度的目标处理器调度的目标n以满足系统目标的方式，把进程指定一个以满足系统目标的方式，把进程指定一个处理器或多个处理器执行处理器或多个处理器执行n响应时间响应时间 从进程提出请求到首次被响应从进程提出请求到首次被响应而不是输出结果而不是输出结果的的时

5、间段时间段在分时系统环境下在分时系统环境下n吞吐率吞吐率 单位时间内运行完的进程数单位时间内运行完的进程数n处理器效率处理器效率 CPU利用率利用率 使使CPU尽可能的忙碌尽可能的忙碌处理器调度的类型处理器调度的类型n主要按照调度的时间周期划分主要按照调度的时间周期划分n长程调度长程调度 决定后备队列中的决定后备队列中的哪哪些些作业可以成为作业可以成为进程，进程，并加入并加入待执行的进程池中待执行的进程池中n中程调度中程调度 决定将决定将哪些哪些进程进程换入换入内存，将内存，将哪些哪些进程进程换出换出内内存存n短程调度短程调度 决定就绪队列中决定就绪队列中哪一个哪一个进程应先获得处理器进程应先

6、获得处理器选秀女？选秀女？冷宫管理？冷宫管理？翻牌子？翻牌子？从频率上看，从频率上看，谁更频繁谁更频繁?进程一定要经过中程调进程一定要经过中程调度才能进入短程调度么度才能进入短程调度么?调度和进程状态转换调度和进程状态转换表示了调度功能的嵌套关系调度是属于管理队列方面的问题，用来在排队环境中减少延迟和优化性能。一个进程状态转换过程中所涉及的队列长程调度长程调度(高级调度、作业调度）高级调度、作业调度）n长程调度决定哪一个程序何时可以进入到系统中长程调度决定哪一个程序何时可以进入到系统中处理处理n决策决策1何时创建一个新进程何时创建一个新进程n由要求的系统并发度驱动。创建的进程越多，每个进由要求

7、的系统并发度驱动。创建的进程越多，每个进程可以执行的时间百分比就越小程可以执行的时间百分比就越小n决策决策2加入哪一个新进程加入哪一个新进程n基于简单的先来先服务原则、基于管理的系统性能的基于简单的先来先服务原则、基于管理的系统性能的工具等（优先级、期待执行时间和工具等（优先级、期待执行时间和I/O需求）需求）n执行的频率最低执行的频率最低中程调度中程调度n为提高系统吞吐量和内存利用率而引入的内为提高系统吞吐量和内存利用率而引入的内外外存对换功能（换出时，进程为挂起状态），主要存对换功能（换出时，进程为挂起状态），主要涉及内存管理与扩充涉及内存管理与扩充n将进程的部分或全部加载到内存中将进程的

8、部分或全部加载到内存中n换入决策基于管理多道程序并发程度的要求换入决策基于管理多道程序并发程度的要求n执行的频率比长程调度要频繁些执行的频率比长程调度要频繁些短程调度（低级调度、进程调度）短程调度（低级调度、进程调度）n执行得最频繁，要求在实现时达到高效率执行得最频繁，要求在实现时达到高效率n短程调度程序也称作分派程序短程调度程序也称作分派程序dispatchn主要任务：按照某种策略和方法选取一个处于就主要任务：按照某种策略和方法选取一个处于就绪状态的进程占用处理机绪状态的进程占用处理机n保存处理机现场信息保存处理机现场信息n按某种算法选取进程按某种算法选取进程n把处理机分配给进程把处理机分配

9、给进程n短程调度的三个基本机制短程调度的三个基本机制n排队器、分派器、上下文切换机制排队器、分派器、上下文切换机制CPU Switch From Process to Process短程调度短程调度n当可能导致当前进程挂起或可能抢占当前正在运行的当可能导致当前进程挂起或可能抢占当前正在运行的进程的事件发生时，调用短程调度程序。进程的事件发生时，调用短程调度程序。n引起进程调度的事件有哪些？引起进程调度的事件有哪些？n时钟中断（例如时间片用完）时钟中断（例如时间片用完）nI/O中断中断n操作系统调用操作系统调用n信号（例如在信号量上的信号（例如在信号量上的wait操作，使进程阻塞）操作，使进程阻

10、塞）n抢占方式下，就绪队列中出现某更高优先权的进程抢占方式下，就绪队列中出现某更高优先权的进程按照按照OS的分类的分类n批处理调度应用场合：大中型主机集批处理调度应用场合：大中型主机集中计算，如工程计算、理论计算（流体力中计算，如工程计算、理论计算（流体力学）学）n分时调度、实时调度分时调度、实时调度n多处理机调度多处理机调度9.2调度算法调度算法n调度准则调度准则n调度策略调度策略n性能分析性能分析我们只考虑我们只考虑短程调度短程调度算法算法1.短程调度准则短程调度准则n面向用户准则面向用户准则与单个用户或进程感知到的系统的行为有关，如响应时与单个用户或进程感知到的系统的行为有关，如响应时间

11、，间，周转时间，公平性，优先级等周转时间，公平性，优先级等n周转时间周转时间 指一个进程从提交到完成之间的时间间隔指一个进程从提交到完成之间的时间间隔n响应时间响应时间 指从提交一条请求到响应出现在输出中所经历的时间指从提交一条请求到响应出现在输出中所经历的时间n面向系统准则面向系统准则重点是有效和高效地利用处理器，如吞吐量重点是有效和高效地利用处理器，如吞吐量n吞吐量：单位时间内所完成的进程数吞吐量：单位时间内所完成的进程数短程调度准则短程调度准则根据是否与性能直接相关划分：根据是否与性能直接相关划分：n与性能直接相关的准则与性能直接相关的准则n是定量的是定量的n通常是很容易度量的，如响应时

12、间和吞吐量通常是很容易度量的，如响应时间和吞吐量n与性能无关的准则与性能无关的准则n是定性的、或有助于测量和分析是定性的、或有助于测量和分析n可预测性，公平性，优先级等可预测性，公平性，优先级等2.优先级优先级的使用的使用n在许多系统中，每个进程都被指定一个优在许多系统中，每个进程都被指定一个优先级，调度程序总是选择具有较高优先级先级，调度程序总是选择具有较高优先级的进程的进程n提供一组就绪队列，按优先级递减的顺序提供一组就绪队列，按优先级递减的顺序排列排列n低优先级的进程可能会处于饥饿状态低优先级的进程可能会处于饥饿状态n允许一个进程的优先级可以随着它的时间或执允许一个进程的优先级可以随着它

13、的时间或执行历史而改变行历史而改变3.选择调度策略选择调度策略n选择函数选择函数确定在就绪进程中选择哪一个在确定在就绪进程中选择哪一个在下一次执行下一次执行n基于优先级、资源需求量、该进程的执行特性基于优先级、资源需求量、该进程的执行特性n决策模式决策模式说明运用选择函数的瞬间，通常说明运用选择函数的瞬间，通常分为两类：非抢占、抢占分为两类：非抢占、抢占决策模式决策模式n非抢占非抢占n一旦进程处于运行状态，它就不断执行直到终止一旦进程处于运行状态，它就不断执行直到终止n抢占抢占n当前正在运行的进程被操作系统中断，并转移到当前正在运行的进程被操作系统中断，并转移到就绪状态就绪状态n可能对所有进程

14、提供较好的服务，因为它们避免可能对所有进程提供较好的服务，因为它们避免任何一个进程独占处理器太长的时间任何一个进程独占处理器太长的时间江山坐到底江山坐到底江山轮流坐江山轮流坐preempt英prempt美primptvt.先占;取代;先取;先发制人更正书上几个翻译和印刷错误更正书上几个翻译和印刷错误n1. P286：图：图 9.5 中，中，“最短剩余事件最短剩余事件”应应为为“最短进程优先最短进程优先”；“最短进程优先最短进程优先”应为应为“最短剩余时间最短剩余时间”。n2. P287：表：表 9.5 中，除第一个中，除第一个“服务时间服务时间(T s )”之外，其余的之外，其余的“服务时间服

15、务时间(T s ) ”全全部改为部改为“周转时间周转时间(T r ) ” n3. P285： “ w:到现在为此，在系统中到现在为此，在系统中停停留留的时间的时间”应为应为“在系统中在系统中等待等待的时间的时间”这个公式来自排队论，请无视这个公式来自排队论，请无视n出现在出现在p286第三段第三段驻留时间驻留时间=等待时间等待时间+服务时间服务时间这个公式来自排队论，请无视这个公式来自排队论，请无视短程调度中的几个短程调度中的几个“时间时间”概念概念nw：等待等待时间，时间，得不到得不到CPU的时间的时间ne：执行执行时间，时间，得到得到CPU的时间的时间ns或或Ts：预计进程：预计进程需要得

16、到需要得到的的CPU服务服务时间时间nTr ：周转时间：周转时间指一个进程从提交到完成之间的时间间隔指一个进程从提交到完成之间的时间间隔周转时间周转时间=完成时间完成时间 到达时间到达时间周转时间周转时间=w+e 当进程结束时当进程结束时nTr/Ts：归一化周转时间：归一化周转时间 27来算一下来算一下进进 程程到达时间到达时间 服务时间服务时间A A0 03 3B B2 26 6C C4 44 4D D6 65 5E E8 82 2ABCDE进程进程C的的 W E S Tr Tr/Ts 分别是多少？分别是多少？0 3 9 13 18 20调度调度结果结果决策模式决策模式n非抢占非抢占n一旦进

17、程处于运行状态，它就不断执行直到终止一旦进程处于运行状态，它就不断执行直到终止n抢占抢占n当前正在运行的进程被操作系统中断，并转移到当前正在运行的进程被操作系统中断，并转移到就绪状态就绪状态n可能对所有进程提供较好的服务，因为它们避免可能对所有进程提供较好的服务，因为它们避免任何一个进程独占处理器太长的时间任何一个进程独占处理器太长的时间江山坐到底江山坐到底江山轮流坐江山轮流坐preempt英prempt美primptvt.先占;取代;先取;先发制人29再算一个抢占模式的再算一个抢占模式的进进 程程到达时间到达时间 服务时间服务时间A A0 03 3B B2 26 6C C4 44 4D D6

18、 65 5E E8 82 2ABABCBDCBEDCBEDCBD0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20进程进程C的的 W E S Tr Tr/Ts 分别是多少？分别是多少？调度调度结果结果进程调度示例进程调度示例进进 程程到达时间到达时间 服务时间服务时间A A0 03 3B B2 26 6C C4 44 4D D6 65 5E E8 82 251015200ABCDE先来先服务先来先服务(FCFS)n选择函数选择函数MAX(w),非抢占非抢占n选择就绪队列中选择就绪队列中等待时间最长等待时间最长的进程运行的进程运行ABCDE510152

19、00ABCDE先来先服务先来先服务(FCFS)FCFS的缺点：的缺点：n一个短进程在它能够执行之前，可能必须等待很一个短进程在它能够执行之前，可能必须等待很长时间长时间n有利于处理器密集型的进程，而不利于有利于处理器密集型的进程，而不利于I/O密集密集型的进程型的进程n处理器密集型进程：一个进程大多数时候使用处理器处理器密集型进程：一个进程大多数时候使用处理器n可能导致处理器和可能导致处理器和I/O设备都没有得到充分利用设备都没有得到充分利用时间片轮转时间片轮转ABCDE51015200ABCDE时间片时间片=1=1n运行后，运行后，等待等待时间清零时间清零n等待等待时间相等时，新进程优先时间

20、相等时，新进程优先CDEBn选择函数选择函数MAX(wi),时间片用完时时间片用完时抢占抢占n选择就绪队列中选择就绪队列中等待时间最长等待时间最长的进程运行的进程运行时间片轮转时间片轮转ABCDE51015200ABCDE时间片时间片=4=4n运行后，运行后，等待等待时间清零时间清零n等待等待时间相等时，新进程优先时间相等时，新进程优先n选择函数选择函数MAX(wi),时间片用完时时间片用完时抢占抢占n选择就绪队列中选择就绪队列中等待时间最长等待时间最长的进程运行的进程运行时间片轮转时间片轮转n使用基于时钟的抢占策略，可以减少使用基于时钟的抢占策略，可以减少FCFS策略策略下短作业的不利情况下

21、短作业的不利情况n每个进程在被抢占前都给定一个每个进程在被抢占前都给定一个时间片时间片运行，当运行，当中断发生时，当前运行进程转移至就绪队列，然中断发生时，当前运行进程转移至就绪队列，然后以后以FCFS策略选择下一个就绪进程运行。策略选择下一个就绪进程运行。时间片大小时间片大小n时间片长度变化的影响时间片长度变化的影响n过长过长退化为退化为FCFS算法，进程在一个时间片内都算法，进程在一个时间片内都执行完，响应时间长。执行完，响应时间长。n过短过短用户的一次请求需要多个时间片才能处理完，用户的一次请求需要多个时间片才能处理完，进程切换次数增加，响应时间长。进程切换次数增加，响应时间长。n最好：

22、略大于一次典型的交互所需的时间最好：略大于一次典型的交互所需的时间虚轮转法虚轮转法n轮转法缺点：受处理器限制的进程和受轮转法缺点：受处理器限制的进程和受I/O限制限制的进程的相对处理，导致实际占用处理器时间的的进程的相对处理，导致实际占用处理器时间的不公平不公平n虚轮转法：虚轮转法：n新进程到达或时间段用完加入就绪对列，基于新进程到达或时间段用完加入就绪对列，基于FCFSn为为I/O而阻塞的进程加入一个而阻塞的进程加入一个I/O对列，解除了对列，解除了I/O阻塞的进程都转移到一个阻塞的进程都转移到一个FCFS辅助队列中辅助队列中n进行一次调度决策时，辅助对列中的进程优先于就绪进行一次调度决策时

23、，辅助对列中的进程优先于就绪对列中的进程对列中的进程图图9.7最短进程优先最短进程优先n选择函数选择函数MIN(s),非抢占非抢占n选择所需选择所需CPU时间最短的进程时间最短的进程n短进程将会越过长作业，跳到队列头短进程将会越过长作业，跳到队列头ABCDE51015200ABCDE最短进程优先最短进程优先n对长进程非常不利，长进程可能被饿死对长进程非常不利，长进程可能被饿死n难以准确估计进程的执行时间，从而影响难以准确估计进程的执行时间，从而影响调度性能调度性能n如果估计进程所需处理的时间不正确，操如果估计进程所需处理的时间不正确，操作系统可能终止这个作业作系统可能终止这个作业1973 19

24、73 年关闭年关闭 MIT MIT 的的 IBM 7094,IBM 7094,发发现现 1967 1967年提交的作业还未运行！年提交的作业还未运行！最短剩余时间（最短剩余时间（SRT）n选择函数选择函数MIN(s-e),到达时抢占到达时抢占n对对SPN增加了抢占机制的版本，调度程序增加了抢占机制的版本，调度程序总是选择预期总是选择预期剩余时间最短剩余时间最短的进程的进程n执行选择函数时必须估计处理时间执行选择函数时必须估计处理时间n周转时间方面，性能优于周转时间方面，性能优于SPNABCDE51015200ABCDE最高响应比优先最高响应比优先 (HRRN)n选择函数选择函数MAX(R),非

25、抢占非抢占n选择响应比最大的进程选择响应比最大的进程等待处理器的时间等待处理器的时间 + 预计的服务时间预计的服务时间预计的服务时间预计的服务时间ABCDE是FCFS和SPN的折衷51015200ABCDEw+ ssR=多级反馈队列调度多级反馈队列调度(MFQ)n特点特点 多个就绪队列，各个队列具有不同优先级多个就绪队列，各个队列具有不同优先级 新进程首先插入第一个队列末尾，新进程首先插入第一个队列末尾，FCFSFCFS排队；在规排队；在规定的时间片内该进程若执行完，则撤离，否则降至定的时间片内该进程若执行完，则撤离，否则降至第二个队列排队。第二个队列排队。直到降至第直到降至第n n个队列，则按个队列，则按时间片轮转方式执行。时间片轮转方式执行。n性能：长、短作业兼顾，有较好的响应时间性能：长、短作业兼顾，有较好的响应时间 终端型作业一次完成；终端型作业一次完成； 短批处理作业周转时间不长；短批处理作业周转时间不长； 长批处理作业不会长期不处理。长批处理作业不会长期不处理。多级反馈队列调度多级反馈队列