Semaphores Intro

Semaphores, another important contribution by E. W. Dijkstra,
can be viewed as an extension to mutex locks. A semaphore is an object
with two methods Wait and Signal, a private integer counter and a
private queue (of threads). The semantics of a semaphore is very simple.
Suppose S is a semaphore whose private counter has been
initialized to a non-negative integer.

* When Wait is executed by a thread, we have two possibilities:
o The counter of S is positive


In this case, the counter is decreased by 1 and the thread
resumes its execution.
o The counter of S is zero


In this case, the thread is suspended and put into the
private queue of S.
* When Signal is executed by a thread, we also have two
possibilities:
o The queue of S has no waiting thread


The counter of S is increased by one and the
thread resumes its execution.
o The queue of S has waiting threads


In this case, the counter of S must be zero
(see the discussion of Wait above). One of the
waiting threads will be allowed to leave the queue and
resume its execution. The thread that executes
Signal also continues.

The operations of Wait or Signal are
atomic. This means once the
activities of Wait start (i.e., testing and decreasing the value
of the counter and putting the thread into the queue), they will continue
to the end without
any interruption. More precisely, even though there are many steps to
carry out Wait and Signal, these steps are considered as
a single non-interruptible instruction. Similarly, the same applies to
Signal. Moreover, if more than one threads try to execute Wait (or
Signal), only one of them will succeed.
We should not make any assumption about which thread
will succeed.