Semaphores

The solutions to the critical-section problem presented before are not easy to generalize to more complex problems. To overcome this difficulty, we can use a synchronization tool called a semaphore. A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait and signal. These operations were originally termed P (for wait; from the Dutch proberen, to test) and V (for signal; from Verhagen, to increment). The classical definition of wait in pseudocode is

 

wait(S) {

while (S <= 0)

; // no-op

S –;

}

The classical definitions of signal in pseudocode is

 

Signal(S){

S++;

}

 

Modifications to the integer value of the semaphore in the wait and signal operations must be executed indivisibly. That is, when one process modifies the semaphore value, no other process can simultaneously modify that same semaphore value. In addition, in the case of the wait (S), the testing of the integer value of S (S 5 O), and its possible modification (S–), must also be executed without interruption.

 

Usage

We can use semaphores to deal with the n-process critical-section problem. The n processes share a semaphore, mutex (standing for mutual exclusion), initialized to 1. Each process Pi is organized as shown in Figure.We can also use semaphores to solve various synchronization problems.

For example, consider two concurrently running processes: PI with a statement S1 and P2 with a statement S2. Suppose that we require that S2 be executed only after S1 has completed. We can implement this scheme readily by letting P1 and P2 share a common semaphore synch, initialized to 0, and by inserting the statements in process PI, and the statements

 

wait (synch) ;

s2;

in process P2. Because synch is initialized to 0, P2 will execute S2 only after PI

has invoked signal (synch), which is after S1.

s1;

signal (synch) ;

do {

wait (mutex) ;

critical section

signal (mutex) ;

remainder section

} while (1);

 

• Mutual-exclusion implementation with semaphores