Introduction

Conceptually, a semaphore is a data structure that is shared by several processes. [1] Semaphores are most often used to synchronize operations when multiple processes access a common, non-shareable resource. By using semaphores, we attempt to avoid starvation (which occurs when a process is habitually denied access to a resource it needs) and deadlock (which occurs when two or more processes each hold a resource that the other needs while waiting for the other process to release its resource). When used to synchronize the access to a resource, a semaphore is initially set to the number of available resources. Each time a process wants to obtain the resource, the associated semaphore is tested . A positive, nonzero semaphore value indicates the resource is available. To indicate it has gained access to the resource, the process decrements the semaphore. For events to progress correctly, the test and decrement operation on the semaphore must be atomic (i.e., noninterruptible/indivisible). If the tested semaphore is zero, indicating the resource is not available, the requesting process must wait. When a process is finished with a semaphore-associated resource, the process indicates the return of the resource by incrementing the semaphore. Once a resource is returned, other processes that have been waiting for the resource are notified by the system. Semaphores that control access to a single resource, taking the value of 0 (resource is in use) or 1 (resource is available), are often called binary semaphores. [2] Semaphores controlling access to multiple resources, thus assuming a range of nonnegative values, are frequently called counting semaphores.

[1] In this chapter we concentrate on semaphores as they relate to processes. In Chapter 11, we revisit semaphores and address their use with threads.

[2] In function, binary semaphores are similar to the lock files discussed in Chapter 4. Unfortunately, semaphores can only be used by processes residing on the same system, while, with some stretching, lock files can be implemented in a networked environment. Of course, semaphores are much faster and more reliable than lock files.

E. W. Dijkstra (1965) did much of the early work describing the use of semaphores to coordinate access to shared resources. Most college-level operating systems textbooksfor example, Silberschatz and Peterson (1989), Tanenbaum (2001), Nutt (2002), Stallings (2001), and Deitel (1990)contain excellent discussions on the theory and use of semaphores for process synchronization.

Implementation-wise, a semaphore is a nonnegative integer that is stored in the kernel. Access to the semaphore is provided by a series of semaphore system calls. The semaphore system calls assure the user the test and decrement operations on the semaphore will be atomic. Likewise, the semaphore system calls, by default, cause the invoking process to block if the semaphore value indicates the resource is not available (i.e., the semaphore is a 0). When the resource becomes available and the semaphore becomes nonzero, the system notifies the queued, waiting processes of this event. To increase their flexibility, in UNIX semaphores are generated as sets (arrays) consisting of one or more semaphores. Operations acting upon individual semaphores within the set or upon the entire semaphore set are provided.