第九课：SJF（Shortest Job First）

我们先讲一个故事

假设你在奶茶店。

前面有三个人。

小明：点了100杯奶茶（需要30分钟）

小红：点了1杯奶茶（需要1分钟）

小刚：点了2杯奶茶（需要2分钟）

如果按照 FCFS：

小明

↓

小红

↓

小刚

那么：

小红：

为了买一杯奶茶。

却要：

等30分钟。

是不是很不合理？

于是：

老板改规则：

谁做得快，谁先做。

于是：

小红

↓

小刚

↓

小明

是不是：

大家平均等待时间：

变少了？

这就是：

SJF——短作业优先。

SJF规则

一句话：

每次都选择"运行时间最短"的进程。

注意。

不是：

最先到。

而是：

最短。

第一道例题

假设：

进程 到达时间 运行时间
A 0 8
B 1 4
C 2 2
D 3 1

第一步

时间：

0

只有：

A。

所以：

运行A

注意！

这里很多同学会问：

C最短，为什么不先运行C？

因为：

C还没有到。

SJF：

只能：

在已经到达的进程里选择。

第二步

A运行结束。

时间：

8

现在：

谁已经到了？

B（4）

C（2）

D（1）

CPU：

选谁？

当然：

最短。

所以：

D

第三步

D结束。

现在：

剩：

B（4）

C（2）

选：

C

第四步

最后：

B

甘特图

时间 →
0        8    9      11        15
|--------|----|------|----------|
    A      D      C        B

是不是：

除了顺序不同。

其他计算：

完全一样？

完成时间

看看图。

进程 完成时间
A 8
D 9
C 11
B 15

周转时间

公式：

周转时间 = 完成时间 − 到达时间

计算：

A：

8−0=8

B：

15−1=14

C：

11−2=9

D：

9−3=6

整理：

进程 周转时间
A 8
B 14
C 9
D 6

带权周转时间

公式：

带权周转时间 = 周转时间 ÷ 运行时间

计算：

进程 带权周转时间
A 8÷8=1
B 14÷4=3.5
C 9÷2=4.5
D 6÷1=6

为什么SJF平均等待时间更短？

来看一个例子。

三个进程：

进程 运行时间
A 8
B 2
C 1

FCFS

A → B → C

等待：

A：0

B：8

C：10

平均等待：

(0+8+10)/3=6

SJF

C → B → A

等待：

C：0

B：1

A：3

平均等待：

(0+1+3)/3≈1.33

是不是：

差很多？

所以：

SJF 的最大优点就是平均等待时间更短。

SJF的问题（★★★★★）

现在来看一个经典问题。

假设：

有一个长进程：

A

运行100秒

然后：

每隔1秒。

都来了一个：

1秒的小进程。

例如：

B：1秒

C：1秒

D：1秒

E：1秒

……

SJF会怎么选？

当然：

一直选：

B

↓

C

↓

D

↓

E

那么：

A：

什么时候运行？

可能：

一直没有机会。

这种现象叫：

饥饿（Starvation）

也叫：

饥饿现象。

意思就是：

一个进程长期得不到CPU。

这是SJF最大的缺点。

非抢占式SJF 和 抢占式SJF

这里是很多同学第一次容易混淆的地方。

教材里实际上有两种 SJF。

第一种：非抢占式SJF（教材默认）

规则：

CPU一旦开始运行一个进程，就必须等它结束。

例如：

A：

运行8秒

即使：

中间来了：

B

运行1秒

也不能：

打断A。

必须：

等A结束。

这就是：

非抢占式。

我们今天一直讲的就是这一种。

第二种：抢占式SJF（Shortest Remaining Time First，SRTF）

规则：

如果来了一个剩余运行时间更短的进程，就立即抢占CPU。

举个例子。

A：

总共需要10秒。

已经运行：

3秒。

还剩：

7秒。

这时候：

B来了。

只需要：

2秒。

操作系统说：

A暂停！

CPU给B！

运行顺序：

A（3秒）

↓

B（2秒）

↓

A（剩下7秒）

这就是：

抢占式SJF。

很多教材也叫：

最短剩余时间优先（SRTF）。

FCFS 和 SJF 对比

这是考试非常喜欢出的选择题。

对比项 FCFS SJF
排队依据 到达时间 运行时间
是否简单 非常简单 较复杂
平均等待时间 较长 较短（理论最优）
是否可能饥饿 不会 会
是否公平 较公平 对长作业不公平

记住一句：

FCFS公平，但效率不高；SJF效率高，但可能饿死长作业。

本课最重要的知识点

① SJF规则

在已经到达的进程中，选择运行时间最短的。

② SJF优点

平均等待时间最短。

这是它最大的优势。

③ SJF缺点

可能发生饥饿（Starvation）。

长作业可能一直得不到CPU。

④ 两种SJF

  • 非抢占式：运行后不能中断（本章重点）。
  • 抢占式（SRTF）：更短的作业到来时可以抢占CPU。

课堂练习

请你自己完成这道题。

进程 到达时间 运行时间
P1 0 6
P2 1 2
P3 2 8
P4 3 3

要求：

  1. 使用 非抢占式SJF 画出甘特图。
  2. 求每个进程的完成时间。
  3. 求周转时间。
  4. 求平均周转时间。

学到这里，你已经掌握了两种调度算法

CPU调度算法
│
├── FCFS（先来先服务） ✅
│
└── SJF（短作业优先） ✅

第十课：时间片轮转（RR，Round Robin）

先回顾一下前两节

我们已经学过两种调度算法：

FCFS（先来先服务）

A → B → C

特点：

谁先来，谁先运行。

SJF（短作业优先）

运行时间最短

↓

先运行

特点：

效率高，但是长任务容易"饿死"。

现在问题来了。

假设：

你正在：

  • 微信聊天
  • 听音乐
  • 看视频
  • 下载游戏

如果使用 FCFS。

视频：

需要运行：

30秒。

那么：

微信是不是：

要等30秒？

不能接受。

如果使用 SJF。

视频：

运行时间最长。

是不是：

一直轮不到？

还是不行。

所以：

需要一种新的算法。

RR的思想

一句话：

大家轮流使用CPU，每个人只能运行一小会儿。

这里：

"一小会儿"就是：

时间片（Time Quantum）

例如：

规定：

时间片：

2ms

那么：

每个进程：

最多：

连续运行2ms。

时间一到。

必须：

让CPU给别人。

一个生活例子

想象只有一支麦克风。

四个人都要发言。

规则：

每个人：

只能说2分钟。

于是：

A

↓

B

↓

C

↓

D

↓

A

↓

B……

是不是：

每个人都能很快轮到自己？

这就是：

RR。

第一道例题

假设：

时间片：

2秒

三个进程：

进程 到达时间 运行时间
A 0 5
B 0 4
C 0 2

注意：

三个都同时到达。

第一步

CPU：

运行：

A。

但是：

只能：

2秒。

于是：

A：

还剩：

3秒。

时间：

来到：

2

A：

回到：

队尾。

等待队列：

B

↓

C

↓

A

第二步

运行：

B。

2秒。

还剩：

2秒。

队列：

C

↓

A

↓

B

第三步

运行：

C。

它：

总共：

2秒。

正好：

结束。

所以：

C：

退出。

队列：

A

↓

B

第四步

运行：

A。

2秒。

还剩：

1秒。

队列：

B

↓

A

第五步

运行：

B。

2秒。

刚好：

结束。

队列：

A

第六步

运行：

A。

最后：

1秒。

结束。

甘特图（一定会画）

时间 →
0   2   4   6   8   10  11
|---|---|---|---|----|---|
 A   B   C   A    B    A

注意。

RR：

最大的特点就是：

一个进程会出现很多次。

不像：

FCFS：

A

↓

一次结束。

RR：

A

↓

回来

↓

再回来

↓

再回来

如何计算完成时间？

看最后一次结束的位置。

例如：

A：

最后：

结束：

11

所以：

完成时间：

11。

B：

结束：

10

C：

结束：

6

整理：

进程 完成时间
A 11
B 10
C 6

周转时间

公式：

完成时间 − 到达时间

三个都：

0秒到达。

所以：

进程 周转时间
A 11
B 10
C 6

平均：

(11+10+6)

÷3

=9

为什么RR适合交互系统？

来看一个例子。

假设：

微信：

只需要：

0.1秒

响应。

浏览器：

需要：

10秒。

FCFS：

浏览器：

一直运行。

微信：

等10秒。

用户：

会觉得：

电脑卡死了。

RR：

浏览器：

跑2ms。

然后：

微信：

马上：

获得CPU。

用户：

感觉：

微信：

秒回。

所以：

RR：

非常适合：

Windows。

Linux。

macOS。

因为：

用户最关心：

响应速度。

时间片到底应该多长？

这是一个经典问题。

时间片太长

例如：

100秒。

A：

一直运行。

其他：

一直等。

是不是：

又变成：

FCFS？

所以：

太长。

不好。

时间片太短

例如：

0.000001秒。

CPU：

不停：

保存PCB

↓

恢复PCB

↓

保存PCB

↓

恢复PCB

真正运行程序：

时间：

反而很少。

因为：

上下文切换：

也需要时间。

所以：

太短。

也不好。

最佳情况

一般来说：

时间片应远大于一次上下文切换时间，又不能长到影响交互体验。

例如：

  • 上下文切换可能是几微秒到几十微秒；
  • 时间片通常是几毫秒到几十毫秒（不同系统实现不同）。

这样既减少切换开销，又保证程序响应及时。

RR优点

✅ 公平。

每个人：

都有机会。

✅ 响应快。

交互体验：

很好。

✅ 不会饿死。

没有进程：

一直：

得不到CPU。

RR缺点

第一：

上下文切换：

很多。

CPU：

浪费：

一部分时间。

第二：

平均周转时间：

通常：

不如SJF。

因为：

SJF：

专门优化：

等待时间。

RR：

主要优化：

响应时间。

三种算法对比

这是考试很喜欢出的表格。

算法 排队规则 优点 缺点 适合场景
FCFS 先到先服务 简单、公平 护航效应 批处理
SJF 最短作业优先 平均等待时间最短 可能饥饿 批处理
RR 时间片轮流运行 响应快、公平 切换开销大 交互系统

一个容易混淆的问题

很多同学会问：

时间片到了，进程应该进入阻塞态还是就绪态？

答案：

就绪态。

为什么？

因为：

它不是：

等待磁盘。

不是：

等待网络。

不是：

等待键盘。

它只是：

CPU时间用完了。

所以：

它仍然具备运行条件。

只是：

需要：

重新排队。

因此：

运行态 →（时间片到）→ 就绪态

而不是：

运行态 → 阻塞态

这是考试中非常经典的选择题。

今天最重要的一张图

时间片到
  ┌──────────────────┐
  ▼                  │
运行态 ───────────▶ 就绪态
  │
  │ 等待I/O等事件
  ▼
阻塞态
  │
  │ 事件完成
  ▼
就绪态

你会发现：

我们把第五课的 进程状态 和今天的 RR调度 联系起来了。

本课重点（必须掌握）

✅ RR（时间片轮转）：每个进程轮流运行一个固定时间片。

✅ 时间片结束后，进程进入 就绪态 ，排到就绪队列尾部。

✅ RR 的目标是提高 响应速度 ，特别适合交互式系统。

✅ 时间片太长接近 FCFS；时间片太短会导致上下文切换开销过大。

# 算法
Logo
openEuler 社区

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐

cover

Raspberry Pi OS：连接硬件与创意的官方操作系统

avatar openEuler 社区

Raven Agent（渡鸦）深度解读

发布：2026‑07‑10｜盛大孵化 EverMind｜底层基座：自研智能体操作系统，主打双向记忆内化、技能自迭代、代码级自我重写；开源框架，面向开发者构建长期持续进化 Agent。

avatar openEuler 社区

鸿蒙应用开发学习路线（2026 初学者版）

鸿蒙操作系统（HarmonyOS）是华为面向全场景的分布式操作系统，支持手机、平板、智能穿戴、智慧屏、车机等多种设备。随着鸿蒙生态的快速发展，应用开发人才需求持续增长。对于初学者来说，2026 年是学习鸿蒙应用开发的绝佳时机，官方文档和开发工具已经非常成熟，生态也日趋完善。本文为完全零基础的初学者梳理了一条清晰的学习路线，从编程基础到项目实战，每个阶段都给出了学习内容和参考资源，帮助你循序渐进地掌

avatar openEuler 社区