GATE IT 2004 | Question: 63

Question

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 $P_h$ be the process holding a resource $R, P_r$ be a process requesting for the same resource $R,$ and $T(P_h)$ and $T(P_r)$ 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

Comments

Looking at this protocol two words are coming in mind - "Wait Die" and "Wound Wait"

---

Why no deadlock? Higher timestamp process gets preference. So there is order in which resources are allocated. So no circular wait hence no deadlock possible.

Why there is starvation? "restarted with the same timestamp if killed". So it cannot get ahead in race as it will be started with same TS.

So A is correct.

---

If it was either wound-wait  or  wait-die then there would not be starvation also. The question is using neither wound-wait nor wait-die because in either of these schemes, a higher priority process is never killed. In wound-wait, A higher priority process kills lower priority process. In wait-die, higher priority process waits for lower priority process. 

In the question, “ If( T(Pr)<T(Ph) ) then kill Pr “ ………..this means higher priority process is getting killed. This doesnt happen in wound-wait or wait-die.

Now, if question has been using either wound-wait or wait-die then any process which is killed should again be started with the same timestamp. This is done because after some time all processes having higher priority than our killed process will finish eventually and our process will become the highest priority process.If this was used:

WAIT-DIE:

  If(T(Pr)<T(Ph))

                wait;

  else

                 die;

 

WOUND-WAIT:

   If(T(Pr)<T(Ph))

                   kill  Ph;

   else

                   wait;

 

then answer would be-->no DL and no starvation.

Ramkrishna and Gehrke:-

 

 

Timestamp can be used in other way also:-(in this way, the aborted transaction is restarted with a new timestamp which is higher in value)

---

similar questions on Timestamp-

https://gateoverflow.in/19705/gate1997_75

https://gateoverflow.in/3706/gate2004-it-63

https://gateoverflow.in/118325/gate2017-1-42

Answer 1

Pls see if I am thinking right or wrong

If resource Is with process Ph and requesting process is Pr then what we can conclude is that definitely Ph would have came first than Pr than only Ph would have got the resource it means that timestamp of Ph would be less than Pr (say Ph came at 2 pm and Pr at 3p

m).Now since Pr is not killed by IF condition it goes in wait state and it is clearly it is mentioned that it will start at same time stamp than again it will have greater time stamp than Ph this will continue infintenly There this solution is not starvation free but deadlock free

Answer 2

Why no deadlock? Higher timestamp process gets preference. So there is order in which resources are allocated. So no circular wait hence no deadlock possible.

Why there is starvation? "restarted with the same timestamp if killed". So it cannot get ahead in race as it will be started with same TS.

So A is correct.