操作系统｜进程同步八股文详解：从临界区到死锁的完整知识体系

油墨香^_^

66人浏览 · 2026-09-19 14:54:35

油墨香^_^ · 2026-09-19 14:54:35 发布

引言：为什么进程同步是操作系统面试的必考点

在操作系统这门课程中，进程同步几乎贯穿了并发编程的全部核心概念：临界区、互斥、信号量、管程、死锁、经典同步问题等。无论是校招面试、考研复试，还是日常后端开发中处理多线程竞争，进程同步都是绕不开的高频考点。本文将以“八股文”的方式，系统梳理进程同步的知识脉络，从最基本的概念出发，逐步深入到经典算法、信号量机制、管程模型以及死锁处理，并配以大量 C 语言代码示例，帮助你建立完整的知识体系。

本文的结构安排如下：首先介绍进程同步的动机与核心概念，包括并发、竞态条件、临界资源和临界区；接着讨论解决临界区问题的软件方法和硬件方法；然后重点讲解信号量机制及其在经典同步问题中的应用；随后引入管程这一高级同步机制；最后讨论死锁的成因、检测、避免和预防策略，并总结常见面试题与易错点。建议读者边阅读边手写关键代码，做到“能讲清原理、能写出代码、能分析边界情况”。

一、进程同步的基本概念

1.1 并发与并行的区别

并发（Concurrency）和并行（Parallelism）是两个容易混淆的概念。并发指多个任务在同一个时间段内交替执行，强调逻辑上的“同时进行”；并行指多个任务在同一个时刻真正同时执行，强调物理上的“同时进行”。在单核 CPU 上，多个进程通过时间片轮转实现并发，任意时刻只有一个进程真正运行；在多核 CPU 上，多个进程可以分别在不同的核心上运行，从而实现真正的并行。

理解这一点对进程同步非常重要：同步问题既可能出现在单核并发场景，也可能出现在多核并行场景。单核上的并发虽然任意时刻只有一个进程在运行，但由于上下文切换可能发生在任意指令之间，仍然可能产生竞态条件；多核上则因为多个核心真正同时访问共享数据，竞争更加激烈。

1.2 竞态条件

竞态条件（Race Condition）是指多个进程并发访问和操作同一份共享数据，而最终结果依赖于这些进程执行的相对顺序或精确时序。由于操作系统的调度具有不确定性，多个进程的执行顺序无法预知，因此程序在存在竞态条件时可能出现不可复现、间歇性的错误。

举一个经典的例子：两个进程同时执行 count++ 操作。在机器指令层面，这个看似简单的自增通常分为三步：将 count 的值从内存读入寄存器；寄存器值加一；将新值写回内存。如果进程 A 读完值后、写回前被切换出去，进程 B 也读取了旧值并加一，那么最终两个进程各执行一次自增，count 却只增加了 1，这就是典型的竞态条件。

// 共享变量
int count = 0;

// 进程 A 与进程 B 都执行如下操作
// 逻辑上希望 count 加两次
count++;
// 机器指令层面：
// 1. tmp = count
// 2. tmp = tmp + 1
// 3. count = tmp

竞态条件的危害在于其偶发性：错误只在特定交错顺序下出现，难以复现和调试。因此，操作系统必须提供同步机制，保证多个进程对共享数据的访问是互斥的、有序的。

1.3 临界资源

临界资源（Critical Resource）是指一次只允许一个进程使用的资源。它可以是硬件设备（如打印机、磁带机），也可以是软件资源（如全局变量、共享缓冲区、文件）。临界资源的特点是排他性，多个进程必须互斥地访问，否则会破坏资源状态的一致性。

1.4 临界区及其四个条件

每个进程访问临界资源的代码段称为临界区（Critical Section）。进入临界区之前需要检查是否可以进入的代码称为进入区（Entry Section）；离开临界区之后用于释放资源、唤醒等待进程的代码称为退出区（Exit Section）；其余代码称为剩余区（Remainder Section）。

一个好的临界区解决方案必须同时满足以下四个条件：

互斥（Mutual Exclusion）：任意时刻至多一个进程进入临界区。
前进（Progress）：当没有进程在临界区中，且有进程希望进入临界区时，应能够选出并让一个进程进入，不能无限期推迟；选择过程不能只由剩余区中的进程决定。
有限等待（Bounded Waiting）：从某个进程申请进入临界区到它真正进入，其他进程进入临界区的次数必须有限，即该进程不能永远等待。
让权等待（等待的进程不占用 CPU）：进程暂时无法进入临界区时，应释放 CPU 进入阻塞态，而不是忙等。这一条件有时被单独提出，用于区分“忙等待”和“让权等待”两大类方案。

条件	含义	违反时的后果
互斥	同一时刻只有一个进程在临界区	数据被破坏，出现竞态
前进	临界区空闲时能选出进程进入	死锁或饥饿
有限等待	进程等待进入的时间有限	饥饿
让权等待	等不到时不占用 CPU	CPU 空转，忙等浪费

二、软件同步方法

2.1 单标志法（严格轮换）

单标志法又称严格轮换法（Strict Alternation），是最早尝试解决互斥问题的方法之一。它设置一个共享的整数变量 turn，turn 的值表示当前允许哪个进程进入临界区。进程在进入区中不断检查 turn 是否等于自己的编号，若不等于则忙等；离开临界区时将 turn 修改为对方的编号。

int turn = 0; // 0 表示允许进程 0 进入，1 表示允许进程 1 进入

// 进程 0
while (1) {
    while (turn != 0);   // 进入区：忙等
    critical_section();   // 临界区
    turn = 1;             // 退出区：把使用权交给进程 1
    remainder_section();  // 剩余区
}

// 进程 1
while (1) {
    while (turn != 1);   // 进入区
    critical_section();   // 临界区
    turn = 0;             // 退出区
    remainder_section();  // 剩余区
}

单标志法可以保证互斥，但存在严重缺陷：它强制两个进程轮流进入临界区。如果进程 0 的临界区执行频率远高于进程 1，进程 1 在使用完临界区后长时间停留在剩余区，那么 turn 停留在 0，进程 0 虽然想进入临界区却因为 turn 已经等于 0 而顺利进入；但如果进程 1 是那种进入一次临界区后就不再进入的进程，进程 0 在第二次想进入时就会因为 turn 被置为 1 而永远阻塞。这违反了“前进”条件：即使临界区空闲且只有进程 0 想进入，也无法进入。

2.2 双标志先检查法

双标志先检查法为每个进程设置一个布尔标志 flag，表示该进程是否想进入临界区。进程在进入区先检查对方是否想进入，若对方不想进入，则把自己的 flag 置为 true 并进入临界区；若对方想进入，则忙等。离开临界区时把自己的 flag 置为 false。

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

// 进程 0
while (1) {
    while (flag[1]);      // 先检查对方是否想进入
    flag[0] = true;       // 再表达自己想进入
    critical_section();   // 临界区
    flag[0] = false;      // 退出区
    remainder_section();
}

// 进程 1
while (1) {
    while (flag[0]);
    flag[1] = true;
    critical_section();
    flag[1] = false;
    remainder_section();
}

该方法的问题在于“检查”和“置位”两个动作不是原子的。进程 0 检查到 flag[1] 为 false 后、尚未执行 flag[0] = true 之前，进程 1 也检查到 flag[0] 为 false，于是两个进程都认为自己可以进入，从而同时进入临界区，互斥被破坏。

2.3 双标志后检查法

针对先检查法的问题，后检查法把顺序颠倒：先把自己的 flag 置为 true，再去检查对方是否也想进入。如果双方都表达了进入意愿，则出现“谁也进不去”的局面，违背了“前进”条件。更严重的是，如果两个进程几乎同时置位，然后互相检查到对方为 true，就会陷入无限等待，造成死锁。

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

// 进程 0
while (1) {
    flag[0] = true;       // 先表达自己想进入
    while (flag[1]);      // 再检查对方
    critical_section();
    flag[0] = false;
    remainder_section();
}

// 进程 1 对称

2.4 Peterson 算法

Peterson 算法由 Gary L. Peterson 于 1981 年提出，它结合了单标志法和双标志法的思想，用一个 turn 变量解决“谦让”问题、用 flag 数组表达“意愿”，能够同时满足互斥、前进和有限等待三个条件，被广泛认为是软件解决临界区问题的经典算法。

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

// 进程 i（i 为 0 或 1），j 为对方编号
while (1) {
    flag[i] = true;       // 表达进入意愿
    turn = j;             // 谦让：把优先权给对方
    while (flag[j] && turn == j);  // 对方想进入且轮到对方时忙等
    critical_section();   // 临界区
    flag[i] = false;      // 退出区
    remainder_section();
}

Peterson 算法的正确性可以从三个方面理解。互斥性：假设两个进程同时进入临界区，那么必然有 P0 观察到 flag[1] == false 或 turn == 0，P1 观察到 flag[0] == false 或 turn == 1。由于两个进程都在临界区内，它们必然都执行过 flag 置位，所以 flag 都为真，于是 P0 必须在 turn == 0 时才能进入，P1 必须在 turn == 1 时才能进入，而 turn 不可能同时等于 0 和 1，矛盾，因此互斥成立。前进性：如果临界区空闲，想进入的进程在 while 循环处最多等对方执行完临界区后置 flag 为 false。有限等待：以进程 i 为例，它最多等待对方进入一次临界区，因为 i 置 turn = j 后，j 进入一次临界区退出时会发现 turn 已经是 i（若 i 再次运行则置 turn = j……实际上结合 turn 的语义，进程不会无限等待）。

需要注意的是，Peterson 算法在现代多核体系结构下可能会因为编译器优化和 CPU 乱序执行而失效，通常需要配合内存屏障。面试中一般考察其逻辑正确性，以及为何它能同时满足三个条件，而单纯的单标志法或双标志法做不到。

2.5 Dekker 算法与面包店算法

Dekker 算法是更早提出的双进程互斥算法（1965 年），它把严格轮换和意愿标志结合起来，并引入了“对方正在临界区时自己等待、对方没有意愿时自己抢占”的复杂逻辑。Dekker 算法同样能满足互斥、前进和有限等待，但其实现更加繁琐。

面包店算法（Bakery Algorithm）由 Lamport 提出，用于解决多进程互斥。它模拟了面包店取号排队的过程：每个进程进入时领取一个号码，号码取当前所有号码中的最大值加一；号码最小的进程进入临界区；如果两个进程号码相同，则按进程编号较小的先进入。该算法不需要硬件原子指令，是纯软件的多进程互斥方案。

bool choosing[N] = { false };
int number[N] = { 0 };
// 进程 i
choosing[i] = true;
number[i] = max(number[0..N-1]) + 1;
choosing[i] = false;
for (int j = 0; j < N; j++) {
    while (choosing[j]);              // 等对方取号完成
    while (number[j] != 0 &&
           (number[j] < number[i] ||
            (number[j] == number[i] && j < i)));  // 号码小者优先
}
critical_section();
number[i] = 0;

软件方法的共同缺点是都需要忙等待，进程无法进入临界区时消耗大量 CPU 时间。因此在现代操作系统中，实际更多采用硬件提供的原子指令或内核提供的同步原语。

三、硬件同步方法

3.1 中断屏蔽

在单 CPU 系统中，进程切换由时钟中断等中断事件触发。如果在进入临界区之前关中断，在执行临界区期间就不会发生进程切换，从而保证临界区的原子执行。离开临界区后再开中断即可。

void lock() {
    disable_interrupts();  // 关中断
}

void unlock() {
    enable_interrupts();   // 开中断
}

中断屏蔽法的优点是简单高效，但它存在明显局限：第一，关中断会影响系统的时钟和 I/O 响应，若临界区代码较长则风险很大；第二，它只适用于单 CPU 系统，在多 CPU 系统中，关掉一个 CPU 的中断并不能阻止其他 CPU 上的进程访问共享数据；第三，用户态程序通常无法直接执行关中断指令，因此该机制只能用于内核态。

3.2 Test-and-Set 指令

Test-and-Set（TS）是一条由硬件提供的原子指令。它读取指定内存单元的值，并将该单元置为 1（或 true），整个“读-写”过程不可被中断，是一条不可分割的机器指令。TS 指令常用于实现自旋锁（Spin Lock）。

// 硬件原子指令的伪代码
bool test_and_set(bool *target) {
    bool old = *target;
    *target = true;   // 无论原先是什么，都置为 true
    return old;       // 返回旧值
}

bool lock = false;
void acquire() {
    while (test_and_set(&lock));  // 若 lock 原先为 true，则忙等
}
void release() {
    lock = false;
}

TS 指令的意义在于把“检查锁状态”和“上锁”两个动作合并为一个原子操作，从而避免了软件方法中检查与置位之间被切换的问题。多个进程同时执行 test_and_set 时，硬件保证只有一个进程能读到 false 并成功上锁，其余进程都读到 true 并继续忙等。这种锁称为自旋锁，其缺点是忙等，适用于临界区很短、竞争不太激烈的场景（如内核中保护数据结构）。

3.3 Swap / Exchange 指令

Swap 指令（也称 Exchange 或 XCHG）也是硬件原子指令，它交换两个内存单元的值。其典型用法是：每个进程持有一个局部变量 key，初始为 true；不断用 key 与全局锁变量交换。若交换后 key 为 false，说明进程拿到了锁，可以进入临界区；否则说明锁被占用，继续交换等待。

// 硬件原子指令：交换 a、b 两个地址的值
void swap(bool *a, bool *b) {
    bool tmp = *a;
    *a = *b;
    *b = tmp;
}

bool lock = false;
void acquire() {
    bool key = true;
    while (key) {
        swap(&lock, &key);  // 交换后，若 key 变 false 则获得锁
    }
}
void release() {
    lock = false;
}

3.4 Compare-and-Swap 指令

Compare-and-Swap（CAS）指令比 Test-and-Set 更通用。它比较目标地址的当前值与期望值，若相等则把新值写入目标地址，否则不写入。整个过程原子完成，并返回目标地址的旧值（或比较结果）。CAS 是现代并发编程中无锁数据结构（如无锁队列、原子计数器）的基础。

// 原子操作：若 *addr == expected，则 *addr = new_value
int compare_and_swap(int *addr, int expected, int new_value) {
    int old = *addr;
    if (old == expected) {
        *addr = new_value;
    }
    return old;  // 返回旧值
}

int lock = 0;                // 0 表示未加锁，1 表示已加锁
void acquire() {
    while (compare_and_swap(&lock, 0, 1) != 0);  // 尝试把 0 改成 1
}
void release() {
    lock = 0;
}

硬件方法的共同优点是原子性由硬件保证，能可靠地实现互斥；缺点是存在忙等待。为克服忙等待，操作系统在这些原子指令之上构建了更高级的同步原语，即信号量和管程，它们能在进程无法进入临界区时将其阻塞，实现让权等待。

四、信号量机制

4.1 整型信号量

信号量（Semaphore）由 Dijkstra 于 1965 年提出，是操作系统中最重要的同步原语。整型信号量本质上是一个用于表示资源数量的整数变量，只能通过两个原子操作来访问：P 操作（也称 wait 操作、荷兰语 Proberen“尝试”）和 V 操作（也称 signal 操作、荷兰语 Verhogen“增加”）。

int S = 1;  // 整型信号量

// P 操作：等待资源
void P() {
    while (S <= 0);  // 忙等
    S--;
}

// V 操作：释放资源
void V() {
    S++;
}

整型信号量虽然实现了互斥，但 P 操作中使用了 while 忙等，没有做到让权等待。当多个进程竞争同一资源时，等待进程会空耗 CPU。

4.2 记录型信号量

为了克服忙等问题，记录型信号量在整型信号量的基础上增加了一个等待队列。当资源不足时，执行 P 操作的进程不再忙等，而是把自己放入等待队列并阻塞，主动放弃 CPU；当资源释放时，V 操作从等待队列中唤醒一个进程。

typedef struct {
    int value;            // 可用资源数量
    struct process *list; // 等待该信号量的进程链表
} semaphore;

void P(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // 资源不足，阻塞自己并加入等待队列
        block(S->list);
    }
}

void V(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // 仍有进程在等待，唤醒一个
        wakeup(S->list);
    }
}

记录型信号量中，value 的绝对值表示等待该信号量的进程数量。若 value 为正，表示还有可用资源；若 value 为 0，表示资源耗尽且无等待者；若 value 为负，表示有 |value| 个进程被阻塞等待。多个进程同时执行 P、V 操作时，这些操作必须是原子的，通常由硬件原子指令或关中断保证。

4.3 P、V 操作的语义与使用原则

P 操作表示“申请一个资源”或“等待某个条件成立”，V 操作表示“释放一个资源”或“通知某个条件已满足”。在互斥场景下，信号量初值通常为 1，表示临界区同一时刻只允许一个进程进入；在资源计数场景下，初值为资源的初始数量；在同步场景下，初值为 0，用于实现“先做某事才能做另一件事”的先后顺序。

使用场景	信号量初值	P/V 位置
互斥访问临界区	1	进入临界区前 P，离开后 V
管理有限资源	资源数量	申请资源时 P，使用完毕 V
同步（先 A 后 B）	0	被等待方完成后 V，等待方开始前 P

4.4 利用信号量实现前驱关系

信号量可以描述进程之间的前驱图（Precedence Graph）。对于每一对前驱关系，设置一个初值为 0 的信号量；前驱节点在完成本阶段工作后对该信号量执行 V 操作，后继节点在执行本阶段工作前对该信号量执行 P 操作。这样就能保证后继节点必须等前驱节点完成后才能开始。

semaphore S1 = 0, S2 = 0, S3 = 0;

// 进程 P1：先执行
void P1() {
    do_job1();
    V(S1);   // 通知 P2
    do_job2();
    V(S2);   // 通知 P3
}

// 进程 P2：等待 P1 的 job1 完成
void P2() {
    P(S1);
    do_job3();
    V(S3);   // 通知 P3
}

// 进程 P3：等待 P1 的 job2 和 P2 的 job3
void P3() {
    P(S2);
    P(S3);
    do_job4();
}

4.5 AND 型信号量与信号量集

在某些场景下，一个进程需要同时获得多个资源才能继续执行，如果分别用 P 操作申请，可能因为申请顺序不当而陷入死锁。AND 型信号量（也称同时 P 操作）一次性地申请多个资源，要么全部成功，要么一个都不占用地阻塞等待，避免了“占着一部分等另一部分”的死锁风险。

// AND 型 P：同时申请多个资源
void SP(semaphore *S1, semaphore *S2, ..., semaphore *Sn) {
    if (S1->value >= 1 && S2->value >= 1 && ... && Sn->value >= 1) {
        for (int i = 0; i < n; i++) {
            Si->value--;
        }
    } else {
        // 把自己放入第一个资源不足的信号量等待队列，并阻塞
    }
}

信号量集机制是对 AND 型信号量的推广，它为每个资源设置一个需求下限值和需求上限值。P 操作时检查每个资源的可用数量是否都不低于其下限值，若满足则一次性申请所需数量；V 操作则一次性归还所有申请的资源。这种机制常被用于实现资源的批量分配与控制。

五、经典进程同步问题

5.1 生产者-消费者问题

生产者-消费者问题是进程同步中最经典的模型。一组生产者进程不断生产产品放入缓冲区，一组消费者进程不断从缓冲区取出产品消费。缓冲区的大小有限（假设为 n），当缓冲区满时生产者必须等待，当缓冲区空时消费者必须等待。此外，多个进程对缓冲区的访问必须互斥。

该问题需要三个信号量：互斥信号量 mutex（初值 1，保护缓冲区操作）、同步信号量 empty（初值 n，表示空缓冲区的数量）和 full（初值 0，表示满缓冲区的数量）。

#define N 10
semaphore mutex = 1;   // 互斥访问缓冲区
semaphore empty = N;   // 空缓冲区数量
semaphore full = 0;    // 满缓冲区数量

// 生产者
void producer() {
    while (1) {
        item = produce();   // 生产产品
        P(empty);           // 申请空缓冲区，满则阻塞
        P(mutex);           // 进入临界区
        put_item(item);     // 放入缓冲区
        V(mutex);           // 离开临界区
        V(full);            // 满缓冲区数量加一，唤醒消费者
    }
}

// 消费者
void consumer() {
    while (1) {
        P(full);            // 申请满缓冲区，空则阻塞
        P(mutex);           // 进入临界区
        item = get_item();  // 取出产品
        V(mutex);           // 离开临界区
        V(empty);           // 空缓冲区数量加一，唤醒生产者
        consume(item);      // 消费产品
    }
}

这段代码中 P、V 操作的顺序至关重要。生产者必须先 P(empty) 再 P(mutex)，如果顺序颠倒，当缓冲区满时，生产者先 P(mutex) 成功进入临界区，再 P(empty) 失败而阻塞，此时消费者因为无法 P(mutex) 进入临界区取出产品，也就无法执行 V(empty) 唤醒生产者，形成死锁。同一个进程内 P(mutex) 与 V(mutex) 必须成对出现，且分别在临界区的首尾。

5.2 读者-写者问题

读者-写者问题描述了一个共享数据区，多个读者可以同时读，但当有写者在写时，其他读者和写者都不能访问；写者之间也必须互斥。该问题存在多种变体，常见的有“读者优先”和“写者优先”以及“读写公平”。

读者优先的解法使用互斥信号量 rw（初值 1，用于读写互斥和写写互斥），并用一个计数器 read_count 记录当前读者数量，再用一个互斥信号量 mutex（初值 1）保护 read_count 的修改。

semaphore rw = 1;      // 读写互斥
semaphore mutex = 1;   // 保护 read_count
int read_count = 0;

// 读者
void reader() {
    while (1) {
        P(mutex);
        read_count++;
        if (read_count == 1)   // 第一个读者进入前，禁止写者
            P(rw);
        V(mutex);
        read();                // 读数据
        P(mutex);
        read_count--;
        if (read_count == 0)   // 最后一个读者离开后，允许写者
            V(rw);
        V(mutex);
    }
}

// 写者
void writer() {
    while (1) {
        P(rw);      // 与读者和其他写者互斥
        write();    // 写数据
        V(rw);
    }
}

读者优先策略的问题在于：如果读者源源不断地到来，写者可能被饿死，因为只要仍有读者在读，写者就无法获得 rw。为解决这个问题，可以引入写者优先或公平策略。写者优先的常见做法是再增加一个信号量，使新来的读者在已有写者等待时不能进入，从而避免读者无限插队。

semaphore rw = 1;       // 读写互斥
semaphore mutex1 = 1;   // 保护 read_count
semaphore mutex2 = 1;   // 保护 write_count
semaphore w = 1;        // 写者优先控制
int read_count = 0;
int write_count = 0;

// 读者
void reader() {
    while (1) {
        P(w);            // 若有写者等待，读者在此阻塞
        P(mutex1);
        read_count++;
        if (read_count == 1)
            P(rw);
        V(mutex1);
        V(w);
        read();
        P(mutex1);
        read_count--;
        if (read_count == 0)
            V(rw);
        V(mutex1);
    }
}

// 写者
void writer() {
    while (1) {
        P(mutex2);
        write_count++;
        if (write_count == 1)
            P(w);        // 第一个写者到来后，阻止新读者
        V(mutex2);
        P(rw);
        write();
        V(rw);
        P(mutex2);
        write_count--;
        if (write_count == 0)
            V(w);        // 最后一个写者离开后，放行读者
        V(mutex2);
    }
}

5.3 哲学家进餐问题

哲学家进餐问题由 Dijkstra 提出：五个哲学家围坐在一张圆桌旁，每两个哲学家之间有一根筷子，共五根筷子。哲学家平时思考，饥饿时拿起左右两根筷子进餐，吃完放下筷子继续思考。每根筷子同一时间只能被一个哲学家使用。如果每个哲学家都同时拿起自己左边的筷子，再等待右边的筷子，就会形成循环等待，导致死锁。

解法一（限制人数）：利用信号量限制同时进餐的哲学家最多为四个，这样至少有一个哲学家能同时拿到两根筷子。

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore limit = 4;    // 最多允许 4 个哲学家同时就餐

void philosopher(int i) {
    while (1) {
        think();
        P(limit);
        P(chopstick[i]);                    // 拿左边筷子
        P(chopstick[(i + 1) % 5]);          // 拿右边筷子
        eat();
        V(chopstick[i]);
        V(chopstick[(i + 1) % 5]);
        V(limit);
    }
}

解法二（奇偶法）：规定奇数号哲学家先拿左边筷子再拿右边筷子，偶数号哲学家先拿右边筷子再拿左边筷子，破坏循环等待条件。解法三（一次性拿两根）：只有左右两根筷子都可用时才拿起，即 AND 型信号量。解法四（可用管程实现，见后文）。

5.4 吸烟者问题

吸烟者问题涉及一个供应者和三个吸烟者。桌子上有三种材料：烟草、纸和火柴。吸烟者 A 拥有烟草，需要纸和火柴；吸烟者 B 拥有纸，需要烟草和火柴；吸烟者 C 拥有火柴，需要烟草和纸。供应者每次随机地在桌上放两种材料，拥有剩下那种材料的吸烟者完成吸烟后，向供应者发出信号。

该问题需要正确表达供给与消费的同步关系，常用一个互斥信号量保护桌面，以及三个同步信号量分别通知三类吸烟者。

semaphore desk = 1;      // 桌面互斥
semaphore offer1 = 0;    // 通知吸烟者 1（有纸和火柴）
semaphore offer2 = 0;    // 通知吸烟者 2（有烟草和火柴）
semaphore offer3 = 0;    // 通知吸烟者 3（有烟草和纸）
semaphore finish = 0;    // 吸烟完成信号

void supplier() {
    while (1) {
        int i = random() % 3;   // 随机选一种组合
        P(desk);
        if (i == 0) {
            put_paper_and_match();
            V(offer1);
        } else if (i == 1) {
            put_tobacco_and_match();
            V(offer2);
        } else {
            put_tobacco_and_paper();
            V(offer3);
        }
        V(desk);
        P(finish);   // 等待吸烟者吸完
    }
}

void smoker1() {   // 拥有烟草，需要纸和火柴
    while (1) {
        P(offer1);
        take_paper_and_match();
        V(desk);        // 补充说明：不同教材桌面互斥处理略有差异
        smoke();
        V(finish);
    }
}

5.5 理发师问题

理发师问题描述一个理发店：店里有若干把理发椅和一个等候区（有若干座位）。没有顾客时理发师睡觉；顾客到来时，若有空理发椅则唤醒理发师理发，若理发椅都忙但等候区有空位则坐下等待，若等候区也满了则离开。这个问题综合考察了对资源计数、互斥和同步的理解。

#define CHAIRS 5    // 等候区座位数
semaphore customers = 0;   // 等待理发的顾客数（不包含正在理发者）
semaphore barbers = 0;     // 空闲理发师数量
semaphore mutex = 1;       // 保护 waiting 变量
int waiting = 0;           // 等候区中等待的顾客数

void barber() {
    while (1) {
        P(customers);      // 无顾客则睡觉（阻塞）
        P(mutex);
        waiting--;
        V(barbers);        // 通知顾客可以理发
        V(mutex);
        cut_hair();
    }
}

void customer() {
    P(mutex);
    if (waiting < CHAIRS) {
        waiting++;
        V(customers);      // 唤醒理发师
        V(mutex);
        P(barbers);        // 等待理发师空闲
        get_haircut();
    } else {
        V(mutex);          // 没有空位，离开
    }
}

5.6 独木桥问题

独木桥问题：一座独木桥一次只允许一个人通过；若桥上有行人，则后续同方向的行人可以继续上桥，反方向的行人必须等桥上的人全部过完后才能上桥。这个问题可以看作是读者-写者问题的一个变形，其中“读者”是同方向的行人，“写者”是反方向的行人。

semaphore bridge = 1;    // 桥的互斥
semaphore mutex = 1;     // 保护同方向计数
int count = 0;           // 当前桥上同方向人数
int direction = -1;      // 当前桥上方向，-1 表示无人

void pass(int dir) {
    P(mutex);
    if (count == 0) {
        direction = dir;
        P(bridge);       // 第一个上桥者占用桥
        count = 1;
    } else if (direction == dir) {
        count++;         // 同方向，直接上桥
    } else {
        V(mutex);
        // 反方向等待（完整实现需要等待队列协调）
        P(mutex);
        // 重新尝试…
    }
    V(mutex);
    cross();             // 过桥
    P(mutex);
    count--;
    if (count == 0) {
        V(bridge);       // 最后一个过桥者释放桥
    }
    V(mutex);
}

这些经典问题虽然场景各异，但本质上考察的都是同一种能力：根据并发场景中的互斥与同步要求，选择合适数量的信号量、设置正确的初值，并把 P、V 操作放在正确的位置。面试中除了要求默写解法，还经常追问 P、V 顺序颠倒的后果、如何避免死锁等问题。

六、管程

6.1 管程的定义与组成

信号量机制虽然功能强大，但 P、V 操作分散在代码各处，编写和验证都容易出错。管程（Monitor）是一种更高级的同步机制，由数据结构、对数据结构操作的一组过程以及初始化代码组成。管程最重要的特性是：一次只允许一个进程在管程内执行，实现对共享数据的自动互斥，互斥由编译器或运行时保证，程序员不必显式编写锁操作。

monitor example {
    // 共享数据
    int count = 0;
    condition not_empty, not_full;  // 条件变量

    void put() {
        if (count == N)
            not_full.wait();   // 缓冲区满，等待
        count++;
        not_empty.signal();    // 放入后，唤醒等待取数据的进程
    }

    void get() {
        if (count == 0)
            not_empty.wait();  // 缓冲区空，等待
        count--;
        not_full.signal();     // 取出后，唤醒等待放数据的进程
    }
}

6.2 条件变量

条件变量（Condition Variable）用于让进程在某个条件不满足时等待。与信号量不同，条件变量没有“计数值”，只有 wait 和 signal 两个操作。当一个进程在管程内发现条件不满足时，执行 wait 操作释放管程并阻塞自己；当另一个进程使条件满足时，执行 signal 操作唤醒一个在该条件变量上等待的进程。条件变量通常与 while 循环配合使用，以应对“唤醒后条件可能再次不成立”的情况。

6.3 用管程解决哲学家进餐问题

管程解法通过条件变量和状态数组来协调哲学家。每个哲学家只有在左右邻居都不在进餐状态时才能拿起筷子。用状态数组记录思考、饥饿、进餐三种状态，并设置五个条件变量供哲学家等待。

monitor DiningPhilosophers {
    enum { THINKING, HUNGRY, EATING } state[5];
    condition self[5];

    void pickup(int i) {
        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING)
            self[i].wait();   // 拿不到筷子就等待
    }

    void putdown(int i) {
        state[i] = THINKING;
        test((i + 4) % 5);    // 检查左邻居
        test((i + 1) % 5);    // 检查右邻居
    }

    void test(int i) {
        if (state[(i + 4) % 5] != EATING &&
            state[i] == HUNGRY &&
            state[(i + 1) % 5] != EATING) {
            state[i] = EATING;
            self[i].signal(); // 唤醒自己（或使后续 pickup 直接成功）
        }
    }

    void init() {
        for (int i = 0; i < 5; i++)
            state[i] = THINKING;
    }
}

管程解法保证了哲学家不会同时拿起两根筷子而引发死锁：只有当左右邻居都不在进餐时，哲学家才能进入进餐状态，而这个判断在管程的互斥保护下原子完成。

6.4 管程与信号量的对比

维度	信号量	管程
互斥保证	用户显式使用 P/V 保证	管程自动保证
同步方式	P 操作申请、V 操作释放	条件变量 wait/signal
易错性	P/V 顺序易错、易死锁	结构更清晰，更易证明正确
计数值	有资源计数	条件变量无计数，且 signal 可能丢失
语言支持	POSIX、Linux 内核	Java synchronized、Mesa/Hoare 模型

需要注意的是，Hoare 管程和 Mesa 管程在 signal 语义上有所不同：Hoare 管程中，执行 signal 的进程会立即让出管程，使被唤醒进程立即恢复执行；Mesa 管程中，signal 只是把等待进程放入就绪队列，执行 signal 的进程继续运行，被唤醒进程稍后重新竞争管程锁，因此必须用 while 循环重新检查条件。

七、死锁

7.1 死锁的定义与产生原因

死锁（Deadlock）是指多个进程因竞争资源而造成的一种僵局：每个进程都在等待其他进程占有的资源，而没有任何一个进程能释放自己占有的资源，导致所有相关进程都无法继续推进。产生死锁的常见原因包括：竞争不可剥夺资源、竞争可消耗资源、进程推进顺序不当等。

7.2 死锁产生的四个必要条件

死锁必须同时满足以下四个条件，缺一不可：

互斥条件：资源一次只能被一个进程占有，其他进程不能同时使用。
请求并保持条件（占有并等待）：进程在占有一个或多个资源的同时，又请求其他资源，若请求不到则保持已占资源不放。
不可剥夺条件：已分配给进程的资源在使用完毕前不能被强行剥夺，只能由该进程主动释放。
循环等待条件：存在一个进程-资源的循环等待链，链中每个进程都在等待下一个进程占有的资源。

这四个条件是死锁的必要条件，只要破坏其中任意一个，死锁就可以被预防。这也是死锁预防策略的理论基础。

7.3 死锁的处理策略

操作系统处理死锁的策略主要有四种：预防（Prevention）、避免（Avoidance）、检测与解除（Detection and Recovery）以及鸵鸟算法（忽略）。

7.3.1 死锁预防

死锁预防通过破坏四个必要条件之一来防止死锁发生。具体做法包括：

破坏互斥条件：对于某些可共享资源，尽量改为共享访问，但互斥条件往往无法完全破坏（打印机、写文件等本质上需要互斥）。
破坏请求并保持条件：采用静态分配策略，进程在运行前一次性申请全部资源，只有全部满足才运行，运行期间不再申请新资源；缺点是实现简单但资源利用率低，且可能发生饥饿。
破坏不可剥夺条件：进程申请资源失败时，必须释放已占有的全部资源，稍后再重新申请；缺点是需要保存现场并可能反复重试。
破坏循环等待条件：采用顺序资源分配法，把所有资源编号，进程必须按编号递增顺序申请资源；缺点是编号难以合理设计，某些进程可能因此等待不相关资源。

7.3.2 死锁避免

死锁避免在资源分配前进行判断，只有分配后系统仍处于安全状态时才分配资源。最经典的算法是银行家算法（Banker's Algorithm）。系统维护可用资源向量 Available、最大需求矩阵 Max、已分配矩阵 Allocation 和需求矩阵 Need（Need = Max - Allocation）。

// 安全性检查算法的核心步骤
// 1. Work = Available，Finish[i] = false（i = 0..n-1）
// 2. 查找满足 Finish[i] == false 且 Need[i] <= Work 的进程 i
// 3. 若找到：
//      Work = Work + Allocation[i]
//      Finish[i] = true
//      回到步骤 2
// 4. 若所有 Finish[i] == true，则系统处于安全状态

当进程请求资源时，银行家算法先试探性地分配资源，然后执行安全性检查。若分配后系统仍安全，则真正分配；否则让进程等待。银行家算法的缺点是：需要事先知道每个进程的最大资源需求，且算法开销较大，在实际系统中较少直接使用。

7.3.3 死锁检测与解除

死锁检测允许系统进入死锁状态，但通过定期检测来发现死锁。检测方法主要基于资源分配图：首先化简掉所有不阻塞的进程节点（即能获得全部所需资源的进程），若最终仍有进程无法消去，则说明存在死锁。对每种资源只有一个实例的系统，可以采用检查资源分配图是否存在环的方法；对每种资源有多个实例的系统，则使用类似银行家算法的检测算法。

解除死锁的常用方法有：资源剥夺法（从其他进程剥夺足够资源分配给死锁进程）、撤销进程法（终止部分或全部死锁进程）和进程回退法（让进程回退到安全检查点重新执行）。

7.3.4 鸵鸟算法

鸵鸟算法指对死锁采取忽略的态度，认为死锁发生的概率很低，处理死锁的代价大于死锁造成的损失。Windows、Linux 等主流操作系统在大多数场景下采用鸵鸟算法，而数据库系统对死锁通常采取检测与恢复策略。

7.4 死锁与饥饿的关系

死锁与饥饿（Starvation）既有联系又有区别。死锁一定是循环等待，涉及的进程都在等待其他进程占有的资源，谁也推进不了；饥饿则是指某个进程长期得不到所需的资源或 CPU 时间，虽然它理论上有可能在未来获得，但被其他进程不断“插队”而无法推进。死锁的进程集合是静态的僵局，饥饿的进程则可能是动态的、可恢复的。死锁必然导致饥饿，但饥饿不一定导致死锁。

八、高频面试题与易错点

8.1 面试题：进程与线程的同步有什么异同

进程同步主要解决不同进程之间共享资源的互斥与协作问题，需要通过操作系统提供的 IPC 机制（信号量、共享内存、消息队列等）实现，因为这些进程拥有独立地址空间。线程同步则发生在同一进程内的多个线程之间，由于线程共享进程的地址空间，同步开销相对较小，可以使用互斥锁、条件变量、读写锁、自旋锁等机制。两种同步的本质相同，都是为了保证共享资源访问的有序性和互斥性。

8.2 面试题：信号量的 P 操作为什么必须是原子的

P 操作中先检查资源数量、再修改资源数量的过程，如果被打断，多个进程同时执行 P 操作可能都会读取到“资源可用”的状态，然后同时进入临界区或同时申请成功，导致互斥失败。因此必须以“不可中断”的方式执行，由硬件原子指令或关中断来保证。

8.3 面试题：生产者-消费者问题中如果把两个 P 操作顺序颠倒会发生什么

若生产者先执行 P(mutex) 再执行 P(empty)，当缓冲区满时，生产者会在持有 mutex 的情况下因 P(empty) 而阻塞；消费者随后尝试 P(mutex) 也会阻塞，二者都无法推进，形成死锁。因此必须先申请资源信号量（empty/full），再申请互斥信号量，释放时顺序相反。

8.4 易错点总结

P、V 操作顺序：同一临界区中“先资源后互斥”，P 操作顺序与 V 操作顺序相反。
P、V 必须成对：一个 P 对应一个 V，漏掉任何一个都会导致进程永远阻塞或资源计数混乱。
互斥信号量初值为 1：同步信号量初值常为 0，资源信号量初值为资源数量，切勿混淆。
条件变量要用 while 而非 if：被唤醒后条件可能已不成立，必须重新检查。
死锁四个条件缺一不可：判断是否死锁时先检查是否满足循环等待等条件。
忙等与让权等待：软件算法和自旋锁是忙等，记录型信号量和管程是让权等待。

九、实践：一个完整的线程同步示例

下面给出一个使用 POSIX 线程和信号量实现生产者-消费者问题的完整示例，编译时需要链接 pthread 库。该示例展示了记录型信号量在现代系统中的实际使用方式。

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>

#define N 5

sem_t empty, full, mutex;
int buffer[N];
int in = 0, out = 0;

void *producer(void *arg) {
    int item;
    for (int i = 0; i < 10; i++) {
        item = i;
        sem_wait(&empty);
        sem_wait(&mutex);
        buffer[in] = item;
        in = (in + 1) % N;
        printf("生产: %d\n", item);
        sem_post(&mutex);
        sem_post(&full);
        usleep(100000);
    }
    return NULL;
}

void *consumer(void *arg) {
    int item;
    for (int i = 0; i < 10; i++) {
        sem_wait(&full);
        sem_wait(&mutex);
        item = buffer[out];
        out = (out + 1) % N;
        printf("消费: %d\n", item);
        sem_post(&mutex);
        sem_post(&empty);
        usleep(150000);
    }
    return NULL;
}

int main() {
    sem_init(&empty, 0, N);
    sem_init(&full, 0, 0);
    sem_init(&mutex, 0, 1);

    pthread_t p, c;
    pthread_create(&p, NULL, producer, NULL);
    pthread_create(&c, NULL, consumer, NULL);

    pthread_join(p, NULL);
    pthread_join(c, NULL);

    sem_destroy(&empty);
    sem_destroy(&full);
    sem_destroy(&mutex);
    return 0;
}

十、总结

进程同步是操作系统的核心内容，也是并发编程的理论基础。本文从并发与竞态条件出发，介绍了临界区问题的四个条件，梳理了单标志法、双标志法、Peterson 算法、面包店算法等软件同步方法，讲解了中断屏蔽、Test-and-Set、Swap、CAS 等硬件同步方法，重点剖析了信号量机制及其在生产者-消费者、读者-写者、哲学家进餐、吸烟者、理发师、独木桥等经典问题中的应用，最后讨论了管程和死锁的处理策略。

学习进程同步的关键在于“动手写代码、动脑推时序”。建议读者针对每个经典问题，亲手写出信号量或管程解法，并思考以下问题：P、V 顺序颠倒会怎样？如何证明算法满足互斥、前进和有限等待？如何避免死锁或饥饿？只有在反复推演中，才能真正掌握这些看似简单却极易出错的同步知识。希望本文能帮助你构建完整的进程同步知识框架，从容应对面试与考试。