INTRODUCTION

A distributed system can be visualized as a set of sites, each site consisting of a number of independent processes. No process knows the global state of the whole system. The processes communicate through messages. The communication is asynchronous and a message may take an arbitrary but finite time. A distributed operating system is one that looks to its user like an ordinary centralized operating system but runs on multiple, independent central processing units (CPUs). The key concept here is transparency. In other word, the use of multiple processors should be invisible to the user. A distributed operating system (OS) is an operating system is a generalization of a traditional operating system. A distributed OS provides the essential services and functionality required of an OS, adding attributes and particular configurations to allow it to support additional requirements such as increased scale and availability. To a user, a distributed OS works in a manner similar to a single-node, monolithic operating system. That is, although it consists of multiple nodes, it appears to users and applications as a single-node.

In a distributed system if a process needs a resource on another site for its computation, it sends a message to the manager of that site through a communication network to request access to the resource. If the resource is available, it will be granted to the requesting process; otherwise, the requesting process may need to wait until the resource is acquired. In this environment, a deadlock may occur in which processes involved in the deadlock are waiting indefinitely in a circular fashion until a special action is taken.

 

 

TYPES OF DEADLOCK DETECTION

ALGORITHMS

1 Path Pushing

The first distributed algorithms for the deadlock problem maintained the notion of an explicit global WFG, which had worked so well in the centralized case. In path-pushing algorithms, distributed deadlocks are detected by maintaining an explicit global WFG. The basic idea is to build a global WFG for each site of the distributed system. In this class of algorithms, at each site whenever deadlock computation is performed, it sends its local WFG to all the neighboring sites. After the local data structure of each site is updated, this updated WFG is then passed along to other sites, and the procedure is repeated until some site has a sufficiently complete picture of the global state to announce deadlock or to establish that no deadlocks are present. This feature of sending around the paths of global WFG has led to the term path-pushing algorithms. Many of these algorithms were found to be incorrect as they were not able to detect true deadlocks or detected phantom deadlocks.

 

2 Edge Chasing Algorithms

In an edge-chasing algorithm, the presence of a cycle in a distributed graph structure is be verified by propagating special messages called probes, along the edges of the graph. These probe messages are different than the request and reply messages. The formation of cycle can be detected by a site if it itself receives the matching probe sent by it previously. Whenever a process that is executing receives a probe message, it discards this message and continues. Only blocked processes propagate probe messages along their outgoing edges. Main advantage of edge-chasing algorithms is that probes are fixed size messages which are normally very short.

 

3 Global State Detection Based

Algorithms

A consistent snapshot of a distributed system can be obtained without freezing the underlying computation and If a stable property holds in the system before the snapshot collection is initiated, this property will still hold in the snapshot. Therefore, distributed deadlocks can be detected by taking a snapshot of the system and examining it for the condition of a deadlock. This type of algorithms fall into the category of Global state detection.

 

4 Diffusion Computation Based

Algorithms

In diffusion computation based distributed deadlock detection algorithms; deadlock detection computation is diffused through the WFG of the system. These algorithms make use of echo messages to detect deadlocks. This computation is superimposed on the underlying distributed computation. If this computation terminates, the initiator declares a deadlock. To detect a deadlock, a process sends out messages along all the outgoing edges in the WFG. These messages are successively propagated (i.e., diffused) through the edges of the WFG.

The general idea behind diffusion computation approach is this: A process determines if it is deadlocked by initiating a diffusion computation. The messages used in diffusion computation take the form of a query (i, j, k) and a reply (i, j, k), denoting that they belong to a diffusion computation initiated by a process Pi and are being sent from process Pj to process Pk. If an active process receives a query or reply message, it discards it. When a blocked process Pk receives a query (i, j, k) message, it takes the following actions: If this is the first query message received by Pk for the deadlocked detection initiated by Pi (called the engaging query), then it propagates the query to all the processes in its dependent set and sets a local variable num k(i), to the number of query messages sent. If this is not an engaging query, then Pk returns a reply message to it immediately, provided Pk has been continuously blocked since it received the corresponding engaging query. Otherwise, it discards the query. A local boolean variable wait k(i) at process Pk denotes the fact that it has been continuously blocked since it received the last engaging query from process P i .

fig.1 shows three sites having different processes. A blocked process say P1 initiates the algorithm and sends a probe (1, 1, 2) and P2 passes it to P3 as probe(1, 2, 3) which forwards it to P4 on another site as probe(1, 3, 4). This probe keep on going forward by changing the corresponding values and at last arrives back to P1 as probe(1, 9, 1) from P9. Therefore P1 declares deadlock as the probe has reached to the same node which initiated the algorithm.This is a very general approach of diffusion computation and is known as Chandy-Misra-Haas Algorithm.