A number of processes could be in a deadlock state if none of them can execute due to non-availability of sufficient resources. Let P_0, P_1, P_2, P_3, P_4 represent five processes and let there be four resource types R_0, R_1, R_2, R_3. Suppose the following data structures have been used. Available: A vector of length 4 such that Available[j] = k if there are k instances of resource type R_j available. Allocation: A 5x4 matrix defining the number of resources of each type currently allocated to each process. Max: A 5x4 matrix indicating the maximum demand of each process. The data is given as follows: Allocation: Max: Available: R0 R1 R2 R3 R0 R1 R2 R3 R0 R1 R2 R3 P0: 0 0 1 2 0 0 1 2 1 5 2 0 P1: 1 0 0 0 1 7 5 0 P2: 1 3 5 4 2 3 5 6 P3: 0 6 3 2 0 6 5 2 P4: 0 0 1 4 0 6 5 6 Is the system currently in a safe state? If yes, explain why.

GATE 1988 · Operating System · Resource Allocation · medium

Answer: Yes, the system is in a safe state. Safe sequence: P0 -> P3 -> P4 -> P1 -> P2.

1. Compute Need matrix (Max - Allocation): P0: [0,0,1,2] - [0,0,1,2] = [0,0,0,0] P1: [1,7,5,0] - [1,0,0,0] = [0,7,5,0] P2: [2,3,5,6] - [1,3,5,4] = [1,0,0,2] P3: [0,6,5,2] - [0,6,3,2] = [0,0,2,0] P4: [0,6,5,6] - [0,0,1,4] = [0,6,4,2]
2. Run safety algorithm simulation: Step 1: P0: Need=[0,0,0,0] <= [1,5,2,0]. Run P0. Available += [0,0,1,2] = [1,5,3,2]. Finish[P0]=true. Step 2: P3: Need=[0,0,2,0] <= [1,5,3,2]. Run P3. Available += [0,6,3,2] = [1,11,6,4]. Finish[P3]=true. Step 3: P4: Need=[0,6,4,2] <= [1,11,6,4]. Run P4. Available += [0,0,1,4] = [1,11,7,8]. Finish[P4]=true. Step 4: P1: Need=[0,7,5,0] <= [1,11,7,8]. Run P1. Available += [1,0,0,0] = [2,11,7,8]. Finish[P1]=true. Step 5: P2: Need=[1,0,0,2] <= [2,11,7,8]. Run P2. Finish[P2]=true. All processes finish. Safe sequence: P0 -> P3 -> P4 -> P1 -> P2.