Deadlock Detection Algorithm : Deadlock Detection Control:Centralized : Distributed:Hierarchical

In this lecture you will understand the concept of Deadlock Detection control Algorithm like : Centralized Deadlock Detection Algorithms ,Distributed Deadlock Detection Algorithm, Hierarchical Deadlock Detection Algorithms .

Deadlock Detection :
Principle of operation:
Occurrence of a cycle between Resource and Process in WFG is known as Deadlock Detection.
Detection of a cycle in WFG.
Deadlock detection is the most popular strategy for handling deadlocks in distributed systems
How to Detect and resolve Deadlock ?
Detection:
The algorithm must detect all existing deadlock in finite time.
The algorithm should not report non-existent deadlock.
Resolution (recovery):
All existing wait-for dependencies in WFG must be removed, i.e. roll-back one or more processes that are deadlocked and give their resources to other blocked processes

Deadlock Detection Control :
We can control Deadlock detection in 3 types/ ways:
Centralized b. Distributed c. Hierarchical
 1 Centralized Deadlock Detection Algorithms: In this, Only one node is responsible for building and analyzing a real WFG(wait for graph) for a cycle.
Each site maintain its WFG and update control site periodically or on request.
A central control site constructs the global WFG and searches for cycles.
Control site maintains WFG continuously (asking all sites for WFG updates). 
All sites request resources and release resources by sending corresponding messages to control site.
Control site updates WFG for each request and release of resources.
For every new request, Edge added to WFG and control site checks WFG for deadlock.
Disadvantages: Single point of failure and congestion.


2. Distributed Deadlock Detection Algorithm: In this, each node (all nodes) participates equally in detecting the deadlocks… WFG.
Principle:
All sites are responsible for detecting a global deadlock.
Global state graph distributed over many sites: several of them participate in detection
Detection initiated when a process suspected to be deadlocked.

Advantages: No single point of failure and no congestion.

Disadvantages: Difficult to implement (there is no shared memory).

3. Hierarchical Deadlock Detection Algorithms : In this, Nodes are organized or arranged in a tree pattern.
Principle:
In this, the sites are organized in a tree structure with one site at the root of the tree.
Each node (except for leaf nodes) has information about the dependent nodes.
Deadlock is detected by the node that is the common ancestor of all sites which have resource allocations in conflict.
Deadlock is detected at the lowest level.
In this, Sets of nodes are required to report periodically to a control site node (as with centralized algorithms) but control sites are organized in a tree structure.
The master control site forms the root of the tree, with leaf nodes having no control responsibility, and interior nodes serving as controllers for their branches.

for more videos , subscribe the channel: Computer Science Academy by Dinesh Sir.