
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.
Additional resources at Green Tea Press.
- Preface
- Introduction
- Synchronization
- Execution model
- Serialization with messages
- Non-determinism
- Shared variables
- Concurrent writes
- Concurrent updates
- Mutual exclusion with messages
- Semaphores
- Definition
- Syntax
- Why semaphores?
- Basic synchronization patterns
- Signaling
- Rendezvous
- Rendezvous hint
- Rendezvous solution
- Deadlock #1
- Mutex
- Mutual exclusion hint
- Mutual exclusion solution
- Multiplex
- Multiplex solution
- Barrier
- Barrier hint
- Barrier non-solution
- Deadlock #2
- Barrier solution
- Deadlock #3
- Reusable barrier
- Reusable barrier non-solution #1
- Reusable barrier problem #1
- Reusable barrier non-solution #2
- Reusable barrier hint
- Reusable barrier solution
- Preloaded turnstile
- Barrier objects
- Queue
- Queue hint
- Queue solution
- Exclusive queue hint
- Exclusive queue solution
- Fifo queue
- Fifo queue hint
- Fifo queue solution
- Classical synchronization problems
- Producer-consumer problem
- Producer-consumer hint
- Producer-consumer solution
- Deadlock #4
- Producer-consumer with a finite buffer
- Finite buffer producer-consumer hint
- Finite buffer producer-consumer solution
- Readers-writers problem
- Readers-writers hint
- Readers-writers solution
- Starvation
- No-starve readers-writers hint
- No-starve readers-writers solution
- Writer-priority readers-writers hint
- Writer-priority readers-writers solution
- No-starve mutex
- No-starve mutex hint
- No-starve mutex solution
- Dining philosophers
- Deadlock #5
- Dining philosophers hint #1
- Dining philosophers solution #1
- Dining philosopher's solution #2
- Tanenbaum's solution
- Starving Tanenbaums
- Cigarette smokers problem
- Deadlock #6
- Smokers problem hint
- Smoker problem solution
- Generalized Smokers Problem
- Generalized Smokers Problem Hint
- Generalized Smokers Problem Solution
- Producer-consumer problem
- Less classical synchronization problems
- The dining savages problem
- Dining Savages hint
- Dining Savages solution
- The barbershop problem
- Barbershop hint
- Barbershop solution
- Hilzer's Barbershop problem
- Hilzer's barbershop hint
- Hilzer's barbershop solution
- The Santa Claus problem
- Santa problem hint
- Santa problem solution
- Building H2O
- H2O hint
- H2O solution
- River crossing problem
- River crossing hint
- River crossing solution
- The roller coaster problem
- Roller Coaster hint
- Roller Coaster solution
- Multi-car Roller Coaster problem
- Multi-car Roller Coaster hint
- Multi-car Roller Coaster solution
- The dining savages problem
- Not-so-classical problems
- The search-insert-delete problem
- Search-Insert-Delete hint
- Search-Insert-Delete solution
- The unisex bathroom problem
- Unisex bathroom hint
- Unisex bathroom solution
- No-starve unisex bathroom problem
- No-starve unisex bathroom solution
- Baboon crossing problem
- The Modus Hall Problem
- Modus Hall problem hint
- Modus Hall problem solution
- The search-insert-delete problem
- Not remotely classical problems
- The sushi bar problem
- Sushi bar hint
- Sushi bar non-solution
- Sushi bar non-solution
- Sushi bar solution #1
- Sushi bar solution #2
- The child care problem
- Child care hint
- Child care non-solution
- Child care solution
- Extended child care problem
- Extended child care hint
- Extended child care solution
- The room party problem
- Room party hint
- Room party solution
- The Senate Bus problem
- Bus problem hint
- Bus problem solution #1
- Bus problem solution #2
- The Faneuil Hall problem
- Faneuil Hall Problem Hint
- Faneuil Hall problem solution
- Extended Faneuil Hall Problem Hint
- Extended Faneuil Hall problem solution
- Dining Hall problem
- Dining Hall problem hint
- Dining Hall problem solution
- Extended Dining Hall problem
- Extended Dining Hall problem hint
- Extended Dining Hall problem solution
- The sushi bar problem
- Synchronization in Python
- Mutex checker problem
- Mutex checker hint
- Mutex checker solution
- The coke machine problem
- Coke machine hint
- Coke machine solution
- Mutex checker problem
- Synchronization in C
- Mutual exclusion
- Parent code
- Child code
- Synchronization errors
- Mutual exclusion hint
- Mutual exclusion solution
- Make your own semaphores
- Semaphore implementation hint
- Semaphore implementation
- Semaphore implementation detail
- Mutual exclusion
- Cleaning up Python threads
- Semaphore methods
- Creating threads
- Handling keyboard interrupts
- Cleaning up POSIX threads
- Compiling Pthread code
- Creating threads
- Joining threads
- Semaphores
Free Machine Learning Books
11 Books
- Pattern Recognition and Machine Learning (Information Science and Statistics)
- by Christopher M. Bishop
- Data mining
- by I. H. Witten
- The Elements of Statistical Learning: Data Mining, Inference, and Prediction
- by Various
Free Chemistry Textbooks
9 Books
- CK-12 Chemistry
- by Various
- Concept Development Studies in Chemistry
- by John Hutchinson
- An Introduction to Chemistry - Atoms First
- by Mark Bishop
Free Mathematics Textbooks
21 Books
- Microsoft Word - How to Use Advanced Algebra II.doc
- by Jonathan Emmons
- Advanced Algebra II: Activities and Homework
- by Kenny Felder
- de2de
- by
Free Children Books
38 Books
- The Sun Who Lost His Way
- by
- Tania is a Detective
- by Kanika G
- Firenze_s-Light
- by
Free Java Books
10 Books
- Java 3D Programming
- by Daniel Selman
- The Java EE 6 Tutorial
- by Oracle Corporation
- JavaKid811
- by
- Jamaica Primary Social Studies 2nd Edition Student's Book 4
- by Eulie Mantock, Trineta Fendall, Clare Eastland
- Reggae Readers Student's Book 1
- by Louis Fidge
- Reggae Readers Student's Book 2
- by Louis Fidge