Deadlock





Deadlock

Resources

Hardware or a piece of information which is access by operating system is called resource.  Hardisk, tape driver, etc  are examples of hardware and database is example of data resource. Deadlocks can occur when processes have been granted exclusive access to devices, files and soon. The resource can be divided into two types.

  1.  pre emptitable resource:-

The resource which can be taken away from the process without any ill condition. In case of permutable resource, the process can be switch to another resource and again it switches to it and complete the process. An example of pre-emptable resource is memory. Let us consider an example of memory and printer, a system with 256 k of user memory, and printer and 256 k processes that each want to print. Process A request and gets the printer then starts to compare the values of print before it has finished with the compaction, it excess its time  quantum and is swapped out.

  1. Non-preempt able resource:-

This resource cannot take away from the current computation without any error. In case of printer resource, if a process has begun to print output, taking the printer away from it and giving it to another process will result to garbled output. Therefore printers are non-pre emptitable resource.

The sequence of events required the use resources are:-

  1. Request the hardware.
  2. Use the resource.
  3. Release the resource.
  4. If this requested resource is not available, two process to force to wait. In case operating system the process is automatically blocked. When a resource request fails, and use when it seems available in other systems. The request fails with error code and it is up to the calling process to wait a little while and try again. The excrete nature of requesting resource is highly system dependent.

DEADLOCK

A set of processes is said to be deadlocked if each process is waiting for an event that only another process in the set can cause. Here, all the processes are waiting for resources that are use by another. In this case no process can access the resource and all the process is blocked.

*conditions for deadlock:-

1. Mutual exclusion condition:-

Each process is either currently assigned to exactly case process or is available.

2. Wait and hold condition:-

Process concurrently holding resource granted earlier can request new resource.

3. No pre emption condition:-

Resources previously granted cannot be forcibly taken away from a process. They must be explicitly rescued, by the process holding them

  1. 4.       Circular wait condition: -   there must be circular chain of two or more processes, each of which is waiting for a resource hold by the next member of the chain. All above four conditions must occur for dead lock. If one of them is not present no deadlock is caused.

Deadlock modeling:-

Deadlock can be modeled using direct graph. The graphs have two kinds of nodes processes shown by circle and resource shown by resources. An arc of a resource to process node means that the resource is hold by their process. Similarly on an arc from a process to resource means that the process is requesting for the resource.

deadlock modeling

deadlock modeling

In figure

  1.  Process A is holding a resource R.
  2. Process is requesting resources.
  3. There is a deadlock, process C is waiting for resource T, which is con currently hold by process D. process D is not about to measure resource T because it is waiting for resource U, hold by C. both the processes will wait forever. A cycle in a graph means that there is a deadlock involving the process and resources in the cycle.

dead lock handling

Stages for dealing with deadlocks:-

There are four ways for dealing with deadlocks. They are;-

  1. Just ignore the problem all together.
  2. Detection and recover.
  3. Dynamic avoidance by careful resource allocation.
  4. Prevention by structurally negating one of the four required condition.

Ostrich algorithm

It is a strategy to deal with deadlock. It is simplest approach. “Stick your head in sand and pretend there is no problem at all” is the main idea behind this algorithm. The general meaning of this statement is, we are ignoring a great problem. Different people react to this strategy in different ways. Mathematicians find it totally unacceptable and say that deadlock must be prevented at any costs. Engineer ask how often the problem is excepted, how serious a deadlock is ignoring the dead lock since it take more effort and the dead lock occurs rarely must engineering willing to pay a large penalty in performance or convenience to eliminate deadlock.

Let us take an example of UNIX system. It potentially suffers from deadlocks that are not even detected, let alone automatically broken. The total number of processes is determined by number of entities in the process table. Thus, the process table slots are finite resources. If new process comes then it fails to access, the solution of this is waiting it for random amount of time.

The Unix approach is just to ignore the problem on the assumption that must user would prefer an occasional deadlock to rule restricting all user to one process, one open file and one of everything. If the deadlocks could be eliminated for free, there could not be much discussion. The problem is that the price is high mostly in terms of putting inconvenient restrictions on processes, as we will use shortly.

Deadlock detection and recovery

The second technique is detection and recovery. Ehen this technique is used, the system does not attempt to prevent deadlock from occurring.  Instead it lets them occur, tries to detect when this happens and then takes some action to recover after the fault.

In this technique, whenever a resource is requested or released, the resource graph is updated, and checks whether the cycle exists or not. If cycle exists, one of the processes in cycle is killed and checks again whether the deadlock break or not. If the deadlock occurs again it again kill another process. The step continues until deadlock break.

This technique is mainly used in large system usually in batch system this technique is an acceptable. The main difficulty in this technique is to kill and restart the same process and update the process table or resource graph.

Deadlock prevention

Deadlock prevention means to ensure the restriction of deadlock occurrence. Thing strategy deals with the mechanism to block the condition to occur the deadlock. As we know, there are four conditions to occur a deadlock. If we can ensure that at least one of three conditions is never satisfied, then deadlock will be never occurred. The four conditions are:-

  1. Mutual exclusion
  2. Hold and wait
  3. No pre emption
  4. Circular wait

Let us discuss with first co9ndition if no resource were over assigned exclusively to a single process, we could never have deadlocks. Let us take an example of printer resources. In printer more processes can generate output at same time in this model, only process that actually request two physical printers is the available. And process does not request another only start printing after finding all information. In this case, we face dead lock in resource. So printer is not always assigning to that process.

In second condition, if we prevent processes that hold resources from waiting for more resources we can eliminate deadlock. One way to achieve this goal is to require processes to request all their resources before starting execution. If one or more resources are busy, then nothing would be allocated and process will just wait. For completion of task, process will not hold all the resource.

A slightly different way to break the hold and wait condition is to require a process requesting a resource to first temporarily release all the resources it currently holds only it the request is successful can it get the original resource back.

In dealing with third condition, if a process has been assigned the printer and is in the middle of printing its output, possibly taking away the printer because a needed plotter is not available will lead to a mess.

The circular wait can be eliminated in several ways one way is simply to have a rule saying that a process is entitled only to a single resource at any moment. If it needs the second one, it must release the first one for a process that needs to copy a huge file from a tape to a printer, this restriction is not acceptable. Another way to avoid the circular wait is global numbering. And the available resources are numbered to give the priority. The number help it assigned to the process.

Deadlock avoidance

After detecting a deadlock, the system must be able to avoid that deadlock as well it must be able to decide whether granting a resource is safe of not and only make a allocation when it is safe. There are certain ways to avoid deadlock by careful resources allocation.

  1. Safe and unsafe state: -     A state is said to be safe if it is not deadlocked and there is same scheduling order in which every process can run to completion, if all of them suddenly request their maximum number of resources immediately. Otherwise a sate is unsafe. In other word, a state is said to be safe if it is not deadlocked and is a way to satisfy all requests currently pending by running the process in same order.

 

deadlock avoidance

deadlock avoidance

 

In figure 1. We have a state in which A has 3 instances of resources and may need maximum of 9 B currently has 2 and may need 4 altogether similarly, C has 2 and may not need 7 more.

The state a. is safe because there exists a sequence of allocations that allows all processes to complete.

  1. Banker’s algorithm for a single resource: -     The banker’s algorithm first checks to see if granting request leads to an unsafe mode. If it does, the request is denied. Otherwise, if granting a request leads to safe state, it is granted, otherwise, it is postponed until later. To see if a state is safe, the banker checks if he has enough resource to satisfy some customer. If so, these loans are assumed to be repaid, and the customer closest to the limit is checked and soon. If all loans are essentially being repaid, the state is safe and the initial request can be granted.

 

deadlock avoidance

deadlock avoidance

 

Analyzing the above states, we came to conclusion that deadlock avoidance is impossible in the system because the future request of resource should be available in advance which is not rational.



Related posts:

  1. processes creation A process can create several new processes. The creating process...
  2. Mutual Exclusion of Processes Mutual exclusion is a mechanism to ensure that only one...
  3. Processes Scheduling queue As processes enter the system they put in job queue....
  4. Introduction to operating system Operating System: An operating system is a collection of system...
  5. What is kernel? Kernel: All the operating involving processes are controlled by a...