Daemon- Based Distributed Deadlock Detection and Resolution

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.




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