调度程序：挑选就绪进程的内核函数: 调度策略(依据什么原则挑选进程/线程？
) 调度时机(什么时候进行调度？)
调度时机
在进程/线程的生命周期中的什么时候进行调度？
(1)进程从运行状态切换到等待状态
(2) 进程被终结了
非抢占系统: 当前进程主动放弃CPU时
可抢占系统：（1）中断请求被服务例程响应完成时（2）当前进程被抢占a. 进程时间片用完b. 进程从等待切换到就绪
调度策略: 确定如何从就绪队列中选择下一个执行进程
比较调度算法的准则：
（1）CPU使用率：CPU处于忙状态的时间百分比
（2）吞吐量： 单位时间内完成的进程数量
（3）周转时间：进程从初始化到结束(包括等待)的总时间
（4）等待时间：进程在就绪队列中的总时间
（5）响应时间：从提交请求到产生响应所花费的总时间
吞吐量与延迟
调度算法的要求： 希望“更快”的服务
什么是更快？
传输文件时的高带宽，调度算法的高吞吐量
玩游戏时的低延迟，调度算法的低响应延迟
这两个因素是独立的
与水管的类比：低延迟：喝水的时候想要一打开水龙头水就流出来
高带宽：给游泳池充水时希望从水龙头里同时流出大量的水，并且不介意是否存在延迟
处理机调度策略的响应时间目标
减少响应时间：及时处理用户的输入请求，尽快将输出反馈给用户
减少平均响应时间的波动：在交互系统中，可预测性比高差异低平均更重要
处理机调度策略的吞吐量目标
增加吞吐量：减少开销（操作系统开销，上下文切换）上下文切换的速度更快，系统资源的高效利用（CPU，I/O设备）
减少等待时间：减少每个进程的等待时间（用户和系统的目标是一致的）
吞吐量是操作系统的计算带宽：单位时间执行尽可能多的进程
处理机调度的公平性目标
公平的定义
保证每个进程占用相同的CPU时间（不一定，各个用户需要的时间不同）
保证每个进程的等待时间相同 （第二种度量）
公平通常会增加平均响应时间
这公平么？
一个用户比其他用户运行更多的进程时，怎么办？
调度算法
(1)先来先服务算法：FCFS: First Come, First Served
不公平，平均等待时间较差
（2）短进程优先算法：SPN: Shortest Process Next
SJF: Shortest Job First (短作业优先算法)
SRT: Shortest Remaining Time (短剩余时间优先算法)
不公平，平均周转时间最小
需要精确预测计算时间
可能导致饥饿
（3）最高响应比优先算法
HRRN: Highest Response Ratio Next
基于SPN调度
不可抢占
（4）时间片轮转算法
RR: Round Robin
公平，但是平均等待时间较差
（5）多级反馈队列算法
MFQ: Multilevel Feedback Queues
多种算法的集成
（6）公平共享调度算法
FSS: Fair Share Scheduling
公平是第一要素
先来先服务算法(First Come First Served, FCFS)
依据进程进入就绪状态的先后顺序排列
进程进入等待或结束状态时（进程主动让出PCU），就绪队列中的下一个进程占用CPU
FCFS算法的周转时间：
任务到达顺序：P1,(12) P2(3), P3 (3)
执行时间 0———–12——15———-18周转时间=(12+15+18)/3=15
优点
简单
缺点
平均等待时间波动较大(与队列到达的时间有很大的关系)
短进程可能排在长进程后面
I/O资源和CPU资源的利用率较低
CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也等待
短进程优先算法(SPN)
选择就绪队列中执行时间最短进程占用CPU进入运行状态
就绪队列按预期的执行时间来排序
短剩余时间优先算法(SRT): SPN算法的可抢占改进
短剩余时间优先算法(SPN)具有最优平均周转时间
SPN： P1 P2 P3 P4 P5 P6
时间：0 r1 r2 r3 r4 r5 r6
得到的周转时间：（r1+r2+r3+r4+r5+r6）/6
缺点
可能导致饥饿
连续的短进程流会使长进程无法获得CPU资源
需要预知未来
如何预估下一个CPU计算的持续时间？
简单的解决办法：询问用户
用户欺骗就杀死相应进程
用户不知道怎么办？
用历史的执行时间来预估未来的执行时间
tn——第n次的CPU计算时间
τn+1——第n+1次的CPU计算时间预估
τn+1 = αtn+(1-α) τn，其中 0≤α≤1
τn+1=αtn+(1-α) αtn-1+(1-α)(1-α) αtn-2+…
离最近的衰减系数 a ,次之的为(1-a)^n*(a)
最高响应比优先算法(HRRN)
选择就绪队列中响应比R值最高的进程
Ｒ＝（ｗ+s)/s
w: 等待时间(waiting time)
s: 执行时间(service time)
在短进程优先算法的基础上改进
不可抢占
关注进程的等待时间
防止无限期推迟
时间片轮转算法(RR, Round-Robin)
时间片
分配处理机资源的基本时间单元
算法思路
时间片结束时，按FCFS算法切换到下一个就绪进程
每隔(n – 1)个时间片进程执行一个时间片q(时钟中断)
时间片为20的RR算法示例
示例: 4个进程的执行时间如下
P1 53
P2 8
P3 68
P4 24 
时间片轮转算法中的时间片长度
RR算法开销
额外的上下文切换
时间片太大
等待时间过长
极限情况退化成FCFS
时间片太小
反应迅速，但产生大量上下文切换
大量上下文切换开销影响到系统吞吐量
时间片长度选择目标
选择一个合适的时间片长度
经验规则：维持上下文切换开销处于1%以内 
多级队列调度算法(MQ)
就绪队列被划分成多个独立的子队列
每个队列拥有自己的调度策略
队列间的调度
如：前台–RR、后台–FCFS
固定优先级
先处理前台，然后处理后台
可能导致饥饿
时间片轮转
每个队列都得到一个确定的能够调度其进程的CPU总时间
如：80%CPU时间用于前台，20%CPU时间用于后台
多级反馈队列算法(MLFQ)
进程可在不同队列间移动的多级队列算法
MLFQ算法的特征
CPU密集型进程的优先级下降很快
时间片大小随优先级级别增加而增加
如进程在当前的时间片没有完成，则降到下一个优先级
I/O密集型进程停留在高优先级
公平共享调度(FSS, Fair Share Scheduling)
FSS控制用户对系统资源的访问
一些用户组比其他用户组更重要
保证不重要的组无法垄断资源
未使用的资源按比例分配
没有达到资源使用率目标的组获得更高的优先级