recategorized by
13,257 views
52 votes
52 votes

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
recategorized by

6 Answers

Best answer
80 votes
80 votes

Answer is (A).

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.

edited by
58 votes
58 votes

"....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.

Will it be deadlock 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.

Think about classical 2 processes, 2 resources deadlock.


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

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.

edited by
5 votes
5 votes

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.

Therefore Answer should be A.

3 votes
3 votes
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.

Answer:

Related questions

28 votes
28 votes
4 answers
4