67 %
33 %
Information about deadlocks

Published on September 17, 2007

Author: Flemel


Deadlocks:  Deadlocks Chapter 3 3.1. Resource 3.2. Introduction to deadlocks 3.3. The ostrich algorithm 3.4. Deadlock detection and recovery 3.5. Deadlock avoidance 3.6. Deadlock prevention 3.7. Other issues Resources:  Resources Examples of computer resources printers tape drives tables Processes need access to resources in reasonable order Suppose a process holds resource A and requests resource B at same time another process holds B and requests A both are blocked and remain so Hardware and software deadlocks Resources:  Resources Deadlocks occur when … processes are granted exclusive access to devices we refer to these devices generally as resources Resources may have multiple copies Preemptable resources can be taken away from a process with no ill effects (for example memory) Nonpreemptable resources will cause the process to fail if taken away (e.g. CDR) Resources:  Resources Sequence of events required to use a resource request the resource use the resource release the resource Must wait if request is denied requesting process may be blocked may fail with error code Nature of requesting a resource is highly system dependent (e.g. request system call) Resource Acquisition:  Resource Acquisition t Introduction to Deadlocks:  Introduction to Deadlocks Formal definition : A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause Usually the event is release of a currently held resource None of the processes can … run release resources be awakened Number of processes and resources is unimportant Introduction to Deadlocks:  Introduction to Deadlocks Different from starvation and livelock Starvation – one process is active, but never gets the resource Livelock – all processes starve Four Conditions for Deadlock:  Four Conditions for Deadlock Mutual exclusion condition Each resource assigned to 1 process or is available Hold and wait condition Process holding resources can request additional No preemption condition Assigned resources cannot be involuntarily claimed Circular wait condition Must be a circular chain of 2 or more processes Each is waiting for resource held by next member of the chain Dealing with Deadlocks:  Dealing with Deadlocks Strategies Just ignore the problem altogether (Ostrich Alg.) Allow deadlock, detect it, break it Prevention Negate one of the four necessary conditions Dynamic avoidance Careful resource allocation – each resource request is analyzed and denied if deadlock might result The Ostrich Algorithm:  The Ostrich Algorithm Pretend there is no problem Reasonable if deadlocks occur very rarely cost of prevention is high UNIX and Windows takes this approach It is a trade off between convenience correctness Deadlock Prevention & Avoidance:  Deadlock Prevention andamp; Avoidance Deadlock prevention Define a global ordering of all resources Each process locks resources in order Resource can be unlocked at any time Useful within multi-threaded programs Deadlock avoidance – 'Banker’s Algorithm' Detection: Deadlock Modeling:  Detection: Deadlock Modeling Modeled with directed graphs resource R assigned to process A process B is requesting/waiting for resource S process C and D are in deadlock over resources T and U Deadlock Modeling:  How deadlock occurs A B C Deadlock Modeling Detection with One Resource of Each Type:  Detection with One Resource of Each Type A…G: processes; R…W: resources Note the resource ownership and requests Is this system deadlocked and if yes, which processes are involved? A cycle can be found within the graph, denoting deadlock Detection with One Resource of Each Type:  Detection with One Resource of Each Type We need a formal algorithm for detecting deadlocks A simple one to detect cycles: Use resource graph Perform DFS (depth first search) starting at each node, looking for cycles (recurrence of starting node) If it comes to a node it has encountered in this run, then there exists a cycle. Why use DFS and not BFS? Review DFS vs. BFS. Pseudocode for Deadlock Detection:  Pseudocode for Deadlock Detection For i=1 to N nodes { reset graph to unmarked; L = empty list; traverse_graph (node[i]); } traverse_graph (node) { add node to L; check for cycle in L; if (there exists outgoing unmarked arcs from node) { mark node-andgt;outgoing; traverse_graph (node-andgt;outgoing); } } Detection: Time Complexity:  Detection: Time Complexity N nodes, E arcs Time complexity for DFS is O (N + E) Need to do DFS N times (once for each node) O (N (N + E)) Check for cycles Simple way: can check every node visited to see if it is equal to root – O(1) complexity Better: check for any cycle in branch – worse case O (N ) Total complexity O (N (N + E) + N ) = O (2N + NE) = O (N + NE) N andlt;andlt; E, so N andlt;andlt; N E, total complexity is O (NE) 2 2 2 2 2 Detection: How often to run?:  Detection: How often to run? After every allocation of resource is too expensive Every few minutes When CPU is idle – indication of blocked processes waiting for resources Detection with Multiple Resources of Each Type:  Detection with Multiple Resources of Each Type Basic idea: Allocate resources to a process that can be run to completion 4 data structures: Vector of resources in existence E = # of resource i in system Vector of available resources, A = # of available resource i Allocation matrix C = # of resource j that are being held by process i Request matrix R = # of resource j that are requested by process i i i ij ij Detection with Multiple Resources of Each Type:  Detection with Multiple Resources of Each Type Invariant property: Σi=1Cij + Aj = Ej n Detection with Multiple Resources of Each Type:  Detection with Multiple Resources of Each Type Deadlock detection is based on comparing vectors: Algorithm Look for an unmarked process, Pi for which the i-th row of R is less or equal to A If such a process is found, add the i-th row of C to A, mark the process and go back to step 1 If no such process exists the algorithm terminates Detection with Multiple Resources of Each Type:  Detection with Multiple Resources of Each Type Unmark all processes; While (there exists unmarked processes) for i = 1to n processes { can_satisfy = TRUE; for j = 1 to r resources { if (Rij andgt; Aj) { can_satisfy = FALSE; break; } } if (can_satisfy) { for j = 1 to r resources // Release resources since alloted to process i Aj += Cij; // process i can finish and release its resources mark process; } } Detection with Multiple Resources of Each Type:  Detection with Multiple Resources of Each Type An example for the deadlock detection algorithm (3/2/1) Recovery from Deadlock:  Recovery from Deadlock Recovery through preemption Take a resource from some process to allow others to complete Depends on nature of the resource Recovery through rollback Checkpoints are written to a file and include memory image, resource state, and other state variables Lose work that was done after checkpoint since roll back returns machine back to checkpoint state Checkpoints are considered safe states Total rollback means that no safe state existed; restart process Kill process to release resources Need to make sure process can be started again later w/o ill effects Recovery from Deadlock:  Recovery from Deadlock Abort all deadlocked processes Expensive – lose data and results of computation Deadlock may occur again if all processes restarted Abort one process at a time until no deadlock Lots of overhead – after each process is aborted, must do detection again Which process to abort? Abort the one that incurs minimal cost Factors – priority, how long process has run, type of resource process has, requested resources, type of process Deadlock Prevention: Attack 4 Deadlock Conditions:  Deadlock Prevention: Attack 4 Deadlock Conditions Condition Approach Problem Mutual -Spooling – exp. only printer -Not all devices can be spooled Exclusion daemon requests printer Competition for spooler space can become deadlocked Hold andamp; Wait -Require all processes to Condition request all resources before running (then, can use Banker’s) -Allow processes access to only -Not practical for some cases 1 resource at a time. (exp. Copy between 2 disks) No Preemption -Allow preemption -Not viable for some resources (exp. Printers) Circular Wait -Order resources numerically -There may be too many Processes must make requests resources to numerically order in order. (database tables, for exp.) Deadlock PreventionAttacking the Mutual Exclusion Condition:  Deadlock Prevention Attacking the Mutual Exclusion Condition Some devices (such as printer) can be spooled only the printer daemon uses printer resource thus deadlock for printer eliminated Not all devices can be spooled Principle: avoid assigning resource when not absolutely necessary as few processes as possible actually claim the resource Attacking the Hold and Wait Condition:  Attacking the Hold and Wait Condition Goal: Prevent processes that hold resources from waiting for more resources Require processes to request resources before starting a process never has to wait for what it needs Problems may not know required resources at start of run also ties up resources other processes could be using Variation: process must give up temporarily all resources before requesting a new one then request all immediately needed Attacking the No Preemption Condition:  Attacking the No Preemption Condition This is not a viable option Consider a process given the printer halfway through its job now forcibly take away printer !!?? Attacking the Circular Wait Condition:  Attacking the Circular Wait Condition Normally ordered resources A resource graph (a) (b) Attacking the Circular Wait Condition:  Attacking the Circular Wait Condition Rule: All requests of a process must be made in numerical order =andgt; the resource allocation graph can not have cycles Either i andlt; j or i andgt; j =andgt; can’t have deadlocks Same logic with multiple resources: at every instant one assigned resource will be the highest Problem: impossible to find an ordering to satisfy everyone Deadlock Avoidance:  Deadlock Avoidance So far we assumed that all requests take place at the beginning The system must be able to decide whether granting a resource request is safe or not Is there an algorithm that can always avoid deadlocks? Yes, if certain information is known in advance State of Resource Allocation: Safe & Unsafe States:  State of Resource Allocation: Safe andamp; Unsafe States Safe System is not deadlocked and can guarantee that all processes will finish. There is some scheduling order such that all processes finish. Unsafe System may not be deadlocked, but cannot guarantee that all processes can finish No scheduling order that guarantees all processes will finish, but process may be lucky and finish due to some processes releasing resources early Determining Safe/Unsafe Using Banker’s Alg.:  Determining Safe/Unsafe Using Banker’s Alg. Similar to deadlock detection Consider each request as it occurs and see if granting it leads to a safe state If a granting a resource leads to a deadlock cycle, then state is unsafe and do not grant Key assumptions: All processes need to declare their max resources #of processes and resources are fixed. Need to dynamically update resource allocation table for entering/exiting processes to handle dynamic environment Determining Safe & Unsafe States:  Determining Safe andamp; Unsafe States Use resource allocation table Examples for a single resource. Can be scaled to multiple resources Proc. Has Max (Needs) Proc. Has Max (Needs) A 3 9 6 A 4 9 5 B 2 4 2 B 2 4 2 C 2 7 5 C 2 7 5 Free: 3 Free: 2 What is the difference between detection alg. And Banker’s? Other IssuesTwo-Phase Locking:  Other Issues Two-Phase Locking Deadlock avoidance and prevention are difficult to use in practice for large dynamic systems Detection and recovery is more practical Two-phase locking is practical solution often used in databases Phase 1 process tries to lock all records it needs, one at a time if needed record found locked, start over (no real work done in phase one) If phase 1 succeeds, start phase 2 perform updates release locks Note similarity to requesting all resources at once Applicable in small-scale, such as process that updates a few records in a few tables Not useful for processes where release and restart is not possible Non-resource Deadlocks:  Non-resource Deadlocks Possible for two processes to deadlock Each is waiting for the other to do some task Can happen with semaphores Each process required to do a down() on two semaphores (mutex and another) If done in wrong order, deadlock results Solution is more careful programming

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 (Informatik) – Wikipedia

Der Zustand eines Deadlocks kann folgendermaßen definiert werden: Eine Menge von Prozessen befindet sich in einem Deadlock, ...
Read more

Deadlock - Wikipedia, the free encyclopedia

Distributed deadlock. Distributed deadlocks can occur in distributed systems when distributed transactions or concurrency control is being used.
Read more


Deadlocks treten auf, wenn sich mehrere Tasks dauerhaft gegenseitig blockieren, weil jeder der Tasks eine Sperre für eine Ressource aufrecht erhält, die ...
Read more

Erkennen und Beenden von Deadlocks

Wenn Deadlocks auftreten, geben die Ablaufverfolgungsflags 1204 und 1222 Informationen zurück, die im SQL Server 2005-Fehlerprotokoll erfasst werden.
Read more

Analysieren von Deadlocks mit SQL Server Profiler

SQL Server Profiler und SQL Server Management Studio verwenden Deadlock-Wartediagramme zum Beschreiben von Deadlocks. Das Deadlock-Wartediagramm enthält ...
Read more

The Deadlocks | Traktorrock from outta space

Heute gratulieren wir uns selber. 10 Jahre Deadlocks!!! Wer hätte das gedacht als wir im Sommer 2003 angefangen haben. Aber der Spaß und die Freude haben ...
Read more


Deadlocks Es kann eine Situation in einem Mehrprozess-System eintreten, in der mehrere Prozesse derart blockiert sind, dass keiner von ihnen (z. B. durch ...
Read more

Betriebssysteme - Deadlocks

Betriebssysteme - Deadlocks ! Version: (8c45d65) ARSnova 19226584 Uberblick Bedingungen f ur Deadlocks Damit ein Deadlock entsteht, m ...
Read more

Deadlock | Define Deadlock at

Deadlock definition, a state in which progress is impossible, as in a dispute, produced by the counteraction of opposing forces; standstill; stalemate: The ...
Read more