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

目录⏱️ 实时调度 · 第1课什么是实时系统 第一部分专业学术讲解1. 什么是实时系统2. 两种实时系统 第二部分实时任务的关键概念1️⃣ 截止时间Deadline2️⃣ 周期任务Periodic Task3️⃣ 非周期任务Aperiodic Task4️⃣ 就绪时间Ready Time5️⃣ 执行时间Execution Time / Burst Time6️⃣ 松弛度Laxity / Slack Time⚙️ 第三部分实现实时调度的三个基本条件条件一系统处理能力足够CPU得够用专业表达通俗解释 例子条件二采用抢占式调度条件三快速切换机制为什么需要两个具体要求 一张表总结三个条件 第四部分通俗生活化讲解 什么是“实时” 生活中的例子 硬实时 vs 软实时厨房版 第三部分实时 vs 分时 vs 批处理 第四部分这一课的小结 想一想⏱️ 实时调度 · 第2课EDF 和 LLF 调度算法 第一部分专业学术讲解1. 实时调度要解决什么问题2. 算法一最早截止时间优先EDF3. 算法二最低松弛度优先LLF4. EDF 和 LLF 的区别 第二部分通俗生活化讲解 EDF 类比医院的“急诊分诊” LLF 类比更精细的急诊 一个例子帮你区分 第三部分这一课的小结 想一想⏱️ 实时调度 · 第3课优先级倒置与优先级继承 第一部分什么是优先级倒置专业定义为什么这很“反直觉” 第二部分优先级倒置如何发生需要的三个角色一步一步推演 第二部分通俗生活化讲解 医院急诊的优先级倒置 打印店的例子 第三部分解决方案 —— 优先级继承核心思想推演加上优先级继承 第三部分这一课的小结 想一想⏱️ 实时调度 · 第1课什么是实时系统对应教材3.3 实时调度概念部分 第一部分专业学术讲解1. 什么是实时系统实时系统是指系统能够在规定的时间内对外部事件做出响应并完成相应处理的计算机系统。正确性 计算结果正确 时间正确换句话说普通系统结果对就行慢一点没关系实时系统结果对 按时完成缺一不可2. 两种实时系统类型错过截止时间的后果例子硬实时必须这个时间完成灾难性后果火箭发射、汽车安全气囊、心脏起搏器软实时最好这个时间完成完不成也没大事性能下降系统不会崩溃视频播放、网络游戏、语音通话 第二部分实时任务的关键概念概念解释截止时间任务必须开始或完成的最晚时间周期任务每隔固定时间执行一次如传感器每10ms采集一次非周期任务随机到达但有时间要求就绪时间任务可以开始执行的时间执行时间任务实际需要占用的CPU时间松弛度 截止时间 − 当前时间 − 剩余执行时间越紧急松弛度越小1️⃣ 截止时间Deadline专业解释任务必须开始或完成的最晚时间。通俗解释这是任务的“死线”。就像期末考试铃响必须停笔。两种截止时间类型含义例子开始截止时间必须在某个时间之前开始执行火箭必须在11:00:00之前点火完成截止时间必须在某个时间之前执行完导弹必须在10秒内命中目标实时调度中我们通常更关心完成截止时间。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% 例子任务执行时间 C周期 PCPU 占用率 (C/P)传感器采集1ms10ms10%图像处理4ms20ms20%网络通信2ms5ms40%总和 10% 20% 40% 70% ≤ 100%✅ → 理论上可调度如果总和 100%就像一个人同时打三份工必然迟到。条件二采用抢占式调度如果是非抢占式假设电脑此时正在更新游戏那么万一有个火箭要准备发射了电脑告诉你“不行不行现在不能发射等我更新完游戏”故而必须是抢占式为什么必须抢占实时任务随时可能到达。如果不允许抢占一个低优先级的长任务会堵住后面的高优先级实时任务 → 错过截止时间。通俗解释急诊病人来了正在看普通门诊的医生必须立刻停下来去救急诊。结论实时系统必须用抢占式调度。条件三快速切换机制上面说了需要抢占式调度抢占式调度则意味着需要频繁的切换进程故而需要快速切换机制为什么需要抢占式调度意味着频繁切换。如果切换本身很慢比如要保存/恢复很多寄存器就会浪费大量 CPU 时间导致任务错过截止时间。两个具体要求要求说明快速响应中断外部事件一来CPU 要能很快停下来快速任务分派上下文切换开销要尽量小通俗解释医生必须几秒钟内从普通门诊切换到急诊而不是“等我写完这份病历再说”。 一张表总结三个条件条件核心要求不满足的后果处理能力足够∑(Cᵢ/Pᵢ) ≤ 1任务必然超时抢占式调度高优先级可以打断低优先级实时任务被堵快速切换中断响应快、上下文切换快切换开销太大CPU 浪费 第四部分通俗生活化讲解 什么是“实时”“实时”不是“非常快”而是到点必须完成不能迟到。 生活中的例子场景是否实时为什么你写作业❌ 非实时今天写不完明天写也行期末考试交卷✅ 硬实时铃响必须停笔否则0分看视频✅ 软实时卡一下还能忍一直卡就不行坐高铁✅ 硬实时高铁不等人错过就没了 硬实时 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 的区别对比维度EDFLLF优先级依据截止时间松弛度是否考虑剩余时间❌ 不考虑✅ 考虑实现复杂度较简单更复杂典型场景周期任务混合任务 第二部分通俗生活化讲解 EDF 类比医院的“急诊分诊”EDF 概念医院类比截止时间病人能撑多久EDF 规则谁快撑不住了谁先看不看你病多重执行时间只看你还能撑多久。 LLF 类比更精细的急诊LLF 概念医院类比松弛度还能等几分钟LLF 规则谁再不救就要死了谁先看同时考虑还能撑多久 救他要多久。 一个例子帮你区分假设两个病人病人还能撑多久截止时间抢救需要多久A10 分钟8 分钟B9 分钟1 分钟EDFB 先还能撑 9 分钟 10 分钟LLFA 松弛度 10 − 0 − 8 2 分钟B 松弛度 9 − 0 − 1 8 分钟A 更紧急 →A 先结果完全不同。 第三部分这一课的小结你要记住的一句话EDF截止时间越早优先级越高LLF松弛度越小优先级越高松弛度 截止时间 − 当前时间 − 剩余时间谁更优理论上 EDF 最优但 LLF 更精细 想一想你赶飞机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是指一个高优先级的进程被一个低优先级的进程间接阻塞而一个中优先级的进程反而抢先运行的现象。简单说高优先级的人被低优先级的人“卡住”了而中间的人反而先走。为什么这很“反直觉”直觉告诉我们高优先级应该最先运行低优先级应该最后运行但在优先级倒置中高优先级 →等中优先级 →跑低优先级 →被中优先级等这是调度逻辑的“颠倒”。 第二部分优先级倒置如何发生需要的三个角色进程优先级角色P1高需要某个共享资源P2中不需要该资源纯计算P3低已经占用了该资源一步一步推演第1步P3 先运行占用了一个共享资源比如一把锁第2步P1 到达需要同一个资源 → 被 P3 阻塞 → P1 等待第3步P2 到达优先级比 P3 高 → 抢占 CPU → P2 开始运行第4步P1 还在等 P3 释放资源但 P3 被 P2 抢占了没法运行所以 P3 释放不了资源所以 P1 永远等不到结果P1高→ 等 P3低P3低→ 等 P2中P2中→ 在运行高优先级被低优先级“卡住”了。 第二部分通俗生活化讲解 医院急诊的优先级倒置角色进程类比优先级危重病人P1高普通门诊病人P2中急诊医生P3低这里需要调整比喻更准确的比喻 打印店的例子你在一家打印店 ️角色优先级你着急打印高另一个普通顾客中老板拿着唯一的U盘转接头低本来在做别的事过程老板拿着转接头资源准备帮普通顾客打印你来了需要转接头 → 等老板普通顾客说“我先来的你先帮我”老板被普通顾客“拖住”你高优先级等老板低优先级老板等普通顾客中优先级你被普通顾客卡住了。 第三部分解决方案 —— 优先级继承核心思想当一个低优先级进程P3阻塞了高优先级进程P1时P3 临时继承 P1 的高优先级。推演加上优先级继承第1步P3 运行占用资源第2步P1 到达需要资源 → 被 P3 阻塞→ 触发优先级继承P3 优先级升到和 P1 一样高第3步P2 到达优先级比 P3现在已提高低→ P2无法抢占P3第4步P3 继续运行尽快释放资源第5步P3 释放资源后恢复原优先级→ P1 获得资源继续运行结果P1 不再被无限拖延中优先级 P2 无法“插队” 第三部分这一课的小结你要记住的一句话优先级倒置高优先级被低优先级间接阻塞发生条件共享资源 中优先级抢占严重后果高优先级任务错过截止时间实时系统可能崩溃解决方案优先级继承优先级继承低优先级临时继承高优先级防止被中优先级抢占 想一想优先级倒置在现实中很常见你急着用打印机高但被一个普通打印任务中卡住因为管理员低在帮别人你赶高铁高但安检口只有一个资源前面有人低在慢慢翻包还被插队中优先级继承就是让那个“慢慢翻包的人”临时变成“VIP”先把你放过去。