GATE Overflow Test Series | Operating Systems | Test 1 | Question: 28

Question

$5$ processes $P_{0}$ through $P_{4}; 3$ resource types $\text{A (10 instances), B (5 instances), and C (7 instances)}$
Snapshot at time $T_{0}:$
$$\begin{array}{|c|c|c|c|}\hline
\quad & \textbf{Allocation} & \textbf{Max} & \textbf{Available}
\\\hline \quad & A\quad B\quad C & A\quad B\quad C & A\quad B\quad C
\\\hline P_{0} & 0\quad 1\quad 0 & 7 \quad 5 \quad 3 & 3\quad 3\quad 2
\\ P_{1} & 2\quad 0\quad 0 & 3\quad 2\quad 2 & \quad
\\ P_{2} & 3\quad 0\;\; 2 & 9\quad 0\quad 2 & \quad
\\ P_{3} & 2\quad 1\quad 1 & 2\quad 2\quad 2 & \quad
\\ P_{4} & 0\quad 0\quad 2 & 4\quad 3\quad 3 & \quad
\\\hline \end{array}$$
The system is currently in a safe state. Consider the following independent requests for additional resources in the current state:
$\textbf{REQ1:}\;P_{0}$ requests $0$ units of $A, 2$ units of $B$ and $0$ units of $C$
$\textbf{REQ2:}\;P_{1}$ requests $1$ units of $A, 0$ units of $B$ and $2$ units of $C$
$\textbf{REQ3:}\; P_{4}$ requests $3$ units of $A, 3$ units of $B$ and $0$ units of $C$
Which one of the following is TRUE?

• A. Only $\text{REQ1 and REQ2}$ can be permitted.
• B. Only $\text{REQ2 and REQ3}$ can be permitted.
• C. All of $\text{REQ1, REQ2 and REQ3}$ can be permitted.
• D. None of $\text{REQ1, REQ2 or REQ3}$ can be permitted.

Answer 1

A system is in a safe state only if there exists a safe sequence of processes $P_{1}, P_{2},\dots , P_{n}$ where: For each $P_{i},$ the resources that $P_{i}$ can still request can be satisfied by the currently available resources plus the resources help by all $P_{j}, j<i.$

$$\begin{array}{|c|c|c|c|}\hline
\quad & \textbf{Allocation} & \textbf{Max} & \textbf{Need}
\\\hline \quad & A\quad B\quad C & A\quad B\quad C & A\quad B\quad C
\\\hline P_{0} & 0\quad 1\quad 0 & 7 \quad 5 \quad 3 &7 \quad 4\quad 3
\\ P_{1} & 2\quad 0\quad 0 & 3\quad 2\quad 2 & 1\quad 2\quad 2
\\ P_{2} & 3\quad 0\;\; 2 & 9\quad 0\quad 2 & 6 \quad 0 \quad 0
\\ P_{3} & 2\quad 1\quad 1 & 2\quad 2\quad 2 & 0 \quad 1 \quad 1
\\ P_{4} & 0\quad 0\quad 2 & 4\quad 3\quad 3 & 4 \quad 3 \quad 1
\\\hline \end{array}$$
Available$:\overset{A}{3}\quad \overset{B}{3} \quad \overset{C}{2}$

It is given in question that this is a safe state. Still, the proof for this is given at end. 

Now, $\textbf{REQ1:}\;P_{0}$ requests $0$ units of $A, 2$ units of $B$ and $0$ units of $C$

$$\begin{array}{|c|c|c|c|}\hline
\quad & \textbf{Allocation} & \textbf{Max} & \textbf{Need}
\\\hline \quad & A\quad B\quad C & A\quad B\quad C & A\quad B\quad C
\\\hline {\color{Red} {P_{0}}} & 0\quad  3 \quad 0 & 7 \quad 5 \quad 3 &7 \quad 2 \quad 3
\\ P_{1} & 2\quad 0\quad 0 & 3\quad 2\quad 2 & 1\quad 2\quad 2
\\ P_{2} & 3\quad 0\;\; 2 & 9\quad 0\quad 2 & 6 \quad 0 \quad 0
\\ P_{3} & 2\quad 1\quad 1 & 2\quad 2\quad 2 & 0 \quad 1 \quad 1
\\ P_{4} & 0\quad 0\quad 2 & 4\quad 3\quad 3 & 4 \quad 3 \quad 1
\\\hline \end{array}$$
Available$:\overset{A}{3}\quad \overset{B}{1} \quad \overset{C}{2}$

• $P_{3}’s$ requests can be satisfied and it’ll release $\left[2,1,1\right]$ instances of the three resources respectively.
  • New available$:\overset{A}{5}\quad \overset{B}{2} \quad \overset{C}{3}$
• $P_{1}’s$ requests can be satisfied and it’ll release $\left[2,0,0\right]$ instances of the three resources respectively.
  • New available$:\overset{A}{7}\quad \overset{B}{2} \quad \overset{C}{3}$
• $P_{0}’s$ requests can be satisfied and it’ll release $\left[0,3,0\right]$ instances of the three resources respectively.
  • New available$:\overset{A}{7}\quad \overset{B}{5} \quad \overset{C}{3}$
• $P_{2}’s$ requests can be satisfied and it’ll release $\left[3,0,2\right]$ instances of the three resources respectively.
  • New available$:\overset{A}{10}\quad \overset{B}{5} \quad \overset{C}{5}$
• $P_{4}’s$ requests can be satisfied and it’ll release $\left[0,0,2\right]$ instances of the three resources respectively.
  • New available$:\overset{A}{10}\quad \overset{B}{5} \quad \overset{C}{7}$

$\langle P_{3} , P_{1} , P_{0} , P_{2} , P_{4}\rangle$  is a safe sequence.

So, $\textbf{REQ1}$ can be permitted.

---

$\textbf{REQ2:}\;P_{1}$ requests $1$ units of $A, 0$ units of $B$ and $2$ units of $C$

$$\begin{array}{|c|c|c|c|}\hline
\quad & \textbf{Allocation} & \textbf{Max} & \textbf{Need}
\\\hline \quad & A\quad B\quad C & A\quad B\quad C & A\quad B\quad C
\\\hline P_{0} & 0\quad 1\quad 0 & 7 \quad 5 \quad 3 &7 \quad 4\quad 3
\\ {\color{Magenta} {P_{1}}} & 3\quad 0\quad 2 & 3\quad 2\quad 2 & 0 \quad 2\quad 0
\\ P_{2} & 3\quad 0\;\; 2 & 9\quad 0\quad 2 & 6 \quad 0 \quad 0
\\ P_{3} & 2\quad 1\quad 1 & 2\quad 2\quad 2 & 0 \quad 1 \quad 1
\\ P_{4} & 0\quad 0\quad 2 & 4\quad 3\quad 3 & 4 \quad 3 \quad 1
\\\hline \end{array}$$
Available$:\overset{A}{2}\quad \overset{B}{3} \quad \overset{C}{0}$

• $P_{1}’s$ requests can be satisfied and it’ll release $\left[3,0,2\right]$ instances of the three resources respectively.
  • New available$:\overset{A}{5}\quad \overset{B}{3} \quad \overset{C}{2}$
• $P_{3}’s$ requests can be satisfied and it’ll release $\left[2,1,1\right]$ instances of the three resources respectively.
  • New available$:\overset{A}{7}\quad \overset{B}{4} \quad \overset{C}{3}$
• $P_{2}’s$ requests can be satisfied and it’ll release $\left[3,0,2\right]$ instances of the three resources respectively.
  • New available$:\overset{A}{10}\quad \overset{B}{4} \quad \overset{C}{5}$
• $P_{0}’s$ requests can be satisfied and it’ll release $\left[0,1,0\right]$ instances of the three resources respectively.
  • New available$:\overset{A}{10}\quad \overset{B}{5} \quad \overset{C}{5}$
• $P_{4}’s$ requests can be satisfied and it’ll release $\left[0,0,2\right]$ instances of the three resources respectively.
  • New available$:\overset{A}{10}\quad \overset{B}{5} \quad \overset{C}{7}$

$\langle P_{1} , P_{3} , P_{2} , P_{0} , P_{4}\rangle$  is a safe sequence.

So, $\textbf{REQ2}$ can be permitted.

---

$\textbf{REQ3:}\;P_{4}$ requests $3$ units of $A, 3$ units of $B$ and $0$ units of $C$
$$\begin{array}{|c|c|c|c|}\hline
\quad & \textbf{Allocation} & \textbf{Max} & \textbf{Need}
\\\hline \quad & A\quad B\quad C & A\quad B\quad C & A\quad B\quad C
\\\hline P_{0} & 0\quad 1\quad 0 & 7 \quad 5 \quad 3 &7 \quad 4\quad 3
\\ P_{1} & 2\quad 0\quad 0 & 3\quad 2\quad 2 & 1\quad 2\quad 2
\\ P_{2} & 3\quad 0\;\; 2 & 9\quad 0\quad 2 & 6 \quad 0 \quad 0
\\ P_{3} & 2\quad 1\quad 1 & 2\quad 2\quad 2 & 0 \quad 1 \quad 1
\\ {\color{Teal} {P_{4}}} & 3\quad 3\quad 2 & 4\quad 3\quad 3 & 1 \quad 0 \quad 1
\\\hline \end{array}$$

Available$:\overset{A}{0}\quad \overset{B}{0} \quad \overset{C}{2}$

At this point of time, no process’s requests can be fully satisfied, and so the state is not safe. So, $\text{REQ3}$ cannot be permitted.

So, the correct answer is $(A).$

---

Proof for the given state being safe:

• $P_{1}’s$ requests can be satisfied and it’ll release $\left[2,0,0 \right]$ instances of the three resources respectively.
  • New available$:\overset{A}{5}\quad \overset{B}{3} \quad \overset{C}{2}$
• $P_{3}’s$ requests can be satisfied and it’ll release $\left[2,1,1\right] $ instances of the three resources respectively.
  • New available$:\overset{A}{7}\quad \overset{B}{4} \quad \overset{C}{3}$
• $P_{4}’s$ requests can be satisfied and it’ll release $\left[0, 0,2\right] $ instances of the three resources respectively.
  • New available$:\overset{A}{7}\quad \overset{B}{4} \quad \overset{C}{5}$
• $P_{2}’s$ requests can be satisfied and it’ll release $\left[3,0,2 \right]$ instances of the three resources respectively.
  • New available$:\overset{A}{10}\quad \overset{B}{4} \quad \overset{C}{7}$
• $P_{0}’s$ requests can be satisfied and it’ll release $\left[0 ,1,0 \right]$ instances of the three resources respectively.
  • New available$:\overset{A}{10}\quad \overset{B}{5} \quad \overset{C}{7}$

$\langle P_{1} , P_{3} , P_{4} , P_{2} , P_{0}\rangle$  is a safe sequence.

Comments

@gatecse @Lakshman in request1 process p0 needs 2 additional resources of instance B so it should be added in need matrix? why have we allocated them to p0 partially ?

If it will go in need matrix then it will need total 6 instances of B which can not be fullfilled and req1 can not be permitted.

I am confused why have u allocated the requested resources directly.

---

@Lakshman Patel RJIT  @gatecseAs per question “independent requests for additional resources”, we must have to increase the need of that specific process. Mean as P0 need (7,4,3) resources before addition resources request, after additional request need must be (7,6,3). After that we should to check either that request is permitted or not. Please reply if you think my understanding is wrong.

---

https://gateoverflow.in/1800/gate-cse-2014-set-1-question-31?start=0#a_list_title

(similar question to clear misconception)