A novel deadlock detection algorithm for neighbour replication on grid environment - Noriyani, Mohd Zin (2012)
Deadlock occurs when each of the transaction involves is waiting to grant the data that has been locked by other transactions. This can lead to a circular wait called Wait-for Graph (WFG). Deadlock can make the transaction become an inactive, so other transaction is not able to perform any action and further cause unavailability of resources. Therefore, an action must be taken to detect and solve this problem. A new framework and algorithm called Neighbour Replication on Grid Deadlock Detection (NRGDD) has been developed to handle deadlock cycles that exist during the transaction in Neighbour Replication on Grid (NRG) environment. The aim of this research is to handle the deadlock problem in NRG to preserve the consistency of data and increase the throughput. The NRGDD simulation model has been developed to test the algorithm on NRG. Two experiments have been conducted to test the correctness of NRGDD algorithm. The first experiment is to detect two cycles of deadlock while the second experiment is to spot deadlock by using different number of transaction, from three to five transactions. The use of three to five transactions is in NRG the data will be replicated into three to five sites. Each site is locked by different set of transaction. Then, the transaction can send request to other site that is held by another transaction. So, circular wait is formed. Through this experiment, the NRGDD simulation model is able to detect multiple cycles of deadlock which exist on NRG. The NRGDD is compared with Multi-Cycle of Deadlock Detection and Recovery (MC2DR) algorithm based on the time required for both models to detect two deadlock cycles and using different numbers of transactions. The NRGDD achieved 27.5% improvement from MC2DR. From the experimental result, it is clearly shown that handling deadlock on NRG using NRGDD is able to preserve the data consistency and increase the throughput by maximizing the availability of resources.