19.5.2 Semaphores

A semaphore is an object with two basic methods: wait and signal (or release). To use a semaphore you create a semaphore variable (an instance) for a particular critical region or other resource you want to protect. When a process wants to use a given resource it waits on the semaphore. If no other process is currently using the resource then the wait call sets the semaphore to in-use and immediately returns to the process. At that time the process has exclusive access to the resource. If some other process is already using the resource (e.g. is in the critical region) then the semaphore blocks the current process by moving it off the run queue and onto the semaphore queue. When the process that currently holds the resource releases it the release operation removes the first waiting process from the semaphore queue and places it back in the run queue. At the next available time slice that new process returns from its wait call and can enter its critical region.

Semaphores solve the two important problems with the busy-waiting loop described in the previous section. First when a process waits and the semaphore blocks the process that process is no longer on the run queue so it consumes no more CPU time until the point that a release operation places it back onto the run queue. So unlike busy-waiting the semaphore mechanism does not waste (as much) CPU time on processes that are waiting for some resource.

Semaphores can also solve the starvation problem. The wait operation when blocking a process can place it at the end of a FIFO semaphore queue. The release operation can fetch a new process from the front of the FIFO queue to place back on to the run queue. This policy ensures that each process entering the semaphore queue gets equal priority access to the resource.

Implementing semaphores is an easy task. A semaphore generally consists of an integer variable and a queue. The system initializes the integer variable with the number of processes than may share the resource at one time (this value is usually one for critical regions and other resources requiring exclusive access). The wait operation decrements this variable. If the result is greater than or equal to zero the wait function simply returns to the caller; if the result is less than zero the wait function saves the machine state moves the process' pcb from the run queue to the semaphore's queue and then switches the CPU to a different process (i.e. a yield call).

The release function is almost the converse. It increments the integer value. If the result is not one the release function moves a pcb from the front of the semaphore queue to the run queue. If the integer value becomes one there are no more processes on the semaphore queue so the release function simply returns to the caller. Note that the release function does not activate the process it removes from the semaphore process queue. It simply places that process in the run queue. Control always returns to the process that made the release call (unless of course a timer interrupt occurs while executing the release function).

Of course any time you manipulate the system's run queue you are in a critical region. Therefore we seem to have a minor problem here - the whole purpose of a semaphore is to protect a critical region yet the semaphore itself has a critical region we need to protect. This seems to involve circular reasoning. However this problem is easily solved. Remember the main reasons we do not turn off interrupts to protect a critical region is because that critical region may take a long time to execute or it may call other routines that turn the interrupts back on. The critical section in a semaphore is very short and does not call any other routines. Therefore briefly turning off the interrupts while in the semaphore's critical region is perfectly reasonable.

If you are not allowed to turn off interrupts you can always use a test and set instruction in a loop to protect a critical region. Although this introduces a busy-waiting loop it turns out that you will never wait more than two time slices before exiting the busy-waiting loop so you do not waste much CPU time waiting to enter the semaphore's critical region.

Although semaphores solve the two major problems with the busy waiting loop it is very easy to get into trouble when using semaphores. For example if a process waits on a semaphore and the semaphore grants exclusive access to the associate resource then that process never releases the semaphore any processes waiting on that semaphore will be suspended indefinitely. Likewise any process that waits on the same semaphore twice without a release in-between will suspend itself and any other processes that wait on that semaphore indefinitely. Any process that does not release a resource it no longer needs violates the concept of a semaphore and is a logic error in the program. There are also some problems that may develop if a process waits on multiple semaphores before releasing any. We will return to that problem in the section on deadlocks (see "Deadlock").

Although we could write our own semaphore package (and there is good reason to) the Standard Library process package provides its own wait and release calls along with a definition for a semaphore variable. The next section describes those calls.

Chapter Nineteen: Processes Coroutines and Concurrency (Part 13)
29 SEP 1996