CPU调度的基本概念
CPU会按一定调度算法从就绪队列中选择一个进程，把CPU的使用权交给被选中的进程，如果没有就绪进程，系统会安排一个系统空闲进程或idle进程
何时调度
发生事件、当前进程暂停运行、硬件机制相应、操作系统处理事件、结束处理、就绪队列有调整、调度算法选择进程、运行该进程
典型事件：
- 创建、唤醒、退出等进程控制操作
- 进程等待I/O，I/O中断
- 时钟中断（时间片用完，计时器到时）
- 出现abort异常
可总结如下：
- 进程终止（正常或发生错误）
- 新进程创建（变为就绪态）
- 等待进程变成就绪
- 运行进程变成就绪
- 运行进程变成阻塞
调度过程（进程切换）
进程切换是让一个进程让出处理器，让另一个进程占用处理器，包括对原来进程各种状态的保存和对新进程各种状态的恢复
主要包括两部分工作：
- 切换全局页目录以加载一个新的地址空间
- 切换内核栈和硬件上下文
具体步骤：
- 保存进程A的上下文环境（程序计数器、程序状态字、其他寄存器）
- 更新A的PCB（新状态和其他信息）
- 把进程A移至合适队列（就绪，阻塞，···）
- 把进程B的状态设置为运行态
- 从进程B的PCB中恢复上下文（程序计数器、程序状态字、其他寄存器）
上下文切换的开销：
- 保存和恢复寄存器
- 切换地址空间（相关指令可能比较昂贵）
- 缓存和缓冲失效（高速缓存、缓冲区缓存、TLB）
调度算法
算法衡量指标：
- 吞吐量（Throughput）：单位时间完成的进程数目
- 周转时间（Turnaround Time, TT）：进程从提出请求到运行完成的时间
- 响应时间（Response Time，RT）：从提出请求到第一次回应的时间
- CPU利用率（CPU Utilization）：CPU做有效工作的时间比例
- 等待时间（Waiting Time）：进程在就绪队列中等待的时间
相关概念：
- 进程优先级
- 抢占式（Preemptive）与不可抢占式（Non-preemptive）
- I/O密集型（I/O bound）与CPU密集型（CPU bound）
- 时间片（Time slice， Quantum）
各种调度算法：
| 调度算法 | 英文 | 占用CPU方式 | 吞吐量 | 响应时间 | 开销 | 对进程的影响 | 饥饿问题 |
| ------------- | ------------- | ----- | -------- | ------ | --- | --- | --- | --- |
| 先来先服务 | FCFS | 非抢占 | 不强调 | 当进程执行时间差别很大时，可能很慢 | 最小 | 对短进程不利，对I/O型进程不利 | 无 |
| 时间片轮转 | Round Robin,RR | 抢占（时间片用完） | 若时间片小，吞吐量会很低 | 为短进程提供好的响应时间 | 最小 | 公平对待 | 无 |
| 短作业优先 | SJF | 非抢占 | 高 | 为短进程提供好的响应时间 | 可能较大 | 对长进程不利 | 可能 |
| 最短剩余时间优先 | SRTN | 抢占（到达时） | 高 | 提供好的响应时间 | 可能较大 | 对长进程不利 | 可能 |
| 最高响应比优先 | HRRN | 非抢占 | 高 | 提供好的响应时间 | 可能较大 | 很好的平衡 | 无 |
| 多级反馈队列 | Multilevel Feedback | 抢占（时间片用完） | 不强调 | 不强调 | 可能较大 | 对I/O型进程有利 | 可能 |
多处理器调度：
- 需要决定在哪一个CPU上执行
- 需要考虑进程在多个CPU之间迁移的开销（高速缓存失效，TLB失效），尽可能使CPU总在同一个进程上执行
- 要考虑负载均衡问题
具体实例
多级反馈队列调度算法（BSD 5.3）
- 设置多个就绪队列，第一级队列优先级最高
- 给不同就绪队列中的进程分配不同长度的时间片，随着优先级的降低逐渐增大
- 当第一级队列为空时，在第二级队列调度，以此类推
- 各级队列按照时间片轮转方式进行调度
- 当一个新创建进程就绪后，进入第一级队列
- 如果进程因为用完时间片而放弃CPU，则进入下一级就绪队列
- 如果进程因为阻塞而放弃CPU，则进入相应的等待队列，等待事件发生后，该进程回到原来一级就绪队列末尾（或队首）
基于优先级的抢占式多任务调度（Windows）
调度过程：
- 调度单位是线程
- 采用基于优先级的抢占式调度，结合时间配额的调整
- 就绪线程按优先级进入相应队列
- 系统总是选择优先级最高的就绪线程运行
- 同一优先级的各线程按时间片轮转进行调度
- 多CPU系统中允许多个线程并行运行
引发线程调度的条件：
- 进程终止（正常或发生错误）
- 新进程创建（变为就绪态）
- 等待进程变成就绪
- 运行进程变成就绪
- 运行进程变成阻塞
- 一个线程的优先级改变了
- 一个线程改变了它的亲和处理机集合
32个线程优先级：
- 实时优先级（16-31)不改变其优先级
- 可变优先级（1-15）其优先级可在一定范围内升高或降低
- 系统线程（0）用于对系统中空闲物理页面清零（零页线程）
调度策略：
- 主动切换：转到阻塞态
- 抢占：回到相应优先级的就绪队列队首，如果被抢占线程处于实时优先级，则重置为完整的时间配额，如果是可变优先级，则时间配额不变（得到剩余时间配额）
- 时间配额用完：如果线程的优先级没有降低，则回到原来就绪队列末尾（可能继续运行），如果优先级降低了，则选择更高优先级的线程运行。
线程优先级的提升：
- I/O操作完成
- 信号量或事件等待结束
- 前台进程中的线程完成一个等待操作
- 由于窗口活动而唤醒窗口线程
- 线程处于就绪态超过了一定时间还没有运行（饥饿现象
