DistributedDeadlock on distriburtedNetwork.pptx

ppt on distributed deadlock

1. What are Deadlocks ? Deadlock is a state of a database system having two or more transactions, when each transaction is waiting for a data item that is being locked by some other transaction . Locking-based CC algorithms may cause deadlocks. Deadlock in a distributed database system occurs when two or more transaction are blocked because each transaction is holding a resource that the other transaction requires. As a result, neither transaction can continue until the resources held by the other transaction are released. This can lead to a permanent blockage and a halt of the system, resulting in lost data or decreased efficiency.

2. The necessary conditions for a deadlock to occur in a distributed database system are : Mutual Exclusion: At least one resource must be held in a non-shareable mode, meaning that only one process can access the resource at a time. Hold and Wait: A process must hold one or more resources while waiting for additional resources to become available. No Preemption : Resources cannot be forcibly taken from a process. A process must voluntarily release resources. Circular Wait: There must be a cycle of processes waiting for resources held by others in the cycle. These four conditions must all be met simultaneously for a deadlock to occur in a distributed database system.

3. Deadlock Handling Dealing with Deadlocks:  PAID Prevention Guarantee that deadlocks can never occur . Check transaction when it is initiated. Avoidance Detecting potential deadlocks in advance and taking action to insure that deadlock will not occur. Requires run time support Ignorance Let the application programmer deal with it, or restart the system Detection and Recovery Allowing deadlocks to form and then finding and breaking them. As in the avoidance scheme, this requires run time support. All the approaches can be incorporated in both a centralized and a distributed database system.

4. Deadlock Prevention Deadlock is  prevented  when any  one  of the four conditions for deadlock is denied, prohibited, or otherwise prevented from ever occurring. Collective Requests : For instance, in order to prevent the  Hold & Wait  condition from happening, each process can be required to collect simultaneously all its needed resources before it can begin processing.If it is unable to acquire all of its resources at once, it must give up all its current resources, and then try to request them all again later.No partial allocation is permitted.In this manner, it will never be waiting for a resource, once it begins execution. Unfortunately, it is not really possible to acquire all the resources simultaneously when they are on different sites. However, the system can get into trouble doing this serially, as processes can become deadlocked while in the resource collection stage. Furthermore, this is inefficient and decreases system concurrency. This degrades resource utilization. It also leads to starvation for those processes with large resource needs. In addition, it requires each process to know all its possible future resource needs.

5. Deadlock Prevention Ordered Requests : All resources are classified into a fixed order of many different levels.A process can only request resources in classes higher than the classes it currently holds  (i.e., batch/collective allocation by by levels) . However, this method also degrades resource utilization, as processes are gathering and holding onto resources as they move up the chain. Preemption : The idea is to permit preemption, getting rid of the  No Preemption  condition. Access to the CPU, main memory, and a database can easily be preempted, and these are often considered the most important resources. However, this would be a problem in real-time systems, as data may be lost before you come back to it.

6. Deadlock Prevention Non- Preempted Approach In this algorithm, each process is assigned a timestamp based on the order in which it requests resources. If a process requests a resource that is held by another process, the process with the older timestamp waits and the process with the newer timestamp is allowed to proceed . Example: WAIT-DIE Rule Preempted Approach This method assigns a priority to each transaction and allows the transaction with the higher priority to wound the transaction with the lower priority, causing it to abort and release any locked data items. If two transactions have the same priority, the transaction requesting the data item that has been locked the longest waits . Example : WOUND-WAIT Rule

7. Wait-Die Algorithm WAIT-DIE Rule : If T i requests a lock on a data item which is already locked by T j , then T i is permitted to wait iff ts ( T i )< ts ( T j ). If ts ( T i )> ts ( T j ), then T i is aborted and restarted with the same timestamp. if ts ( T i )< ts ( T j ) then T i waits else T i dies non-preemptive: T i never preempts T j prefers younger transactions

8. Wound-Wait Algorithm WOUND-WAIT Rule: If T i requests a lock on a data item which is already locked by T j , then T i is permitted to wait iff ts ( T i )> ts ( T j ). If ts ( T i )< ts ( T j ), then T j is aborted and the lock is granted to T i . if ts ( T i )< ts ( T j ) then T j is wounded else T i waits preemptive: T i preempts T j if it is younger prefers older transactions

9. Deadlock Prevention: Wait/Wound/Die Algorithms Both the Wait-Die and Wound-Wait methods can be used to prevent deadlocks in a transaction-based system. The choice of method depends on the specific requirements and constraints of the system. The Wait-Die method is appropriate for systems where transactions are short-lived and the risk of deadlocks is low , while the Wound-Wait method is more appropriate for systems where transactions are long-lived and deadlocks are more likely to occur.

10. Deadlock Detection wait-for-graphs have cycles or knots in the case of deadlock.This means deadlock can be detected by just checking the WFG for cycles . The advantages of this approach is Once the WFG has a cycle, that cycle will persist. This means that detection can happen concurrently with normal processing. Thus, deadlock detection is used for most distributed systems. To detect deadlock, the system just needs to maintain a WFG, and periodically invoke a algorithm that looks for cycles in the WFG . E ach site in a distributed system can maintain its own  local WFG , periodically exchanging this information with other sites to update a  global WFG . Deadlock detection algorithms must maintain the WFG and search the WFG for cycles and knots.

11. Deadlock Detection The main difficulty is how to maintain the WFGs. Deadlock detection algorithms should meet the following conditions for correctness : Progress , meaning there should be no undetected deadlocks The algorithm must detect existing deadlocks within a finite amount of time. Once the WFG indicates the existence of deadlock, the algorithm should not wait for more arcs in the WFG to detect the deadlock. Safety, meaning there should be no  false deadlocks The algorithm should not report  phantom deadlocks . Since a global state in a distributed system is put together by communicating messages, a global WFG may include out-of-date arcs that appear to denote a cycle in the system. It is hard to create algorithms that are not confused by this.

12. Deadlock Detection and Recovery Resolution of Deadlock can be handled by Killing a transaction in the cycle(s); Preempting the resources from a transaction in the cycle(s); Rolling back a transaction in the cycle(s). The resources of this transactions are then released and may be acquired by other transactions .

13. Control Organization for Distributed Deadlock Detection Algorithms Algorithms for detecting distributed deadlock can be handled in three different ways : Centralized Distributed Hierarchical

14. Centralized One central site sets up a global WFG and searchs for cycles.All decisions are made by the central control node . It must maintain the global WFG constantly  or Periodically reconstruct it. The main advantage is that this permits the use of relatively simple algorithms. The disadvantages include the following : There is one, single point of failure. There can be a communication bottleneck around the site due to all the WFG information messages.

15. Hierarchical The sites (nodes) are logically connected in a hierarchical structure (such as a tree).A site can detect deadlock in its descendants. This type of algorithm has the best of both the centralized and the distributed deadlock detection algorithms. For efficiency purposes, it is best to keep clusters of interacting processes together in the hierarchy.

16. Distributed In a distributed control organization, All sites have an equal amount of information. All sites make decisions based on local information. All sites bear equal responsibility for the final decision in detecting deadlock. All sites expend equal effort to the final decision. The global WFG is spread across the sites. Deadlock detection is initiated whenever a process thinks there might be a problem. Several sites can initiate the detection at the same time

17. Distributed The advantages include the following : There is no central point of failure. A single node failure cannot cause a crash. There is no  one  site with heavy traffic due to the detection algorithm. The algorithm is only initiated when process( es ) feel there might be a problem. The algorithm is not run periodically, only when needed. The main disadvantage is that resolution may be difficult, as not all sites may be aware of the processes involved in the deadlock.The proof of correctness for this type of algorithm may be difficult.

18. Wait-for graph A deadlock can be indicated by a cycle in the wait-for-graph. This is a directed graph in which the vertices denote transactions and the edges denote waits for data items. If transaction T i waits for another transaction T j to release a lock on an entity, then T i  T j in WFG. Wait for Graph T i T j

19. L ocal wait-for graph A local wait-for graph is a directed graph that represents the resource allocation and waiting relationships of the transactions within a single node in a distributed database system. Each node in the local wait-for graph represents a transaction, and each directed edge represents a resource request or allocation. For example, if transaction T1 is waiting for a resource held by transaction T2, there will be a directed edge from node T1 to node T2 in the graph. The local wait-for graph is used to detect deadlocks that may occur within a single node in the distributed system. By analyzing the relationships between transactions and resources, the local wait-for graph helps to identify cycles in the resource allocation and waiting relationships, which can indicate the presence of a deadlock.

20. Global wait-for graph A global wait-for graph is a directed graph that represents the resource allocation and waiting relationships of all processes across all nodes in a distributed database system. Each node in the global wait-for graph represents a process, and each directed edge represents a resource request or allocation. For example, if process A in node 1 is waiting for a resource held by process B in node 2, there will be a directed edge from node A to node B in the graph. The global wait-for graph provides a comprehensive view of the resource allocation and waiting relationships across the entire distributed system, helping to detect deadlocks that may not be visible in a local wait-for graph.

21. Local WFG versus Global WFG