To help debug and experiment with concurrent algorithms, we have
written a deadlock detection algorithm written in python.
This system has OS161-like threads, semaphores, locks and
condition variables, and provides a deadlock detection algorithm to
This example code requires the python
interpreter to run. This is available on most platforms (eg. Linux,
Windows, Mac). These files also run on the CSE lab machines.
The files are available individually:
concurrency.py is the main executable
python script. This loads the sim161 system and executes the
sim161.py provides the OS161 environment
to simplify porting of code. The majority of code in this file has
been translated almost line for line from the OS161 sources.
deadlock.py is the deadlock detection
alg_cvsignal.py is a small piece of
code to test the condition variable `cv_signal' function works
correctly, and demonstrates its use.
alg_cvtest.py is a port of the condition
variable part of the OS161 sync primitive testing code.
alg_dead1.py is a simple example of
deadlocking a thread, and triggering the deadlock detection algorithm,
by trying to acquire (P) the same semaphore twice without releasing.
The alg_dead2.py algorithm has two threads
which acquire semaphores in a different order to cause deadlock.
alg_dead_lock.py demonstrates that a
lock can just as easily be used to cause deadlock by acquiring twice.
alg_dead_lock2.py creates two threads
which acquire locks in a different order.
alg_ostrich_count.py shows the
original reason for mutual exclusion - race conditions.
alg_safe2.py is an algorithm with
two threads which acquire resources in the same order and
hence do not deadlock.
Or as a tar ball:
sim161 is invoked as follows:
% python concurrency.py alg_name.py
This will invoke the simulator with the algorithm in `alg_name.py'
and execute it. There are a number of algorithms provided above to
look at, or you can easily write your own.
Below is an example execution of the alg_dead2 algorithm
which has two threads that acquire semaphores in a different order.
1 ~/code/cs3231 % python concurrency.py alg_dead2.py
2 Initialising sim161 module
3 cs3231 Lock Example Code starting
4 Counter is 1 in thread 0
5 Deadlock detected!!
6 Deadlocked processes: ['thread1', 'thread0']
7 Process thread1
8 Holding sem1 - file alg_dead2.py, line 45
9 P( sem1 )
10 Waiting on sem0 - file alg_dead2.py, line 46
11 P( sem0 )
12 Process thread0
13 Holding sem0 - file alg_dead2.py, line 30
14 P( sem0 )
15 Waiting on sem1 - file alg_dead2.py, line 31
16 P( sem1 )
17 cs3231 Lock Example Code exiting
Lines 2 and 3 of the above output are the normal startup messages from
the emulator. Line 4 is output from the algorithm itself. This output
depends on the algorithm chosen, and this case is telling us the value of
a shared variable in `thread 0'.
Line 5 is the deadlock detection algorithm triggering. Line 6 shows that
there are two threads in the deadlock - 'thread1' and 'thread0'.
Lines 7-11 show the status of thread1. It is holding the
semaphore 'sem1', which it acquired in the code on line 45 of the
file 'alg_dead2.py'. The line of code is shown on Line 9. Line 10 shows
that thread1 was also waiting on semaphore 'sem0'. The code to wait is
line 46 of alg_dead2.py.
Lines 12 through 16 is a similar status dump for thread0. In this case
thread0 is holding sem0 and waiting on sem1. Classic deadlock! The
offending lines of code are lines 30 and 31 in alg-dead2.py.
Line 17 is the exit message from the emulator. When a deadlock is
detected the system exits with a dump of the deadlock status, as shown.
If a threads runs continually (eg. alg_safe2.py) because it is a safe
algorithm in an infinite loop, the emulator can be killed with CTRL+C.
Below is a marked-up listing of the alg_dead_lock2.py
example algorithm, with detailed comments on how it works.
# Deadlock by acquiring waiting on the same lock twice
# We want all the symbols from sim161
# This imports the os161 functions for threads, lock, semaphores etc.
# This is basically necessary on any algorithm using sim161
from sim161 import *
# Global variables for out lock variable, lock0 and lock1
# Tailor these to your needs.
lock0 = None
lock1 = None
# This is the code for one of the threads. It acquires the locks
# in the other 0, 1
# You are free to write your own thread code, however you like
def thread_code_one( arg ):
lock_acquire( lock0 )
lock_acquire( lock1 )
# This is the code for the other thread, it acquires the locks in
# the order 1, 0
def thread_code_two( arg ):
lock_acquire( lock1 )
lock_acquire( lock0 )
# This is the entry point for the algorithm. We will be running
# in an os161 thread called `main'. We can either implement our
# test code in here, or use it to create other threads to do the
# The `args' argument is all the command-line parameters passed to
# concurrency.py after the algorithm name. We do not use them in
# this example code.
# Every algorithm needs a `main' function
def main( args ):
# In Python we need the `global' keyword to write to
# the global variables. Each global variable we write in a
# function needs to be declared in that function as 'global'
global lock0, lock1
# Create the actual lock variables
# This interface is identical to OS161 internals
lock0 = lock_create( "lock0" )
lock1 = lock_create( "lock1" )
# Create two threads to deadlock
# We implement a simpler thread_create instead of the thread_fork
# used in OS161. It should be sufficient for toy example code.
# The first argument is the name of the thread to create. This
# is shown in deadlock dumps. The 2nd argument is the function
# to start the new thread at. The 3rd argument is an argument to
# pass through as an argument for the new thread. This is handy
# if you want to create multiple threads on the same function.
# If you do not need a parameter, simply pass `None' as shown.
thread_create( "thread0", thread_code_one, None )
thread_create( "thread1", thread_code_two, None )
# At this point the `main' thread exits. The emulator will
# continue to run until someone calls the exit() function,
# or a deadlock is encountered.
# Pressing CTRL+C should kill the emulator at any time.