调度

操作系统

处理机调度概念

进程切换：CPU资源当前占用着切换（保存当前CPU状态恢复到下一进程上下文）
处理机调度：从就绪队列挑选下一个占用CPU运行的进程，从多个可用CPU中挑选就绪进程可使用的CPU资源。
调度程序：挑选就绪进程的内核函数
调度时机：条件：运行态-->等待态，进程终结，非抢占（主动放弃CPU），抢占（时间片占完，等待-->就绪）

调度准则

处理机资源使用模式：进程在CPU计算和I/O操作间交替。
CPU使用率：忙状态时间百分比；
吞吐量：单位时间内完成的进程数目；
周转时间：从初始化到结束的总时间；
等待时间：过程在就绪队列的总时间；
相应时间：从提交请求到产生响应。

调度方法：
- 高吞吐量
增加吞吐量：减少开销（系统开销、上下文切换），系统资源的高效利用（CPU、I/O设备）
减少等待时间
保证吞吐量不受用户交互影响
- 低响应延迟
减少响应时间、减少平均响应时间波动

公平性：CPU时间，等待时间

调度算法

先来先服务FCFS

就绪队列先后顺序（简单、平均等待时间波动较大，I/O资源如和CPU资源利用率低）

短进程优先（预期执行时间最短）

SPN：短进程优先
SJF：短作用优先算法
SRT：短剩余时间优先算法（可抢占），可能出现长进程无法获得CPU（饥饿）
预知未来：询问用户，用历史预知未来 Tn+1=αtn+(1-α)Tn

最高响应比优先调度算法HRRN

R=(W+S)/S W等待，S执行
不可抢占，关注等待时间，防止无限期推迟

时间片轮转RR

时间片q结束后按FCFS切换下一进程，时间片长度选择10ms左右，维持上下文切换开销处于1%以内。
开销：额外的上下文切换。

多级反馈队列MLFQ

• 多级队列调度算法MQ：就绪队列划分为若干子队列，每个队列有自己的策略，队列间的调度
• 多级反馈队列MLFQ：进程在不同队列间移动的多级队列算法
  时间片对优先级增肌，时间片抢占
  CPU密集型进程优先级下降，I/O密集型进程优先级升高
• 公平共享调度算法 FSS
  控制用户对系统资源的访问

实时调度和多处理器调度

实时调度

实时调度：时间&功能，时间约束及时性，可预测性
任务：资源，定时参数
周期实时任务：有规律地重复，周期P，执行时间e，使用率U=e/p
硬时限：最坏满足
软时限：尽量保证满足

可调度性：静态优先级调度、动态优先级调度

算法：
速率单调调度算法：周期安排优先级，周期短优先级高
最早截止时间优先：截止时间越早优先级越高

多处理器调度

多处理机组成一个多处理机系统，处理机间负载共享
对称多处理器SMP调度：
截止时间越早，优先级越高，每个处理器运行自己的调度程序；
调度程序对共享资源访问需进行同步。

静态进程分配：调度开销小，忙用不均；
动态进程分配：共享一个队列，负载均衡，调度开销。

优先级反置

高优先级进程长时间等待低优先级：基于优先级的可抢占调度算法
优先级继承：低优先级进程继承申请高优先级的优先级（占用资源阻塞）
优先级天花板：占用资源进程优先级和所有可能申请资源的进程的最高优先级相同（谁先拿到资源谁先用）