Semaphore

What is Semaphore

Semaphore is an integer variable (S). Two atomic operations, wait() and signal(), help to modify the value of the semaphore. When a specific process changes the semaphore value, another process cannot modify the semaphore value simultaneously.

The code of wait and signal are as follows.

wait(S)

{

while(s<=0);

s–;

}

signal(s)

{

s++;

}

Moreover, there are two types of semaphore; binary semaphore and counting semaphore. In a binary semaphore, the integer value can change between 0 to 1. If a process wants to access the critical section, it performs the wait() operation. Then, it decreases the semaphore value from 1 to 0. When exiting the critical section, it performs signal() operation on the semaphore. Thus, it will increase the value to 1.

In counting semaphores, the value can change in an unrestricted domain. If a process requires to execute in the critical section, it a () operation and decrements the semaphore value by 1. When exiting the critical section, it performs signal() operation and increments the semaphore value by one.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

 SEMAPHORES 

Semaphores provide a much more organized approach to controlling the interaction of multiple processes than would be available if each user had to solve all inter process communications using simple variables, but more organization is possible. In a sense, semaphores are something like the goto statement in early programming languages; they can be used to solve a variety of problems, but they impose little structure on the solution and the results can be hard to understand without the aid of numerous comments. Just as there have been numerous control structures devised in sequential programs to reduce or even eliminate the need for goto statements, numerous specialized concurrent control structures have been developed which reduce or eliminate the need for semaphores. 

Definition: The effective synchronization tools often used to release mutual exclusion in more complex systems are semaphores. A semaphore S is an integer variable which can be accessed only through two standard atomic operations: wait and signal. The definition of the wait and signal operation are:

wait(S): while S ≤ 0 do skip;

S := S – 1; 

signal(S): S := S + 1;

or in C language notation we can write it as: 

wait(s) 

 { 

while (S<=0) 

{

 /*do nothing*/ 

 }

 S= S-1; 

 }

 signal(S) 

 { 

 S = S + 1;

 }

It should be noted that the test (S ≤ 0) and modification of the integer value of S which is S := S – 1 must be executed without interruption. In general, if one process modifies the integer value of S in the wait and signal operations, no other process can simultaneously modify that same S value. We briefly explain the usage of semaphores in the following example: 

Consider two currently running processes: P1 with a statement S1 and P2 with a statement S2. Suppose that we require that S2 be executed only after S1 has completed. This scheme can be implemented by letting P1 and P2 share a common semaphore synch, initialised to 0, and by inserting the statements:

S1;

signal(synch); 

in the process P1 and the statements: 

wait(synch); 

S2;

in the process P2. 

Since synch is initialized to 0, P2 will execute S2 only after P1 has involved signal (synch), which is after S1.

The disadvantage of the semaphore definition given above is that it requires busy-waiting, i.e., while a process is in its critical region, any either process it trying to enter its critical region must continuously loop in the entry code. It’s clear that through busy-waiting, CPU cycles are wasted by which some other processes might use those productively.

To overcome busy-waiting, we modify the definition of the wait and signal operations. When a process executes the wait operation and finds that the semaphore value is not positive, the process blocks itself. The block operation places the process into a waiting state. Using a scheduler the CPU then can be allocated to other processes which are ready to run. 

A process that is blocked, i.e., waiting on a semaphore S, should be restarted by the execution of a signal operation by some other processes, which changes its state from blocked to ready. To implement a semaphore under this condition, we define a semaphore as:

struct semaphore

 { 

 int value;

 List *L; //a list of processes

 }

Each semaphore has an integer value and a list of processes. 

When a process must wait on a semaphore, it is added to this list. A signal operation removes one process from the list of waiting processes, and awakens it. The semaphore operation can be now defined as follows:

 wait(S) 

 {

 S.value = S.value -1;

 if (S.value <0)

{

 add this process to S.L;

 block; 

   } 

 } 

   signal(S) 

 {

   S.value = S.value + 1;

    if (S.value <= 0) 

   {

      remove a process P from S.L;

      wakeup(P);

       } 

    } 

 The block operation suspends the process. The wakeup(P) operation resumes the execution of a blocked process P. These two operations are provided by the operating system as basic system calls. 

One of the almost critical problem concerning implementing semaphore is the situation where two or more processes are waiting indefinitely for an event that can be only caused by one of the waiting processes: these processes are said to be deadlocked. To illustrate this, consider a system consisting of two processes P1 and P2, each accessing two semaphores S and Q, set to the value one:

               P1                                                 P2

             wait(S);                                       wait(Q);

             wait(Q);                                       wait(S);

                 ...                                                    ...

             signal(S);                                     signal(Q);

             signal(Q);                                     signal(S);

Suppose P1 executes wait(S) and then P2 executes wait(Q). When P1 executes wait(Q), it must wait until P2 executes signal(Q). It is no problem, P2 executes wait(Q), then signal(Q). Similarly, when P2 executes wait(S), it must wait until P1 executes signal(S). Thus these signal operations cannot be carried out, P1 and P2 are deadlocked. It is clear, that a set of processes are in a deadlocked state, when every process in the set is waiting for an event that can only be caused by another process in the set.