Semáforos

The Little Book of Semaphores
Allen B. Downey
Version 2.1.5

2

The Little Book of Semaphores
Second Edition
Version 2.1.5
Copyright 2005, 2006, 2007, 2008 Allen B. Downey

Permission is granted to copy, distribute and/or modify this document under
the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; this bookcontains no Invariant
Sections, no Front-Cover Texts, and no Back-Cover Texts.
You can obtain a copy of the GNU Free Documentation License from
www.gnu.org or by writing to the Free Software Foundation, Inc., 59 Temple
Place - Suite 330, Boston, MA 02111-1307, USA.
The original form of this book is LaTeX source code. Compiling this LaTeX
source has the effect of generating a device-independentrepresentation of a
book, which can be converted to other formats and printed.
This book was typeset by the author using latex, dvips and ps2pdf, among
other free, open-source programs. The LaTeX source for this book is available
from http://greenteapress.com/semaphores.

Preface
Most undergraduate Operating Systems textbooks have a module on Synchronization, which usually presents a setof primitives (mutexes, semaphores, monitors, and sometimes condition variables), and classical problems like readerswriters and producers-consumers.
When I took the Operating Systems class at Berkeley, and taught it at Colby
College, I got the impression that most students were able to understand the
solutions to these problems, but few would have been able to produce them, or
solve similarproblems.
One reason students don’t understand this material deeply is that it takes
more time, and more practice, than most classes can spare. Synchronization is
just one of the modules competing for space in an Operating Systems class, and
I’m not sure I can argue that it is the most important. But I do think it is one
of the most challenging, interesting, and (done right) fun.
I wrote thefirst edition this book with the goal of identifying synchronization
idioms and patterns that could be understood in isolation and then assembled
to solve complex problems. This was a challenge, because synchronization code
doesn’t compose well; as the number of components increases, the number of
interactions grows unmanageably.
Nevertheless, I found patterns in the solutions I saw, anddiscovered at
least some systematic approaches to assembling solutions that are demonstrably
correct.
I had a chance to test this approach when I taught Operating Systems at
Wellesley College. I used the first edition of The Little Book of Semaphores
along with one of the standard textbooks, and I taught Synchronization as a
concurrent thread for the duration of the course. Each week I gave thestudents
a few pages from the book, ending with a puzzle, and sometimes a hint. I told
them not to look at the hint unless they were stumped.
I also gave them some tools for testing their solutions: a small magnetic
whiteboard where they could write code, and a stack of magnets to represent
the threads executing the code.
The results were dramatic. Given more time to absorb the material, studentsdemonstrated a depth of understanding I had not seen before. More
importantly, most of them were able to solve most of the puzzles. In some
cases they reinvented classical solutions; in other cases they found creative new
approaches.

ii

Preface

When I moved to Olin College, I took the next step and created a half-class,
called Synchronization, which covered The Little Book ofSemaphores and also
the implementation of synchronization primitives in x86 Assembly Language,
POSIX, and Python.
The students who took the class helped me find errors in the first edition and
several of them contributed solutions that were better than mine. At the end of
the semester, I asked each of them to write a new, original problem (preferably
with a solution). I have added their...