14.2 Semaphores

In 1965, E. W. Dijkstra [30] proposed the semaphore abstraction for high-level management of mutual exclusion and synchronization. A semaphore is an integer variable with two atomic operations, wait and signal . Other names for wait are down , P and lock . Other names for signal are up , V , unlock and post .

If S is greater than zero, wait tests and decrements S in an atomic operation. If S is equal to zero, the wait tests S and blocks the caller in an atomic operation.

If threads are blocked on the semaphore, then S is equal to zero and signal unblocks one of these waiting threads. If no threads are blocked on the semaphore, signal increments S . In POSIX:SEM terminology, the wait and signal operations are called semaphore lock and semaphore unlock , respectively. We can think of a semaphore as an integer value and a list of processes waiting for a signal operation.

Example 14.4

The following pseudocode shows a blocking implementation of semaphores.

 void wait(semaphore_t *sp) {    if (sp->value > 0)       sp->value--;    else {       <Add this process to sp->list>       <block>    } } void signal(semaphore_t *sp) {    if (sp->list != NULL)       <remove a process from sp->list and put in ready state>    else       sp->value++; } 

The wait and signal operations must be atomic. An atomic operation is an operation that, once started, completes in a logically indivisible way (i.e., without any other related instructions interleaved). In this context, being atomic means that if a process calls wait , no other process can change the semaphore until the semaphore is decremented or the calling process is blocked. The signal operation is atomic in a similar way. Semaphore implementations use atomic operations of the underlying operating system to ensure correct execution.

Example 14.5

The following pseudocode protects a critical section if the semaphore variable S is initially 1.

 wait(&S);                                /* entry section or gatekeeper */ <critical section> signal(&S);                                             /* exit section */ <remainder section> 

Processes using semaphores must cooperate to protect a critical section. The code of Example 14.5 works, provided that all processes call wait(&S) before entering their critical sections and that they call signal(&S) when they leave. If any process fails to call wait(&S) because of a mistake or oversight, the processes may not execute the code of the critical section in a mutually exclusive manner. If a process fails to call signal(&S) when it finishes its critical section, other cooperative processes are blocked from entering their critical sections.

Exercise 14.6

What happens if S is initially 0 in the previous example? What happens if S is initially 8? Under what circumstances might initialization to 8 prove useful?

Answer:

If S is initially 0, every wait(&S) blocks and a deadlock results unless some other process calls signal for this semaphore. If S is initially 8, at most eight processes execute concurrently in their critical sections. The initialization to 8 might be used when there are eight identical copies of the resource that can be accessed concurrently.

Example 14.7

Suppose process 1 must execute statement a before process 2 executes statement b . The semaphore sync enforces the ordering in the following pseudocode, provided that sync is initially 0.

 Process 1 executes:           Process 2 executes:   a;                            wait(&sync);   signal(&sync);                b; 

Because sync is initially 0, process 2 blocks on its wait until process 1 calls signal .

Exercise 14.8

What happens in the following pseudocode if the semaphores S and Q are both initially 1? What about other possible initializations?

 Process 1 executes:           Process 2 executes:    for( ; ; ) {                  for( ; ; ) {       wait(&S);                     wait(&Q);       a;                            b;       signal(&Q);                   signal(&S);    }                             } 

Answer:

Either process might execute its wait statement first. The semaphores ensure that a given process is no more than one iteration ahead of the other. If one semaphore is initially 1 and the other 0, the processes proceed in strict alternation . If both semaphores are initially 0, a deadlock occurs.

Exercise 14.9

What happens when S is initially 8 and Q is initially 0 in Exercise 14.8? Hint: Think of S as representing buffer slots and Q as representing items in a buffer.

Answer:

Process 1 is always between zero and eight iterations ahead of process 2. If the value of S represents empty slots and the value of Q represents items in the slots, process 1 acquires slots and produces items, and process 2 acquires items and produces empty slots. This generalization synchronizes access to a buffer with room for no more than eight items.

Exercise 14.10

What happens in the following pseudocode if semaphores S and Q are both initialized to 1?

 Process 1 executes:           Process 2 executes:    for( ; ; ) {                  for( ; ; ) {       wait(&Q);                     wait(&S);       wait(&S);                     wait(&Q);       a;                            b;       signal(&S);               signal(&Q);       signal(&Q);               signal(&S);    }                             } 

Answer:

The result depends on the order in which the processes get the CPU. It should work most of the time, but if process 1 loses the CPU after executing wait(&Q) and process 2 gets in, both processes block on their second wait call and a deadlock occurs.

A semaphore synchronizes processes by requiring that the value of the semaphore variable be nonnegative. More general forms of synchronization allow synchronization on arbitrary conditions and have mechanisms for combining synchronization conditions. OR synchronization refers to waiting until any condition in a specified set is satisfied. The use of select or poll to monitor multiple file descriptors for input is a form of OR synchronization. NOT synchronization refers to waiting until some condition in a set is not true. NOT synchronization can be used to enforce priority ordering [76]. AND synchronization refers to waiting until all the conditions in a specified set of conditions are satisfied. AND synchronization can be used for simultaneous control of multiple resources such as that needed for Exercise 14.10. POSIX:XSI semaphore sets described in Chapter 15 are capable of providing AND synchronization.