🔒 进程同步

解决并发进程对共享资源的访问冲突，确保执行结果的正确性
信号量PV 生产者-消费者 读者-写者 哲学家就餐 管程
🔁 信号量PV操作
P(wait)申请资源 · V(signal)释放资源 · 观察信号量值和临界区状态
🎬 动画演示
📝 PV原语代码
P操作（wait）：申请一个资源。若S≥0则分配进入临界区；否则进程进入等待队列。
V操作（signal）：释放一个资源。若有等待进程则唤醒一个进入临界区。
初始信号量：
临界区中 等待队列 已离开 信号量值≥0表示可用资源数
初始 mutex=1，资源空闲，可以进入临界区
typedef struct { // 记录型信号量 int value; // 资源数量 Queue waiting; // 等待队列 } Semaphore; void P(Semaphore S) { // wait操作 S.value--; if (S.value < 0) { // 资源不足，阻塞当前进程 addToQueue(S.waiting, currentProcess); block(); // 让出CPU } } void V(Semaphore S) { // signal操作 S.value++; if (S.value <= 0) { // 有进程在等待，唤醒一个 Process p = removeFromQueue(S.waiting); wakeup(p); } }
整型信号量 vs 记录型信号量：
整型：忙等（spinlock），不会阻塞进程，浪费CPU
记录型：阻塞进程，让出CPU，符合"让权等待"原则
📦 生产者-消费者问题
三信号量协作 · 互斥访问缓冲区 · 可视化物品流动
🎬 动画演示
📝 代码解析
问题设定：有界缓冲区N=5，生产者生产物品放入缓冲区，消费者从缓冲区取出。
三个信号量：mutex=1（互斥访问缓冲区）、empty=N（空格数）、full=0（已填充数）
已填充 空槽位 empty(空格数) + full(已填数) = N
初始状态：缓冲区全部为空，empty=5, full=0
完整代码（竖排显示）：三个信号量协作 — empty、full、mutex
🔵 生产者进程
void producer() { while(1) { item = produce_item(); P(empty); // 1. 申请一个空格 P(mutex); // 2. 申请进入临界区 insert_item(item); V(mutex); // 3. 释放临界区 V(full); // 4. 增加满格数，唤醒消费者 } }
🟠 消费者进程
void consumer() { while(1) { P(full); // 1. 申请一个已填充格 P(mutex); // 2. 申请进入临界区 item = remove_item(); V(mutex); // 3. 释放临界区 V(empty); // 4. 增加空格数，唤醒生产者 consume_item(item); } }
⚠️ 信号量操作顺序很重要！
· 必须先P(empty/full)再P(mutex)，否则可能死锁
· 多个生产者和消费者时，必须加mutex保护对缓冲区的读写
📖 读者-写者问题
读者优先策略 · 读者可共享 · 写者必须互斥
🎬 动画演示
📝 代码解析
读者优先策略：只要有读者在读，新读者可以直接进入；写者必须等所有读者都离开才能写。
信号量：rmutex（保护readCount）、wrt（写者互斥）、readCount（当前读者数）
读者（可共享） 写者（互斥） 共享资源 多读者可同时访问
初始状态：无读者，无写者，共享资源空闲
📖 读者进程
void reader() { P(rmutex); readCount++; if (readCount == 1) P(wrt); // 第一个读者阻止写者 V(rmutex); // 读共享资源 read_data(); P(rmutex); readCount--; if (readCount == 0) V(wrt); // 最后一个读者唤醒写者 V(rmutex); }
✏️ 写者进程
void writer() { P(wrt); // 申请写互斥，阻塞直到无读者 // 写共享资源 write_data(); V(wrt); // 释放写互斥 }
读者优先的问题：如果读者持续不断进入，写者可能永远无法获得wrt（饥饿）。
写者优先：增加信号量wrt_1=1，写者申请后立即阻止新读者进入。
🍽️ 哲学家就餐问题
五名哲学家围坐圆桌 · 需要两根筷子才能吃饭 · 观察死锁与预防
🎬 动画演示
🔍 死锁分析
📝 代码解析
问题描述：五名哲学家围坐圆桌，每人需要左右两根筷子才能吃饭。 若每人同时拿起左边筷子，则所有人都在等右边筷子——死锁！
预防策略：限制最多4人同时就餐 · 奇偶规则拿筷子 · 一次拿两根
策略：
就餐中 等待筷子 思考中 死锁!
点击「步进一次」观察哲学家状态变化
死锁的四个必要条件在此全部满足：
· 互斥：筷子一次只能被一人使用
· 不剥夺：筷子不能被强制拿走
· 请求并保持：拿着左筷子等右筷子
· 循环等待：P0等P1、P1等P2...P4等P0

解决方案对比：
✅ 限制4人：最多4人同时就餐，必有1人能拿到两根筷子
✅ 奇偶规则：偶数号先拿L(顺时针相邻)再拿R(逆时针相邻)，奇数号先拿R再拿L，打破循环等待
✅ 管程：用管程封装拿/放筷子，一次最多拿两根
哲学家就餐问题 — 三种经典解法代码实现
解法一：限制最多4人同时就餐
Semaphore chopstick[5] = {1,1,1,1,1}; Semaphore limit = 4; // 最多4人同时就餐，打破死锁 void philosopher(int i) { while(1) { think(); // 思考 P(limit); // 先申请就餐名额 P(chopstick[i]); // 拿左筷子 P(chopstick[(i+1)%5]); // 拿右筷子 eat(); // 吃饭 V(chopstick[i]); // 放左筷子 V(chopstick[(i+1)%5]); // 放右筷子 V(limit); // 释放就餐名额 } }
解法二：奇偶规则（打破循环等待）
void philosopher(int i) { while(1) { think(); if (i % 2 == 0) { // 偶数号：先左后右 P(chopstick[i]); P(chopstick[(i+1)%5]); } else { // 奇数号：先右后左 P(chopstick[(i+1)%5]); P(chopstick[i]); } eat(); V(chopstick[i]); V(chopstick[(i+1)%5]); } }
解法三：一次拿两根筷子（AND信号量）
void philosopher(int i) { while(1) { think(); Swait(chopstick[i], chopstick[(i+1)%5]); // 原子操作：同时申请两根 eat(); Ssignal(chopstick[i], chopstick[(i+1)%5]); // 释放两根 } }
🏛️ 管程（Monitor）
高级同步机制 · 封装共享变量和条件变量 · 一次只允许一个进程进入
🎬 动画演示
📖 概念详解
管程定义：管程是一个封装了共享数据和对这些数据的操作的高级同步机制。 同一时刻只有一个进程/线程能在管程内执行。
点击按钮模拟：进程进入管程 → 执行操作 → 等待条件 → 被唤醒 → 离开
执行中 等待条件 共享数据 同一时刻只有1个进程在管程内
初始状态：管程空闲，无进程执行
管程定义：管程是一个封装了共享数据和对这些数据的操作的过程（函数）， 同一时刻只有一个进程/线程能在管程内执行。

核心组成：
· 共享数据（如缓冲区数组）
· 对数据的操作过程（enter/remove）
· 条件变量（condition variable）

条件变量操作：
· x.wait()：进程在条件x上等待
· x.signal()：唤醒一个在x上等待的进程
Hoare管程 vs Mesa管程：

Hoare：signal后立即让出CPU，被唤醒进程马上执行（更高效但复杂）
Mesa：signal后发信号者继续执行，被唤醒者等到下次调度才执行（需重新检查条件，用while循环）

管程 vs 信号量：
· 管程：封装性更好，不易出错
· 信号量：更底层，灵活但容易出错（顺序错误、遗漏P/V）
// 用管程实现生产者-消费者 monitor ProducerConsumer { condition notFull, notEmpty; void insert(item) { if (count == N) wait(notFull); buf[in] = item; in++; count++; signal(notEmpty); } item remove() { if (count == 0) wait(notEmpty); item = buf[out]; out++; count--; signal(notFull); return item; } }