I seem to have trouble understand the Semaphore implementation. Q = Queue.

Wait(Process P) {
    value = value - 1; 
    if (value < 0) {
       add P to Q;

Signal() {
    value = value + 1;
    if (value <= 0) {
      remove P from Q;

I don't understand why the signal remove P from Q if the value is negative. Let's consider this scenario.

Semaphore value is 0;

Thread A Calls


// Now Semaphore value is -1 and thread A is in the waiting queue.

Thread B Calls:


// Now Semaphore value is -2 and thread B is in the waiting queue.

Thread C Calls:


** // Now Semaphore value is -1 and thread A is removed from queue and is placed in the ready queue?! Why is that? **

  • 1
    Because... that's what the code does? What's wrong with that? What about it is causing you difficulty? – Jack Parkinson Jul 13 '17 at 7:45
  • That doesn't make any sense...The semaphore value is -1 and it's released from the queue. Semaphore shouldn't behave like that.... – MasterOfPuppets Jul 13 '17 at 8:21
  • What is the initial value of semaphore? It will be >1 if its a counting semaphore? I am suspecting you are getting confused with this aspect. – nikhil_kotian Jul 13 '17 at 10:36
  • The initial value is 0.I specified it above... – MasterOfPuppets Jul 13 '17 at 10:36
  • Could you please fix your code? especially missing braces – Adrian Maire Jul 14 '17 at 8:57

Simple: If your value is 0, then every consecutive wait () puts one thread on the waiting queue, and every consecutive signal () removes one thread from the waiting queue. wait and signal should come in pairs, each thread calling wait () going on the queue until there is a matching signal ().

To explain the behaviour when the value is > 0: Normally, you use wait/signal like this: You start an independent thread to do some work. You call wait() to wait for the thread to finish. The thread calls signal() to signal that it has done its job. And you would expect that wait () is called before signal(), so everything works as described above.

But what if the thread is very very fast and manages to finish before you wait for it to finish? It calls signal() but there is no matching thread calling wait () yet, so it just increases the value. Then the waiting thread calls wait (). The value was positive, because signal() was called before wait(), so the waiting thread can continue running immediately.

| improve this answer | |
  • So, you are saying that if I initialize a semaphore with a value of -5 and then I call wait, and right afterward I call signal. The thread that I called wait on will get into a running state? Is that right? – MasterOfPuppets Jul 14 '17 at 18:08

I don't understand why the signal remove P from Q if the value is negative.

if (value <=0) {
  remove P from Q;

If value is negative, then value <= 0 is true, and P will be removed.

If you look at other implementations, for example the description at https://msdn.microsoft.com/en-us/library/windows/desktop/ms685129(v=vs.85).aspx vs the description at http://www.cs.fsu.edu/~baker/opsys/notes/semaphores.html then there are differences, for example in the Windows implementation the count can't be less than zero and resources are available if the count is greater than zero:

A semaphore object is a synchronization object that maintains a count between zero and a specified maximum value. The count is decremented each time a thread completes a wait for the semaphore object and incremented each time a thread releases the semaphore. When the count reaches zero, no more threads can successfully wait for the semaphore object state to become signaled. The state of a semaphore is set to signaled when its count is greater than zero, and nonsignaled when its count is zero.

Each time one of the wait functions returns because the state of a semaphore was set to signaled, the count of the semaphore is decreased by one. The ReleaseSemaphore function increases a semaphore's count by a specified amount. The count can never be less than zero or greater than the maximum value.

This implementation appears to be working the opposite way round, something like

Wait(Process P)
    if (value == 0)
        add P to Q;
        value = value -1; 

    value = value + count
    if value > max_count
        value = max_count

    while (value > 0 and Q is not empty ) 
      value = value - 1
      remove P from Q

The difference between this behaviour and that of semaphores described at http://www.cs.fsu.edu/~baker/opsys/notes/semaphores.html is that 'value' is the only ever the number of resources available, rather than going negative if there are processes waiting.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.