调度算法 | Computer Science

在计算机学科专业基础综合（408）考研考纲中，进程调度算法是操作系统部分的核心考点，主要包括以下几类，需重点掌握其原理、特点及适用场景：

一、先来先服务调度算法（FCFS，First-Come, First-Served）

原理：按照进程到达就绪队列的先后顺序调度，先到达的进程先获得处理机，直到运行完成或因I/O等原因阻塞才释放处理机。
特点：
- 公平性：按到达顺序处理，无优先级歧视；
- 不利于短作业：长作业可能“饥饿”短作业，平均周转时间较长；
- 属于非抢占式调度（一旦开始运行，除非主动放弃，否则持续执行）。
适用场景：早期批处理系统，或对公平性要求高、作业运行时间差异小的场景。

二、短作业优先调度算法（SJF，Shortest Job First）

原理：优先调度就绪队列中估计运行时间最短的进程，直到完成或阻塞。
分类：
- 非抢占式SJF：一旦进程开始运行，直到完成或阻塞才让出处理机；
- 抢占式SJF（最短剩余时间优先，SRTN，Shortest Remaining Time Next）：若新到达的进程运行时间比当前运行进程的剩余时间更短，则立即抢占处理机。
特点：
- 优点：能有效降低平均周转时间和平均带权周转时间，提高系统吞吐量；
- 缺点：
  - 需预先知道作业的运行时间（实际中难以精确估计）；
  - 对长作业不利，可能导致长作业“饥饿”；
  - 未考虑作业的紧急程度（优先级）。
适用场景：作业运行时间已知的批处理系统。

三、高优先级优先调度算法（HPF，Highest Priority First）

原理：为每个进程分配优先级，就绪队列中优先级最高的进程优先获得处理机。
分类：
- 非抢占式HPF：当前进程运行时，即使有更高优先级进程到达，也需等当前进程完成或阻塞后再调度；
- 抢占式HPF：当更高优先级进程到达时，立即抢占当前处理机，调度新进程运行。
优先级划分：
- 静态优先级：进程创建时确定优先级，运行期间不变（简单但不够灵活）；
- 动态优先级：进程运行期间根据情况调整优先级（如等待时间越长优先级越高，避免饥饿）。
特点：
- 优点：可灵活处理紧急任务；
- 缺点：低优先级进程可能长期“饥饿”（需通过动态优先级缓解）。
适用场景：实时系统（需快速响应高优先级任务）、多任务系统。

四、时间片轮转调度算法（RR，Round-Robin）

原理：为就绪队列中的每个进程分配一个固定的时间片（如10ms），进程运行完一个时间片后，若未完成则被剥夺处理机，排到就绪队列末尾，等待下一次调度。
关键参数：时间片大小（过大会退化为FCFS，过小会导致频繁上下文切换，增加系统开销）。
特点：
- 属于抢占式调度（时间片用完即被抢占）；
- 公平性好，每个进程轮流获得处理机；
- 平均响应时间短，适合交互型系统。
适用场景：分时操作系统（如Unix早期版本、Linux桌面系统）。

五、多级反馈队列调度算法（Multilevel Feedback Queue）

原理：结合了RR和HPF的优点，设置多个优先级不同的就绪队列，各队列时间片大小不同（优先级越高，时间片越小）：
1. 新进程进入最高优先级队列，按RR调度（时间片最小）；
2. 若一个时间片内未完成，进程降级到下一级队列；
3. 低优先级队列时间片更大，按RR调度；
4. 仅当高优先级队列为空时，才调度低优先级队列的进程（避免低优先级进程饥饿）。
特点：
- 动态调整进程优先级和时间片，兼顾短作业（快速完成）、长作业（最终能运行）和交互型作业（响应快）；
- 是“最通用”的调度算法之一，综合性能优。
适用场景：通用操作系统（如Unix、Linux）。

总结（考纲核心要求）

408考研中需重点掌握上述5类算法，尤其注意：

各类算法的调度逻辑（抢占/非抢占、优先级/时间片等）；
性能指标（平均周转时间、带权周转时间、响应时间等）的计算与对比；
适用场景的区分（如分时系统用RR，实时系统用HPF等）。

其中，多级反馈队列算法是考纲明确要求的“综合型算法”，需理解其多级队列设计和反馈机制的细节。

在408计算机学科专业基础综合考试中，除了进程调度算法外，还需掌握以下几类调度算法，这些内容分布在操作系统的不同章节，是高频考点：

一、作业调度算法（高级调度）

作用：从外存作业队列中选择作业调入内存，并为其创建进程。
核心算法：

先来先服务（FCFS）
- 原理：按作业到达顺序调度，非抢占式。
- 缺点：长作业可能导致短作业“饥饿”。
- 适用场景：批处理系统。
短作业优先（SJF）
- 原理：优先调度预计运行时间最短的作业。
- 变种：
  - 非抢占式SJF：作业一旦开始运行，直到完成才释放资源；
  - 抢占式SJF（SRTF）：新到达的短作业可抢占当前作业。
- 优缺点：平均周转时间最短，但需预先知道作业运行时间，且可能导致长作业“饥饿”。
高响应比优先（HRRN）
- 原理：动态计算响应比 ( R = \frac{\text{等待时间} + \text{运行时间}}{\text{运行时间}} )，选择 ( R ) 最高的作业。
- 优势：兼顾短作业优先和长作业公平性，避免“饥饿”。
- 特点：非抢占式，每次调度前重新计算响应比。

二、内存调度算法（中级调度）

作用：将暂时无法运行的进程从内存换出到外存（挂起），腾出空间给更需要的进程。
核心算法：

页框回收算法（PFRA）
- 原理：当内存不足时，选择部分页面换出到磁盘。
- 经典算法：
  - 最佳置换（OPT）：淘汰未来最久不被访问的页面（理论最优但不可实现）；
  - 先进先出（FIFO）：淘汰最早进入内存的页面（可能出现Belady异常）；
  - 最近最久未使用（LRU）：淘汰最久未访问的页面（需硬件支持）；
  - 时钟（Clock）算法：LRU的近似实现，利用引用位优化性能。
动态分区分配算法
- 作用：为进程分配内存空间，解决外部碎片问题。
- 核心算法：
  - 首次适应（First Fit）：从低地址开始查找第一个满足需求的空闲分区；
  - 最佳适应（Best Fit）：选择能满足需求的最小空闲分区（易产生微小碎片）；
  - 最坏适应（Worst Fit）：选择最大空闲分区（减少碎片数量但可能浪费大空间）；
  - 伙伴算法（Buddy System）：按2的幂次方分割内存，仅合并大小相等的“伙伴”分区。

三、磁盘调度算法（I/O调度）

作用：优化磁头移动路径，减少I/O访问时间。
核心算法：

先来先服务（FCFS）
- 原理：按请求到达顺序服务，公平但效率低。
最短寻道时间优先（SSTF）
- 原理：优先服务离当前磁头最近的请求，减少寻道时间。
- 缺点：可能导致“饥饿”（如边缘磁道请求长期被忽略）。
扫描算法（SCAN，电梯算法）
- 原理：磁头固定方向移动（如从内到外），沿途服务所有请求，到达端点后反向。
- 变种：
  - 循环扫描（C-SCAN）：磁头到达端点后立即跳转到另一端，避免端点附近请求延迟；
  - LOOK/C-LOOK：磁头仅移动到该方向最远请求处，减少无效移动。
N步SCAN/C-SCAN
- 原理：将请求队列分成若干子队列，按SCAN/C-SCAN处理每个子队列，减少磁头频繁换向开销。

四、实时调度算法

作用：确保实时任务在截止时间前完成，分为硬实时和软实时。
核心算法：

最早截止时间优先（EDF）
- 原理：按任务截止时间排序，截止时间越早优先级越高。
- 支持抢占：可动态调整任务执行顺序，适用于周期和非周期实时任务。
最低松弛度优先（LLF）
- 原理：计算任务松弛度（松弛度 = 截止时间 - 当前时间 - 剩余执行时间），松弛度最小的任务优先执行。
- 优势：动态反映任务紧急程度，更灵活。
优先级驱动调度（含实时扩展）
- 动态优先级调整：如等待时间越长优先级越高，防止低优先级实时任务“饥饿”。

五、多处理机调度算法

作用：在多核/多CPU系统中分配任务，提升并行性。
核心策略：

对称多处理（SMP）调度
- 负载均衡：将就绪进程均匀分配到各个CPU，避免资源闲置；
- 处理机亲和性：尽量让进程在同一CPU上运行，减少缓存失效。
分布式调度
- 原理：每个CPU独立维护就绪队列，通过全局锁或消息传递协调任务分配。

六、其他相关算法

高响应比优先（HRRN）
- 已包含在作业调度中，但需注意其在进程调度中的变形（如动态优先级调整）。
多级反馈队列调度（MFQ）
- 归类为进程调度，但融合了时间片轮转和优先级调度的思想，是综合型算法。

总结（408考纲核心覆盖）

调度类型	关键算法	常考题型
作业调度	FCFS、SJF、HRRN	周转时间计算、甘特图绘制、算法对比分析
内存调度	FIFO、LRU、Clock、伙伴算法	缺页率计算、内存分配与回收过程分析
磁盘调度	SSTF、SCAN、C-SCAN、LOOK	磁头移动路径模拟、总寻道时间计算
实时调度	EDF、LLF	任务执行顺序判断、截止时间验证
多处理机调度	负载均衡、处理机亲和性	多核系统性能优化策略分析