GateAI
Deadlock

GATE CSE 2014 Set 1 · Q31

MCQ2 marksMedium

Time

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. 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**?

GATE CSE 2014 Set 1 Q31 diagram

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: B) Only REQ2 can be permitted.

Deadlock

From the given table, we calculate the Need matrix (extNeed=extMax−extAllocation ext{Need} = ext{Max} - ext{Allocation}):

  • Need(P0)=(8−0,  4−0,  3−1)=(8,4,2)\text{Need}(P_0) = (8 - 0,\; 4 - 0,\; 3 - 1) = (8, 4, 2)

  • Need(P1)=(6−3,  2−2,  0−0)=(3,0,0)\text{Need}(P_1) = (6 - 3,\; 2 - 2,\; 0 - 0) = (3, 0, 0)

  • Need(P2)=(3−2,  3−1,  3−1)=(1,2,2)\text{Need}(P_2) = (3 - 2,\; 3 - 1,\; 3 - 1) = (1, 2, 2)

Currently, Available=(3,2,2)\text{Available} = (3, 2, 2).

---

### Analyzing REQ1: P0P_0 requests (0,0,2)(0, 0, 2).

  • Request ≤Need(P0)\le \text{Need}(P_0) and Request ≤Available\le \text{Available}.

  • If granted tentatively:

    • Allocation(P0)=(0,0,3)\text{Allocation}(P_0) = (0, 0, 3)

    • Need(P0)=(8,4,0)\text{Need}(P_0) = (8, 4, 0)

    • Available=(3,2,2)−(0,0,2)=(3,2,0)\text{Available} = (3, 2, 2) - (0, 0, 2) = (3, 2, 0)

Now, test for a safe sequence:

  • $Need\text{Need}(P_0) = (8, 4, 0)

leq (3, 2, 0)$

  • Need(P1)=(3,0,0)≤(3,2,0)  ⟹  P1\text{Need}(P_1) = (3, 0, 0) \le (3, 2, 0) \implies P_1 finishes, new Available=(3,2,0)+(3,2,0)=(6,4,0)\text{Available} = (3, 2, 0) + (3, 2, 0) = (6, 4, 0)

  • Now:

    • $Need\text{Need}(P_0) = (8, 4, 0)

leq (6, 4, 0)− - Need\text{Need}(P_2) = (1, 2, 2) leq (6, 4, 0)(since (since Zhas has 0availablebutrequires available but requires 2$)

  • Neither P0P_0 nor P2P_2 can proceed. Hence, the system enters an unsafe state.

  • Therefore, REQ1 cannot be permitted.

---

### Analyzing REQ2: P1P_1 requests (2,0,0)(2, 0, 0).

  • Request ≤Need(P1)\le \text{Need}(P_1) and Request ≤Available\le \text{Available}.

  • If granted tentatively:

    • Allocation(P1)=(5,2,0)\text{Allocation}(P_1) = (5, 2, 0)

    • Need(P1)=(1,0,0)\text{Need}(P_1) = (1, 0, 0)

    • Available=(3,2,2)−(2,0,0)=(1,2,2)\text{Available} = (3, 2, 2) - (2, 0, 0) = (1, 2, 2)

Now, test for a safe sequence:

  • Need(P1)=(1,0,0)≤(1,2,2)  ⟹  P1\text{Need}(P_1) = (1, 0, 0) \le (1, 2, 2) \implies P_1 finishes, new Available=(1,2,2)+(5,2,0)=(6,4,2)\text{Available} = (1, 2, 2) + (5, 2, 0) = (6, 4, 2)

  • Next, Need(P2)=(1,2,2)≤(6,4,2)  ⟹  P2\text{Need}(P_2) = (1, 2, 2) \le (6, 4, 2) \implies P_2 finishes, new Available=(6,4,2)+(2,1,1)=(8,5,3)\text{Available} = (6, 4, 2) + (2, 1, 1) = (8, 5, 3)

  • Next, Need(P0)=(8,4,2)≤(8,5,3)  ⟹  P0\text{Need}(P_0) = (8, 4, 2) \le (8, 5, 3) \implies P_0 finishes.

  • A safe sequence ⟨P1,P2,P0⟩\langle P_1, P_2, P_0 \rangle exists.

  • Therefore, REQ2 can be permitted.

Thus, Only REQ2 can be permitted (Option B).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Deadlock previous year question is Q31 of the GATE CSE 2014 Set 1 paper. Find more GATE CSE PYQs on Deadlock in Operating Systems, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Deadlock PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Deadlock in GATE CSE

Deadlock has 11 GATE CSE PYQs across 10 papers from 2014 to 2026. 4 of them are 2-mark MCQs like this one, and it is the only one in GATE CSE 2014 Set 1.

How GATE tests Deadlock

More from GATE CSE 2014 Set 1

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2014 Set 1 · Q31 · MCQ

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. 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?

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.