当前位置：首页 > news >正文

【操作系统】进程调度算法（FCFS/SJF/优先级/时间片轮转）

news 2026/6/25 13:53:25

考点频率：★★★★★（必考，常结合计算题考查）
难度：⭐⭐
建议：掌握各算法的核心思想、特点、优缺点，能计算平均周转时间

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	非抢占/抢占	平均等待时间最短	难以预估时间，可能饥饿	批处理系统（需预估时间）
优先级	非抢占/抢占	可区分重要性	低优先级可能饥饿	实时/分时系统
时间片轮转	抢占	响应快，公平	切换开销	分时系统