Problems on Safety algorithm
1. System consists of five jobs (J1, J2, J3, J4, J5 ) and three resources. Resource type R1 has 10
instances, resource type R2 has 5 instances and R3 has 7 instances. The following snapshot of
the system has been taken. Find need matrix and calculate the safe sequence by using the
Banker’s algorithm. Mention whether the above system is safe or not.
Jobs Allocation Maximum Available
R1 R2 R3 R1 R2 R3 R1 R2 R3
J1 0 1 0 7 5 3 3 3 2
J2 2 0 0 3 2 2
J3 3 0 2 9 0 2
J4 2 1 1 2 2 2
J5 0 0 2 4 3 3
Step 1: Calculate the Need Matrix
Need = Maximum – Allocation
Jobs Need (R1 R2 R3)
J1 7-0 5-1 3-0 = (7 4 3)
J2 3-2 2-0 2-0 = (1 2 2)
J3 9-3 0-0 2-2 = (6 0 0)
J4 2-2 2-1 2-1 = (0 1 1)
J5 4-0 3-0 3-2 = (4 3 1)
So the Need Matrix is:
Jobs Allocation Maximum Available Need Matrix
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3
J1 0 1 0 7 5 3 3 3 2 7 4 3
J2 2 0 0 3 2 2 5 3 2 1 2 2
J3 3 0 2 9 0 2 7 4 3 6 0 0
J4 2 1 1 2 2 2 7 5 3 0 1 1
J5 0 0 2 4 3 3 10 5 5 4 3 1
10 5 7
Step 2: Calculate the Total Allocated Resources
Sum of Allocation column:
R1 = 0 + 2 + 3 + 2 + 0 = 7
R2 = 1 + 0 + 0 + 1 + 0 = 2
R3 = 0 + 0 + 2 + 1 + 2 = 5
Calculate Available Resources:
Total resources - Allocated = Available
R1: 10 - 7 = 3
R2: 5 - 2 = 3
R3: 7 - 5 = 2
Matches the given Available vector: (3 3 2)
Step 3: Apply Banker's Algorithm to find Safe Sequence
Initial Available = (3 3 2)
Step-by-step:
Check J1: Need = (7 4 3) — Not ≤ Available (3 3 2) False
Check J2: Need = (1 2 2) — ≤ (3 3 2) True
→ Allocate to J2 → Finish J2 → Release Allocation (2 0 0)
→ New Available = (3+2, 3+0, 2+0) = (5 3 2)
→ Safe sequence so far: J2
Check J1: Need = (7 4 3) — Not ≤ (5 3 2) False
Check J3: Need = (6 0 0) — Not ≤ (5 3 2) False
Check J4: Need = (0 1 1) — ≤ (5 3 2) True
→ Allocate to J4 → Release (2 1 1)
→ New Available = (5+2, 3+1, 2+1) = (7 4 3)
→ Safe sequence: J2, J4
Check J1: Need = (7 4 3) — ≤ (7 4 3) True
→ Allocate to J1 → Release (0 1 0)
→ New Available = (7+0, 4+1, 3+0) = (7 5 3)
→ Safe sequence: J2, J4, J1
Check J3: Need = (6 0 0) — ≤ (7 5 3) True
→ Allocate to J3 → Release (3 0 2)
→ New Available = (7+3, 5+0, 3+2) = (10 5 5)
→ Safe sequence: J2, J4, J1, J3
Check J5: Need = (4 3 1) — ≤ (10 5 5) True
→ Allocate to J5 → Release (0 0 2)
→ New Available = (10+0, 5+0, 5+2) = (10 5 7)
→ Safe sequence: J2, J4, J1, J3, J5
Final Answer:
Need Matrix:
Jobs R1 R2 R3
J1 7 4 3
J2 1 2 2
J3 6 0 0
J4 0 1 1
J5 4 3 1
Safe Sequence:
J2 → J4 → J1 → J3 → J5
Problem 2
2. Assume that there are 5 processes, P0 through P4, and 4 types of resources. At T0 we have
the following system state:
Max Instances of Resource Type A = 3 Max Instances of Resource Type B = 17 Max
Instances of Resource Type C = 16 Max Instances of Resource Type D = 12
Given Matrices
Allocation Max Available
A B C D A B C D A B C D
P0 0 1 1 0 0 2 1 0 1 5 2 0
P1 1 2 3 1 1 6 5 2
P2 1 3 6 5 2 3 6 6
P3 0 6 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
Total 2 12 14 12
1. Calculate need Matrix?
2. Use the safety algorithm to test if the system is in a safe state or not?
Total allocated resources:
Resource Total Allocated
A 2
B 12
C 14
D 12
Step 1: Calculate Need Matrix
Need=Max−Allocation
Calculate for each process and resource:
Process Need (A, B, C, D)
P0 (0-0, 2-1, 1-1, 0-0) = (0, 1, 0, 0)
P1 (1-1, 6-2, 5-3, 2-1) = (0, 4, 2, 1)
P2 (2-1, 3-3, 6-6, 6-5) = (1, 0, 0, 1)
P3 (0-0, 6-6, 5-3, 2-2) = (0, 0, 2, 0)
P4 (0-0, 6-0, 5-1, 6-4) = (0, 6, 4, 2)
Step 2: Available Resources vector
Allocation Maximum Available Need Matrix
A B C D A B C D A B C D A B C D
P0 0 1 1 0 0 2 1 0 1 5 2 0 0 1 0 0
P1 1 2 3 1 1 6 5 2 1 6 3 0 0 4 2 1
P2 1 3 6 5 2 3 6 6 1 12 6 2 1 0 0 1
P3 0 6 3 2 0 6 5 2 2 14 9 3 0 0 2 0
P4 0 0 1 4 0 6 5 6 3 17 15 8 0 6 4 2
3 17 16 12
Given: Available= (1, 5, 2, 0)
We can verify available resources using:
Available=Total Instances−Sum of Allocations
For A: 3 - 2 = 1
For B: 17 - 12 = 5
For C: 16 - 14 = 2
For D: 12 - 12 = 0
Matches perfectly.
Step 3: Use Banker's Algorithm to check system safety
Iteration 1: Find a process with Need ≤ Work
P0: Need = (0, 1, 0, 0) ≤ (1, 5, 2, 0)? True
Finish P0:
Available = Available + Allocation (P0) = (1, 5, 2, 0) + (0, 1, 1, 0) = (1, 6, 3, 0)
Safe sequence so far: P0
P1: Need = (0, 4, 2, 1) ≤ (1, 6, 3, 0)? False
P2: Need = (1, 0, 0, 1) ≤ (1, 6, 3, 0)? False
P3: Need = (0, 0, 2, 0) ≤ (1, 6, 3, 0)? True
Finish P3:
Available = (1, 6, 3, 0) + Allocation (P3) = (1, 6, 3, 0) + (0, 6, 3, 2) = (1, 12, 6, 2)
Safe sequence: P0, P3
Iteration 2: Check remaining:
P1: Need = (0, 4, 2, 1) ≤ (1, 12, 6, 2)? True
Finish P1: Available = (1, 12, 6, 2) + Allocation (P1)
Available = (1, 12, 6, 2) + (1, 2, 3, 1) = (2, 14, 9, 3)
Safe sequence: P0, P3, P1
P2: Need = (1, 0, 0, 1) ≤ (2, 14, 9, 3)? True
Finish P2:
Available = (2, 14, 9, 3) + Allocation (P2) = (2, 14, 9, 3) + (1, 3, 6, 5) = (3, 17, 15, 8)
Safe sequence: P0, P3, P1, P2
P4: Need = (0, 6, 4, 2) ≤ (3, 17, 15, 8)? True
Finish P4:
Available = (3, 17, 15, 8) + Allocation (P4) = (3, 17, 15, 8) + (0, 0, 1, 4) = (3, 17, 16, 12)
Safe sequence: P0, P3, P1, P2, P4
Final answers:
1. Need Matrix:
Process A B C D
P0 0 1 0 0
P1 0 4 2 1
P2 1 0 0 1
P3 0 0 2 0
P4 0 6 4 2
2. Safe sequence: P0 → P3 → P1 → P2 → P4
3. Is system safe? Yes, the system is in a safe state.
3. For the following snapshot find the safe sequence using bankers algorithm: The number of
resource units are R1, R2, and R3 which are 7,7,10 respectively
Process Allocation Maximum Available
R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 2 2 3 3 6 8 7 7 10
P2 2 0 3 4 3 3
P3 1 2 4 3 4 4
Step 1: Calculate the Need Matrix
Need = Maximum – Allocation
Process Need (R1 R2 R3)
P1 3-2 6-2 8-3 = (1 4 5)
P2 4-2 3-0 3-3 = (2 3 0)
P3 3-1 4-2 4-4 = (2 2 0 )
So the Need Matrix is:
Process Allocation Maximum Available Need Matrix
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 2 2 3 3 6 8 7 7 10 1 4 5
P2 2 0 3 4 3 3 9 9 13 2 3 0
P3 1 2 4 3 4 4 11 9 16 2 2 0
12 11 20
Step 2: Calculate the Total Allocated Resources
Sum of Allocation column:
R1 = 2+2+1+7 = 12
R2 = 2+0+2+7 = 11
R3 = 3+3+4+10 = 20
Calculate Available Resources:
Total resources - Allocated = Available
R1: 12 - 5 = 7
R2: 11 - 4 = 7
R3: 20 - 10 = 10
Matches the given Available vector: (7 7 10)
Step 3: Apply Banker's Algorithm to find Safe Sequence
Initial Available = (7 7 10)
Step-by-step:
Need ≤ Available
Check P1: Need = (1 4 5) ≤ Available (7 7 10) True
→ Allocate to P1 → Finish P1 → Release Allocation (2 2 3)
→ New Available = (7+2, 7+2, 10+3) = (9 9 13)
→ Safe sequence so far: P1
Check P2: Need = (2 3 0) ≤ (9 9 13) True
→ Allocate to p2 → Finish p2 → Release Allocation (2 0 3)
→ New Available = (9+2, 9+0, 13+3) = (11 9 16)
→ Safe sequence so far:P1 P2
Check P3: Need = (2 2 0) — ≤ (11 9 16) True
→ Allocate to P3 → Release (1 2 4)
→ New Available = (11+1 9+2 16+4) = (12 11 20)
→ Safe sequence: P1 P2 P3
Final Answer:
Need Matrix:
Jobs R1 R2 R3
P1 1 4 5
P2 2 3 0
P3 2 2 0
Safe Sequence:
P1 → P2 → P3
Assignment
1. For the following snapshot. Find the safe sequence using Banker’s algorithm.
Process Allocation Maximum Available
A B C A B C A B C
P0 0 0 2 0 0 4 1 0 2
P1 1 0 0 2 0 1
P2 1 3 5 1 3 7
P3 6 3 2 8 4 2
P4 1 4 3 1 5 7