postgraduate-prep/subjects/os/03_同步互斥与死锁.md

## 笔记记录

### 要点 01 - 临界区与互斥基本概念

#### 临界资源与临界区

- **临界资源（Critical Resource）**：一次仅允许一个进程使用的资源
- **临界区（Critical Section）**：访问临界资源的代码段

#### 临界区访问原则

| 原则 | 说明 |
|------|------|
| **空闲让进** | 无进程在临界区时，应允许一个请求进入的进程立即进入 |
| **忙则等待** | 已有进程在临界区时，其他试图进入的进程必须等待 |
| **有限等待** | 对请求进入的进程，应在有限时间内获准进入 |
| **让权等待** | 进程不能进入临界区时应释放CPU（非必须，但现代OS推荐） |

#### 同步与互斥

- **互斥（Mutual Exclusion）**：同一时刻只允许一个进程进入临界区
- **同步（Synchronization）**：多个进程之间因执行顺序约束而产生的协调关系

---

### 要点 02 - Peterson 算法

#### 算法实现

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

// 进程 Pi (i=0,1)
flag[i] = true;
turn = 1 - i;
while (flag[1-i] && turn == 1-i);
// 临界区
flag[i] = false;
// 剩余区
```

#### 特点

满足互斥、空闲让进、有限等待，但**不满足让权等待**（忙等）。

---

### 要点 03 - 硬件互斥方法

#### 关中断

进入临界区前关中断，之后开中断。简单但关中断权限过大，不适用于多核。

#### TestAndSet 指令

原子操作：返回 `lock` 旧值并置为 `1`。

```c
bool TestAndSet(bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;
}
// 使用
while (TestAndSet(&lock));  // 忙等
// 临界区
lock = false;
```

#### Swap 指令

原子交换两个变量的值。

适用于多核，但仍是忙等。

---

### 要点 04 - 信号量机制

#### 整型信号量

```c
int S = 1;  // 资源数量
wait(S) { while (S <= 0); S--; }
signal(S) { S++; }
```

仍是忙等，不满足让权等待。

#### 记录型信号量

```c
typedef struct {
    int value;           // 资源数量
    struct process *list; // 等待队列
} semaphore;

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) block(S->list);
}

signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) wakeup(S->list);
}
```

- `S->value < 0` 时，绝对值表示等待队列中的进程数
- 满足**让权等待**

#### 两种信号量用法

- **互斥信号量**：初始为 1，`wait`/`signal` 成对出现在同一进程
- **同步信号量**：初始为 0（或n），`wait`/`signal` 成对出现在不同进程

---

### 要点 05 - 生产者-消费者问题

#### 问题描述

一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区。

#### 代码实现

```c
semaphore mutex = 1;   // 互斥访问缓冲区
semaphore empty = n;   // 空缓冲区数
semaphore full = 0;    // 满缓冲区数

// 生产者
producer() {
    while (1) {
        produce();
        wait(empty);
        wait(mutex);
        buffer[in] = item;  in = (in + 1) % n;
        signal(mutex);
        signal(full);
    }
}

// 消费者
consumer() {
    while (1) {
        wait(full);
        wait(mutex);
        item = buffer[out];  out = (out + 1) % n;
        signal(mutex);
        signal(empty);
        consume(item);
    }
}
```

#### 易错点

`wait(empty)` 和 `wait(mutex)` 的顺序不可交换，否则可能死锁。

---

### 要点 06 - 读者-写者问题

#### 读者优先

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

writer() {
    wait(rw);  write();  signal(rw);
}

reader() {
    wait(mutex);
    if (read_count == 0) wait(rw);
    read_count++;
    signal(mutex);
    read();
    wait(mutex);
    read_count--;
    if (read_count == 0) signal(rw);
    signal(mutex);
}
```

#### 写者优先

增加一个 `w` 信号量，使写者到达后阻止后续读者进入。

---

### 要点 07 - 哲学家就餐问题

#### 问题描述

5 个哲学家围坐圆桌，每两人之间有一根筷子，哲学家只有同时拿到左右两根筷子才能进餐。

#### 代码实现

```c
semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;    // 限制最多4人同时就餐，避免死锁

philosopher(int i) {
    while (1) {
        think();
        wait(mutex);
        wait(chopstick[i]);
        wait(chopstick[(i+1)%5]);
        signal(mutex);
        eat();
        signal(chopstick[i]);
        signal(chopstick[(i+1)%5]);
    }
}
```

#### 防死锁策略

- 最多允许 4 人同时进餐（如上述代码）
- 奇数号先左后右，偶数号先右后左

---

### 要点 08 - 吸烟者问题

#### 问题描述

三个吸烟者分别缺烟草、纸、胶水，一个供应者随机提供两种材料。

#### 代码实现

```c
semaphore offer[3] = {0, 0, 0};
semaphore finish = 0;
int turn = 0;

provider() {
    while (1) {
        turn = rand() % 3;
        signal(offer[turn]);
        wait(finish);
    }
}

smoker(int i) {
    while (1) {
        wait(offer[i]);
        smoke();
        signal(finish);
    }
}
```

---

### 要点 09 - 管程

#### 基本概念

**管程（Monitor）** 是一个高级同步原语，封装了共享变量和操作过程：

- 任一时刻最多只有一个进程在管程内执行
- 通过 **条件变量（Condition Variable）** 实现同步：
  - `wait(cond)`：阻塞当前进程，释放管程互斥锁
  - `signal(cond)`：唤醒一个在 `cond` 上等待的进程（如果存在）
- **MESA 管程**（实际OS采用）：`signal` 只是将等待进程移入就绪队列，需用 `while` 重新检查条件

---

### 要点 10 - 死锁的条件与预防

#### 死锁定义

多个进程因竞争资源而造成的一种互相等待的僵局。

#### 四个必要条件（必须同时满足）

| 条件 | 说明 |
|------|------|
| **互斥** | 资源一次只能被一个进程占用 |
| **请求与保持** | 进程已持有资源，又请求新资源，但不释放已有资源 |
| **不可剥夺** | 进程已获得的资源不能被强制剥夺 |
| **循环等待** | 存在进程资源的循环等待链 |

#### 死锁预防

| 策略 | 破坏的条件 | 缺点 |
|------|-----------|------|
| **互斥突破** | 互斥 | 许多资源本身就是互斥的，不可行 |
| **请求与保持突破** | 请求与保持 | 资源利用率低，可能饥饿 |
| **不可剥夺突破** | 不可剥夺 | 实现复杂，加重系统开销 |
| **循环等待突破** | 循环等待 | 资源编号顺序申请，增加编程复杂度 |

---

### 要点 11 - 银行家算法

#### 数据结构

- `Available[m]`：每种资源的可用数量
- `Max[n][m]`：每个进程对每种资源的最大需求
- `Allocation[n][m]`：每个进程已分配的资源数
- `Need[n][m]`：每个进程还需要的资源数，`Need = Max - Allocation`

#### 安全性算法

1. 设 `Work = Available`，`Finish[i] = false`
2. 寻找 `Finish[i] = false` 且 `Need[i] <= Work` 的进程
3. 若找到，则 `Work += Allocation[i]`，`Finish[i] = true`，重复步骤2
4. 若所有 `Finish[i] = true`，则系统安全

#### 资源请求算法

1. 若 `Request[i] > Need[i]`，则出错
2. 若 `Request[i] > Available`，则等待
3. 尝试分配：`Available -= Request[i]`，`Allocation[i] += Request[i]`，`Need[i] -= Request[i]`
4. 执行安全性算法，若安全则正式分配，否则回滚并等待

---

### 要点 12 - 死锁检测与恢复

#### 检测方法

通过**资源分配图**（Resource Allocation Graph）检测循环等待。

**资源分配图简化**：
- 找出非阻塞非孤立的进程（能获得全部所需资源）
- 消去其所有请求边和分配边
- 若能消去所有边，则无死锁

#### 恢复方法

- **剥夺资源**：从死锁进程剥夺资源给其他进程
- **终止进程**：终止所有死锁进程或逐个终止直到解除死锁
- **进程回退**：回退到安全状态（需要系统支持）