###
#
# An implementation of Deadlock Detection Algorithm
#
# The algogorithm is the general purpose algorithm given in
# cs3231 lectures and tutorials.
# The support code only does one resource at a time, though.
# Feel free to write your own client program, however :)
#
###

import sys
import threading
import traceback
import os

# Set SHOW_DEBUG to 0 to supress debug output, some other value to show it!
SHOW_DEBUG = 0

# Exit function - called on deadlock
# by default we just use sys.exit, but we can override this
exit = sys.exit

# debug function
# Handy if you want to see how the internals of the algorithm work.
def DEBUG( str ):
    if( SHOW_DEBUG ):
        print str

### The actual algorithm

# Sum to vectors - assuming they are the same length
# Eg. To add acquired resources to the available vector
def add_row( a, b ):
    ret = []
    for i in range(0, len(a)):
        ret.append( a[i] + b[i] )


    DEBUG( "add_row: %s + %s = %s" % (a, b, ret ) )
    return ret

# Compare each element in `a' with the corresponding element in `b'
# if all are <= then we return true
# To compare whether a process can complete with the available resources
def less_than_eq( a, b ):
    for i in range(0, len(a)):
        if( a[i] > b[i] ):
            return 0

    return 1

# Algorithm entry point
# @A - Available resources
# @C - Current resource allocation
# @R - Requested resource allocation
#
# These are named as per the lecture notes
# A is a list, one item per resource
# C and R are matrices - lists of lists.
# The external list contains one list per process.
# The process list has one item per resource.
# Resource and process lists must all correspond, and be
# of similar lengths!
def detect_deadlock( A, C, R ):

    DEBUG( "Doing Deadlock Detection Algorithm" )
    DEBUG( "A: %s" % A )
    DEBUG( "C: %s" % C )
    DEBUG( "R: %s" % R )

    # Generate the list of unmarked processes
    unmarked = range( 0, len(C) )

    while(1):
        # 1: Look for an unmarked process Pi, for which the i-th row of R
        #    is less than or equal to A
        found_one = 0
        for i in unmarked:
            DEBUG( "Checking %s <= %s" % ( R[i], A ) )
            if( less_than_eq( R[i],  A ) ):
                # 2: If found, add the i-th row of C to A...
                A = add_row( A, C[i] )

                # 2.1: and mark Pi.
                del unmarked[unmarked.index(i)]
                found_one = 1

                # 2.2: Go to step 1
                break

        # Everything worked!
        if( len( unmarked ) == 0 ):
            # Cheer!
            return []
        
        # 3: If no such process exists, terminate.
        if( found_one == 0 ):
            DEBUG( "Deadlock!" )
            DEBUG( "Resources: %s" % show_resources() )
            DEBUG( "A: %s" % show_vector( A ) )
            DEBUG( "C: %s" % show_matrix( C ) )
            DEBUG( "R: %s" % show_matrix( R ) )

            # Return the deadlock list
            return unmarked


### Print functions - convert things to nice strings
#
# This allows us to make pretty output.
# This code is not really interesting :)

def show_resources():
    return repr(resources.keys())

def show_vector( vec ):
    return repr(vec)

def show_matrix( mat ):
    ret = ""

    for i in range( 0, len(mat) ):
        ret += "\n" + processes.keys()[i] + " " + show_vector( mat[i] )

    return ret

def proc_keylist( list ):
    keylist = []
    for i in list:
        keylist.append( processes.keys()[i] )

    return keylist

def rsrc_keylist( list ):
    keylist = []
    for i in list:
        keylist.append( i )

    return keylist

def show_proclist( list ):
    namelist = proc_keylist( list )
    return repr( namelist )

def show_rsrclist( list ):
    namelist = rsrc_keylist( list )
    return repr( namelist )

def show_info( info ):
    fname = os.path.basename( info[0] )
    lineno = info[1]
    line = info[3]
    return "file %s, line %s\n\t %s" % ( fname, lineno, line )

def show_lockinfo( item ):
    return "%s - %s" % (item.resource, show_info(item.info))

# Show deadlocked processes
# Dump information on a deadlock
def show_deadlock( deadlist ):

    print "Deadlock detected!!"
    print "Deadlocked processes: %s" % show_proclist( deadlist )

    for proc in proc_keylist( deadlist ):
        print "Process %s" % proc

        for item in processes[proc]:
            print " Holding    %s" % show_lockinfo( item )

        for item in waiters[proc]:
            print " Waiting on %s" % show_lockinfo( item )
        

### Internal state
#
# Below here is the 'management code'. This is what stores the state
# beteen calls to the above algorithm, and coverts the state into something
# useful for the algorithm. The algorithm and the code below should be
# freely changeable, provided you use the same interface.
#
# This code maintains internal lists of available resources, and what
# processes hold and are waiting on which resources.  We could have put this
# state into sim161 and arguably made things a little easier, however this
# would change the sim161 implementation more than necessary, and would also
# make this module less self-standing

processes = {}   # The list of processse & what they hold
waiters   = {}   # The list of processes & what they are trying to acquire 
resources = {}   # The list of resources and how many are available


# An entry in the process/waiting list
class LockInfo:
    def __init__( self, resource, info ):
        # The resource that's being held/waited on
        self.resource = resource
        # Traceback information for the acquire/wait so we can
        # provide useful debugging information in the event of deadlock
        self.info = info

# List management

# Add an item to a process (acquired or waiting) list
def process_list_add( plist, process, resource, info ):
    li = LockInfo( resource, info )
    plist[process].append( li )

# Remove an item from a process (acquired or waiting) list
def process_list_remove( plist, process, resource ):

    list = plist[process]
    for i in range( 0, len(list) ):
        if( list[i].resource == resource ):
            del( list[i] )
            return


### Interface to full algorithm
# Construct vectors and matrices as per the algorithm
# See lecture notes, textbook, whatever
#
# This is the code that converts the 3-list runtime state into
# a vector and two matrices for the detection algorithm

# Create a vector (row) for the matrix
# @held - a list of the resources held
# @rs   - a list of resources, in order of how to place them in the vector
def create_vector( held, rs ):

    # Create a row of zeros
    row = [None] * len(rs)

    # Fill out the counts for what we have
    for resource in rs:
        c = held.count( resource )
        row[ rs.index(resource) ] = c

    return row

# Turn a list of ListInfos into a list of resouce keys
def make_rslist( lilist ):
    ret = []
    for i in lilist:
        ret.append( i.resource )
    return ret

# Create a matrix from the information in a process list (acquire or waiting)
def create_matrix( proclist, rkeys ):
    mat = []
    for key in processes.keys():
        mat.append( create_vector( make_rslist( proclist[key] ), rkeys ) )

    return mat

# Check for deadlock
def check_for_deadlock():

    # Make a tuple of available resources
    keys = resources.keys()   # get a list of resource names
    A = [0] * len(keys)       # make an n-tuple (n-element list here)

    # set the available count
    for i in range( 0, len( keys ) ):
        A[i] = resources[keys[i]]

    # build the list of current allocations
    C = create_matrix( processes, keys )

    # Make the request matrix
    R = create_matrix( waiters, keys )
    
    # Now we can *actuall* run the algorithm!
    deadlocked = detect_deadlock( A, C, R )

    # If the list is empty, nothing is deadlocked
    if( len(deadlocked) == 0 ):
        return

    # Otherwise we need to dump the list of deadlocked processes
    show_deadlock( deadlocked )

    # quit
    exit(1)

### getinfo
# Get call stack information. We want to know our caller's caller's caller
# interesting_info( sem_op( dlock_op( getinfo() ) ) )
#
# This is so we can have nice output when there is deadlock
#
# This essentially pokes up the call frame a few invocations to see what
# algorithm code called a lock primitive. We can then dump this information
# later. This is tricky to do in a language like C, and requires excessive
# use of pre-processor macros
def getinfo():
    tb = traceback.extract_stack()

    info = tb[-4]

    DEBUG( "lock primitive called from %s" % show_info( info ) )

    return info
    
### Interface functions

# Add a resource to monitor
# @name - the name of the resource
# @quantity - the number of this resource available
def add_resource( resource, quantity ):
    # Make sure we don't add the same resource name twice
    if( resources.has_key( resource ) ):
        print "ERROR! Adding resource %s twice!" % resource
        sys.exit(1)
        
    # add it
    resources[resource] = quantity

# Add a process to monitor
# @name - the name of the process
def add_process( process ):
    # Make sure process names are unique
    if( processes.has_key( process ) ):
        print "ERROR! Adding process %s twice!" % process
        sys.exit(1)

    # add it
    processes[process] = []
    waiters[process] = []    

# Add an entry for `process' waiting on `resource'
# Check whether acquisition of `resource' by `process' will cause deadlock
def acquire_resource_wait( process, resource ):

    info = getinfo()
    
    DEBUG( "Waiting resource %s by process %s at %s" % \
           ( resource, process, info ) )

    # add it to the list
    process_list_add( waiters, process, resource, info );
    
    DEBUG( "Checking For Deadlock" )

    # Check it will work
    check_for_deadlock()

# `process' is no longer waiting on `resource'. Remove it from the lists
def release_resource_wait( process, resource ):
    DEBUG( "Unwaiting resource %s by process %s" % ( resource, process ) )

    process_list_remove( waiters, process, resource )

# Mark `resource' as taken by `process'
def acquire_resource( process, resource ):

    info = getinfo()
    
    DEBUG( "Adding resource %s to process %s at %s" % \
           ( resource, process, info ) )

    # Do the acquisition
    process_list_add( processes, process, resource, info )
    resources[resource] -= 1

# Release resource `resource' from 'process'
def release_resource( process, resource ):
    DEBUG( "Removing resource %s from process %s" % ( resource, process ) )
    process_list_remove( processes, process, resource )
    resources[resource] += 1

# Increase the number of availble of a type of resource
# Use this *with care*
#
# Resources like semaphores can be acquired multiple times in a loop
# to be released later by other threads. This model is used in OS161 to
# wait for a number of threads to exit etc.
# Doing this would trigger the deadlock detection algorithm because the
# semaphore is marked as having a value of zero, and no thread can release it.
# By using `increase_resource', we can leave the OS161 semaphore value at
# zero, and then tell the deadlock detection algorithm that it is to be
# signalled later, and how many times. It is then necessary to acquire the
# semaphore on behalf of the threads that will be signalling.
#
# NB: increasing the available resource count on a semaphore will not help
# solve deadlock! The deadlock detection algorithm may not trigger, but the
# program will still deadlock. Fix the algorithm.
def increase_resource( resource, num ):
    DEBUG( "Increasing resource %s by %d" % ( resource, num ) )

    resources[resource] += num