Deadlocks cont #

Banker’s algorithm cont. #

Recall that the safety subroutine simulates allocating all resources, and if able to if returns true (because it is considered a safe state). If it is unable to simulate allocating all resources, it will return false.

The second subroutine of the Banker’s algorithm is the resource request:

• simulates allocating resource requests by modifying the state of the process
• if safe, the resources can be allocated
• otherwise, it has to wait

Example using Banker’s algorithm #

So first we run the safety algorithm:

After the initial loop thru all processes, we then go back and check the remaining false finished processes.

This returns a safe sequence. A safe sequence may or may not be unique.

When \( P_1 \) requests (1,0,2), the resource request subroutine is called.

Then, the safety algorithm runs on this new simulated state. If it returns true, then we can approve this request. Otherwise, it is denied.

Deadlock detection #

Incase we can’t always avoid deadlock, we need a way to detect whether we are in a deadlock state or not.

Once the wait-for graph is built, we can see that there are cycles (2). However, for multiple instance case, we rely on a variation of the Banker’s algorithm.

• this is the safety algorithm in the detection version
• if any process’s finish[i] is false, then a deadlock has occured