Synchronizing Access to Shared Objects - Operating Systems: Principles and Practice - page 210

Semaphores considered harmful

During system conception it transpired that we used the semaphores in two
completely different ways. The difference is so marked that, looking back,
one wonders whether it was really fair to present the two ways as uses of
the very same primitives. On the one hand, we have the semaphores used
for mutual exclusion, on the other hand, the private semaphores.
(From Dijkstra “The structure of the 'THE'-Multiprogramming System” Com-
munications of the ACM v. 11 n. 5 May 1968.)

In this topic we focus on constructing shared objects using locks and condition vari-
ables for synchronization. Another widely used type of synchronization variable is a

semaphore.
Semaphores were introduced by Dijkstra to provide synchronization in the THE op-
erating system, which (among other advances) explored structured ways of using con-
currency in operating system design.
Semaphores are defined as follows:

A semaphore has a non-negative value
When a semaphore is created, value can be set to any non-negative integer
Semaphore::P() waits until value is positive. When value is positive, it atomically
decrements value by 1.
Semaphore::V() increments the value by 1, and if any threads are waiting in P() ,
one such thread is atomically enabled with its call to P() succeeding in decre-
menting the value and returning.

Note that P() is an atomic operation—the read that observes the positive value is
atomic with the update that decrements it. Also note that if V() enables a thread in P() ,
then P() 's increment and V() 's decrement of value are atomic—no other thread can
observe the incremented value, and the thread in P() is guaranteed to decrement the
value and return.
The names P() and V() are historical artifacts. Sorry.
Given this definition, semaphores can be used for either mutual exclusion (like locks)
or waiting for another thread to do something (like condition variables.)
To use a semaphore like a mutual exclusion lock, initialize it to 1. Then Semaphore::P()
is equivalent to Lock::acquire() and Semaphore::V() is equivalent to Lock::release() .
Using a semaphore for more general waiting is trickier. Normally (but not always),
you initialize the semaphore to 0. Then Semaphore::V() is similar to Cond::wait(&lock)
and Semaphore::P() is similar to Cond::signal() . However, there are important differ-
ences. First, Cond::Wait(&lock) atomically releases a lock, so you can check a shared
object's state while holding the lock and then atomically suspend execution; conversely
Semaphore::V() does not release an associated mutual exclusion lock, so you have to
carefully construct the program so that you can release the lock and then call V() with-
out allowing intervening operations to cause confusion. Second, whereas a condition
variable is stateless, a semaphore has a value , so if no threads are waiting, a call to
Cond::signal() has no effect, while a call to Semaphore::P() increments the value ,
which will cause the next call to Semaphore::V() to proceed without blocking.