Home
Sync is a thread simulator used you can use to solve classical (and not-so-classical) synchronization problems using semaphores. It is intended to help with the exercises in The Little Book of Semaphores.
A semaphore is a data structure that can be shared between concurrent threads in order to enforce synchronization constraints. The most common synchronization constraint is "mutual exclusion", in which a critical section of a program is protected so that only one thread can execute it concurrently.
The following screenshot shows a Sync simulation of two threads using a semaphore to enforce exclusive access to an increment operation (which is usually not thread-safe):
The top three rows show the initialization code that creates a Semaphore object named mutex and a counter named x. The current value of mutex is -1, which indicates that there is one thread in queue waiting for this semaphore.
The next four rows show the code the threads are executing. In order to enter the critical section, each thread executes mutex.wait. After executing the critical section the threads execute mutex.signal to indicate that the critical section is free.
The threads are represented by colored, lettered circles. Thread A is in the critical section; it is just about to execute x=x+1. Thread B has just executed mutex.wait, but because the critical section is occupied, Thread B has been moved into the queue. When Thread A executes mutex.signal, Thread B will be moved back into the Run column and allowed to proceed.
The Little Book of Semaphores presents a series of classical synchronization problems; the following screenshot shows a solution to the producer-consumer problem (in this case the "buffer" is a coke machine with a capacity of three cokes).
The code in these examples is "live" in the sense that users can modify it at any time (even while the simulator is running). The "Random Run" button simulates a non-deterministic scheduler that chooses a runnable thread at random. Students can also click on the thread markers to generate an arbitrary schedule.
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 goal of Sync is to give readers a model of execution for multithreaded programs and an environment for testing solutions. After working on these exercises, readers are able to solve the most difficult synchronization problems; they can also formulate new problems based on real-world synchronization constraints.
Sync runs in Python 2 and 3, and requires Tkinter.
Sync and the text of The Little Book of Semaphores is in this Git repository: https://github.com/AllenDowney/LittleBookOfSemaphores. Git is a version control system that allows you to keep track of the files that make up a project. A collection of files under Git’s control is called a repository. GitHub is a hosting service that provides storage for Git repositories and a convenient web interface.
The GitHub homepage for my repository provides several ways to work with the code:
- You can create a copy of my repository on GitHub by pressing the Fork button. If you don’t already have a GitHub account, you’ll need to create one. After forking, you’ll have your own repository on GitHub that you can use to keep track of code you write while working on this book. Then you can clone the repo, which means that you copy the files to your computer.
- Or you could clone my repository. You don’t need a GitHub account to do this, but you won’t be able to write your changes back to GitHub.
- If you don’t want to use Git at all, you can download the files in this Zip file.
Once you have downloaded the Sync code, you can launch Sync on the command line like this:
cd LittleBookOfSemaphores/code
python Sync.py sync_code/mutex.py
The argument to Sync.py is the file it should read code from. The sync_code directory contains many of the examples from the book.
Code that can run in Sync is basically a subset of Python. Input files are divided into sections divided by comments beginning with ##.
The first section is considered initialization code. Variables defined in this section are available to all threads. Each subsequent section of code is put into a column of thread code. For example, here are the contents of mutex.py:
# mutual exclusion
mutex = Semaphore(1)
counter = 0
## Thread code
mutex.wait()
# critical section
counter += 1
mutex.signal()
This first section initializes mutex and counter. The second section contains the code the threads will run.