01先把问题说具体
紧急任务应该优先执行,但低优先级任务一直被插队怎么办?
02一步步得到方法
数字大小必须有约定
本课规定数字越小优先级越高,采用非抢占调度:CPU 空闲时选择当前有效优先级最小的就绪任务,已经运行的任务执行完再做下一次决策。
抢占式优先级调度会在更高优先级任务到来时中断当前任务,涉及另一套事件处理。本课代码不把两种策略混在一起。
等待越久,逐步提高有效优先级
定义有效优先级 p_eff=p_base−a×等待时间,a≥0 是老化速度。等待越久数值越小,因此更有机会被选择。这里任务在第一次运行前一直等待,非抢占完成后退出。
老化能缓解低优先级任务长期等待,但是否严格保证有限等待还依赖到达模式、优先级是否有界、老化规则和运行时长。不要只加一个减法就宣称适用于所有无限工作负载。
动态分数如何实现
本课每次决策扫描就绪任务并按当前时间重新计算分数,简单透明,适合手算。直接把旧分数放进堆后永远不更新,通常会与随等待变化的策略不一致。
优先级反转是另一问题:高优先级任务可能等待低优先级任务持有的锁,此时可考虑优先级继承等机制。它不是仅靠就绪队列老化就自然解决的。
03把一个小例子完全算清楚
A=(到达0,时长4,优先级0),B=(0,1,5),C=(3,1,3),a=1。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 时刻0 | 先执行 A 到4 | 有效优先级0比B的5高 |
| 时刻4 | B:5−4=1,C:3−1=2 | B 因等待较久而优先 |
| 后续 | B:4→5,C:5→6 | 没有老化时此刻会先选C |
窄屏可左右滑动表格,阅读完整计算与理由。
老化使等待4个时间单位的 B 获得先于 C 的机会。
04为什么这个方法成立
- 决策时只考虑已到达、未完成任务,评分使用同一当前时间。
- 选择最小的 p_base−a(t−arrival),正好实现本课给定的有效优先级规则。
- 执行是非抢占的,完成后删除该任务并重新评分,不保留失效的旧排名。
05把推导翻译成代码
Python · 可独立运行的教学实现
def priority_schedule(jobs,aging=0.0):
if aging<0 or any(a<0 or d<=0 for _,a,d,p in jobs):
raise ValueError("invalid configuration")
pending = list(enumerate(jobs))
time,result = 0,[]
while pending:
ready = [item for item in pending if item[1][1]<=time]
if not ready:
time = min(job[1] for _,job in pending)
ready = [item for item in pending if item[1][1]<=time]
chosen = min(ready,key=lambda item:
(item[1][3]-aging*(time-item[1][1]),item[1][1],item[0]))
_,(name,arrival,duration,priority) = chosen
result.append((name,time,time+duration))
time += duration
pending.remove(chosen)
return result
jobs=[("A",0,4,0),("B",0,1,5),("C",3,1,3)]
print(priority_schedule(jobs,aging=1))逐个理解关键决定
item[1][3]-aging*(time-item[1][1])- 此模型在执行前没有运行过,所以等待时间等于当前时刻减到达时刻。
item[0]- 输入次序作为最后平局规则,让结果确定。
pending.remove(chosen)- 非抢占执行完成后任务退出,不再参与老化。
06时间、空间与实现范围
每次扫描最多 n 个剩余任务,n 次决策总时间 O(n²),空间 O(n)。
更高效实现需要利用评分规则的结构或维护动态队列,不能把此扫描代码标成 O(n log n)。
07改变条件,检查哪里会出错
各系统都规定数字越小越紧急
优先级约定可能相反,阅读接口前必须确认。
老化与优先级继承是同一机制
老化基于等待;继承通常用于锁依赖导致的优先级反转。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
a=0 时是什么策略?
需要一点提示
等待项消失。
查看解析与答案
按固定基础优先级选择,平局按到达及输入顺序。
本例关闭老化后 A 之后是谁?
需要一点提示
比较 B=5、C=3。
查看解析与答案
C 先,再 B。
抢占式版本需要额外处理什么事件?
需要一点提示
高优先级任务可能在运行中到达。
查看解析与答案
需要记录当前任务剩余时间、比较新任务优先级,并决定是否中断及重新入队。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Arpaci-Dusseau · Operating Systems: Three Easy Pieces