操作系统代码改错题专项练习（10题）

所有题目均基于第8章（并发控制与同步机制）和第9章（进程间通信）的核心知识点。
每题包含：问题描述 → 代码 → 题目要求 → 完整答案（错误分析 + 修正代码）。

---

第1题：生产者-消费者问题（有界缓冲区）

问题描述：
系统中有2个生产者线程和2个消费者线程，共享一个大小为 N=10 的有界缓冲区。同步规则如下：

1. 缓冲区满时生产者必须等待
2. 缓冲区空时消费者必须等待
3. 多个生产者之间互斥访问缓冲区
4. 多个消费者之间互斥访问缓冲区

已给出的程序代码：

#include <semaphore.h>
#include <pthread.h>

#define N 10

sem_t mutex = 1;      // 互斥访问缓冲区
sem_t empty = N;      // 缓冲区空位数
sem_t full = 0;       // 缓冲区已填数
int buffer[N];
int in = 0, out = 0;

void producer(void) {
    while (1) {
        // 生产数据
        int item = produce_item();

        acquire(&empty);     // 等待空位
        acquire(&mutex);     // 进入临界区

        buffer[in] = item;   // 放入产品
        in = (in + 1) % N;

        release(&full);      // 先释放full
        release(&mutex);     // 后释放mutex —— 错误！
    }
}

void consumer(void) {
    while (1) {
        acquire(&mutex);     // 先获取互斥锁 —— 错误！
        acquire(&full);      // 等待产品

        int item = buffer[out];
        out = (out + 1) % N;

        release(&mutex);
        release(&empty);

        // 消费数据
        consume_item(item);
    }
}

全局信号量操作接口：

sem_t sem;
sem_init(&sem, 0, init);  // 初始化信号量，init 为初始值
acquire(&sem);            // P 操作（等待）
release(&sem);            // V 操作（释放）

题目要求：
（1）代码改错（4 分）：上述代码中存在多处错误。请找出至少 2 处错误，按以下格式作答：

序号	错误位置	错误描述	可能导致的后果	修正方法
1
2

（2）信号量分类（2 分）：请指出 mutex、empty、full 三个信号量各属于计数信号量还是二值信号量。

（3）死锁场景分析（4 分）：假设缓冲区此时为空（full=0），消费者先执行。请逐步描述 consumer() 中的死锁过程。如果交换 consumer() 中前两条 acquire 语句的顺序，能否解决死锁？

---

完整答案：

（1）代码改错

错误1：producer() 中 release(&full) 和 release(&mutex) 的释放顺序不合理

• 错误位置：producer() 函数末尾
• 错误描述：release(&full) 和 release(&mutex) 顺序颠倒——先释放 full 再释放 mutex。虽然这不会导致死锁，但在多生产者场景下可能导致逻辑不准确：full 增加后消费者被唤醒，但 mutex 尚未释放，消费者立刻又阻塞在 mutex 上，增加了不必要的上下文切换。
• 可能导致的后果：效率降低、不必要的上下文切换。
• 修正方法：交换两条语句的顺序，先 release(&mutex) 再 release(&full)。

错误2：consumer() 中 acquire(&mutex) 和 acquire(&full) 的顺序错误（致命错误）

• 错误位置：consumer() 函数开头两条 acquire 语句
• 错误描述：消费者先获取 mutex 再等待 full，而生产者需要 mutex 才能放入产品并增加 full。如果缓冲区为空，消费者先拿到 mutex 然后阻塞在 acquire(&full) 上；生产者需要 acquire(&mutex) 但被消费者占着 → 死锁。
• 可能导致的后果：系统死锁，所有生产者和消费者永远阻塞。
• 修正方法：交换顺序——先 acquire(&full) 再 acquire(&mutex)。

修正后的正确代码：

void producer(void) {
    while (1) {
        int item = produce_item();

        acquire(&empty);     // 等待空位
        acquire(&mutex);     // 进入临界区

        buffer[in] = item;
        in = (in + 1) % N;

        release(&mutex);     // 先释放 mutex（修正）
        release(&full);      // 再释放 full（修正）
    }
}

void consumer(void) {
    while (1) {
        acquire(&full);      // 先等待产品（修正）
        acquire(&mutex);     // 再获取互斥锁（修正）

        int item = buffer[out];
        out = (out + 1) % N;

        release(&mutex);
        release(&empty);

        consume_item(item);
    }
}

（2）信号量分类

信号量	类型	初始值	说明
mutex	二值信号量	1	只取值 0 或 1，用于互斥访问缓冲区
empty	计数信号量	N=10	可取 0~N，追踪缓冲区空位数
full	计数信号量	0	可取 0~N，追踪缓冲区已填产品数

（3）死锁场景分析

初始状态：缓冲区空，full=0，mutex=1。

步骤	执行者	操作	结果
1	consumer	acquire(&mutex)	mutex=0，consumer 进入临界区
2	consumer	acquire(&full)	full=0 → consumer 阻塞，等待 full>0（但 mutex 未释放！）
3	producer	acquire(&empty)	empty=10 → 成功，empty=9
4	producer	acquire(&mutex)	mutex=0 → producer 阻塞，等待 consumer 释放 mutex

结果：consumer 等 producer 增加 full，producer 等 consumer 释放 mutex → 死锁。

交换顺序能否解决：能。若 consumer 先 acquire(&full)，缓冲区为空时 consumer 阻塞在 full 上（此时未占 mutex），producer 可以正常获得 mutex、放入产品、release(&full) 唤醒 consumer。

---

第2题：哲学家就餐问题（死锁风险）

问题描述：
5 位哲学家围坐在圆桌旁，中间放着一碗面条。每位哲学家左右各有一根筷子（共 5 根）。哲学家要么思考、要么就餐。就餐时需要同时拿到左右两根筷子。已给出的代码如下：

#include <semaphore.h>
#include <pthread.h>

#define N 5

sem_t chopstick[N];   // 每根筷子对应一个信号量

void init(void) {
    for (int i = 0; i < N; i++) {
        sem_init(&chopstick[i], 0, 1);
    }
}

void philosopher(int i) {
    while (1) {
        think();                          // 思考

        acquire(&chopstick[i]);           // 拿左边筷子
        acquire(&chopstick[(i + 1) % N]); // 拿右边筷子

        eat();                            // 就餐

        release(&chopstick[i]);           // 放左边筷子
        release(&chopstick[(i + 1) % N]); // 放右边筷子
    }
}

题目要求：
（1）代码改错（6 分）：找出上述代码中的潜在问题（至少 2 处），按格式作答：

序号	错误位置	错误描述	可能导致的后果	修正方法
1
2

（2）死锁分析（2 分）：描述上述代码产生死锁的具体过程（以哲学家 0~4 同时拿起左手边的筷子为例）。

（3）方案设计（2 分）：如果要求打破死锁但不引入额外的条件变量或管程，仅修改信号量的使用方式，请提出至少一种方案并简要说明。

---

完整答案：

（1）代码改错

错误1：对称的筷子获取顺序导致死锁风险

• 错误位置：philosopher() 中两根筷子的获取方式
• 错误描述：所有哲学家采用相同的获取顺序——先左后右。若 5 位哲学家同时拿起左手边筷子（chopstick[i]），每个人都持有一根并等待右边的那根。但每根筷子都被邻座哲学家当作"左手筷"占着 → 形成循环等待。
• 可能导致的后果：系统死锁，所有哲学家永远饥饿。
• 修正方法：打破对称性。可让最后一位哲学家（编号 N-1）采用相反的获取顺序——先右后左（即先拿 chopstick[0] 再拿 chopstick[N-1]）。这样打破循环等待环路。

错误2：sem_init 和线程函数中缺少错误处理/返回值检查

• 错误位置：init() 中 sem_init()
• 错误描述：sem_init 可能失败（返回 -1），但代码未检查返回值。
• 可能导致的后果：信号量初始化失败时程序仍继续运行，导致未定义行为。
• 修正方法：检查 sem_init 的返回值，失败时打印错误并退出。

（2）死锁过程

初始状态：5 根筷子信号量均为 1（可用）。

步骤	哲学家	操作	状态
1	P0	acquire(chopstick[0])	chopstick[0]=0，P0 持有筷 0
2	P1	acquire(chopstick[1])	chopstick[1]=0，P1 持有筷 1
3	P2	acquire(chopstick[2])	chopstick[2]=0，P2 持有筷 2
4	P3	acquire(chopstick[3])	chopstick[3]=0，P3 持有筷 3
5	P4	acquire(chopstick[4])	chopstick[4]=0，P4 持有筷 4
6	P0	acquire(chopstick[1])	chopstick[1]=0 → P0 阻塞（等 P1 释放）
7	P1	acquire(chopstick[2])	chopstick[2]=0 → P1 阻塞（等 P2 释放）
8	P2	acquire(chopstick[3])	chopstick[3]=0 → P2 阻塞（等 P3 释放）
9	P3	acquire(chopstick[4])	chopstick[4]=0 → P3 阻塞（等 P4 释放）
10	P4	acquire(chopstick[0])	chopstick[0]=0 → P4 阻塞（等 P0 释放）

最终形成环路：P0 → P1 → P2 → P3 → P4 → P0 → 死锁。

满足死锁的四条件：

1. 互斥：筷子只能被一人持有
2. 持有并等待：每人持有一根筷子，等待另一根
3. 不可剥夺：不能抢走别人手里的筷子
4. 循环等待：P0→P1→P2→P3→P4→P0 形成闭环

（3）打破死锁的方案

方案一：打破对称（修改获取顺序）

让编号最大的哲学家（P4）以相反顺序获取筷子：

void philosopher(int i) {
    while (1) {
        think();

        if (i == N - 1) {
            // 最后一位哲学家：先右后左
            acquire(&chopstick[(i + 1) % N]); // 先拿右边
            acquire(&chopstick[i]);           // 再拿左边
        } else {
            acquire(&chopstick[i]);           // 先拿左边
            acquire(&chopstick[(i + 1) % N]); // 再拿右边
        }

        eat();

        release(&chopstick[i]);
        release(&chopstick[(i + 1) % N]);
    }
}

方案二：限制同时就餐人数

增加一个计数信号量，限制最多 N-1=4 人同时尝试拿筷子：

sem_t limit = N - 1; // 最多 N-1 人同时尝试就餐

void philosopher(int i) {
    while (1) {
        think();
        acquire(&limit);                    // 先获准入座
        acquire(&chopstick[i]);
        acquire(&chopstick[(i + 1) % N]);
        eat();
        release(&chopstick[i]);
        release(&chopstick[(i + 1) % N]);
        release(&limit);
    }
}

---

第3题：信号量用作互斥锁时的初始化错误

问题描述：
某系统使用信号量实现互斥锁功能，保护共享变量 shared_counter。代码如下：

#include <semaphore.h>
#include <pthread.h>

sem_t lock = 0;           // 互斥锁信号量
int shared_counter = 0;

void thread_func(void) {
    for (int i = 0; i < 1000; i++) {
        acquire(&lock);          // P 操作（期望：进入临界区）
        shared_counter++;        // 临界区
        release(&lock);          // V 操作（期望：离开临界区）
    }
}

题目要求：
（1）错误分析（3 分）：上述代码存在什么错误？会导致什么后果？请详细说明。

（2）修正方法（2 分）：如何修正？写出一条关键修改语句。

（3）信号量原理（3 分）：请解释 acquire（P 操作）和 release（V 操作）对信号量计数值的原子操作过程。二值信号量如何保证不会超过 1？

（4）互斥锁正确性标准（2 分）：此代码修正后，shared_counter 在 2 个线程各执行 1000 次循环后，最终值应该是多少？若最终值不为期望值，可能的原因是什么（假设锁已修正）？

---

完整答案：

（1）错误分析

• 错误位置：sem_t lock = 0;
• 错误描述：互斥锁信号量应初始化为 1（表示锁可用），但此处初始化为 0（表示锁已被占用/无资源可用）。
• 可能导致的后果：第一个调用 acquire(&lock) 的线程发现 lock=0，立即阻塞。但没有任何线程持有锁来执行 release()，所有线程永远阻塞在 acquire 上 → 死锁（无人能进入临界区，也无人释放锁）。

（2）修正方法

sem_t lock = 1;   // 或其他方式确保 sem_init(&lock, 0, 1)

或者使用正确的初始化方式：

sem_t lock;
sem_init(&lock, 0, 1);  // pshared=0（线程间共享），初始值=1

（3）信号量原理

P 操作（acquire）：

原子地执行：
  while (sem.value <= 0) {
      将当前线程加入该信号量的等待队列，阻塞;
  }
  sem.value--;

V 操作（release）：

原子地执行：
  sem.value++;
  if (sem.value > 0 且等待队列非空) {
      从等待队列头部取出一个线程，唤醒它;
  }

二值信号量的 value 只取 0 或 1：value=1 表示锁可用，value=0 表示锁被占用。因为初始值=1，每个 acquire 减 1、每个 release 加 1，若有线程在等则 release 先唤醒等待者而不增加 value（等待者被唤醒后拿着锁走，value 保持为 0）。这保证了 value 不会超过 1。

（4）互斥锁正确性

修正后 shared_counter 的最终值应为 2000（2 × 1000）。

若最终值不为 2000，可能的原因：

• 编译器优化导致对 shared_counter 的读写被重排（需使用 volatile 或原子操作）
• 锁的实现有 bug（如果使用软件实现而非硬件原子指令）
• 但若信号量本身实现正确且使用硬件原子指令保证，则最终值必然为 2000

---

第4题：条件变量使用中的 Mesa 语义陷阱

问题描述：
两个线程使用互斥锁和条件变量实现"等待某个条件满足后继续执行"的模式。代码如下：

#include <pthread.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int data_ready = 0;   // 条件标志：0 = 数据未就绪，1 = 数据已就绪

void consumer(void) {
    pthread_mutex_lock(&mutex);

    if (data_ready == 0) {            // 错误！使用 if 而非 while
        pthread_cond_wait(&cond, &mutex);
    }

    // 消费数据
    process_data();
    data_ready = 0;

    pthread_mutex_unlock(&mutex);
}

void producer(void) {
    pthread_mutex_lock(&mutex);

    produce_data();
    data_ready = 1;
    pthread_cond_signal(&cond);       // 唤醒一个等待者

    pthread_mutex_unlock(&mutex);
}

题目要求：
（1）错误分析（4 分）：上述代码的主要错误是什么（提示：与条件变量的语义有关）？在什么场景下该错误会导致问题？

（2）语义比较（3 分）：请比较 Mesa 语义和 Hoare 语义的区别。上述代码在 Hoare 语义下是否有问题？

（3）修正方法（2 分）：写出修正后的 consumer() 关键代码段。

（4）惊群效应（1 分）：如果 producer 中使用 pthread_cond_broadcast()（唤醒所有等待者）替代 pthread_cond_signal()（唤醒一个），可能产生什么问题？

---

完整答案：

（1）错误分析

• 错误位置：consumer() 中 if (data_ready == 0) 应改为 while (data_ready == 0)。
• 错误描述：pthread_cond_wait 使用的是 Mesa 语义：被唤醒的线程仅进入就绪状态，不一定立即获得锁和 CPU；在等待获得锁的过程中，其他线程可能先获得锁并改变了条件（例如另一个 consumer 或第三条线程将 data_ready 重新设为 0）。如果用 if 只检查一次，被虚假唤醒或被其他线程抢走数据后，不会重新检查条件，导致在 data_ready 实际为 0 的情况下错误地继续消费。
• 问题场景：若系统有 2 个 consumer 线程，producer 生产一份数据后用 signal 唤醒 C1。但 C1 在争锁时被 C2 抢到锁（C2 是正常进入而非被唤醒），C2 发现 data_ready=1 消费了数据并设 data_ready=0。然后 C1 获得锁，从 pthread_cond_wait 返回——此时 data_ready 已经变成 0，但 if 不会重新检查，C1 会在数据不存在的情况下调用 process_data()，导致错误。

（2）Mesa 语义 vs Hoare 语义

特性	Mesa 语义	Hoare 语义
被唤醒线程	进入就绪队列，需竞争锁	立即获得锁并运行
条件检查	醒来后条件可能已变，必须用 while 重新检查	条件 100% 成立，可以用 if
实现复杂度	较简单	更复杂（需要额外的调度保证）
实际系统	Linux pthread、Java monitor	理论模型，实际系统较少使用

在 Hoare 语义下：被唤醒的线程立即得到锁和 CPU，且条件不可能被其他线程改变，使用 if 就没有问题。但实际系统（Linux pthread、Java）都采用 Mesa 语义，所以必须用 while。

（3）修正代码

void consumer(void) {
    pthread_mutex_lock(&mutex);

    while (data_ready == 0) {         // 修正：while 而非 if
        pthread_cond_wait(&cond, &mutex);
    }

    process_data();
    data_ready = 0;

    pthread_mutex_unlock(&mutex);
}

（4）惊群效应

若 producer 使用 pthread_cond_broadcast() 唤醒所有等待者：

• 多个 consumer 被同时唤醒，争抢同一个互斥锁
• 只有一个 consumer 获得锁并消费数据（data_ready→0）
• 其余 consumer 获得锁后发现条件已不满足，重新进入 wait
• 大量无意义的上下文切换和锁竞争 → 惊群效应（Thundering Herd）

---

第5题：锁的获取顺序导致死锁

问题描述：
某银行转账系统需要同时操作两个账户（转出方和转入方），使用两把互斥锁保护两个账户。代码如下：

#include <pthread.h>

pthread_mutex_t lock_A = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_B = PTHREAD_MUTEX_INITIALIZER;

int account_A = 1000;
int account_B = 1000;

// 线程1：从 A 转 100 到 B
void transfer_A_to_B(void) {
    pthread_mutex_lock(&lock_A);      // 锁 A
    pthread_mutex_lock(&lock_B);      // 锁 B —— 保持 A 的同时请求 B

    account_A -= 100;
    account_B += 100;

    pthread_mutex_unlock(&lock_B);
    pthread_mutex_unlock(&lock_A);
}

// 线程2：从 B 转 50 到 A
void transfer_B_to_A(void) {
    pthread_mutex_lock(&lock_B);      // 锁 B
    pthread_mutex_lock(&lock_A);      // 锁 A —— 保持 B 的同时请求 A

    account_B -= 50;
    account_A += 50;

    pthread_mutex_unlock(&lock_A);
    pthread_mutex_unlock(&lock_B);
}

题目要求：
（1）死锁分析（4 分）：描述上述代码的死锁过程。这个场景满足死锁的哪些必要条件？

（2）修正方案（4 分）：给出两种不同的修正方案，并比较其优缺点。

（3）活锁辨析（2 分）：如果将代码改为：若无法一次获取两把锁则释放已获取的锁并重试，能否完全避免问题？这样做会产生什么新问题（提示：活锁）？

---

完整答案：

（1）死锁分析

死锁过程：

时刻	线程1 (A→B)	线程2 (B→A)
t1	lock(&lock_A) 成功，lock_A 被占
t2		lock(&lock_B) 成功，lock_B 被占
t3	lock(&lock_B) → 阻塞（等线程2释放）
t4		lock(&lock_A) → 阻塞（等线程1释放）

线程1 持有 lock_A、等待 lock_B；线程2 持有 lock_B、等待 lock_A → 死锁。

满足死锁的四个必要条件：

1. 互斥：每把锁同时只能被一个线程持有 ✓
2. 持有并等待：各自持有一把锁的同时等待另一把 ✓
3. 不可剥夺：不能强制抢走对方的锁 ✓
4. 循环等待：线程1 → lock_B → 线程2 → lock_A → 线程1，形成环路 ✓

（2）修正方案

方案一：统一锁的获取顺序（推荐）

给每把锁分配一个全局唯一编号（如按地址排序），所有线程按相同顺序获取：

// 先获取编号小的锁，再获取编号大的锁
void transfer(pthread_mutex_t *from, pthread_mutex_t *to, 
              int *from_acct, int *to_acct, int amount) {
    pthread_mutex_t *first, *second;
    if (from < to) {          // 按锁地址排序
        first = from; second = to;
    } else {
        first = to; second = from;
    }

    pthread_mutex_lock(first);
    pthread_mutex_lock(second);

    *from_acct -= amount;
    *to_acct += amount;

    pthread_mutex_unlock(second);
    pthread_mutex_unlock(first);
}

优点：简单高效，无额外开销。缺点：需要全局规定获取顺序，代码中所有用到多锁的地方都要遵守。

方案二：trylock + 回退

尝试获取锁，若失败则释放已获得的锁并重试：

void transfer_A_to_B(void) {
    while (1) {
        pthread_mutex_lock(&lock_A);
        if (pthread_mutex_trylock(&lock_B) == 0) {
            // 两把锁都拿到
            account_A -= 100;
            account_B += 100;
            pthread_mutex_unlock(&lock_B);
            pthread_mutex_unlock(&lock_A);
            break;
        }
        pthread_mutex_unlock(&lock_A);  // 没拿到第二把，释放第一把
        usleep(rand() % 100);            // 随机等待后重试
    }
}

优点：无需全局排序。缺点：有活锁风险，性能较差（需要反复重试）。

（3）活锁辨析

能否完全避免死锁：是——trylock + 回退可以破坏死锁的"持有并等待"条件（未同时持有两把锁），从而避免死锁。

活锁问题：如果两个线程反复同时尝试、同时失败、同时释放、同时重试，双方永远无法推进——这就是活锁。虽然线程未被阻塞（仍在执行），但始终无法完成实际工作。

缓解方法：加入随机退避（random backoff）——每次重试前等待一个随机时间，降低双方同步重试的概率。

---

第6题：自旋锁实现缺少原子操作

问题描述：
某同学尝试用 C 语言实现一个简单的自旋锁，用于多线程环境中的互斥。代码如下：

typedef struct {
    int locked;
} spinlock_t;

void spin_lock(spinlock_t *lock) {
    while (lock->locked == 1) {
        // 忙等待（自旋）
    }
    lock->locked = 1;              // 获得锁
}

void spin_unlock(spinlock_t *lock) {
    lock->locked = 0;              // 释放锁
}

题目要求：
（1）错误分析（4 分）：上述代码在单核和多核环境下各有什么问题？解释为什么这种实现不是线程安全的。

（2）原子指令修正（3 分）：使用 TAS（Test-And-Set） 或 CAS（Compare-And-Swap） 指令重写 spin_lock() 函数。你需要说明所使用的原子指令的语义。

（3）自旋锁 vs 阻塞锁（3 分）：在临界区非常短（< 100 个 CPU 周期）且竞争不激烈的情况下，自旋锁和阻塞锁哪个更合适？为什么？

---

完整答案：

（1）错误分析

在多核环境中的问题：

时刻	CPU0 (线程A)	CPU1 (线程B)
t1	读取 lock->locked，发现 = 0
t2		读取 lock->locked，发现 = 0
t3	设置 lock->locked = 1
t4		设置 lock->locked = 1

两个线程同时读取到 locked=0，然后同时将 locked 设为 1，都认为自己获得了锁 → 互斥失效。

根本原因：while (lock->locked == 1) 读检查 + lock->locked = 1 写设置是两个独立的非原子操作。编译器或 CPU 可能在两者之间插入调度/中断，导致 TOCTOU（Time-Of-Check-Time-Of-Use）竞争条件。

在单核环境下的额外问题：若线程 A 在 while 循环中被抢占，且线程 B 持有锁——线程 A 占着 CPU 空转（while 循环）直到时间片用完，浪费 CPU 资源。

（2）原子指令修正

使用 TAS（Test-And-Set）：

// TAS: 原子地将 *addr 设为 1，返回旧值
// 返回 0 → 之前无人持锁，成功获得
// 返回 1 → 之前有人持锁，需继续等待
int TAS(int *addr);  // 硬件原子指令

void spin_lock(spinlock_t *lock) {
    while (TAS(&lock->locked) == 1) {
        // 自旋等待
    }
}

使用 CAS（Compare-And-Swap）：

// CAS: 若 *addr == expected，则设为 new 并返回 1（成功）；否则返回 0（失败）
int CAS(int *addr, int expected, int new_val);

void spin_lock(spinlock_t *lock) {
    while (CAS(&lock->locked, 0, 1) == 0) {
        // 自旋等待
    }
}

（3）自旋锁 vs 阻塞锁

自旋锁更合适。

原因：

• 短临界区：自旋锁等待的时间很短，被阻塞线程很可能在几次自旋后就能获得锁。避免了阻塞锁的上下文切换开销（保存/恢复寄存器、TLB flush 等，约 1~10μs），这个开销可能远大于临界区本身。
• 低竞争：大部分时候锁空闲，自旋锁几乎可以立即获得，零额外开销。
• 多核友好：自旋线程在一个核心上空转时，持锁线程在另一个核心上执行，不浪费太多时间。

对比：

• 临界区长或竞争激烈 → 阻塞锁更合适（避免 CPU 空转浪费）
• 单核环境 → 阻塞锁更合适（自旋锁在单核上完全无效——自旋线程占着唯一 CPU，持锁线程无法运行释放锁）

---

第7题：读者-写者锁中的写者饥饿

问题描述：
一个读者-写者锁的简单实现如下（读者优先策略）：

#include <semaphore.h>

sem_t rw_mutex = 1;      // 读者-写者互斥锁
sem_t mutex = 1;         // 保护 reader_count
int reader_count = 0;

void reader(void) {
    while (1) {
        acquire(&mutex);
        reader_count++;
        if (reader_count == 1) {
            acquire(&rw_mutex);   // 第一个读者阻止写者
        }
        release(&mutex);

        read_data();               // 读取（可并发）

        acquire(&mutex);
        reader_count--;
        if (reader_count == 0) {
            release(&rw_mutex);   // 最后一个读者允许写者
        }
        release(&mutex);
    }
}

void writer(void) {
    while (1) {
        acquire(&rw_mutex);        // 等待读者全部离开
        write_data();              // 写入（独占）
        release(&rw_mutex);
    }
}

题目要求：
（1）问题分析（4 分）：上述实现可能导致什么问题？描述该问题发生的具体场景。此现象在 IPC 术语中叫什么？

（2）饥饿根因（2 分）：为什么上述代码会导致此问题？从代码逻辑角度分析。

（3）解决方案设计（4 分）：请设计一个"写者优先"的读者-写者锁。只需描述需要增加什么信号量和关键代码逻辑（不要求完整代码）。新增的信号量各起什么作用？

---

完整答案：

（1）问题分析

上述实现可能导致写者饥饿（Writer Starvation）。

具体场景：

• 时刻 t1：R1 到达，reader_count=1，获取 rw_mutex，开始读
• 时刻 t2：W1 到达，尝试获取 rw_mutex，阻塞（等待读完成）
• 时刻 t3：R2 到达，reader_count=2，直接进入读取（因为已有 reader，无需获取 rw_mutex）
• 时刻 t4：R1 离开，reader_count=1（>0），rw_mutex 未释放
• 时刻 t5：R3 到达，reader_count=2，进入读取
• …（只要有读者持续到达且在最后一个读者离开前新读者到达，reader_count 始终 > 0）

结果：只要读者持续到来，写者永远无法获得 rw_mutex。在 IPC 术语中这是**饥饿（Starvation）**问题。

（2）饥饿根因

关键代码逻辑：当 reader_count > 0 时，新到来的读者不需要获取 rw_mutex 即可进入临界区。这导致：

• 写者需要等待 reader_count == 0（所有当前读者+之后读者全部离开）
• 但新读者可以在写者等待期间持续进入，使 reader_count 永不为 0

根因在于：读者优先——读者对 rw_mutex 的获取没有受到写者存在的任何抑制。

（3）写者优先方案

新增信号量：

信号量	作用
write_pending（初始值=1）	写者意向标志。写者在获取 rw_mutex 前先获取 write_pending 并立即释放，目的是阻止新读者进入。读者在获取 mutex 之前必须先获取 write_pending 然后立即释放。当有写者等待时，write_pending 被写者持有，读者阻塞。
write_count	等待中的写者数量。用于最后一个写者释放时清除写优先标志。

关键逻辑：

// 写者
void writer(void) {
    acquire(&wmutex);
    write_count++;
    if (write_count == 1) {
        acquire(&write_pending);  // 第一个等待的写者阻止新读者
    }
    release(&wmutex);

    acquire(&rw_mutex);           // 等待读写互斥
    write_data();
    release(&rw_mutex);

    acquire(&wmutex);
    write_count--;
    if (write_count == 0) {
        release(&write_pending);  // 最后一个写者离开，允许读者
    }
    release(&wmutex);
}

// 读者
void reader(void) {
    acquire(&write_pending);      // 检查是否有写者在等
    release(&write_pending);      // 若有写者，读者在此阻塞

    // ... 其余与读者优先相同
}

工作原理：

• 当有写者等待时，write_pending 被占用，新读者阻塞在 acquire(&write_pending) 上
• 已经在读的读者完成读取后，当 reader_count=0 时写者获得 rw_mutex
• 写者完成后释放 write_pending，允许被阻塞的读者继续

---

第8题：屏障（Barrier）同步实现错误

问题描述：
某并行计算程序需要所有 N=4 个线程在每次迭代结束时同步（都到达屏障后才能继续下一轮）。一个简单的屏障实现如下：

#include <semaphore.h>

#define N 4

sem_t mutex = 1;      // 保护计数器
sem_t barrier = 0;    // 阻塞线程直到全部到达
int count = 0;        // 已到达屏障的线程数

void thread_barrier(void) {
    acquire(&mutex);
    count++;
    if (count == N) {
        count = 0;
        release(&barrier);      // 错误：只释放一次
    }
    release(&mutex);

    acquire(&barrier);          // 等待其他线程
    release(&barrier);          // 错误：所有线程通过后谁重置 barrier？

    // ... 继续下一轮
}

在上面的代码中，sem_t barrier = 0 初始化为 0，意味着所有线程会在 acquire(&barrier) 处阻塞。当第 N 个线程到达时，执行一次 release(&barrier) 唤醒一个被阻塞的线程，然后该线程立即执行 release(&barrier) 唤醒下一个，形成"链式唤醒"。下一轮 count 被重置为 0。

但是上述代码中存在潜在问题。

题目要求：
（1）错误分析（5 分）：上述屏障实现至少有 2 处问题。请分别指出并说明在什么情况下会出错。

（2）可重用性问题（3 分）：上述屏障能否被多轮循环安全地重复使用？如果不能，请详细说明为什么。这类问题在并发编程中有什么专门的名称？

（3）正确实现（2 分）：给出使用信号量的正确屏障实现（可以添加新的信号量）。

---

完整答案：

（1）错误分析

错误1：barrier 信号量被错误地使用——所有线程在 acquire 后立即 release

• 错误位置：release(&barrier) 紧跟在 acquire(&barrier) 后面
• 问题：acquire 和 release 之间没有临界区保护，多个线程可能同时执行到此处。但实际上这个问题在"链式唤醒"模式下还算可工作——真正的问题见错误 2。

错误2（致命）：count 重置与第 N 个线程唤醒之间存在竞争

• 错误位置：if (count == N) { count = 0; release(&barrier); }
• 问题：若第 N 个线程（设为 T4）执行 release(&barrier) 唤醒 T1，然后 T4 释放 mutex。但 T1 被唤醒后立即执行 release(&barrier)（在 acquire(&barrier) 之后），这会唤醒 T2、T2 唤醒 T3……看起来能工作。
• 但问题在于：如果 T1 被唤醒后（从 acquire 返回），在它执行下一行的 release(&barrier) 之前，T4（第 N 个线程）已经完成了整个屏障等待并进入了下一轮循环！T4 将 count 从 0 增加到 1，且（如果它是下一轮的第一个线程）可能再次执行到 acquire(&barrier)。而这时上一轮的"链式唤醒"尚未完成——barrier 的值可能被重置。这叫屏障重用问题（Barrier Reuse Problem）。

（2）可重用性问题

不能安全重复使用。

原因：

• 第 N 个线程（T4）在 T1 被唤醒前就将 count 重置为 0 并释放了 mutex
• T4 可能快速完成本轮工作并进入下一轮，再次执行 count++（使 count=1）
• 同时，上一轮的 T1~T3 可能还在执行 release(&barrier) 的"链式唤醒"
• 若 T4 在下一轮中又执行了 acquire(&barrier)，而上轮的 release 链还在进行——可能导致 T4 被提前唤醒（上一轮多余的 release 唤醒了下一轮的线程）

这个问题在并发编程中称为**屏障重用问题（Barrier Reuse Problem）**或 "闪电式重用"问题（Lightning Reuse）。

（3）正确实现

使用两阶段屏障（sense-reversing barrier）或计数+回合标记方法：

sem_t mutex = 1;
sem_t barriers[2] = {0, 0};   // 两套屏障，交替使用
int count = 0;
int phase = 0;                 // 当前回合（0或1）

void thread_barrier(void) {
    int my_phase = phase;      // 记录我参与的回合

    acquire(&mutex);
    count++;
    if (count == N) {
        count = 0;
        // 唤醒所有等待上一轮 barrier 的线程
        for (int i = 0; i < N - 1; i++) {
            release(&barriers[my_phase]);
        }
        phase = 1 - phase;     // 切换到下一回合的屏障
    }
    release(&mutex);

    acquire(&barriers[my_phase]);  // 等待当前回合的屏障

    // 到达此处时所有 N 个线程已同步
}

工作原理：

• 使用两套屏障（phase=0 和 phase=1）
• 每个线程记录自己属于哪个回合
• 第 N 个线程一次释放 N-1 个信号量（而非链式释放），确保所有等待者都被唤醒
• 切换到下一回合（phase = 1 - phase），下一轮使用另一套屏障

---

第9题：共享内存无同步访问

问题描述：
两个进程使用共享内存通信。进程 A 向共享缓冲区写入数据，进程 B 从共享缓冲区读取数据。代码如下：

进程 A（写者）：

// 共享内存结构
struct shared_data {
    int data_ready;     // 0 = 空，1 = 有新数据
    char message[256];
};

struct shared_data *shm;  // 通过 shmat 映射的共享内存

void process_A(void) {
    while (1) {
        // 准备数据
        char msg[256];
        generate_message(msg);

        // 等待 B 读完上一批数据
        while (shm->data_ready == 1) {
            // 忙等待
        }

        // 写入新数据
        strcpy(shm->message, msg);
        shm->data_ready = 1;       // 标记数据就绪
    }
}

进程 B（读者）：

void process_B(void) {
    while (1) {
        // 等待 A 写入新数据
        while (shm->data_ready == 0) {
            // 忙等待
        }

        // 读取数据
        char msg[256];
        strcpy(msg, shm->message);
        shm->data_ready = 0;       // 标记已读完

        process_message(msg);
    }
}

题目要求：
（1）错误分析（4 分）：上述代码有啥问题？在多核 CPU 环境下可能出现什么错误行为？（提示：考虑编译器优化和 CPU 缓存一致性）

（2）内存屏障（3 分）：请解释为什么在 C 语言中 shm->data_ready = 1 这样的赋值语句在多线程/多进程中不能保证正确的内存可见性。volatile 关键字能完全解决这个问题吗？

（3）改进方案（3 分）：如果必须在共享内存上实现同步，你有什么更好的方案？请至少提出两种方法并比较。

---

完整答案：

（1）错误分析

1. 竞态条件：进程 A 检查 data_ready == 1 后、设置 data_ready = 1 前，进程 B 可能刚好读完并置 data_ready = 0，导致 A 写入的数据被 B 漏读或被覆盖。

2. 内存可见性问题（核心）：

   • 编译器优化：编译器可能将 while (shm->data_ready == 1) 优化为只读取一次的循环（将 data_ready 的值缓存在寄存器中），因为编译器不知道这个变量会被另一个进程修改。
   • CPU 缓存一致性：CPU0 上的进程 A 写入 data_ready = 1 可能只写入了 CPU0 的 L1 缓存，CPU1 上的进程 B 读取 data_ready 时可能从自己的 L1 缓存读到旧值（0），导致 B 永远看不到数据已就绪。
   • 指令重排：CPU 可能将 strcpy(shm->message, msg) 和 shm->data_ready = 1 的顺序重排——先标记 data_ready=1，再写入 message。此时 B 看到 data_ready=1 后读取 message，但 message 可能尚未写完。

3. 忙等待浪费 CPU：while 循环持续消耗 CPU 时间。

（2）内存屏障与 volatile

volatile 的局限性：

• C 语言的 volatile 只能：① 阻止编译器优化掉对变量的读写（不将变量缓存在寄存器中）；② 阻止编译器对 volatile 变量之间的访问重排
• volatile 不能：阻止 CPU 的硬件指令重排；保证多核 CPU 的缓存一致性；提供跨进程的内存可见性保证
• 结论：volatile 不能完全解决共享内存多进程同步问题。

需要的内存屏障：

• 写屏障（Write Barrier）：确保 strcpy(shm->message, msg) 在 shm->data_ready = 1 之前对内存生效
• 读屏障（Read Barrier）：确保 shm->data_ready 的读取在 strcpy(msg, shm->message) 之前完成

（3）改进方案

方案一：使用 POSIX 命名信号量（进程间信号量）

sem_t *sem_data_ready, *sem_space_avail;

// 进程 A
void process_A(void) {
    while (1) {
        generate_message(msg);
        acquire(sem_space_avail);     // 等待缓冲区空
        strcpy(shm->message, msg);
        release(sem_data_ready);      // 通知有新数据
    }
}

// 进程 B
void process_B(void) {
    while (1) {
        acquire(sem_data_ready);      // 等待新数据
        strcpy(msg, shm->message);
        release(sem_space_avail);     // 通知缓冲区已空
        process_message(msg);
    }
}

优点：内核保证的信号量原子性和可见性，无需忙等待。缺点：需内核介入，有系统调用开销。

方案二：使用 C11 原子操作（_Atomic + memory_order）

#include <stdatomic.h>

struct shared_data {
    atomic_int data_ready;    // 原子标志
    char message[256];
};

// 进程 A
void process_A(void) {
    generate_message(msg);
    strcpy(shm->message, msg);
    atomic_store_explicit(&shm->data_ready, 1, memory_order_release);
    // memory_order_release 保证：之前的所有写操作（message）对后续的 acquire 操作可见
}

// 进程 B
void process_B(void) {
    while (atomic_load_explicit(&shm->data_ready, memory_order_acquire) == 0) {
        // 可加 yield 降低 CPU 消耗
    }
    strcpy(msg, shm->message);
    atomic_store_explicit(&shm->data_ready, 0, memory_order_release);
}

优点：无系统调用，高效；memory_order 提供正确的内存屏障语义。缺点：需要 C11 支持，忙等待仍浪费 CPU。

---

第10题：管程（Monitor）条件变量 Signal 位置错误

问题描述：
使用管程实现一个简单的生产者-消费者模型。管程封装了缓冲区操作。简化代码如下：

// 管程伪代码（模拟 pthread 的 mutex + cond 实现管程）
pthread_mutex_t monitor_lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t not_full = PTHREAD_COND_INITIALIZER;   // 缓冲区非满
pthread_cond_t not_empty = PTHREAD_COND_INITIALIZER;  // 缓冲区非空
int buffer[10];
int count = 0;
int in = 0, out = 0;

void monitor_produce(int item) {
    pthread_mutex_lock(&monitor_lock);

    if (count == 10) {                       // 错误：应使用 while
        pthread_cond_wait(&not_full, &monitor_lock);
    }

    buffer[in] = item;
    in = (in + 1) % 10;
    count++;

    pthread_cond_signal(&not_empty);         // 通知非空
    // 错误：此处缺少释放锁！
}

int monitor_consume(void) {
    pthread_mutex_lock(&monitor_lock);

    if (count == 0) {                        // 错误：应使用 while
        pthread_cond_wait(&not_empty, &monitor_lock);
    }

    int item = buffer[out];
    out = (out + 1) % 10;
    count--;

    pthread_cond_signal(&not_full);          // 通知非满
    // 错误：此处缺少释放锁！
    return item;
}

题目要求：
（1）错误分析（5 分）：找出上述代码中至少 3 处错误，分析后果并给出修正。

（2）Signal 位置问题（3 分）：在 Mesa 语义的管程中，pthread_cond_signal 应该在 pthread_mutex_unlock 之前还是之后调用？两种放置方式各有什么优缺点？

（3）Hoare vs Mesa 综合比较（2 分）：如果上述代码运行在 Hoare 语义的管程中，哪些错误仍然存在？哪些不再算是错误？

---

完整答案：

（1）错误分析

错误1：使用 if 而非 while 检查条件

• 错误位置：if (count == 10) 和 if (count == 0)
• 后果：Mesa 语义下，被唤醒的线程可能在被调度运行前条件已被其他线程改变（虚假唤醒或竞争），导致在条件不满足的情况下错误地执行后续操作（如缓冲区满时仍写入）。
• 修正：将 if 改为 while。

错误2：函数末尾缺少 pthread_mutex_unlock

• 错误位置：monitor_produce() 和 monitor_consume() 函数的 return 之前
• 后果：锁永不释放，其他线程永远无法进入管程 → 死锁。
• 修正：在 return 之前添加 pthread_mutex_unlock(&monitor_lock);。

错误3：monitor_produce() 在 signal 之后才 unlock（若添加了 unlock），signal 的唤醒线程可能立即被阻塞

• 错误位置：pthread_cond_signal(&not_empty) 在 pthread_mutex_unlock 之前（若 unlock 加在最后）
• 后果：signal 唤醒等待者，等待者被唤醒后需要获取 monitor_lock，但锁仍被生产者持有 → 等待者立即阻塞。H2O（“Hurry-up and wait”），不必要的上下文切换。
• 修正方案（见(2)）。

（2）Signal 位置分析

Signal 在 unlock 之前（当前代码的逻辑）：

• 唤醒的线程立即尝试获取锁 → 因锁还在 signaler 手中而阻塞
• 额外的上下文切换开销 → Hurry-up-and-wait 问题
• 优点：被唤醒的线程保证看到了 signaler 留下的最新状态

Signal 在 unlock 之后（推荐做法）：

• 先释放锁，再发 signal
• 被唤醒的线程可以直接获取锁（或与其他等锁者竞争）
• 优点：减少一次无效的阻塞/唤醒循环
• 缺点（极小）：signal 后锁已释放，可能有其他线程先于被唤醒者抢到锁并修改条件（但 Mesa 语义本来就需要 while 重新检查，所以无影响）

推荐：在 Mesa 语义中，signal 放在 unlock 之后更高效。

（3）Hoare 语义下的对比

在 Hoare 语义中：

错误项	Hoare 语义下是否仍是错误
if vs while	不再是错误——Hoare 语义保证被唤醒的线程立即获得 CPU 和锁，条件不会在中间被改变
缺少 unlock	仍是致命错误——锁永不释放
signal 在 unlock 前	不再是问题——Hoare 语义下被唤醒的线程立即运行并完成，signaler 不持有锁。但在 Hoare 语义的实际实现中通常 signal 会自动转让锁

结论：Hoare 语义放宽了对条件检查的要求，但缺少 unlock 在任何语义下都是错误。在实际系统（全部采用 Mesa 语义）中，必须使用 while + unlock。

---

答案速查表

题号	核心考点	错误摘要	关键修正
1	生产者-消费者同步	consumer 先 mutex 后 full → 死锁；producer 释放顺序不佳	交换 acquire 顺序，full 先于 mutex
2	哲学家就餐死锁	对称获取筷子 → 循环等待死锁	打破对称（最后一位先右后左）或限制人数
3	信号量初始化	lock 初始化为 0 而非 1 → 无人能进临界区	lock 初始值 = 1
4	条件变量 Mesa 语义	用 if 而非 while → 虚假唤醒时条件不满足仍执行	改为 while 循环检查条件
5	锁顺序死锁	多锁获取顺序不一致 → AB-BA 死锁	统一锁获取顺序或 trylock+回退
6	自旋锁原子性	读写分离 → TOCTOU 竞争	使用 TAS/CAS 原子指令
7	读者-写者饥饿	读者优先 → 连续到达导致写者饥饿	增加 write_pending 信号量实现写者优先
8	屏障可重用性	链式唤醒 + 快速重用 → 屏障重用问题	两阶段屏障（phase 交替）
9	共享内存可见性	无同步机制 + 缓存一致性问题	POSIX 信号量或 C11 原子操作
10	管程条件变量	缺 unlock、if 非 while、signal 位置不佳	加 unlock、while 检查、signal 后移