题目

有 A、B 两人通过信箱进行辩论：

• 每个人都从自己的信箱中取得对方的问题，将答案和向对方提出的新问题组成一个邮件放入对方的信箱中
• 假设 A 的信箱最多放 M 个邮件，B 的信箱最多放 N 个邮件
• 初始时 A 的信箱中有 x 个邮件（0 < x < M），B 的信箱中有 y 个邮件（0 < y < N）
• 辩论者每取出一个邮件，邮件数减 1
• A、B 两人的操作过程描述如下：

A {
    while (true) {
        从 A 的信箱中取出一个邮件;
        回答问题并提出一个新问题;
        将新邮件放入 B 的信箱;
    }
}

B {
    while (true) {
        从 B 的信箱中取出一个邮件;
        回答问题并提出一个新问题;
        将新邮件放入 A 的信箱;
    }
}

约束：信箱不为空时，辩论者才能从信箱中取邮件，否则等待；信箱不满时，辩论者才能将新邮件放入信箱，否则等待。

请添加必要的信号量和 P、V（或 wait、signal）操作，以实现上述过程的同步。要求写出完整的过程，并说明信号量的含义和初值。

解析

关系拆解

每个信箱本质上是一个容量受限的缓冲区——典型的"生产者消费者"模型，但本题特殊在：

• A 是 B 信箱的生产者，又是 A 信箱的消费者
• B 是 A 信箱的生产者，又是 B 信箱的消费者

每个信箱独立维护"满 / 空 / 互斥"三个信号量：

信号量	初值	含义
A_full	x	A 信箱中已有的邮件数（初始 = x）
A_empty	M − x	A 信箱中还可以放的邮件数
A_mutex	1	A 信箱互斥锁
B_full	y	B 信箱中已有邮件数
B_empty	N − y	B 信箱中还可以放的邮件数
B_mutex	1	B 信箱互斥锁

→ 共 6 个信号量。每个信箱 3 个、两个信箱共 6 个。

信号量与代码

semaphore A_full  = x;       // A 信箱中已有邮件数
semaphore A_empty = M - x;   // A 信箱中可放空位
semaphore B_full  = y;       // B 信箱中已有邮件数
semaphore B_empty = N - y;   // B 信箱中可放空位
semaphore A_mutex = 1;       // A 信箱互斥
semaphore B_mutex = 1;       // B 信箱互斥

A() {
    while (true) {
        // 从 A 信箱取邮件
        P(A_full);            // 等 A 信箱有邮件
        P(A_mutex);           // 占用 A 信箱
        从 A 信箱中取出一个邮件;
        V(A_mutex);           // 让出 A 信箱
        V(A_empty);           // A 信箱腾出 1 格

        回答问题并提出新问题;  // 不占信箱，无需互斥

        // 把新邮件放入 B 信箱
        P(B_empty);           // 等 B 信箱有空位
        P(B_mutex);           // 占用 B 信箱
        将新邮件放入 B 信箱;
        V(B_mutex);           // 让出 B 信箱
        V(B_full);            // B 信箱多 1 件
    }
}

B() {
    while (true) {
        // 从 B 信箱取邮件
        P(B_full);
        P(B_mutex);
        从 B 信箱中取出一个邮件;
        V(B_mutex);
        V(B_empty);

        回答问题并提出新问题;

        // 把新邮件放入 A 信箱
        P(A_empty);
        P(A_mutex);
        将新邮件放入 A 信箱;
        V(A_mutex);
        V(A_full);
    }
}

信号量含义说明（答题必写）

信号量	初值	含义
A_full	x	A 信箱中已有的邮件数
A_empty	M - x	A 信箱中剩余可放空位
A_mutex	1	A 信箱单次操作互斥锁
B_full	y	B 信箱中已有的邮件数
B_empty	N - y	B 信箱中剩余可放空位
B_mutex	1	B 信箱单次操作互斥锁

易错点

编者注（核心设计点）：

1. 初值 x、y、M-x、N-y 的来源：题面明示初始邮件数 = x（在 A 信箱）、y（在 B 信箱）。所以：

   • 已有邮件数信号量初值就是当前已有数量（x / y）
   • 空位信号量初值就是容量减去已有（M - x / N - y）
   • 互斥信号量永远初值 1

   不要全部设为 0 或全部设 1——那是 0 ↔ 0 的初始状态，与题面不符。

2. 不会死锁——本题虽然每个 P 都"等"，但不存在循环等待：

   • A 先 P(A_full) 取 → V(A_empty) → 中间空隙 → P(B_empty) 放
   • B 先 P(B_full) 取 → V(B_empty) → 中间空隙 → P(A_empty) 放

   A 等 A_full 时不持有任何锁；A 在持有 B_mutex 时已经过了 P(B_empty) → 不会因 B_empty 不够阻塞。死锁的"持有并等待"条件不成立。

3. P(full) 和 P(mutex) 的顺序——必须 full 在前、mutex 在后（与 2009-45 同理）。否则可能在持有 mutex 时阻塞，导致死锁。

4. "回答问题"放在两个临界区之间——这是为了最大化并发度：A 在思考问题时，B 完全可以独立操作 A 信箱（V(A_empty) 已经释放过空位通知）。把"思考"塞在临界区里会无故拉长持锁时间。

5. A_mutex 和 B_mutex 必须独立——不能共用一个 mutex。共用会让"A 取 A 信箱"和"B 取 B 信箱"互斥，但这两个操作完全无关，无故串行化降低并发。互斥粒度要恰到好处——细到每个独立资源一把锁。