《操作系统》第五章：CPU调度

第5章CPU调度5.1基本概念（1）什么是CPU调度？

每当CPU空闲时，操作系统必须按照一定的策略从

就绪队列当中选择一个进程来执行。调度的对象：进程或线程。其方式与原则是一样的。

故经常以进程来说明：进程调度<==>CPU调度（2）CPU调度遵循什么原则？

总原则：资源高效、公平合理具体一般包括：提高CPU利用率提高系统运算的吞吐量缩短进程的周转时间缩短进程的等待时间提高用户的响应满意度

……5.1基本概念（3）CPU-I/O区间周期

程序代码可以分为计算类代码和I/O类代码进程执行过程由CPU执行和I/O等待周期组成

CPU区间和I/O区间

CPU约束型程序以计算为主，CPU区间会较

多，还会有少量长的CPU区间

I/O约束型程序以I/O为主，但配合I/O处理会

有大量短的CPU区间区间区间区间区间区间区间5.1基本概念（3）CPU-I/O区间周期（续）

实验证明：进程中短的CPU区间出现的几率极高区间持续长度（ms）出现频率（次数）调度情况1：因等待某些事件而让出CPUsum(等待文件输出)(等待文件输出)PCB1RegistersPCB6RegistersHeadTail磁盘等待队列PCB4RegistersPCB8RegistersPCB7RegistersHeadTail就绪队列物理CPUPCB6RegistersPCB4Registers5.1基本概念（4）非抢占式调度与抢占式调度PCB4RegistersPCB8RegistersPCB7RegistersHeadTail就绪队列物理CPUPCB7RegistersPCB4Registers调度情况2：规定的时间片到了

调度情况3：出现了优先级更高的进程5.1基本概念（4）非抢占式调度与抢占式调度（续）PCB4RegistersPCB8RegistersPCB7RegistersHeadTail就绪队列物理CPUPCB7RegistersPCB4Registers调度情况4：进程的任务完成了，自动终止退出僵死队列HeadTailPCB10Registers5.1基本概念（4）非抢占式调度与抢占式调度（续）调度情况1：因等待某些事件而让出CPU

调度情况4：进程的任务完成了，自动终止退出

非抢占式调度：由于主动让出CPU的情况发生，致使调度程

序将CPU分配给某就绪进程的调度方式

早期的多道批处理操作系统；Windows3.X版等5.1基本概念（4）非抢占式调度与抢占式调度（续）调度情况2：规定的时间片到了

调度情况3：出现了优先级更高的进程

抢占式调度：操作系统将正在运行的进程强行暂停，由调

度程序将CPU分配给其他就绪进程的调度方式

大多数现代操作系统采用：

Windows95及之后版本；MacOS-X；Linux等让出CPU的具体实现externQueueReadyQueue;externQueueDiskWaitQueue;...DiskWaitQueue.EnQueue(pCur);Dispatch();...Dispatch(){

pNew=PickNext(ReadyQueue);

Switch(pCur,pNew);}分派程序调用“进程选择函数”完成调度该函数就是CPU调度，调度就是下一步该选择哪一个进程或线程来执行(分配CPU资源)!进程和线程都可能是调度单位，统称为任务PickNext()的直观思考简单想一想!应该有很多种策略优先级该怎么设定?Priority?FIFO?FIFO显然是公平的策略FIFO显然没有考虑进程(线程)执行的任务的区别许多算法：评价准则是什么?5.2调度准则CPU调度策略的设计准则公平性：“合理”的分配CPU响应时间短(交互式)，周转时间短(批处理)响应时间:从用户输入到产生反应的时间周转时间:从任务开始到任务结束的时间吞吐量大吞吐量:单位时间完成的任务数量吞吐量大

CPU使用率高+上下文切换代价小周转(响应)时间短

等待时间(在就绪队列中的时间)短

存在矛盾的目标集合响应时间短与公平性之间的矛盾响应时间短

前台任务的优先级高前台任务优先调度

后台任务得不到CPU吞吐量和响应时间之间的矛盾吞吐量大

上下文切换代价小

时间片大时间片大

响应时间长(1010msvs.10500ms)……协调多个目标是操作系统之所以复杂的一个重要原因，也是复杂系统的一个基本特点CPU调度应综合考虑

任务特点任务可以分为交互式任务和批处理任务交互式任务注重对用户的响应：如WORD批处理任务注重对任务吞吐量：如gcc有趣的问题是许多系统中既有交互式任务，又有批处理任务前台任务+后台任务CPU调度应综合考虑

任务特点(续)任务的CPU-IO区间的周期特性任务生存期:I/O(载入),CPU,I/O,CPU,..,CPU(exit())CPU区间长度(ms)频率CPU-约束I/O-约束指数衰减!CPU区间CPU区间CPU调度应综合考虑

调度算法的实现复杂调度算法vs.调度程序执行时间兼顾许多特点会造成复杂的调度算法调度程序执行时间应尽量短就绪队列的数据结构:队列、多级队列、树、无序链表不可能设计完美的调度算法，只能根据应用的特征进行折中权衡。这是操作系统等复杂系统的设计精髓!CPU调度应综合考虑……….CPU调度算法

（1）先到先服务调度FCFS

（2）最短作业优先调度SJF

（3）优先级调度

（4）转轮法调度RR

（5）多级队列调度

（6）多级反馈队列调度5.3调度算法（1）FIFO或FirstCome,FirstServed(FCFS)调度的顺序就是任务到达就绪队列的顺序调度结果P1P2P3106103942P449P5一个实例假定任务的到达顺序为:P1，P2，P3，P4，P5；到达时刻都为0。任务CPU区间(ms)P110P229P33P47P512（1）FIFO或FirstCome,FirstServed(FCFS)调度的顺序就是任务到达就绪队列的顺序调度结果P1P2P3106103942P449P5一个实例假定任务的到达顺序为:P1，P2，P3，P4，P5；到达时刻都为0。任务CPU区间(ms)P110P229P33P47P512FCFS的分析P1P2P3106103942P449P5平均等待时间:(0+10+39+42+49)/5=28公平、简单(FIFO队列)、非抢占、不适合交互式P1P3P2106101342P449P5平均等待时间:(0+10+13+42+49)/5=22.8未考虑任务特性，平均等待时间可以缩短（2）ShortestJobFirst(SJF)最短的作业(CPU区间长度最小)最先调度调度结果P3P4P136101020P532P2一个实例假定任务的到达顺序为:P1，P2，P3，P4，P5；到达时刻都为0。任务CPU区间(ms)P110P229P33P47P512（2）ShortestJobFirst(SJF)最短的作业(CPU区间长度最小)最先调度调度结果P3P4P136101020P532P2一个实例假定任务的到达顺序为:P1，P2，P3，P4，P5；到达时刻都为0。任务CPU区间(ms)P110P229P33P47P512SJF的分析SJF可以保证最小的平均等待时间P3P4P136101020P532P2平均等待时间:(0+3+10+20+32)/5=13证明:设p1p2…pn是调度结果序列，pi是任务CPU区间大小。显然该调度序列的平均等待时间为:

0

+p1

+p1+p2+p1+p2+p3

+….=(n-i)pi如果存在i<j而pi>pj，交换pi,pj调度顺序会减小上值。

SJF:任务到达的时间有先后怎么办?ShortestRemainingJobFirst(SRJF)SJF的可抢占版本一个实例假定任务P1，P2，P3，P4，P5的到达顺序为:任务CPU区间(ms)P110P229P33P47P512到达时间(ms)005530调度结果P1P3P15610813P420P2P230P542SJF:任务到达的时间有先后怎么办?ShortestRemainingJobFirst(SRJF)SJF的可抢占版本一个实例假定任务P1，P2，P3，P4，P5的到达顺序为:任务CPU区间(ms)P110P229P33P47P512到达时间(ms)005530调度结果P1P3P15610813P420P2P230P542SJFvs.SRJF任务CPU区间(ms)P110P229P33P47P512到达时间(ms)005530P1P3P15610813P420P2P230P542P1P31061013P420P5P249SRJFSJF平均等待时间(SRJF):(3+32+0+8+0)/5=8.6平均等待时间(SJF):(0+20+5+8+19)/5=10.4抢占显然具有优点SJF(SRJF):如何知道下一CPU区间大小

n+1=tn+(1-

)

n|

n+1是预测值，tn是当前CPU区间根据历史进行预测:指数平均法

n+1=tn+(1-)tn+...+(1-)j

tn-j+…+(1-)n+1

0

用来控制最近信息和历史对预测的作用

=0-忽略近期，关注历史；

=1-只跟当前有关；通常

=0.5CPU区间(ti):64641313

13预测结果(

i-1):10866591112（3）SJF的一般化:优先权调度每个任务关联一个优先权，调度优先权最高的任务实例1:I/Obound任务应获得更大的优先权，使得I/O尽量忙，并和CPU并行工作。优先级设为1/f，f为CPU区间所占的比重。实例2:

定义多个优先队列:前台任务、后台任务。只有高优先级队列为空时才调度其他任务。优先级3优先级2优先级1优先级4优先权调度引起的一个有趣问题优先权太低的任务一直就绪，得不到运行:饥饿FCFS是RR的特例，SJF是优先权调度的特例。这些调度算法都不适合于交互式系统。一个有趣故事:1973年关闭的MIT的IBM7094时，发现有一个进程在1967年提交但一直未运行。处理办法:

优先级动态调整。最常见的方法是“老化”(aging)技术:

任务的优先级会随等待时间增长而不断增高。（4）适合交互式的调度:Round-Robin(RR)RR:按时间片来轮转调度（“轮叫”算法）一个实例假定任务的到达顺序为:P1，P2，P3，P4，P5；到达时刻都为0，时间片为10。任务CPU区间(ms)P110P229P33P47P512调度结果P1P4P2236101020P330P540P250P552P2（4）适合交互式的调度:Round-Robin(RR)RR:按时间片来轮转调度（“轮叫”算法）一个实例假定任务的到达顺序为:P1，P2，P3，P4，P5；到达时刻都为0，时间片为10。任务CPU区间(ms)P110P229P33P47P512调度结果P1P4P2236101020P330P540P250P552P2RR的分析RR优点:定时有响应，等待时间较短P1P4P2236101020P330P540P250P552P2平均等待时间:(0+32+20+23+40)/5=23SJF的平均等待时间:13;FCFS的平均等待时间:28RR缺点:上下文切换次数较多(7次vs.4次)P3P4P136101020P532P2RR中的时间片该如何设定?响应时间太长时间片太大时间片太小吞吐量变小，周转时间变长如时间片500ms10任务，响应需要5秒如时间片20ms，上下文切换5ms，20%的切换代价折中:时间片10-100ms，切换时间0.1-1ms(1%)RR调度例子：周转时间随着时间片大小而变化时间片进程切换过程12345678910111213141516171P1P2P3P4P1P2P4P1P2P4P1P4P1P4P1P4P42P1P2P3P4P1P2P4P1P4P43P1P2P3P4P1P4P44P1P2P3P4P1P45P1P2P3P4P1P46P1P2P3P4P47P1P2P3P4时间片（时间单位）进程平均周转时间（时间单位）时间片P1周转时间P2周转时间P3周转时间P4周转时间平均周转时间115931744/4=11.02141051746/4=11.5313671743/4=10.75414781746/4=11.5515891749/4=12.25669101742/4=10.5769101742/4=10.5当时间片≥7时等同FCFS！（5）混合多种调度算法

多级队列调度按照一定的规则建立多个进程队列不同的队列有固定的优先级（高优先级有抢占权）不同的队列可以给不同的时间片和采用不同的调度方法

交互式任务批处理任务系统任务最高优先级最低优先级if(!IsEmpty(KernelQ)){next=Pri();return;}if(!IsEmpty(ResponseQ)){next=RR();return;}if(!IsEmpty(BatchQ)){next=SJF();return;}...存在问题1：没法区分I/Obound和CPUbound。存在问题2：也存在一定程度的“饥饿”现象（6）更成熟的多级队列调度

多级反馈队列任务可以在队列之间移动，更细致的区分任务可以根据“享用”CPU时间多少来移动队列，阻止“饥饿”最通用的调度算法，多数OS都使用该方法或其变形，如UNIX、Windows等。系统任务队列2用户任务(时间片为8)系统任务队列1用户任务(时间片为16)用户任务(FCFS)优先权可近似SJF，可使I/Obound停留在高优先级…来看一种实际的调度算法?Linux调度算法概述每个进程有一个信用度counter采用优先权的、基于信用度的、可抢占的RR调度调度时选择信用度最大的进程每次定时器中断，运行进程信用度减1进程信用度为0时，进程暂停并被抢占counter