Concurrency Example Code

Requirements

Download

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.

Usage

% 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

     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
    

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

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