# Deadlock

[Slides](https://hackmd.io/pGmMX5tjSW6P3UiLK0X-8Q)

* https://www.geeksforgeeks.org/deadlock-prevention/
* https://www.geeksforgeeks.org/deadlock-detection-recovery/
* https://www.geeksforgeeks.org/deadlock-detection-in-distributed-systems-2/
* https://docs.aws.amazon.com/codeguru/latest/reviewer-ug/welcome.html
* https://patents.google.com/patent/US8261280
* An actual case: https://www.sqlshack.com/how-to-resolve-deadlocks-in-sql-server/

## Distributed Deadlock Detection HO Ramamurthy (Two-Phase Algorithm)

Distributed deadlock detection is a process used to identify and resolve deadlock situations in distributed systems. Distributed deadlock detection is a complex computing task that requires coordination between multiple computer nodes. The Two-Phase Algorithm, developed by HO Ramamurthy, is a distributed deadlock detection algorithm that is based on the concept of “global snapshots.”

The Two-Phase Algorithm begins by having each node in the distributed system take a local snapshot. The snapshot includes information about the current state of each node in the system, including the resources each node is holding, the resources each node is requesting, and the resources each node is waiting to receive. Each node then sends this snapshot to every other node in the system.

Once all nodes have received each other’s snapshots, the algorithm enters its second phase. During this phase, each node compares the received snapshots to determine if any node is in a state of deadlock. If a deadlock is detected, the algorithm identifies which node is causing the deadlock and how to resolve it. For example, the algorithm may require that the node causing the deadlock release certain resources, or that it request additional resources.

The Two-Phase Algorithm is an efficient and reliable distributed deadlock detection algorithm that is used in many distributed systems. It is able to detect deadlocks quickly and reliably and it is able to identify the cause of the deadlock.

# This program implements HO Ramamurthy's Two-Phase Algorithm for distributed deadlock detection

# Define the data structures necessary to store the snapshot information
snapshots = []
resource_dict = {}

# Function to take a local snapshot of a node
def take_snapshot(node):
    # Store the node's current state in the snapshot list
    snapshots.append(node.current_state)

    # Store the node's resources in the resource_dict
    for resource in node.resources:
      resource_dict[resource] = node

# Function to send each node's snapshot to all other nodes in the system
def send_snapshots():
    for snapshot in snapshots:
        for node in system.nodes:
            if node != snapshot.node:
                node.receive_snapshot(snapshot)

# Function to compare the received snapshots and detect deadlock
def detect_deadlock():
    # Iterate through all snapshots
    for i in range(len(snapshots)):
        snapshot1 = snapshots[i]

        # Iterate through all other snapshots
        for j in range(i+1, len(snapshots)):
            snapshot2 = snapshots[j]

            # Compare the two snapshots
            if snapshot1.resources_waiting == snapshot2.resources_held and \
               snapshot2.resources_waiting == snapshot1.resources_held:
                
                # Deadlock detected!
                # Return the nodes causing the deadlock
                return (snapshot1.node, snapshot2.node)

# Function to resolve the deadlock
def resolve_deadlock(node1, node2):
    # Node 1 must release the resources it is holding
    node1.release_resources()

    # Node 2 must request additional resources
    node2.request_resources()

Resources sounds fairly generic, so here's some examples of what we mean by resources, by calling the python functions with realistic data:

# Create some resources
disk_space = Resource("Disk Space", 50)
memory = Resource("Memory", 100)
cpu = Resource("CPU", 5)

# Take a snapshot of node A
take_snapshot(nodeA)

# Take a snapshot of node B
take_snapshot(nodeB)

# Send the snapshots to all other nodes
send_snapshots()

# Detect deadlock
node1, node2 = detect_deadlock()

# Resolve the deadlock
resolve_deadlock(node1, node2)

## Tools for preventing some deadlock:
https://docs.aws.amazon.com/codeguru/latest/reviewer-ug/welcome.html

## Practice Your Response To These Questions:

1. What is a deadlock and how does it occur?
2. What are the four necessary conditions for a deadlock to occur?
3. How can a deadlock be prevented?
4. Describe the technique of time-slicing as a method of preventing deadlocks.
5. How can a deadlock be identified in a system?
6. What techniques can be used to resolve a deadlock?
7. Describe the process of breaking a deadlock using the wait-die and wound-wait algorithms.