第9周-处理机调度

《第9周-处理机调度》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章处理机调度4.1分级调度4.2作业调度4.3进程调度4.4调度算法4.5算法评价4.6实时系统调度方法本章小结习题4.4调度算法包括进程调度、作业调度（两种不同的调度机制）关于进程的CPUburst与I/Oburst：阵发期:CPUburstcycle:进程使用CPU计算；I/Oburstcycle:进程使用设备I/O。进程运行行为：CPUburst,I/Oburst,CPUburst,I/Oburst,……进程调度：对处于CPUburst的进程集合的调度。1.先来先服务调度算法（FCFS）－FirstComeFirstServe将用户作业或就绪进程按提交顺序

2、或变为就绪状态的顺序排成队列，并按照先进先出(先来先服务)的方式进行调度处理，是一种最简单的方法。特点:(1)实现简单(2)适于作业调度、进程调度(3)公平?对于执行时间较短的作业或进程来说，等待时间可能较长。先来先服务调度算法（续）考虑下面的例子:如果作业队列依次(几乎同时)到达如下3个作业,按“先来先服务”的方式进行调度完成后，计算平均等待时间：作业需运行时间J150J210J31运行情况：0506061平均等待时间=（0+50+60）/3≈36.67如果到达顺序为J3、J2、J1，运行情况：011161平均等待时间=（0+1+11）/3=4J1J2J3J3J2

3、J12.轮转调度算法（RoundRobin）轮转法的基本概念是将CPU的处理时间分成固定大小的时间片（⊿T）。如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的CPU而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程。注意：（1）该算法适于进程调度，一般不适于作业调度（为什么？）（2）适应系统：分时系统图4.4轮转法调度或进入等待队列时间片到轮转调度算法（续）例：设某系统时间片值为20，下列进程的调度情况：ProcessBurstTimeP153P217P368P424在实际系统中

4、，通常情况下随着时间的推移，某些进程运行完成本次的CPUBurst而撤离就绪队列，同时还会有新的就绪进程不断地加入。P1P2P3P4P1P3P4P1P3P302037577797117121134154162（3）时间片长度的取值①固定时间片时间片长度：几十毫秒几百毫秒(例如50ms)过长：响应速度慢算法会退化为FCFS；过短：进程切换过于频繁系统开销(overhead)大。②可变时间片设系统对响应时间的要求是R，就绪队列中最大进程数为Nmax。因为R≈

5、⊿T

6、*Nmax所以

7、⊿T

8、≈R/Nmax一种可行的办法是，每当一轮调度开始时，系统便根据就绪队列中已有进

9、程数目计算一次⊿T值，作为新一轮调度的时间片。这种方法得到的时间片值随就绪队列中的进程数变化。轮转调度算法（续）3.最短作业优先调度算法（SJF）－ShortestJobFirst最短作业优先法（SJF）就是选择那些估计需要执行时间最短的作业投入执行。例：如果作业队列依次(几乎同时)到达如下3个作业,按最短作业优先法（SJF）调度。作业需运行时间J150J210J31011161平均等待时间=（0+1+11）/3=4J3J2J1最短作业优先调度算法（续）优点：（1）可使得系统在单位时间内处理的作业个数最多——吞吐量最大。（2）对同一批作业而言，该算法使得作业的平均等

10、待时间最短。缺点：可能使得某些运行时间较长的作业得不到调度执行的机会。两种调度方式：（1）非剥夺方式（2）剥夺方式，即最短剩余时间优先——Shortest-Remaining-TimeFirst(SRTF)。最短作业优先调度算法（续）非剥夺方式示例：ProcessArrivalTimeBurstTimeP10.07P22.04P34.01P45.04平均等待时间=(0+6+3+7)/4=4P1P3P273160P4812最短作业优先调度算法（续）剥夺方式示例：ProcessArrivalTimeBurstTimeP10.07P22.04P34.01P45.04平均等

11、待时间=(9+1+0+2)/4=3P1P3P242110P457P2P116最短作业优先调度算法（续）对运行时间的估计：（1）作业调度：系统要求用户在提交作业时声明估计作业的运行时间。（2）进程调度：CPUburst时间的确定—根据进程以前的行为推测。1.tn=第n次CPUburst的实际运行时间2.n+1=下一次CPUburst的估计(预测)运行时间3.0≦≦14.定义:=0时，n+1=n，即估计时间为常量，没考虑实际运行时间=1时，n+1=tn，即估计时间为上次的实际运行时间通常，可以选择=1/2最短作业优先调度算法（续）例：现有某进程，各