# 2.4 进程同步

## 一、进程同步的概念

### 1.1 进程同步的定义

**进程同步**：协调多个进程的执行顺序，使它们按照一定的规则共享资源和相互合作，避免竞争条件和数据不一致。

### 1.2 进程同步的原因

**资源共享**：多个进程需要访问共享资源
**进程合作**：多个进程需要协调完成某项任务

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

#### 临界资源

**临界资源**：一次仅允许一个进程使用的资源。

**例子**：
- 打印机
- 共享变量
- 共享文件
- 共享数据库

#### 临界区

**临界区**：每个进程中访问临界资源的那段代码。

```
进程P1:
    进入区
    临界区（访问临界资源）
    退出区
    剩余区
```

### 1.4 同步机制应遵循的原则

1. **空闲让进**：当临界区空闲时，应允许一个请求进入临界区的进程立即进入
2. **忙则等待**：当已有进程进入临界区时，其他试图进入临界区的进程必须等待
3. **有限等待**：对请求访问的进程，应保证在有限时间内进入临界区
4. **让权等待**：当进程不能进入临界区时，应立即释放CPU

---

## 二、硬件同步机制

### 2.1 关中断

**方法**：进入临界区前关中断，退出临界区后开中断。

**优点**：简单
**缺点**：
- 只适用于单处理机
- 关中断时间过长影响系统效率
- 不适用于用户程序

### 2.2 Test-and-Set指令

**指令功能**：测试并设置某个内存单元的值。

```c
// 硬件指令
boolean TS(boolean *lock) {
    boolean old = *lock;
    *lock = true;
    return old;
}

// 使用
while (TS(&lock));  // 如果lock为true，循环等待
    // 临界区
lock = false;       // 退出临界区
```

**特点**：
- 原子操作
- 适用于多处理机
- 不满足"让权等待"原则

### 2.3 Swap指令

**指令功能**：交换两个内存单元的值。

```c
// 硬件指令
void Swap(boolean *a, boolean *b) {
    boolean temp = *a;
    *a = *b;
    *b = temp;
}

// 使用
boolean key = true;
while (key != false)
    Swap(&lock, &key);
    // 临界区
lock = false;
```

---

## 三、信号量机制

### 3.1 信号量的概念

**信号量（Semaphore）**：一种用于进程同步和互斥的变量。

**信号量的组成**：
- 信号量值（S）：表示资源的数量或状态
- 等待队列：等待该信号量的进程队列

### 3.2 整型信号量

**定义**：
```c
int S;  // 信号量，初值为资源数量
```

**操作**：
```c
// P操作（Wait）
void P(int S) {
    while (S <= 0);  // 忙等待
    S--;
}

// V操作（Signal）
void V(int S) {
    S++;
}
```

**缺点**：不满足"让权等待"原则，存在忙等待。

### 3.3 记录型信号量

**定义**：
```c
typedef struct {
    int value;          // 资源数量
    struct PCB *queue;  // 等待队列
} semaphore;
```

**操作**：
```c
// P操作
void P(semaphore S) {
    S.value--;
    if (S.value < 0) {
        // 将进程插入等待队列
        block(S.queue);
    }
}

// V操作
void V(semaphore S) {
    S.value++;
    if (S.value <= 0) {
        // 从等待队列唤醒一个进程
        wakeup(S.queue);
    }
}
```

**特点**：
- 满足"让权等待"原则
- 没有忙等待
- 是考研重点

### 3.4 信号量的应用

#### 互斥

```c
semaphore mutex = 1;  // 互斥信号量

// 进程P1
P(mutex);
    // 临界区
V(mutex);

// 进程P2
P(mutex);
    // 临界区
V(mutex);
```

#### 同步

```c
semaphore S = 0;  // 同步信号量

// 进程P1（先执行）
    // 代码1
V(S);

// 进程P2（后执行）
P(S);
    // 代码2（在代码1之后执行）
```

---

## 四、管程机制

### 4.1 管程的概念

**管程（Monitor）**：一组数据以及定义在这组数据上的操作的集合，是一种高级同步机制。

**管程的组成**：
- 局部于管程的共享变量
- 对共享变量进行操作的过程
- 初始化语句

### 4.2 管程的特点

- 封装性：共享变量只能被管程内的过程访问
- 互斥性：任一时刻只能有一个进程在管程内执行
- 同步机制：提供条件变量实现同步

### 4.3 条件变量

**条件变量**：用于阻塞和唤醒进程。

**操作**：
- `wait(x)`：阻塞进程，将进程放入x的等待队列
- `signal(x)`：唤醒x等待队列上的一个进程

**注意**：条件变量没有值，只是队列。

---

## 五、经典同步问题

### 5.1 生产者-消费者问题

见2.5节

### 5.2 读者-写者问题

见2.5节

### 5.3 哲学家进餐问题

见2.5节

---

## 六、考研重点

1. **临界区的概念**：什么是临界区
2. **同步机制的原则**：空闲让进、忙则等待、有限等待、让权等待
3. **信号量机制**：整型信号量、记录型信号量
4. **P、V操作**：理解其含义和执行过程
5. **信号量的应用**：互斥、同步
6. **管程的概念**：条件变量

---

*下一节：2.5 经典同步问题*