Skip to content
GATETECH
Official PYQ · 1993Q7.9DeadlockMSQ1 mark

GATE CS 1993 Q7.9 — Deadlock

Explain with AI

Consider a system having mm resources of the same type. These resources are shared by 33 processes A,BA, B, and CC which have peak demands of 3,43, 4, and 66 respectively.  For what value of mm deadlock will not occur?

Select all correct options
View worked solution

Answer: D;E

To ensure that a deadlock will never occur, the total number of resources mm must be sufficient to guarantee that at least one process can satisfy its peak demand even in the worst-case allocation.

Let the peak demands of the three processes A,B,A, B, and CC be d1,d2,d_1, d_2, and d3d_3 respectively:

  • d1=3d_1 = 3
  • d2=4d_2 = 4
  • d3=6d_3 = 6

In the worst-case scenario, each process is allocated one resource less than its peak demand, and no resources are left to satisfy any process. The maximum number of resources that can be allocated in this deadlock state is:

∑i=1n(di−1)=(3−1)+(4−1)+(6−1)=2+3+5=10\sum_{i=1}^{n} (d_i - 1) = (3 - 1) + (4 - 1) + (6 - 1) = 2 + 3 + 5 = 10

If we add just 11 more resource to this state, at least one process will get its peak demand, complete its execution, and release its resources, thereby preventing deadlock. Thus, the condition for a deadlock-free system is:

m≥∑i=1n(di−1)+1m \ge \sum_{i=1}^{n} (d_i - 1) + 1 m≥10+1=11m \ge 10 + 1 = 11

Therefore, deadlock will not occur for any value of m≥11m \ge 11.

Evaluating the given options:

  • A. 7: 7<117 < 11 (Deadlock can occur)
  • B. 9: 9<119 < 11 (Deadlock can occur)
  • C. 10: 10<1110 < 11 (Deadlock can occur)
  • D. 13: 13≥1113 \ge 11 (Deadlock will not occur)
  • E. 15: 15≥1115 \ge 11 (Deadlock will not occur)

Thus, the correct options are D and E.

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

Published
Report a correction
Keep exploringMore Deadlock questions