edited by
7,488 views
41 votes
41 votes

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.

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

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

edited by

4 Answers

Best answer
43 votes
43 votes
  1. 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.
  2. 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.

edited by
10 votes
10 votes
Its wound-wait protocol of database, which is deadlock-free and starvation-free.
0 votes
0 votes
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.
0 votes
0 votes
there is no starvation and no deadlock possible in given que. if someone says possible then how.....????
reshown by

Related questions

25 votes
25 votes
6 answers
1
Kathleen asked Sep 29, 2014
17,446 views
An operating system contains $3$ user processes each requiring $2$ units of resource $R$. The minimum number of units of $R$ such that no deadlocks will ever arise is$3$$...
51 votes
51 votes
14 answers
2
48 votes
48 votes
4 answers
3
32 votes
32 votes
2 answers
4
Kathleen asked Sep 29, 2014
8,523 views
I/O redirectionimplies changing the name of a filecan be employed to use an existing file as input file for a programimplies connecting $2$ programs through a pipeNone of...