并发编程：使用信号量实现三线程同步的最优方案咨询

前置约束说明 #

三个进程内部语句天然按顺序执行（如p1一定在p2前，无需额外同步），跨进程必须满足的约束如下：

• p1执行完成后，q2才可启动
• q1执行完成后，r2才可启动
• r1执行完成后，p2才可启动
• p2、q2全部执行完成后，r3才可启动

注：题目未对p3、q3的执行顺序做任何限制，只要p2、q2执行完成即可立刻启动，无需等待其他进程的语句。

原有两版方案的问题 #

• 第一版4信号量方案逻辑本身是正确的，无死锁、无效率问题，但存在信号量命名歧义问题：比如pCompleted实际标记的是p1完成，而非整个P进程完成，容易误导开发者误以为存在进程级的等待冗余。信号量的signal()操作是纯原子计数操作，不会阻塞调用方，因此p2执行完发信号后会立刻执行p3，不存在额外等待开销。
• 第二版3信号量方案存在致命逻辑错误：复用信号量传递不同语义的事件，会出现多等待方抢信号的问题。比如pCompleted第一次发信号是通知q2，第二次发信号是通知r3，r3可能提前消费掉给q2的信号，导致q2永久阻塞，触发死锁。

最优无死锁实现（信号量方案） #

该方案仅用4个初始值为0的信号量，每个信号量语义唯一，无多消费方冲突，所有等待都是约束要求的必须等待，无任何冗余阻塞，可达到理论最高并发度。

信号量定义 #

# 所有信号量初始值为0，语义唯一，仅对应一类事件通知
sem_p1_done = Semaphore(0)  # 仅用于通知q2：p1已执行完成
sem_q1_done = Semaphore(0)  # 仅用于通知r2：q1已执行完成
sem_r1_done = Semaphore(0)  # 仅用于通知p2：r1已执行完成
sem_r3_ready = Semaphore(0) # 仅用于r3等待p2、q2双完成事件，计数到2即放行

各进程执行逻辑 #

P进程

p1()
sem_p1_done.signal() # 通知等待p1完成的进程（仅q2）
sem_r1_done.wait()   # 等待r1完成，满足p2的前置约束
p2()
sem_r3_ready.signal() # 通知r3：p2已完成
p3() # p3无跨进程约束，p2执行完直接运行，无需等待

Q进程

q1()
sem_q1_done.signal() # 通知等待q1完成的进程（仅r2）
sem_p1_done.wait()   # 等待p1完成，满足q2的前置约束
q2()
sem_r3_ready.signal() # 通知r3：q2已完成
q3() # q3无跨进程约束，q2执行完直接运行，无需等待

R进程

r1()
sem_r1_done.signal() # 通知等待r1完成的进程（仅p2）
sem_q1_done.wait()   # 等待q1完成，满足r2的前置约束
r2()
# 等待p2、q2两个完成信号
sem_r3_ready.wait()
sem_r3_ready.wait()
r3()

方案正确性说明 #

• 无死锁：所有wait()操作均在发出自身负责的通知信号后才执行，不存在循环等待的可能；每个信号量只有一个等待方，不会出现信号丢失或错拿。
• 最高效率：所有无前置约束的语句均可立刻并发执行，不存在任何非必要的阻塞，p3、q3在p2、q2完成后即可立刻运行，和r2、r3的执行完全并行。

内容的提问来源于stack exchange，提问作者Kotaka Danski