The Little Book of Semaphores

by Allen B. Downey

Download The Little Book of Semaphores in PDF.

The Little Book of Semaphores is a free (in both senses of the word) textbook that introduces the principles of synchronization for concurrent programming.

In most computer science curricula, synchronization is a module in an Operating Systems class. OS textbooks present a standard set of problems with a standard set of solutions, but most students don’t get a good understanding of the material or the ability to solve similar problems.

The approach of this book is to identify patterns that are useful for a variety of synchronization problems and then show how they can be assembled into solutions. After each problem, the book offers a hint before showing a solution, giving students a better chance of discovering solutions on their own.

The book covers the classical problems, including “Readers-writers,” “Producer-consumer”, and “Dining Philosophers.” In addition, it collects a number of not-so-classical problems, some written by the author and some by other teachers and textbook writers. Readers are invited to create and submit new problems.

This book is available under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0), which means that you are free to copy, distribute, and modify it, as long as you attribute the work, make it available under a similar license, and don’t use it for commercial purposes.

The LaTeX source and supporting code are in this GitHub repository. See the instructions there to install and run Sync, the thread simulator that runs the code in the book.

Example code

threading_cleanup.py
counter.py
counter_mutex.py
coke.py
counter.c
counter_mutex.c
semaphore.c