Question

Using a pseudocode example, explain the wait and signal operations of a binary semaphore.

Answer 1

*****************************Please give feedback if there is an issue in explanation.Thanks*********************

Abbreviation:

1. CS Critical Section where shared variables are accessed and no two process can coexist.
2. S Binary Semaphore

Binary Semaphore can only attain two value 0 or 1. Value 1 indicate that no process is currently in Critical Section.Value 0 indicate that one process is in critical section or may be more process are waiting to enter in CS. Binary Semaphore supports two operation wait(S) and Signal(S). Every process accessing a CS executes wait(S) before entering CS and executes Signal(S) after exiting CS further elaborated.

Terms Used

1. waiting Queue : Queue that maintain all process that waiting to enter critical section .This queue is First In First Out.
2. process Queue: Queue that maintain all process that are currently ready to be executed. Similar to ready queue. This queue is priority queue and priority is decided by which type of CPU scheduling algo is used

All process follow the below sequence of code

wait(S)

.....

CS

........

signal(S)

The wait and signal can be implemented in two approached

BLOCKING : CPU cycles are wasted on doing nothing just Looping.Unknown which process will be processed.(mainly depend on CPU scheduler which is selecting the process when signal was called). Can lead to starvation when a process is never get selected after a Signal

NON-BLOCKING : CPU cycles are not wasted but a waiting queue is maintained. Guarantee first process that was put in wait queue to removed first when signal is called . Least waiting time and no starvation.

Below is implementation of above approaches

=============================BLOCKING CALL===============================================

wait(S) {

while(S==0); // Loops forever until S is changed to 1

S=S-1; // The statement is only executed when S=1;

}

Signal(S)

{

if(s>=1)

return;

else

s=s+1;

}

====================NON-BLOCKING-CALL====================================================

wait(S)

{

if(S==1) //No process is waiting of this semaphore

{

S=0; // S is decreased to denote a process is waiting

return;

}

else

{

insert process 'p' executing wait to queue(Q) of waiting process.

Suspend(P); //Move process 'p' out of process queue

}

}

Signal (S)

{

if(S>=1) // A signal is called on no suspended process

return;

else // there is atleast one process suspended

{

P=remove from wait queue // first waited process is choden

resume(p); //Allow it execute by moving to process queue

}

}

Reference : Opearting System by Silberschatz, Galvin et al