Free

The Little Book of SEMAPHORES (2nd Edition)

By Allen B. Downey

Free

Read Now

Description Table of Contents Reviews Comments

Book Description

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.

Table of Contents

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
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
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
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
Synchronization in Python
- Mutex checker problem
  - Mutex checker hint
  - Mutex checker solution
- The coke machine problem
  - Coke machine hint
  - Coke machine solution
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
Cleaning up Python threads
- Semaphore methods
- Creating threads
- Handling keyboard interrupts
Cleaning up POSIX threads
- Compiling Pthread code
- Creating threads
- Joining threads
- Semaphores