In a database system, unique timestamps are assigned to each transaction using Lamport's logical clock
Since Unique Timestamps are assigned, so there is no question of two transaction having same timestamp.
Moreover, there is nothing mentioned about the size of the counter by which it can be determined that whether there will be case of timestamp wrap around or not.
So, there will be no timestamp wrap around.
In Lamport's logical clock Timestamps are assigned in increasing order of enumeration.
So, $T_{i} < T_{j}$ if Transaction $T_{i}$ came into system before $T_{j}.$
The above scheme given is nothing but " Wound-Wait " Scheme in which younger transaction is killed by older transaction that came into system before this younger transaction came.$[1][2]$
So, this is a part of Basic Time-Stamp Ordering in Concurrency Control.
And Basic Time Stamp ordering protocol is deadlock free and not starvation free, in general.
Here in this question according to given condition, the database system is both deadlock free and starvation free as well , as it is Wound wait scheme and in case of wound wait it avoid starvation, because in Wound Wait scheme we restart a transaction that has been aborted, with it's same original Timestamp . If it restart with a new Timestamp then there is a possibility of Starvation ( as larger TimeStamp transaction is aborted here and new Transaction which is coming next have always greater TimeStamp than previous one ). But that is Not the case here.
References:
Hence, answer is (A).
PS: The Wound-wait scheme means :
- The newer transactions are killed when an older transaction make a request for a lock being held by the newer transactions .
- Here the algorithm says $TS(T_{2}) < TS(T_{1})$ means $T_{2}$ is older transaction ( as $TS$ of $T_{2}$ is less than $TS$ of $T_{1}$ means $T_{2}$ come first then $T_{1}$ come and $TS$ is assign in increasing order ) , so newer one is $T_{1}$ and also question says $T_{1}$ holds a lock on the resource $R,$ and $T_{2}$ has requested a conflicting lock on the same resource $R.$
- So $T_{1}$ is killed as per Wound-wait scheme .
|
Reference :
timestamps are assigned to each transaction using Lamport's logical clock.
This line means timestamps are assigns in increasing order.
We can divide the answer into $3$ parts:
Part $1:$ Is it Wound wait scheme?
Yes, given algorithm:
If $TS(T_{2}) < TS(T_{1})$, then
$T_{1}$ is killed
else, $T_{2}$ waits.
comes under wound wait scheme..as here old transaction is always survive and older transaction wounds newer transaction when both want to apply lock on same resource.
Part $2:$ Wound Wait avoid Starvation
Yes, How?
as newer one is die and restart with same timestamp and older one is survive always so after execute older transaction that newer one can definitely execute and new transactions which are coming can die and restart again ( previous newer became older that time).
Part $3:$ Does Starvation freedom implies Deadlock freedom?
Yes, here no starvation means also No deadlock possibility.
In one line - wound wait $\to $ no starvation $\to$ no deadlock $\to$ option A.
EDIT:
Another way to think about Deadlock and starvation
Deadlock is prevented because we are violating NO-Preemption Condition for the deadlock to happen.
How starvation free? Here Bounded waiting for transactions is ensured. HOW?
Consider $``n"$ transactions $T_1,T_2, \ldots,T_n$ having their timestamps order as $TS(T_1) \lt TS(T_2) \lt \ldots TS(T_n)$ (Timestamps are unique)
Consider for $k, 1 \lt k \leq n$ a transaction $T_k$, this transaction $T_k$ can be atmost preempted by Transaction sets $T_1,T_2, \ldots,T_{k-1}$ and it is also given "Any transaction that is not killed eventually terminates". Means Eventually a time would come when, all transactions $T_j$ having $TS(T_j) \lt TS(T_k)$ will terminate and $T_k$ would get chance without preemption.And this $j$ would lie in range $1\leq j \leq k-1$. Bounded waiting ensured.