You are here:-->View note-->View question

What all are the break conditions for deadlock

Explain neatly

By:scribed

Taged users:
|pallaviaithaln|scribed|manjarimattur

Likes:
Be first to like this question

Dislikes:
Be first to dislike this question
Talk about this

Edit|Delete|Like|Dislike|

Answers

There is mainly four scenarios where deadlock can occur they are

Mutual exclusion. There must be some resource that can't be shared between processes.
Hold and wait. Some process must be holding one resource while waiting for another. 
No preemption. Only the process holding a resource can release it.
Circular wait. There must be some cycle of waiting processes P1, P2, ..., Pn such that each process Pi is waiting for a resource held by the next process in the cycle. (Note that this implies hold-and-wait.)
To deal with these scenarios we can help them to not occur which follows in at these ways.
No mutual exclusion. If there's no need for mutual exclusion, there's no deadlock. This is the best solution when it can be arranged, particularly when resources (read-only files, lock-free data structures) can be shared. This doesn't work for resources that can't reasonably be shared by two processes at the same time (most writable data structures, the CPU, CD-ROM burners, the keyboard). Sometimes resources can be partitioned to avoid mutual exclusion (memory partitioning, window systems). 
No hold-and-wait. Adopt a policy of not letting a process wait for one resource while holding another, either by requiring each process to hold only one resource at a time, or to request all of the resources it needs simultaneously. The first approach may be severely limiting (for example, an interactive program can't get exclusive access to the keyboard and the display at the same time). The second has two problems: it requires a process to predict what resources it needs in advance, and it may allow a process to starve waiting for a group of resources that never become free all at the same time. Sometimes resources can be consolidated to allow the single-resource approach: it's quite natural, for example, to have a single mutex that covers all three of the keyboard, mouse, and display. In the limit we can lock the entire system (caveat: difficult for distributed systems) in order to lock any resource, but then things are likely to get slow. 
Allow preemption. This is almost as good as eliminating mutual exclusion: if I can bump some process off a resource it is hogging, then I can break a deadlock cycle. The CPU is the primary preemptible resource (although we may get deadlock if we allow processes to block preemption while waiting for other resources—as can happen with disabled interrupts or in cases of priority inversion where a high-priority process pushes the low-priority process it's waiting for off the CPU). Another preemptible resource is memory (assuming we can swap out to disk). The difference between preemption and sharing is that in the preemption case we just need to be able to restore the state of the resource for the preempted process rather than letting it in at the same time as the preemptor. 
Eliminate cycles. This is similar to no-hold-and-wait. We'll require processes to grab resources in increasing order according to some total order (one common heuristic is increasing order by the memory address of the mutexes guarding the resources). If process P is holding R1 while waiting for R2, then R2 > R1 in the ordering (otherwise P would have grabbed it first). So we can't have a circular wait, because this would give a cycle in the total order on resources. Note that unlike hold and wait we don't get starvation if the resources are allocated fairly: I will eventually come to the front of the line for the next resource on my list and will thus eventually get all the resources. The disadvantage though is that I still need to be able to predict what resources I want in advance or accept that I may not be able to ask for some resource if I was unlucky enough to request some other resource first.


How to deal with deadlock
There are several ways to detect and deal with deadlock. In increasing order of complexity: 
Do nothing. If the system locks up, that will teach the user not to try doing what they just did again. This is approach taken in practice for many resource constraints.
Kill processes. We can detect deadlock by looking for waiting cycles (which can be done retrospectively once we notice nobody is making as much progress as we like). Having done so, we can either kill every process on the cycle if we are feeling particularly bloodthirsty or kill one at a time until the cycle evaporates. In either case we need to be able to reset whatever resources the processes are holding to some sane state (which is a weaker than full preemption since we don't care if we can restore the previous state for the now-defunct process that used to be holding it). This is another reason why we design operating systems to be rebooted. 
Preempt and rollback. Like the previous approach, but instead of killing a process restore it to some earlier safe state where it doesn't hold the resource. This requires some sort of checkpointing or transaction mechanism, and again requires the ability to preempt resources.

metaphor

Likes:
Be first to like this answer

Dislikes:
Be first to dislike this answer
Talk about thisOnce you have earned teacher badge you can edit this questionDelete|Like|Dislike|
------------------------------------

You dont have permission to add an answer herePlease see this