考点频率：★★★★★（必考，常结合计算题考查）
难度：⭐⭐
建议：掌握各算法的核心思想、特点、优缺点，能计算平均周转时间
1️⃣ 为什么需要进程调度算法？
当多个进程同时处于就绪状态时，操作系统需要决定让哪个进程先占用CPU。这个决策规则就是进程调度算法。
简单说就是：CPU就一个，进程一大堆，先让谁上？
软考中常考查四种经典调度算法：FCFS、SJF、优先级调度、时间片轮转。要求能计算平均周转时间，理解各自的适用场景。
2️⃣ 先来先服务（FCFS）
2.1 核心思想
按照进程进入就绪队列的先后顺序分配CPU，先请求的先服务。与日常生活中的排队类似，公平性极强。
2.2 优点
- 实现最简单
- 公平
2.3 缺点
- 长作业会阻塞后面的短作业（“ convoy effect”，护航效应），导致平均等待时间较长
- 对短作业不友好，用户体验差
2.4 示例
进程到达时间均为0，服务时间如下：
- P1: 10ms, P2: 2ms, P3: 3ms
执行顺序：P1 → P2 → P3
- 完成时间：P1=10, P2=12, P3=15
- 平均周转时间 = (10+12+15)/3 ≈ 12.33ms
2.5 软考提示
FCFS属于非抢占式算法，只要进程获得CPU，就会一直运行到结束或主动阻塞。
3️⃣ 短作业优先（SJF）
3.1 核心思想
选择预计运行时间最短的进程先执行。
3.2 优点
- 平均等待时间最小（理论最优）
- 对短作业友好
3.3 缺点
- 需要预知进程的运行时间（实际很难准确预估）
- 可能导致长作业饥饿（长作业永远排不上）
3.4 两种变体
- 非抢占式 SJF：进程一旦获得CPU，运行完才能让出。对应示例顺序：P2(2ms)→P3(3ms)→P1(10ms)。
- 抢占式 SJF（又称 SRTN，最短剩余时间优先）：若新到达的进程剩余时间比当前进程的剩余时间更短，则立即抢占CPU。实际系统中更常用。
3.5 示例（非抢占式）
进程到达时间均为0，服务时间同上：P1:10, P2:2, P3:3
执行顺序：P2 → P3 → P1
平均周转时间 = (2+5+15)/3 ≈ 7.33ms < 12.33ms，性能优于FCFS。
4️⃣ 优先级调度
4.1 核心思想
为每个进程分配一个优先级，CPU总是选择优先级最高的进程运行。
4.2 优先级的确定
- 静态优先级：创建时固定（如系统进程 > 用户进程）
- 动态优先级：运行过程中动态调整（如等待时间越长，优先级越高，防止饥饿）
4.3 两种变体
- 非抢占式：高优先级进程来了，也要等当前进程运行完
- 抢占式：高优先级进程一来，立即抢占CPU
4.4 缺点
- 低优先级进程可能饥饿（特别是静态优先级，低优先级可能永远等不到）
4.5 实际系统
现代操作系统通常采用动态优先级，兼顾I/O型和CPU型进程，防止低优先级任务饿死。
5️⃣ 时间片轮转（RR，Round Robin）
5.1 核心思想
将CPU时间划分为固定大小的时间片（如10ms），按顺序分配给就绪队列中的每个进程。进程用完时间片后，无论是否执行完，都必须让出CPU，回到就绪队列末尾重新排队。
5.2 优点
- 响应时间短，所有用户都能在较短时间内得到响应
- 公平，适合分时操作系统
5.3 缺点
- 时间片太小：上下文切换频繁，系统开销大
- 时间片太大：退化为FCFS，响应变慢
5.4 时间片大小的权衡
- 通常设为10ms ~ 100ms
- 一般为数毫秒到数十毫秒，大于上下文切换时间，保证切换开销占比可控
6️⃣ 四种算法对比表
| 算法 | 调度方式 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| FCFS | 非抢占 | 简单公平 | 长作业阻塞短作业 | 批处理系统 |
| SJF | 非抢占/抢占 | 平均等待时间最短 | 难以预估时间，可能饥饿 | 批处理系统（需预估时间） |
| 优先级 | 非抢占/抢占 | 可区分重要性 | 低优先级可能饥饿 | 实时/分时系统 |
| 时间片轮转 | 抢占 | 响应快，公平 | 切换开销 | 分时系统 |
SJF的平均等待时间最短是理论结论，但实际中无法准确预知运行时间，因此常用近似方案（如基于历史统计）。
7️⃣ 经典例题
例题1：某单CPU系统，三个进程P1、P2、P3同时到达，运行时间分别为 24ms、3ms、4ms。若采用非抢占式短作业优先调度，则平均周转时间为（ ）。
解析：
- 执行顺序：P2(3ms) → P3(4ms) → P1(24ms)
- 完成时间：P2=3，P3=7，P1=31
- 平均周转时间 = (3+7+31)/3 = 41/3 ≈ 13.67ms
答案：13.67ms
例题2：以下关于时间片轮转调度的叙述中，正确的是（ ）。
A. 时间片越大，响应时间越短
B. 时间片越小，上下文切换越少
C. 时间片大小不会影响系统性能
D. 时间片过大时，时间片轮转会退化为FCFS
解析：时间片越大，响应变慢，切换减少；时间片越小，响应变快，切换增多。时间片过大，每个进程都能在一个时间片内执行完，变成FCFS。选D。
例题3：某系统采用动态优先级调度，下列措施中能有效防止低优先级进程饥饿的是（ ）。
A. 采用静态优先级
B. 允许进程抢占CPU
C. 随着进程等待时间增长而提高其优先级
D. 每次总是选择优先级最高的进程运行
解析：动态提高等待时间长的进程优先级（等待时间越长优先级越高），可以避免饥饿。选C。
8️⃣ 记忆口诀
FCFS先来先服务，长作业堵短进度。
SJF最短先执行，平均等待时间最优。
优先级高先上CPU，低优先级可能饿肚。
时间片轮转最公平，响应快但切换多。
9️⃣ 小测验（评论区对答案）
某系统采用先来先服务（FCFS）调度算法，有4个进程同时到达，所需CPU时间分别为 8ms、4ms、10ms、6ms，则这些进程的平均周转时间为（ ）。
A. 7ms
B. 14ms
C. 17ms
D. 28ms
🔔本专栏日更2篇，点击头像 → 专栏《软考中级高频考点》订阅，第一时间接收新内容
#软考中级 #软件设计师 #进程调度 #FCFS #SJF #优先级调度 #时间片轮转 #操作系统