The Full Wiki

Semaphore (programming): Wikis


Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.


From Wikipedia, the free encyclopedia

In computer science, a semaphore is a protected variable or abstract data type that constitutes a classic method of controlling access by several processes to a common resource in a parallel programming environment. A semaphore generally takes one of two forms: binary and counting. A binary semaphore is a simple "true/false" (locked/unlocked) flag that controls access to a single resource. A counting semaphore is a counter for a set of available resources. Either semaphore type may be employed to prevent a race condition. On the other hand, a semaphore is of no value in preventing resource deadlock, such as illustrated by the dining philosophers problem.

The semaphore concept was invented by the Dutch computer scientist, Edsger Dijkstra[1], and has found widespread use in a variety of operating systems.


Counting semaphore analogy

Assume the "resources" are tables in a restaurant and the "processes" are the restaurant's customers. The "semaphore" is represented by the maître d’hôtel, who has sole responsibility and authority in granting access to the tables. The maître d mentally maintains a count of unoccupied tables (utables) and always knows who is first to be seated when a table becomes available. He or she is also very focused and can never be interrupted while performing his or her duties.

When the restaurant opens for business, it will initially be empty. In other words, the "value" of the "semaphore" will be equal to the number of tables (tables) in the restaurant—that is, utables=tables. When someone arrives, the maître d will seat him or her, and will mentally reduce the count of available tables, that is, utables=utables-1. Now, the "value" of the "semaphore" will be equal to the number of tables in the restaurant minus one.

If several diners simultaneously arrive, the maître d will seat them in the order of arrival, assuming there are sufficient tables for all (utables > 0). Arriving diners with reservations may be seated ahead of others who do not have reservations, the former having priority over the latter. For each table taken, the maître d will again mentally compute utables=utables-1. If all tables are occupied, that is, utables=0, new arrivals will have to wait their turn to be seated.

As each diner leaves, the maître d will mentally compute utables=utables+1. If another diner is waiting and at least one unoccupied table is available, the maître d will seat him or her, and again mentally compute utables=utables-1. Eventually, all diners will have left and the maître d's utables=utables+1 mental computation will result in utables=tables—an empty restaurant.


Counting semaphores are accessed using operations similar to the following Pascal examples. Procedure V will increment the semaphore S, whereas procedure P will decrement it:

 procedure V (S : Semaphore);
   (* Atomic operation: increment the semaphore. *)
   S := S + 1;
   (* Atomic operation: decrement the semaphore. *)
 procedure P (S : Semaphore);
   (* Whole operation is atomic *)
   until S > 0;
   S := S - 1;

The value of the semaphore S is the number of units of the resource that have not been claimed. If there is only one such resource, a binary semaphore is used as a simple "true/false" flag. The P operation wastes time or sleeps until a resource controlled by the semaphore becomes available, at which time the resource is immediately claimed. The V operation is the inverse: it makes a resource available again after the process has finished using it.

The counting semaphore concept can be extended with the ability to claim or return more than one "unit" from the semaphore. a technique implemented in UNIX. The modified V and P operations would be as follows:

 procedure V (S : Semaphore; I : Integer);
   S := S + I (* atomic operation *)
 procedure P (S : Semaphore; I : Integer);
   (* Whole operation is atomic *)
   until S >= I;
   S := S - I

To avoid starvation, a semaphore may have an associated queue of processes (usually a first-in, first out). If a process performs a P operation on a semaphore that has the value zero, the process is added to the semaphore's queue. When another process increments the semaphore by performing a V operation, and there are processes on the queue, one of them is removed from the queue and resumes execution. When processes have different priorities the queue may be ordered by priority, so that the highest priority process is taken from the queue first.

To guarantee that two or more processes do not attempt to simultaneously modify the same semaphore, the operations that actually increment or decrement the semaphore are designated as atomic, meaning they cannot be interrupted, such as by preemption. This requirement may be met by using a machine instruction that is able to read, modify and write the semaphore in a single operation. In the absence of such a hardware instruction, atomic operation may be synthesized by temporarily suspending preemption or, less desirably, by temporarily disabling hardware interrupts.

Function names

The canonical names P and V come from the initials of Dutch words. V stands for verhogen ("increase"). Several explanations have been offered for P, including proberen for "to test,"[2] passeer for "pass," probeer for "try," and pakken for "grab." However, Dijkstra wrote that he intended P to stand for the made-up word prolaag,[3] short for probeer te verlagen, literally "try to reduce," or to parallel the terms used in the other case, "try to decrease." [4][5][6] This confusion stems from the fact that the words for increase and decrease both begin with the letter V in Dutch, and the words spelled out in full would be impossibly confusing for those not familiar with the Dutch language.

In ALGOL 68, the Linux kernel,[7] and in some English textbooks, the P and V operations are called, respectively, down and up. In software engineering practice, they are often called wait and signal, acquire and release (which the standard Java library uses [8]), or pend and post. Some texts call them procure and vacate to match the original Dutch initials.

Current usage

Semaphores remain in common use in programming languages that do not intrinsically support other forms of synchronization. They are the primitive synchronization mechanism in many operating systems. The trend in programming language development, though, is towards more structured forms of synchronization, such as monitors (though these advanced structures typically employ semaphores behind the scenes). In addition to their inadequacies in dealing with (multi-resource) deadlocks, semaphores do not protect the programmer from the easy mistakes of taking a semaphore that is already held by the same process, and forgetting to release a semaphore that has been taken.

Binary semaphore vs. Mutex vs. Event

A mutex is a binary semaphore that usually incorporates extra features, such as ownership, priority inversion protection or recursivity. The differences between mutexes and semaphores are operating system dependent, though mutexes are implemented by specialized and faster routines. Mutexes are meant to be used for mutual exclusion (post/release operation is restricted to thread that called pend/acquire) only and binary semaphores are meant to be used for event notification (post-ability from any thread) and mutual exclusion.

Events are also sometimes called event semaphores and are used for event notification.

See also

Notes and references

  1. ^ E. W. Dijkstra, Cooperating sequential processes. Technological University, Eindhoven, The Netherlands, September 1965.
  2. ^ Silberschatz, Galvin, & Gagne 8th Ed. p.234
  3. ^
  4. ^ MULTIPROGAMMERING EN DE X8 from the E.W. Dijkstra Archive (in Dutch)
  5. ^ Dijkstra's own translation reads "try-and-decrease", although that phrase might be confusing for those unaware of the colloquial "try-and..."
  6. ^ Linux Kernel Mailing List: [PATCH 1/19] MUTEX: Introduce simple mutex implementation
  7. ^ Kernel hacking howto on
  8. ^ java.util.concurrent.Semaphore
  • Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Operating System Concepts (8th ed.), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5 

External links



Got something to say? Make a comment.
Your name
Your email address