单处理器调度

处理器调度的类型

调度目的：把进程分配到一个或多个处理器上执行（需要满足：响应时间、吞吐率、处理器效率、公平性）

调度类型

• 长程调度：决定加入待执行进程池，也称作业调度，仅仅是将作业调入内存，进程处于就绪态
• 中程调度：决定加入部分或全部位于内存中的进程集合
• 短程调度：决定处理器执行哪个可运行进程，也称进程调度，频度最高
• I/O调度：决定I/O设备处理哪个进程挂起的I/O请求

调度层次

调度本质上属于队列管理，用于在排队中减少延迟并优化性能

长程调度

决定哪个程序加载入系统处理

• 控制系统的并发度
• 越多进程，每个进程执行的时间百分比越小（由于竞争处理器时间）

中程调度

交换功能的一部分，基于管理系统并发度的需求

短程调度

也被称为分派器（dispatcher），执行的最为频繁

导致当前进程阻塞或抢占当前运行进程的事件发生时，调用短程调度

• 时钟中断
• I/O中断
• OS调用
• 信号

调度算法

短程调度准则

• 面向用户：与单个用户或进程感知到的系统行为有关，如交互式系统中的响应时间
• 面向系统：重点是处理器使用的效果和效率，如吞吐量

另一个划分维度：性能

• 与性能相关：响应时间、吞吐量
• 其他：定性的，不宜测量和分析，如可预测性

选择调度策略

决策模式分为非抢占和抢占（OS中断运行中程序、新进程到达、中断发生后一个阻塞态置为就绪态、周期性时间中断）

区分静态/动态优先级：进程创建时优先级就确定的为静态优先级，如FCFS和SPN

FCFS，先来先服务

最简单，严格排队方案；当前正运行的进程停止执行后，选择就绪队列中存在时间最长的进程运行

（非抢占），缺点：短进程可能需要很长时间才能执行

RR，轮转

基于时钟的抢占策略，周期性产生时钟中断，出现中断时，当前正在运行的进程换出到就绪队列，然后基于FCFS选择下一个就绪作业运行（该技术称为时间片，time slicing，每个进程在被抢占前都会给定一片时间）

这里要尤其注意时间片长度的选择：长度很短，短作业会相对比较快地通过系统；长度很长，接近FCFS

改进的RR：VRR，虚拟轮转法：把因为I/O阻塞的进程放到单独的队列，并给予优先选择

SPN，最短进程优先

非抢占策略，下次选择预计处理时间会最短的进程

缺点：更长的进程可能会饥饿，很难预测未来

SRT，最短剩余时间

在SPN中增加了抢占机制，一个时间片结束时，优先选择最短剩余时间的进程

HRRN，最高响应比优先

非抢占，选择有最大响应比的进程，$R=\frac{w+s}{s}$，R为响应比，w为等待处理器的时间，s为预计的服务时间，相当于周转/驻留时间和实际服务时间的比值

偏向短作业时，长进程由于得不到服务，等待的时间增加，R变大，最终在竞争中赢了短进程

同SPN、SRT，这些都需要估计预计的服务时间

feedback，反馈法

如果不能获取各个进程相对长度，不能使用上述SPN、SRT、HRRN

处罚运行时间长的作业，即关注已执行的时间

调度基于抢占原则（按时间片）并使用动态优先级机制：长进程每次被抢占就降级到优先级低的队列中