[!info] related notes 操作系统 MOC

同步 / 互斥 / 信号量 / PV

速记结论（背就够用）

• 互斥：同一时刻只能一个进入临界区（资源使用权）
• 同步：强调先后顺序/配合（执行时序）
• 信号量：既能做互斥（mutex=1），也能做同步（计数型）

1) 为什么要同步互斥

共享资源会出现竞态条件（race condition），导致数据不一致。

2) 临界资源与临界区

• 临界资源：一次只允许一个进程使用
• 临界区：访问临界资源的那段代码

互斥的四个原则：空闲让进、忙则等待、有限等待、让权等待。

3) P/V 操作（最常考定义）

• P（wait/down）：申请资源；不够就阻塞
• V（signal/up）：释放资源；唤醒等待者

4) 经典模型题（先记模板）

4.1 生产者-消费者

问题描述：

有一个大小为 n 的缓冲池，生产者进程生产物品并放入缓冲池，消费者进程从缓冲池取出物品并消费。缓冲池是临界资源，一次只能有一个进程访问。

信号量定义：

• mutex = 1（互斥访问缓冲区）
• empty = n（空位数量，初始为缓冲池大小）
• full = 0（产品数量，初始为 0）

完整代码：

semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;

// 生产者进程
void producer() {
    while(true) {
        生产一个产品;
        P(empty);      // 申请一个空位
        P(mutex);      // 进入临界区
        将产品放入缓冲区;
        V(mutex);      // 离开临界区
        V(full);       // 产品数+1
    }
}

// 消费者进程
void consumer() {
    while(true) {
        P(full);       // 申请一个产品
        P(mutex);      // 进入临界区
        从缓冲区取出产品;
        V(mutex);      // 离开临界区
        V(empty);      // 空位数+1
        消费产品;
    }
}

典型考题：

题目：设有 3 个生产者和 2 个消费者，共享一个大小为 5 的缓冲池。初始时刻缓冲池为空。

问题 1：写出信号量的初值

答案：mutex = 1, empty = 5, full = 0

问题 2：若生产者依次放入 5 个产品后，再执行 P(empty) 会怎样？

答案：empty = 0，第 6 个 P(empty) 会阻塞生产者

问题 3：若先执行 V(full) 再执行 V(mutex) 会怎样？

答案：可能导致错误。如果此时有消费者在等 full，被唤醒后可能因为 mutex 仍为 0 而阻塞

易错点：

1. P 操作顺序：必须先 P(empty/full) 再 P(mutex)，否则可能死锁
2. V 操作顺序：V(full/empty) 和 V(mutex) 顺序可以交换
3. 不能对 mutex 做 V 操作超过 1 次

4.2 读者-写者

问题描述：

多个进程共享一个数据对象，读者进程只读取数据，写者进程修改数据。允许多个读者同时读，但写者与其他写者、写者与读者都必须互斥。

读优先方案：

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);
    }
}

写优先方案：

semaphore rw_mutex = 1;
semaphore mutex = 1;
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);
    }
}

典型考题：

题目：有读者 1、读者 2、写者 1、写者 2 四个进程，初始状态为读优先。

问题 1：若读者 1 正在读取，此时读者 2 申请读，会发生什么？

答案：读者 2 可以直接读取，因为 read_count = 2，不需要申请 rw_mutex

问题 2：若读者 1 正在读取，此时写者 1 申请写，会发生什么？

答案：写者 1 被阻塞，因为 rw_mutex 被读者 1 占用

问题 3：若读者 1、2 正在读取，读者 3 退出，此时写者 1 能写吗？

答案：不能，因为 read_count = 1（还剩读者 2），rw_mutex 仍被占用

问题 4：什么情况下写者会被饿死？

答案：读优先方案中，如果持续有读者到达，写者可能永远得不到写锁

易错点：

1. read_count 必须用 mutex 保护，否则会出现竞态
2. 第一个读者负责加锁，最后一个读者负责解锁
3. 写优先方案需要额外的 w_mutex 信号量

4.3 哲学家进餐

问题描述：

5 个哲学家围坐在圆桌旁，每两人之间有一根筷子，共 5 根。每个哲学家需要同时拿起左右两根筷子才能进餐。

问题分析：

如果每个哲学家都先拿左边筷子再拿右边筷子，可能出现死锁：每个哲学家都拿着左边筷子等待右边筷子。

解决方案 1：限制同时进餐人数

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore limit = 4;  // 最多 4 人同时进餐

void philosopher(int i) {
    while(true) {
        P(limit);           // 限制人数
        P(chopstick[i]);    // 拿左边筷子
        P(chopstick[(i+1)%5]); // 拿右边筷子
        
        进餐;
        
        V(chopstick[(i+1)%5]); // 放右边筷子
        V(chopstick[i]);       // 放左边筷子
        V(limit);              // 释放名额
    }
}

解决方案 2：奇偶编号不同顺序

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

void philosopher(int i) {
    while(true) {
        if(i % 2 == 0) {
            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：仅当两根筷子都可用时才拿

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;

void philosopher(int i) {
    while(true) {
        P(mutex);
        P(chopstick[i]);
        P(chopstick[(i+1)%5]);
        V(mutex);
        
        进餐;
        
        V(chopstick[(i+1)%5]);
        V(chopstick[i]);
    }
}

典型考题：

题目：5 个哲学家，5 根筷子，初始都未进餐。

问题 1：为什么会出现死锁？

答案：每个哲学家都拿着左边筷子，等待右边筷子，形成环路等待

问题 2：若限制最多 4 人进餐，能否避免死锁？

答案：能。因为最多 4 个哲学家，至少有 1 个能拿到两根筷子

问题 3：若哲学家 0、2、4 同时进餐，需要几根筷子？

答案：需要 6 根，但只有 5 根，所以不可能同时 3 人进餐

易错点：

1. 死锁四条件：互斥、占有且等待、不可抢占、循环等待
2. 解决方案核心：破坏四个条件中的任意一个
3. P 操作顺序很重要：先拿哪根筷子可能影响死锁

高频陷阱

• P/V 顺序写反：先 P 同步量再 P mutex（一般先拿资格，再进临界区）
• 忘记 V：一旦漏 V 基本就是“人为制造死锁”

5) 同步与互斥的典型例题

5.1 互斥问题

题目：有两个进程 P1 和 P2，共享变量 x（初值为 0），都要执行 x++ 100 次。

// 不加互斥的代码
void process() {
    for(int i = 0; i < 100; i++) {
        x++;  // 非原子操作：读-改-写
    }
}

问题：最终 x 的值是多少？

分析：x++ 实际是三条指令：

1. LOAD x → 寄存器
2. 寄存器 +1
3. STORE 寄存器 → x

如果 P1 和 P2 并发执行，可能出现：

• P1: LOAD x (0) → 寄存器 R1
• P2: LOAD x (0) → 寄存器 R2
• P1: R1+1 = 1
• P2: R2+1 = 1
• P1: STORE R1 → x (x=1)
• P2: STORE R2 → x (x=1)

答案：x 最终可能小于 200，取决于调度顺序

解决：用 P/V 操作互斥

semaphore mutex = 1;

void process() {
    for(int i = 0; i < 100; i++) {
        P(mutex);
        x++;
        V(mutex);
    }
}

5.2 同步问题

题目：进程 P1 计算 x = a + b，进程 P2 计算 y = x * c，需要保证 P1 先执行。

代码：

semaphore sync = 0;

// P1 进程
void P1() {
    x = a + b;
    V(sync);  // 通知 P2
}

// P2 进程
void P2() {
    P(sync);  // 等待 P1 完成
    y = x * c;
}

分析：

• 若 P2 先执行，P(sync) 会阻塞，因为 sync = 0
• 若 P1 先执行，V(sync) 使 sync = 1，P2 可以通过

典型考题：有三个进程 P1、P2、P3，执行顺序为 P1 → P2 → P3

semaphore s1 = 0, s2 = 0;

void P1() {
    执行任务;
    V(s1);
}

void P2() {
    P(s1);
    执行任务;
    V(s2);
}

void P3() {
    P(s2);
    执行任务;
}

5.3 综合例题

题目：司机-售票员问题

• 售票员关门后，司机才能启动汽车
• 司机停车后，售票员才能开门

semaphore s1 = 0;  // 司机等待售票员关门
semaphore s2 = 0;  // 售票员等待司机停车

// 司机进程
void driver() {
    while(true) {
        P(s1);       // 等待关门
        启动汽车;
        正常行驶;
        到站停车;
        V(s2);       // 通知售票员
    }
}

// 售票员进程
void conductor() {
    while(true) {
        关门;
        V(s1);       // 通知司机
        售票;
        P(s2);       // 等待停车
        开门;
    }
}

分析：

• 售票员先关门，V(s1) 通知司机
• 司机 P(s1) 通过，启动汽车
• 到站后司机停车，V(s2) 通知售票员
• 售票员 P(s2) 通过，开门

6) 高频陷阱

• P/V 顺序写反：先 P 同步量再 P mutex（一般先拿资格，再进临界区）
• 忘记 V：一旦漏 V 基本就是”人为制造死锁”
• 读写者问题：read_count 必须用 mutex 保护
• 哲学家问题：必须破坏死锁四条件之一