Question

An operating system uses the Banker’s algorithm for deadlock avoidance when managing the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table given below presents the current system state. Here, the Allocation matrix shows the current number of resources of each type allocated to each process and the Max matrix shows the maximum number of resources of each type required by each process during its execution.

	Allocation			Max
	X	Y	Z	X	Y	Z
P0	0	0	1	8	4	3
P1	3	2	0	6	2	0
P2	2	1	1	3	3	3

 

There are 3 units of type X, 2 units of type Y and 2 units of type Z still available. The system is currently in a safe state. Consider the following independent requests for additional resources in the current state:

REQ1: P0 requests 0 units of X, 0 units of Y and 2 units of Z

REQ2: P1 requests 2 units of X, 0 units of Y and 0 units of Z

Which one of the following is TRUE?

1. Only REQ1 can be permitted
2. Only REQ2 can be permitted.
3. Both REQ1 and REQ2 can be permitted
4. Neither REQ1 nor REQ2 can be permitted

Answer 1

Correct Answer - Option 2 : Only REQ2 can be permitted.

Concept:

Using banker’s algorithm, we will find the Need matrix and with the available resources, we will try to come up a feasible sequence of process completion.

Explanation:

	Allocation			Max			Need
	X	Y	Z	X	Y	Z	X	Y	Z
P0	0	0	1	8	4	3	8	4	2
P1	3	2	0	6	2	0	3	0	0
P2	2	1	1	3	3	3	1	2	2
Available X = 3, Y = 2, Z = 2

 

REQ1 asks X = 0, Y = 0, Z = 2 for P0

Now, if the request REQ1 is permitted, the state would become:

	Allocation			Max			Need
	X	Y	Z	X	Y	Z	X	Y	Z
P0	0	0	3	8	4	3	8	4	2
P1	3	2	0	6	2	0	3	0	0
P2	2	1	1	3	3	3	1	2	2
Available X = 3, Y = 2, Z = 0

 

Notice that in table P0’s allocated Z becomes 3 from 1 and Available resources of Z reduce to 0 from 2.

With the above table, we can use available resources to service P1. 

	Allocation			Max			Need
	X	Y	Z	X	Y	Z	X	Y	Z
P0	0	0	3	8	4	3	8	4	2
P1	3	2	0	6	2	0	0	0	0
P2	2	1	1	3	3	3	1	2	2
Available X = 3, Y = 2, Z = 0 becomes Available X = 6, Y = 4, Z = 0

 

With 0 instances of Z being available, no requests of P0 or P2 can be fulfilled, hence the system is in deadlock.

Therefore, REQ1 cannot be permitted.

REQ2 asks X = 2, Y = 0, Z = 0 for P1

Now, if the request REQ2 is permitted, the state would become:

	Allocation			Max			Need
	X	Y	Z	X	Y	Z	X	Y	Z
P0	0	0	3	8	4	3	8	4	2
P1	5	2	0	6	2	0	1	0	0
P2	2	1	1	3	3	3	1	2	2
Available X = 1, Y = 2, Z = 2

 

Notice that in table P1’s allocated X becomes 5 from 3 and Available resources of X reduce to 1 from 3.

With the above table, we can use available resources to service P1. (P2 can also be serviced)

	Allocation			Max			Need
	X	Y	Z	X	Y	Z	X	Y	Z
P0	0	0	1	8	4	3	8	4	2
P1	5	2	0	6	2	0	0	0	0
P2	2	1	1	3	3	3	1	2	2
Available X = 1, Y = 2, Z = 2 becomes Available X = 6, Y = 4, Z = 2

 

With the above available instances, P2 can be services and then P0.

Final table will look like, 

	Allocation			Max			Need
	X	Y	Z	X	Y	Z	X	Y	Z
P0	0	0	1	8	4	3	0	0	0
P1	5	2	0	6	2	0	0	0	0
P2	2	1	1	3	3	3	0	0	0
Available X = 1, Y = 2, Z = 2 becomes Available X = 6, Y = 4, Z = 2

 

Therefore, REQ1 can be permitted.