Categories

A sample text widget

Etiam pulvinar consectetur dolor sed malesuada. Ut convallis euismod dolor nec pretium. Nunc ut tristique massa.

Nam sodales mi vitae dolor ullamcorper et vulputate enim accumsan. Morbi orci magna, tincidunt vitae molestie nec, molestie at mi. Nulla nulla lorem, suscipit in posuere in, interdum non magna.

Deadlock avoidance and prevention

Deadlock Prevention

In order to prevent deadlock, the system is built in such a way that no deadlock occurs. Make sure that at least one of the four conditions in which deadlock can occur does not exist.

Attacking Hold and wait : In order to ensure that hold and wait condition never occurs, two protocols can be used:
• Make all the requests in the beginning. All or nothing policy.
• A process should request a resource only when it has none.

Attacking Pre-emption : To avoid this situation, the protocol that can be used is if a process that is holding some resources requests another resource that cannot be allocated immediately, then all the resources currently held are released. These released resources gets added to the list of resources for which process is waiting.

Or, if process requests a resource, check their availability, if available allocate them. If not, check if they are allocated to other process that is waiting for additional resources. If so, preempt the desired resources from waiting process and allocate to requesting process. If not available, requesting process should wait.

Attacking Mutual Exclusion : This condition holds for nonsharable resources e.g printer. Sharable resources do not require a mutually exclusive access, and thus cannot be involved in a deadlock.

Attacking Circular Wait Condition : To prevent this condition, use the following protocol:
• Order all the resources.
• Make sure that the requests are issued in such a way so that there are no cycles present in the graph.
• Resources can be requested only in an increasing order i.e. we cannot request a resource whose number is less than any you may be holding.

Deadlock Avoidance

It turns out that there are algorithms you can use to avoid deadlock. The principle is as follows: Whenever you are about to make an allocation, you can run this algorithm and see if making that allocation would lead to a deadlock.This seems like
the ideal method but has some important drawbacks.Let us see what these drawbacks are:
1. The algorithms are not that fast and there is a lot of overhead in running them before every resource allocation. The OS might be allocating resources hundreds of times a second.
2. The algorithms assume that processes know their maximum resource needs a priority. But this is often not the case.
3. They (processes) assume that they know what resources are available in the system. Hardware can go down and resources can become unavailable. This could lead to unpredictable deadlock situations.
In short, in deadlock avoidance method, the OS must be given in advance additional information concerning which resources a process will request and use during its lifetime.

Here are some salient points of the algorithm working nature:
• The deadlock avoidance algorithm dynamically examines the resource allocation state to ensure that there can never be a circular-wait condition.
• A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid deadlock.
• A system is in a safe state only if there exists a safe sequence.
• A safe state is not a deadlocked state but a deadlocked state is an unsafe state.
• An unsafe state may lead to a deadlock.

Safe State

A state is safe if the system can allocate resources to each process in some order and avoid deadlock. A safe sequence is a sequence of processes
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 the resources held by all Pj with j <= i . In this situation, if the resources that process Pi needs are not immediately available, then Pi can wait until all Pj have finished. When they have finished, Pi can obtain all its needed resources, complete its designated task, return its allocated resources, and terminate. When Pi terminates, Pi+1 can obtain its needed resources and so on. If no such sequence exists, then the system state is said to be unsafe. Resource Allocation Graph Algorithm Deadlocks can be described more precisely in terms of directed graphs called a system resource allocation graph. A directed edge Pi -> Rj is called request edge which signifies that process Pi requested an instance of resource Rj. A directed edge Rj->Pi is called assignment edge which signifies that resource Rj is allocated to process Pi. A directed edge Pi–>Rj is called a claim edge which indicates that process Pi can request resource Rj at some time in future. When process Pi requests resource Rj the claim edge becomes a request edge. Similarly, when a resource Rj is released by Pi, the assignment edge is converted to a claim edge.

Suppose process P1 requests resource Rj. Request is granted only if this request edge is converted to an assignment edge, hence not resulting in the formation of a cycle in resource allocation graph. Hence the process has to wait for the resource.

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>