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.
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.
Avoiding deadlock Here we aren't going to violate the Coffman conditions, but we may make processes wait for a resource even if it is available because granting the resource might lead to deadlock later. Typically this requires that processes declare in advance what resources they might request. For example, in the keyboard-and-display situation, each process could declare that it may want at some point 1 keyboard and 1 display. Then once process P grabs the keyboard, a deadlock-avoidance algorithm could make Q wait for the display even if P hasn't asked for it.
Formally, this condition is expressed in terms of safe states. Intuitively, a state is safe if there is some way to let all the processes run without creating deadlock. The idea is that the safe sequence describes the order in which processes will finish and release their resources, and once all previous processes have finished, P i can get whatever it needs and finish too. A working deadlock-avoidance algorithm will notice this and keep Q from acquiring the display.
The method is the following: we write down a matrix whose rows correspond to processes and columns to resources, and put each process's maximum remaining demand in its row.
We keep track of a separate vector A of available resources. To determine if a state is safe: Look for a row that is componentwise less than or equal to A. If there is none, the state is not safe. Otherwise, pretend that the process for that row has finished, remove its row from the matrix, and give all of its resources back to A. Repeat until we get stuck or all processes are removed.
It's not hard to see that the Banker's Algorithm computes a safe sequence. More work is needed to show that it always finds a safe sequence if one exists. Tanenbaum observes that in practice nobody uses this algorithm given the unreasonable requirement that each process pre-specify its maximum demand. Dealing 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. Like Article. Previous Deadlock Detection And Recovery. Next Banker's Algorithm in Operating System. Recommended Articles. Article Contributed By :. Easy Normal Medium Hard Expert. Writing code in comment? Please use ide. Load Comments. What's New. Most popular in Articles. If the edge goes from resource to process node, it indicates that the process has acquired the resource.
If the edge goes from the process node to the resource node, it indicates that the process has requested the resource. We can use these graphs to determine if a deadlock has occurred or may occur. For example, if all resources only have one instance all resource node rectangles have one dot and the graph is circular, a deadlock has occurred. If some resources have several instances, a deadlock may occur.
If the graph is not circular, a deadlock cannot occur because the circular wait condition will not be satisfied. Below is an example of a deadlock system. Process X has resource B and is waiting for resource A. Process Y has resource A and is waiting for resource B.
Note there exists a cycle in the directed graph. The diagram below is an example of a resource graph that has a cycle but does not represent a deadlocked system. It is possible for process Z to continue execution. When process Z is completed, it will release resource A. It will allow process X to acquire it and continue processing. A cycle is a necessary, but not sufficient condition for deadlock.
All deadlocked systems will exhibit all of the above four conditions. Not every system that exhibits the above four conditions will be deadlocked.
We can prevent deadlock by ensuring that at least one of the four necessary conditions for deadlock cannot occur. If at least one condition is not satisfied, a deadlock will not occur. Mutual exclusion condition must hold for non-sharable resources.
For example, only one process can have access to a printer at a time, otherwise, the output is disturbed. Some resources can be made shareable like a read-only file. Several processes can be granted read-only access to a file without inferring from each other. However, deadlock cannot be prevented by only denying mutual exclusion conditions because some resources are intrinsically non-shareable.
Deadlock can be prevented by denying the hold and wait for a precondition. This can be implemented in two different ways. Preemption of resources means that we take away sources from processes when they are waiting for other resources.
This could work in the following ways:. We can prevent deadlock by making circular wait impossible. We can define an order by which the process is to get resources to prevent circular wait. For example, each resource type is assigned a number. The process can only get resources in increasing order of those resource numbers.
0コメント