同步与互斥：从信号量到管程

引言

2004年9月，Linux内核邮件列表上爆发了一场关于RCU（Read-Copy-Update）机制的激烈讨论。争论的焦点是：当多个CPU核心同时访问共享数据结构时，要保证正确性又不牺牲多核性能，仅靠一把大锁是不够的。

这个令内核开发者头疼的问题，它的理论根基可以追溯到1965年——Dijkstra在THE操作系统的设计文档中，第一次提出了**信号量（Semaphore）**这一概念。六十年后的今天，你手机里Android内核的同步原语、JVM中synchronized关键字的实现、甚至数据库事务的隔离机制，都建立在这个看似简单却无比深刻的"PV操作"之上。

本文是你学习408操作系统中"进程同步与互斥"的完整指南。我们从最朴素的软件锁出发，穿越信号量的设计哲学，最终抵达管程这一现代编程语言中并发控制的理论基石。

核心速览

  • 互斥解决"争夺资源"的问题，同步解决"协作等待"的问题——两者共享同一套底层机制但设计意图截然不同
  • 信号量不是简单的计数器，它的真正威力在于block/wakeup机制——将等待的进程挂起而非忙等
  • PV操作的顺序不是风格偏好，而是死锁与正确性的分界线

📌 核心要点

  • 临界资源的本质：一次只允许一个进程访问的共享资源，保护它的是临界区代码而非资源本身
  • 信号量的灵魂是"让权等待"：整型信号量做不到，记录型信号量通过阻塞队列做到了
  • PV操作的顺序决定生死：先P同步信号量再P互斥信号量——违背这一条，死锁必然发生
  • 管程=编译器兜底的互斥+条件变量实现的同步——程序员只管业务逻辑，不用手动维护锁
  • 四种解决方案是层层递进的：软件→硬件→信号量→管程，每一层解决前一层的一个痛点

背景：为什么会有同步与互斥问题

临界资源与临界区

在多道程序环境下，进程是并发执行的。举个例子：两个进程A和B都想往打印机上输出内容。A先打印了"Hello"，轮到B之前发生了进程切换，B抢在A之前又打印了"World"，最终纸张上印出来的可能是"HelWorlod"——一段谁也看不懂的乱码。

问题出在哪？打印机是一种临界资源（Critical Resource）：同一时刻只能被一个进程使用。访问临界资源的那段代码，就叫临界区（Critical Section）。

进程A                    进程B
  │                        │
  ├── 进入区（申请权限）       │
  ├── 临界区（使用打印机）      ├── 进入区（申请权限）
  ├── 退出区（释放权限）       │    ↓ 被阻塞等待
  ├── 剩余区（干别的事）       ├── 临界区（使用打印机）
  │                        ├── 退出区（释放权限）
  │                        └── 剩余区（干别的事）

访问临界区需要遵循四条铁律：

规则 含义 考研考点
空闲让进 没人用时，申请即可进入 单标志法违背这一条
忙则等待 别人在用，你在门口排队 所有方案都必须保证
有限等待 排队不能排到天荒地老 防止饥饿（starvation）
让权等待 进不去就别占着CPU 这是信号量优于软件方案的关键

这四条规则看似简单，但真正在代码级实现它们时，会暴露出令人意想不到的陷阱。

同步 vs 互斥：两种不同的约束

[ANSWER-FIRST] 互斥是对资源的排他性约束，同步是对执行顺序的协作性约束。

  • 互斥（Mutual Exclusion）：也称间接制约关系。两个进程都要访问同一台打印机，操作系统必须确保它们不会同时使用。进程之间不需要知道对方的存在——它们只是在争抢同一个资源。
  • 同步（Synchronization）：也称直接制约关系。进程A执行到某个位置必须等进程B产生数据后才能继续。这是主动的协作关系，进程之间需要互相感知。

举个考研经常用的例子：生产者-消费者问题中，生产者往缓冲区放数据、消费者从缓冲区取数据。这两个操作互相是互斥的（不能同时修改缓冲区），但同时它们也是同步的——缓冲区为空时消费者必须等生产者先放东西，缓冲区满了生产者必须等消费者取走一些。一个场景同时包含了互斥和同步。

[INTERNAL-LINK: 进程基础与状态转换 → 进程的创建、终止与状态切换]

软件解法：从"单标志"到Peterson

在硬件没有提供原子指令的年代，人们只能用纯软件变量实现互斥。这段历史虽然看起来"过时"，但它完美展示了没有原子操作时并发编程有多脆弱——这段痛苦的经历也正是信号量被发明的动机。

单标志法：最朴素的尝试

int turn = 0;  // 轮到谁进入临界区

// 进程 P0
while (turn != 0);   // ① 检查是不是自己的回合
critical_section();   // ② 进入临界区
turn = 1;            // ③ 把权限交给 P1
remainder_section();

// 进程 P1
while (turn != 1);
critical_section();
turn = 0;
remainder_section();

问题在于：如果P0执行完后把turn设为1，P1进入临界区完成后turn回到0——此时如果P1还想再次进入临界区，它必须等P0来"还"这个权限。但P0可能正在剩余区处理完全不相关的事情，根本没打算进入临界区。turn的值告诉P1"你等着"，可临界区实际上是空的。

违背了"空闲让进"。这个方案在逻辑上假设两个进程一定交替进入临界区，然而现实情况可不是这么规整的。

双标志法：从"先检查"到"后检查"

双标志法的思路是给每个进程一个独立的标志位，让它表达"我想进入临界区"的意图。

双标志先检查法：

bool flag[2] = {false, false};

// 进程 Pi (i = 0 或 1)
flag[i] = true;               // ① 挂上"我想进入"的旗子
while (flag[1-i]);           // ② 检查对方是不是也想进入
critical_section();           // ③ 进入临界区
flag[i] = false;              // ④ 解开自己的旗子
remainder_section();

问题出在①和②之间。如果Pi执行完flag[i] = true还没执行while检查，发生进程切换，Pj也把自己的flag设为true。两人都看到对方的flag为true，都在while循环里死等，谁也别想进去。

更致命的情况：如果恰好两个进程都完成了flag赋值（都看到了false），又都没有被对方拦住，结果两个进程同时进入了临界区。这就是"检查和上锁无法一气呵成"的代价。

双标志后检查法把while放到了flag赋值前面：

// 进程 Pi
while (flag[1-i]);           // ① 先检查对方有没有意愿
flag[i] = true;               // ② 再挂自己的旗
critical_section();
flag[i] = false;
remainder_section();

这次的问题变成了"互相谦让"——两个进程同时检查，都没看到对方有意愿，同时置flag为true，然后僵住。如果竞态条件恰好发生在while和flag赋值之间，两个进程都认为"对方先来的"，谁也不敢动。可能产生饥饿。

Peterson算法：两个标志位 + “让权”

1981年，Gary L. Peterson发表了一篇仅两页的论文，提出了一个精巧的软件互斥方案：

bool flag[2] = {false, false};
int turn = 0;

// 进程 P0
flag[0] = true;               // ① "我想进"
turn = 1;                     // ② "让P1先进"
while (flag[1] && turn == 1); // ③ 如果P1也想进且我让了，就等
critical_section();
flag[0] = false;              // ④ 退出

// 进程 P1
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0);
critical_section();
flag[1] = false;

核心思路：用flag表达意愿，用turn解决冲突。当两个进程同时想进入时，turn变量决定了谁——后写turn值的人"谦让"，先写的人获得进入权。这里的关键是：turn只能保存一个值，最后一次对turn的赋值会覆盖前一次，所以必然有一个进程的while条件不成立。

[ORIGINAL DATA] 在x86平台上用GCC -O2编译Peterson算法，由于现代CPU的乱序执行和编译器优化，这个纯软件方案实际上可能失效。Store-Load重排可以让flag[i]=true和while(turn==…)的执行顺序被颠倒。这就是为什么Linux内核中实际使用的自旋锁必须依赖硬件原子指令——软件互斥在现代多核系统上是不可靠的。

Peterson算法完美解决了互斥问题，但有一个致命缺陷：当进程进不去临界区时，它在while循环里忙等（busy waiting）——CPU时间白白消耗在"看别人有没有完事"上。这违背了"让权等待"原则。

硬件解法：中断屏蔽与原子指令

软件方案的根本困境在于：检查和修改状态这两个操作无法原子完成。那如果在"检查并修改"的瞬间，让其他进程无法插足呢？硬件提供了两条路。

中断屏蔽（关中断）

最简单的想法：进入临界区之前把中断关了，不让进程切换发生。

关中断();           // cli 指令（x86）
critical_section();
开中断();           // sti 指令（x86）

问题很明显：关中断是特权指令，用户态程序无权执行。而且关中断影响的是整个CPU核心——其他不相关的进程也被迫等待。在多核CPU上，关一个核的中断挡不住其他核心同时访问临界区。这个方案的适用场景被限制在单CPU内核代码的短临界区。

Test-and-Set（TS/TSL）指令

1964年IBM System/360引入了TS指令，它是一个硬件保证的原子操作：

// TS指令的语义（原子执行）
bool TestAndSet(bool *lock) {
    bool old = *lock;
    *lock = true;     // 无条件上锁
    return old;        // 返回旧值，告诉你之前有没有锁
}

// 使用TS指令的互斥锁
while (TestAndSet(&lock));  // 如果lock原本是false（无人持有），
                            // 则lock变为true且返回false，跳出循环
critical_section();
lock = false;               // 释放锁

TS指令的精妙之处在于："读取旧值并写入新值"这两个动作在硬件层面不可分割。这个方案实现了互斥，但仍然忙等——进不去临界区的进程在while里疯狂执行TS指令。

Swap/XCHG指令

与TS原理相同但实现形式不同的原子交换指令：

// Swap指令的语义
void Swap(bool *a, bool *b) {
    bool temp = *a;
    *a = *b;
    *b = temp;
}

// 使用方式
bool key = true;
do {
    Swap(&lock, &key);  // lock变为true，key拿到旧值
} while (key == true);  // 如果拿到的旧值是true（已被锁），继续循环
critical_section();
lock = false;

TS和Swap两种方案本质等价，都解决了互斥问题但都没有解决忙等。硬件给了原子性，但没有给"让权等待"。

Citation Capsule

Dijkstra, E. W. (1965). “Cooperating Sequential Processes.” Technical Report, Technological University, Eindhoven. 信号量概念的原始论文。

Peterson, G. L. (1981). “Myths About the Mutual Exclusion Problem.” Information Processing Letters, 12(3), 115-116. Peterson算法的原始发表。

上述内容基于王道考研《操作系统》第二章同步与互斥知识体系梳理 (CSKAOYAN.COM)。

信号量机制：一道分水岭

1965年，Dijkstra在为一台名为THE的荷兰计算机设计操作系统时，意识到一个问题：现有的互斥方案要么忙等，要么在软件层面捉襟见肘。他提出了一个在当时看来相当激进的想法——为什么不让操作系统来管理"等还是不等"这件事？

整型信号量：概念先行，实现有缺

Dijkstra最初的信号量就是一个整数变量，配两个原子操作——他分别用荷兰语中的"Proberen（尝试）"和"Verhogen（增加）"的首字母命名为P操作和V操作：

// 整型信号量（概念版，不满足让权等待）
typedef struct {
    int value;  // 剩余资源数
} Semaphore;

void P(Semaphore S) {
    while (S.value <= 0);  // 忙等！资源不够就一直循环
    S.value--;
}

void V(Semaphore S) {
    S.value++;
}

P操作检查到资源不够时，进程在while循环里死等——CPU空转。这就是为什么考研教材通常一笔带过整型信号量：它不过是一个被原子保护了的整数，没有解决最关键的"让权等待"问题。

记录型信号量：考研默认的"信号量"

把忙等替换为"进程阻塞，让出CPU"，就得到了记录型信号量——408考研中如果没有特别说明，"信号量"指的就是这一种：

// 记录型信号量——考研标准定义
typedef struct {
    int value;              // 剩余资源数（可为负！）
    Queue wait_queue;       // 等待该信号量的阻塞进程队列
} Semaphore;

/* P操作（wait操作）：申请一个资源
 *
 * 逻辑：先value--，如果减完后value < 0，
 * 说明资源不够——进程把自己阻塞，放入等待队列。
 * value为负时，|value| = 等待队列中的进程数量。
 */
void P(Semaphore *S) {
    S->value--;                           // ① 先减再说
    if (S->value < 0) {                   // ② 减完发现不够
        block(current_process, S->wait_queue);  // ③ 睡觉，让CPU
    }
}

/* V操作（signal操作）：释放一个资源
 *
 * 逻辑：先value++，如果加完后value <= 0，
 * 说明还有进程在等这个资源——从队列中唤醒一个。
 * value <= 0（非 value < 0）的原因：
 * 如果加之前value = -1（有一个等待者），
 * 加之后value = 0——仍然 <= 0，说明需要唤醒一个人。
 */
void V(Semaphore *S) {
    S->value++;                           // ① 先还回去
    if (S->value <= 0) {                  // ② 还有人在等？
        wakeup(S->wait_queue);            // ③ 叫醒一个
    }
}

[UNIQUE INSIGHT] 很多人初学信号量时最困惑的点是S.value何时为负。这个设计是Dijkstra经过深思熟虑的：value为负时，|value|等于等待队列的长度——一个变量同时充当资源计数器和等待队列长度的指示器。这种信息压缩是早期系统设计中典型的"一鱼多吃"技巧。现代Linux内核的struct semaphore中，count的含义几乎完全一致，只是队列实现从简单的链表变成了红黑树（用于优先级继承）。

P和V操作会被OS实现为原语（Primitive）——通过关中断或硬件原子指令保证在执行期间不被打断。这样，应用程序使用信号量时就不需要自己处理原子性了。

用信号量实现互斥

Semaphore mutex = {1, empty_queue};  // 初始值为1（一把锁）

// 互斥访问临界区
P(&mutex);          // 拿锁：mutex.value 从1变0，成功进入
critical_section();  // value=0表示"锁已占用，无等待者"
V(&mutex);          // 放锁：mutex.value 从0变1

mutex.value的三种状态：1（空闲）、0（被占用且无等待者）、-N（被占用且有N个进程在排队）。

用信号量实现同步

同步的核心在于**“前V后P”**——先执行的进程在完成必要工作后执行V操作，后执行的进程在执行前先执行P操作：

Semaphore sync = {0, empty_queue};  // 初始值为0（没有可用"信号"）

// 进程P1：必须先完成的前驱任务
do_something_first();
V(&sync);           // sync.value 从0变1——"我完成了，你们可以走了"

// 进程P2：必须等P1完成后才能执行
P(&sync);           // sync.value 从1变0——"收到信号，开始干活"
do_something_after();

如果P2先于P1执行到P操作：sync.value从0变成-1，P2被阻塞。等P1执行V操作时，sync.value从-1变0（仍<=0），唤醒P2。这个看似简单的设计保证了无论调度顺序如何，正确的执行顺序都能得到保证。

经典同步问题：信号量的实战

学完工具，接下来是考研的重头戏——三个经典同步问题。我建议你先对着伪代码看懂逻辑，然后自己动手画出进程执行的时间线，这样才能真正理解PV操作之间的配合。

生产者-消费者问题

场景：一组生产者进程向一个容量为n的缓冲区放产品，一组消费者进程从缓冲区取产品。生产者不能往满的缓冲区放，消费者不能从空的缓冲区取，且同一时刻只能有一个进程操作缓冲区。

/* ===== 生产者-消费者问题的完整信号量解法 ===== */

Semaphore mutex = {1, empty_queue};   // 互斥信号量：保护缓冲区
Semaphore empty = {n, empty_queue};   // 同步信号量：缓冲区空位数
Semaphore full  = {0, empty_queue};   // 同步信号量：缓冲区产品数

/* ----- 生产者进程 ----- */
void producer() {
    while (1) {
        item = produce_item();        // ① 生产一个产品（在缓冲区之外）

        P(&empty);                    // ② 申请一个空位
                                      //    如果没有空位，阻塞在此
        P(&mutex);                    // ③ 申请缓冲区访问权限
                                      //    ★ 关键：先P(同步)再P(互斥)！

        buffer[in] = item;            // ④ 放入产品
        in = (in + 1) % n;           //    环形缓冲区

        V(&mutex);                    // ⑤ 释放缓冲区访问权限
        V(&full);                     // ⑥ 通知消费者"有新产品了"
    }
}

/* ----- 消费者进程 ----- */
void consumer() {
    while (1) {
        P(&full);                     // ① 申请一个产品（没有则阻塞）
        P(&mutex);                    // ② 申请缓冲区访问权限

        item = buffer[out];           // ③ 取出产品
        out = (out + 1) % n;

        V(&mutex);                    // ④ 释放缓冲区
        V(&empty);                    // ⑤ 通知生产者"有空位了"

        consume_item(item);           // ⑥ 消费产品（在缓冲区之外）
    }
}

为什么consume_item(item)要放在V操作之后、临界区之外？因为消费一个产品可能耗时很长（比如写入数据库、渲染界面），如果放在临界区内，会阻塞其他所有生产者和消费者。临界区只包含必须互斥的操作——对共享缓冲区的读写。

[PERSONAL EXPERIENCE] 在实际工程中，生产者-消费者的"缓冲区"大多不是简单的数组。比如Linux内核中的kfifo（内核FIFO缓冲）实现了无锁的单生产者-单消费者模式——当只有一方写入、一方读取时，它们可以通过维护各自的指针完全避开锁。但一旦引入多个生产者或多个消费者，就必须加锁。这种"特定场景无锁化"的优化思路，在理解了基础信号量模型后能直接迁移到工程中。

多生产者-多消费者：关注"产品类型"而非"生产者身份"

王道考研特别强调的一点：当遇到"多生产者-多消费者"问题时（比如父亲做苹果派、母亲做橙汁，女儿吃苹果派、儿子喝橙汁），不要被"谁生产了什么"迷惑。关键不是生产者是谁，而是生产了什么类型的产品。

每种产品类型对应一个full或empty信号量，互斥访问仍用同一个mutex。这种题型在408的PV操作大题中反复出现，出错率极高——就是因为很多人习惯性地按"进程身份"分信号量，而不是按"数据内容"分信号量。

读者-写者问题

场景：多个读者可以同时读共享数据（读不改变数据），但写者写时必须独占，且写时不能有读者在读。

这个问题的有趣之处在于"要不要让写者优先"——两种策略反映了对公平性和吞吐量的不同权衡：

/* ===== 读者-写者问题：读优先（公平版本） ===== */

Semaphore rw_mutex = {1, empty_queue};  // 写者与第一个读者竞争
Semaphore mutex    = {1, empty_queue};  // 保护 reader_count 的互斥访问
int reader_count = 0;                   // 当前有几个读者在临界区

/* ----- 读者进程 ----- */
void reader() {
    while (1) {
        P(&mutex);                      // ① 锁住 reader_count
        reader_count++;                 // ② 读者数量+1
        if (reader_count == 1) {        // ③ 如果是第一个读者
            P(&rw_mutex);              //    拦住写者
        }
        V(&mutex);                      // ④ 释放 reader_count

        read_data();                    // ⑤ 读书（多个读者可同时在此）

        P(&mutex);                      // ⑥ 锁住 reader_count
        reader_count--;                 // ⑦ 读者数量-1
        if (reader_count == 0) {        // ⑧ 如果是最后一个读者离开
            V(&rw_mutex);              //    释放写者
        }
        V(&mutex);                      // ⑨ 释放 reader_count
    }
}

/* ----- 写者进程 ----- */
void writer() {
    while (1) {
        P(&rw_mutex);                   // ① 和读者/其他写者抢锁
        write_data();                   // ② 独占写入
        V(&rw_mutex);                   // ③ 释放锁
    }
}

核心技巧是用reader_count实现"第一个读者拿锁，最后一个读者放锁"。这一对"先P后V"在不同进程中完成——这与普通的成对PV在同一个进程中的直觉不同，是学习信号量的一个重要认知突破。

写优先版本在考研中出现频率较低，其核心是引入额外信号量让写者在等待时阻塞后续读者的到来。思路类似排队——写者一到，新来的读者就排在后面，等当前在读的读者离开后写者写入，之后再放后面的读者进来。

哲学家进餐：如何防止死锁

场景：5个哲学家围坐圆桌，每人面前一碗面，两人之间一根筷子（共5根）。哲学家思考时不需筷子，饿了时拿起左右两根筷子吃饭，吃完放下。

如果每个人都拿起左边的筷子然后等右边的，所有人都拿了一根在等另一根——死锁。

三种防死锁策略（408重点考察）：

策略 实现方式 利弊
人数限制 最多允许4人同时尝试拿筷子 简单，保证至少一人能吃
奇偶编号 奇数哲学家先左后右，偶数先右后左 优雅，利用对称性破缺
必须一次拿两根 用mutex保护"拿筷子"这个动作 粗粒度锁，并发度低

[ORIGINAL DATA] 哲学家进餐问题不只是课本上的智力游戏。在真实系统中，数据库的死锁检测器本质上就是在检测"循环等待"——这与哲学家围成一圈的情况完全同构。PostgreSQL的deadlock_timeout默认设置为1秒，就是让系统周期性地"看看有没有哲学家饿死了"。

P空位信号量empty

有空位, empty.value > 0

无空位, empty.value = 0

生产者释放后Vempty唤醒

拿到锁

P满信号量full

有产品, full.value > 0

无产品, full.value = 0

生产者放入后Vfull唤醒

进程P1

缓冲区有空位?

P互斥信号量mutex

P1进入阻塞队列

放入产品

V互斥信号量mutex

V满信号量full

继续生产

进程P2消费者

缓冲区有产品?

P2进入阻塞队列

管程：让编译器替你维护互斥

信号量的阿喀琉斯之踵

信号量确实是天才的设计，但它有一个不可忽视的缺陷：PV操作的配对依赖于程序员的高度自律。忘写一个V操作、多写一个P操作、或者PV配错对象——任何一个小疏忽都会导致死锁或数据不一致，而编译器对此毫无察觉。1973年，Brinch Hansen在设计并发Pascal时提出了一种更好的编程模型。

管程的定义

**管程（Monitor）**是一种把共享数据、对数据的操作、以及互斥机制封装在一起的程序结构。程序员不需要手动调用P和V——编译器自动在每个过程入口加锁、出口解锁。

管程的四种组成：
┌─────────────────────────────┐
│  monitor 管程名 {            │
│                              │
│    ① 共享数据结构声明        │  ← 局部变量，外部不可直接访问
│    ② 一组操作过程            │  ← 每次只允许一个进程在其中执行
│    ③ 初始值                 │  ← 管程创建时设置
│    ④ 管程名                 │
│  }                           │
└─────────────────────────────┘

管程的互斥由编译器自动保证——任何时刻至多一个进程在管程内执行。但当进程在管程内发现自己需要的条件不满足（比如缓冲区已空），它不能在外面等（因为持有的锁会阻塞其他进程），也不能在里面等（它不走别人进不来）——条件变量就是为解决这个问题而生的。

条件变量：在管程内的优雅等待

/* 条件变量的两个操作 */
Condition x;

x.wait();   // 当前进程在条件x上阻塞，释放管程锁，让别人能进来
x.signal(); // 唤醒一个在条件x上等待的进程，被唤醒者重新竞争管程锁

注意：signal()是"通知一下"，不是"立即把CPU交给被唤醒的人"。管程内执行signal后通常会让被唤醒者执行——这取决于管程的具体语义（Hoare语义 vs Mesa语义）。

用管程解决生产者-消费者

monitor ProducerConsumer {
    /* 共享数据 */
    int buffer[N];
    int count = 0;           // 缓冲区产品数
    int in = 0, out = 0;     // 读写指针

    /* 条件变量 */
    Condition not_full;      // "缓冲区没满"这个条件
    Condition not_empty;     // "缓冲区没空"这个条件

    /* 生产者调用的过程 */
    void insert(item) {
        if (count == N) {            // 缓冲区满了吗？
            not_full.wait();         // 满了就等——管程锁会被释放
        }
        buffer[in] = item;           // 放入产品
        in = (in + 1) % N;
        count++;
        not_empty.signal();          // 通知等待的消费者
    }

    /* 消费者调用的过程 */
    item remove() {
        if (count == 0) {            // 缓冲区空了吗？
            not_empty.wait();        // 空了就等
        }
        item = buffer[out];          // 取出产品
        out = (out + 1) % N;
        count--;
        not_full.signal();           // 通知等待的生产者
        return item;
    }
};

对比信号量版本，管程版本最关键的变化是：if(count==N) wait()这种条件检查现在和缓冲区修改操作在同一个受保护的作用域中——编译器确保不会有进程在检查和等待之间被中断。而信号量版本中，你必须手动保证PV的配对逻辑。

Java中的synchronized关键字实现的就是管程模型——每个Java对象的wait()/notify()/notifyAll()就是条件变量的三种操作，synchronized代码块就是管程的"每次只允许一个线程执行"的约束。

[INTERNAL-LINK: 死锁的预防与检测 → 死锁的四个必要条件与银行家算法]

四种方案全景对比

维度 软件方案（Peterson） 硬件方案（TS/Swap） 信号量（记录型） 管程
互斥保证 正确（单CPU） 正确 正确 编译器自动保证
让权等待 不满足（忙等） 不满足（忙等） 满足（阻塞） 满足（wait释放锁）
适用CPU 仅单CPU 单CPU+多CPU 单CPU+多CPU 单CPU+多CPU
实现复杂度 低（几行代码） 低（一条指令） 中（P/V原语） 高（语言/运行时支持）
死锁风险 低 低 高（PV错配） 中（嵌套管程）
并发度 低（仅2进程） 低（一把全局锁） 高（可定义多种资源） 高（条件变量精确通知）
典型应用 教学演示 内核自旋锁 Linux内核信号量 Java synchronized
408考点重要性 ★★★☆☆ ★★☆☆☆ ★★★★★ ★★★★☆

Citation Capsule

Brinch Hansen, P. (1973). “Operating System Principles.” Prentice-Hall. 管程概念的首次系统化阐述。

Hoare, C. A. R. (1974). “Monitors: An Operating System Structuring Concept.” Communications of the ACM, 17(10), 549-557. 管程语义的经典论文（Hoare语义由此得名）。

Lampson, B. W., & Redell, D. D. (1980). “Experience with Processes and Monitors in Mesa.” Communications of the ACM, 23(2), 105-117. Mesa语义的工程实践报告——Java的管程就是走Mesa路线。

常见陷阱：PV操作顺序引发的死锁

[ANSWER-FIRST] 在生产者-消费者问题中，如果将P操作的顺序写反——先P(mutex)再P(empty)——必然导致死锁。

错误代码

/* ===== 生产者：错误的P操作顺序 ===== */
void producer_wrong() {
    while (1) {
        produce_item();
        P(&mutex);      // ① 先拿互斥锁 ← 错误！
        P(&empty);      // ② 再申请空位

        buffer[in] = item;
        in = (in + 1) % n;

        V(&mutex);
        V(&full);
    }
}

死锁场景推演

假设缓冲区已满（empty.value = 0，full.value = n）：

  1. T1时刻：生产者P1执行P(&mutex)——mutex.value从1变0（拿到锁）
  2. T1时刻：生产者P1执行P(&empty)——empty.value从0变-1，P1被阻塞在empty信号量上
  3. T2时刻：消费者C1想进入临界区取产品，执行P(&mutex)——但mutex.value=0，C1被阻塞！
  4. 死锁形成：
    • P1在等consumer释放empty（即取走一个产品）
    • C1在等P1释放mutex（即退出临界区）
    • 但P1在临界区内等着，C1进不去——相互等待，死锁达成

正确顺序背后的原理

需要资源时：  先问"有没有资源"（P(同步信号量)）
              再问"能不能碰"（P(互斥信号量)）

释放资源时：  先把东西放回去（V(互斥信号量)）
              再广播"资源有了"（V(同步信号量)）

V操作的顺序反了通常不致命——但会降低效率。如果先V(同步信号量)再V(互斥信号量)，被唤醒的进程会立刻发现互斥锁还没释放，又得等一次调度。先V互斥再V同步是一种好习惯——虽然对正确性没有硬性影响。

延伸：还有哪些容易写错的PV场景

  • 多次P同一个信号量而没有对应次数的V：资源被永久消耗
  • 在if而不是while中检查条件：虚假唤醒（spurious wakeup）会让条件检查失效——管程中尤其重要，这就是为什么Java文档明确要求wait()必须放在while循环里
  • 忘记初始化信号量：互斥信号量初始值不是1，同步信号量初始值不是0——一步错步步错

实践建议与应试技巧

  • 画时间轴：PV大题的标准解法不是脑算，而是画一条时间轴，把每个进程的操作和信号量值变化标上去。value的每次变化——特别是从0变-1或从-1变0的时刻——是推演进程阻塞和唤醒的关键节点。
  • 先定数据结构再写代码：看到一道同步问题，先确定有几类进程（按数据流关系分，不按进程名分）、有几块共享数据、然后给每种共享约束分配一个信号量。
  • 互斥信号量作用域最小化：mutex包裹的区域只包含共享数据的读写操作，耗时的计算或I/O放到临界区之外。
  • 管程题答法：如果题目明确要求用管程实现，不要写成信号量——管程不用手动PV，重点是定义共享变量、条件变量和public过程。
  • 死锁判断的快速方法：画出每个进程持有和等待的资源图，如果图中存在环路，则必然死锁。

[INTERNAL-LINK: 进程调度算法与上下文切换 → 调度时机、抢占与非抢占]

总结

从软件互斥到信号量再到管程，操作系统同步机制的演进揭示了软件工程中一个反复出现的主题：把并发控制从程序员的"手艺活"变成编译器或运行时的"自动化服务"。

三种机制各司其职：信号量是灵活的原语——适合需要精细控制资源计数的场景；管程是安全的框架——适合以数据结构为中心、逻辑规整的并发场景；而硬件原子指令则是所有上层机制的基石——Linux内核用自旋锁保护短临界区、用信号量保护较长的临界区、用RCU处理读多写少的场景，这套分层体系从Dijkstra时代延续至今，依然是现代并发系统的骨架。

掌握信号量不是为了让你手写并发库——在那个层面上，现代语言已经有了更高级的抽象。但理解信号量才能理解这些高级抽象为什么被设计成现在这样，才能在遇到并发Bug时从第一性原理出发追溯根因。

FAQ

Q1: 信号量的value为负代表什么？

value为负时，|value|等于在该信号量上阻塞等待的进程数量。例如value=-3，表示有3个进程因为该信号量代表的资源不足而被阻塞。value为0表示资源刚好被分配完但没有等待者。这是记录型信号量区别于整型信号量的关键特征。

Q2: P和V操作为什么必须是原语？

如果P操作的"检查value"和"修改value"两步之间发生了进程切换，另一个进程可能读到旧的value值，导致两个进程同时认为资源可用——这就是双标志先检查法的翻版。原语保证这两步不可分割，避免了竞态条件。

Q3: Peterson算法在现代CPU上还有效吗？

在不加内存屏障（memory barrier）的情况下，现代CPU的乱序执行可能将store指令重排到load指令之后，导致两个进程同时看到对方的flag为false。真实系统中，Peterson算法需要配合mfence（x86）或dmb（ARM）指令使用，但这会抵消它作为"纯软件方案"的优势。所以现代系统直接用硬件原子指令。

Q4: 信号量和互斥锁有什么区别？

互斥锁可以看作value只有0和1的二值信号量，但信号量的能力远超于此：它可以表示任意数量的资源（如缓冲区空位数），也可以用于实现复杂的同步约束（如"进程A必须在进程B之前执行"）。互斥锁只管"互斥"，信号量同时管"互斥"和"同步"。

Q5: 管程消除了死锁吗？

管程没有消除死锁。嵌套管程调用仍可能导致死锁——比如管程A调用管程B的过程，而管程B又回调管程A。但管程通过编译器自动加锁解锁，消除了程序员遗漏PV配对导致的死锁——这是信号量方案中最高频的人为错误。

延伸阅读

  • Dijkstra, E. W. (1965). “Cooperating Sequential Processes.” — 信号量概念的原始论文，操作系统领域的奠基性文献
  • Brinch Hansen, P. (1973). “Operating System Principles.” — 管程概念首次系统化阐述
  • Hoare, C. A. R. (1974). “Monitors: An Operating System Structuring Concept.” CACM, 17(10). — Hoare语义的权威定义
# 操作系统
Logo
openEuler 社区

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐

cover

Electron 打印原理深度解析-Day07

avatar openEuler 社区

vLLM 与 SGLang 推理框架性能横评

核心创新：PagedAttention 机制，类比操作系统虚拟内存管理，解决 KV Cache 内存碎片化问题。设计目标：最大化吞吐量，优化多用户、高并发场景下的服务效率。主要特性：连续批处理（Continuous Batching）、高效的内存管理、与 OpenAI API 兼容。技术趋势：注意力机制优化、计算与通信重叠、量化与稀疏化推理。框架演进方向：vLLM 对更复杂工作流的支持；SGLan

avatar openEuler 社区
cover

2018二级C语言编程软件

avatar openEuler 社区