the little book of semaphores

Below is code in which each thread must wait for each o开发者_StackOverflow社区ther thread to complete the rendezvous part and then wait until everyone has completed the critical section.

/* rendezvous code */
mutex.wait()
count++;
mutex_signal()
if(count==n)
            sem.signal()
sem.wait()
sem.signal()

mutex.wait()
          count--;
mutex.signal()

if(count==0)
         sem.wait()

I know that two processes can reach the case where both see the same value of count (0 or n may be). Due to this two or more signals may be sent at the same time. How can there be a deadlock in the last test. I don't seem to get this.

This is a turnsile kindof semaphore arrangement and author is actually thinking it is a turnstile, but it's a semaphore and it should work without a deadlock. Please tell me how is there a deadlock in this code!

I'll try to explain the way I see it.

All threads but the last will come and wait at the first sem.wait(). Once the last thread arrives it will sem.signal() (because count==n) allowing one of the waiting threads(say T1) to continue. Then T1 will in turn do a sem.signal() which will allow another thread to continue. It is something like a chain reaction. Note that the last thread to pass will also do a signal which will make the Semaphore value 1. Now if two threads come and see that the count==0 then will try to do sem.wait(). But since the semaphore value is 1, one thread will not be able to pass, causing deadlock.

The "if" statements should also be inside the critical sections designated by the "mutex" semaphore, otherwise race conditions can lead to deadlock.

I.e., the correct code is

/* rendezvous code */
mutex.wait()
count++;
if(count==n)
        sem.signal()
mutex.signal()

sem.wait()
sem.signal()

mutex.wait()
      count--;
if(count==0)
     sem.wait()
mutex.signal()