I don’t get how turnstiles are able to work

by

I’m reading the little book of semaphores and reached the following code:

rendezvous

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

if count == n: barrier . signal ()

barrier . wait ()// the part i don't get
barrier . signal ()

critical point

barrier is semaphore(0) and mutex is semaphore(1)
the book says that this code works, but i have no clue how. if n-1 threads reach the barrier.wait(), the barrier will equal -(n-1) and at for the last thread where count == n, it signals the barrier, but wont that only make the barrier -(n-1)+1 which is still negative for most values of n. apparently this is supposed to start to let the threads go past one by one, but i am confused. can someone explain

  • The barrier.signal() after the barrier.wait() lets the next thread through, and then it lets the next thread through, etc.

    – 

if n-1 threads reach the barrier.wait(), the barrier will equal -(n-1)

Absolutely not. It is a basic property of semaphores, which your book taught long before this point, that the value of a semaphore cannot be reduced below 0. A thread attempting to decrement a semaphore when its value is already zero will block until the value is positive.

for the last thread where count == n, it signals the barrier, but wont that only make the barrier -(n-1)+1 which is still negative for most values of n

No. When the last thread makes it through, it will increase the barrier semaphore from 0 to 1. That will allow either that same thread itself or one of those already blocked at barrier.wait() to complete a barrier.wait(). That briefly reduces the semaphore’s value to 0 again, but each thread that reaches that point continues by incrementing the barrier semaphore again, letting one more thread through.

Leave a Comment