/ 0
Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems
Summary
- Deadlock handling
- Deadlock prevention
- Deadlock avoidance
Deadlock Handling
We can deal with deadlocks in a number of ways:
- Ensure that the system will never enter a deadlock state.
- Allow the system to enter a deadlock state and then recover from deadlock.
- Ignore the problem and pretend that deadlocks never occur in the system.
These three ways result in the following general methods of handling deadlocks:
- Deadlock prevention: is a set of methods for ensuring that at least one of the necessary conditions cannot hold. These methods prevent deadlocks by constraining how processes can request for resources.
- Deadlock Avoidance: This method of handling deadlocks requires that processes give advance additional information concerning which resources they will request and use during their lifetimes. With this information, it may be decided whether a process should wait or not.
- Allowing Deadlocks and Recovering: One method is to allow the system to enter a deadlocked state, detect it, and recover.
Deadlock Prevention
By ensuring that one of the four necessary conditions for a deadlock does not occur, we may prevent a deadlock.
Mutual exclusion
The mutual exclusion condition must hold for non-sharable resources, e.g., printer.
Sharable resources do not require mutually exclusive access and thus cannot be involved
in a deadlock, e.g., read-only files. Also, resources whose states can be saved and
restored can be shared, such as a CPU. In general, we cannot prevent deadlocks by
denying the mutual exclusion condition, as some resources are intrinsically non-sharable.
Hold and Wait
To ensure that the hold and wait condition does not occur in a system, we must guarantee
that whenever a process requests a resource, it does not hold any other resources. One
protocol that can be used requires each process to request and be allocated all its resources before it begins execution. We can implement this provision by requiring that
system calls requesting resources for a process precede all other system calls.
An alternative protocol requires a process to request resources only when it has none.
A process may request some resources and use them. But it must release these before
requesting more resources.
The two main disadvantages of these protocols are: firstly, resource utilization may
be low, since many resources may be allocated but unused for a long time. Secondly,
starvation is possible. A process that needs several popular resources may have to wait
indefinitely, because at least one of the resources that it needs is always allocated to some
other process.
No preemption
To ensure that this condition does not hold we may use the protocol: if a process is
holding some resources and requests another that cannot be allocated immediately to it,
then all resources currently being held by the process are preempted. These resources are
implicitly released, and added to the list of resources for which the process is waiting.
The process will be restarted when it gets all its old, as well as the newly requested
resources.
Circular Wait
One way to ensure that this condition never holds is to impose a total ordering of all resource types, and to require that each process requests resources in an increasing ordering of enumeration.
}be resource types. We assign to each a unique integer, which
allows us to compare two resources and to determine whether one precedes another in our
ordering. For example, if the set of resource types R includes tape drivers, disk drives,
and printers then the function F: R→N might be used to assign positive integers to these
resources as follows:
F(tape drive) =1
F(disk drive) =5
F(printer)=12
Each process can request resources in an increasing order of enumeration. For
example, a process wanting to use the tape and the disk drive must first request the tape
drive and then the disk drive.
We can prove that if processes use this protocol then circular wait can never occur.
We will prove this by contradiction. Let’s assume that there is a cycle involving process
P0 through Pk and that Pi is holding an instance of Ri, as shown below. The proof
follows.
P0 → P1 → P2 → … → Pk → P0
R0 R1 R2 Rk R0
⇒ F(R0) < F(R1) < … < F(Rk) < F(R0)
⇒ F(R0) < F(R0), which is impossible
⇒ There can be no circular wait.
Deadlock Avoidance
One method for avoiding deadlocks is to require additional information about how
resources may be requested. Each request for resources by a process requires that the
system consider the resources currently available, the resources currently allocated to the
process, and the future requests and releases of each process, to decide whether the
current request can be satisfied or must wait to avoid a possible future deadlock. The
simplest and most useful model requires that each process declare the maximum number
of resources of each type that it may need. Given a priori information about the maximum
number of resources of each type that may be requested by each process, it is possible to
construct an algorithm that ensures that the system will never enter a deadlocked state. A
deadlock avoidance algorithm dynamically examines the resource-allocation state to
ensure that a circular wait condition can never exist.
Safe State
A state is safe if the system can allocate resources to each process in some order and still
avoid a deadlock. More formally a system is in a safe state only if there exists a safe
sequence. A sequence of processes <P1, P2… Pn> is a safe sequence for the current
allocation state if, for each Pi, the resources that Pi can still request can be satisfied by the
currently available resources plus all the resources held by all the Pj with j < i. In this
situation, if the resources that Pi needs are not immediately available, then Pi can wait
until all Pj have finished. When they have finished, Pi can obtain all of its needed
resources, complete its designated task, return its allocated resources and terminate.
When Pi terminates, Pi+1 can obtain its needed resources and terminate. If no such
sequence exists, then the system is said to be unsafe.
If a system is in a safe state, there can be no deadlocks. An unsafe state is not a
deadlocked state; a deadlocked state is conversely an unsafe state. Not all unsafe states
are deadlocks, however an unsafe state may lead to a deadlock state. Deadlock avoidance
makes sure that a system never enters an unsafe state. The following diagram shows the
relationship between safe, unsafe, and deadlock states.
Let’ consider the following example to explain how a deadlock avoidance algorithm
works. There is a system with 12 tape drives and three processes. The current system
state is as shown in the following table. The available column shows that initially there
are three tapes drives available and when process P1 finishes, the two rape drives
allocated to it are returned, making the total number of tape drives 5. With 5 available
tape drives, the maximum remaining future needs of P0 (of 5 tape drives) can be met.
Once this happens, the 5 tape drives that P0 currently holds will go back to the available
pool of drives, making the grand total of available tape drives 10. With 10 available
drives, the maximum future need of P2 of 7 drives can be met. Therefore, system is
currently in a safe state, with the safe sequence <P1, P0, P2>.
Now, consider that P2 requests and is allocated one more tape drive. Assuming that the tape drive is allocated to P2, the new system state will be:
This new system is not safe. With two tape drives available, P1’s maximum remaining
future need can be satisfied which would increase the number of available tapes to 4.
With 4 tapes available, neither P0’s nor P2’s maximum future needs can be satisfied. This
means that if P2 request for an additional tape drive is satisfied, it would the system in an
unsafe state. Thus, P2’s request should be denied at this time.
Resource Allocation Graph Algorithm
In addition to the request and assignment edges explained in the previous lectures, we
introduce a new type of edge called a claim edge to resource allocation graphs. A claim
edge Pi →Rj indicates that process Pi may request resource Rj at some time in the future.
A dashed line is used to represent a claim edge. When Pi requests resource Rj the claim
edge is converted to a request edge.
Suppose that Pi requests resource Rj. The request can be granted only if converting the
request edge Pi →Rj into an assignment edge Rj →Pi does not result in the formation of a
cycle. If no cycle exists, then the allocation of the resource will leave the system in a safe
state. If a cycle is found, then the allocation will put the system in an unsafe state.
Google +