Units needed to rule out deadlock — Aptitude Question
Units needed to rule out deadlock: Four processes share identical units of a single resource, and each process may… Answer and worked solution on CodeKairo.
- Topic: OS, DBMS & Networks
- Section: Programming MCQs
- Difficulty: Hard
- Time target: 135 seconds
Question
Four processes share identical units of a single resource, and each process may need up to 3 units to finish. What is the smallest number of units that makes deadlock impossible?
Options
- 7
- 8
- 9
- 12
Show the answer and the worked solution
Correct answer: C. 9
Worked solution
- The worst case has every process holding one unit short of its maximum, that is 2 units each.
- Four processes holding 2 units each account for 8 units, and none of them can proceed.
- With one more unit available, some process reaches its maximum of 3, finishes and releases everything it holds, so 9 units guarantee progress.
Answer: 9.
The idea
The general rule is P × (N − 1) + 1 units for P processes each needing at most N. It is the standard 'minimum resources for a deadlock-free system' question and appears in nearly every paper that covers deadlock.
Shortcut. 8 units is the largest pool that can still deadlock, every process stuck at 2 of its 3; one more unit always lets someone finish, so 9.
Common trap. 8 stops at the deadlocked allocation of 2 units each and forgets the extra unit that breaks the stalemate.