CPU调度：从就绪队列挑选出一个 进程/线程 作为CPU将要运行的下一个 进程/线程
调度程序：挑选 进程/线程 的内核函数
内核运行调度程序的条件：（满足一条即可）
- 一个进程从running变为wait
- 一个进程被终结了
可分为两种：
- 不可抢占：调度程序必须等待事件结束
- 可以抢占：调度程序在中断被响应后执行。当前进程从running——>ready或者一个进程从wait——>ready，当前进程可以被换出。
1.调度原则
执行模型：程序在CPU突发和I/O中交替
- 每个调度决定在下一个CPU突发时将哪个工作交给CPU
- 在时间分片机制下，线程可能在结束当前CPU突发前被迫放弃CPU
评价指标：
- CPU利用率
- 吞吐量（OS的计算带宽）
- 周转时间
- 等待时间
- 响应时间（OS的计算延迟）
什么是更快：传输文件的高带宽？低延迟？
目标：1.减少响应时间；2.减少平均响应时间波动；3.增加吞吐量——减少开销；系统资源的高效利用；
公平？
2.调度算法
1.先来先服务/FCFS
FIFO队列的规定：如果进程在执行中阻塞，队列中的下一个会得到CPU
优点：
- 简单
缺点：
- 平均等待时间波动较大，
- 费时少的任务可能会排到费事长的任务之后
- 可能导致I/O和CPU之间的重叠现象——CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也在等待
2.短 任务/进程 优先
可以是抢占，也可以是非抢占式的
抢占：Shortest-Remaining-Time/SRT/最短剩余时间
优点：
- 最短平均等待时间（周转时间）
缺点：
- 可能会导致饥饿——连续的短任务流会使长任务饥饿
- 需要预知未来
[latex] \tau_{n+1} = \alpha t_{n} + (1-\alpha)\tau_{n}, (0 \leq \alpha \leq 1)[/latex]
[latex] \tau_{n+1} [/latex]: predicted duration of the [latex] (n+1)^{th}[/latex] CPU burst
[latex] t_{n} [/latex]: duration of the [latex] n^{th}[/latex] CPU burst
3.最高响应比优先
响应比： [latex] R = \frac{w+s}{s} [/latex]
w: waiting time
s: service time（执行时间）
- 不可抢占
- 关注进程等待了多久
- 防止无限期延迟
4.轮询调度/Round Robin
RR花销：额外的上下文切换
时间量子太大：等待时间长；极限情况下退化为FCFS
时间片太小：反映迅速；吞吐量由于大量的上下文切换开销受到影响
目标：选择一个合适的时间量子
经验规则：维持上下文切换开销处于1%内
5.多级反馈队列
- 就绪队列被划分为独立的队列（例如：前台（交互），后台（批处理））
- 每个队列都拥有自己的调度策略（例如：前台（RR），后台（FCFS））
- 调度必须在队列间进行
· 固定优先级（先处理前台，后处理后台，可能会导致饥饿）
· 时间切片：每个队列都得到一个确定的能够调度其进程的CPU的总时间 - 一个进程可以在不同的队列间移动
· 时间量子大小随着优先级增加而增加
· 若任务没有在当前的时间量子中完成，则降到下一优先级
优点：CPU密集型任务优先级下降很快；I/O密集型停留在高优先级
6.公平共享调度/Fair Share Scheduling
在用户级别实现公平调度
优先级反转
可以发生在任何基于优先级的可抢占的调度中
当系统内的环境强制使高优先级任务等待低优先级的任务
Solutions：
- 低优先级任务继承高优先级任务的优先级，依赖于它们共享的资源
- 优先级天花板：“资源”的优先级 和 “可锁定改资源的任务中优先级最高的任务”的优先级相同。持有最高优先级上限信息量锁的任务，会继承被该锁所阻塞的任务的优先级。
3.实时调度
RTOS：
- 强/硬：需要在保证的时间内完成重要任务，必须完成
- 软/弱：要求重要的进程优先级更高，尽量完成，非必须
任务：工作单元。例如：一次计算，一次文件读取，一次信息传递
静态优先级调度——RM速率单调调度
- 最佳静态优先级调度
- 周期越短，优先级越高
最佳动态优先级调度——EDF/Earliest Deadline First/最早期限调度
- Deadline越早，优先级越高
4.多处理调度/多处理器调度
load balance
Comments | NOTHING