9,134 views

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?

1. The scheme is deadlock-free, but not starvation-free
2. The scheme is not deadlock-free, but starvation-free
3. The scheme is neither deadlock-free nor starvation-free
4. The scheme is both deadlock-free and starvation-free

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.
edited by

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)

When the process wakes up again after it has been killed once or twice IT WILL HAVE SAME TIME-STAMP as it had WHEN IT WAS KILLED FIRST TIME. And that time stamp can never be greater than a process that was killed after that or a NEW process that may have arrived.

So every time when the killed process wakes up it MIGHT ALWAYS find a new process that will say "your time stamp is less than me and I take this resource", which of course is as we know, and that process will again be killed.

This may happen indefinitely if processes keep coming and killing that "INNOCENT" process every time it try to access.

So, STARVATION is possible. Deadlock is not possible.

Can we say this has Live Lock?
Yes @anupam_yedida because the rejected process will be doing some unproductive task being in a safe state.
Thanks :)

"....and is restarted with the same timestamp if killed." This statement needs all of your attention.

Ph: Process that is Holding.
Pr: Process that is Requesting.

if T(Pr) < T(Ph) then
kill Pr
else wait

If a process is respawning again with same timestamp then why to kill?
Well, it has its own perks. (it avoids Deadlock, explained later in this answer.)

If any process is holding some resource, Does it give it to anyone?
Nopes. No one can take it (Unless holding process completes execution), Either Requesting process will be killed or Requesting process will wait.

Now see this scenario: (P3 holds R, all other requesting it.)

In this case P2, P4 and Pi all will wait for R. (only difference is, P2 will be killed again and again.)

Once P3 releases R on completion, Who will get R ?
-Any process irrespective of its timestamp can take R. And some arbitrary process Pi may starve.
This Shows that implementation is NOT starvation free.

-Yes.

"....and is restarted with the same timestamp if killed."  Because of this statement, Hold and wait can never arise. Because when we kill the process, it forces to release all of its currently holding resources.

The moment P1 requests for R2, it will be killed and R1 will be given to P2.

We can think this resource allocation scheme as Deadlock Prevention scheme as it always prevents Circular wait.

If somewhere this exact code is given as an example of Deadlock Prevention scheme, It won't be surprising for me.
Hence A.

But sir if Ts(Pr)>Ts(Ph) then our Pr waits for Ph to release the R1 and Ph waits for Pr to release R2.

Sir if Ts(p2) > Ts(p1) then P2 not get killed.p2 holding R2 and requesting for R1 .p1 holding R1 and requesting for R2 and non of the process get killed becoz Ts(p2)> Ts(p1) then deadlock should happen.

My attempt at proving that Deadlock isn’t possible here :-

Let there be 3 pairs of contesting processes for 3 different resources – Ph, Pr for resource R, Ph, Pz for resource S and Pr, Pz for resource T.

So, in the 1st case, we have that Ph holds resource R, while Pr requests for it, and T(Pr) > T(Ph); in the 2nd case, we have Pz holding resource S, while Ph requests for it and T(Ph) > T(Pz); in the 3rd case, we have Pr holding resource T, while Pz requests for it and T(Pz) > T(Pr).

The timestamps for the above processes have been taken in such a way that in any case, no process gets killed and we only have the wait option in each of the above 3 cases. Thus, we can observe a circular wait between Pr, Ph and Pz – thus giving us a Deadlock.

But if we notice the relations between the timestamps, we can observe that T(Pr) > T(Pz) (transitively, since T(Pr) > T(Ph) and T(Ph) > T(Pz)) and also in the 3rd case, T(Pr) < T(Pz).

Suppose T(Pr) < T(Ph) then Kill Pr will be happen .in this condition both process will start execution same time .But what is gaurantee that process pr will get chance and suppose it will repeat again and again then such satuation is called as starvation.But deadlock free bcz strave process will wait for completion of process Ph.

if T(Pr) < T(Ph) then
kill Pr
else wait

so this mean that older process are killed when a younger process request data from them.

so obviously not deadlock because whenever a new process come and it requests data then older process will be killed and restarted with same time stamp and therefore resources are released new process can use those resource.

But starvation will be there because older process which got killed always restart with the same time stamp that is always be old therefore this may lead to starvation to those processes if new processes remains arriving and requesting their data.