Spring 2005


  • Professor: Allen Downey,, Olin Center 359, x2558.

  • Class time: Monday and Thursday, 1:00 to 1:50 pm.

  • Textbook, The Little Book of Semaphores, by Allen Downey. I will be handing out this book a few pages at a time. You will need a three-ring binder.

  • Web page: The class web page is at On campus, it can be abbreviated wb/sync.

  • Class mailing list:


Synchronization covers techniques for coordinating concurrent threads. At least the first half of the class will focus on a series of synchronization puzzles for which students will write solutions. We may also write concurrent programs that implement these solutions.

Initially, we will focus on semaphores, a software tool used to control interactions among threads that access shared data structures. As a simple example, semaphores can enforce mutual exclusion, which means that only one thread can access the data at a time.

We will discuss and solve a range of classical synchronization problems, and some not-so-classical problems, like the Baboon Crossing and the Unisex Bathroom. In addition, students will be asked to invent new problems.

The prerequisite for the class is Software Design or intermediate programming skill.


The following are the topics we will start with. We may add additional topics depending on student interest and time.

  1. Synchronization with message-passing.

  2. Semaphores.

  3. Basic synchronization patterns.

  4. Classical synchronization problems.

  5. Not-so-classical synchronization problems.

  6. Condition variables.

  7. Pthreads.