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

https://gateoverflow.in/118325/gate-cse-2017-set-1-question-42

same question asked in gate 2017 but the difference is timestamps are not geeting updated here so it will cause starvation as process having larger timestamp always acquire the critical section but in normal conditions "wound and wait" is deadlock and starvation free.

---

this custom algorithm punishes older processes, which is the exact opposite of standard deadlock prevention schemes (like Wait-Die or Wound-Wait) that specifically prioritize older processes to ensure they eventually finish.

• an older process $P_{old}$ requests a resource held by a younger process $P_{young}$.

• Because $T(P_{old}) < T(P_{young})$, the older process $P_{old}$ is killed.

• $P_{old}$ is restarted with the same timestamp, meaning it retains its status as an older process.

• if $P_{young}$ hasn't released the resource yet, or if a continuous stream of newer (younger) processes keep acquiring that resource while $P_{old}$ is busy restarting, $P_{old}$ will just keep getting killed over and over again.

• so yeah starvation is possible

---

1. Smaller timestamp = older process, while larger timestamp = younger process.
    
2. If the requester is older than the holder, i.e. T(Pr)<T(Ph), the requester is killed instead of waiting. So an older process can never wait for a younger one.
    
3. If the requester is younger, i.e. T(Pr)>T(Ph), it is allowed to wait. Therefore, every waiting edge goes from a younger process to an older process.
    
4. Hence, timestamps keep decreasing along a waiting chain. A cycle like 10→6→2→10 is impossible. No cycle → no circular wait → no deadlock. 
    
5. But starvation is still possible. Suppose an old process P1 repeatedly requests a resource held by a younger process P2. Every time, P1 gets killed because it is older.
    
6. The killer detail is that after being killed, P1 gets the same timestamp again. So when it retries, the system can make exactly the same decision and kill it again.
    
7. In the worst case: request → killed → restart → request → killed → restart →
    
8. Therefore, the scheme is deadlock-free but not starvation-free.
    

Answer 1

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.

Comments

Livelock is not possible here because livelock means the entire system makes no progress because processes keep looping. Here, whenever a process is killed, its resources are released, so some other process will always be able to move forward and finish. And in starvation, a particular process may keep getting killed again and again and never complete. So we can say that system-level progress is there which means there is no livelock, but individual process-level progress may fail, so there is starvation.

---

no livelock as the younger process is getting completed . in livelock no process was getting completed.

---

https://www.youtube.com/watch?v=YtH0y6rELbE&list=PLG9aCp4uE-s3klreqEhbzOBQDg5Ha0U38&index=20

Answer 2

"....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(P_r) < T(P_h) \) then
    kill \( P_r \)
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.)

 

Fig. 1 — P₃ holds resource R, while P₂, P₄, and Pᵢ are 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.

 

Fig. 2 — Classical two-process, two-resource deadlock scenario.

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.

Comments

 Hold and wait can never arise.

this deadlock prevention algo is basically modifed wound-wait scheme (but suffers from starvation)
anyway the gist is if new process is req for resource held by old process, the new process will wait
But,if old process is requesting for resource held by new process, the old process will abort

Now, here i think there should be hold and wait if the requesting process is new one, cuz it will hold it's existing resources and wait for the requested resource

and circular wait is always eliminated

This is the case i am talking about

so, @Sachin Mittal 1  in ur ans , you have written hold and wait is eliminated, but i think it is not always the case, can you kindly look into it

 

---

@Sachin Mittal 1  @Deepak Poonia  sir,can you please clear my doubt .
In your lectures you told that this scheme  wait- die and wound wait is deadlock free and starvation free.

 

& what is the difference between these two questions. https://gateoverflow.in/19705/gate-cse-1997-question-75
(in this question the scheme is starvation free)
But in the above question the scheme is not starvation free.

 

 

---

@kritika madaan this is because the above question does not follow either wait-die or wound-die, the question describe its own algorithm and based on that algorithm the option A is correct

Answer 3

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.

Answer 4

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 5

We can also think in a way that here, hold and wait is there as process Ph is holding resource R but it is not waiting for some other resource and process Pr is waiting for resource R. So it is like the below diagram: 

Ph <----R<-----Pr.

Thus hold and wait is there but circular wait is not there. And if here Ph holds this resource for a long time, then it may lead to starvation to Pr and we also know that "Every Deadlock implies hold and wait but every hold and wait doesn't imply deadlock". Thus correct option is A.The scheme is deadlock-free, but not starvation-free

Answer 6

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