管程、优先级反转与 Peterson 算法

基于通用操作系统概念 · 核于 2026-08

速查

• 管程（Monitor）：把共享数据与操作它的过程封装在一起的高级同步结构（语言级，如 Java synchronized/Hoare 模型）。同一时刻只允许一个进程在管程内执行（自动互斥），用条件变量（condition variable） + wait/signal（阻塞/唤醒）实现同步——比手写 P/V 更安全、不易出错。
• 条件变量：管程内的"等待队列"。wait(c)：释放管程锁、本线程阻塞在条件 c 上；signal(c)（也叫 notify）：唤醒一个等在 c 上的线程。区别于信号量的 P/V——条件变量没有记忆（无人 wait 时 signal 丢失），而信号量的计数会累加。
• Peterson 算法（1981）：两进程软件互斥的经典解法，只需两个共享变量 flag[2]（表示想进）和 turn（轮到谁）。同时满足互斥、前进、有限等待——纯软件实现，证明互斥可严格推导。
• 优先级反转（Priority Inversion）：低优先级线程持有锁，高优先级线程被它阻塞，而中优先级线程抢占低优先级线程，导致高优先级被"中"间接拖延——违背优先级调度的初衷。**火星探路者号（1997）**因此任务超时、反复重启。
• 解法：优先级继承（Priority Inheritance）：低优先级线程持有锁时，临时继承等锁的高优先级线程的优先级，避免被中优先级抢占；放锁后恢复原优先级。mutex 常支持 PTHREAD_PRIO_INHERIT 属性。另有优先级天花板协议（天花板=所有可能用此锁的线程的最高优先级，持锁即升至天花板）。
• 自旋锁（Spinlock）vs 阻塞锁（Blocking Lock）：自旋锁忙等（循环测锁，不睡眠，占 CPU 但无切换开销，适合临界区极短）；阻塞锁抢不到则睡眠（进等待队列，不占 CPU 但有上下文切换开销，适合临界区长）。单核慎用自旋，多核短临界区用自旋锁。
• 进阶顺序：参考 —— mutex/semaphore/管程对比表、代码模板、易错点。

一、管程（Monitor）：语言级封装

手写 P/V 信号量极易出错——忘了配对、顺序颠倒、漏写一个 V，轻则死锁重则数据错乱。管程（Monitor）由 Hoare（1974）/Brinch Hansen 提出，把共享数据与操作它的过程封装在一起，由编译器/运行时自动保证互斥：

monitor Buffer {
    condition not_full, not_empty;   // 条件变量
    int count = 0;

    void put(item) {
        while (count == N)           // 满了就等
            wait(not_full);
        buffer.add(item);
        count++;
        signal(not_empty);           // 通知消费者
    }

    item get() {
        while (count == 0)           // 空了就等
            wait(not_empty);
        item = buffer.remove();
        count--;
        signal(not_full);            // 通知生产者
        return item;
    }
}

• 自动互斥：管程保证同一时刻只有一个进程在管程内执行——开发者无需手写 lock/unlock。
• 条件变量：用于同步（等某个条件成立）。wait(c) 会释放管程锁并阻塞本线程；signal(c) 唤醒一个等待者。条件变量不记数（无人等待时 signal 是空操作），所以 wait 前通常用 while 循环重新检查条件（防"惊群"/Hoare vs Mesa 语义差异）。
• Java 的实现：每个对象有一个内置锁（synchronized 方法/块即管程入口）和 wait()/notify()/notifyAll()（条件变量）。synchronized void put() 等价于进入管程。

对比	信号量	管程
谁保证互斥	程序员手写 P/V	编译器/运行时自动
易错性	高（顺序/配对易错）	低（封装好）
同步原语	P/V（带计数）	条件变量 wait/signal（无计数）
代表	POSIX semaphore、System V	Java synchronized、Hoare 管程

二、Peterson 算法：两进程软件互斥

Peterson 算法（1981，Gary Peterson）是纯软件实现两进程互斥的经典算法——不依赖任何硬件原子指令或关中断，只用两个普通共享变量：

int flag[2] = {false, false};  // flag[i]=true 表示进程 i 想进临界区
int turn;                      // 轮到谁（0 或 1），解决冲突

void process(int i) {
    int j = 1 - i;             // 另一个进程
    while (1) {
        flag[i] = true;        // ① 我想进
        turn = j;              // ② 礼让：把机会先给对方
        while (flag[j] && turn == j)  // ③ 对方也想进 且 轮到对方 → 等
            ;                  // 忙等
        // ──── 临界区 ────
        critical_section();
        // ──── 退出 ────
        flag[i] = false;       // ④ 我不想进了
    }
}

为什么正确（满足三条件）：

• 互斥：若 0、1 同时想进，都置 flag 为 true，但 turn 只能有一个最终值。假设 turn=1，则进程 0 的 while(flag[1] && turn==1) 为 true（阻塞），进程 1 的 while(flag[0] && turn==1) 中 turn==1 为 true 但要 flag[0]&&...——进程 0 的 flag[0]=true，故进程 1 也会阻塞？不对。重新理：turn=1 表示"轮到进程 1"，进程 0 检查 flag[1] && turn==1→true→等；进程 1 检查 flag[0] && turn==0？不，进程 1 检查的是 turn==j 这里 j=0，即 flag[0] && turn==0→turn==0 为 false→进程 1 不等，进入临界区。所以同一时刻只有一个进——互斥成立。

• 前进：临界区空闲时（无人 flag 为 true），想进者的 while 条件为 false，直接进入，不会无限阻塞。

• 有限等待：因 turn 机制，一个进程最多被对方"插队"一次——对方进完会置 flag[j]=false，本进程的 while 即为 false，必能进入。

• 局限：经典 Peterson 只解决两进程互斥（多进程需用"树形锦标赛"扩展）；在现代 CPU 的乱序执行/弱内存模型下需加内存屏障才正确（flag/turn 的读写可能被重排）。

三、优先级反转：高优先级被低优先级拖延

优先级反转（Priority Inversion）是实时系统里的经典陷阱：高优先级线程被低优先级线程间接阻塞，导致高优先级任务错过截止时间。

场景：三个线程——高 H、中 M、低 L。

时刻 t1：低优先级 L 运行，获取锁 lock（保护某共享资源）
时刻 t2：高优先级 H 就绪，抢占 L，运行
时刻 t3：H 需要同一资源 → 尝试 lock → 被 L 持有 → H 阻塞，等 L 放锁
时刻 t4：L 恢复运行（H 已阻塞）想放锁，但中优先级 M 就绪 → M 抢占 L
时刻 t5：M 长时间运行，L 无法执行（被 M 抢占）→ 无法放锁 → H 一直阻塞
结果：高优先级 H 被"中"优先级 M 间接拖延，违背优先级调度初衷

真实事故：1997 年 NASA 火星探路者号（Mars Pathfinder）在火星表面反复软件复位重启——根因就是优先级反转：高优先级的"总线管理"任务被低优先级的"气象数据"任务持锁阻塞，又被中优先级的通信任务抢占，导致看门狗超时复位。后来开启 VxWorks 的优先级继承选项，问题消失。

解法一：优先级继承（Priority Inheritance）

低优先级线程持锁期间，临时继承等锁线程中最高的优先级，放锁后恢复：

L 持 lock，H 等 lock → L 的优先级临时提升到 H 的级别
→ M 无法抢占 L（M 优先级低于"提升后的 L"）
→ L 继续运行直到放锁 → H 唤醒并抢占 L → 高优先级 H 不被 M 拖延

• 优点：实现相对简单，POSIX mutex 支持 PTHREAD_PRIO_INHERIT。
• 缺点：存在"链式继承"（L 等 K 的锁，K 又被 H 等，需逐级提升）和边界情况。

解法二：优先级天花板（Priority Ceiling）

每个锁预先指定天花板优先级=所有可能用此锁的线程的最高优先级。线程持锁瞬间立即升至天花板：

lock 的天花板 = max(所有用此锁线程的优先级)
线程获锁 → 立即升到天花板 → 绝不会被任何其他线程抢占（直到放锁）

• 优点：无需等"发生反转"才提升（预先提升），实时性可预测；能防死锁。
• 缺点：需静态知道每个锁的所有使用者，工程上较繁琐。

四、自旋锁 vs 阻塞锁：忙等还是睡眠

锁在抢不到时如何等待，分两类：

维度	自旋锁（Spinlock）	阻塞锁（Blocking Lock，如标准 mutex）
等待方式	循环反复测锁（忙等）	睡眠，进等待队列，被唤醒
占不占 CPU	✅ 占（空转浪费）	❌ 不占（让出 CPU）
上下文切换	无（不调度）	有（两次切换约 μs 级）
适用临界区	极短（几条指令）	较长（可能阻塞、IO）
单核	慎用（持锁者被抢占则自旋者永远等）	推荐
多核	短临界区推荐（无切换开销）	长临界区推荐

• 单核自旋锁的危险：A 持自旋锁后被调度切走，B 抢占并尝试同一锁→B 自旋等待→A 永远没机会运行放锁→B 永远自旋。所以单核自旋锁通常要关中断/关抢占。
• 选择原则：临界区短于两次上下文切换的开销（约几 μs）用自旋锁；否则用阻塞锁。Linux 内核中断处理（不可睡眠）必须用自旋锁。
• 混合锁：实际系统（如 Linux futex、Java synchronized）常先自旋一会儿，等不到再阻塞——兼顾两者优点。

下一步

理解了管程、Peterson 与优先级反转后，下一步系统梳理——参考（mutex/semaphore/管程对比表、经典问题信号量配置速查、代码模板、易错点清单）。