QuickEmbeddedTips

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:
  • The counter of S is positive
    
    
    In this case, the counter is decreased by 1 and the thread
    resumes its execution.
  • 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:
  • The queue of S has no waiting thread
    
    
    The counter of S is increased by one and the
    thread resumes its execution.
  • 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.