Scribd
Upload
294 views15 pages

Banker's Algorithm Safety Analysis

The document describes 4 problems involving the Banker's algorithm for process synchronization. In Problem 1, it analyzes 3 scenarios where it checks if the system is safe by simulating the Banker's algorithm. In Problem 2, it determines the system is safe when given the allocation, maximum needs, and available resources for 5 processes and 3 resource types. Problem 3 checks if two specific process requests can be granted safely.

Uploaded by

Hoàng Nguyễn
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
294 views15 pages

Banker's Algorithm Safety Analysis

The document describes 4 problems involving the Banker's algorithm for process synchronization. In Problem 1, it analyzes 3 scenarios where it checks if the system is safe by simulating the Banker's algorithm. In Problem 2, it determines the system is safe when given the allocation, maximum needs, and available resources for 5 processes and 3 resource types. Problem 3 checks if two specific process requests can be granted safely.

Uploaded by

Hoàng Nguyễn
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Problem 1.

 A system has 16 tapes, and 4 processes P , P , P , P with corresponding requests:


0 1 2 3
 P0 requests at most 10 tapes
 P1 requests at most 4 tapes
 P2 requests at most 9 tapes
 P3 requests at most 5 tapes
 At t , P has 5 tapes, P and P each has 2 tapes , P has 3 tape
0 0 1 2 3
 4 tapes available
 Is the system safe with Banker’s algorithm?
Max = [10, 4, 9, 5]
Allocation = [5, 2, 2, 3]
Need = [5, 2, 7, 2]
Work = [4]; Finish = [F, F, F, F]
P1
Work += Allocation[1] = 6; Finish = [F, T, F, F]
P0
Work += Allocation[0] = 11; Finish = [T, T, F, F]
P2
Work += Allocation[2] = 13; Finish = [T, T, T, F]
P3
Work += Allocation[3] = 16; Finish = [T, T, T, T]
Not found
Finish = [T, T, T, T] -> Safety
 At t , P has 7 tapes, P and P each has 2 tapes , P has 3 tape
1 0 1 2 3
 2 tapes available
 Is the system safe with Banker’s algorithm?
Max = [10, 4, 9, 5]
Allocation = [7, 2, 2, 3]
Need = [3, 2, 7, 2]
Work = [2]; Finish = [F, F, F, F]
P1
Work += Allocation[1] = 4; Finish = [F, T, F, F]
P0
Work += Allocation[0] = 11; Finish = [T, T, F, F]
P2
Work += Allocation[2] = 13; Finish = [T, T, T, F]
P3
Work += Allocation[3] = 16; Finish = [T, T, T, T]
Not found
Finish = [T, T, T, T] -> Safety
 At t , P has 7 tapes, P has 3 tapes, P each has 2 tapes, P has 3 tape
2 0 1 2 3
 1 tapes available
 Is the system safe with Banker’s algorithm?
Max = [10, 4, 9, 5]
Allocation = [7, 3, 2, 3]
Need = [3, 1, 7, 2]
Work = [1]; Finish = [F, F, F, F]
P1
Work += Allocation[1] = 4; Finish = [F, T, F, F]
P0
Work += Allocation[0] = 11; Finish = [T, T, F, F]
P2
Work += Allocation[2] = 13; Finish = [T, T, T, F]
P3
Work += Allocation[3] = 16; Finish = [T, T, T, T]
Not found
Finish = [T, T, T, T] -> Safety

 At t , P has 7 tapes, P has 3 tapes, P each has 2 tapes, P has 4 tape


3 0 1 2 3
 0 tape available
 Is the system safe with Banker’s algorithm?
Max = [10, 4, 9, 5]
Allocation = [7, 3, 2, 4]
Need = [3, 1, 7, 1]
Work = [0]; Finish = [F, F, F, F]
Not found
Finish = [F, F, F, F] -> Unsafety
Problem 2
 5 processes: P - P 3 resource types
0 4;
 A (10 instances), B (5 instances), and C (7 instances)
 At time T :
0
Allocation Max Available
ABC ABC ABC
P0 110 753 332

P1 100 322

P2 202 902

P3 211 222

P4 102 433
Is the system safe with banker’s algorithm?
Max = [[7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3]]
Allocation = [[1, 1, 0], [1, 0, 0], [2, 0, 2], [2, 1, 1], [1, 0, 2]]
Need = [[6, 4, 3], [2, 2, 2], [7, 0, 0], [0, 1, 1], [3, 3, 1]]
Work = [3, 3, 2]; Finish = [F, F, F, F, F]
P1
Work += Allocation[1] = [4, 3, 2]; Finish = [F, T, F, F, F]
P3
Work += Allocation[3] = [6, 4, 3]; Finish = [F, T, F, T, F]
P0
Work += Allocation[0] = [7, 5, 3]; Finish = [T, T, F, T, F]
P2
Work += Allocation[2] = [9, 5, 5]; Finish = [T, T, T, T, F]
P4
Work += Allocation[4] = [10, 5, 7]; Finish = [T, T, T, T, T]
Not found
Finish = [T, T, T, T, T] -> Safety
PROBLEM 3
 5 processes: P - P 3 resource types
0 4;
 A (10 instances), B (5 instances), and C (7 instances)
Allocation Max Available
ABC ABC ABC
P0 012 753 332

P1 200 322

P2 301 902

P3 211 222

P4 001 433
 If P1 requests for (1,0,2) => can it be granted?
Max = [[7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3]]
Allocation = [[0, 1, 2], [2, 0, 0], [3, 0, 1], [2, 1, 1], [0, 0, 1]]
Need = [[7, 4, 1], [1, 2, 2], [6, 0, 1], [0, 1, 1], [4, 3, 2]]
Available = [3, 3, 2]
Request[1] = [1, 0, 2] < Need[1]
Allocation[1] += Request[1] = [3, 0, 2]
Need[1] -= Request[1] = [0, 2, 0]
Available -= Request[1] = [2, 3, 0]
Call Banker’s algorithm
Work = [2, 3, 0]; Finish = [F, F, F, F, F]
P1
Work += Allocation[1] = [5, 3, 2]; Finish = [F, T, F, F, F]
P3
Work += Allocation[3] = [7, 4, 3]; Finish = [F, T, F, T, F]
P0
Work += Allocation[0] = [7, 5, 5]; Finish = [T, T, F, T, F]
P2
Work += Allocation[2] = [10, 5, 6]; Finish = [T, T, T, T, F]
P4
Work += Allocation[2] = [10, 5, 7]; Finish = [T, T, T, T, T]
Not found
Finish = [T, T, T, T, T] -> safety
Exit()

 If P4 requests for (1,0,0) => can it be granted?


Max = [[7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3]]
Allocation = [[0, 1, 2], [2, 0, 0], [3, 0, 1], [2, 1, 1], [0, 0, 1]]
Need = [[7, 4, 1], [1, 2, 2], [6, 0, 1], [0, 1, 1], [4, 3, 2]]
Available = [3, 3, 2]
Request[4] = [1, 0, 0] < Need[4]
Allocation[4] += Request[4] = [1, 0, 1]
Need[4] -= Request[4] = [3, 3, 2]
Available -= Request[4] = [2, 3, 2]
Call Banker’s algorithm
Work = [2, 3, 2]; Finish = [F, F, F, F, F]
P1
Work += Allocation[1] = [4, 3, 2]; Finish = [F, T, F, F, F]
P3
Work += Allocation[3] = [6, 4, 3]; Finish = [F, T, F, T, F]
P2
Work += Allocation[2] = [9, 4, 4]; Finish = [F, T, T, T, F]
P0
Work += Allocation[0] = [9, 5, 6]; Finish = [T, T, T, T, F]
P4
Work += Allocation[4] = [10, 5, 7]; Finish = [T, T, T, T, T]
Not found
Finish = [T, T, T, T, T] -> safety
Exit()

 If P0 requests for (0, 2, 0) => can it be granted?


Max = [[7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3]]
Allocation = [[0, 1, 2], [2, 0, 0], [3, 0, 1], [2, 1, 1], [0, 0, 1]]
Need = [[7, 4, 1], [1, 2, 2], [6, 0, 1], [0, 1, 1], [4, 3, 2]]
Available = [3, 3, 2]
Request[0] = [0, 2, 0] < Need[0]
Allocation[0] += Request[0] = [0, 3, 2]
Need[0] -= Request[0] = [7, 2, 1]
Available -= Request[0] = [3, 1, 2]
Call Banker’s algorithm
Work = [3, 1, 2]; Finish = [F, F, F, F, F]
P3
Work += Allocation[3] = [5, 2, 3]; Finish = [F, F, F, T, F]
P1
Work += Allocation[1] = [7, 2, 3]; Finish = [F, T, F, T, F]
P0
Work += Allocation[0] = [7, 5, 5]; Finish = [T, T, F, T, F]
P2
Work += Allocation[2] = [10, 5, 6]; Finish = [T, T, T, T, F]
P4
Work += Allocation[4] = [10, 5, 7]; Finish = [T, T, T, T, T]
Not found
Finish = [T, T, T, T, T] -> safety
Exit()
 If P1 requests for (1,0,2) => can it be granted
If P1’s request is granted, can the next request for (1,0,0) by P4 be granted?
Max = [[7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3]]
Allocation = [[0, 1, 2], [3, 0, 2], [3, 0, 1], [2, 1, 1], [0, 0, 1]]
Need = [[7, 4, 1], [0, 2, 0], [6, 0, 1], [0, 1, 1], [4, 3, 2]]
Available = [2, 3, 0]
Request[4] = [1, 0, 0] < Need[4]
Allocation[4] += Request[4] = [1, 0, 1]
Need[4] -= Request[4] = [3, 3, 2]
Available -= Request[4] = [1, 3, 0]
Call Banker’s algorithm
Work = [1, 3, 0]; Finish = [F, F, F, F, F]
P1
Work += Allocation[1] = [4, 3, 2]; Finish = [F, T, F, F, F]
P3
Work += Allocation[3] = [6, 4, 3]; Finish = [F, T, F, T, F]
P2
Work += Allocation[2] = [9, 4, 4]; Finish = [F, T, T, T, F]
P0
Work += Allocation[0] = [9, 5, 6]; Finish = [T, T, T, T, F]
P4
Work += Allocation[4] = [10, 5, 7]; Finish = [T, T, T, T, T]
Not found
Finish = [T, T, T, T, T] -> safety
Exit()

 If P1 requests for (1,0,2) => can it be granted


 If P1’s request is granted, can the request for (0,2,0) by P0 be granted?
Max = [[7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3]]
Allocation = [[0, 1, 2], [3, 0, 2], [3, 0, 1], [2, 1, 1], [0, 0, 1]]
Need = [[7, 4, 1], [0, 2, 0], [6, 0, 1], [0, 1, 1], [4, 3, 2]]
Available = [2, 3, 0]
Request[0] = [0, 2, 0] < Need[0]
Allocation[0] += Request[0] = [0, 3, 2]
Need[0] -= Request[0] = [7, 2, 1]
Available -= Request[0] = [2, 1, 0]
Call Banker’s algorithm
Work = [2, 1, 0]; Finish = [F, F, F, F, F]
Not found
Finish = [F, F, F, F, F] -> unsafety
Restore resource
Allocation[0] -= Request[0] = [0, 1, 2]
Need[0] += Request[0] = [7, 4, 1]
Available += Request[0] = [2, 3, 0]

PROBLEM 4

 5 processes: P - P 3 resource types


0 4;
 A (10 instances), B (5 instances), and C (7 instances)
 At snapshot at time T0
Allocation Request Available
ABC ABC ABC
P0 010 100 431
P1 200 202
P2 203 000
P3 211 100
P4 002 002
 Is there a deadlock at T ?
0
Work = [4, 3, 1]; Finish = [F, F, F, F, F]
P0
Work += Allocation[0] = [4, 4, 1]; Finish = [T, F, F, F, F]
P2
Work += Allocation[2] = [6, 4, 4]; Finish = [T, F, T, F, F]
P1
Work += Allocation[1] = [8, 4, 4]; Finish = [T, T, T, F, F]
P3
Work += Allocation[3] = [10, 5, 5]; Finish = [T, T, T, T, F]
P4
Work += Allocation[4] = [10, 5, 7]; Finish = [T, T, T, T, T]
No deadlock
 If P2 request (0, 0, 1), is there a deadlock?

Work = [4, 3, 1]; Finish = [F, F, F, F, F]


P0
Work += Allocation[0] = [4, 4, 1]; Finish = [T, F, F, F, F]
P2
Work += Allocation[2] = [6, 4, 4]; Finish = [T, F, T, F, F]
P1
Work += Allocation[1] = [8, 4, 4]; Finish = [T, T, T, F, F]
P3
Work += Allocation[3] = [10, 5, 5]; Finish = [T, T, T, T, F]
P4
Work += Allocation[4] = [10, 5, 7]; Finish = [T, T, T, T, T]
No deadlock

You might also like