Semaphore (programming)

For other uses, see Semaphore.

In computer science(CSE S6 VIDYA ACADEMY) , 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, 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’hôtel 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’hôtel 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’hôtel 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’hôtel 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’hôtel will mentally compute utables=utables+1. If another diner is waiting and at least one unoccupied table is available, the maître d’hôtel will seat him or her, and again mentally compute utables=utables-1. Eventually, all diners will have left and the maître d’hôtel's utables=utables+1 mental computation will result in utables=tables—an empty restaurant.

Implementation

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);
 begin
   (* Atomic operation: increment the semaphore. *)
   S := S + 1;
 end;
 
   (* Atomic operation: decrement the semaphore. *)
 procedure P (S : Semaphore);
 begin
   (* Whole operation is atomic *)
   repeat
     Wait();
   until S > 0;
   S := S - 1;
 end;

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);
 begin
   S := S + I (* atomic operation *)
 end;

 procedure P (S : Semaphore; I : Integer);
 begin
   (* Whole operation is atomic *)
   repeat
     Wait()
   until S >= I;
   S := S - I
 end;

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 name etymology

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," 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, short for probeer te verlagen, literally "try to reduce," or to parallel the terms used in the other case, "try to decrease." 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, 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 ), 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

• Cigarette smokers problem
• Dining philosophers problem
• Readers-writers problem
• Sleeping barber problem
• Producers-consumers problem
• Reentrant mutex, which can "count" like a counting semaphore.

Notes and references

• 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

• Over Seinpalen (EWD 74), in which Dijkstra introduces the concept (in Dutch)
• semaphore.h programming interface - The Open Group Base Specifications Issue 6, IEEE Std 1003.1
• The Little Book of Semaphores, by Allen B. Downey
• A pragmatic, historically oriented survey on the universality of synchronization primitives, by Jouni Leppäjärvi