Concurrency Example Code

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 help debugging.

Requirements

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.

Download

The files are available individually:

Or as a tar ball:

Usage

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.

Example Output

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.

Example Algorithm

Below 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.

    

Charles Gray