edited by
26,726 views
83 votes
83 votes

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?

  1. The database system is both deadlock-free and starvation-free.
  2. The database system is deadlock-free, but not starvation-free.
  3. The database system is starvation-free, but not deadlock-free.
  4. The database system is neither deadlock-free nor starvation-free.
edited by

4 Answers

Best answer
137 votes
137 votes

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.


edited by
8 votes
8 votes

The given algorithm in the question is Wound wait scheme where Wound Wait  is a preemptive technique for deadlock prevention.

The given algorithm in the question is as follows :

              if TS(T2)  < TS(T1) then 

                          T1 is killed 

                     else T2 waits.

it is also given in the question T1 holds a lock on the resource R, and T2 has requested a conflicting lock on the same resource R.

It means --> When transaction T2 requests a data item currently held by T1, T2 is allowed to wait only if T2 has a timestamp larger than that of T1 that is T2 is younger than T1 [ means after T1 , then comes T2 ](this is the else part),  [ the else part is True when : T2 > T1 ] .  

otherwise T1 is rolled back (dies) ie. T2 kills T1 [ the if part in the algorithm ] and T1 is resubmitted to the system with same timestamp ,so later it will win the race -so no chance of starvation . [ as said in the question --> algorithm is used to prevent deadlocks in the database system assuming that a killed transaction is restarted with the same timestamp. ]

In a single line , we can say :

As it is Wound Wait scheme , there is No starvation ( due to Younger Transaction re-started with same timestamp - older one is always survive - new transaction again come with increasing timestamp - die - restart with same timestamp .. and this process continues so no starvation  ) ... as we know starvation freedom implies deadlock freedom ,  there is no starvation, we can say there is No deadlock too.

Hence option A is correct choice only . 

For further reading :

http://stackoverflow.com/questions/32794142/what-is-the-difference-between-wait-die-and-wound-wait

edited by
2 votes
2 votes

For all the confusion, why starvation-free? Here is my opinion.

There is ONE AND ONLY ONE condition wherein we will get starvation as per the description of this wound-wait scheme that they have mentioned in the question. And that is when older transaction (i.e. the one with lower timestamp) never dies off (by never i mean dies off very late). Then, in this case, it will keep killing the newer transaction whenever it again requires the lock.

But see this line

Assume any transaction that is not killed terminates eventually.

I think this line has been put for this sole exceptional case, otherwise, i don’t think there is any use of this line.

Now if the question itself is saying that the older transaction will die off quickly after receiving the resource then we can conclude that it is starvation free. Because all other case where starvation would have been possible has been eliminated by ‘same timestamp’ constraint.

AM i right @ sir?

0 votes
0 votes
Other way you can think like that

wound wait protocal prevent the deadlock because after die transaction come back again with pervious Time so 𝓝𝓸 𝓭𝓮𝓪𝓭𝓵𝓸𝓿𝓴.
 
unique timestamps are assigned to each transaction using Lamport's logic clock it means increase order so every process get chance𝓼 𝓷𝓸 𝓼𝓽𝓪𝓻𝓿𝓪𝓽𝓲𝓸𝓷

Same question come in OS for process in 2003 but in that question process no use lamport clk so starvation occur
Answer:

Related questions

52 votes
52 votes
5 answers
1
Arjun asked Feb 14, 2017
12,780 views
Consider a database that has the relation schema CR(StudentName, CourseName). An instance of the schema CR is as given below.$$\begin{array}{|c|c|} \hline \textbf{Student...
0 votes
0 votes
1 answer
4
aditi19 asked Dec 1, 2018
1,134 views
T1: R(X), T2: W(X), T2: commit, T1: W(X), T1: commit, T3: R(X), T3: commitis this allowed in Thomas write rule?if yes then what will be the serial order