GATE CSE 1997 | Question: 75

Question

An operating system handles requests to resources as follows.

A process (which asks for some resources, uses them for some time and then exits the system) is assigned a unique timestamp are when it starts. The timestamps are monotonically increasing with time. Let us denote the timestamp of a process $P$ by $TS(P)$.

When a process $P$ requests for a resource the $OS$ does the following:

1. If no other process is currently holding the resource, the $OS$ awards the resource to $P$.

2. If some process $Q$ with $TS(Q) < TS(P)$ is holding the resource, the $OS$ makes $P$ wait for the resources.

3. If some process $Q$ with $TS(Q)>TS(P)$ is holding the resource, the $OS$ restarts $Q$ and awards the resources to $P$. (Restarting means taking back the resources held by a process, killing it and starting it again with the same timestamp)

When a process releases a resource, the process with the smallest timestamp (if any) amongst those waiting for the resource is awarded the resource.

• A. Can a deadlock over arise? If yes, show how. If not prove it.

• B. Can a process P ever starve? If yes, show how. If not prove it.

Comments

Does a bigger timestamp mean a younger process?

---

Similar question has appeared again:

Operating System: GATE IT 2004 | Question: 63 (gateoverflow.in)

 Databases: GATE CSE 2017 Set 1 | Question: 42 (gateoverflow.in)

---

Generally yes. But depends on the definition. They will provide you with the definition, most questions say that timestamp of processes are monotonically increasing.

Honestly that is intuitive too. But still read the question thoroughly once. It will be evident.

Answer 1

• A. Can Deadlock occur. No, because every time Older Process who wants some resources which are already acquired by some younger process. In this condition Younger will be killed and release its resources which is now taken by now older process. So never more than one process will wait for some resources indefinitely. Timestamp will also be unique.
• B. Can a process Starve. No, because every time when Younger process is getting killed, it is restarted with same timestamp which he had at time of killing. So it will act as an elder even after killing for all those who came after it..

There is No starvation. Consider this scenario:

Say a process $p_{12}$ with TS $12$ and another process $p_{11}$ with timestamp $11$ so,  $p_{12}$ gets killed but again come with same timestamp. As timestamp is increasing for newly enter process so  at next process $p_{13}$ enter with timestamp $13$ which have greater timestamp than $p_{12}$ so, $p_{12}$ gets executed. Hence there is no starvation possible.

Comments

Starvation possible if they didn't mention the line " process (which asks for some resources, uses them for some time and then exits the system)"…

---

But @Sachin Mittal 1 sir can it not be a case that older process is having some condition like infinite loop and due to that younger process will starve?

 

Same logic were used in Gate cse 2023 question.

---

"A process (which asks for some resources, uses them for some time and then exits the system) is assigned a unique timestamp are when it starts"

In question they have mentioned some time
Some time can't means it will run indefinitely, it will halt, and eventually the process will the resouces

Answer 2

Its wound-wait protocol of database, which is deadlock-free and starvation-free.

Answer 3

The process will starve if it is restarted with a newer timestamp. This will lead to the process to get killed all the time and get renewed with being the same younger ( junior ) process, and hence, starve

Answer 4

any deadlock? no

but I Think the process will starve, imagine the one with the highest time stamp,it gets killed by a younger process,it has to start with the same time stamp, even though it gets hold of a resource it is always killed.secondly whenever any process releases a resource,the one with the smallest time stamp is awarded the resource, so the one with the highest time stamp in the entire system will starve prvided new processes with lower time stamps keep coming.

Comments

I think there would be starvation if after releasing the resources, the process does not terminate.

Consider 

$P_{1}, P_{2}  \cdots P_{n}$ with $(TS)$ corresponding to IDs

Then if $P_{1}$ is holding a resource, and all others request for it, then they would wait.

Once $P_{1}$ releases and does not terminate, $P_{2}$ will get the resource(lowest TS).

But if $P_{1}$ tries to get the resource again, then $P_{2}$ gets killed and restarted with the same TS and the cycle continues leading to starvation, as others will never get a chance to execute.

Correct me if I am wrong. Of course this is the scenario if the processes didn't terminate.

---

there is no starvation because  it is given in question when two process wants the same resource then it use the resource for some time and leaves then. suppose there are two process p11 and p12 then first p11 use the resource for some time and then p11  leaves and then p12 use the resource so there is no starvation

---

@Neelay Upadhyaya your concern is valid but The problem statement explicitly says:

“A process … uses the resources for some time and then exits the system.”

This means:

• Processes are finite
• After releasing resources, they terminate
• They do not request again

Therefore no Starvation

"If processes repeatedly request resources without terminating, the scheme may lead to starvation of younger processes(higher timestamps). However, under the given assumption that processes eventually terminate, starvation does not occur."

Answer 5

there is no starvation and no deadlock possible in given que. if someone says possible then how.....????

Comments

someone doing unnecessary voting down even for correct thing also i don't know who r u and how can u behave like this.plz read the statement again carefully bcoz its correct statement.

---

@ rajoramanoj 

Please read the best answer now .. it is elaborated how Deadlock and Starvation not possible here with given condition..

---

@ Bikram sir thank u , now it is correct . i also want to say that only. 

Answer 6

Lets deal with question a bit differently.

Suppose in a house there are 5 members. Grand father , Father , Mother , Elder Brother(B) , Youngest Sister(S). There is only one tv in the house.

Now the rule in the house is : 1)If any younger family member is watching tv and an elder member joins then elder member will watch tv and younger had to leave.

2)If elder member is watching tv and any younger member joins , then younger member will keep waiting till older member is watching tv.

3)Every member watches tv only once(this we have taken because an older process will keep its execution continue till the end as it will kill all the younger process in the meantime to get resources.This means older process will stop only after complete execution)

4) Only younger members can join the family in future like if a new member joins after S then it needs to be younger ( This rule is applied because process with younger time stamps will join . Process with older timestamps are already present. Whatever new process comes it will have a younger timestamp)

Deadlock: will there be deadlock?

No

Explanation:  If mother  is watching tv and B joins then B will wait .Suppose B is already waiting and S also joins in then she will also wait.

Now mother  was about to leave and B was happy that he will get the chance but in the meantime Father joins in.

So as per the rule:  As mother left , father is the eldest so he gets the chance to watch tv and B and S keeps on waiting.

But but but

Father was watching and grandfather joins so father gives the remote to grand father and waits for his chance.

Eventually grandfather leaves then father watches tv then he leaves then son watches and then sister.

So there can never be a deadlock.

PS : There was chance of deadlock if elder member comes back to watch tv even after watching it one time but this will not happen as per our rules

Starvation: Will it happen?

No

Explanation: It's clear now that if older member joins the younger members will wait for there chance and they will get it eventually. What if more younger members join ?

Suppose B is watching tv and S is waiting and one more member joins who is younger, say Q .

If this happens still there is no problem because Q is younger and younger members keep waiting till elder members finish watching tv .

So no deadlock and no starvation