沃以的小站

Appearance

02-3 进程调度 ​

1. 调度概述 ​

1.1 调度的原因 ​

合理地处理计算机软硬件资源，提高系统资源利用率（如 CPU 利用率）和系统吞吐量，同时保证进程的响应时间和公平性。

1.2 调度的层次 ​

操作系统中的调度分为多个层次，各层负责不同粒度的资源分配：

调度层次功能描述发生频率
作业调度 (Job Scheduling)从后备队列中选择作业调入内存，为其创建进程。决定“哪些作业可以进入系统”。低
内存调度 (Memory Scheduling / 中级调度)将暂时不能运行的进程换出到外存（挂起），或从外存换入内存。用于解决内存不足问题。中等
进程调度 (Process Scheduling / 短程调度)从就绪队列中选择一个进程，分配 CPU 时间片。决定“哪个进程当前运行”。高
线程调度 (Thread Scheduling)在多线程环境中，从线程就绪队列中选择一个线程执行。高

注：在现代操作系统中，“进程调度”通常指短程调度，是本章的核心内容。

2. 调度方式 ​

根据是否允许中断当前正在运行的进程，调度方式分为两类：

调度方式定义特点适用场景
非剥夺式 (Non-preemptive)一旦进程获得 CPU，它将一直运行直到完成或主动放弃（如等待 I/O）。即使有更高优先级的进程到来，也不会被抢占。实现简单，开销小；但响应性差，可能导致长进程阻塞短进程。批处理系统、早期操作系统
剥夺式 (Preemptive)当有更高优先级或更紧急的进程进入就绪队列时，可以立即中断当前运行的进程，将 CPU 分配给新进程。响应性好，能保证重要任务及时执行；但实现复杂，需要保存/恢复上下文，开销较大。交互式系统、实时系统

3. 主要调度算法 ​

3.1 先来先服务 (First-Come, First-Served, FCFS) ​

  • 原理：按照进程到达就绪队列的先后顺序进行调度。
  • 优点：实现简单，公平。
  • 缺点：
    • 平均等待时间长。
    • 对短进程不公平（“护航效应”：长进程后跟随的短进程需长时间等待）。
    • 不利于 I/O 密集型进程。
  • 调度方式：非剥夺式。

3.2 短作业优先 (Shortest Job First, SJF) ​

  • 原理：总是选择预计运行时间最短的进程优先执行。
  • 优点：理论上可使平均等待时间最小化。
  • 缺点：
    • 需要预知进程的运行时间，实际中难以准确估计。
    • 可能导致长作业“饥饿”（Starvation）。
  • 调度方式：可为非剥夺式或剥夺式（SJF 的剥夺式版本称为 最短剩余时间优先 SRTF）。
  • SRTF (Shortest Remaining Time First)：如果新到达的进程比当前运行进程的剩余时间还短，则抢占 CPU。

3.3 优先级调度 (Priority Scheduling) ​

  • 原理：为每个进程赋予一个优先级，调度器总是选择优先级最高的进程运行。
  • 优先级类型：
    • 静态优先级：进程创建时确定，运行期间不变。
    • 动态优先级：根据进程行为（如等待时间、I/O 使用情况）动态调整。
  • 优点：可以区分任务的重要性。
  • 缺点：
    • 低优先级进程可能长期得不到调度（饥饿）。
    • 优先级设置不当会导致系统性能下降。
  • 调度方式：可为非剥夺式或剥夺式。
  • 防止饥饿：引入“老化 (Aging)”机制，即随等待时间增长，逐步提升进程优先级。

3.4 高响应比优先 (Highest Response Ratio Next, HRRN) ​

HRRN（高响应比优先）调度算法的核心是计算每个就绪进程的“响应比”，然后选择响应比最高的进程执行。下面以一个具体例子说明其计算步骤与调度过程。

响应比公式 ​

[ \text{响应比} = \frac{\text{等待时间} + \text{服务时间}}{\text{服务时间}} = 1 + \frac{\text{等待时间}}{\text{服务时间}} ]

  • 等待时间 = 当前时刻 - 到达时刻（仅对已在就绪队列中的进程）
  • 服务时间 = 进程总执行时间（必须已知，HRRN 仍需预知服务时间！⚠️注意：你原文说“无需预知”是常见误解，实际仍需服务时间）
  • 调度时刻：仅当当前运行进程结束时，才触发新调度（因为 HRRN 是非剥夺式）

示例：计算 HRRN 调度过程 ​

进程到达时刻服务时间（执行时间）
P106
P228
P342
P454

调度规则：非剥夺式，每次一个进程完成后，重新计算所有已到达且未完成进程的响应比，选最大者。

步骤 1：t = 0 ​

  • 只有 P1 到达 → 执行 P1（无选择）

  • P1 运行至 t = 6 结束

步骤 2：t = 6（P1 完成，触发调度） ​

此时已到达但未运行的进程：P2 (t=2), P3 (t=4), P4 (t=5)

计算各进程等待时间和响应比：

  • P2: 等待时间 = 6 - 2 = 4 → 响应比 = (4 + 8) / 8 = 12/8 = 1.5
  • P3: 等待时间 = 6 - 4 = 2 → 响应比 = (2 + 2) / 2 = 4/2 = 2.0
  • P4: 等待时间 = 6 - 5 = 1 → 响应比 = (1 + 4) / 4 = 5/4 = 1.25

✅ 选择 P3（响应比最高 = 2.0） → P3 从 t=6 执行到 t=8 结束

步骤 3：t = 8（P3 完成，再次调度） ​

剩余进程：P2, P4

  • P2: 等待时间 = 8 - 2 = 6 → 响应比 = (6 + 8)/8 = 14/8 = 1.75
  • P4: 等待时间 = 8 - 5 = 3 → 响应比 = (3 + 4)/4 = 7/4 = 1.75

⚠️ 响应比相同！通常按先来先服务或进程编号处理。假设选 P2（先到达） → P2 从 t=8 执行到 t=16 结束

步骤 4：t = 16 ​

只剩 P4：

  • P4 等待时间 = 16 - 5 = 11 → 响应比 = (11 + 4)/4 = 15/4 = 3.75（但只剩它了） → P4 执行，t=16 到 t=20 结束

📊 调度结果总结 ​

进程到达服务开始完成等待（开始-到达）周转（完成-到达）
P1060606
P3426824
P228816614
P45416201115

3.5 时间片轮转 (Round Robin, RR) ​

  • 原理：为每个进程分配一个固定长度的时间片（Time Quantum）。当时间片用完，进程被剥夺 CPU，放入就绪队列末尾，等待下一轮调度。
  • 优点：
    • 公平性好，每个进程都能获得 CPU 时间。
    • 响应性好，适合交互式系统。
  • 缺点：
    • 如果时间片过大，退化为 FCFS；过小则上下文切换开销大。
    • 对长进程不够友好，周转时间可能较长。
  • 调度方式：剥夺式。
  • 关键参数：时间片大小的选择至关重要，需在响应性和开销间权衡。

3.6 多级反馈队列调度 (Multilevel Feedback Queue, MLFQ) ​

  • 设计思想：结合了时间片轮转和优先级调度的优点，是一种自适应调度算法。其核心是“试探”：通过观察进程的行为（CPU 使用、I/O 等待）自动将其归类到不同的队列中。
  • 典型配置：
    • 设置多个就绪队列，优先级从高到低排列。
    • 每个队列拥有不同的时间片大小（高优先级队列时间片小，低优先级队列时间片大）。
    • 新进程首先进入最高优先级队列。
  • 调度规则：
    1. 新进程进入最高优先级队列。
    2. CPU 总是优先调度最高优先级非空队列中的进程。
    3. 进程在时间片内完成：结束。
    4. 进程在时间片内未完成：降级到下一级队列。
    5. 进程因 I/O 等待而主动放弃 CPU：返回原队列（不降级），以鼓励 I/O 密集型进程。
    6. 老化机制 (Aging)：为防止低优先级队列中的进程饥饿，系统会定期将等待时间过长的进程提升到更高优先级队列。

注意

当一个正在运行的进程被更高优先级进程（例如新到达的进程进入高优先级队列）抢占时，该被中断的进程会保持在其当前所在的队列中，并通常被放回该队列的末尾（或保留其剩余时间片），等待下一次调度。它不会降级，也不会回到曾经待过的更高优先级队列。

  • 优点：
    • 自适应性强，能有效区分交互式进程和批处理进程。
    • 交互式进程（频繁 I/O）能保持在高优先级队列，获得快速响应。
    • 长作业最终也能得到执行（通过老化机制）。
  • 缺点：实现复杂，参数（队列数、时间片大小、老化策略）配置困难。
  • 调度方式：剥夺式。

平均带权周转时间 = （进程i使用的总时间 / 进程i的服务时间） 的平均值= [ta/(ta+tw)+....+tc]/n

4. 关键概念与对比 ​

4.1 饥饿 (Starvation) ​

一个就绪的进程由于调度策略的原因，长时间得不到 CPU 时间片，从而无法向前推进的现象。

  • 易发生场景：
    • 纯 SJF/SRTF：持续有短作业到达，长作业永远被延迟。
    • 优先级调度：持续有高优先级作业到达，低优先级作业永远得不到执行。
    • MLFQ：若无老化机制，持续有高优先级作业到达，低优先级队列中的作业会饥饿。
  • 解决方案：
    • 老化 (Aging)：随着时间推移，增加进程的优先级。
    • 最大等待时间限制：强制将等待过久的进程提升优先级。

4.2 各调度算法对比总结 ​

算法是否需要预知时间是否支持抢占是否易导致饥饿主要优点主要缺点适用场景
FCFS否通常否否简单、公平平均等待时间长教学、简单系统
SJF是可选是平均等待时间理论最优需预知时间、易致长作业饥饿理论分析、批处理（带老化）
SRTF是是是最优响应性（对短作业）需预知时间、易致长作业饥饿与 SJF 类似
优先级调度否可选是可区分任务重要性易致低优先级饥饿实时系统、通用系统（带老化）
HRRN否否否公平兼顾长短作业计算开销大理论分析、特定系统
RR否是否公平、响应性好上下文切换开销、长进程周转时间长交互式系统、分时系统
MLFQ否是否（配老化机制）自适应、兼顾各类进程实现复杂、参数难调现代通用操作系统（Linux CFS）

5. 现代操作系统应用 ​

  • Linux (CFS - Completely Fair Scheduler)：
    • 核心思想是“完全公平”，目标是让每个进程获得相等的 CPU 时间份额。
    • 使用红黑树管理就绪进程，按虚拟运行时间排序。
    • 本质是 MLFQ 的高级变体，具有完善的防饥饿机制（老化）。
  • Windows：采用基于优先级的多级反馈队列模型，支持实时和分时任务。
  • 实时操作系统 (RTOS)：常采用固定优先级的剥夺式调度，以保证硬实时任务的截止时间。

6. 核心要点总结 ​

  1. 调度层次：理解作业调度、内存调度、进程调度、线程调度的区别与联系。
  2. 调度方式：掌握剥夺式与非剥夺式的定义、特点及适用场景。
  3. 核心算法：熟练掌握 FCFS, SJF/SRTF, 优先级调度, HRRN, RR, MLFQ 的工作原理、优缺点及调度方式。
  4. 饥饿问题：理解饥饿的成因及解决方案（特别是老化机制）。
  5. MLFQ：重点掌握其多级队列、时间片递增、降级/不降级规则、老化机制等核心特性。
  6. 权衡取舍：任何调度算法都是在效率 (Throughput)、响应性 (Responsiveness)、公平性 (Fairness) 和实现复杂度之间进行权衡。

参考阅读：操作系统调度的机制

上次更新于: