BSCS students who find synchronization the hardest part of their Operating Systems course can use this guide to study The Little Book of Semaphores by Allen B. Downey, published free by Green Tea Press. This page covers the Second Edition, Version 2.2.2, which the official site and source repository list as last updated on 7 October 2026.
It is not a theory text. It is a workbook of synchronization puzzles: it defines the semaphore in two short chapters, builds a toolbox of basic patterns such as signaling, rendezvous, mutex and barrier, then sets the classical problems (producer-consumer, readers-writers, dining philosophers) and many harder ones. Every puzzle is followed by a hint and then a solution, so you can try before you look. The examples use Python-like pseudocode, with real Python and C in later chapters. If your exams ask you to design a solution with semaphores, this is the practice material.
Book Overview
| Course | Operating Systems (Concurrency and Synchronization) |
| Degree Programs | BSCS |
| Level | University / Undergraduate |
| Edition | Second Edition, Version 2.2.2 (last updated 7 October 2026) |
| Author | Allen B. Downey |
| Publisher | Green Tea Press |
| Structure | 9 chapters and 2 appendices, plus a preface |
| Exercises | Synchronization puzzles, each followed by a hint and a solution |
| Language | English |
| Code | Python-like pseudocode; real Python in Chapter 8 and C in Chapter 9 |
| License | Creative Commons BY-NC-SA 4.0 International (copyright 2016 Allen B. Downey) |
| Format | Free PDF; LaTeX source and the Sync thread simulator on GitHub |
Chapter List
Chapter 1: Introduction
Difficulty: Easy · Key topics: synchronization constraints, serialization, mutual exclusion, concurrent events, non-determinism, execution paths, shared variables, atomic operations
The opening chapter builds the vocabulary before any semaphore appears. A synchronization constraint is a rule about the order of events, and the two basic kinds are serialization (A before B) and mutual exclusion (A and B never together). Downey uses a lunch with a friend called Bob to show why events in different threads cannot be compared, and why a phone call can fix the order. He then shows that concurrent programs are non-deterministic, works through concurrent writes and concurrent updates of a shared variable, and explains why count = count + 1 is really a read followed by a write.
Key Points:
- A synchronization constraint is a requirement about the order of events; the two basic kinds are serialization and mutual exclusion.
- Two events are concurrent if you cannot tell by looking at the program which will happen first.
- Parallel processors and multiple threads on one processor raise the same problem, because the scheduler decides when each thread runs.
- A non-deterministic program can work 1000 times and fail on the 1001st run, so testing alone rarely finds these bugs.
- An execution path is one particular order of statements; the core skill is working out which paths are possible and what each one produces.
- An update such as
count = count + 1is a read followed by a write; an operation that cannot be interrupted is called atomic. - The safe assumption is that every write and update is not atomic, so shared variables need explicit constraints such as mutual exclusion.
Practice Tip: Write two threads that each run temp = count then count = temp + 1 many times, and force a switch between the two lines with time.sleep(0). The final total comes out far below the expected value, which makes the lost-update path from this chapter visible on your own screen.
Common Mistake: Believing a program is correct because it passed many test runs. With concurrency a bug can stay hidden for thousands of runs and then appear, so the argument has to come from the possible execution paths, not from testing alone.
Important Questions:
- What is the difference between serialization and mutual exclusion? Serialization means event A must happen before event B. Mutual exclusion means A and B must not happen at the same time, in either order.
- Why can two threads executing
count = count + 1give the wrong result? The statement is a read followed by a write. If both threads read the old value before either writes, both write the same new value and one increment is lost.
Chapter 2: Semaphores
Difficulty: Easy · Key topics: Dijkstra, semaphore definition, blocking and waking, meaning of the value, signal and wait, P and V, why use semaphores
This short chapter defines the one tool the rest of the book uses. A semaphore is like an integer with three differences: you choose its initial value, afterwards you may only increment or decrement it, and you can never read it. A decrement that makes the value negative blocks the thread, and an increment wakes one waiting thread if there is one. The chapter explains what the value means, lists the competing names for the two operations (increment and decrement, signal and wait, V and P), says why the book picks signal and wait, and gives three reasons to prefer semaphores.
Key Points:
- After creation the only operations on a semaphore are increment and decrement; its current value cannot be read.
- A thread that decrements the value below zero blocks until another thread increments it.
- An increment wakes one waiting thread if any; you cannot know which one, or whether the waker or the woken thread continues first.
- A positive value counts the threads that can decrement without blocking; a negative value counts the threads waiting; zero means nobody waits but the next decrement blocks.
- The operation names are increment and decrement, signal and wait, and Dijkstra’s original V and P; the book uses signal and wait.
- The book writes
Semaphore(n)to create a semaphore with initial valuen. - Semaphores impose deliberate constraints, give clean solutions that are easy to argue correct, and are efficient and portable.
Memory Tip: Picture the value as a pile of permission tokens. Wait takes a token and sleeps if the pile is empty; signal puts a token back and wakes a sleeper. A negative value is just the number of sleepers who are still owed a token.
Common Mistake: Writing code that checks the semaphore’s value before deciding whether to wait. The definition forbids reading it, and such a check would be a race anyway, because the value can change the instant after you read it.
Important Questions:
- How does a semaphore differ from an ordinary integer? You can only initialize, increment and decrement it; a decrement that makes it negative blocks the calling thread; and an increment wakes one waiting thread if any.
- What does the value of a semaphore tell you? Positive means that many threads can decrement without blocking, negative means that many threads are waiting, and zero means none are waiting but a new decrement would block.
Chapter 3: Basic Synchronization Patterns
Difficulty: Medium · Key topics: signaling, rendezvous, mutex, multiplex, barrier, turnstile, reusable barrier, queue, deadlock
This chapter builds the toolbox that every later problem draws on. It starts with signaling, where one thread tells another that something has happened, then sets the reader puzzles for a rendezvous, a mutex, a multiplex and a barrier, each with a hint. The reusable barrier takes several attempts, and the book shows why the early ones fail. The last section uses semaphores as queues to pair leaders with followers in a ballroom dance. Along the way it numbers its first deadlocks and states the lesson that blocking on a semaphore while holding a mutex is dangerous.
Key Points:
- Signaling guarantees that a statement in one thread runs before a statement in another, so it solves the serialization problem.
- A rendezvous makes two threads wait for each other; a good solution does not enforce more ordering than the problem asks for.
- A mutex lets one thread at a time into a critical section; a multiplex allows up to a fixed number
nat once. - A barrier blocks every thread until all
nhave arrived; a turnstile is a wait immediately followed by a signal, and it can be locked to bar all threads. - A barrier that is used once is easy; a barrier reused inside a loop must lock itself again, and a thread that gets a lap ahead of the others is the hazard.
- Deadlock means every thread is blocked waiting for a signal that only another blocked thread could send.
- Section 3.2, Sync.py, is only a short unfinished stub in this version of the book.
Practice Tip: Implement each pattern with Python’s threading.Semaphore, using acquire for wait and release for signal, and put a print in each statement. Run it fifty times: a wrong rendezvous or barrier eventually prints something out of order, and a correct one never does.
Common Mistake: Putting the wait before the signal in both threads of a rendezvous. Each thread then waits for a signal the other has not sent yet, and both block forever.
Important Questions:
- What is a deadlock? A situation in which threads are blocked, each waiting for an event that only another blocked thread could cause, so none of them can ever proceed.
- What is the difference between a mutex and a multiplex? A mutex allows exactly one thread in the critical section at a time. A multiplex generalizes this and allows up to
nthreads at the same time but no more.
Chapter 4: Classical Synchronization Problems
Difficulty: Hard · Key topics: producer-consumer, finite buffer, readers-writers, starvation, weak and strong semaphores, no-starve mutex, dining philosophers, cigarette smokers
This chapter covers the problems that every operating systems course names. Producer-consumer comes first with an unbounded buffer and then a finite one. Readers-writers introduces categorical mutual exclusion and shows how writers can starve. A section on thread starvation sets out four properties of schedulers and semaphores, separates weak from strong semaphores, and presents Morris’s 1979 result. Dining philosophers is posed with four explicit constraints, and the cigarette smokers problem comes in an impossible, an interesting and a trivial version, followed by Parnas’s generalization.
Key Points:
- Producers add items to a shared buffer and consumers remove them; buffer access must be exclusive and a consumer must block while the buffer is empty.
- A finite buffer adds one more constraint: a producer must block while the buffer is full.
- Readers-writers is categorical mutual exclusion: any number of readers may be inside together, but a writer needs the room to itself.
- A deadlock-free solution can still starve writers, because starvation means some threads progress while one waits indefinitely.
- A weak semaphore only guarantees that some waiting thread is woken; a strong semaphore bounds how many threads can be woken before a given waiter, for example with first-in-first-out order.
- Dijkstra conjectured that starvation-free mutual exclusion is impossible with weak semaphores alone; Morris refuted this in 1979 for a finite number of threads.
- Dining philosophers needs: one holder per fork, no deadlock, no starvation, and more than one philosopher able to eat at once.
Memory Tip: For every classical problem ask the same three questions: what must be exclusive, what must wait for what, and who could wait forever? Answering them for readers-writers (the writer is exclusive, the writer waits for an empty room, writers could wait forever) takes a minute and works on every later problem.
Common Mistake: Calling a solution correct because it never deadlocks. The book’s first readers-writers solution cannot deadlock, yet a steady stream of readers can keep a writer waiting forever, so deadlock and starvation must be checked separately.
Important Questions:
- What is the difference between deadlock and starvation? In deadlock the threads involved are all blocked and none can ever move. In starvation other threads keep making progress while one particular thread waits without bound.
- What constraints define the readers-writers problem? Any number of readers may be in the critical section at once, and a writer must have exclusive access, so no reader or other writer may be inside while it writes.
Chapter 5: Less Classical Synchronization Problems
Difficulty: Hard · Key topics: dining savages, barbershop, FIFO barbershop, Hilzer’s barbershop, Santa Claus, building H2O, river crossing, roller coaster, scoreboard pattern
Nine further puzzles, drawn mostly from Andrews, Silberschatz and Galvin, and Stallings. In dining savages a tribe eats from a pot of M servings and wakes a cook when it is empty. The barbershop appears three times: Dijkstra’s original with a small waiting room, a first-in-first-out version, and Hilzer’s shop with three barbers, a sofa and one cash register. Santa Claus, building H2O and river crossing are barrier-like puzzles that let threads pass only in certain combinations. The chapter ends with a roller coaster whose car runs only when full, then a version with several cars that must unload in boarding order.
Key Points:
- Dining savages: savages may not take a serving from an empty pot, and the cook may refill only when the pot is empty.
- A scoreboard is a set of shared counters protected by a mutex that threads inspect to decide whether to proceed or to wait.
- Barbershop: a customer who finds the shop full balks, the barber sleeps when nobody is waiting, and each
cutHairpairs with exactly onegetHairCut; the FIFO version adds service in arrival order. - Hilzer’s barbershop limits the shop to 20 customers and has three chairs, a four-seat sofa and one cash register that handles one payment at a time.
- Santa Claus: Santa is woken by all nine reindeer or by three elves, and the reindeer take priority over the elves.
- Building H2O and river crossing release threads only in complete valid groups: one oxygen with two hydrogen, or a boat of four that is never one-against-three.
- Roller coaster: the car departs only when it holds
Cpassengers; in the multi-car version, cars unload in the order they boarded.
Practice Tip: Start with the barbershop. Write the customer and barber functions as stubs that only print, add your synchronization, run many customers, and check the printed order against each constraint in the problem statement. The statement lists the constraints explicitly, so each one becomes a check.
Common Mistake: Reading a constraint list loosely. In the Santa Claus problem the last reindeer must get Santa even if three elves are already waiting, and a solution that treats elves and reindeer equally breaks that rule.
Important Questions:
- Who gets priority in the Santa Claus problem, and why? The reindeer. If Santa wakes to find all nine reindeer back and three elves at the door, he gets the sleigh ready first, because the elves can wait until after Christmas.
- What do building H2O and river crossing have in common? Both are peculiar barriers: threads may only pass in complete valid groups, and all threads of one group must act before any thread of the next group.
Chapter 6: Not-So-Classical Problems
Difficulty: Hard · Key topics: search-insert-delete, lightswitch, unisex bathroom, starvation, baboon crossing, Modus Hall, majority rule
Four problems built on categorical exclusion, each harder than readers-writers. In search-insert-delete, three kinds of thread share a linked list: searchers share it freely, inserters work one at a time alongside searchers, and deleters need it alone. The unisex bathroom allows at most three people and never men and women together, and a follow-up asks for a version in which nobody starves. Baboon crossing adds a rope with a capacity of five and no head-on meetings, and the book deliberately prints no solution. The Modus Hall problem lets the larger of two factions control a narrow path.
Key Points:
- Search-insert-delete is a three-way categorical exclusion: searches share, inserts exclude other inserts but not searches, and a delete excludes everything.
- The lightswitch idea: the first thread of a category switches the light on by locking the room, and the last one out switches it off by unlocking it.
- Unisex bathroom: never both sexes together, never more than three people, no deadlock; the first version allows starvation and the follow-up removes it.
- Baboon crossing: no head-on meetings, at most five baboons on the rope, and no starvation in either direction. The book prints no solution.
- Modus Hall: control of the path goes by majority rule, and the waiting side accumulates in a queue until it becomes the majority.
- Students using the UPPAAL model checker found errors in the author’s published solutions to the Modus Hall and room party problems.
Memory Tip: Before writing code, list the categories and say which pairs may share the room. Searchers, inserters and deleters, men and women, east-bound and west-bound baboons: that table is the whole specification, and the semaphores only enforce it.
Common Mistake: Treating a deadlock-free answer as finished. The first bathroom solution never deadlocks, but a long line of women can keep a man waiting indefinitely, and the problem statement postpones starvation only for that first version.
Important Questions:
- What is categorical mutual exclusion? A thread does not necessarily exclude other threads of its own category, but the presence of one category in the critical section excludes the other categories. Readers-writers and the bathroom problem are examples.
- What properties must a baboon crossing solution have? A baboon that has begun to cross reaches the other side without meeting one coming the other way, never more than five baboons are on the rope, and a stream in one direction cannot bar the other direction forever.
Chapter 7: Not Remotely Classical Problems
Difficulty: Hard · Key topics: sushi bar, child care, room party, Senate bus, Faneuil Hall, dining hall, pass the baton, I’ll do it for you
Seven problems written by teachers and students, most with several constraints that interact. The sushi bar has five seats, and a full bar must empty before anyone new sits. Child care requires one adult for every three children. In the room party problem the dean may enter only when the room is empty or holds more than fifty students. The Senate bus carries fifty riders and takes only those waiting when it arrives. Faneuil Hall coordinates immigrants, spectators and a judge. The last two problems say no student may ever sit alone, and some of them show a flawed first attempt before a better one.
Key Points:
- Sushi bar: five seats, and if all are taken a newcomer must wait until the whole party has left.
- Child care: at least one adult for every three children; the extended version asks for a solution where an adult who wants to leave does not block children who could legally enter.
- Room party: the dean enters only if the room is empty or has over 50 students, nobody new enters while the dean is inside, and the dean leaves last.
- Senate bus: capacity 50, riders arriving during boarding wait for the next bus, and the bus departs at once if nobody is waiting.
- Faneuil Hall: nobody enters while the judge is inside, immigrants cannot leave, and the judge confirms only after every immigrant who entered has checked in.
- Dining Hall: a student may never sit alone; the extended version adds a ready-to-eat stage between getting food and dining.
- Reek’s patterns pass the baton and I’ll do it for you appear in several of these problems.
Practice Tip: Number the constraints in the problem statement and, for each one, point to the single line of your solution that enforces it. A constraint with no line is a bug, and a line that enforces nothing is probably wasted blocking.
Common Mistake: Reading a shared counter without holding the mutex. In the dining hall, two students can both check the ready-to-leave count, both decide it is safe to go, and leave the last student sitting alone.
Important Questions:
- What rules does the dean follow in the room party problem? The dean may enter only when the room is empty or has more than 50 students; while the dean is inside no new student may enter, though students may leave; and the dean may not leave until all students have left.
- What does the Dining Hall problem forbid? A student may never be left sitting alone, meaning everyone else who invoked
dinemust not leave before she has finished dining.
Chapter 8: Synchronization in Python
Difficulty: Medium · Key topics: real Python threads, shared object, mutex checker, histogram of errors, coke machine, producers and consumers
After a book of pseudocode, this chapter runs real Python threads. A first example has two children incrementing a shared counter with no protection. The mutex checker problem builds an array and a histogram to detect lost updates: nothing goes wrong for small loops, but with 100,000 iterations many entries are incremented twice. The lesson is that errors can be rare without being random. The coke machine problem simulates two producers and two consumers on a machine with capacity ten that starts half full, and asks the reader to keep the count from going below zero or above ten.
Key Points:
- Variables declared inside a function are thread-specific; shared state is kept in a
Sharedobject (global variables are shared too). - Python’s semaphore methods are
acquireandrelease; the book’s cleanup code in Appendix A renames themwaitandsignal. - The mutex checker keeps an array of counts; if everything works, every entry is incremented exactly once.
- The run with 100,000 iterations produced a large share of doubled entries, while 10,000 showed none.
- A bug that appears one time in a million does not mean it cannot happen a million times in a row.
- Coke machine constraints: exclusive access to the count, consumers block at zero, producers block at ten.
- The code is Python 2 style (
printstatements,threading._Semaphore) and needs small changes to run on Python 3.
Practice Tip: Port the shared-counter test to Python 3 with print() and threading.Semaphore, then raise the loop limit until the histogram shows twos. Add your mutex and confirm the histogram goes back to all ones; seeing the failure first makes the fix meaningful.
Common Mistake: Concluding that code is thread-safe because a short run printed correct results. In the book’s own experiment the checker finds nothing at 10,000 iterations and a flood of errors at 100,000.
Important Questions:
- Why can an unsynchronized counter test pass for small sizes and fail for large ones? An error needs a context switch in the middle of a read-modify-write. A short run may finish without one, while a long run gets many.
- What must the coke machine program guarantee? Access to the count is mutually exclusive, consumers block when there are no cokes, and producers block when the machine already holds ten.
Chapter 9: Synchronization in C
Difficulty: Medium · Key topics: POSIX threads, shared struct, create and join threads, semaphore in C, mutexes and condition variables, building a semaphore
The same mutual exclusion problem, now in C with POSIX threads. A shared struct holds the counter, the end value and a checking array; the parent creates the children in one loop, joins them in a second, and then runs a checker. The child code appears unsynchronized and then protected, with a reminder to release before every return. The second half notes that Pthreads programs usually use mutexes and condition variables, asks the reader to build semaphores from them, and discusses why a thread must not be able to catch its own signal.
Key Points:
- The parent program has a fixed shape: create the threads in a loop, join them in a second loop, then run a checker on the shared data.
- A thread handle (
pthread_t) can be copied freely, but a semaphore cannot safely be copied, so the book handles it through pointers. - Release the semaphore before every
returnin the child code, or the other threads block forever. - The usual Pthreads tools are mutexes and condition variables; the book recommends Butenhof’s book on POSIX threads for them.
- A semaphore built from a mutex and a condition variable must still ensure that a thread cannot wake and consume its own signal.
- The chapter depends on the helper wrappers in Appendix B.
Practice Tip: Compile the unsynchronized version with gcc -g -O2 -o array array.c -lpthread and run it several times with a large end value to see the checker report errors. Then compile the protected version and compare the output.
Common Mistake: Leaving a function through an early return while still holding the mutex. The next thread then waits forever, and the program hangs without any error message.
Important Questions:
- Which synchronization tools do Pthreads programs normally use? Mutexes and condition variables. POSIX semaphores exist but are not part of Pthreads itself, so the book also shows how to build semaphores from the first two.
- What must you add to the
gcccommand to build a threaded program? You must link the Pthread library, for example with the-lpthreadoption.
Appendix A: Cleaning Up Python Threads
Appendix · Difficulty: Easy · Key topics: Semaphore subclass, signal and wait, Thread wrapper, starting threads, Ctrl-C and join
A short helper chapter for the Python examples. It subclasses Python’s semaphore so the methods are called wait and signal instead of acquire and release, which lets the code in the book run as written. Creating a thread normally takes keyword arguments and two steps, and four lines of code reduce it to one call that starts the thread at once, so a list comprehension can create many threads. The last section deals with join not being interruptible by Ctrl-C, which raises a KeyboardInterrupt in Python.
Key Points:
- The subclass simply gives the existing acquire and release methods the names wait and signal.
- The wrapper creates and starts a thread in one call, in the form
Thread(function, arg1, arg2). - A list comprehension can then create a whole group of threads in one line.
- Ctrl-C produces
SIGINT, which Python turns into aKeyboardInterrupt, butThread.joincannot be interrupted by it. - The code subclasses
threading._Semaphore, which is Python 2; on Python 3 you subclassthreading.Semaphoreinstead.
Practice Tip: Write the Python 3 version of the wrapper yourself: subclass threading.Semaphore, add the two method names, and test it by rerunning a Chapter 3 pattern unchanged.
Common Mistake: Copying the appendix code into a Python 3 interpreter and expecting it to run. The semaphore subclass and the print statements are Python 2 and fail with errors until you update them.
Important Questions:
- Why does the book wrap Python’s semaphore and thread classes? To match the signal and wait names used throughout the book, and to create and start a thread with a single, simpler call.
- What problem does Appendix A mention with
Thread.join? It cannot be interrupted by Ctrl-C, so a program waiting injoindoes not respond to the keyboard interrupt the way you would expect.
Appendix B: Cleaning Up POSIX Threads
Appendix · Difficulty: Medium · Key topics: headers, linking with Pthreads, error-checking wrappers, creating and joining threads, POSIX semaphores, sem_post
The C counterpart of Appendix A, holding the helper code behind the Chapter 9 examples. It lists the headers needed, shows how to link the Pthread library with gcc, and wraps calls such as malloc, pthread_create and pthread_join so that failures print a message and exit. It explains the unusual function pointer that a new thread starts from. The last section wraps POSIX semaphores, notes that copying one is undefined, and renames sem_post to sem_signal to match the book.
Key Points:
- The headers used are
stdio.h,stdlib.h,pthread.handsemaphore.h; link the Pthread library at compile time. - C reports errors through return codes, so the book wraps each library call in a function that checks the result.
- A new thread starts in a function that takes and returns a
voidpointer, conventionally calledentry. - The parent waits for a child by calling
pthread_joinwith the child’s handle. - POSIX semaphores have type
sem_t, are not part of Pthreads itself, and must not be copied because the behavior is undefined. - POSIX names the signal operation
sem_post; the book adds a smallsem_signalwrapper.
Practice Tip: Type in the wrapper for pthread_create and make a deliberate error, such as passing a null function pointer, to see how the wrapper reports it. You learn what the checks are for much faster than by reading them.
Common Mistake: Assigning one semaphore variable to another to share it. That copies the structure, which POSIX leaves undefined, so always pass a pointer to the single semaphore.
Important Questions:
- Why does the book wrap library calls such as
pthread_createandmalloc? C has no exceptions, so every call must be checked explicitly. A wrapper checks the result once and exits with a message on failure. - Why should you not copy a POSIX semaphore? The type has structure semantics and the standard leaves the behavior of a copy undefined, so semaphores are always manipulated through pointers.
How to Study This Book
This is a puzzle workbook, not a theory text, so read it with a pencil. The preface explains the method: after each puzzle the printed book leaves a gap so the hint falls on the next sheet and the solution on the sheet after that. In the PDF, cover everything below the problem statement with a sheet of paper, try the puzzle, and only then read the hint. If you read the solutions straight through you will understand them but not be able to produce them, which is exactly the trap the author wrote the book to avoid.
Read Chapters 1 and 2 in one sitting. They are short, they contain almost no code, and they fix the vocabulary (constraint, concurrent, atomic, blocked, signaled) that every later chapter uses without re-explaining. Do the small puzzles in Chapter 1 on paper: list the execution paths and decide which ones give which output.
Chapter 3 is the heart of the book, so give it the most time. Signaling, rendezvous, mutex, multiplex, barrier, reusable barrier and queue reappear in almost every later problem. Do not move on until you can write the barrier and the reusable barrier from memory and explain why the early attempts fail. Section 3.2 (Sync.py) is only a stub in this version, so skip it.
For exams, Chapter 4 matters most: producer-consumer, readers-writers (including the starvation discussion) and dining philosophers match what most operating systems papers ask. The no-starve mutex section is optional; the author himself says that if it is not your idea of fun you can assume strong semaphores and go straight to dining philosophers. The cigarette smokers problem is a good challenge once the rest is solid.
Chapters 5, 6 and 7 are practice, not syllabus. Pick two or three problems from each rather than all of them: the barbershop and roller coaster from Chapter 5, the unisex bathroom from Chapter 6, and the Senate bus or dining hall from Chapter 7 are good starting points. Remember that some printed solutions have been wrong (model-checking found errors in the room party and Modus Hall solutions), and that baboon crossing has no printed solution at all, so check your own answers by reasoning about every execution path.
Chapters 8 and 9 and the two appendices are about running real code. The Python in Chapter 8 and Appendix A is Python 2 style, so port print and the semaphore subclass to Python 3 as you go. The C chapter needs a Linux system (or WSL on Windows) with gcc and the Pthread library. Both chapters repeat the shared-counter experiment, which is worth running yourself.
Know what the book leaves out before you rely on it for a whole course. It covers semaphores only: there is no treatment of monitors, scheduling algorithms, deadlock detection and avoidance, or memory models, and condition variables appear only briefly in Chapter 9. Pair it with a full operating systems text for those topics.
Used In These Programs
This book is used for the synchronization and concurrency part of the Operating Systems course in: BS Computer Science · BS Software Engineering. Browse all Operating Systems books, all Concurrency books or all Computer Science books.
Who Should Read This
The Little Book of Semaphores is for BSCS students, usually in the semester where Operating Systems introduces threads, mutexes and classical synchronization problems, who can follow the lecture solutions but struggle when an exam or assignment gives them a new problem. It suits you if you want to learn to design solutions rather than memorize them, and it is excellent preparation for questions that say “use semaphores to enforce these constraints”. It also helps students heading for systems programming or interviews that ask about deadlock, starvation and thread safety. It is not a complete operating systems textbook, it covers only semaphores, and its pseudocode is Python-like rather than the C or Java your course may use. Pair it with a full text such as Operating Systems: Three Easy Pieces, which covers scheduling, memory and file systems and also has chapters on concurrency, or with the shorter Think OS, which introduces threads, condition variables and semaphores in C.
Applicable Universities
This book is useful for students at Pakistani universities offering BSCS and BS Software Engineering including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, and other HEC-recognized institutions.
Official Copy of Little Book of Semaphores
This book is free from its official source at Green Tea Press. Click below to open the official book page, where the PDF download link sits at the top. The same page links the LaTeX source, the example code and Sync, the thread simulator, on GitHub.
→ Visit Official PageFAQs
Is The Little Book of Semaphores free to download?
Yes. Allen B. Downey publishes it free through Green Tea Press under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International license. You may copy, share and adapt it with credit, for non-commercial use, and under the same license. The button on this page opens the official page.
Which edition is this, and is it still current in 2026?
It is the Second Edition, Version 2.2.2, listed on the official site and source repository as last updated on 7 October 2026. The ideas do not age, but two details do: the Python code in Chapter 8 and Appendix A is Python 2 style and needs small changes to run on Python 3, and Section 3.2 (Sync.py) is only an unfinished stub in this version.
How many chapters does it have?
Nine chapters plus a preface and two appendices: Introduction, Semaphores, Basic synchronization patterns, Classical synchronization problems, Less classical synchronization problems, Not-so-classical problems, Not remotely classical problems, Synchronization in Python and Synchronization in C. The appendices clean up Python threads and POSIX threads.
Does it include solutions to the puzzles?
Yes. Each puzzle is followed by a hint and then a solution, so you can decide how much help you want. The one exception is the baboon crossing problem, which has no printed solution. The author notes that model checking found errors in two of his own solutions, so check your own answers by reasoning too.
Do I need to know Python to read it?
Not really. The pseudocode is close to Python and the author explains any Python-specific syntax, but it is not exactly runnable Python: indentation sometimes marks code protected by a mutex, which real Python would reject. Chapter 8 uses real Python threads and Chapter 9 uses C with POSIX threads.
Is it enough for an Operating Systems course?
No. It covers synchronization with semaphores only, and covers it deeply. It has no treatment of scheduling, memory management, file systems, monitors or deadlock detection and avoidance, and condition variables appear only briefly in Chapter 9. Use it next to a full operating systems textbook.
Related Books
- Operating Systems: Three Easy Pieces – Arpaci-Dusseau
- Think OS – Allen B. Downey
- Operating Systems and Networks – IT Series BSCS
- Think Python – Allen B. Downey (3rd Edition)
The Little Book of Semaphores will not replace an operating systems textbook, but it teaches the one skill lectures rarely give you time to practice: designing a synchronization solution yourself and arguing that it is correct. Work through Chapters 1 to 4 carefully, treat the later chapters as practice, and your exam answers on deadlock, starvation and semaphore problems will be far more confident. Browse more Computer Science books for the rest of your semester.
The Little Book of Semaphores (Second Edition, Version 2.2.2) by Allen B. Downey, Green Tea Press. Copyright 2016 Allen B. Downey. Free under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Official source: https://greenteapress.com/wp/semaphores/
© Copyright Policy
Freebooks.pk is an educational resource for students in Pakistan. Textbooks and other books belong to their respective boards, authors and publishers, and all rights remain with them. If you are the copyright holder of any material on this page and want it changed or removed, please contact us or file a request under our DMCA policy. We review every request and remove reported content promptly.
