深入浅出讲解操作系统——实时调度

目录

⏱️ 实时调度 · 第1课：什么是实时系统？

🎓 第一部分：专业学术讲解

1. 什么是实时系统？

2. 两种实时系统

🎓 第二部分：实时任务的关键概念

1️⃣ 截止时间（Deadline）

2️⃣ 周期任务（Periodic Task）

3️⃣ 非周期任务（Aperiodic Task）

4️⃣ 就绪时间（Ready Time）

5️⃣ 执行时间（Execution Time / Burst Time）

6️⃣ 松弛度（Laxity / Slack Time）

⚙️ 第三部分：实现实时调度的三个基本条件

条件一：系统处理能力足够

CPU得够用

专业表达

通俗解释

🧸 例子

条件二：采用抢占式调度

条件三：快速切换机制

为什么需要？

两个具体要求

📊 一张表总结三个条件

🏠 第四部分：通俗生活化讲解

🧸 什么是“实时”？

🧸 生活中的例子

🧸 硬实时 vs 软实时（厨房版）

📊 第三部分：实时 vs 分时 vs 批处理

🧸 第四部分：这一课的小结

💭 想一想

⏱️ 实时调度 · 第2课：EDF 和 LLF 调度算法

🎓 第一部分：专业学术讲解

1. 实时调度要解决什么问题？

2. 算法一：最早截止时间优先（EDF）

3. 算法二：最低松弛度优先（LLF）

4. EDF 和 LLF 的区别

🏠 第二部分：通俗生活化讲解

🧸 EDF 类比：医院的“急诊分诊”

🧸 LLF 类比：更精细的急诊

🧸 一个例子帮你区分

🧸 第三部分：这一课的小结

💭 想一想

⏱️ 实时调度 · 第3课：优先级倒置与优先级继承

🎓 第一部分：什么是优先级倒置？

专业定义

为什么这很“反直觉”？

🎓 第二部分：优先级倒置如何发生？

需要的三个角色

一步一步推演

🏠 第二部分：通俗生活化讲解

🧸 医院急诊的优先级倒置

🧸 打印店的例子

🎓 第三部分：解决方案 —— 优先级继承

核心思想

推演（加上优先级继承）

🧸 第三部分：这一课的小结

💭 想一想

⏱️ 实时调度 · 第1课：什么是实时系统？

对应教材：3.3 实时调度（概念部分）

🎓 第一部分：专业学术讲解

1. 什么是实时系统？

实时系统是指系统能够在规定的时间内对外部事件做出响应，并完成相应处理的计算机系统。

正确性 =计算结果正确 + 时间正确

换句话说：

• 普通系统：结果对就行，慢一点没关系

• 实时系统：结果对 + 按时完成，缺一不可

2. 两种实时系统

🎓 第二部分：实时任务的关键概念

1️⃣ 截止时间（Deadline）

专业解释：

任务必须开始或完成的最晚时间。

通俗解释：

这是任务的“死线”。
就像期末考试：铃响必须停笔。

两种截止时间：

实时调度中，我们通常更关心完成截止时间。

2️⃣ 周期任务（Periodic Task）

专业解释：

每隔固定时间间隔执行一次的任务。

通俗解释：

就像你的闹钟：每天早上7点响一次，周期是24小时。

例子：

• 传感器每10ms采集一次温度

• 雷达每5ms扫描一次

• 视频每40ms刷新一帧（25帧/秒）

周期任务的数学形式：每 P 毫秒执行 C 毫秒

3️⃣ 非周期任务（Aperiodic Task）

专业解释：

到达时间不固定，但有时间要求（截止时间）。

通俗解释：

你永远不知道它什么时候来，但来了就必须在一定时间内处理完。

例子：

• 用户按下一个按钮

• 网络数据包到达

• 紧急中断信号

非周期任务是实时系统里最难处理的，因为你无法提前规划。

4️⃣ 就绪时间（Ready Time）

任务以及达到可以执行的状态，等待分配CPU

专业解释：

任务可以开始执行的最早时间。

通俗解释：

任务“醒来”的时间。
在这之前，任务还不能运行（比如数据还没到）。

例子：

• 周期任务：就绪时间 = 周期的整数倍（0, P, 2P, …）

• 非周期任务：就绪时间 = 随机到达的时间

5️⃣ 执行时间（Execution Time / Burst Time）

专业解释：

任务实际需要占用的CPU时间。

通俗解释：

任务真正“干活”需要多久。
不是“挂钟时间”，而是“CPU转了多少毫秒”。

重要：

• 执行时间 ≠ 响应时间（响应时间 = 等待时间 + 执行时间）

• 执行时间通常是已知的（最坏情况估计）

6️⃣ 松弛度（Laxity / Slack Time）

假设一个人很懒，做什么事情都拖到最后能完成的时间，这个松弛度就是中这个人最多还能偷多长时间的懒

专业解释：

任务还能“等多久”而不至于错过截止时间。

公式：

松弛度 = 截止时间 − 当前时间 − 剩余执行时间

通俗解释：

这是任务的“紧急程度”。
松弛度越小，越紧急。

例子：

• 截止时间 = 100ms，当前时间 = 30ms，还剩 50ms 要跑
  松弛度 = 100 − 30 − 50 =20ms（还能等20ms）

• 如果松弛度 = 0 → 必须立刻开始跑

• 如果松弛度 < 0 → 已经错过截止时间

LLF（最低松弛度优先）调度算法，就是每次选松弛度最小的任务先跑。

⚙️ 第三部分：实现实时调度的三个基本条件

这三个条件是硬指标，不满足就无法保证实时性。

条件一：系统处理能力足够

CPU得够用

专业表达

对于 m 个周期任务，每个任务的处理时间为 Cᵢ，周期为 Pᵢ：

∑(Cᵢ / Pᵢ) ≤ 1（单处理机）

通俗解释

• Cᵢ / Pᵢ = 这个任务占用的 CPU 百分比

• 所有任务的 CPU 占用率加起来不能超过 100%

🧸 例子

总和 = 10% + 20% + 40% =70% ≤ 100%✅ → 理论上可调度

如果总和 > 100%，就像一个人同时打三份工，必然迟到。

条件二：采用抢占式调度

如果是非抢占式，假设电脑此时正在更新游戏，那么万一有个火箭要准备发射了，电脑告诉你“不行不行，现在不能发射，等我更新完游戏”，故而必须是抢占式

为什么必须抢占？

实时任务随时可能到达。
如果不允许抢占，一个低优先级的长任务会堵住后面的高优先级实时任务 → 错过截止时间。

通俗解释：

急诊病人来了，正在看普通门诊的医生必须立刻停下来去救急诊。

结论：

实时系统必须用抢占式调度。

条件三：快速切换机制

上面说了需要抢占式调度，抢占式调度则意味着需要频繁的切换进程，故而需要快速切换机制

为什么需要？

抢占式调度意味着频繁切换。
如果切换本身很慢（比如要保存/恢复很多寄存器），就会浪费大量 CPU 时间，导致任务错过截止时间。

两个具体要求

通俗解释：

医生必须几秒钟内从普通门诊切换到急诊，而不是“等我写完这份病历再说”。

📊 一张表总结三个条件

🏠 第四部分：通俗生活化讲解

🧸 什么是“实时”？

“实时”不是“非常快”，而是：

到点必须完成，不能迟到。

🧸 生活中的例子

🧸 硬实时 vs 软实时（厨房版）

• 硬实时：汤快溢出来了 → 必须立刻关火，晚1秒都不行

• 软实时：菜凉了不好吃 → 最好准时，但晚几分钟也能吃

📊 第三部分：实时 vs 分时 vs 批处理

🧸 第四部分：这一课的小结

实时系统 = 到点必须完成，不能迟到

💭 想一想

你每天坐地铁、赶火车、等红绿灯，其实都在“实时系统”里生活。
只不过你是被调度的那个人 😊

上节课我们知道了什么是实时系统，以及“硬实时”和“软实时”的区别。
这节课我们来讲：实时调度具体怎么“排班”。

⏱️ 实时调度 · 第2课：EDF 和 LLF 调度算法

实时调度还需要更细化的调度算法，在多个实时任务到达时，选择不同的调度算法，会决定哪个实时任务先进行

对应教材：3.3.2 ~ 3.3.4

🎓 第一部分：专业学术讲解

1. 实时调度要解决什么问题？

在多个实时任务同时到达时，决定先做哪一个，才能保证所有任务都不错过截止时间。

2. 算法一：最早截止时间优先（EDF）

核心规则：

截止时间越早的任务，优先级越高。

特点：

• 优先级是动态的

有两个原因

一：有可能某个任务到了截止时间仍未完成，此时这个任务就已经失效了，那么优先级就会发生变化

二：因为是可抢占的，所以新来的任务可能截止时间更短

• 可抢占（新来的任务如果截止时间更早，可以打断当前任务）

• 在单处理机中，EDF 被证明是最优的实时调度算法

简单理解：

谁的死线（Deadline）更近，谁先做。

3. 算法二：最低松弛度优先（LLF）

核心规则：

松弛度（Laxity）越小的任务，优先级越高。

松弛度公式：

松弛度 = 截止时间 − 当前时间 − 剩余执行时间

松弛度的含义：

• 松弛度 = 任务还能“等多久”

• 松弛度越小 → 越紧急

特点：

• 也是动态优先级

• 可抢占

• 比 EDF 更精细（考虑了剩余执行时间）

4. EDF 和 LLF 的区别

🏠 第二部分：通俗生活化讲解

🧸 EDF 类比：医院的“急诊分诊”

不看你病多重（执行时间），只看你还能撑多久。

🧸 LLF 类比：更精细的急诊

同时考虑：还能撑多久 + 救他要多久。

🧸 一个例子帮你区分

假设两个病人：

• EDF：B 先（还能撑 9 分钟 < 10 分钟）

• LLF：

  • A 松弛度 = 10 − 0 − 8 = 2 分钟

  • B 松弛度 = 9 − 0 − 1 = 8 分钟

  • A 更紧急 →A 先

结果完全不同。

🧸 第三部分：这一课的小结

💭 想一想

你赶飞机：

• EDF 思维：谁的航班起飞早，谁先安检 ✅

• LLF 思维：谁再不安检就来不及了（考虑排队+安检时间），谁先

LLF 更聪明，但需要更多信息。

上节课我们讲了 EDF 和 LLF 这两种实时调度算法。
这节课我们来讲实时调度中一个非常经典、而且非常“反直觉”的问题——优先级倒置。

⏱️ 实时调度 · 第3课：优先级倒置与优先级继承

对应教材：3.3.5 优先级倒置

🎓 第一部分：什么是优先级倒置？

这一部分比较难理解，要理解这个部分我们首先要明确一个点：抢占式调度解决的是“CPU 竞争”问题，但解决不了“资源竞争”问题。

也就是说如果某个低优先级任务和某个高优先级任务所需资源是一样的，而低优先级任务在高优先级任务之前来到，那么此时高优先级任务会被低优先级任务阻塞

此时如果在来一个与低高优先级任务所用资源都不一样的中优先级任务，此时中优先级任务就会先执行，从而造成了优先级倒置

此时你可能会有几个问题（我当时就有这几个疑问）

假设p1=高优先级，p2=中优先级，p3=低优先级

①p1不是更高吗，为什么会被p2抢先

这个问题和问题三差不多，核心就是：p1此时是阻塞状态，而非就绪状态，根本没有抢的资格

②为什么p2不会阻塞呢

p2所需要的资源和p1p3不一样，而p1所需要的资源和p3一样

③如果p2抢占了p3运行，此时p1和p2的资源不同了，而p1的优先级更高，为什么不会抢占p2

同问题一

因为 P1 此时处于“阻塞状态”，根本不在 CPU 的就绪队列里。

一个阻塞的进程，无论它的优先级有多高，都无法参与 CPU 的竞争。

专业定义

优先级倒置（Priority Inversion）是指：

一个高优先级的进程，被一个低优先级的进程间接阻塞，而一个中优先级的进程反而抢先运行的现象。

简单说：

高优先级的人，被低优先级的人“卡住”了，而中间的人反而先走。

为什么这很“反直觉”？

直觉告诉我们：

• 高优先级应该最先运行

• 低优先级应该最后运行

但在优先级倒置中：

• 高优先级 →等

• 中优先级 →跑

• 低优先级 →被中优先级等

这是调度逻辑的“颠倒”。

🎓 第二部分：优先级倒置如何发生？

需要的三个角色

一步一步推演

第1步：P3 先运行，占用了一个共享资源（比如一把锁）

第2步：P1 到达，需要同一个资源 → 被 P3 阻塞 → P1 等待

第3步：P2 到达，优先级比 P3 高 → 抢占 CPU → P2 开始运行

第4步：P1 还在等 P3 释放资源
但 P3 被 P2 抢占了，没法运行
所以 P3 释放不了资源
所以 P1 永远等不到

结果：

• P1（高）→ 等 P3（低）

• P3（低）→ 等 P2（中）

• P2（中）→ 在运行

高优先级被低优先级“卡住”了。

🏠 第二部分：通俗生活化讲解

🧸 医院急诊的优先级倒置

更准确的比喻：

🧸 打印店的例子

你在一家打印店 🖨️

过程：

1. 老板拿着转接头（资源），准备帮普通顾客打印

2. 你来了，需要转接头 → 等老板

3. 普通顾客说：“我先来的，你先帮我”

4. 老板被普通顾客“拖住”

5. 你（高优先级）等老板（低优先级）
   老板等普通顾客（中优先级）

你被普通顾客卡住了。

🎓 第三部分：解决方案 —— 优先级继承

核心思想

当一个低优先级进程（P3）阻塞了高优先级进程（P1）时，
P3 临时继承 P1 的高优先级。

推演（加上优先级继承）

第1步：P3 运行，占用资源

第2步：P1 到达，需要资源 → 被 P3 阻塞
→ 触发优先级继承：P3 优先级升到和 P1 一样高

第3步：P2 到达，优先级比 P3（现在已提高）低
→ P2无法抢占P3

第4步：P3 继续运行，尽快释放资源

第5步：P3 释放资源后，恢复原优先级
→ P1 获得资源，继续运行

结果：

• P1 不再被无限拖延

• 中优先级 P2 无法“插队”

🧸 第三部分：这一课的小结

💭 想一想

优先级倒置在现实中很常见：

• 你急着用打印机（高），但被一个普通打印任务（中）卡住，因为管理员（低）在帮别人

• 你赶高铁（高），但安检口只有一个（资源），前面有人（低）在慢慢翻包，还被插队（中）

优先级继承就是：

让那个“慢慢翻包的人”临时变成“VIP”，先把你放过去。