# 处理器调度

# 1. 调度层次

# 1.1 高级调度

决定了被允许进入系统参与CPU的竞争的作业

高级调度决定多道程序的道数

# 1.1.1 批处理系统

• 何时从后备作业队列创建新进程
• 选择哪些作业进入主存，使其成为进程

# 1.1.2 时分系统

• 所有授权用户都被准入，直至系统饱和

# 1.2 中级程调度

根据主存状态决定主存中所能容纳的进程数目。当主存资源紧缺时，决定将哪些进程交换出内存；而当主存资源空闲时，选择将哪些进程交换回内存。

# 1.3 低级调度

决定将就绪队列中的哪个进程/内核级线程分配处理器资源，使其能占用CPU执行。

短程调度的执行时刻

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

# 2. 调度算法

# 2.1 调度算法的评价指标

• 吞吐率 (单位时间完成的进程数)
• 响应时间 (从请求提交到开始接受到响应的时间)
• 处理器利用率 ($CPU利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲时间}$)
• 周转时间 (进程从提交到结束的时间，包括执行时间和等待时间)
• 截止时间 (进程必须在给定截止时间前完成，适用于实时任务)
• 公平性：确保每个进程过的合理的 CPU 份额和其他资源分配，避免出现进程饿死

# 2.2 调度策略

1. 抢占式

• 系统可以根据剥夺原则剥夺正在运行的进程 / 线程的处理器资源
  剥夺原则:
  • 高优先级进程 / 线程剥夺低优先级进程 / 线程
  • 当前运行进程 / 线程的时间片用完

2. 非抢占式

• 进程 / 线程开始运行后不再让出处理器，除非进程 / 线程结束或者出现 I/O 操作

# 2.2.1 先来先服务 (First Come First Served ：FCFS)

每个进程就绪时，加入就绪队列。当前进程停止执行时，选择在就绪队列中时间最长的进程执行。

优点

• 非抢占式调度算法，易于实现
• 适用于作业调度和进程调度

缺点

• 效率低
• 不利于短作业而优待长作业
• 不利于 I/O 繁忙作业而有利于 CPU 繁忙作业

# 2.2.2 最短作业优先 (Shortest Job First ：SJF)

机制

• 当前进程停止执行时，选择预计所需的 CPU 运行时间最小的进程执行
• 非抢占式

优点

• 有利于短作业
• 易于实现

缺点

• 无法准确获知进程所需的 CPU 运行时间
• 忽视作业的等待时间，有可能造成长作业饿死
• 缺乏抢占机制，对分时、实时处理依然不理想

# 2.2.3 最短剩余时间优先 (Shortest Remaining Time First ：SRTF)

机制

• 调度器总是选择具有最短期望剩余运行时间的进程运行；
• 当一个新进程加入就绪队列时，它可能具有比当前运行进程更短的剩余运行时间，此时，调度器将让该就绪进程抢占当前运行的进程。
• 可以看做抢占式的 SJF

优点

• 有利于短作业
• 实现额外代价低

缺点

• 必须估计进程的处理时间
• 有可能造成长作业饿死
  

# 2.2.4 最高响应比优先 (Highest Response Ratio First：HRRF)

$R=1+\frac{w}{s} R:响应比 w:等待处理器时间 s:服务时间$
当前运行进程结束或阻塞后，选择响应比 R 值最大的进程执行

• 非抢占式

优点

• 考虑了进程的老化，有利于短进程 (s 小，R 值大)；同时避免了长进程的饿死 (等待时间加长会使 R 增加)

缺点

• 需要估算进程的服务时间
  

# 2.2.5 优先级调度

优先级调度算法根据确定的优先级来选取进程 / 线程总是选取就绪队列中优先级最高者投入运行

系统可以采用非剥夺式和剥夺式
规定优先级的方法

• 用户提出优先级
• 系统提出优先级

优先级确定分为静态和动态
静态：优先级在生命周期内不再改变 -> 饥饿
动态：随着占有 CPU 时间增加，逐渐降低优先级；随着就绪队列中等待 CPU 的时间增加，逐渐提高优先级。

# 2.2.6 轮转调度 (Round Robin：RR)

机制

• 将时间划分成定长的时间片，当时间片完成后，产生时钟中断。
• 当时钟中断发生后，当前运行进程被放到就绪队列，按 FCFS 的原则选取下一个就绪进程执行。
• 抢占式

优点

• 克服了 FCFS 中短作业可能会等待很长时间的问题
• 有利于多用户、交互型进程

缺点

• 增加了切换的额外开销
• 对 I/O 密集型和 CPU 密集型作业一视同仁，优待了 CPU 密集型作业

# 2.2.7 多级反馈队列调度 (Multi-Level Feedback Queue：MLFQ)

机制

• MLFQ 通过进程已经被服务的时间来预测进程的总服务时间
• MLFQ 通过惩罚已经在处理器上运行时间很长的进程来达到优待短作业的效果
• 系统维持一个动态优先级队列 RQ0, RQ1, RQ2...
• 当进程首次进入系统，置于队列 RQ0，当其运行时间片到并返回就绪队列时，被置于 RQ1。随后每次由于时间片到被抢占，它将被置于下一级就绪队列
• 处理器每次先从第一个队列中选取执行执行者，每个队列内部采用 FCFS 的机制调度。只有未选到时才从较低一级的就绪队列中选取，仅当前面所有队列为空时才会运行最后一个就绪队列中的进程 / 线程。
• 当进入最低优先级队列后，进程不能再进入更低优先级的队列，而是采用 Round Robin 的方式呆在该队列中，直至完成服务。

优点

• 无需预先估算进程的运行时间
• 新进入系统的短进程会得到优待

缺点

• 长进程可能会饿死

# 2.2.8 实时调度算法

硬实时

• 必须满足时间限制

软实时

• 偶尔超过时间限制是可以的

响应事件分类

• 周期性事件
• 非周期性事件

# 3. 多处理器调度

# 3.1 调度算法

1. 负载共享调度算法
2. 群调度算法
3. 专用处理器调度算法