GATE CSE 2015 Set 3 | Question: 52

Question

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?

• A. Any one of (I) and (III) but not (II) or (IV)
• B. Any one of (I), (III) and (IV) but not (II)
• C. Any one of (II) and (III) but not (I) or (IV)
• D. Any one of (I), (II), (III) and (IV)

Comments

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

---

“mutually exclusive resources" in first line of question

 means  “each instance of resource can be used by single process at a time”  that is each instance of resource is non shareable .

It does not comment about number of instances.

Answer 1

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.

http://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/7_Deadlocks.html

Comments

Give example for B,C,D  options plz.

---

@satyam dont you think option 1 implies more no preemption condition.

---

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 2

Answer is D These all cases are various methods for preventing deadlock

Answer 3

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.

so answer is option D

Comments

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.

---

if process is requesting decreasing no. of resources then, Is there any chance of getting deadlock????

Answer 4

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.