In computer science, a
semaphore is a
variableIn computer programming, a variable is a symbolic name given to some known or unknown quantity or information, for the purpose of allowing the name to be used independently of the information it represents...
or
abstract data typeIn computing, an abstract data type is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics...
that provides a simple but useful abstraction for controlling access by multiple
processesIn computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
to a common resource in a
parallel programmingParallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
environment.
A useful way to think of a semaphore is as a record of how many units of a particular resource are available, coupled with operations to
safely (i.e. without race conditions) adjust that record as units are required or become free, and if necessary wait until a unit of the resource becomes available. Semaphores are a useful tool in the prevention of race conditions and
deadlockA deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
s; however, their use is by no means a guarantee that a program is free from these problems. Semaphores which allow an arbitrary resource count are called
counting semaphores, while semaphores which are restricted to the values 0 and 1(or locked/unlocked, unavailable/available) are called
binary- Mathematics :* Binary numeral system, a representation for numbers using only two digits * Binary function, a function in mathematics that takes two arguments- Computing :* Binary file, composed of something other than human-readable text...
semaphores (same functionality that mutexes have).
The semaphore concept was invented by
DutchThe Dutch people are an ethnic group native to the Netherlands. They share a common culture and speak the Dutch language. Dutch people and their descendants are found in migrant communities worldwide, notably in Suriname, Chile, Brazil, Canada, Australia, South Africa, New Zealand, and the United...
computer scientistA computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
Edsger DijkstraEdsger Wybe Dijkstra ; ) was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.Shortly before his...
, and the concept has found widespread use in a variety of
operating systemAn operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
s.
Library analogy
Suppose a library has 10 identical study rooms, intended to be used by one student at a time. To prevent disputes, students must request a room from the front counter if they wish to make use of a study room. When a student has finished using a room, the student must return to the counter and indicate that one room has become free. If no rooms are free, students wait at the counter until someone relinquishes a room.
The librarian at the front desk does not keep track of which room is occupied, only the number of free rooms available. When a student requests a room, the librarian decreases this number. When a student releases a room, the librarian increases this number. Once access to a room is granted, the room can be used for as long as desired, and so it is not possible to book rooms ahead of time.
In this scenario the front desk represents a semaphore, the rooms are the resources, and the students represent processes. The value of the semaphore in this scenario is initially 10. When a student requests a room he or she is granted access and the value of the semaphore is changed to 9. After the next student comes, it drops to 8, then 7 and so on. If someone requests a room when it is 0, they are forced to wait. When multiple people are waiting, they will either wait in a queue, or use
Round-robin schedulingRound-robin is one of the simplest scheduling algorithms for processes in an operating system. As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority . Round-robin scheduling is simple, easy to...
and race back to the counter when someone releases a room (depending on the nature of the semaphore).
Important observations
When used for a pool of resources, a semaphore does not keep track of which of the resources are free, only how many there are. Some other mechanism (possibly involving more semaphores) may be required to select a particular free resource.
Processes are trusted to follow the protocol. Fairness and safety are likely to be compromised (which practically means a program may behave slowly, act erratically,
hangIn computing, a hang or freeze occurs when either a single computer program, or the whole system ceases to respond to inputs. In the most commonly encountered scenario, a workstation with a graphical user interface, all windows belonging to the frozen program become static, and though the mouse...
or
crashA crash in computing is a condition where a computer or a program, either an application or part of the operating system, ceases to function properly, often exiting after encountering errors. Often the offending program may appear to freeze or hang until a crash reporting service documents...
) if even a single process acts incorrectly. This includes:
- requesting a resource and forgetting to release it
- releasing a resource that was never requested
- holding a resource for a long time without needing it
- using a resource without requesting it first.
Even if all processes follow these rules,
multi-resource deadlock may still occur when there are different resources managed by different semaphores and when processes need to use more than one resource at a time, as illustrated by the
dining philosophers problemIn computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them....
.
Semantics and implementation
One important property of these semaphore variables is that their value cannot be changed except by using the wait and signal functions.
Counting semaphores are equipped with two operations, historically denoted as
V (also known as signal) and
P (or wait)(see below). Operation
V incrementAn increment is an increase of some amount, either fixed or variable. For example one's salary may have a fixed annual increment or one based on a percentage of its current value...
s the semaphore
S, and operation
P decrements it. The semantics of these operations is shown below. Square brackets are used to indicate atomic operations, i.e., operations which appear indivisible from the perspective of other processes.
The value of the semaphore
S is the number of units of the resource that are currently available. The
P operation
wastes timeIn software engineering, busy-waiting or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input is available, or if a lock is available. Spinning can also be used to generate an arbitrary time delay, a technique that was necessary...
or
sleepsA computer program may sleep, which places it into an inactive state for a period of time. Eventually the expiration of an interval timer, or the receipt of a signal or interrupt causes the program to resume execution.- Usage :...
until a resource protected 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.
Many operating systems provide efficient semaphore primitives which mean that one waiting process is awoken when the semaphore is free. This means that processes do not waste time checking the semaphore value unnecessarily.
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
UNIXUnix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
. The modified
V and
P operations are as follows:
A simple way to understand wait and signal operations is:
wait: It decrements the value of semaphore variable by 1. If the value becomes negative the process executing wait is blocked, i.e., added to the semaphore's queue.
signal: It increments the value of semaphore variable by 1. After the increment if the value is negative, it transfers a blocked process from the semaphore's queue to the ready queue.
function V(semaphore S, integer I):
[S ← S + I]
function P(semaphore S, integer I):
repeat:
[
if S >= I:
S ← S - I
break]
To avoid
starvationIn computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task....
, a semaphore has an associated queue of processes (usually a
first-in, first outFIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...
). 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.
If the implementation does not ensure atomicity of the increment, decrement and comparison operations, then there is a risk of increments or decrements being forgotten, or of the semaphore value becoming negative. Atomicity may be achieved by using a machine instruction that is able to
read, modify and writeIn computer science, read-modify-write is a class of atomic operations such as test-and-set, fetch-and-add, and compare-and-swap which both read a memory location and write a new value into it simultaneously, either with a completely new value or some function of the previous value. These...
the semaphore in a single operation. In the absence of such a hardware instruction, an atomic operation may be synthesized through the use of a software mutual exclusion algorithm. On
uniprocessorA uniprocessor system is a computer system with a single central processing unit. As more and more computers employ multiprocessing architectures, such as SMP and MPP, the term is used to refer to systems that still have only one CPU. Most desktop computers are now shipped with multiprocessing...
systems, atomic operations can be ensured by temporarily suspending
preemptionIn computing, preemption is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation, and with the intention of resuming the task at a later time. Such a change is known as a context switch...
or disabling hardware
interruptIn computing, an interrupt is an asynchronous signal indicating the need for attention or a synchronous event in software indicating the need for a change in execution....
s. This approach does not work on multiprocessor systems where it is possible for two programs sharing a semaphore to run on different processors at the same time. To solve this problem in a multiprocessor system a locking variable can be used to control access to the semaphore. The locking variable is manipulated using a
test-and-set-lockIn computer science, the test-and-set instruction is an instruction used to write to a memory location and return its old value as a single atomic operation. If multiple processes may access the same memory, and if a process is currently performing a test-and-set, no other process may begin...
(TSL) command.
Example: Producer/consumer problem
In the
Producer-consumer problemIn problem is a classical example of a multi-process synchronization problem. The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer used as a queue. The producer's job is to generate a piece of data, put it into the buffer and start again...
, one process (the producer) generates data items and another process (the consumer) receives and uses them. They communicate using a queue of maximum size N. Obviously the consumer has to wait for the producer to produce something if the queue is empty. Perhaps more subtly, the producer has to wait for the consumer to consume something if the buffer is full.
The problem is easily solved if we model the queue as a series of boxes which are either
empty or
full, and regard empty boxes as one type of resource and full boxes as another type of resource. The producer "removes" an empty box and then "creates" a full one, whilst the consumer does the reverse.
Given that
emptyCount and
fullCount are counting semaphores, and
emptyCount is initially N whilst
fullCount is initially 0, the producer does the following repeatedly:
produce:
P(emptyCount)
putItemIntoQueue(item)
V(fullCount)
The consumer does the following repeatedly:
consume:
P(fullCount)
item ← getItemFromQueue
V(emptyCount)
Typically, either fullCount or emptyCount is set to 1, with the other set to 0. The producer or consumer that goes first will decrement the P value to 0, and after its critical section, it will increment the V value to 1. On the second iteration, it will block on the P, since it set it to 0 after grabbing it the first time, and the other process will run, releasing the first in the same way once it hits the V command at the end.
It is important to note that the order of operations is essential. For example, if the producer places the item in the queue
after incrementing fullCount, the consumer may obtain the item before it has been written. If the producer places the item in the queue
before decrementing emptyCount, the producer might exceed the size limit of the queue.
Function name etymology
The canonical names
P and
V come from the initials of
DutchDutch is a West Germanic language and the native language of the majority of the population of the Netherlands, Belgium, and Suriname, the three member states of the Dutch Language Union. Most speakers live in the European Union, where it is a first language for about 23 million and a second...
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 portmanteau
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 68ALGOL 68 isan imperative computerprogramming language that was conceived as a successor to theALGOL 60 programming language, designed with the goal of a...
, the
Linux kernelThe Linux kernel is an operating system kernel used by the Linux family of Unix-like operating systems. It is one of the most prominent examples of free and open source software....
, 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
JavaJava is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
library uses), or
pend and
post. Some texts call them
procure and
vacate to match the original Dutch initials.
Semaphore vs. mutex
A mutex is essentially the same thing as a binary semaphore, and sometimes uses the same basic implementation. However, the term "mutex" is used to describe a construct which prevents two processes from executing the same piece of code, or accessing the same data, at the same time. The term "binary semaphore" is used to describe a construct which limits access to a single resource.
In many cases a mutex has a concept of an "owner": the process which locked the mutex is the only process allowed to unlock it. In contrast, semaphores generally do not have this restriction, something the producer-consumer example above depends upon.
See also
- Cigarette smokers problem
The cigarette smokers problem is a concurrency problem in computer science, originally described in 1971 by S. S. Patil.-Problem description:Assume a cigarette requires three ingredients to smoke:#Tobacco#Paper#A match...
- Dining philosophers problem
In computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them....
- Readers-writers problem
In computer science, the first and second readers-writers problems are examples of a common computing problem in concurrency. The two problems deal with situations in which many threads must access the same shared memory at one time, some reading and some writing, with the natural constraint that...
- Sleeping barber problem
In computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes...
- Producers-consumers problem
- Mutex
- Reentrant mutex
A reentrant mutex is a mutual exclusion mechanism. In a reentrant mutex, the same thread can acquire the lock multiple times. However, the lock must be released the same number of times or else other threads will be unable to acquire the lock....
, which can "count" but in a different manner to a counting semaphore.
- Asynchronous semaphore
Asynchronous Semaphore is a structure that is being used in asynchronous programming models.It's goal is to lock an action to run only after other asynchronous actions have been executed....
External links
, Dijkstra introduces the concept (in Dutch)