Semaphores

Semaphores

This was the position in 1965, when E. W. Dijkstra (1965) suggested using an integer variable to count the number of wakeups saved for future use. In his suggestion, a new variable type, which he called a semaphore, was introduced. A semaphore could have the value 0, indicating that no wakeups were saved, or some positive value if one or more wakeups were pending.

Dijkstra suggested having two operations, down and up (generalizations of sleep and wakeup, respectively). The down operation on a semaphore checks to see if the value is greater than 0. If so, it decreases the value (i.e., uses up one stored wakeup) and just continues. If the value is 0, the process is put to sleep without completing the down for the moment. Checking the value, changing it, and maybe going to sleep, are all done as a single, indivisible atomic action. It is guaranteed that once a semaphore operation has started, no other process can access the semaphore until the operation has completed or blocked. This atomicity is very essential to solving synchronization problems and avoiding race conditions.  Atomic actions, in which a group of related operations are either all performed without interruption or not performed at all, are very important in many other areas of computer science as well.

The up operation increments the value of the semaphore addressed. If one or more processes were sleeping on that semaphore, unable to complete an earlier down operation, one of them is chosen by the system (e.g., at random) and is allowed to complete its down. Thus, after an up on a semaphore with processes sleeping on it, the semaphore will still be 0, but there will be one fewer process sleeping on it. The operation of incrementing the semaphore and waking up one process is also indivisible. No process ever blocks doing an up, just as no process ever blocks doing a wakeup in the earlier model.

As an aside, in Dijkstra's original paper, he used the names P and V instead of down and up, respectively. Since these have no mnemonic importance to people who do not speak Dutch and only minor importance to those who do - Proberen (try) and Verhogen (raise, make higher),  we will use the terms down and up instead. These were first introduced in the Algol 68 programming language.

Solving the Producer-Consumer Problem Using Semaphores

Semaphores solve the lost-wakeup problem, as shown in Figure 1. To make them work accurately, it is important that they be implemented in an indivisible way. The normal way is to implement up and down as system calls, with the operating system briefly disabling all interrupts while it is testing the semaphore, updating it, and putting the process to sleep, if required. As all of these actions take only a few instructions, no harm is done in disabling interrupts. If numerous CPUs are being used, each semaphore should be protected by a lock variable, with the TSL or XCHG instructions used to make sure that only one CPU at a time observes the semaphore.

Be sure you understand that using TSL or XCHG to prevent several CPUs from accessing the semaphore at the same time is completely different from the producer or consumer busy waiting for the other to empty or fill the buffer. The semaphore operation will only take a few microseconds, whereas the producer or consumer might take randomly long.

This solution uses three semaphores: one called full for counting the number of slots that are full, one called empty for counting the number of slots that are empty, and one called mutex to make sure the producer and consumer do not access the buffer at the same time. Full is initially 0, empty is initially equal to the number of slots in the buffer, and mutex is initially 1. Semaphores that are initialized to 1 and used by two or more processes to ensure that only one of them can enter its critical region at the same time are called binary semaphores. If each process does a down just before entering its critical region and an up just after leaving it, mutual exclusion is guaranteed.

Now that we have a good interprocess communication primitive at our disposal, let us go back and look at the interrupt sequence of "Implementation of Processes" Figure (c) again. In a system using semaphores, the natural way to hide interrupts is to have a semaphore, in the beginning set to 0, associated with each I/O device.  Just after starting an I/O device, the managing process does a down on the associated semaphore, hence blocking immediately. When the interrupt comes in, the interrupt handler then does an up on the associated semaphore, which makes the relevant process ready to run again. In this model, step 5 in "Implementation of Processes" Figure (c) comprises doing an up on the device's semaphore, so that in step 6 the scheduler will be able to run the device manager. Of course, if numerous processes are now ready, the scheduler may choose to run an even more important process next. We will examine some of the algorithms used for scheduling later on in this section.

In the example of Figure 1, we have in fact used semaphores in two different ways. This difference is essential enough to make clear. The mutex semaphore is used for mutual exclusion. It is designed to guarantee that only one process at a time will be reading or writing the buffer and the associated variables. This mutual exclusion is necessary to prevent chaos. We will study mutual exclusion and how to achieve it in the next section.

The producer-consumer problem using semaphores

The other use of semaphores is for synchronization. The full and empty semaphores are required to guarantee that certain event sequences do or do not take place. In this case, they ensure that the producer stops running when the buffer is full, and that the consumer stops running when it is empty. This use is different from mutual exclusion.



Tags

semaphore, atomic action, system calls, interrupts, i/o device