Efficient Method for Deadlock Detection and Avoidance Using Two Way Search

Abstract

Dynamically changing graphs are used in many applicationsof graph algorithms. The scope of these graphs are in graphics, communication networks and in VLSI designs where graphs are subjected to change, such as addition and deletion of edges and vertices. There is a rich body of the algorithms and data structures used for dynamic graphs. The thesis discussed the techniques and data structures used in various dynamic algorithms. The effort is tried to find out the comparison in these techniques namely the hierarchical decomposition of graphs and highlighting the ingenuity used in designing these algorithms. The thesis provides the comparative analysis of dynamic graph techniques over the various graph properties like planarity , spanning forest, edge connectivity and bipartion.It analyze that which techniques worksbetter for which properties and minimizes the time and space usage.The thesis propose the algorithm for one of the online dynamic graph application,i.e deadlock detection. A deadlock detection and avoidance technique is based on various techniques of representing the directed acylic graph. The various graph model is developed based on the resource allocation graph and detecting the cycle in the graph using wait for conditions. These techniques are much discussed in past and has the algorithm for detecting the cycle for centralized system or distributed system for multiprocessing environment. This newer approach described in this thesis defines the online algorithm approach to detect the deadlock when the new edge is created and maintain the topological order of the graph using the two way search method for cycle detection.