15.1处理机调度概念

CPU资源的时分复用

■进程切换：CPU资源的当前占用者切换

保存当前进程在PCB中的执行上下文(CPU状态)

恢复下一个进程的执行上下文

■处理机调度

从就绪队列中挑选下一个占用CPU运行的进程

从多个可用CPU中挑选就绪进程可使用的CPU资源

■调度程序：挑选就绪进程的内核函数

调度策略

依据什么原则挑选进程/线程？

调度时机

什么时候进行调度？

调度时机

■内核运行调度程序的条件

进程从运行状态切换到等待状态

进程被终结了

■非抢占系统

当前进程主动放弃CPU时

■可抢占系统

中断请求被服务例程响应完成时

当前进程被抢占

进程时间片用完

进程从等待切换到就绪

精髓：

操作系统根据进程的执行对三种类型的调度方案做出选择。长程调度确定何时允许一个新进程进入系统。中程调度是交换功能的一部分，它确定何时把一个程序的部分或全部取进内存，使得该程序能够被执行。短程调度确定哪一个就绪进程下一次被处理器执行。

15.2调度准则

处理机资源的使用模式

■进程在CPU计算和I/O操作间交替

每次调度决定在下一个CPU计算时将哪个工作交给CPU

在时间片机制下，进程可能在结束当前CPU计算前被迫放弃CPU（对进程执行不利）

比较调度算法的准则

■CPU使用率

CPU处于忙状态的时间百分比（需要是CPU尽可能的忙）

■吞吐量

单位时间内完成的进程数量

■周转时间

进程从初始化到结束的总时间(包括进入内存、在就绪队列中等待、在CPU上执行和I/O执行。通常受输出设备速度的限制）

■等待时间

进程在就绪队列中的总时间

■响应时间

从提交请求到产生响应所花费的总时间

吞吐量与延迟

■调度算法的要求

希望“更快”的服务

■什么是更快？

传输文件时的高带宽，调度算法的高吞吐量

玩游戏时的低延迟，调度算法的低响应延迟

这两个因素是独立的

■与水管的类比

低延迟：喝水的时候想要一打开水龙头水就流出来

高带宽：给游泳池充水时希望从水龙头里同时流出大量的水，并且不介意是否存在延迟

概念：需要使CPU使用率和吞吐量最大化，而使周转时间、等待时间和相应时间最小化。

处理机调度策略的响应时间目标

■减少响应时间

及时处理用户的输入请求，尽快将输出反馈给用户

■减少平均响应时间的波动

在交互系统中，可预测性比高差异低平均更重要

■低延迟调度改善了用户的交互体验

如果移动鼠标时，屏幕中的光标没动，用户可能会重启电脑

■响应时间是操作系统的计算延迟

处理机调度策略的吞吐量目标

■增加吞吐量

减少开销（操作系统开销，上下文切换）

系统资源的高效利用（CPU，I/O设备）

■减少等待时间

减少每个进程的等待时间（可以提高它的响应性能也可以提高它的吞吐量的性能）

■操作系统需要保证吞吐量不受用户交互的影响

操作系统必须不时进行调度，即使存在许多交互任务

■吞吐量是操作系统的计算带宽

处理机调度的公平性目标

■公平的定义

保证每个进程占用相同的CPU时间

保证每个进程的等待时间相同

■公平通常会增加平均响应时间

15.3调度算法

先来先服务算法(First Come First Served, FCFS)

■依据进程进入就绪状态的先后顺序排列

进程进入等待或结束状态时（进程主动让出cpu），就绪队列中的下一个进程占用CPU

■优点

简单

■缺点

·平均等待时间波动较大

短进程可能排在长进程后面

·I/O资源和CPU资源的利用率较低

CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也等待

短进程优先算法(SPN)

■选择就绪队列中执行时间最短进程占用CPU进入运行状态

就绪队列按预期的执行时间来排序

■短剩余时间优先算法(SRT)

SPN算法的可抢占改进

■优点

短进程优先算法具有最优平均周转时间

■缺点

·可能导致饥饿

连续的短进程流会使长进程无法获得CPU资源

·需要预知未来

如何预估下一个CPU计算的持续时间？

简单的解决办法：询问用户

用户欺骗就杀死相应进程

用户不知道怎么办？

■短进程优先算法的执行时间预估

用历史的执行时间来预估未来的执行时间

最高响应比优先算法(HRRN)

■选择就绪队列中响应比R值最高的进程

Ｒ＝（ｗ+s)/s

w:等待时间(waiting time)

s:执行时间(service time)

在短进程优先算法的基础上改进

不可抢占

关注进程的等待时间

防止无限期推迟

时间片轮转算法(RR, Round-Robin)

■时间片

分配处理机资源的基本时间单元q

■算法思路

时间片结束时，按FCFS算法切换到下一个就绪进程

每隔(n–1)个时间片进程执行一个时间片q

注：分配了一个基本时间单元q，每个进程每次在时间片q的时间内执行，没完成则继续排队尾，完成了结束。

时间片为20的RR算法示例

时间片轮转算法中的时间片长度

■RR算法开销

额外的上下文切换

■时间片太大（退化成FCFS）

等待时间过长

极限情况退化成FCFS

■时间片太小

反应迅速，但产生大量上下文切换

大量上下文切换开销影响到系统吞吐量

■时间片长度选择目标

选择一个合适的时间片长度

经验规则：维持上下文切换开销处于1%以内

比较FCFS和RR

多级队列调度算法(MQ)

■就绪队列被划分成多个独立的子队列

如：前台(交互)、后台(批处理)

■每个队列拥有自己的调度策略

如：前台–RR、后台–FCFS

■队列间的调度

·固定优先级

先处理前台，然后处理后台

可能导致饥饿

·时间片轮转

每个队列都得到一个确定的能够调度其进程的CPU总时间

如：80%CPU时间用于前台，20%CPU时间用于后台

多级反馈队列算法(MLFQ)

注：例：分三个执行队列，0队列的时间片是8，1队列的时间片是24，2队列采用FCFS。不超过8的进程有最高优先级，接下来依次。在队列0中未执行完的进程将会排至队列1末尾，队列1中未执行完的排队列2尾。

■进程可在不同队列间移动的多级队列算法

时间片大小随优先级级别增加而增加（优先级高时间片小）

如进程在当前的时间片没有完成，则降到下一个优先级（执行时间越长，优先级调的越低）

■MLFQ算法的特征

CPU密集型进程的优先级下降很快，优先级会逐步降低，并且时间片会分的很大

I/O密集型进程停留在高优先级

公平共享调度(FSS, Fair Share Scheduling)

■FSS控制用户对系统资源的访问

一些用户组比其他用户组更重要（用户分组，根据重要程度）

保证不重要的组无法垄断资源

未使用的资源按比例分配

没有达到资源使用率目标的组获得更高的优先级

传统调度算法总结

■先来先服务算法

不公平，平均等待时间较差

■短进程优先算法

不公平，平均周转时间最小

需要精确预测计算时间

可能导致饥饿

■最高响应比优先算法（主要考虑等待时间）

基于SPN调度

不可抢占

■时间片轮转算法

公平，但是平均等待时间较差，交互性很好

■多级反馈队列

多种算法的集成

■公平共享调度

公平是第一要素

概念：先到先服务〔FCFS)调度是最简单的调度算法，但是它会让短进程等待非常长的进程。最短作业优先(SJF)调度可证明是最佳的，它提供了最短平均等待时间。实现SJF调度比较困难，因为预测下一个CPU区间的长度有难度。SJF算法是通用优先级调度算法（将CPU简单地分配给具有最高优先级的进程)的特例。优先级和SJF调度会产生饥饿。老化技术（随等待时间增加逐渐提高优先级）可阻止饥饿。

轮转法(RR)调度对于分时(交互)系统更为合适。RR调度让就绪队列的第一个进程使用CPU的q个时间单元，这里q是时间片。在q时间单元之后，如果该进程还没有释放CPU，那么它被抢占并放到就绪队列的尾部。该算法是主要问题是选择时间片。如果时间片太大，那么RR调度就成了FCFS调度:

如果时间片太小，那么因上下文切换而引起的调度开销就过大。

FCFS算法是非抢占的，而RR算法是抢占的。SJF和优先级算法可以是抢占的，也可以是非抢占的。

多级队列调度算法允许多个不同算法用于各种类型的进程。最为常用的模型包括使用RR调度的前台交互队列，以及使用FCFS调度的后合批处理队列。多级反馈队列调度算法允许进程在队列之间迁移。

15.5实时调度

实时操作系统

■实时操作系统

正确性依赖于其时间和功能两方面的操作系统

■实时操作系统的性能指标

时间约束的及时性（deadlines）

速度和平均性能相对不重要

■实时操作系统的特性

时间约束的可预测性

实时操作系统分类

■强实时操作系统

要求在指定的时间内必须完成重要的任务

■弱实时操作系统

重要进程有高优先级，要求尽量但非必须完成

实时任务

■任务（工作单元）

一次计算，一次文件读取，一次信息传递等等

■任务属性

完成任务所需要的资源

定时参数

周期实时任务

■周期实时任务：一系列相似的任务

任务有规律地重复

周期p =任务请求时间间隔(0

执行时间e =最大执行时间(0 < e < p)

使用率U = e/p

软时限和硬时限

■硬时限（Hard deadline）

错过任务时限会导致灾难性或非常严重的后果

必须验证，在最坏情况下能够满足时限

■软时限(Soft deadline)

通常能满足任务时限

如有时不能满足，则降低要求

尽力保证满足任务时限

可调度性

■可调度表示一个实时操作系统能够满足任务时限要求

需要确定实时任务的执行顺序

静态优先级调度（事先把执行顺序排出来，按这个顺序调度，理论上保证能够满足要求）

动态优先级调度（执行过程中给出执行顺序）

实时调度

■速率单调调度算法(RM, Rate Monotonic)（静态）

通过周期安排优先级

周期越短优先级越高

执行周期最短的任务

■最早截止时间优先算法(EDF, Earliest Deadline First)动态

截止时间越早优先级越高

执行截止时间最早的任务

15.5（2）多处理器调度

■多处理机调度的特征

多个处理机组成一个多处理机系统

处理机间可负载共享

■对称多处理器(SMP, Symmetric multiprocessing)调度

每个处理器运行自己的调度程序

调度程序对共享资源的访问需要进行同步

对称多处理器（SMR）的进程分配

■静态进程分配

进程从开始到结束都被分配到一个固定的处理机上执行

每个处理机有自己的就绪队列

调度开销小

各处理机可能忙闲不均

■动态进程分配

进程在执行中可分配到任意空闲处理机执行

所有处理机共享一个公共的就绪队列

调度开销大

各处理机的负载是均衡的

概念：

处理器亲和性：绝大多数SMP系统试图避免将进程从一个处理器移至另一个处理器，而是努力使一个进程在同一个处理器上运行

负载平衡（load balancing）：Push migration,pull mifration。

对称多线程（SMT）：通过提供多个物理处理器，SMP系统允许同时运行几个线程。另一种方法是提供多个逻辑（而不是物理逻辑）处理器来实现。SMT是硬件而不是软件提供的。

15.6优先级反置(Priority Inversion)

■操作系统中出现高优先级进程长时间等待低优先级进程所占用资源的现象

■基于优先级的可抢占的调度算法存在优先级反置

注：已经排好的执行队列中有T1。T2两个进程，T1的优先级比T2低，这是一个处于中间的进程T3抢占T1，三个都要用的资源L1现在被T3占用，这就是优先级反置。

解决方法：优先级继承（Priority Inheritance），优先级天花板协议（priority ceiling protocol）

优先级继承（Priority Inheritance）

■占用资源的低优先级进程继承申请资源的高优先级进程的优先级

只在占有资源的低优先级进程被阻塞时,才提高占有资源进程的优先级

优先级天花板协议（priority ceiling protocol）

■占用资源进程的优先级和所有可能申请该资源的进程的最高优先级相同

不管是否发生等待,都提升占用资源进程的优先级

优先级高于系统中所有被锁定的资源的优先级上限，任务执行临界区时就不会被阻塞