《Little Book of Semaphores》中屏障代码工作原理解惑

先贴出你提到的代码：

rendezvous

mutex.wait()
    count = count + 1
mutex.signal()

if count == n: barrier.signal()

barrier.wait()// 我不理解的部分
barrier.signal()

critical point

已知条件：barrier初始值为0，mutex初始值为1，count初始值为0，n是需要同步的线程总数。

核心原理拆解 #

要搞懂这段代码，得先明确信号量P（wait）/V（signal）操作的标准定义：

• wait操作：信号量值减1；若结果<0，线程阻塞并进入等待队列；若≥0，线程继续执行。
• signal操作：信号量值加1；若结果≤0，从等待队列唤醒一个线程，使其继续执行。

接下来分阶段分析：

1. 前n-1个线程的执行流程

每个线程到达 rendezvous 点后：

• 通过mutex互斥更新count，count依次变为1、2...n-1。
• 因为count≠n，不会执行barrier.signal()。
• 执行barrier.wait()：barrier初始值为0，每执行一次wait减1，执行完n-1次后，barrier值为-(n-1)，这n-1个线程全部阻塞在barrier.wait()步骤，进入等待队列。

2. 第n个线程的执行流程

• 同样通过mutex更新count，使其变为n。
• 触发if count == n，执行barrier.signal()：barrier值从-(n-1)变为-(n-2)，由于结果≤0，会唤醒等待队列中的一个线程（比如第一个到达的线程）。
• 随后执行barrier.wait()：barrier值从-(n-2)变为-(n-1)，结果<0，第n个线程自己也进入等待队列。

3. 线程唤醒的连锁反应

被第n个线程唤醒的线程，会继续执行后续代码：

• 它已经通过了barrier.wait()，接下来执行barrier.signal()：barrier值加1，结果仍≤0（直到倒数第二个线程执行signal），这会唤醒等待队列中的下一个线程。
• 每个线程通过屏障后，都会执行一次barrier.signal()，形成连锁唤醒效应：从第一个被唤醒的线程开始，逐个唤醒队列里的其他线程，直到最后一个线程（第n个线程）被唤醒。

最终，所有n个线程都会依次通过屏障，进入临界区。

举个n=3的例子更直观：

• T1、T2先执行，barrier变为-2，两者阻塞。
• T3执行signal，barrier变为-1，唤醒T1；随后T3执行wait，barrier变为-2，自己阻塞。
• T1执行signal，barrier变为-1，唤醒T2；T1进入临界区。
• T2执行signal，barrier变为0，唤醒T3；T2进入临界区。
• T3执行signal，barrier变为1；T3进入临界区。

内容的提问来源于stack exchange，提问作者Miles DeBoer