In a certain operating system, deadlock prevention is attempted using the…
2004
In a certain operating system, deadlock prevention is attempted using the following scheme. Each process is assigned a unique timestamp, and is restarted with the same timestamp if killed. Let Ph be the process holding a resource R, Pr be a process requesting for the same resource R, and T(Ph) and T(Pr) be their timestamps respectively. The decision to wait or preempt one of the processes is based on the following algorithm.
if T(Pr) < T(Ph)
then kill Pr
else wait
Which one of the following is TRUE?
- A.
The scheme is deadlock-free, but not starvation-free
- B.
The scheme is not deadlock-free, but starvation-free
- C.
The scheme is neither deadlock-free nor starvation-free
- D.
The scheme is both deadlock-free and starvation-free
Attempted by 162 students.
Show answer & explanation
Correct answer: A
Answer: The scheme is deadlock-free but not starvation-free
Reasoning:
The scheme kills the requester when the requester is older than the holder (requester timestamp < holder timestamp); otherwise the requester waits. Therefore a requester only waits when it is younger than the holder (requester timestamp > holder timestamp).
Any wait edge goes from a process with a larger timestamp to one with a smaller timestamp, so timestamps strictly decrease along any chain of waiting processes. A strictly decreasing sequence of unique timestamps cannot form a cycle, so deadlock (a cycle of waiting) cannot occur.
Starvation is possible: an older process requesting resources held by younger processes will be killed and restarted with the same timestamp; if younger processes repeatedly hold needed resources, the older process can be killed again and may never make progress.
Conclusion: Deadlock is prevented by the timestamp rule, but the scheme does not guarantee starvation-freedom.
A video solution is available for this question — log in and enroll to watch it.