"Semaphore: An apparatus for conveying information…any of various devices for signaling by changing the position of a light, flag, etc."
The Random House Compact Unabridged Dictionary, Second edition (ISBN 0-679-4499-8)
The dictionary includes a picture of a railroad semaphore, which communicates by moving its arms to different positions: horizontal for stop, at an angle for go. If two trains approach a switch, only one will be allowed to pass. The second will wait. When the first train passes the semaphore, it will be reset so that the second train may go.
A semaphore in a computer system serves an analogous purpose. It is used as a gatekeeper to allow only one process or thread to enter a critical region at a time. A critical region is a section of code that only one process or thread may execute at a time. Languages with built-in multi-threading, such as Java, provide mutual exclusion semaphores as a synchronization mechanism. The operating system typically uses semaphores to protect its critical regions, such as process control blocks. Database servers use them to protect shared structures.
The classic semaphore was invented by Dijkstra. He described the semaphore as an object that provides two operations, known as
and P
. V
stands for the Dutch word Proberen,to test and P
stands for Verhogen, to increment. V
is used to get access to the protected resource. P
is used to give up access. The specific uses for V
and P
depend on the type of semaphore. V
There are two basic uses of semaphores in systems. The first is to protect a critical region, and the second is to share resources.
A semaphore provides exclusive use when it prevents two or more processes or threads from accessing the same data simultaneously. An activity uses the
operation when it wants to access the resource and the P
operation when it is done accessing the resource. V
Such a critical region of code might be one that supports table access and update, whenever there is more than one process or thread that can access the table at a time. This would be true, for example, for an operating system and its list of process control blocks (PCBs). Various threads in the operating system kernel may have access to the PCBs, but only one of them may update the list pointers at a time, or the semantics of the list will be violated.
A producer-consumer semaphore can be used to regulate the flow of data between n producers and m consumers. Many systems or sub-systems have the architecture of a data-flow system: the output from one stage becomes the input to another stage. Each stage waits until data is available, gets the data, and processes it. The result is the output data for the next stage. Database systems are often organized using such a data flow architecture. Semaphores can be used to regulate the flow of data: consumers issue
operations when they want to receive data, and producers issue P
operations when they make data available.V
Classically, semaphores were implemented with a global data structure and an API for the
and P
operations. These days, semaphores are encapsulated within objects. Typically, an abstract semaphore class defines the basic V
and P
operations. Exclusive and shared semaphores are derived from this base semaphore class. An exclusive or shared semaphore can be named or can be created as an anonymous semaphore. Named semaphores can be shared across processes — so that a client and a server can both access the same semaphore. Anonymous semaphores are named as variables within your application, but that name is not visible to any other process.V
The pseudo-code shown below sketches an
class. The semaphore is not aware of the region that it is protecting. It is passed a reference to the entity that wants to use the region, and either grants access or suspends the entity until access can be granted.ExclusiveSemaphore
Ignoring inheritance from the base semaphore class, the
class may be defined as:ExclusiveSemaphore
class ExclusiveSemaphore
{
Public:
ExclusiveSemaphore();
~ExclusiveSemaphore();
// get access to semaphore or add caller to list of waiting entities
P(Entity e);
// give up access to semaphore
V(Entity e);
private:
// if in use, who has access
Entity* owner;
// list of waiting entities (list used for illustrative purposes)
Entity* entityListHead;
};
The
operation examines the semaphore. If the semaphore is free, access is granted to the entity. If not, the operation suspends the entity and adds it to the list of entities waiting for the semaphore.P
void ExclusiveSemaphore::P(Entity e)
{
// examine the list of waiting entities;
// if semaphore is free, set owner to this entity and return;
// otherwise add entity to end of list and put entity to sleep;
}
void ExclusiveSemaphore::V(Entity e)
{
// in one atomic step: clear owner data member;
// if no entity waiting, return;
// remove first waiting entity, set owner to this entity;
// wakeup entity;
}
The
and P
operations are passed a reference to the calling entity. The V
operation suspends the entity until it is granted access to the region. An atomic procedure, or machine instruction, is used to set the list of waiting entities and the owner.P
An atomic instruction is indivisible, that is it cannot be interrupted. Such operations are normally supported through hardware — the CPU instruction set.
This next example of pseudo-code demonstrates a class,
, which can be used to grant access to one writer or many readers of the resource. This is similar, for example, to the semaphores that are used for locking database pages. SharedSemaphore
Shared semaphores keep a list of waiting entities and a count of the number of entities that have been granted the semaphore (for an exclusive semaphore, this is always one). They also have a mode, which can take the values
, free
or shared
.exclusive
class SharedSemaphore
{
public:
enum SemaphoreMode {free, shared, exclusive};
SharedSemaphore();
~SharedSemaphore();
// get access to semaphore or add caller to list of waiting entities
P(Entity e, Semaphore Mode m);
// give up access to semaphore
V(Entity e);
private:
SemaphoreMode mode;
// if in use, how many entities are using it
unsigned int numberOfOwners;
// list of waiting entities (list used for illustrative purposes)
Entity* entityListHead;
};
The pointer to the
is used to wake up those entities waiting on the semaphore. In the entityListHead
there is a member pointer ExclusiveSemaphore
, which is used as a flag to indicate whether or not the semaphore is free (e.g. if the pointer is null, the semaphore is free). The owner
may have more than one owner, so we keep a count of the SharedSemaphore
, but there is no need for the numberOfOwners
pointer. owner
The
and P
operations are passed a reference to the calling entity. The V
operation is also passed the mode that is requested. The semaphore is granted if it is either unused, or in use in share mode with no waiters and the request is for share mode. Otherwise, it suspends the entity, until that entity is granted access to the region. An atomic procedure or machine instruction is used to set the list of waiting entities and the owner.P
void SharedSemaphore::P(Entity e, SemaphoreMode requestMode)
{
// if numberOfOwners = 0 increment numberOfOwners and return;
// if entityListHead = NULL AND mode = Shared AND
// requestMode = shared increment numberOfOwners and return;
// add entity to end of list and put entity to sleep;
}
void SharedSemaphore::V(Entity e)
{
// if numberOfOwners = 1 and mode = shared
// and entityListHead = NULL
// then decrement number of owners and return;
// if numberOfOwners > 1 decrement numberOfOwners and return;
// Wake up all the waiters that want shared access
}