专题进阶 · 操作系统算法推荐总顺序 · 第 144 / 148 课

明确优先级约定,并用老化计算解释长期等待如何影响选择。

先学会这些,再进入本课 最短作业优先 时间片轮转
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 操作系统算法

优先级调度Priority Scheduling

按优先级选任务,老化机制可缓解低优先级任务长期饥饿。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

明确优先级约定,并用老化计算解释长期等待如何影响选择。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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高
时刻4B:5−4=1,C:3−1=2B 因等待较久而优先
后续B:4→5,C:5→6没有老化时此刻会先选C

窄屏可左右滑动表格,阅读完整计算与理由。

老化使等待4个时间单位的 B 获得先于 C 的机会。

04为什么这个方法成立

  1. 决策时只考虑已到达、未完成任务,评分使用同一当前时间。
  2. 选择最小的 p_base−a(t−arrival),正好实现本课给定的有效优先级规则。
  3. 执行是非抢占的,完成后删除该任务并重新评分,不保留失效的旧排名。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

a=0 时是什么策略?

需要一点提示

等待项消失。

查看解析与答案

按固定基础优先级选择,平局按到达及输入顺序。

练习 2 · 边界与辨析

本例关闭老化后 A 之后是谁?

需要一点提示

比较 B=5、C=3。

查看解析与答案

C 先,再 B。

练习 3 · 变式与迁移

抢占式版本需要额外处理什么事件?

需要一点提示

高优先级任务可能在运行中到达。

查看解析与答案

需要记录当前任务剩余时间、比较新任务优先级,并决定是否中断及重新入队。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Arpaci-Dusseau · Operating Systems: Three Easy Pieces

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。