4010-441 Principles of Concurrent System Design
The Banker's Algorithm

This page is accessible at www.se.rit.edu/~se441/Assignments/Bankers_Algorithm.html.

Here are pointers to other discussions of the Banker's Algorithm; the Web is full of them.

• Wikipedia
• University of Idaho
• Colorado State

Overview

One of the trickiest problems in concurrency is system resource management; the Banker's Algorithm is a classic deadlock free solution that is appropriate when (a) the resources are mutable, (b) processes / threads may request multiple units of a resource (e.g., printers), and (c) each process / thread can determine, at startup, the maximum number of units it needs of the resource (actually, we can relax these restrictions a bit at the cost of some additional complexity, but we won't).

The banker is initially configured with the number of resources it has to loan. Newly created threads register their maximum resource claim; obviously, this cannot exceed the number of resources the banker has. For each registered thread the banker maintains the maximum claim and the number of resources on loan to the thread (initially 0).

Once registered, a thread can request and release resources. We will ignore the details of how specific units (e.g., specific printers) are associated with a thread; all we care about is the following:

• The number of resource units currently allocated to each thread.
• The number of resource units remaining in each thread's request.
• The number of unallocated resource units.

The information above defines the state of the system from the perspective of the Banker. Note the following state invariants:

1. The unallocated units plus the sum of the units allocated to each thread equals the total number of units available.
2. For each thread, its allocation plus its remaining claim equals its maximum claim.

Safe States

The design of the system revolves around the notion of a safe state. In a safe state, there is some order in which threads could repay all outstanding loans (return all allocated resources) even if every thread requests all the remaining resources it can claim. Any other state is unsafe, as it may lead to deadlock (deadlock is not certain, because threads are not required to request all the resources in their claim). Below are examples of safe and unsafe states in a system with two threads and four allocatable resources. The columns are (C)laim (as initially sent to the banker), (A)llocated and (R)emaining claim. Note that, for each thread, C = A + R is an invariant.

Thus state 1 is safe.

Assume T_2 requests one unit; if granted, the system state would look like:

Thus, state 2a is also safe and the request can proceed.

Now assume we are in state 1 again and T_1 requests 1 unit; if granted, the system state would look like:

1. The initial state, where no threads have registered a claim, is safe.
2. If the system is in a safe state and  new thread registers a claim for no more than the available resources, the resulting state is safe (in the worst case we can run all the threads in the original state to completion, and then run the new thread to completion).
3. Thus, the only time we can create an unsafe state is when a thread attempts to acquire more resources (up to its remaining claim). In this case, we "pretend" to allocate the resource(s) by creating a copy of the current state, and altering the copy to reflect an increase of the requesting thread's allocation (and decrease of its remaining claim) by the number of units requested.
4. Run the bankers algorithm (see below) on the pretend sate, and
1. If the pretend state is safe, use it as the current state and return the resources to the requester.
2. If the pretend state is unsafe, block the requester until some resources are released, and repeat the "pretend" allocation again.
5. If the system is in a safe state and a thread releases some resources, the resulting state is safe (why?). As this may allow a blocked requester to get the resources it needs, we unblock any and all blocked requesters in the hope that at least one will be able to proceed.

The Banker's Algorithm: Determining State Safety

Design

Banker Class

public Banker(int nUnits)

Initialize the new Banker object to manage nUnits units of resource.
No threads are registered with the Banker.

public void setClaim(int nUnits)

The current  thread (available via static method Thread. currentThread()) attempts to register a claim for up to nUnits units of resource.

• The method calls System.exit(1) if:
1. the thread already has a claim registered, or
2. nUnits is not strictly positive, or
3. nUnits exceeds the number of resources in the system.
• Associate the thread with a current claim equal to nUnits and a current allocation of 0.
• Print a message of the form:
         Thread name sets a claim for nUnits units.
  where name is the thread name (via Thread.currentThread().getName()) and nUnits is the number of resources claimed, and return.

public boolean request(int nUnits)

The current thread requests nUnits more resources.

• The method calls System.exit(1) if (a) the current thread has no claim registered, (b) nUnits is not strictly positive or (c) nUnits exceeds the invoking thread's remaining claim.
• Print the message
         Thread name requests nUnits units.
• If allocating the resources results in a safe state,
          Print a message Thread name has nUnits units allocated.
          Update the banker's state and return to the caller.
• Otherwise enter a loop that
          Prints the message Thread name waits.
          Waits for notification of a change.
          When reawakened, prints the message Thread name awakened.
          If allocating the resources results in a safe state, prints
                 Thread name has nUnits units allocated.
                           Updates the banker's state and returnz.

public void release(int nUnits)

The current thread releases nUnits resources.

• The method calls System.exit(1) if (a) the current thread has no claim registered, (b) nUnits is not strictly positive or (c) nUnits exceeds the number of units allocated to the current thread.
• Print the message
           Thread name releases nUnits units.
• Release nUnits of the units allocated to the current thread, notify all waiting threads, and return.

public int allocated( )

Returns the number of units allocated to the current thread.

public int remaining( )

Returns the number of units remaining in the current thread's claim.

Client Class

The Client class extends Thread; multiple Client objects content for the pool of resources by calling methods in a shared Banker object.

public Client(String name, Banker banker, int nUnits, int nRequests, long minSleepMillis, long maxSleepMillis)

Initialize the new Client  thread object. The name string is passed to the super (Thread) class's constructor. The remaining 5 arguments should be saved in instance variables of the same names for use when the thread is started and run( ) is called.

public void run( )

Register a claim for up to nUnits of resource with the banker. Then create a loop that will be executed nRequests times; each iteration will either request or release resources by invoking methods in the banker.

• If the banker.remaining() == 0, then the client will release all of its units, otherwise the client will request some units.
• At the end of each loop, use Thread.sleep(millis) to sleep a random number of milliseconds from minSleepMillis to maxSleepMillis. This will introduce another dose of non-determinism into your program.

When the loop is done, release any units still allocated and simply return from run( ) - this will terminate the client thread.

Driver Class

The driver class contains the public static void main( ... ) method that (a) creates a Banker object, (b) creates several Client objects, (c) starts all of the Clients, and (d) waits for all the clients to complete via the instance method join( ). With proper setting of the configuration parameters you should be able to produce runs where a Client is delayed because granting its request would lead to an unsafe state.

The Driver should also contain a set of well-documented final private static int variables that specify the configuration parameters (number of resources for the Banker, number of Clients, arguments to the Client constructors, etc.).  I may use these to experiment with your solution to see if I can break it.

Deliverables

Submit three files (and only three files), Driver.java, Client.java, and Banker.java to the Banker Activity dropbox by due date. Of the 10 points available for this activity:

• 2 will be granted on an all-or-nothing basis for a correct submission in accordance with the preceding specification,
• 5 will be based on the correctness of the solution,
• 2 will be based on the quality of the solution (naming, spacing, indentation, etc.), and
• 1 will be based on whether or not the internal documentation is of acceptable quality.