Banker's Safety Algorithm.

bankers.py

from operator import add, sub, le
def vector(operator):
    '''
    Apply operator to each element of vector and returns
    the resultant vector:
    from operator import add, sub, mul
    vector(add)([1,2,3], [2,3,4]) => [3,5,7]
    '''
    return lambda A, B: map(operator, A, B)

def matrix(operator):
    '''
    Similar to 'vector(operator)' but works on matrices
    '''
    return lambda A, B: map(vector(operator), A, B)

def isSafe (available, maximum, current):
    '''
    Determines if the system is in a safe state.

    available(array) : available[j] represents number of resources
    available of type j

    maximum(matrix) : maximum[i][j] represents the maximum number 
    of resources of type j needed by process i

    current(matrix) : current[i][j] represents the current number
    of allocations of resource of type j to proccess i
   
    Returns: True if system is in safe state, otherwise False
    '''
    
    m = len(available) # number of type of resources
    n = len(maximum) # number of processes
    need = matrix(sub)(maximum, current) # need = maximum - current
    work = available[:] #copy available in work
    finish = [False]*n
    while True:
        i = None
        for k in range(n):
            if not finish[k] and all(vector(le)(need[k], work)):
                i = k
        if i == None:
            break
        work = vector(add)(work, current[i])
        finish[i] = True
    return all(finish)

def resourcesRequest(available, maximum, current, i, request):
    '''
    Allocates resources to processors after checking the safety
    available

    available(array) : available[j] represents number of resources
    available of type j

    maximum(matrix) : maximum[i][j] represents the maximum number 
    of resources of type j needed by process i

    current(matrix) : current[i][j] represents the current number
    of allocations of resource of type j to proccess i
    
    i(integer) : index of the processor making the request

    request(array) : request[j] represent the number of resources
    of type j which processor i is requesting

    Returns:
    if allocation succeeds, returns the new state of 'available'
    array and 'current' matrix
    False otherwise
    '''
    
    need = matrix(sub)(maximum, current)
    if not all(vector(le)(request, need[i])):
        # process exceeded its maximum claim
        raise Exception('Process exceeded its maximum claim')
    if not all(vector(le)(request, available)):
        # resources are not available, must wait
        return False
    new_available, new_current= map(list, (available, current))
    new_available = vector(sub)(available, request)
    new_current[i] = vector(add)(current[i], request)
    if not isSafe(new_available, maximum, new_current):
        return False
    return (new_available, new_current)

if __name__ == '__main__':
    current = [[0,0,1,2],
               [1,0,0,0],
               [1,3,5,4],
               [0,6,3,2],
               [0,0,1,4]]
    maximum = [[0,0,1,2],
               [1,7,5,0],
               [2,3,5,6],
               [0,6,5,2],
               [0,6,5,6]]
    available = [1,5,2,0]
    print 'Is the system in a safe state:',isSafe(available, maximum, current)

    process_id, request = 1, [0,4,2,0]

    print 'Can the request %s by process %i be granted:' % (str(request), process_id), resourcesRequest(available, maximum, current, process_id, request) is not  False