describe your understadings about Banker's Algorithm, and give your own demo example.

 

There are three types of resources A, B, C and five processes P1, P2, P3, P4, P5, A resource 17, B resource 5, C resource 20 in the system. The current (time T0) system resource allocation and process maximum requirements are shown in the table below.

Resource Process	Allocation	Max
	A  B  C	A  B  C
P1	2  1  2	5  5  9
P2	4  0  2	5  3  6
P3	4  0  5	4  0  11
P4	2  0  4	4  2  5
P5	3  1  4	4        2  4

1、Is the system T0 now in a safe state?

2. Can the following requests be allowed?

(1) Time T1: P2 Request2 = (0,3,4)

(2) Time T2: P4 Request4 = (2,0,1)

(3) Time T3: P1 Request1 = (0,2,0)

Note: T0, T1, T2, and T3 are sequential.

Solution: Need = Max-Allocation

AvailableA = 17- (2 + 4 + 4 + 2 + 3) = 2 (Original-Distribution)

Similarly, AvailableB = 3, AvailableC = 3

The available resource allocation table at time T0 is as follows (the data order in the table is A B C):

Process	Allocation	Max	Need	Available
P1	2  1  2	5  5  9	3  4  7	2  3  3
P2	4  0  2	5  3  6	1  3  4
P3	4  0  5	4  0  11	0  0  6
P4	2  0  4	4  2  5	2  2  1
P5	3  1  4	4  2  4	1  1  0

1、To determine whether it is safe at time T0, a security algorithm needs to be executed to find a safe sequence. The process is as follows:

	Work	Need	Allocation	Work+Allocation	Finish
P4	2   3   3	2  2  1	2  0  4	4   3   7	True
P3	4   3   7	0  0  6	4  0  5	8   3  12	True
P2	8   3  12	1  3  4	4  0  2	12  3  14	True
P5	12  3  14	1  1  0	3  1  4	15  4  18	True
P1	15  4  18	3  4  7	2  1  2	17  5  20	True

A safe sequence {P4, P3, P2, P5, P1} can be found at T0, so the system is in a safe state at T0.

 

2、Determine whether T1, T2, or T3 meet the process request for resource allocation.

(1) At T1, P2 Request2 = (0,3,4)

① Meet Request2 = (0,3,4) <= Need2 (1,3,4)

② Request2 = (0,3,4) <= Available (2,3,3)

Therefore, the system cannot allocate resources to it, and P2 must wait at this time.

 

(2) At T2, P4 Request4 = (2,0,1)

① Meet Request4 = (2,0,1) <= Need4 (2,2,1)

② satisfy Request4 = (2,0,1) <= Available (2,3,3)

 

Available = Available-Request4 = (0,3,2)

Allocation4 = Allocation4 + Request4 = (4,0,5)

Need4 = Need4-Request4 = (0,2,0)

 

	Work	Need	Allocation	Work+Allocation	Finish
P4	0   3   2	0  2  0	4  0  5	4   3   7	True
P2	4   3   7	1  3  4	4  0  2	8   3   9	True
P3	8   3   9	0  0  6	4  0  5	12  3  14	True
P5	12  3  14	1  1  0	3  1  4	15  4  18	True
P1	15  4  18	3  4  7	2  1  2	17  5  20	True

// Step 4 At this time (time T2), there is a security sequence {P4, P2, P3, P5, P1}, then the Request4 request is satisfied, and Request4 = (2,0,1) is assigned to P4.

 

(3) At T3, P1 Request1 = (0,2,0)

② satisfy Request1 = (0,2,0) <= Available (2,3,3)

Available = Available-Request1 = (0,1,2) (based on time T2)

Allocation = Allocation1 + Request1 = (2,3,0)

Need1 = Need1-Request1 = (3,2,7)

For all Needi is not less than Work (the initial value is Available (0,1,2)), no security sequence can be found, so the system cannot allocate resources to it, and P1 must wait.