Operation System -> Process Synchronisation -> Counting Semaphores

Question

Struct Semaphore

{            int value;

              Queue type L;

}

 

Down (Semaphore S)

{

 

              S.value = S.value -1;

 

              if(S.value<0)

               { put process in L;

               sleep();

 }

else return;

 

}

 

Up(Semaphore S)

{           S.value = S.value +1; // line1

            if(S.value<=0)  //line 2

              {       Select a process from L; //line 3

                        wakeup(); // line 4

                }

}

 

When we are Executing 'Up',

say S.value = -3

now after line 1 S.value is -2

Now it will enter the if-block

and select a process from L (which has 2 processes in it as S.value is -2) and wake up a process

Why does it wake up a process from a sleep when the S.value is still less than 0?

The process which is woken up will try to Execute 'Down' and fail and eventually go back to sleep. Then why was it woken up in the first place? Shouldn't we execute the if block as :

 

if(S.value>=0)

{select a process from L, wakeup();

}

 

(I know I'm wrong somewhere, please correct me. I referred Tanenbaum and Galvin but didn't find any such explanation for Counting Semaphores)

Comments

To realize this you must think how a process enters in to L.

say a process p1 perform down operation on a semaphore whose value is 0(before down operation).

now it becomes -1 after decrementing and since its less than zero it will go in to L and sleeps there

now when another process chose that p1 from L and wake up then p1 will not again perform down operation rather it will resume and now executes instructions just next to down operation where it left before.

 

so similarly in your query a process being wakeup not again perform repeated down operation it will just resumes its execution from the point it left..

 

and by this procedures we ensure that by the time semaphore value becomes nonnegative there is no process in its waiting queue or suspended list.

Answer 1

The negative value in semaphore indicates that no of process tries to enter the cs after cs is occupied.As it is a queue the process stores in FIFO order,when a process exit from cs it perform a wakeup on a process from queue and it enters the cs.
NOTE:In counting semaphores more than one process can  access the shared resource.
if s.value is non negative then process directly enters CS without being block
see for reference https://stackoverflow.com/questions/10898022/difference-between-counting-and-binary-semaphores