Semaphore (programming)
Encyclopedia
In computer science, a semaphore is a variable
or abstract data type
that provides a simple but useful abstraction for controlling access by multiple processes
to a common resource in a parallel programming
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 deadlock
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
semaphores (same functionality that mutexes have).
The semaphore concept was invented by Dutch
computer scientist
Edsger Dijkstra
, and the concept has found widespread use in a variety of operating system
s.
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 scheduling
and race back to the counter when someone releases a room (depending on the nature of the semaphore).
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, hang
or crash
) if even a single process acts incorrectly. This includes:
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 problem
.
Counting semaphores are equipped with two operations, historically denoted as V (also known as signal) and P (or wait)(see below). Operation V increment
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 time
or sleeps
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 UNIX
. 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 starvation
, a semaphore has 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.
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 write
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 uniprocessor
systems, atomic operations can be ensured by temporarily suspending preemption
or disabling hardware interrupt
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-lock
(TSL) command.
, 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
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.
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 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.
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.
Variable (programming)
In 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 type
Abstract data type
In 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 processes
Process (computing)
In 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 programming
Parallel computing
Parallel 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 deadlock
Deadlock
A 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
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 Dutch
Dutch people
The 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 scientist
Computer scientist
A 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 Dijkstra
Edsger Dijkstra
Edsger 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 system
Operating system
An 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 scheduling
Round-robin scheduling
Round-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, hang
Hang (computing)
In 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 crash
Crash (computing)
A 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 problem
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....
.
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 increment
Increment
An 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 time
Busy waiting
In 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 sleeps
Sleep (operating system)
A 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 UNIX
Unix
Unix 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 starvation
Resource starvation
In 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 out
FIFO
FIFO 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 write
Read-modify-write
In 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 uniprocessor
Uniprocessor
A 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 preemption
Preemption (computing)
In 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 interrupt
Interrupt
In 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-lock
Test-and-set
In 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 problemProducer-consumer problem
In 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 language
Dutch 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 68
ALGOL 68
ALGOL 68 isan imperative computerprogramming language that was conceived as a successor to theALGOL 60 programming language, designed with the goal of a...
, the Linux kernel
Linux kernel
The 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 Java
Java (programming language)
Java 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 problemCigarette smokers problemThe 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 problemDining 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....
- Readers-writers problemReaders-writers problemIn 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 problemSleeping barber problemIn 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 mutexReentrant mutexA 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 semaphoreAsynchronous semaphoreAsynchronous 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)- semaphore.h programming interface - The Open Group Base Specifications Issue 6, IEEE Std 1003.1
- The Little Book of Semaphores Allen B. Downey
- A pragmatic, historically oriented survey on the universality of synchronization primitives, Jouni Leppäjärvi