# GATE2015-3-52

4.7k views

Consider the following policies for preventing deadlock in a system with mutually exclusive resources.

1. Process should acquire all their resources at the beginning of execution. If any resource is not available, all resources acquired so far are released.
2. The resources are numbered uniquely, and processes are allowed to request for resources only in increasing resource numbers
3. The resources are numbered uniquely, and processes are allowed to request for resources only in deccreasing resource numbers
4. The resources are numbered uniquely. A processes is allowed to request for resources only for a resource with resource number larger than its currently held resources

Which of the above policies can be used for preventing deadlock?

1. Any one of (I) and (III) but not (II) or (IV)
2. Any one of (I), (III) and (IV) but not (II)
3. Any one of (II) and (III) but not (I) or (IV)
4. Any one of (I), (II), (III) and (IV)

edited
0
"mutually exclusive resources" in first line of question

means each resource can be used by only one process at one time. In other words, each resource have only 1 instance.

A deadlock will not occur if any one of the below four conditions are prevented:

1. hold and wait
2. mutual exclusion
3. circular wait
4. no-preemption

Now,

Option-1 if implemented violates 1 so deadlock cannot occur.

Option-2 if implemented violates circular wait (making the dependency graph acyclic)

Option-3 if implemented violates circular wait (making the dependency graph acyclic)

Option-4 it is equivalent to options 2 and 3

So, the correct option is 4 as all of them are methods to prevent deadlock.

edited
2

nice explaination!!!

4
@Tamojit Option B and C will create circular wait condition because do't mention process can not use resource no less than is no.
8

so the correct option is 4 as all of them are methods to avoid deadlock

First of all thank for explanation. But please use word *prevent in place of avoid. :)

1
Nice and clear explanation
0
Give example for B,C,D  options plz.
0
@satyam dont you think option 1 implies more no preemption condition.
0
if we take this consideration that " process can not use resource no less than is no." then only cycle is not created otherwise it create cycle in statement b and c. So statement b and c are false.
Answer is D These all cases are various methods for preventing deadlock
As option I is a standard method to avoid deadlock which overcomes hold and wait one of the four conditions for deadlock.

II and III and IV can be used to avoid condition of circular wait.

2
Option D is right option for it .All four condition is used to break out circular deadlock condition .So any of the four is possible to break deadlock condition.
0
if process is requesting decreasing no. of resources then, Is there any chance of getting deadlock????
As mentioned in the question, these are all techniques of preventing a Deadlock prevention as mentioned in the question. Please note the term Lock and Resources are used interchangeably.

Setting, 10 resources in the system 1, 2, 3, 4.. 10 and all the threads in the system needs all the resources.

1. In this case, the thread start acquiring the lock in random order and if it fails then it retries again. Here CPU cycles are wasted as it might be the case that one thread as acquired the the locks till 9 and then some other thread starts acquiring lock from 10. In this case the earlier thread which was almost done has to retry again and all the work done for acquiring 9 locks is wasted.

2. In this case the thread follows patter that it starts acquiring lock in increasing order. Here if a thread gets lock on resource 1, then it is sure to get all the locks ( This requires a condition of releasing order. Food for thought?).

3.This is same as case 2 here it start acquiring lock in decreasing order. Increasing or decreasing does not matter till all the threads follow some pattern. This will reduce wasted work ( might not even allow thread to do wasteful work).

4. This case is interesting. In current setting this is same as option 2 because every thread will start from Resource 1. This will be different when the requirements of each thread is not same. Here then it is not guaranteed that if you acquire Resource/Lock 1, you will succeed in acquiring everything. For example, suppose thread A need 1,2,3,4,5 and thread B needs 4,5,6,7,8 so when thread A and B starts, thread A will fail at lock 5 (assuming both get a chance to run and other scheduling operations are same).

Hope this helps.

## Related questions

1
5.3k views
For the processes listed in the following table, which of the following scheduling schemes will give the lowest average turnaround time? ... First Come First Serve Non-preemptive Shortest job first Shortest Remaining Time Round Robin with Quantum value two
Two processes $X$ and $Y$ ... deadlock The proposed solution guarantees mutual exclusion and prevents deadlock The proposed solution fails to prevent deadlock and fails to guarantee mutual exclusion
The maximum number of processes that can be in $\textit{Ready}$ state for a computer system with $n$ CPUs is : $n$ $n^2$ $2^n$ Independent of $n$
Consider the following software items: Program-$X$, Control Flow Diagram of Program-$Y$ and Control Flow Diagram of Program-$Z$ as shown below The values of McCabe's Cyclomatic complexity of program-$X$, program-$Y$, and program-$Z$ respectively are 4, 4, 7 3, 4, 7 4, 4, 8 4, 3, 8