An operating system uses the Banker's algorithm for deadlock avoidance when… — GATE CS 2014 Set 1 Q31

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.

$\overset{\Large{\textbf{Allocation}}}{\begin{array}{|l|ll|} \hline & X & Y & Z \\ \hline \textbf{P0} & 0 & 0 & 1 \\ \textbf{P1} & 3 & 2 & 0 \\ \textbf{P2} & 2 & 1 & 1 \\ \hline \end{array}}\quad \qquad \overset{\Large{\textbf{Max}}}{\begin{array}{|ll|} \hline X & Y & Z \\ \hline 8 & 4 & 3 \\ 6 & 2 & 0 \\ 3 & 3 & 3 \\ \hline \end{array}}$
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?

View worked solution

Answer: B

To determine which requests can be permitted, we first calculate the Need matrix using the formula $\text{Need} = \text{Max} - \text{Allocation}$ :

\begin{array}{c|ccc} \text{Process} & X & Y & Z \\ \hline P0 & 8 & 4 & 2 \\ P1 & 3 & 0 & 0 \\ P2 & 1 & 2 & 2 \\ \end{array}

The current available resources are $\text{Available} = [3, 2, 2]$ .

Evaluating REQ1: $P0$ requests $[0, 0, 2]$ .

Since $\text{Request} \le \text{Need}$ ( $[0, 0, 2] \le [8, 4, 2]$ ) and $\text{Request} \le \text{Available}$ ( $[0, 0, 2] \le [3, 2, 2]$ ), we temporarily allocate the resources.
New $\text{Available} = [3, 2, 2] - [0, 0, 2] = [3, 2, 0]$ .
New Allocation for $P0 = [0, 0, 3]$ , and new Need for $P0 = [8, 4, 0]$ .
With $\text{Available} = [3, 2, 0]$ , only $P1$ (Need $[3, 0, 0]$ ) can execute. After $P1$ finishes, $\text{Available}$ becomes $[3, 2, 0] + [3, 2, 0] = [6, 4, 0]$ .
Now, neither $P0$ (Need $[8, 4, 0]$ ) nor $P2$ (Need $[1, 2, 2]$ ) can be satisfied. The system is in an unsafe state. Thus, REQ1 cannot be permitted.

Evaluating REQ2: $P1$ requests $[2, 0, 0]$ .

Since $\text{Request} \le \text{Need}$ ( $[2, 0, 0] \le [3, 0, 0]$ ) and $\text{Request} \le \text{Available}$ ( $[2, 0, 0] \le [3, 2, 2]$ ), we temporarily allocate the resources.
New $\text{Available} = [3, 2, 2] - [2, 0, 0] = [1, 2, 2]$ .
New Allocation for $P1 = [5, 2, 0]$ , and new Need for $P1 = [1, 0, 0]$ .
With $\text{Available} = [1, 2, 2]$ , we can satisfy $P1$ (Need $[1, 0, 0]$ ). After $P1$ finishes, $\text{Available}$ becomes $[1, 2, 2] + [5, 2, 0] = [6, 4, 2]$ .
Next, we can satisfy $P2$ (Need $[1, 2, 2]$ ). After $P2$ finishes, $\text{Available}$ becomes $[6, 4, 2] + [2, 1, 1] = [8, 5, 3]$ .
Finally, we can satisfy $P0$ (Need $[8, 4, 2]$ ).
Since a safe sequence $\langle P1, P2, P0 \rangle$ exists, the system remains in a safe state. Thus, REQ2 can be permitted.

Free practice · Your answers on this page are not saved.

GATE CS 2014 Set 1 Q31 — Deadlock

Related questions