---
title: "04-同步与互斥：进程间的两种制约关系"
aliases:
  - 同步与互斥
created: 2026-08-29
tags:
  - 基础与理论
  - 操作系统
  - "408"
---

# 同步与互斥：进程间的两种制约关系

> 本篇对应王道第二章同步部分（原 10 篇）。核心问题：**进程同步是什么？不同进程间有什么关系？怎么用信号量把关系管起来？**

## 一、同步与互斥是什么

多道程序环境下进程并发执行，不同进程间存在**相互制约关系**，为协调这些关系引入进程同步。

直观理解：系统里有加法进程和乘法进程，要结果正确必须**先乘后加**。但 OS 有异步性，不加以制约的话加法进程完全可能先跑——所以需要制约机制。

你和朋友编辑同一份文档，不沟通谁何时改，就会出现互相覆盖；进程同步就是防止这种问题发生在程序上的机制。

### 临界资源与临界区

一次仅允许一个进程使用的资源叫**临界资源**——打印机、共享变量、共享数据都是。对临界资源的访问必须**互斥**进行，访问它的那段代码叫**临界区**。

访问过程分四部分：

```c
do{
    entry section;      // 进入区：检查能否进入，能则上锁（设"正在访问"标志）
    critical section;   // 临界区：访问临界资源的代码
    exit section;       // 退出区：清除"正在访问"标志
    remainder section;  // 剩余区：其他代码
}while(true);
```

### 同步：合作导致的制约

同步也称**直接制约关系**：为完成同一任务而建立的多个进程，因**协调工作次序**而等待、传递信息。源于**相互合作**。

例子：输入进程 A 通过单缓冲向进程 B 供数据——缓冲区空时 B 阻塞，A 放入数据后唤醒 B；缓冲区满时 A 阻塞，B 取走数据后唤醒 A。

### 互斥：争抢导致的制约

互斥也称**间接制约关系**：一个进程进临界区用临界资源时，另一个必须等。源于**资源共享**（争抢）。

例子：仅一台打印机，A 要打印时打印机已分给 B，A 阻塞；B 释放后系统唤醒 A。

**简而言之：进程间合作导致的制约叫同步，进程间争抢资源导致的制约叫互斥。**

### 同步机制四准则

| 准则 | 含义 |
| --- | --- |
| **空闲让进** | 临界区空闲时，允许一个请求进入的进程立即进入 |
| **忙则等待** | 已有进程在临界区，其他试图进入的必须等 |
| **有限等待** | 请求访问的进程能在有限时间内进入（不能饿死） |
| **让权等待** | 进不去时**应立即释放处理机**，防止忙等待 |

后面每种方法都拿这四条来打分。

## 二、互斥的实现（软件）

思路：进入区设置标志，用循环检查等待；退出区修改标志。

### 单标志法

一个整型变量 `turn` 指示**轮到谁**：turn=0 时 P0 进，turn=1 时 P1 进；用完把 turn 让给对方。

```c
// P0:                          // P1:
while(turn != 0);               while(turn != 1);
critical section;               critical section;
turn = 1;                       turn = 0;
remainder section;              remainder section;
```

**问题：不满足"空闲让进"**——对方不要进临界区，turn 永远不变，我就永远进不去。临界区只能**强制交替使用**。

### 双标志法先检查

每人一个标志 `flag[]`，**先检查对方**想不想进，再**设置自己**想进：

```c
// P0:                          // P1:
while(flag[1]);                 while(flag[0]);
flag[0] = true;                 flag[1] = true;
critical section;               critical section;
flag[0] = false;                flag[1] = false;
```

好处是不用交替进入、可连续使用。**问题：违背"忙则等待"**——两进程几乎同时检查，都看到对方标志为 false，双双进入，互斥失效。

### 双标志法后检查

交换顺序：**先设置自己**想进，**再检查**对方：

```c
// P0:                          // P1:
flag[0] = true;                 flag[1] = true;
while(flag[1]);                 while(flag[0]);
critical section;               critical section;
flag[0] = false;                flag[1] = false;
```

互斥保住了，**问题：违背"空闲让进"和"有限等待"**——同时想进时双方互相谦让，谁也进不了，**饥饿**（"礼让"事故）。

### Peterson 算法

单标志 + 双标志后检查的结合：`flag` 解决互斥，`turn` 解决饥饿。想进时先插自己的旗，再说一句**"轮到你先"**：

```c
// P0:                          // P1:
flag[0] = true;                 flag[1] = true;
turn = 1;                       turn = 0;
while(flag[1] && turn == 1);    while(flag[0] && turn == 0);
critical section;               critical section;
flag[0] = false;                flag[1] = false;
```

双方都想进时，turn 只能是一方的值——**谦让有先后，turn 是最后表态的那个**，于是唯一的一方进入。四准则全满足（除"让权等待"，它还在忙等）。

缺点：依赖原子操作、只适用于两个进程。

### 硬件实现

#### 中断屏蔽

CPU 只在**中断时**进行进程切换，那最简单直接暴力的方式——**把中断关了**：

```c
void enter_critical_section() { disable_interrupts(); /* 临界区 */ }
void leave_critical_section() { enable_interrupts();  /* 剩余区 */ }
```

简单直接，但限制了处理机交替执行程序的能力，效率明显降低；**关中断的权力不能交给用户**——某进程关了中断不再开，系统可能因此终止。只适用于单处理机、不适合长临界区。

#### Test-and-Set（TS）

原子地"读旧值 + 置 1"：

```c
int test_and_set(int *lock) {
    int original = *lock;
    *lock = 1;
    return original;
}
// 加锁: while(test_and_set(&lock));   解锁: lock = 0;
```

锁为 0 时第一个调用者拿到旧值 0 进入，其余人拿到 1 忙等。适合短时间互斥。

#### Compare-and-Swap（CAS）

原子地"比较预期旧值，相同则换新值"：

```c
int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected) *value = new_value;
    return temp;
}
// 加锁: while(compare_and_swap(&lock, 0, 1) != 0);
```

比 TS 更适合复杂同步模式（无锁数据结构）。另有 LL/SC 原语（Load-Link 读值，Store-Conditional 仅当地址未被改过才写入），能检测读写间是否发生冲突。

#### 硬件方法小结

优点：适用于任意数目进程、单/多处理机都行；简单、易验证正确性；支持多个临界区（每区一个布尔变量）。缺点：等待时**消耗处理机时间、不能让权等待**（忙等）；从等待进程中**随机选一个**进入，可能饥饿。

### 互斥锁（mutex lock）

解决临界区最简单的工具：进临界区 `acquire()` 拿锁，出临界区 `release()` 放锁：

```c
acquire()  { while(!available) ; available = false; }
release()  { available = true; }
```

两个操作必须原子（通常用硬件机制实现）。主要缺点还是**忙等待**——多个进程共享一个 CPU 时白白浪费周期，所以互斥锁常用于**多处理器系统**（一个核上忙等，不妨碍别的核干活）。

## 三、信号量

信号量机制功能更强，互斥与同步都能解决。只能被两个标准原语访问：**wait(S) 和 signal(S)**，即 **P 操作和 V 操作**（P=Proberen 尝试，V=Verhogen 增加）——进程通信那一篇提过，这里展开。

### 整型信号量 → 忙等

```c
wait(S)   { while(S <= 0); S = S - 1; }   // S<=0 就一直测
signal(S) { S = S + 1; }
```

问题一目了然：S≤0 时不断测试，**不遵循"让权等待"**，进程处于忙等；而且**没有等待队列**。

### 记录型信号量 → 真正可用

整型变量 value 之外，再加一个**进程链表 L** 链接所有等待进程：

```c
typedef struct {
    int value;
    struct process *L;
} semaphore;

void wait(semaphore S) {        // P操作
    S.value--;                  // 请求一个该类资源
    if (S.value < 0) {          // 资源分配完毕
        add this process to S.L;
        block(S.L);             // 自我阻塞，放弃处理机
    }
}

void signal(semaphore S) {      // V操作
    S.value++;                  // 释放一个资源
    if (S.value <= 0) {         // 仍有进程在等
        remove a process P from S.L;
        wakeup(P);              // 唤醒队首等待进程
    }
}
```

**读法**：S.value 的值就是**剩余资源数**；减完小于 0，说明有人没分到，去排队；V 完仍 ≤0，说明队列里还有人，唤醒一个。这下"让权等待"落实了——阻塞而不是忙等。

### 三种用法

**实现同步**：A 必须等 B 完成后才能执行——信号量初值 0，B 干完 `signal(sem)`，A 开头 `wait(sem)`：

```c
semaphore sem = 0;
// B: do_something(); signal(sem);
// A: wait(sem); continue_work();
```

**实现互斥**：初值 1，进出临界区夹 P/V：

```c
semaphore mutex = 1;
// wait(mutex); critical_section(); signal(mutex);
```

互斥是**不同进程对同一信号量**做 P/V：某进程 P 成功进入，退出后**由它自己** V，表示可让其他进程进了。

**实现前驱关系**：每条前驱边设一个初值 0 的信号量，前件末尾 V、后件开头 P：

![[image-239cf7ad.png]]

```c
semaphore a1=a2=b1=b2=c=d=e=0;
S1(){ ……; V(a1); V(a2); }
S2(){ P(a1); ……; V(b1); V(b2); }
S3(){ P(a2); ……; V(c); }
S4(){ P(b1); ……; V(d); }
S5(){ P(b2); ……; V(e); }
S6(){ P(c); P(d); P(e); ……; }
```

### 小结口诀

- **同步问题**：某行为要用到某种资源 → 行为**前面 P** 一下；某行为会提供某种资源 → 行为**后面 V** 一下
- **互斥问题**：PV 操作**紧夹**使用互斥资源的那个行为，中间不能夹其他冗余代码

## 四、管程

信号量机制的问题：每个要访问临界资源的进程都得**自备同步的 PV 操作**，大量分散的同步操作不好管，还容易因操作不当导致死锁。

于是有了**管程**：用共享数据结构抽象表示系统中的共享资源，把对该数据结构的操作定义成**一组过程**，进程对资源的申请释放都通过这组过程——统一管理所有访问，互斥由管程保证，**无须程序员自己实现**。

**管程很像一个类**：

```
monitor Demo {
    共享数据结构 S;              // 局部于管程内部的共享数据
    init_code() { S = 5; }      // 初始化语句
    take_away() { S--; }        // 过程：申请资源
    give_back() { S++; }        // 过程：归还资源
}
```

- 共享数据只能被管程内的过程访问；进程只有通过管程内的过程才能进入
- **每次只允许一个进程进入管程**（各进程串行执行管程内的过程）——互斥自动保证

### 条件变量

进程进管程后可能被阻塞，若它不释放管程，别人也进不来。于是把阻塞原因定义为**条件变量 condition**，每个条件变量对应一个**等待队列**。两个操作：

- `x.wait`：条件不满足时，调用进程插入 x 的等待队列，**并释放管程**（别人能用）
- `x.signal`：条件变化时，唤醒一个因 x 阻塞的进程

```
monitor Demo {
    共享数据结构 S;  condition x;
    take_away() {
        if (S <= 0) x.wait();   // 资源不够，在x上阻塞等待并释放管程
        dosomething;
    }
    give_back() {
        归还资源 dosomething;
        if (有进程在等待) x.signal();
    }
}
```

**条件变量 vs 信号量**（高频考点）：wait/signal 相似，都能阻塞唤醒；但**条件变量没有值，只实现排队等待**；信号量有值，反映剩余资源数——管程里剩余资源数由共享数据结构记录。

## 五、经典同步问题

### 生产者-消费者

生产者往共享缓冲区放数据，消费者取走处理。挑战：**缓冲区满不能写、空不能读**。三个信号量：

- `empty = N`（空闲位置数）、`full = 0`（已占用数）——管"同步"
- `mutex = 1`（互斥访问缓冲区）——管"互斥"

```c
semaphore empty = N, full = 0, mutex = 1;

void producer() {
    while (true) {
        item = produce_item();
        wait(empty);                    // 先同步：等空位
        wait(mutex);                    // 再互斥：锁缓冲区
        put_item_into_buffer(item);
        signal(mutex);
        signal(full);                   // 通知：多了一件
    }
}

void consumer() {
    while (true) {
        wait(full);                     // 等数据
        wait(mutex);
        item = take_item_from_buffer();
        signal(mutex);
        signal(empty);                  // 通知：空了一个位
        consume_item(item);
    }
}
```

⚠️ **P 操作顺序不能颠倒**：先 `wait(mutex)` 再 `wait(empty)`，缓冲区满时生产者会拿着锁去等空位——死锁。同步 P 在前，互斥 P 在后。

### 读者-写者

多个读者可同时读，写者必须独占。核心技巧：**计数器 + 第一个/最后一个读者负责加解锁**：

```c
semaphore rw_mutex = 1;   // 写者与"第一/最后读者"竞争
semaphore mutex = 1;      // 保护 read_count
int read_count = 0;

void reader() {
    while (true) {
        wait(mutex);
        read_count++;
        if (read_count == 1) wait(rw_mutex);   // 第一个读者锁资源
        signal(mutex);
        read_data();
        wait(mutex);
        read_count--;
        if (read_count == 0) signal(rw_mutex); // 最后一个读者放资源
        signal(mutex);
    }
}

void writer() {
    while (true) {
        wait(rw_mutex);    // 写者直接独占
        write_data();
        signal(rw_mutex);
    }
}
```

**公平性权衡**：基本版里读者源源不断时**写者饥饿**。改进思路：加队列/写者优先规则（如读写公平法，写者到达后堵住后续读者）。这个问题的价值就在权衡效率、公平与简单性。

### 哲学家进餐

五位哲学家围圆桌，每两人之间一根筷子，进餐需要**同时**拿左右两根。5 根筷子 = 5 个初值 1 的信号量：

```c
semaphore chopstick[5] = {1,1,1,1,1};

void philosopher(int i) {
    while (true) {
        think();
        wait(chopstick[i]);             // 先左
        wait(chopstick[(i+1) % 5]);     // 再右
        eat();
        signal(chopstick[i]);
        signal(chopstick[(i+1) % 5]);
    }
}
```

 naive 版本的问题：五人**同时**拿起左边筷子，全在等右边——**死锁**。经典解法：**只让一位哲学家（如编号最大的）先拿右边再拿左边**，破坏"循环等待"，至少保证一人能凑齐两根。

**这个思路其实和贪心是相反的**——贪心强调争取眼前最好的，不考虑后果；哲学家问题若用贪心解，眼前有筷子能拿就拿，就会死锁。若不仅考虑眼前一步、还考虑下一步——**能不能一次拿起两根筷子才做决定**——就能避开死锁。这是哲学家问题的精髓：多想一步，而不是见好就抢。

### 吸烟者

三个吸烟者各拥有无限量的一种材料（烟草/纸/火柴各一），卷一支烟需要**两种**材料。供应者每次随机放两种材料上桌，**拥有第三种材料的吸烟者**拿走、卷、抽，然后发信号让供应者继续：

```c
semaphore agentSem = 1;
semaphore tobacco = 0, paper = 0, match = 0;

void agent() {                      // 供应者：随机放两种
    while (true) {
        wait(agentSem);
        if (random() == 0)      { signal(tobacco); signal(paper); }
        else if (random() == 1) { signal(paper);   signal(match); }
        else                    { signal(tobacco); signal(match); }
    }
}

void smoker_with_tobacco() {        // 有烟草的人：等纸和火柴
    while (true) {
        wait(paper); wait(match);
        smoke();
        signal(agentSem);           // 抽完叫供应者继续
    }
}
// smoker_with_paper / smoker_with_match 同理，等待各自缺的两种
```

四个问题的关注点各不相同：

| 问题 | 关注点 |
| --- | --- |
| 生产者-消费者 | 缓冲管理、满不写空不读的协调 |
| 读者-写者 | 读写公平性与效率、防写者饿死 |
| 哲学家进餐 | 循环等待的死锁避免、资源公平分配 |
| 吸烟者 | 按需分配资源、供应者与消费者的接力协调 |

它们都是同一件事的不同切面：多进程如何安全有效地共享资源、协调操作，各自给出一种避免竞争条件、死锁和饥饿的设计视角。

## 六、盲点

1. **P 操作顺序是送命题**：同步信号量的 P 在前，互斥信号量的 P 在后；先锁后等 = 拿着资源等资源，死锁预备役
2. 信号量 `S.value` 的含义：**>0 剩余资源数；<0 其绝对值 = 排队等待的进程数**（这个负数含义选择题常考）
3. 记录型信号量才满足"让权等待"，整型信号量是忙等
4. 管程里的条件变量**没有值**——值在共享数据结构里；信号量的值反映剩余资源
5. 单标志法违反"空闲让进"（强制交替）；双标志先检查违反"忙则等待"（都能进）；双标志后检查违反"空闲让进+有限等待"（互相谦让全饿着）；Peterson 全满足但忙等
6. 硬件方法互斥绝对可靠，但都忙等，且随机选人可能饥饿
7. 哲学家问题与贪心相反：能拿不一定拿，先想"能否一次拿齐"
8. **练习题有 30 多页……先把大概知识点过一遍，二轮再来细究**——本篇先立框架，题感靠二轮

---

资源管不好会怎样？极端情况就是死锁 → [[05-死锁]]

⬅️ 🏠 [[00-操作系统总览]] ➡️ [[05-死锁]]