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

see this

---

All at once → no Hold & Wait

Fixed ordering (↑ or ↓) → no Circular Wait

---

this is my approach

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

we will never know what resources a process use before we execute it ,so we cant acquire all resources at beginning.

---

note some points for II,III,IV

• A natural number is assigned to every resource.
• Each process is allowed to request for the resources either in only increasing or only decreasing order of the resource number.
• In case increasing order is followed, if a process requires a lesser number resource, then it must release all the resources having larger number and vice versa.
• This approach is the most practical approach and implementable.
• However, this approach may cause starvation but will never lead to deadlock.

(ref: gatevidyalaya)

---

thnku @satyaAchar

Answer 2

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

Answer 3

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.

Answer 4

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 5

A deadlock will never take place if any one of the following condition is preempted.

1. Hold & Wait

2. Circular Wait

3. Mutual Exclusion

4. No-Preemption

           Statement I    violates hold & wait.

           Statement II  violates circular wait.

           Statement III  violates circular wait.

           Statement IV also violates circualr wait by making dependency graph acyclic.

Therefore, option D is correct