In a database system, unique timestamps are assigned to each transaction using…
2017
In a database system, unique timestamps are assigned to each transaction using Lamport's logical clock. Let \(TS(T_1)\) and \(TS(T_2)\) be the timestamps of transactions \(T_1\) and \(T_2\) respectively. Besides, \(T_1\) holds a lock on the resource \(R\), and \(T_2\) has requested a conflicting lock on the same resource \(R\). The following algorithm is used to prevent deadlocks in the database system assuming that a killed transaction is restarted with the same timestamp.
if \(TS(T_2)\) < \(TS(T_1)\) then\(T_1\) is killed
else \(T_2\) waits.
Assume any transaction that is not killed terminates eventually. Which of the following is TRUE about the database system that uses the above algorithm to prevent deadlocks?
- A.
The database system is both deadlock-free and starvation-free.
- B.
The database system is deadlock-free, but not starvation-free.
- C.
The database system is starvation-free, but not deadlock-free.
- D.
The database system is neither deadlock-free nor starvation-free.
Attempted by 98 students.
Show answer & explanation
Correct answer: A
Answer: The system is both deadlock-free and starvation-free.
Key idea: This algorithm implements the wound-wait policy. If a requesting transaction is older than the lock holder, the holder (younger) is aborted; otherwise the requester waits.
Deadlock-free: Older transactions never wait for younger ones because an older requester will abort the younger holder instead of waiting. This preemption breaks any potential waiting cycle, so no circular wait can form.
Starvation-free: Killed transactions are restarted with the same timestamp. Lamport timestamps increase with time, so no new transaction can have an older timestamp than transactions that already exist. Therefore a transaction can only be killed by a finite set of transactions that started earlier (older timestamps). By the assumption that any transaction not killed eventually terminates, those older transactions will finish, so the restarted transaction cannot be killed infinitely often and will eventually succeed.
Conclusion: The wound-wait policy used here ensures both deadlock-freedom (no cycles) and starvation-freedom (no infinite sequence of kills), so the statement that the system is both deadlock-free and starvation-free is correct.
A video solution is available for this question — log in and enroll to watch it.