# 实验六 同步机制——信号量集与哲学家就餐问题

## 一、实验内容

理解 Linux SystemV 信号量集同步机制，掌握 semget/semctl/semop，解决哲学家就餐死锁问题。

创建 5 个信号量（叉子），哲学家同时申请左右叉子，避免死锁。

## 二、实验设计

### 2.1 问题描述

5个哲学家围坐圆桌，每人面前有一碗饭，之间有一根筷子。哲学家要么思考要么吃饭，吃饭需要同时拿起左右两根筷子。

**死锁风险：** 若所有哲学家同时拿起左筷子，等待右筷子，将形成循环等待。

### 2.2 数据结构

```cpp
union semun {
    int val;
    struct semid_ds *buf;
    unsigned short *array;
    struct seminfo *__buf;
} arg;

int semid;  // 信号量集ID
```

每个信号量代表一根筷子，初值为1（可用）。

### 2.3 函数设计

| 函数 | 功能 |
|------|------|
| `main()` | 创建信号量集，fork 5个哲学家进程 |
| `philosopher(int i)` | 哲学家行为：思考→饥饿→吃饭→放下筷子 |
| `semget()` | 创建信号量集 |
| `semctl()` | 初始化信号量值 |
| `semop()` | 原子操作信号量（P/V） |

### 2.4 调用关系

```
main()
├── ftok() 生成key
├── semget() 创建5个信号量
├── semctl() 初始化每个信号量为1
└── fork() 创建5个哲学家进程
    └── philosopher(i)
        ├── 思考
        ├── semop(-1) 拿左筷子
        ├── semop(-1) 拿右筷子
        ├── 吃饭
        ├── semop(+1) 放左筷子
        └── semop(+1) 放右筷子
```

### 2.5 解决死锁策略

**问题：** 同时拿筷子可能死锁

**解决方案：** 原子操作多个信号量

```cpp
struct sembuf sbuf[2];
sbuf[0].sem_num = i;           // 左筷子
sbuf[0].sem_flg = SEM_UNDO;    // 进程退出自动释放
sbuf[1].sem_num = (i + 1) % 5; // 右筷子
sbuf[1].sem_flg = SEM_UNDO;

// 一次性申请/释放两根筷子
semop(semid, sbuf, 2);  // 原子操作
```

**关键：** `semop(semid, sbuf, 2)` 原子地执行两个操作，要么都成功要么都失败

## 三、编码实现

### 3.1 信号量集创建

```cpp
key_t key = ftok("fname", 1);
semid = semget(key, 5, IPC_CREAT | 0666);
```

**要点：**
- `ftok()` 生成唯一key
- `semget()` 创建包含5个信号量的集合
- `IPC_CREAT` 不存在则创建

### 3.2 信号量初始化

```cpp
arg.val = 1;
for (int i = 0; i < 5; i++)
    semctl(semid, i, SETVAL, arg);
```

**要点：** 每个信号量初值为1，表示筷子可用

### 3.3 哲学家线程实现

```cpp
void philosopher(int i) {
    struct sembuf sbuf[2];
    sbuf[0].sem_num = i;
    sbuf[0].sem_flg = SEM_UNDO;
    sbuf[1].sem_num = (i + 1) % 5;
    sbuf[1].sem_flg = SEM_UNDO;

    while (1) {
        printf("philosopher %d is thinking\n", i);
        sleep(2);

        printf("philosopher %d is hungry\n", i);
        sbuf[0].sem_op = -1;  // P(左筷子)
        sbuf[1].sem_op = -1;  // P(右筷子)
        semop(semid, sbuf, 2);  // 原子申请

        printf("philosopher %d is eating\n", i);
        sleep(2);

        sbuf[0].sem_op = 1;   // V(左筷子)
        sbuf[1].sem_op = 1;   // V(右筷子)
        semop(semid, sbuf, 2);  // 原子释放
    }
}
```

### 3.4 解决死锁的关键代码

```cpp
// 一次性申请两根筷子
sbuf[0].sem_op = -1;  // 申请左
sbuf[1].sem_op = -1;  // 申请右
semop(semid, sbuf, 2);  // 原子操作：要么都成功，要么都阻塞
```

**死锁避免原理：**
- 哲学家i和(i+1)%5不会同时饥饿并阻塞
- 当一个哲学家在吃饭时，其左右邻居最多只有一个能拿到一根筷子
- SEM_UNDO 确保进程异常退出时自动释放信号量

### 3.5 编译与运行

```bash
g++ exp06_source.cpp -o philosopher
./philosopher
```

**输出示例：**
```
philosopher 0 is thinking
philosopher 1 is thinking
philosopher 2 is thinking
philosopher 3 is thinking
philosopher 4 is thinking
philosopher 0 is hungry
philosopher 0 is eating
philosopher 2 is hungry
philosopher 2 is eating
...
```

## 四、实验结果

### 4.0 测试命令

```bash
# 编译
g++ exp06_source.cpp -o philosopher

# 运行（哲学家会一直运行，按 Ctrl+C 停止）
./philosopher

# 查看信号量（在另一终端）
ipcs -s

# 清理信号量（如果进程异常退出）
ipcrm -s $(ipcs -s | grep -E '^[0-9]+' | awk '{print $2}')
```

### 4.1 正常运行结果

```
philosopher 0 is thinking
philosopher 1 is thinking
philosopher 2 is thinking
philosopher 3 is thinking
philosopher 4 is thinking
philosopher 0 is hungry
philosopher 0 is eating
philosopher 2 is hungry
philosopher 2 is eating
philosopher 4 is hungry
philosopher 4 is eating
philosopher 1 is hungry
philosopher 1 is eating
...
```

**说明：**
- 无死锁发生
- 最多只有2个哲学家同时吃饭（不相邻）
- 交替思考和吃饭

### 4.2 信号量状态变化

```
初始: [1,1,1,1,1] (5根筷子都可用)

Philosopher 0 拿起筷子0,1: [0,0,1,1,1]
Philosopher 2 拿起筷子2,3: [0,0,0,0,1]
Philosopher 0 放下筷子0,1: [1,0,0,1,1]
Philosopher 4 拿起筷子4,0: [0,1,0,1,0]
```

### 4.3 并发控制验证

- 无相邻哲学家同时吃饭
- 循环等待条件被打破（原子操作）
- 不会有哲学家拿着筷子饿死

## 五、实验结果思考与体会

### 5.1 信号量集优势

| 特性 | 说明 |
|------|------|
| 原子操作 | semop可同时操作多个信号量 |
| SEM_UNDO | 进程退出自动释放资源 |
| 进程间同步 | 适用于亲缘或非亲缘进程 |

### 5.2 哲学家问题解决方案对比

| 方案 | 原理 | 优缺点 |
|------|------|--------|
| 原子操作 | 一次性拿两根筷子 | 简单有效，但只能两人同时吃 |
| 奇偶策略 | 奇数号先拿左，偶数号先拿右 | 破坏循环等待 |
| 最多N人 | 限制最多N-1人同时吃 | 需要额外计数信号量 |

### 5.3 思考问题解答

**问题1：用 clone/vfork 替代 fork**

可以用 clone 创建线程（共享地址空间）或 vfork 创建进程（共享地址空间直到 exec）。但哲学家问题关键是信号量同步，与进程/线程创建方式无关。

**问题2：用信号量集解决吸烟者问题**

吸烟者问题：3个吸烟者 + 1个供应者
- 供应者放两种原料，吸烟者拿原料做烟
- 需要信号量表示原料是否就绪

### 5.4 实验体会

1. **信号量集特点**：可以同时操作多个信号量，实现复杂同步

2. **死锁避免**：通过原子操作打破"占有并请求"条件

3. **SEM_UNDO 重要性**：防止进程异常退出导致的死锁

4. **经典问题理解**：哲学家就餐是经典的同步问题，理解了其解法有助于解决其他同步问题

5. **Linux IPC 机制**：semget/semctl/semop 是 SystemV 信号量接口，提供了强大的进程同步能力