The Little Book of SEMAPHORES (2nd Edition)

The Little Book of SEMAPHORES (2nd Edition)

By Allen B. Downey
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
    No review for this book yet, be the first to review.
      No comment for this book yet, be the first to comment
      You May Also Like
      Also Available On
      App store smallGoogle play small
      Curated Lists
      • 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
        See more...
      • CK-12 Chemistry
        by Various
        Concept Development Studies in Chemistry
        by John Hutchinson
        An Introduction to Chemistry - Atoms First
        by Mark Bishop
        See more...
      • Microsoft Word - How to Use Advanced Algebra II.doc
        by Jonathan Emmons
        Advanced Algebra II: Activities and Homework
        by Kenny Felder
        See more...
      • The Sun Who Lost His Way
        Tania is a Detective
        by Kanika G
        See more...
      • Java 3D Programming
        by Daniel Selman
        The Java EE 6 Tutorial
        by Oracle Corporation
        See more...