进程调度策略

一、概述

进程调度是操作系统实现CPU虚拟化的核心功能，旨在通过时分共享（time sharing）让多个进程看似同时运行。调度策略（policy）决定如何分配CPU时间，需平衡性能（如周转时间）和公平性（如响应时间）。

1.1 关键问题

如何开发调度策略？ 需明确工作负载假设、调度指标和优化目标。
如何在无先验知识下调度？ 需通过历史行为预测进程特性，优化周转时间和响应时间。
如何按比例分配CPU？ 需设计机制确保公平分配，同时保持高效。

1.2 调度机制基础

上下文切换：保存当前进程寄存器状态，恢复另一进程状态，实现进程切换。
时钟中断：定期触发，操作系统借此重新获得CPU控制权，支持抢占式调度。
受限直接执行（LDE）：直接运行用户程序，通过用户模式和内核模式限制进程行为，确保控制权。

二、工作负载假设与调度指标

2.1 工作负载假设

调度策略依赖对工作负载的假设，以下为初始简化假设（部分不现实，逐步放宽）：

每个进程运行时间相同。
所有进程同时到达。
进程运行至完成，不中断。
进程仅使用CPU，无I/O。
进程运行时间已知。

现实性分析：

假设1（相同运行时间）和5（已知运行时间）最不现实，实际进程运行时间差异大且不可预测。
假设4忽略I/O，需考虑进程阻塞和重叠调度。
放宽假设后，调度策略需适应动态到达、I/O操作和未知运行时间。

2.2 调度指标

周转时间（Turnaround Time）：
- 定义：T周转时间 = T完成时间 - T到达时间。
- 衡量性能，优化周转时间需尽早完成短进程。
响应时间（Response Time）：
- 定义：T响应时间 = T首次运行 - T到达时间。
- 衡量交互性，优化响应时间需快速调度进程。
公平性：
- 如Jain's Fairness Index，衡量资源分配均衡性。
- 性能与公平性常冲突：优化周转时间可能牺牲公平性，强调公平性可能延长周转时间。

三、基本调度策略

3.1 先进先出（FIFO / FCFS）

原理：按到达顺序运行进程至完成，非抢占式。
优点：
- 简单易实现。
- 在假设1（相同运行时间）和2（同时到达）下表现良好。
缺点：
- 护航效应（Convoy Effect）：长进程阻塞短进程，导致平均周转时间高。
- 示例：进程A（100s）、B（10s）、C（10s），平均周转时间为(100 + 110 + 120) / 3 = 110s。
适用场景：运行时间相近且无I/O的批处理系统。

3.2 最短任务优先（SJF）

原理：优先运行运行时间最短的进程，非抢占式。
优点：
- 在假设1、2下，优化周转时间，理论上最优。
- 示例：A（100s）、B（10s）、C（10s），调度顺序B、C、A，平均周转时间为(10 + 20 + 120) / 3 = 50s。
缺点：
- 需预知运行时间（不现实）。
- 响应时间差，长进程可能长时间等待。
- 晚到短进程需等待当前进程完成，护航效应仍存在。
适用场景：运行时间可预测的批处理系统。

3.3 最短完成时间优先（STCF / PSJF）

原理：SJF的抢占式版本，新进程到达或当前进程剩余时间较长时，抢占运行剩余时间最短的进程。
优点：
- 放宽假设2（允许动态到达），通过抢占解决护航效应。
- 示例：A（100s，t=0到达）、B（10s，t=10到达）、C（10s，t=10到达），调度B、C后继续A，平均周转时间为(100 + (20-10) + (30-10)) / 3 = 50s。
- 在假设3（允许中断）下最优。
缺点：
- 仍需预知运行时间。
- 响应时间不佳，长进程等待时间长。
适用场景：支持抢占的批处理系统。

3.4 轮转（Round-Robin, RR）

原理：按时间片（scheduling quantum）轮流运行就绪进程，时间片为时钟中断周期的倍数。
优点：
- 优化响应时间，进程快速获得CPU。
- 示例：A、B、C各运行5s，1s时间片，平均响应时间为(0 + 1 + 2) / 3 = 1s（SJF为(0 + 5 + 10) / 3 = 5s）。
缺点：
- 周转时间差，因频繁切换延长完成时间。
- 示例：A、B、C各5s，RR平均周转时间为(13 + 14 + 15) / 3 = 14s。
- 时间片长度需权衡：
  - 过短增加上下文切换开销（包括缓存、TLB、分支预测器状态刷新）。
  - 过长降低响应时间。
提示：摊销（Amortization）延长时间片可降低上下文切换成本（如10ms时间片，1ms切换成本占10%；100ms时间片降至1%）。
适用场景：分时系统，强调交互性。

四、结合I/O的调度

4.1 I/O对调度影响

放宽假设4（允许I/O），进程可能因I/O请求（如磁盘读写）阻塞，释放CPU。
重叠（Overlap）：在进程等待I/O时调度其他进程，提高CPU利用率。

4.2 STCF与I/O

方法：将进程的每次CPU突发（burst）视为独立子任务，优先调度最短子任务。
示例：
- 进程A：5次10ms CPU突发，每次后I/O 10ms。
- 进程B：1次50ms CPU突发，无I/O。
- 调度：优先A的10ms子任务，A的I/O期间运行B，实现重叠。
效果：交互进程频繁运行，CPU密集进程利用I/O间隙，优化利用率。
图示：
- 错误调度（A后B）：A运行50ms，B等待，CPU闲置I/O时间。
- 正确调度（A子任务与B交替）：A的I/O期间B运行，CPU持续忙碌。

五、多级反馈队列（MLFQ）

5.1 背景

提出者：Corbato于1962年为CTSS提出，广泛应用于BSD、Solaris、Windows等现代系统。
目标：
- 优化周转时间（类似SJF/STCF）。
- 降低响应时间（类似RR）。
- 无需预知运行时间，通过历史行为动态调整优先级。
关键问题：无先验知识如何调度？

5.2 基本规则

结构：多个优先级队列，高优先级队列优先运行，同一队列内轮转调度。
规则：
1. 若A优先级 > B优先级，运行A。
2. 若A优先级 = B优先级，轮转运行A和B。
3. 新进程进入最高优先级队列。
4. 进程用完某层时间配额（无论是否主动放弃CPU），降至低一级队列。
5. 每隔时间S，将所有进程提升至最高优先级。

5.3 优先级调整

初始尝试：
- 规则4a（旧）：用完时间片，降低优先级。
- 规则4b（旧）：时间片内主动放弃CPU（如I/O），优先级不变。
- 问题：
  - 饥饿（Starvation）：交互进程过多，长进程无法运行。
  - 愚弄调度（Gaming the Scheduler）：进程在时间片末发起无关I/O，保持高优先级，独占CPU。
  - 行为变化：CPU密集进程转为交互型，无法快速获得高优先级。
优化：
- 规则5（优先级提升）：
  - 周期性（时间S）将所有进程提升至最高优先级。
  - 解决饥饿：长进程定期获得CPU。
  - 适应行为变化：CPU密集进程转为交互型时获高优先级。
  - 挑战：设置S值（巫毒常量），过高导致饥饿，过低影响交互进程。
- 规则4（新计时方式）：
  - 记录每层总时间配额，耗尽后降级，防止I/O滥用保持高优先级。
  - 解决愚弄问题：进程无论I/O与否，耗尽配额即降级。

5.4 示例

单一长进程：从最高优先级逐级下降至最低，稳定运行。
长进程+短进程：短进程到达后置于高优先级，快速完成，近似SJF。
交互进程（带I/O）：频繁I/O保持高优先级，快速响应。
优先级提升：长进程周期性提升，防止饥饿。

5.5 调优

队列数：如Solaris TS类默认60层。
时间片：
- 高优先级：短时间片（如10ms），快速切换交互进程。
- 低优先级：长时间片（如40ms），适合CPU密集进程。
提升频率：如每秒一次，平衡饥饿和交互性。
变体：
- FreeBSD：基于CPU使用量公式动态调整优先级，衰减历史使用量。
- Solaris：通过配置表调整优先级、时间片和提升频率。
用户建议：如nice命令，调整进程优先级。

5.6 优点与挑战

优点：
- 无需运行时间先验知识，通过历史学习动态优化。
- 兼顾短进程（低周转时间）、交互进程（低响应时间）和长进程（避免饥饿）。
挑战：
- 调优复杂，需根据工作负载调整队列数、时间片和提升频率。
- 巫毒常量（如S值）需经验设定。
提示：Ousterhout定律避免巫毒常量，建议通过配置文件或自学习优化参数。

六、比例份额调度

6.1 概述

目标：按比例分配CPU时间，确保公平性，而非优化周转时间或响应时间。
代表：
- 彩票调度（Lottery Scheduling）：随机抽取彩票决定运行进程。
- 步长调度（Stride Scheduling）：确定性分配，基于步长值调度。
关键问题：如何设计高效、公平的比例分配机制？

6.2 彩票调度

原理：
- 彩票数（ticket）表示进程的CPU份额，比例为进程彩票数/总彩票数。
- 每时间片随机抽取彩票，持有中奖彩票的进程运行。
示例：
- 进程A（75票）、B（25票），总100票。
- 随机抽取0-99，A持有0-74，B持有75-99，A概率75%，B概率25%。
机制：
- 彩票货币（Ticket Currency）：
  - 用户以本地货币分配彩票，系统兑换为全局彩票。
  - 示例：用户A给A1、A2各500票（A货币），兑换为50全球票；用户B给B1 10票，兑换为100全球票。
- 彩票转让（Ticket Transfer）：
  - 客户端临时转让彩票给服务端，加速服务端执行。
- 彩票通胀（Ticket Inflation）：
  - 信任环境中，进程动态调整彩票数，表达CPU需求。
实现：
- 数据结构：进程列表记录彩票数，总彩票数。
- 算法：随机选择中奖彩票，遍历列表累加彩票数，找到中奖进程。
c int counter = 0; int winner = getrandom(0, totaltickets); node_t *current = head; while (current) { counter += current->tickets; if (counter > winner) break; // 找到中奖进程 current = current->next; }
- 优化：按彩票数降序排序列表，减少遍历时间。
- 优点：
- 简单轻量，随机性避免复杂状态跟踪。
- 动态适应新进程，只需更新总彩票数。
- 随机性避免极端情况（如LRU替换的序列问题）。
- 缺点：
- 短时间运行比例不精确，需长时间接近期望比例。
- 不适合I/O密集场景。
- 彩票分配无明确策略。

6.3 步长调度

原理：
- 每个进程有步长（stride），与彩票数成反比（大数/彩票数）。
- 进程运行后，行程值（pass）增加步长。
- 调度最小行程值进程，运行后更新行程值。
示例：
- A（100票，步长100）、B（50票，步长200）、C（250票，步长40）。
- 初始行程值0，选择A，运行后行程值100；选择B，行程值200；选择C，行程值40。
- 继续选择最小行程值，C运行多次，比例精确为5:2:1（C:A:B）。
伪代码：

c current = remove_min(queue); // 选择最小行程值进程 schedule(current); current->pass += current->stride; insert(queue, current);
优点：
- 确定性分配，每周期精确比例。
- 适合需精确控制的场景。
缺点：
- 需维护全局行程值，新进程加入需合理设置初始值（0可能导致独占）。
- I/O支持较弱。
与彩票调度对比：
- 彩票调度：无全局状态，适应动态进程，短时间比例不准。
- 步长调度：精确控制，需全局状态，新进程处理复杂。

6.4 应用场景

适用：虚拟化数据中心（如VMWare ESX），明确比例分配CPU或内存。
局限：
- 通用操作系统中，I/O复杂性和彩票分配难题限制应用。
- MLFQ等通用调度更适合动态、复杂工作负载。

七、总结与扩展

7.1 调度策略对比

策略	周转时间	响应时间	公平性	适用场景	主要问题
FIFO	较差	较差	高	简单批处理	护航效应
SJF	最优	较差	低	运行时间可预测的批处理	需预知运行时间，响应时间差
STCF	最优	较差	低	抢占式批处理	需预知运行时间
RR	较差	最优	高	分时系统，交互性优先	周转时间差，切换开销
MLFQ	良好	良好	中	通用系统，动态工作负载	调优复杂，巫毒常量
彩票调度	中等	中等	高	虚拟化，明确比例分配	短时间不精确，I/O支持弱
步长调度	中等	中等	高	需精确比例的虚拟化	全局状态管理，I/O支持弱

7.2 设计哲学

性能与公平权衡：SJF/STCF优化性能，RR/MLFQ强调公平和交互性，比例份额调度专注公平分配。
历史学习：MLFQ通过观察进程行为动态调整优先级，解决未知运行时间问题。
随机性与确定性：彩票调度用随机性简化实现，步长调度用确定性确保精确。
重叠与摊销：I/O重叠提高利用率，延长时间片摊销上下文切换成本。
用户建议：通过nice、配置文件或表（如Solaris TS）允许用户干预调度。

7.3 进一步学习

调度优化：
- 研究Linux CFS（Completely Fair Scheduler），结合MLFQ和比例份额思想。
- 探索实时调度（如EDF，Earliest Deadline First）。
性能分析：
- 使用lmbench测量上下文切换和系统调用开销。
- 分析缓存、TLB对调度性能的影响。
源码实现：
- 阅读xv6或Linux内核调度代码，理解MLFQ和上下文切换。
应用场景：
- 研究虚拟化（如VMWare ESX）中比例份额调度的实现。
- 探索云计算中容器调度的动态分配策略。