We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Reseach Article

VGS Algorithm - An Efficient Deadlock Resolution Method

by Kunwar Singh Vaisla, Menka Goswami, Ajit Singh
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 44 - Number 1
Year of Publication: 2012
Authors: Kunwar Singh Vaisla, Menka Goswami, Ajit Singh
10.5120/6230-8310

Kunwar Singh Vaisla, Menka Goswami, Ajit Singh . VGS Algorithm - An Efficient Deadlock Resolution Method. International Journal of Computer Applications. 44, 1 ( April 2012), 29-33. DOI=10.5120/6230-8310

@article{ 10.5120/6230-8310,
author = { Kunwar Singh Vaisla, Menka Goswami, Ajit Singh },
title = { VGS Algorithm - An Efficient Deadlock Resolution Method },
journal = { International Journal of Computer Applications },
issue_date = { April 2012 },
volume = { 44 },
number = { 1 },
month = { April },
year = { 2012 },
issn = { 0975-8887 },
pages = { 29-33 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume44/number1/6230-8310/ },
doi = { 10.5120/6230-8310 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:34:27.478533+05:30
%A Kunwar Singh Vaisla
%A Menka Goswami
%A Ajit Singh
%T VGS Algorithm - An Efficient Deadlock Resolution Method
%J International Journal of Computer Applications
%@ 0975-8887
%V 44
%N 1
%P 29-33
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The occurrence of deadlocks should be controlled effectively by their detection and resolution, but may sometimes lead to a serious system failure. After implying an efficient detection algorithm the deadlock is resolved by a deadlock resolution algorithm whose primary step is to either select the victim then to abort the victim transaction or cause it to rollback. This step resolves deadlock but is not efficient one. This paper proposes a new deadlock resolution algorithm which doesn't cause any aborts /roll backs in fact it is based on the mutual cooperation of transactions and a random number representing time duration for which the process holding the resource will be suspended.

References
  1. Akikazu IZUMI, Tadashi DOHI and Naoto KAIO, Deadlock Detection Scheduling for Distributed Processes in the Presence of System Failures, 2010 Pacific Rim International Symposium on Dependable Computing, DOI 10. 1109/PRDC. 2010. 49, 2010 IEEE.
  2. G. Bracha and S. Toueg. A distributed algorithm for generalized deadlock detection. Distributed Computing, 2:127–138, 1987.
  3. A. D. Kshemkalyani and M. Singhal. Distributed detection of generalized deadlocks. Proc. 17th Int'l Conf. Distributed Computing Systems, pages 553–560, May 1997.
  4. A. Boukerche and C. Tropper. A distributed graph algorithm for the detection of local cycles and knots. IEEE Trans. Parallel and Distributed Systems, 9(8):748–757, Aug. 1998.
  5. Soojung Lee. Fast Detection and Resolution of Generalized Distributed Deadlocks, Proceedings of the 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing (EUROMICRO-PDP. 02) 1066-6192/02, IEEE computer society 2002.
  6. Omran Bukhres, Jeanne Alm and Noureddine Boudriga, A Priority-Based PCG Algorithm for Global Deadlock Detection and Resolution in Multidatabase Systems, IEEE 0-8186-3710-2/9, 1993.
  7. Yibei Ling, Shigang Chen, Cho-Yu Jason Chiang, On Optimal Deadlock Detection Scheduling, IEEE TRANSACTIONS ON COMPUTERS, VOL. 55, NO. 9, SEPTEMBER 2006.
  8. S. Lee, "Fast, Centralized Detection and Resolution of Distributed Deadlocks in the Generalized Model," IEEE Trans. Software Eng. , vol. 30, no. 8, pp. 561-573, Sept. 2004.
  9. S. Lee and J. L. Kim, "Performance Analysis of Distributed Deadlock Dectection Algorithms," IEEE Trans. Knowledge and Data Eng. , vol. 13, no. 3, pp. 623-636, May/June 2001.
  10. X. Lin and J. Chen, "An Optimal Deadlock Resolution Algorithm in Multidatabase Systems," Proc. 1996 Int'l Conf. Parallel and Distributed Systems, pp. 516-521, 1996.
  11. P. P. Macri, "Deadlock Detection and Resolution in a CODASYL Based Data Management System," Proc. 1976 ACM SIGMOD Int'l Conf. Management of Data, pp. 45-49, 1976.
  12. M. Singhal, "Deadlock Detection in Distributed Systems,"Computer, vol. 40, no. 8, pp. 37-48, Nov. 1989
  13. A. D. Kshemkalyani and M. Singhal, "Efficient Detection and Resolution of Generalized Distributed Deadlocks," IEEE Trans. Software Eng. , vol. 20, no. 1, pp. 43-54, Jan. 1994.
  14. Y. Ling, J. Mi, and X. Lin, "A Variational Calculus Approach to Optimal Checkpoint Placement," IEEE Trans. Computers, vol. 50,no. 7, pp. 699-708, July 2001
  15. K. Min. Performance Study of Distributed Deadlock Detection Algorithms for Distributed Database Systems. PhD thesis, Univ. of Illinois at Urbana-Champaign Nov. 1989.
  16. S. Warnakulasuriya and T. M. Pinkston. A formal model of message blocking and deadlock resolution in interconnection networks. IEEE Transactions on Parallel and Distributed Systems, 11(3):221–229, March 2000.
  17. J. Villadangos, F. Fari˜na, A. C´ordoba, J. R. Gonz´alez de Mend´?vil and J. R. Garitagoitia, Knot Resolution Algorithm and its Performance Evaluation, Proceedings of the Eleventh Euromicro Conference on Parallel,Distributed and Network-Based Processing (Euro-PDP'03) 0-7695-1875-3/03,IEEE computer society,2003.
  18. S. Chen, Y. Deng, and W. Sun, "Optimal Deadlock Detection in Distributed Systems Based on Locally Constructed Wait-For Graph," Proc. 16th Int'l Conf. Distributed Computing Systems, pp. 613-619, 1996.
  19. J. R. Gonzales de Mendivil, J. R. Garitagoitia, C. F. Alastruey, and J. M. Bernabeu-Auban, "A Distributed Deadlock Resolution Algorithm for the AND Model," IEEE Trans. Parallel and Distributed Systems, vol. 10, no. 5, pp. 433-447, May 1999.
  20. A. Cordoba, F. Fari˜na, J. R. Garitagoitia, J. R. Gonz´alez de Mend´?vil, J. Villadangos A Low Communication Cost Algorithm for Distributed Deadlock Detection and Resolution, Proceedings of the Eleventh Euromicro Conference on Parallel,Distributed and Network-Based Processing (Euro-PDP'03),IEEE computer society,0-7695-1875-3/03,2003.
  21. H. A. Ali, T. EL-DNAF, and MSALAH, A proposed algorithm for solving deadlock detection in distributed database systems 0-7803-8575-6/04, 2004, IEEE.
  22. Mehdi Hashemzadeh, Nacer Farajzadeh, Abolfazl T. Haghighat, Optimal Detection and Resolution of Distributed Deadlocks in the Generalized Model, Proceedings of the 14th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP'06),IEEE computer society, 1066-6192/06, 2006.
  23. Manuel Prieto, Jesús Villadangos, Federico Fariña, Alberto Córdoba, An O(n) distributed deadlock resolution algorithm, Proceedings of the 14th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP'06) IEEE computer society, 1066-6192/06, 2006 .
  24. Soojung Lee, Fast, Centralized Detection and Resolution of Distributed Deadlocks in the Generalized Model, published by IEEE computer society, 0098-5589/04, 2004.
Index Terms

Computer Science
Information Sciences

Keywords

Deadlock Wfg Transactions Resources