同步与互斥：进程间的两种制约关系
本篇对应王道第二章同步部分（原 10 篇）。核心问题：进程同步是什么？不同进程间有什么关系？怎么用信号量把关系管起来？
一、同步与互斥是什么
多道程序环境下进程并发执行，不同进程间存在相互制约关系，为协调这些关系引入进程同步。
直观理解：系统里有加法进程和乘法进程，要结果正确必须先乘后加。但 OS 有异步性，不加以制约的话加法进程完全可能先跑——所以需要制约机制。
你和朋友编辑同一份文档，不沟通谁何时改，就会出现互相覆盖；进程同步就是防止这种问题发生在程序上的机制。
临界资源与临界区
一次仅允许一个进程使用的资源叫临界资源——打印机、共享变量、共享数据都是。对临界资源的访问必须互斥进行，访问它的那段代码叫临界区。
访问过程分四部分：
do{
entry section; // 进入区：检查能否进入，能则上锁（设"正在访问"标志）
critical section; // 临界区：访问临界资源的代码
exit section; // 退出区：清除"正在访问"标志
remainder section; // 剩余区：其他代码
}while(true);
同步：合作导致的制约
同步也称直接制约关系：为完成同一任务而建立的多个进程，因协调工作次序而等待、传递信息。源于相互合作。
例子：输入进程 A 通过单缓冲向进程 B 供数据——缓冲区空时 B 阻塞，A 放入数据后唤醒 B；缓冲区满时 A 阻塞，B 取走数据后唤醒 A。
互斥：争抢导致的制约
互斥也称间接制约关系：一个进程进临界区用临界资源时，另一个必须等。源于资源共享（争抢）。
例子：仅一台打印机，A 要打印时打印机已分给 B，A 阻塞；B 释放后系统唤醒 A。
简而言之：进程间合作导致的制约叫同步，进程间争抢资源导致的制约叫互斥。
同步机制四准则
| 准则 | 含义 |
|---|---|
| 空闲让进 | 临界区空闲时，允许一个请求进入的进程立即进入 |
| 忙则等待 | 已有进程在临界区，其他试图进入的必须等 |
| 有限等待 | 请求访问的进程能在有限时间内进入（不能饿死） |
| 让权等待 | 进不去时应立即释放处理机，防止忙等待 |
后面每种方法都拿这四条来打分。
二、互斥的实现（软件）
思路：进入区设置标志，用循环检查等待；退出区修改标志。
单标志法
一个整型变量 turn 指示轮到谁：turn=0 时 P0 进，turn=1 时 P1 进；用完把 turn 让给对方。
// P0: // P1:
while(turn != 0); while(turn != 1);
critical section; critical section;
turn = 1; turn = 0;
remainder section; remainder section;
问题：不满足"空闲让进"——对方不要进临界区，turn 永远不变，我就永远进不去。临界区只能强制交替使用。
双标志法先检查
每人一个标志 flag[]，先检查对方想不想进，再设置自己想进：
// P0: // P1:
while(flag[1]); while(flag[0]);
flag[0] = true; flag[1] = true;
critical section; critical section;
flag[0] = false; flag[1] = false;
好处是不用交替进入、可连续使用。问题：违背"忙则等待"——两进程几乎同时检查，都看到对方标志为 false，双双进入，互斥失效。
双标志法后检查
交换顺序：先设置自己想进，再检查对方：
// P0: // P1:
flag[0] = true; flag[1] = true;
while(flag[1]); while(flag[0]);
critical section; critical section;
flag[0] = false; flag[1] = false;
互斥保住了，问题：违背"空闲让进"和"有限等待"——同时想进时双方互相谦让，谁也进不了，饥饿（"礼让"事故）。
Peterson 算法
单标志 + 双标志后检查的结合：flag 解决互斥，turn 解决饥饿。想进时先插自己的旗，再说一句**"轮到你先"**：
// P0: // P1:
flag[0] = true; flag[1] = true;
turn = 1; turn = 0;
while(flag[1] && turn == 1); while(flag[0] && turn == 0);
critical section; critical section;
flag[0] = false; flag[1] = false;
双方都想进时，turn 只能是一方的值——谦让有先后，turn 是最后表态的那个，于是唯一的一方进入。四准则全满足（除"让权等待"，它还在忙等）。
缺点：依赖原子操作、只适用于两个进程。
硬件实现
中断屏蔽
CPU 只在中断时进行进程切换，那最简单直接暴力的方式——把中断关了：
void enter_critical_section() { disable_interrupts(); /* 临界区 */ }
void leave_critical_section() { enable_interrupts(); /* 剩余区 */ }
简单直接，但限制了处理机交替执行程序的能力，效率明显降低；关中断的权力不能交给用户——某进程关了中断不再开，系统可能因此终止。只适用于单处理机、不适合长临界区。
Test-and-Set（TS）
原子地"读旧值 + 置 1"：
int test_and_set(int *lock) {
int original = *lock;
*lock = 1;
return original;
}
// 加锁: while(test_and_set(&lock)); 解锁: lock = 0;
锁为 0 时第一个调用者拿到旧值 0 进入，其余人拿到 1 忙等。适合短时间互斥。
Compare-and-Swap（CAS）
原子地"比较预期旧值，相同则换新值"：
int compare_and_swap(int *value, int expected, int new_value) {
int temp = *value;
if (*value == expected) *value = new_value;
return temp;
}
// 加锁: while(compare_and_swap(&lock, 0, 1) != 0);
比 TS 更适合复杂同步模式（无锁数据结构）。另有 LL/SC 原语（Load-Link 读值，Store-Conditional 仅当地址未被改过才写入），能检测读写间是否发生冲突。
硬件方法小结
优点：适用于任意数目进程、单/多处理机都行；简单、易验证正确性；支持多个临界区（每区一个布尔变量）。缺点：等待时消耗处理机时间、不能让权等待（忙等）；从等待进程中随机选一个进入，可能饥饿。
互斥锁（mutex lock）
解决临界区最简单的工具：进临界区 acquire() 拿锁，出临界区 release() 放锁：
acquire() { while(!available) ; available = false; }
release() { available = true; }
两个操作必须原子（通常用硬件机制实现）。主要缺点还是忙等待——多个进程共享一个 CPU 时白白浪费周期，所以互斥锁常用于多处理器系统（一个核上忙等，不妨碍别的核干活）。
三、信号量
信号量机制功能更强，互斥与同步都能解决。只能被两个标准原语访问：wait(S) 和 signal(S)，即 P 操作和 V 操作（P=Proberen 尝试，V=Verhogen 增加）——进程通信那一篇提过，这里展开。
整型信号量 → 忙等
wait(S) { while(S <= 0); S = S - 1; } // S<=0 就一直测
signal(S) { S = S + 1; }
问题一目了然：S≤0 时不断测试，不遵循"让权等待"，进程处于忙等；而且没有等待队列。
记录型信号量 → 真正可用
整型变量 value 之外，再加一个进程链表 L 链接所有等待进程：
typedef struct {
int value;
struct process *L;
} semaphore;
void wait(semaphore S) { // P操作
S.value--; // 请求一个该类资源
if (S.value < 0) { // 资源分配完毕
add this process to S.L;
block(S.L); // 自我阻塞，放弃处理机
}
}
void signal(semaphore S) { // V操作
S.value++; // 释放一个资源
if (S.value <= 0) { // 仍有进程在等
remove a process P from S.L;
wakeup(P); // 唤醒队首等待进程
}
}
读法：S.value 的值就是剩余资源数；减完小于 0，说明有人没分到，去排队；V 完仍 ≤0，说明队列里还有人，唤醒一个。这下"让权等待"落实了——阻塞而不是忙等。
三种用法
实现同步：A 必须等 B 完成后才能执行——信号量初值 0，B 干完 signal(sem)，A 开头 wait(sem)：
semaphore sem = 0;
// B: do_something(); signal(sem);
// A: wait(sem); continue_work();
实现互斥：初值 1，进出临界区夹 P/V：
semaphore mutex = 1;
// wait(mutex); critical_section(); signal(mutex);
互斥是不同进程对同一信号量做 P/V：某进程 P 成功进入，退出后由它自己 V，表示可让其他进程进了。
实现前驱关系：每条前驱边设一个初值 0 的信号量，前件末尾 V、后件开头 P：
semaphore a1=a2=b1=b2=c=d=e=0;
S1(){ ……; V(a1); V(a2); }
S2(){ P(a1); ……; V(b1); V(b2); }
S3(){ P(a2); ……; V(c); }
S4(){ P(b1); ……; V(d); }
S5(){ P(b2); ……; V(e); }
S6(){ P(c); P(d); P(e); ……; }
小结口诀
- 同步问题：某行为要用到某种资源 → 行为前面 P 一下；某行为会提供某种资源 → 行为后面 V 一下
- 互斥问题：PV 操作紧夹使用互斥资源的那个行为，中间不能夹其他冗余代码
四、管程
信号量机制的问题：每个要访问临界资源的进程都得自备同步的 PV 操作，大量分散的同步操作不好管，还容易因操作不当导致死锁。
于是有了管程：用共享数据结构抽象表示系统中的共享资源，把对该数据结构的操作定义成一组过程，进程对资源的申请释放都通过这组过程——统一管理所有访问，互斥由管程保证，无须程序员自己实现。
管程很像一个类：
monitor Demo {
共享数据结构 S; // 局部于管程内部的共享数据
init_code() { S = 5; } // 初始化语句
take_away() { S--; } // 过程：申请资源
give_back() { S++; } // 过程：归还资源
}
- 共享数据只能被管程内的过程访问；进程只有通过管程内的过程才能进入
- 每次只允许一个进程进入管程（各进程串行执行管程内的过程）——互斥自动保证
条件变量
进程进管程后可能被阻塞，若它不释放管程，别人也进不来。于是把阻塞原因定义为条件变量 condition，每个条件变量对应一个等待队列。两个操作：
x.wait：条件不满足时，调用进程插入 x 的等待队列，并释放管程（别人能用）x.signal：条件变化时，唤醒一个因 x 阻塞的进程
monitor Demo {
共享数据结构 S; condition x;
take_away() {
if (S <= 0) x.wait(); // 资源不够，在x上阻塞等待并释放管程
dosomething;
}
give_back() {
归还资源 dosomething;
if (有进程在等待) x.signal();
}
}
条件变量 vs 信号量（高频考点）：wait/signal 相似，都能阻塞唤醒；但条件变量没有值，只实现排队等待；信号量有值，反映剩余资源数——管程里剩余资源数由共享数据结构记录。
五、经典同步问题
生产者-消费者
生产者往共享缓冲区放数据，消费者取走处理。挑战：缓冲区满不能写、空不能读。三个信号量：
empty = N（空闲位置数）、full = 0（已占用数）——管"同步"mutex = 1（互斥访问缓冲区）——管"互斥"
semaphore empty = N, full = 0, mutex = 1;
void producer() {
while (true) {
item = produce_item();
wait(empty); // 先同步：等空位
wait(mutex); // 再互斥：锁缓冲区
put_item_into_buffer(item);
signal(mutex);
signal(full); // 通知：多了一件
}
}
void consumer() {
while (true) {
wait(full); // 等数据
wait(mutex);
item = take_item_from_buffer();
signal(mutex);
signal(empty); // 通知：空了一个位
consume_item(item);
}
}
⚠️ P 操作顺序不能颠倒：先 wait(mutex) 再 wait(empty)，缓冲区满时生产者会拿着锁去等空位——死锁。同步 P 在前，互斥 P 在后。
读者-写者
多个读者可同时读，写者必须独占。核心技巧：计数器 + 第一个/最后一个读者负责加解锁：
semaphore rw_mutex = 1; // 写者与"第一/最后读者"竞争
semaphore mutex = 1; // 保护 read_count
int read_count = 0;
void reader() {
while (true) {
wait(mutex);
read_count++;
if (read_count == 1) wait(rw_mutex); // 第一个读者锁资源
signal(mutex);
read_data();
wait(mutex);
read_count--;
if (read_count == 0) signal(rw_mutex); // 最后一个读者放资源
signal(mutex);
}
}
void writer() {
while (true) {
wait(rw_mutex); // 写者直接独占
write_data();
signal(rw_mutex);
}
}
公平性权衡：基本版里读者源源不断时写者饥饿。改进思路：加队列/写者优先规则（如读写公平法，写者到达后堵住后续读者）。这个问题的价值就在权衡效率、公平与简单性。
哲学家进餐
五位哲学家围圆桌，每两人之间一根筷子，进餐需要同时拿左右两根。5 根筷子 = 5 个初值 1 的信号量：
semaphore chopstick[5] = {1,1,1,1,1};
void philosopher(int i) {
while (true) {
think();
wait(chopstick[i]); // 先左
wait(chopstick[(i+1) % 5]); // 再右
eat();
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
}
}
naive 版本的问题：五人同时拿起左边筷子，全在等右边——死锁。经典解法：只让一位哲学家（如编号最大的）先拿右边再拿左边，破坏"循环等待"，至少保证一人能凑齐两根。
这个思路其实和贪心是相反的——贪心强调争取眼前最好的，不考虑后果；哲学家问题若用贪心解，眼前有筷子能拿就拿，就会死锁。若不仅考虑眼前一步、还考虑下一步——能不能一次拿起两根筷子才做决定——就能避开死锁。这是哲学家问题的精髓：多想一步，而不是见好就抢。
吸烟者
三个吸烟者各拥有无限量的一种材料（烟草/纸/火柴各一），卷一支烟需要两种材料。供应者每次随机放两种材料上桌，拥有第三种材料的吸烟者拿走、卷、抽，然后发信号让供应者继续：
semaphore agentSem = 1;
semaphore tobacco = 0, paper = 0, match = 0;
void agent() { // 供应者：随机放两种
while (true) {
wait(agentSem);
if (random() == 0) { signal(tobacco); signal(paper); }
else if (random() == 1) { signal(paper); signal(match); }
else { signal(tobacco); signal(match); }
}
}
void smoker_with_tobacco() { // 有烟草的人：等纸和火柴
while (true) {
wait(paper); wait(match);
smoke();
signal(agentSem); // 抽完叫供应者继续
}
}
// smoker_with_paper / smoker_with_match 同理，等待各自缺的两种
四个问题的关注点各不相同：
| 问题 | 关注点 |
|---|---|
| 生产者-消费者 | 缓冲管理、满不写空不读的协调 |
| 读者-写者 | 读写公平性与效率、防写者饿死 |
| 哲学家进餐 | 循环等待的死锁避免、资源公平分配 |
| 吸烟者 | 按需分配资源、供应者与消费者的接力协调 |
它们都是同一件事的不同切面：多进程如何安全有效地共享资源、协调操作，各自给出一种避免竞争条件、死锁和饥饿的设计视角。
六、盲点
- P 操作顺序是送命题：同步信号量的 P 在前，互斥信号量的 P 在后；先锁后等 = 拿着资源等资源，死锁预备役
- 信号量
S.value的含义：>0 剩余资源数；<0 其绝对值 = 排队等待的进程数（这个负数含义选择题常考） - 记录型信号量才满足"让权等待"，整型信号量是忙等
- 管程里的条件变量没有值——值在共享数据结构里；信号量的值反映剩余资源
- 单标志法违反"空闲让进"（强制交替）；双标志先检查违反"忙则等待"（都能进）；双标志后检查违反"空闲让进+有限等待"（互相谦让全饿着）；Peterson 全满足但忙等
- 硬件方法互斥绝对可靠，但都忙等，且随机选人可能饥饿
- 哲学家问题与贪心相反：能拿不一定拿，先想"能否一次拿齐"
- 练习题有 30 多页……先把大概知识点过一遍，二轮再来细究——本篇先立框架，题感靠二轮
资源管不好会怎样？极端情况就是死锁 → 05-死锁
💬 评论