理解ReusableBarrier问题(摘自“信号量小书”)

Question

问题陈述如下：

通常，一组协作线程将在循环中执行一系列步骤，并在每个步骤之后在障碍处进行同步。对于这个应用程序，我们需要一个可重用的屏障，在所有线程都通过后将其自身锁定。

给定的解决方案是：

1 # rendezvous
2
3 mutex.wait()
4     count += 1
5     if count == n:
6         turnstile2.wait() # lock the second
7         turnstile.signal() # unlock the first
8 mutex.signal()
9
10 turnstile.wait() # first turnstile
11 turnstile.signal()
12
13 # critical point
14
15 mutex.wait()
16     count -= 1
17     if count == 0:
18         turnstile.wait() # lock the first
19         turnstile2.signal() # unlock the second
20 mutex.signal()
21
22 turnstile2.wait() # second turnstile
23 turnstile2.signal()

假设我们将此屏障用于2个线程，并通过此屏障抽出100个线程。当第二个线程已经解锁了旋转门(7)并到达第9行时，现在，线程3出现了，

它递增计数，

count >n所以它释放互斥锁，

由于旋转门是解锁的，它也达到了临界点，

类似地，线程4、线程5、线程6可以执行临界点，执行2次以上。

是什么阻止他们通过线程2前面的障碍物？还是我的理解错了？

Answer 1

问题陈述指出(第22页)：

你可以假设有n个线程，并且这个值存储在一个变量n中，这个变量可以从所有线程访问。

因此，如果n=2有100个线程，您就违反了这一假设，解决方案将无法工作。

Answer 2

也许这超出了问题的范围，但这里是这样的:所列出的解决方案是我所能告诉的最多n个线程在屏障代码内的正确。保证这一点的一种方法是总共只有n个线程。

这本书还提供了一种不同的方法来确保只有n个线程在给定的区域内: Multiplex (使用信号量来保证最多n个线程同时使用给定的资源)。像这样使用它：

general_barrier.init(n):
    occupancy = Semaphore(n)
    barrier = Barrier(n)
general_barrier.enter():
    occupancy.wait()
    barrier.enter()
    barrier.leave()
general_barrier.leave():
    occupancy.signal()

您可以这样使用它：

shared state:
    gbarrier = general_barrier(n)
each of m threads (where m > n, but in particular try m > 2*n):
    while True:
        gbarrier.enter()
        something critical
        gbarrier.leave()

在问题中的代码中，您可以将occupancy.wait()放在第2行，将occupancy.signal()放在第24行，基本上就有了这个解决方案。请注意，问题中的代码将barrier.leave()的等价物放在临界点之后，即在general_barrier.leave()中，而不是像我之前那样。我认为这对于正确性来说并不重要，尽管它可能与执行的上下文切换的数量有关。也许，在某些情况下。建议读者自行决定;-)