本节讲CPU调度，分为如下三个部分:

• 基本概念
• 调度准则
• 调度算法

基本概念

进程执行总是有CPU执行和I/O 等待周期组成的，也就是有下面的这个图

回忆在第5节笔记中讲的进程的三状态模型， CPU调度决策可在如下的决策中发生:

1. 运行切到等待(e.g.: I/o请求 )
2. 进程终止
3. 运行到就绪(e.g.: 中断，抢占，时间片到期)
4. 等待到就绪 (e.g.: I/O 完成)

前两种没有选择只能调度， 不过，3，4都可以选择。 当调度仅发生在前两种时是非抢占的，否则称为抢占的。对于非抢占调度，一个进程会占用CPU到进程结束或等待。而现代计算机大多采用抢占调度，抢占调度涉及共享数据时会发生数据同步问题这时下一节要讲的。

调度准则

当我们评判不同的CPU调度算法时需要有一定的准则来衡量不同算法间的性能。这些准则如下：

• CPU利用率
• 吞吐量 一个时间单位内完成的进程数(PS: 个人认为这样不是很公平，长进程运行时间长而短进程运行时间很短)
• 周转时间 进程从提交到退出所用的时间，包括等待，调度
• 等待时间 周转时间中除去进程运行所固有的时间(CPU执行时间和I/O访问时间)，即在就绪队列中等待消耗的时间
• 响应时间 这是前台进程最关心的时间提交到产生第一响应的时间(e.g.: 点了个ppt，电脑的打开的时间)

接下来我们讨论调度算法

调度算法

主要讲以下几种：

• FCFS
• SPN
• HRRN
• RR
• MQ
• MLFQ

FCFS(先来先服务)

这个算法往往在很多涉及队列的算法中常被使用……，可能是研究方便吧，往往是其他算法的基础

就是将就绪队列组成一个FIFO队列， 谁排在前面谁先服务，这个调度是非抢占的，即进入等待状态的进程等待完成后排到就绪队列的末尾。

特点

• 实现简单
• 平均等待时间与顺序密切相关

如果按照执行时间从小到达排的化能达到最小平均等待时间

SPN/SJF（short job first） 短进程优先

这就是 按照进程执行时间从小到大排的调度。不难证明，这种调度算法能使平均周转时间最小。然而显然难点在于如何”预测未来“。这可以通过指数平均来实现，(有点像TCP/IP里测窗口大小的方法),即：

• πn+1 为下一个CPU区间预测值
• tn 为第 n 个CPU区间长度

则

SJF 可以是抢占的，也可以是非抢占的，即，如果来了一个新进程，而此时执行时间比当前运行进程短，则如果是抢占的，可以将让当前进程先执行。有时称抢占的SJF为最短剩余时间优先

HRRN 最优响应比优先

这种算法与前两种类似，不过是按照响应比来排序的:

• rank: (w+s)/s
• w: wait time
• s: server time

前三种调度算法都是优先级调度算法，即按照某种优先级排序组织就绪队列进行调度。这种算法有一个最大的问题是会引起 饥饿，即有进程一直不能执行。一种解决方法称为 老化 技术，即经过一定的等待时间后将进程优先级调整。

RR 轮转法调度

这是专门为分时系统设计的，即在FCFS的基础上为每个执行进程分配一个固定的时间片，当时间片到期后就切到就绪态。

RR调度算法的平均等待时间与时间片取值密切相关，特别地，当时间片很大的时候，退化到FCFS。我们看下面的比较

多级队列调度

多级队列调度时间进程分成不同的组，(e.g: 前台进程后后台进程)，不同组的采用不同的调度算法，或则是时间片不同。

多级反馈队列调度

显然是多级队列的改进，既然能按任务不同特性分，为撒不按CPU执行区间来分?
MLFQ就是这样的方法，每个队列分配不同的时间片。分配不同的优先级，当前优先级分配的时间片没运行完，将其降一级，以得到更多的时间片，显然这样会最终让前台进程得到更高的优先级而CPU密集型会得到更低的优先级，即更长的时间片。

公平共享调度

待填坑……

多处理器调度

……