GATE CS 2017 Set 1 Q.42 (CS Q.42): Transactions, Serializability and Concurrency Control

In a database system, unique timestamps are assigned to each transaction using Lamport's logical clock. Let $\text{TS}(T_1)$ and $\text{TS}(T_2)$ be the timestamps of transactions $T_1$ and $T_2$ respectively. Besides, $T_2$ holds a lock on the resource $R$ , and $T_1$ 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(T1) < TS(T2) then
    T1 is killed
else
    T1 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?

The database system is both deadlock-free and starvation-free.

The database system is deadlock-free, but not starvation-free.

The database system is starvation-free, but not deadlock-free.

The database system is neither deadlock-free nor starvation-free.

Official answer and solution

Official answer: A
From: Official GATE 2017 answer key

Solution

Analyze the wait-for relationships and transaction restart mechanism under the given timestamp-based deadlock prevention algorithm.

The deadlock prevention algorithm specifies:
When transaction $T_1$ requests a lock held by $T_2$ :

If $\text{TS}(T_1) < \text{TS}(T_2)$ (i.e., $T_1$ is older than $T_2$ ), $T_1$ is killed.
If $\text{TS}(T_1) \ge \text{TS}(T_2)$ (i.e., $T_1$ is younger than $T_2$ ), $T_1$ waits.

Deadlock Freedom:
In this scheme, a transaction waits only if it is younger than the transaction holding the lock ( $\text{TS}(T_{\text{waiting}}) > \text{TS}(T_{\text{holding}})$ ). Consequently, in the wait-for graph, all directed edges point from younger transactions to strictly older transactions. Because timestamps form a strict total order and strictly decrease along every path of waiting transactions, a directed cycle can never form in the wait-for graph. Therefore, the system is guaranteed to be deadlock-free.

Starvation Freedom:
When a transaction $T_1$ is killed, it is restarted with its original timestamp $\text{TS}(T_1)$ . As new transactions enter the system, they receive newer (larger) timestamps. Eventually, $T_1$ 's timestamp becomes smaller than that of other active transactions. An older transaction holding resources is never killed by younger transactions (younger transactions wait for it), so $T_1$ can acquire needed resources and proceed to completion without being indefinitely postponed. Therefore, the system is starvation-free.

Thus, the database system is both deadlock-free and starvation-free.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 1
Question: 42 of 65, printed as CS Q.42
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source