# 2.5 经典同步问题

## 一、生产者-消费者问题

### 1.1 问题描述

有一群生产者进程和一群消费者进程，共享一个能存放n个产品的缓冲区。

**规则**：
- 只要缓冲区未满，生产者就可以放入产品
- 只要缓冲区未空，消费者就可以取出产品
- 缓冲区是临界资源，必须互斥访问

### 1.2 信号量设置

```c
semaphore mutex = 1;    // 互斥信号量，控制对缓冲区的互斥访问
semaphore empty = n;    // 同步信号量，表示空闲缓冲区数量
semaphore full = 0;     // 同步信号量，表示已用缓冲区数量
```

### 1.3 解决方案

```c
// 生产者进程
void producer() {
    while (true) {
        生产一个产品;
        P(empty);       // 等待空闲缓冲区
        P(mutex);       // 进入临界区
        将产品放入缓冲区;
        V(mutex);       // 退出临界区
        V(full);        // 增加已用缓冲区
    }
}

// 消费者进程
void consumer() {
    while (true) {
        P(full);        // 等待已用缓冲区
        P(mutex);       // 进入临界区
        从缓冲区取出产品;
        V(mutex);       // 退出临界区
        V(empty);       // 增加空闲缓冲区
        消费产品;
    }
}
```

### 1.4 注意事项

**P操作的顺序**：必须先执行同步信号量的P操作，再执行互斥信号量的P操作。

**错误顺序**：
```c
P(mutex);   // 错误！先申请互斥
P(empty);   // 如果empty=0，会阻塞，但mutex已占用
```

这样会导致死锁。

---

## 二、读者-写者问题

### 2.1 问题描述

有读者和写者两组并发进程，共享一个数据文件。

**规则**：
- 允许多个读者同时读
- 只允许一个写者写
- 写者写时不允许读者读
- 读者读时不允许写者写

### 2.2 第一类读者-写者问题（读者优先）

**特点**：读者优先，可能导致写者饥饿。

```c
semaphore rw_mutex = 1;     // 互斥信号量，用于写者之间、读者与写者之间
semaphore mutex = 1;        // 互斥信号量，保护read_count
int read_count = 0;         // 读者计数

// 读者进程
void reader() {
    while (true) {
        P(mutex);
        read_count++;
        if (read_count == 1)    // 第一个读者
            P(rw_mutex);        // 阻止写者
        V(mutex);
        
        读数据;
        
        P(mutex);
        read_count--;
        if (read_count == 0)    // 最后一个读者
            V(rw_mutex);        // 允许写者
        V(mutex);
    }
}

// 写者进程
void writer() {
    while (true) {
        P(rw_mutex);            // 申请写权限
        写数据;
        V(rw_mutex);            // 释放写权限
    }
}
```

### 2.3 第二类读者-写者问题（写者优先）

**特点**：写者优先，防止写者饥饿。

```c
semaphore rw_mutex = 1;     // 互斥信号量
semaphore mutex = 1;        // 互斥信号量，保护read_count
semaphore w_mutex = 1;      // 互斥信号量，用于写者优先
int read_count = 0;

// 读者进程
void reader() {
    while (true) {
        P(w_mutex);           // 检查是否有写者等待
        P(mutex);
        read_count++;
        if (read_count == 1)
            P(rw_mutex);
        V(mutex);
        V(w_mutex);           // 允许其他读者或写者
        
        读数据;
        
        P(mutex);
        read_count--;
        if (read_count == 0)
            V(rw_mutex);
        V(mutex);
    }
}

// 写者进程
void writer() {
    while (true) {
        P(w_mutex);           // 申请写权限，阻止新读者
        P(rw_mutex);          // 申请写数据权限
        写数据;
        V(rw_mutex);
        V(w_mutex);           // 释放权限
    }
}
```

---

## 三、哲学家进餐问题

### 3.1 问题描述

五个哲学家围坐在圆桌旁，每两个哲学家之间有一根筷子。

**规则**：
- 哲学家只有两种状态：思考和进餐
- 哲学家必须同时拿到左右两根筷子才能进餐
- 进餐完毕后放下筷子继续思考

### 3.2 信号量设置

```c
semaphore chopstick[5] = {1, 1, 1, 1, 1};  // 5根筷子
```

### 3.3 错误方案（会导致死锁）

```c
void philosopher(int i) {
    while (true) {
        思考;
        P(chopstick[i]);        // 拿左边筷子
        P(chopstick[(i+1)%5]);  // 拿右边筷子
        进餐;
        V(chopstick[(i+1)%5]);  // 放右边筷子
        V(chopstick[i]);        // 放左边筷子
    }
}
```

**死锁原因**：如果五个哲学家同时拿起左边筷子，都会等待右边筷子，形成循环等待。

### 3.4 解决方案

#### 方案1：最多允许4个哲学家同时拿筷子

```c
semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore room = 4;         // 最多4个哲学家同时拿筷子

void philosopher(int i) {
    while (true) {
        思考;
        P(room);                // 申请进入房间
        P(chopstick[i]);
        P(chopstick[(i+1)%5]);
        进餐;
        V(chopstick[(i+1)%5]);
        V(chopstick[i]);
        V(room);                // 离开房间
    }
}
```

#### 方案2：奇数号哲学家先拿左边，偶数号先拿右边

```c
void philosopher(int i) {
    while (true) {
        思考;
        if (i % 2 == 1) {       // 奇数号
            P(chopstick[i]);
            P(chopstick[(i+1)%5]);
        } else {                // 偶数号
            P(chopstick[(i+1)%5]);
            P(chopstick[i]);
        }
        进餐;
        V(chopstick[(i+1)%5]);
        V(chopstick[i]);
    }
}
```

#### 方案3：使用AND型信号量（同时申请两个资源）

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

void philosopher(int i) {
    while (true) {
        思考;
        Swait(chopstick[i], chopstick[(i+1)%5]);  // 同时申请两个筷子
        进餐;
        Ssignal(chopstick[i], chopstick[(i+1)%5]); // 同时释放两个筷子
    }
}
```

---

## 四、睡眠的理发师问题

### 4.1 问题描述

理发店里有一位理发师、一把理发椅和n把供顾客等候的椅子。

**规则**：
- 如果没有顾客，理发师在理发椅上睡觉
- 当有顾客到来时，唤醒理发师
- 如果没有空椅子，顾客离开

### 4.2 信号量设置

```c
semaphore customers = 0;    // 等待的顾客数量
semaphore barber = 0;       // 理发师是否空闲
semaphore mutex = 1;        // 互斥信号量
int waiting = 0;            // 等待的顾客数
int CHAIRS = n;             // 椅子数量
```

### 4.3 解决方案

```c
// 理发师进程
void barber() {
    while (true) {
        P(customers);       // 等待顾客
        P(mutex);
        waiting--;
        V(barber);          // 理发师准备理发
        V(mutex);
        理发;
    }
}

// 顾客进程
void customer() {
    P(mutex);
    if (waiting < CHAIRS) {
        waiting++;
        V(customers);       // 通知理发师有顾客
        V(mutex);
        P(barber);          // 等待理发师
        理发;
    } else {
        V(mutex);           // 没有空椅子，离开
    }
}
```

---

## 五、考研重点

1. **生产者-消费者问题**：
   - 三个信号量的设置
   - P操作的顺序（先同步后互斥）
   - 代码实现

2. **读者-写者问题**：
   - 读者优先和写者优先的区别
   - 读者计数的使用
   - 代码实现

3. **哲学家进餐问题**：
   - 死锁的产生原因
   - 三种解决方案

4. **睡眠的理发师问题**：
   - 信号量的设置
   - 同步关系的分析

5. **解题技巧**：
   - 先分析同步关系
   - 确定信号量的数量和初值
   - 注意P操作的顺序
   - 检查是否有死锁可能

---

*下一节：2.6 进程通信*