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

Question

A system has four processes and five allocatable resources. The current allocation and maximum needs are as follows:
$$\begin{array}{|c|c|c|c|c|}\hline
\quad & \textbf{Allocation} & \textbf{Maximum} & \textbf{Available}
\\\hline \quad & A \quad B \quad C \quad D \quad E & A \quad B \quad C \quad D \quad E & A \quad B \quad C \quad D \quad E
\\\hline P_{0} & 1\quad 0 \quad 2 \quad 1 \quad 1 & 1 \quad 1 \quad 2 \quad 1 \quad 3 & 0 \quad 0 \quad x \quad 1 \quad 0
\\\hline P_{1} & 2 \quad 0 \quad 1 \quad 1\quad 0 & 2 \quad 2\quad 2 \quad 1\quad 1 & \quad
\\\hline P_{2} & 1 \quad 1 \quad 0 \quad 1\quad 0 & 2 \quad 1 \quad 3 \quad 1 \quad 0 & \quad
\\\hline P_{3} & 1 \quad 1 \quad 1 \quad 1\quad 0 & 1 \quad 1 \quad 2 \quad 2 \quad 1 & \quad
\\\hline \end{array}$$
The smallest value of $x$ for which the given state is a safe state, is ________

• A. $1$
• B. $2$
• C. $3$
• D. None of the above

Answer 1

The given state is not safe because the only process which can continue here is $P_2$ as every other process requires one or more instance of resource $E$ which is no longer available and process $P_2$ when completed is not releasing any more instance of $E.$ So, none of the other processes can continue here.

Correct Answer: D

Answer 2

A state is safe if the system can allocate all resources requested by all processes ( up to their stated maximums ) without entering a deadlock state.

$$\begin{array}{|c|c|c|c|c|}\hline
\quad & \textbf{Allocation} & \textbf{Maximum} & \textbf{Need}
\\\hline \quad & A \quad B \quad C \quad D \quad E & A \quad B \quad C \quad D \quad E & A \quad B \quad C \quad D \quad E
\\\hline P_{0} & 1\quad 0 \quad 2 \quad 1 \quad 1 & 1 \quad 1 \quad 2 \quad 1 \quad 3 & 0 \quad 1 \quad 0 \quad 0 \quad 2
\\\hline P_{1} & 2 \quad 0 \quad 1 \quad 1\quad 0 & 2 \quad 2\quad 2 \quad 1\quad 1 & 0 \quad 2 \quad 1 \quad 0 \quad 1
\\\hline P_{2} & 1 \quad 1 \quad 0 \quad 1\quad 0 & 2 \quad 1 \quad 3 \quad 1 \quad 0 & 1 \quad 0\quad 3 \quad 0 \quad 0
\\\hline P_{3} & 1 \quad 1 \quad 1 \quad 1\quad 0 & 1 \quad 1 \quad 2 \quad 2 \quad 1 & 0 \quad 0\quad 1\quad 1 \quad 1
\\\hline \end{array}$$

Available$: \overset{A}{0}\quad \overset{B}{0} \quad \overset{C}{x} \quad \overset{D}{1} \quad  \overset{E}{0}$

• The request $P_{0}:$  It will never be satisfied, because $B, E$ needs $1,2$ resource.
• The request $P_{1}:$  It will never be satisfied, because $B, E$ needs $2,1$ resource.
• The request $P_{2}:$  It will never be satisfied, because $A$ needs $1$ resource.
• The request $P_{3}:$  It will never be satisfied, because $E$ needs $1$ resource.

Irrespective of the value of $’x’,$ safe state is not possible.

a state is safe if there exists a safe sequence of processes $\{ P_{0}, P_{1}, P_{2}, \dots, P_{n} \}$ such that all of the resource requests for $P_{i}$ can be granted using the resources currently allocated to $P_{i}$ and all processes $P_{j}$ where $j < i.$ ( I.e. if all the processes prior to $P_{i}$ finish and free up their resources, then Pi will be able to finish also, using the resources that they have freed up. )

 $\text{Important Points:}$

• If a system is in a safe state, there is no deadlock.

• If the system is deadlocked, it is in an unsafe state.

• If a system is in an unsafe state, there is a possibility of a deadlock.

• Deadlock Avoidance: making sure the system will not enter an unsafe state.

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

Ref: https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/7_Deadlocks.html