Semaphores

As we know now1, one needs both locks and condition variables to solve a broad range of relevant and interesting concurrency prob-lems. One of the first people to realize this years ago was Edsger Di-jkstra (though it is hard to know the exact history [GR92]), known among other things for his famous “shortest paths ” algorithm in graph theory [D59], an early polemic on structured programming en-titled “Goto Statements Considered Harmful ” [D68a] (what a great title!), and, in the case we will study here, the introduction of a pow-erful and flexible synchronization primitive known as the semaphore [D68b,D72]. Indeed, he invented this general semaphore as a single primitive for all things related to synchronization; as you will see, one can use semaphores as both locks and condition variables. THE CRUX: HOW TO USE SEMAPHORES How can we use semaphores instead of locks and condition vari-ables? What is the definition of a semaphore? What is a binary semaphore? Is it straightforward to build a semaphore out of locks and condition variables? What about building locks and condition variables out of semaphores? 1That is, assuming “we”, which is actually “you”, have been reading and paying attention to the previous chapters. And even remembering a few things. You have, right?!