Daemon- Based Distributed Deadlock Detection and Resolution

Authors: Z. RahimAlipour, A. T. Haghighat

Abstract:

detecting the deadlock is one of the important problems in distributed systems and different solutions have been proposed for it. Among the many deadlock detection algorithms, Edge-chasing has been the most widely used. In Edge-chasing algorithm, a special message called probe is made and sent along dependency edges. When the initiator of a probe receives the probe back the existence of a deadlock is revealed. But these algorithms are not problem-free. One of the problems associated with them is that they cannot detect some deadlocks and they even identify false deadlocks. A key point not mentioned in the literature is that when the process is waiting to obtain the required resources and its execution has been blocked, how it can actually respond to probe messages in the system. Also the question of 'which process should be victimized in order to achieve a better performance when multiple cycles exist within one single process in the system' has received little attention. In this paper, one of the basic concepts of the operating system - daemon - will be used to solve the problems mentioned. The proposed Algorithm becomes engaged in sending probe messages to the mandatory daemons and collects enough information to effectively identify and resolve multi-cycle deadlocks in distributed systems.

Keywords: Distributed system, distributed deadlock detectionand resolution, daemon, false deadlock.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1076232

References:

[1] Abdur Razzaque. Md., Mamun-Or-Rashid. Md., Ch.Hong,"MC2DR:Multi-cycle Deadlock Detection and Recovery Algorithm for Distributed Systems", LNCS 4782(HPCC2007), Sep 26- 28 2007, pp. 554-565
[2] Chandy, KM, Misra, J,"A distributed algorithm for detecting resource deadlocks in distributed systems". In Proc. ACM SIGA CT-SIGOPS Syrup, 1982, pp. 157-164
[3] Chandy KM, Misra .J, Haas LM, "Distributed Deadlock Detection", ACM Transactions on Computer Systems, May 1983,Vol 1,No. 2.PP 144-156
[4] Choudhary et al," A Modified Priority Based Probe Algorithm for Distributed Deadlock Detection and Resolution", IEEE Trans Software, January 1989, vol.15, No.1, pp .10-17
[5] Farajzadeh. N, Hashemzadeh. M, Mousakhani.M , Haghighat, .A,"An Efficient Generalized Deadlock Detection and Resolution Algorithm in Distributed Systems",In: Proc.5th IEEE Int'l Conf. Computer and Information Technology (CIT'05),2005.
[6] Knapp, E, "Deadlock Detection in Distributed Databases". ACM Computing Surveys, Dec.1988, vol.3, no. 4, pp.303-328.
[7] Kshemkalyani AD, Singhal M ,"Distributed detection of generalized deadlocks". In: Proceedings of the 17th International Conference on Distributed Computing System, IEEE Computer Society Press, 1997, pp 553-560
[8] Kshemkalyani, A. D, Singhal, M, "Invariant based verification of a distributed deadlock detection algorithm," IEEE Trans. Software Eng, Aug. 1991, vol 17, pp. 789-799.
[9] Lee.S,"Fast, Centralized Detection and Resolution of Distributed Deadlocks in the Generalized Model", IEEE Transaction on Software Engineering, September 2004, Vol. 30 , No.9 ,pp. 561-573
[10] Lee, S., Kim, JL,"An Efficient Distributed Deadlock Detection Algorithm". In: Proc. 15th IEEE Int'l Conf. Distributed Computing Systems, pp. 169-178 (1995)
[11] DP Mitchell and MJ Merritt,"A Distributed Algorithm for Deadlock Detection and Resolution", Proc. Third ACM Symp. Principles of Distributed Computing, pp. 282-284, Vancouver, Canada, Aug. 1984.
[12] MK Sinha and N. Natarjan, "A priority-based distributed deadlock detection algorithm", IEEE Trans. Software Eng., Vol. SE-11, No. 1, Jan. 1985, 67-80.
[13] Singhal, M, "Deadlock Detection in Distributed Systems", IEEE Computer, Nov.1989, No 22, pp. 37-48.
[14] Tanenbaum ,A."Modern Operation Systems", 3 e, (c) Prentice-Hall, Inc. 2008