advertisement

deadlock

75 %
25 %
advertisement
Information about deadlock
Education

Published on December 12, 2008

Author: archana15

Source: authorstream.com

advertisement

Slide 1: DEADLOCK INTRODUCTION THE CONDITION FOR DEADLOCK RESOURCE ALLOCATION GRAPH DEADLOCK PREVENTION DEADLOCK AVOIDANCE DEADLOCK DETECTION RECOVERY FROM DEADLOCK DEADLOCK : DEADLOCK INTRODUCTION : A process request the resources, the resources are not available at that time, so the process enter into the waiting state. The requesting resources are held by another waiting process, both are in waiting state, this situation is said to be “Deadlock”. Resource Allocation Graph R1 R2 P1 P2 Slide 3: For example P1 and P2 are two processes, R1 and R2 are two resources. P1 request the resource R1, R1 held by process P2, P2 request the resource R2, R2 is held by P1, then both are entered into the waiting state. There is no work progress for process P1 and P2, it is also a Deadlock. Deadlock can be represented by Resource Allocation Graph. THE CONDITION FOR DEADLOCK : A Deadlocked system must satisfied the following 4 conditions. These are : MUTUAL EXCLUSION : Mutual exclusion means resource are in non-sharable mode only, it means only one process at a time can use a resource. If some other process requests that resource, the requesting process must be wait until the resource has been released. For example, line printers, the line printers are always in non-sharable mode only, only one process can use the resource at a time. Slide 4: 2. HOLD AND WAIT : Each and every process in the dead lock state, must holding at least one resource and is waiting for additional resources, that are currently being held by other processes. For example, consider the below figure : P1, P2, P3 are 3 processes, R1, R2, R3 and R4 are 4 resources, each process holding a resource and waiting for another resource. P1 holding the resource R3 and is waiting for resource R1. P2 holding resource R1 and R4, waiting for R2 and R3. P3 holding the resource R2 and is waiting for resource R4. R1r R1 R2 R3 R4 P1 P2 P3 Slide 5: 3. NO PREEMPTION : No preemption means resources are not released in the middle of the work, they released only after the process has completed its task. 4. CIRCULAR WAIT : In the previous figure, P1 is waiting for a resource R1 it is held by P2, P2 is waiting for R2, R2 held by P3, P3 waiting for R4, R4 held by P2, P2 waiting for resource R3 it is held by P1. P1 R1 P2 R2 P3 R4 P2 R3 It is said to be Circular Wait. Slide 6: RESOURCE ALLOCATION GRAPH : Deadlocks can be described precisely using a directed graph called a system resource allocation graph. This graph consists of a set of vertices V and a set of edges E. The set of vertices V is partitioned into two different types of nodes P = {P1, P2, P3…………….Pn}, the set of all active processes in the system, and R = {R1, R2,…………Rm}, the set of all resource types in the system. A directed edge from process Pi to resource type Rj is denoted by Pi Rj, it means that process Pi requested an instance of resource type Rj and is waiting for that resource. A directed edge from resource type Rj to process Pi is denoted by Rj Pi, it means that an instance of resource type Rj has been allocated to process Pi. A directed edge Pi Rj is called a request edge and a directed edge Rj Pi is called an assignment edge. Slide 7: Each process Pi is represented as a circle and each resource type Rj as a square. Instances of a resource type Rj are represented by dots within the square. R3 R4 Resource Allocation Graph R1r R1 R3 P1 P3 P2 R1r Slide 8: Fig. shows the resource allocation graph for the following situation : The sets P = { P1, P2, P3 }, R = {R1, R2, R3, R4 }, E = { P1 R1, P2 R3, R1 P2, R2 P2, R2 R1, R3 P3} Resource instances – 1 instance of resource type R1, 2 instances of resource type R2, 1 instance of resource type R3 and 3 instances of resource type R4. Process states – Process P1 is holding an instance of resource type R2, and is waiting for an instance of resource type R1. Process P2 is holding an instance of resource type R1 and R2, and is waiting for an instance of resource type R3. Process P3 is holding an instance of resource type R3. If a resource allocation graph contains no cycles, then no process in the system is deadlocked. If the graph contains a cycle, then deadlock may exist. Slide 9: DEADLOCK PREVENTION : The general meaning for prevention is take the medicine before the attack of diseases. Deadlock prevention is same as take the preventive methods before attacking the deadlock. For deadlock to occur, each of the four necessary conditions must hold, by ensuring that at least one of these conditions can’t hold, we can prevent the occurrence of the deadlock. So apply this technique on four necessary conditions separately. MUTUAL EXCLUSION : Mutual exclusion means resource are in non-sharable mode only, it means only one process at a time can use a resource. If some other process requests that resource, the requesting process must be wait until the resource has been released. We can deny this condition by simple protocol i.e., “convert the all non-sharable resources to sharable resources”. So this condition is not satisfied by the deadlock, then we can prevent the deadlock. Here is a simple correction, a printer is not shared by the number of process at a time, so we can’t convert the printer from non-sharable to sharable mode. So we can’t apply this preventive method if the system consisting of printers. Slide 10: 2. HOLD AND WAIT : Each and every process in the dead lock state, must holding at least one resource and is waiting for additional resources, that are currently being held by other processes. We can deny this condition with following two protocols : “A process request the resources only when the process has none”. This protocol is very expensive, and time consuming. For example, a process wants to copy the data from a tape drive to a disk file, and then take a print out. Initially the process consisting of tape drive, disk file. Now the process to be request the printer. Applying the above said protocol the tape drive and disk file before the request of printer. So it is time consuming. “Each process to request and be allocated all its resources before it begins execution”. It is very difficult to implement, because more number of resources are available to begin the execution. For example, P1, P2, P3,………………P100 are 100 processes . Each requires a printer to complete their jobs. Applying this protocol the system must consisting of 100 printers. So it is very difficult to implement. Slide 11: 3. NO PREEMPTION : No preemption means resources are not released in the middle of the work, they released only after the process has completed its task. To ensure that condition does not hold, we use the following protocol : A process request some resources, we first check whether they are available. If they are available we allocate them. If they are not available, we check whether they are allocated to some other process that is waiting for additional resources. If so, we preempt the desired resources from the waiting process and allocate them to the requesting process. If resources are not either available (or) held by a waiting process, then, the requesting process must wait. While it is waiting some of its resources may be used by other process. 4. CIRCULAR WAIT : We ensure that circular wait must not happened if we apply a simple solution, i.e., numbering all the resources types and each process request resources in an increasing order of enumeration. Alternatively whenever “A process requests an instance of resource type Rj, it has released any resource Ri, such that F(Ri) > F(Rj)” and the second protocol is Slide 12: “A process can initially request any number of instances of resource type, say Ri. After that the process can request the instances of resource type Rj, if and only if F(Rj) > F(Ri)”. If these 2 protocols are used, then the circular wait condition cannot hold. DEADLOCK AVOIDANCE : It is one of the methods of dynamically escaping from the deadlocks, the word dynamically means ‘online’. In this scheme if a process request for resources the avoidance algorithm checks before the allocation of resources about the state of system. If the state is safe, the system allocate the resources to the requesting process otherwise (unsafe) do not allocate the resources. So taking care before the allocation said to be deadlock avoidance. Safe state means “ no deadlock will happen, even we allocate the resources to requesting processes”. Unsafe means the deadlocks may happen if grant the resources . Consider the below figure for better understanding. Slide 13:  Unsafe Safe Deadlock Safe unsafe and deadlock state spaces Slide 14: A safe state is not a deadlock state. Conversely, a deadlock state is an unsafe state. Not all unsafe states are deadlocks, however, an unsafe state may lead to a dead lock. As long as the state is safe, the O.S. can avoid unsafe states. BANKER’S ALGORITHM : If multiple instances of resource are available in the system, then this algorithm is used. Assumption for Banker’s algorithm are as follows: Every process tells in advance, the number of resources of each type it may require. No process asks for more resources then what the system has. At the termination time every process will release resources. DATA STRUCTURE : The following data structures are used, where n be the number of processes and m be the number of resources. Slide 15: Available : A vector of length ‘m’ indicates that number of available resources of each type. If available [ j] = k, there are k instances of resource type Rj available. Max : A nXm matrix indicates maximum demand of each process. If max [i, j] = k, then process Pi may request at most k instances of resource type Rj. Allocation : A nXm matrix indicates number of resources of each type currently allocated to each process. If allocation [i, j] = k, then process Pi is currently allocated k instances of resource type Rj. Need : A nXm matrix indicates remaining resource need of each process. If need [i, j] = k, then process Pi may need k more instances of resource type Rj to complete its task. NECESSARY CONDITION: Need [i, j] = Max [i, j] – Allocation [i, j] Slide 16: SAFETY ALGORITHM : This algorithm checks whether a state is in safe state or not. This algorithm requires O(mXn2) operations. The steps of algorithm are as follows: Initialize Work : = Available and Finish [i ] = false for i= 1,2,3,……………….n Find an i such that both Finish [i ] := false Need [i ] <= work If no such I exists, go to step d. Work := Work + Allocation [i ] Finish [i ] := true Go to step b. If Finish [i ] := true for all I, then the system is in a safe state. Slide 17: RESOURCE - REQUEST ALGORITHM : To satisfy the request made by process Pi for resource following actions are required: If request [i ] <= Need [i ], go to step b else display error message. If request [i ] <= Available, go to step c else Pi must wait until the resources available. Available : = Available – Request [i ] Allocation [i ] : = Allocation [i ] + Request [i ] Need [i ] : = Need [i ] – Request [i ] If the resulting resource allocation state is in safe state, then resources are allocated to Pi. Slide 18: DEADLOCK DETECTION : Detection mechanism of deadlocks for single instance of resource type is different. We can detect the dead locks using wait for graph for single instance resource type and detect using detection algorithm for multiple instances of resource type. SINGLE INSTANCE OF RESOURCE TYPE : Single instance of resource type means, the system consisting of only one resource for one type. We can detect this type of deadlocks with the help of wait for graph. A wait for graph is a graph, it derived from ‘resource allocation graph’. It consisting of only processes as vertices instead of resources and processes in resource allocation graph. Consider the given figure. We represent a resource allocation graph and the corresponding wait for graph. An edge from Pi to Pj in a wait for graph implies that process Pi is waiting for process Pj to release a resource that Pi needs. An edge Pi to Pj exists in a wait for graph if and only if the corresponding resource allocation graph contains two edges Pi to Rq and Rq to Pj for some resource Rq. Slide 19: Resource Allocation Graph R1 R2 R3 R4 P1 P2 P3 Slide 20: P1 R1 P2 P2 R2 P3 P2 R3 P1 P3 R4 P2 Wait for graph A system is in deadlock state , if and only if the wait for graph contains cycles. So we can detect the deadlocks with cycles. In the figure there is 2 cycles one is P1 to P2 to P1, second one P2 to P3 to P2 so the system consisting of deadlocks. P1 P2 P3 Slide 21: 2. SEVERAL INSTANCE OF RESOURCE TYPE : The wait for graph is not applicable to several instance of resource type. So we need another method for this type, that is “deadlock detection algorithm”. This algorithm looks like ‘Banker’s algorithm” and it employees several data structures that are similar to those used in the Banker’s algorithm. DATA STRUCTURE: Available : A vector of length ‘m’ indicates the number of available resources of each type. Allocation : An nXm matrix defines the number of resources of each type currently allocated to each process. Request : An nXm matrix indicates the current request of each process. If request [I, j] = k, then process Pi is requesting K more instances of resource type Rj. Slide 22: DEADLOCK DETECTION ALGORITHM: Initialize Work: = Available If allocation [ i ] != 0 for i = 1,2,3,…………………….n. then Finish [ i ] = false, otherwise Finish [ i ] – true Find an index i such that both Finish [ i ] = false Request [ i ] < work if no such I exists, go to step 4 Work : = Work + Allocation [ i ] Finish [ i ] = true go to step 2 If Finish [ i ] = false, for some I than the system is in a deadlock state. Moreover, if Finish [ i ] = false then process Pi is deadlocked. Slide 23: RECOVERY FROM DEADLOCK : Once deadlock has been detected, some strategy is needed for recovery. The various approaches of recovering from deadlock are: PROCESS TERMINATION : “Process termination” it is one method to recover from deadlock. We use 2 methods for process termination, these are: ABORT ALL DEADLOCKED PROCESS : It means release all the processes in the deadlocked state, and start the allocation from the starting point. It is a great expensive method. ABORT ONE BY ONE PROCESS UNTIL THE DEADLOCK CYCLE IS ELIMINATED : In this method first abort the one of the processes in the deadlocked state, and allocated the resources to some other process in the deadlock state then check whether the deadlock breaked or not. If no, abort the another process from the deadlock state. Continue this process until we recover from deadlock. This method is also expensive but compare with first one it is better. Slide 24: RESOURCE PREEMPTION : To eliminate deadlocks using resource preemption, preempt some resources from processes and give these resources to other processes until the deadlock cycle is broken. There are 3 methods to eliminate the deadlocks using resource preemption. These are : SELECTING A VICTIM : Select a victim resource from the deadlock state, and preempt that one. ROLLBACK : If a resource from a process is preempted, what should be done with that process. The process must be roll backed to some safe state and restart it from that state. STARVATION : It must be guaranteed that resource will not always be preempted from the same process to avoid starvation problem.

Add a comment

Related presentations

Related pages

Deadlock – Wikipedia

Deadlock steht für eine Situation, in der sich beide Alternativen eines Dilemmas gegenseitig blockieren oder in der die Handlungspartner nicht zu ...
Read more

DEADLOCK - official website: new album THE ARSONIST ...

Official site of the German metal band. News, tour dates, bio, pics, media, guestbook, contact and links.
Read more

Deadlock (Band) – Wikipedia

Deadlock beim RockTheLake 2007: Allgemeine Informationen: Genre(s) Melodic Death Metal ... John Gahlert (Bass: 2009–2011, Gutturaler Gesang: seit 2011)
Read more

dict.cc | deadlock | Wörterbuch Englisch-Deutsch

Übersetzung für deadlock im Englisch-Deutsch-Wörterbuch dict.cc.
Read more

Deadlock - Wikipedia, the free encyclopedia

Deadlock can be avoided if certain information about processes are available to the operating system before allocation of resources, such as which ...
Read more

Deadlock - Facebook

Deadlock. 44,673 likes · 293 talking about this. booking: ludwig@extratours-konzertbuero.de management: management@deadlock-official.com label:...
Read more

Deadlock - definition of deadlock by The Free Dictionary

What with the Jay Cooke failure, the Hayes-Tilden deadlock, and the bursting of a hundred railroad bubbles, there was very little in the news of the day to ...
Read more

Deadlock (band) - Wikipedia, the free encyclopedia

Deadlock performing live at Rock The Lake festival in 2007. Background information; Origin: Schwarzenfeld, Bavaria, Germany: Genres: Melodic death metal,
Read more

Deadlock (1970) - IMDb

GET INFORMED. Industry information at your fingertips. GET CONNECTED. Over 200,000 Hollywood insiders. GET DISCOVERED. Enhance your IMDb Page. Go to IMDbPro »
Read more

Deadlock | Definition of Deadlock by Merriam-Webster

1: a state of inaction or neutralization resulting from the opposition of equally powerful uncompromising persons or factions : standstill Read more