next up previous
Next: Implementation Up: Process Coordination Previous: Busy Waiting

Semaphores

An abstract entity (not provided by hardware)

Named by a unique semaphore id.

Consists of a tuple (count, queue), where count is an integer and queue is a list of processes. The following invariant is true for semaphores: a nonnegative count means that the queue is empty; a semaphore count of negative n means that the queue contains n waiting processes.

Associated with four operations, which are described below.

The four operations are:

Wait: decrements count, and enqueues process if count is negative.

Signal: increments count and make a process ready if waiting.

Create: generates a new semaphore.

Delete: destroys an existing semaphore.

The last two operations are non-standard and allow semaphores to be created and destroyed dynamically.




Prasun Dewan
Tue Feb 24 14:38:40 EST 2004