Understanding ReusableBarrier Problem (from 'Little Book of Semaphores')

The problem statement is as follows:

Often a set of cooperating threads will perform a series of steps in a loop and synchronize at a barrier after each step. For this application we need a reusable barrier that locks itself after all the threads have passed through.

Given Solution is:

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()

Suppose we use this barrier for 2 threads and we pump 100 threads through this barrier. when second thread has unlocked turnstile(7) and reaches line 9, now, thread 3 come along and,

it increments count,

count > n so it releases mutex,

since turnstile is unlocked it reaches critical point also,

similarly, thread 4, thread 5, thread 6 can execute critical 开发者_StackOverflowpoint, executing it more than 2 times.

what is stopping them from passing through the barrier ahead of thread 2? Or is my understanding wrong here?

---

The problem statement indicates (page 22):

You can assume that there are n threads and that this value is stored in a variable, n, that is accessible from all threads.

So if n=2 and there are 100 threads, you have violated this assumption and the solution will not work.

---

Maybe this goes beyond the question, but here goes: the listed solution is as far as I can tell correct as long as at most n threads are inside the barrier code. One way of guaranteeing this is to only have n threads in total.

The book also presents a different way of ensuring that only n threads are inside a given region: the Multiplex (using a Semaphore to guarantee that at most n threads use a given resource at a time). Use it like this:

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

You would use it like this:

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()

In the code in the question, you could put occupancy.wait() on line 2 and occupancy.signal() on line 24, and have basically this solution. Note that the code in the question puts the equivalent of barrier.leave() after the critical point, i.e. in general_barrier.leave(), rather than before as I have done it. I don't think this matters for correctness, though it may matter in regards to the number of context switches performed. Maybe, in some situations. Reader discretion is advised ;-)