Wednesday, January 12, 2011

The Little Book of Semaphores

In common use, “synchronization” means making two things happen at the
same time. In computer systems, synchronization is a little more general; it
refers to relationships among events—any number of events, and any kind of
relationship (before, during, after).
Computer programmers are often concerned with synchronization con-
straints, which are requirements pertaining to the order of events. Examples
include:
Serialization: Event A must happen before Event B.
Mutual exclusion: Events A and B must not happen at the same time.
In real life we often check and enforce synchronization constraints using a
clock. How do we know if A happened before B? If we know what time both
events occurred, we can just compare the times.
In computer systems, we often need to satisfy synchronization constraints
without the benefit of a clock, either because there is no universal clock, or
because we don’t know with fine enough resolution when events occur.
That’s what this book is about: software techniques for enforcing synchronization
constraints.

Here are just a few examples of the algorithms covered.

  • Readers-writers problem
  • Dining philosophers
  • The dining savages problem
  • The Santa Claus problem
  • Building H2O
  • The unisex bathroom problem
  • Baboon crossing problem

Read it at http://greenteapress.com/semaphores/downey08semaphores.pdf

No comments: