Concurrency Example CodeTo 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 help debugging.
RequirementsThis 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 algorithm provided.
- 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 algorithm.
- 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:
- concurrency.tar.gz is all the above files in tar.gz format.
Usagesim161 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.
Example OutputBelow 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 exitingLines 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.
Example AlgorithmBelow is a marked-up listing of the alg_dead_lock2.py example algorithm, with detailed comments on how it works.
# alg_dead_lock2.py # # 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 # testing. # 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.