第六章：进程同步

1. 背景：为什么需要同步？

问题根源

当多个进程（或线程）并发访问共享数据时，如果执行顺序不当，可能会导致数据不一致的问题。
这是因为一个进程的执行可能会被另一个进程中断在任何时候，导致一系列操作（“读-改-写”）并非原子性地完成。

经典例子：生产者-消费者问题中的 `counter` 变量

假设 counter 初始为5。
生产者想执行 counter++，消费者想执行 counter--。
这两个操作在机器指令层面都不是一步完成的，通常需要三步：
1. 将 counter 的值从内存加载到寄存器。
2. 在寄存器中增加或减少该值。
3. 将新值从寄存器存回内存。
可能的错误交错执行顺序：
- 生产者：register1 = counter (reg1 = 5)
- 生产者：register1 = register1 + 1 (reg1 = 6)
- 消费者：register2 = counter (reg2 = 5) // 消费者读到了旧值！
- 消费者：register2 = register2 - 1 (reg2 = 4)
- 生产者：counter = register1 (counter = 6)
- 消费者：counter = register2 (counter = 4)
结果：最终 counter 的值是4，而正确值应为5。这就是著名的竞态条件。

结论：我们需要一种机制，来确保在任何时候只有一个进程可以操作共享变量。这段访问共享资源的代码被称为临界区。

2. 临界区问题的解决方案

临界区问题的三个要求

互斥：如果一个进程正在其临界区内执行，那么其他进程不能进入它们的临界区。
进步：如果没有进程在临界区内，并且有进程希望进入临界区，那么选择哪个进程进入不能无限期推迟。
有限等待：从一个进程提出进入临界区的请求直到该请求被允许，其他进程进入其临界区的次数存在上限（防止饥饿）。

解决方案的演进

1. Peterson 算法（软件方案）

一个经典的两个进程在软件层面的解决方案。
通过共享变量 turn（轮到谁）和 flag[2]（谁想进入）来协调。
它满足了互斥、进步和有限等待的要求，但在现代计算机体系结构上可能不保证有效（由于内存排序问题）。

2. 硬件同步方案

禁用中断：在单处理器系统中，在临界区内禁用中断，可以防止被抢占。但不适用于多处理器系统，且将控制权交给用户进程是危险的。
原子硬件指令：现代硬件提供了特殊的、不可中断的指令，如：
- TestAndSet()：测试一个值，如果为假则立即将其置为真。
- Swap()：交换两个位置的内容。
这些指令可以用来构建更高级的同步工具（如锁、信号量），但它们本身通常需要忙等待（自旋），会浪费CPU时间。

3. 信号量

信号量是解决同步问题的高级、强大且通用的工具。

什么是信号量？

一个整型变量 S，只能通过两个原子操作来访问：
- wait(S)（或 P(S)）：
  c wait(S) { while (S <= 0); // 忙等待（如果采用忙等待实现） S--; }
- signal(S)（或 V(S)）：
  c signal(S) { S++; }

信号量的类型

计数信号量：其值可以在一个不受限制的域内取值。用于控制访问具有多个实例的某种资源。
二进制信号量：其值只能是0或1。用于实现互斥锁，解决临界区问题。

用信号量解决临界区问题（n个进程）

semaphore mutex = 1; // 初始化为1的二进制信号量  

do {  
    wait(mutex);  
    // 临界区  
    signal(mutex);  
    // 剩余区  
} while (TRUE);

信号量的实现（无忙等待）

为了避免忙等待造成的CPU浪费，实际的信号量实现中，当一个进程在 wait 操作中阻塞时，它会将自己挂起，放入与该信号量相关的等待队列中。

wait 和 signal 操作的定义变为：

wait(S) {  
    S.value--;  
    if (S.value < 0) {  
        // 将当前进程加入 S.L 等待队列  
        block(); // 挂起该进程  
    }  
}  

signal(S) {  
    S.value++;  
    if (S.value <= 0) {  
        // 从 S.L 等待队列中移除一个进程 P  
        wakeup(P); // 唤醒该进程  
    }  
}

信号量的值：
- 当 S.value >= 0 时，表示可用资源的数量。
- 当 S.value < 0 时，其绝对值表示正在等待该信号的进程数量。

信号量的应用

互斥：如上所述，使用一个初始值为1的二进制信号量。
进程同步：确保一个进程中的一段代码 A 在另一个进程中的代码 B 之前执行。
- 使用一个初始值为0的信号量 sync。
- 进程1：A; signal(sync);
- 进程2：wait(sync); B;

4. 经典同步问题

1. 有限缓冲问题（生产者-消费者）

共享数据：一个大小为 n 的缓冲区。
信号量：
- mutex = 1：用于保证对缓冲区的互斥访问（二进制信号量）。
- empty = n：计数信号量，表示空缓冲区的数量。
- full = 0：计数信号量，表示满缓冲区的数量。
生产者代码：
c do { // 生产一个产品 nextp wait(empty); // 等待有空缓冲区 wait(mutex); // 获取缓冲区互斥锁 // 将 nextp 加入缓冲区 signal(mutex); // 释放缓冲区互斥锁 signal(full); // 增加一个满缓冲区 } while (TRUE);
消费者代码：
c do { wait(full); // 等待有满缓冲区 wait(mutex); // 获取缓冲区互斥锁 // 从缓冲区取出一个产品到 nextc signal(mutex); // 释放缓冲区互斥锁 signal(empty); // 增加一个空缓冲区 // 消费产品 nextc } while (TRUE);

2. 读者-写者问题

要求：允许多个读者同时读，但只允许一个写者写，且写者工作时读者不能读。
共享数据：
- readcount = 0：正在读的读者数量。
- mutex = 1：保护对 readcount 的互斥访问。
- wrt = 1：供写者使用的互斥信号量，也被第一个进入的读者和最后一个离开的读者使用。
写者代码：
c do { wait(wrt); // ... 写入 ... signal(wrt); } while (TRUE);
读者代码：
c do { wait(mutex); // 锁住 readcount readcount++; if (readcount == 1) // 如果是第一个读者 wait(wrt); // 阻止写者 signal(mutex); // ... 读取 ... wait(mutex); readcount--; if (readcount == 0) // 如果是最后一个读者 signal(wrt); // 允许写者 signal(mutex); } while (TRUE);
潜在问题：可能导致写者饥饿（如果读者源源不断）。

3. 哲学家进餐问题

解决方案1：限制就餐人数（破坏“请求与保持”）

思想：通过一个额外的信号量，保证最多只有 4 个哲学家同时尝试去拿筷子。这样，至少有一个哲学家能够成功拿到两支筷子，从而打破循环等待。
信号量定义：
- semaphore chopstick[5] = {1, 1, 1, 1, 1}; // 每支筷子一个信号量，初始为1，表示可用。
- semaphore eating_limit = 4; // 关键！ 限制同时进餐的哲学家数量。

哲学家 i 的代码：
```c
do {
wait(eating_limit); // 首先检查是否还能允许更多人吃饭

  wait(chopstick[i]);       // 拿起左边的筷子  
  wait(chopstick[(i+1)%5]); // 拿起右边的筷子  

  // ... 吃饭 ...  

  signal(chopstick[i]);       // 放下左边的筷子  
  signal(chopstick[(i+1)%5]); // 放下右边的筷子  

  signal(eating_limit);   // 释放一个就餐名额  

  // ... 思考 ...

} while (TRUE);
```

解决方案2：同时拿起两支筷子（破坏“请求与保持”）

思想：将“拿左筷”和“拿右筷”两个操作变成一个原子操作。要么同时拿到两只，要么一只都不拿。这通常需要一个互斥锁来保护拿筷子的整个过程。
信号量定义：
- semaphore chopstick[5] = {1, 1, 1, 1, 1};
- semaphore mutex = 1; // 关键！ 用于让拿筷子的过程互斥。

哲学家 i 的代码：


do {  
    wait(mutex);                // 锁住整个拿筷子的过程  

    wait(chopstick[i]);         // 拿起左边的筷子  
    wait(chopstick[(i+1)%5]);   // 拿起右边的筷子  

    signal(mutex);              // 释放锁  

    // ... 吃饭 ...  

    signal(chopstick[i]);       // 放下左边的筷子  
    signal(chopstick[(i+1)%5]); // 放下右边的筷子  

    // ... 思考 ...  
} while (TRUE);  

这个方案虽然简单，但并发度不高，因为一次只能有一个哲学家在拿筷子。

解决方案3：非对称策略（破坏“循环等待”）

思想：通过一个简单的规则来打破“循环等待”。让奇数编号和偶数编号的哲学家拿筷子的顺序不同，从而破坏那个圆环。
信号量定义：
- semaphore chopstick[5] = {1, 1, 1, 1, 1}; // 和初始方案一样。
哲学家 i 的代码：
```
do {  
    if (i % 2 == 0) {  
        // 偶数号哲学家：先左后右  
        wait(chopstick[i]);  
        wait(chopstick[(i+1)%5]);  
    } else {  
        // 奇数号哲学家：先右后左  
        wait(chopstick[(i+1)%5]);  
        wait(chopstick[i]);  
    }  

    // ... 吃饭 ...  

    signal(chopstick[i]);  
    signal(chopstick[(i+1)%5]);  

    // ... 思考 ...  
} while (TRUE);  
```
为什么这样能避免死锁？
我们以哲学家0（偶数）和哲学家1（奇数）为例：
- 哲学家0（先左后右）：他会先拿到C0。
- 哲学家1（先右后左）：他会先尝试拿C2（他的右边），而不是C1。
  这样，哲学家0和哲学家1竞争的资源（C0和C1）不再是循环依赖的。最坏情况是，偶数号哲学家们会先拿到他们左边的筷子，而奇数号哲学家们会先拿到他们右边的筷子，由于顺序不同，不会形成所有哲学家都持有一支筷子并等待另一支的闭环。

5. 管程

为什么需要管程？

使用信号量编程容易出错，wait 和 signal 操作的顺序至关重要，错误的顺序可能导致死锁或违反互斥。
管程是一种高级语言构造，旨在让同步更简单、更安全。

什么是管程？

一个管程是一个模块，它封装了：
1. 共享变量。
2. 对这些变量进行操作的一组过程。
3. 用于初始化这些变量的代码。
关键特性：管程保证互斥——在任何时候，最多只有一个进程可以在管程内处于活动状态。编译器会自动在管程过程的入口和出口插入互斥锁代码。

条件变量

当一个进程进入管程后，发现需要等待某个条件 C 为真，它不能一直占用管程，否则其他进程无法进入。
条件变量 x 用于这种情况下的等待和通知。
x.wait()：调用此操作的进程将被挂起，并释放对管程的互斥访问。另一个进程现在可以进入管程。
x.signal()：唤醒一个在 x.wait() 上挂起的进程。如果没有进程挂起，则此操作无效。

用管程解决哲学家进餐问题

管程内部维护一个状态数组 state[5]（思考、饥饿、就餐）。
定义一个 test(i) 函数：如果哲学家 i 是饥饿的，并且他的左右邻居都不在就餐，那么他就可以开始就餐。
pickup(i) 操作：将哲学家 i 设为饥饿，调用 test(i)，如果还不能就餐，就在条件变量 self[i] 上等待。
putdown(i) 操作：将哲学家 i 设为思考，并测试他的左右邻居是否可以通过 test 函数开始就餐。

管程的优势：将同步的复杂性封装在管程内部，使用者只需调用 pickup 和 putdown 这样的高级接口，不易出错。

6. 同步示例

Solaris

使用自适应互斥锁：如果锁被占用，在多处理器上会先自旋一小段时间，如果还无法获取，再进入睡眠。这适用于锁持有时间很短的场景。
使用读者-写者锁和条件变量。
使用转门来管理等待获取锁的线程队列。

Windows

在单处理器上使用中断屏蔽来保护全局资源。
在多处理器上使用自旋锁。
提供分发器对象，这些对象可以作为互斥体、信号量或事件（类似于条件变量）使用。

第六章：进程同步

BIMU

1. 背景：为什么需要同步？

问题根源

经典例子：生产者-消费者问题中的 `counter` 变量

2. 临界区问题的解决方案

临界区问题的三个要求

解决方案的演进

1. Peterson 算法（软件方案）

2. 硬件同步方案

3. 信号量

什么是信号量？

信号量的类型

用信号量解决临界区问题（n个进程）

信号量的实现（无忙等待）

信号量的应用

4. 经典同步问题

1. 有限缓冲问题（生产者-消费者）

2. 读者-写者问题

3. 哲学家进餐问题

解决方案1：限制就餐人数（破坏“请求与保持”）

解决方案2：同时拿起两支筷子（破坏“请求与保持”）

解决方案3：非对称策略（破坏“循环等待”）

5. 管程

为什么需要管程？

什么是管程？

条件变量

用管程解决哲学家进餐问题

6. 同步示例

Solaris

Windows

其他文章

第七章：进程同步与死锁

第五章：CPU调度

第六章：进程同步

BIMU

1. 背景：为什么需要同步？

问题根源

经典例子：生产者-消费者问题中的 counter 变量

2. 临界区问题的解决方案

临界区问题的三个要求

解决方案的演进

1. Peterson 算法（软件方案）

2. 硬件同步方案

3. 信号量

什么是信号量？

信号量的类型

用信号量解决临界区问题（n个进程）

信号量的实现（无忙等待）

信号量的应用

4. 经典同步问题

1. 有限缓冲问题（生产者-消费者）

2. 读者-写者问题

3. 哲学家进餐问题

解决方案1：限制就餐人数（破坏“请求与保持”）

解决方案2：同时拿起两支筷子（破坏“请求与保持”）

解决方案3：非对称策略（破坏“循环等待”）

5. 管程

为什么需要管程？

什么是管程？

条件变量

用管程解决哲学家进餐问题

6. 同步示例

Solaris

Windows

其他文章

第七章：进程同步与死锁

第五章：CPU调度

经典例子：生产者-消费者问题中的 `counter` 变量