第9周-处理机调度

单击此处编辑母版标题样式单击此处编辑母版副标题样式第 4章 处理机调度4.1 分级调度4.2 作业调度4.3 进程调度4.4 调度算法4.5 算法评价4.6 实时系统调度方法本章小结习题4.4 调度算法包括进程调度、作业调度（两种不同的调度机制）关于进程的 CPU burst 与 I/O burst： 阵发期 :CPU burst cycle: 进程使用 CPU计算；I/O burst cycle: 进程使用设备 I/O。 进程运行行为：CPU burst, I/O burst, CPU burst, I/O burst, 进程调度：对处于 CPU burst的进程集合的调度。1. 先来先服务调度算法（ FCFS） First Come First Serve将用户作业或就绪进程按提交顺序或变为就绪状态的顺序排成队列，并按照先进先出 (先来先服务 )的方式进行调度处理，是一种最简单的方法。特点 :(1)实现简单(2)适于作业调度、进程调度(3)公平 ?对于执行时间较短的作业或进程来说，等待时间可能较长。先来先服务调度算法（续）考虑下面的例子 :如果作业队列依次 (几乎同时 )到达如下 3个作业 ,按 “先来先服务 ”的方式进行调度完成后，计算平均等待时间：作 业 需运行 时间J1 50J2 10J3 1运行情况：0 50 60 61平均等待时间 =（ 0+50+60） /336.67如果到达顺序为 J3、 J2、 J1，运行情况：0 1 11 61平均等待时间 =（ 0+1+11） /3=4J1 J2 J3J3 J2 J12. 轮转调度算法（ Round Robin）轮转法的基本概念是将 CPU的处理时间分成固定大小的时间片（ T）。如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的 CPU而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程。注意 ：（ 1）该算法 适于进程调度，一般不适于作业调度（为什么？）（ 2） 适应系统：分时系统图 4.4轮转法调度或进入等待队列或进入等待队列时间片到时间片到轮转调度算法（续）例：设某系统时间片值为 20，下列进程的调度情况：Process Burst TimeP1 53P2 17P3 68P4 24在实际系统中，通常情况下随着时间的推移，某些进程运行完成本次的 CPU Burst而撤离就绪队列，同时还会有新的就绪进程不断地加入。P1 P2 P3 P4 P1 P3 P4 P1 P3 P30 20 37 57 77 97 117 121 134 154 162（ 3）时间片长度的取值 固定时间片时间片长度： 几十毫秒 几百毫秒 (例如 50ms) 过长：响应速度慢 算法会退化为 FCFS； 过短：进程切换过于频繁 系统开销 (overhead)大。 可变时间片设系统对响应时间的要求是 R，就绪队列中最大进程数为 Nmax。因为 R | T|*Nmax所以 | T| R/Nmax一种可行的办法是，每当一轮调度开始时，系统便根据就绪队列中已有进程数目计算一次 T值，作为新一轮调度的时间片。这种方法得到的时间片值随就绪队列中的进程数变化。轮转调度算法（续）3. 最短作业优先调度算法（ SJF） Shortest Job First最短作业优先法（ SJF）就是选择那些估计需要执行时间最短的作业投入执行。例：如果作业队列依次 (几乎同时 )到达如下 3个作业 ,按最短作业优先法（ SJF）调度。作 业 需运行 时间J1 50J2 10J3 10 1 11 61平均等待时间 =（ 0+1+11） /3=4J3 J2 J1最短作业优先调度算法（续）优点：（ 1）可使得系统在单位时间内处理的作业个数最多 吞吐量最大。（ 2）对同一批作业而言，该算法使得作业的平均等待时间最短。缺点：可能使得某些运行时间较长的作业得不到调度执行的机会。两种调度方式：（ 1）非剥夺方式（ 2）剥夺方式，即最短剩余时间优先 Shortest-Remaining-Time First (SRTF)。最短作业优先调度算法（续）非剥夺方式示例 ：Process Arrival Time Burst TimeP1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4平均等待时间 = (0 + 6 + 3 + 7)/4 = 4P1 P3 P273 160P48 12最短作业优先调度算法（续）剥夺方式示例：Process Arrival Time Burst TimeP1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4平均等待时间 = (9 + 1 + 0 +2)/4 = 3P1 P3P242 110P45 7P2 P116最短作业优先调度算法（续）对运行时间的估计：（ 1）作业调度：系统要求用户在提交作业时声明估计作业的运行时间。（ 2）进程调度： CPU burst时间的确定 根据进程以前的行为推测 。1. tn=第 n次 CPU burst的实际运行时间2.n+1=下一次 CPU burst的估计 (预测 )运行时间3. 0 14.定义 :=0时， n+1 = n， 即估计时间为常量，没考虑实际运行时间=1时， n+1 = tn， 即估计时间为上次的实际运行时间通常，可以选择 =1/2最短作业优先调度算法（续）例：现有某进程，各 CPU burst实际时间为： 6、 4、 6、 4、13、 13、 13 。 给出系统每次调度前 CPU burst的估计值。系统设定的 1=10 ， 选择 =1/2。 2=10+0.5*(6-10)=8 3=8+0.5*(4-8)=6 4=6+0.5*(6-6)=6 5=6+0.5*(4-6)=5 6=5+0.5*(13-5)=9 7=9+0.5*(13-9)=11 8=11+0.5*(13-11)=124. 最高响应比优先调度算法（ HRN）Highest Response ratio Next最高响应比优先法（ HRN）是对 FCFS方式和 SJF 方式的一种综合平衡。响应比 R定义如下： R=(W+T)/T=1+W/T其中 T为该作业估计需要的执行时间， W 为作业的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中 R最大者投入执行。这种算法是介于 FCFS和 SJF 之间的一种折中算法。由于每次调度前要计算响应比，系统开销也要相应增加。最高响应比优先调度算法（续 ）R=(W+T)/T=1+W/T考虑下面的例子作 业 到达 时间 需运行 时间 开始 时间完成 时间 等待 时间J1 8:00 50分 8:00 8:50 0分J2 8:30 20分J3 8:40 15分J4 8:55 5分8:50 9:10 20分9:15 9:30 35分9:10 9:15 15分平均等待时间 (0 20 35 15)4 17.5分别采用 FCFS、 SJF算法进行调度，各自的平均等待时间？反映了什么问题？5. 优先级调度算法（ HPF） Highest Priority First系统或用户按某种原则为作业或进程指定一个优先级，系统按优先级进行调度。优先级法可被用于作业或进程的调度策略。（ 1）优先级的确定静态法：在作业或进程开始执行之前就确定它们的优先级，一旦开始执行之后就不能改变。动态法：随着作业或进程的执行，其优先级不断变化。（ 2）影响优先级因素外部因素：任务的紧迫程度、付费、进程类型 (系统、用户进程 )。例如，在操作系统中，对于键盘中断的处理优先级和对于电源掉电中断的处理优先级是不相同的。内部因素：作业类型（ IO型、计算型）、资源需求（ 3）剥夺 非剥夺优先级调度非剥夺方式：获得处理机的进程，直至终止、等待剥夺方式：获得处理机的进程，直至终止、等待、出现高优先级的就绪进程优先级调度算法（ 续）其实优先级调度算法仅仅是一种思想，前面介绍的所有算法都可看成是优先级调度。UNIX例子：可剥夺、动态优先级调度优先级计算公式：p_pri=min127, USER+p_cpu/16+p_nice定义 USER=100； p_cpu: 运行进程每 20ms加 1（优先级降低） ，其它 就绪进程每 1200ms减 10（优先级提高）； p_nice: 可以通过系统调用 nice()修改的量 。6.多级队列算法 (MLQ) Multilevel Queue多个就绪队列，进程所属的队列固定。不同就绪队列具有不同优先级；各个队列拥有自己的调度算法；处理机要在不同队列中调度。例如：某通用系统队列 1：实时进程就绪队列（ HPF）队列 2：分时进程就绪队列（ RR）队列 3：批处理进程就绪队列（ HPF）7. 多级反馈队列调度算法（ MFQ） Multilevel Feedback Queue（ 1）多个就绪进程队列（ 2）进程会在不同队列中移动（ 3）该算法的关键点：就绪队列个数每个队列采用的调度算法何时提升、降低进程优先级进程就绪该进程进入哪个就绪队列Q1（ RR， HPF）Q2（ RR， HPF）Qn（ RR， HPF）运行 s1时间片运行 s2时间片.创建唤醒高优先级低运行 sn时间片多级反馈队列调度算法（续）一个实例 :n个就绪队列；每个队列采用类似的 RR算法；队列之间采用剥夺 HPF算法； Q1优先级最高，对应的时间片 S1最小， Qn优先级最低，对应的时间片 Sn最大；就绪进程进入 Q1就绪队列。运行结束退出运行结束退出运行结束退出小时间片大（ 1）该算法宗旨：以 IO为主的进程响应速度较快，以计算为主的进程运行一段时间后，会下降到低优先级队列运行。（ 2）系统效率较高、资源利用率高。（ 3）算法的改进：考虑某些以计算为主的进程，偶尔一次 IO；开始时以计算为主，后来变为以 IO为主。改进方法：每一次 IO结束后，再次就绪时进入高一级就绪队列。例如 VAX VMS操作系统的处理。 多级反馈队列调度算法（续）优先级调度算法（ 实例）例如：线性优先级调度策略（ selfish round robin）使用轮转法调度进程时，新创建的进程也放入就绪队列末尾享受平等的处理机时间片。这对于执行时间长的进程来说是有点不公平的，因为它们需要多个时间片才能完成。因此，线性优先级调度策略采用如下方式，即新创建的进程按 FCFS方式排成就绪队列，而其他已得到过时间片服务的进程也按 FCFS方式排成另一个就绪队列或称享受服务队列 (图 4.5）。图 4.5 线性优先级调度对于这两个不同队列中的进程，设新创建进程就绪队列中进程的优先级 P以 P=a*t (a0) 的速率增加。另外，享受服务队列中进程的优先级 P以 P=b*t (ab0) 的速率增长。设某一进程在时刻 t1时被创建，在时刻 t时，该进程的优先级为P(t)=a*(t-t1) (t1b0 的条件是必要的。否则，当 ba0 时，两个不同队列中的就绪态进程的优先级将永远不会相等，从而，在享受服务进程队列中永远只有一个进程。因此，上述线性优先级调度策略退回到 FCFS方式。另外，如果ab=0， 则线性优先级调度策略退回到轮转法调度方式。事实上，线性优先级调度策略是一种介于轮转法和 FCFS方式之间的调度策略。这几种方式的调度性能，将在下一节中更进一步讨论。习 题 4.1 什么是分级调度？分时系统中有作业调度的概念吗？如果没有，为什么？4.2 试述作业调度的主要功能。4.3 作业调度的性能评价标准有哪些？这些性能评价标准在任何情况下都能反映调度策略的优劣吗？4.4 进程调度的功能有哪些？4.5 进程调度的时机有哪几种？4.6 进程上下文切换由哪几部分组成？形式化地描述进程上下文切换过程。4.7 为什么说在进程上下文切换过程中，上下文切换程序不能破坏 “老 ”进程的上下文结构？ 4.8 假设有 4道作业，它们的提交时刻及执行时间由下表给出：计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。 作 业 号 提交 时 刻（小 时）执 行 时间 （小 时）1 10.00 22 10.20 13 10.40 0.54 10.50 0.34.9 设某进程所需要的服务时间 t=k*q， 其中， k为