Dynamic budget-threshold based resource reservation technique
Keywords:
Deadlock, Deadlock handling, Deadlock Prevention, Deadlock Avoidance, Resource allocation, Banker‟s Algorithm, Resource managementAbstract
The effective utilization of the resources is recognized as essential tool not only for the cost effectiveness of the system but also for the environment. Sharing of the resources improves its utilization but also creates contention among the processes using it. This contention may lead to frequent deadlocks. Many deadlock avoidance techniques exist for avoiding the deadlock while sharing the resources. However, all these technique suffer from two major limitations: 1) they assume that the resource requirement for each process is known in advance; 2) overhead for decision making for resource granting to ensure that any future deadlock must be avoided. This paper proposes a Dynamic Budget for Threshold based Resource Reservation Technique for Deadlock Avoidance (DB-TRA) which extends the existing Threshold based Resource Reservation Technique for Deadlock Avoidance (TRA) [24] technique. The existing TRA address the second limitation of excessive overhead for resource granting by forward calculation to avoid deadlock. However, this TRA technique also suffers from the first limitation and assumes that the resource requirement of each process is known in advance. The proposed DB-TRA technique address this limitation of the deadlock avoidance techniques by proposing a dynamic budget which eliminates the need of prior knowledge of the resource requirement of any process, the budget is adjusted dynamically to cater the need of the process. The proposed technique uses the resource reservation as suggested in TRA for minimizing the overhead in granting of the requested resources. The simulation result shows that the proposed DB-TRA technique performs better than existing deadlock avoidance technique.
References
. Havender, J.W., Avoiding Deadlock in Multitasking Systems, Ibm Systems Journal, 7(2):74–84(1968).
. Dijkstra, E.W., Cooperating Sequential Processes, in Programming Languages, Genuys F. Editor, London, Academic Press, 1965.
. Coffman, E.G., Elphick, M.J, Shoshani, A., Systems Deadlocks, Acm Computer Surveys, 3(2):67-78(1971).
. Dijkstra, E.W., The Structure Of The Multiprogramming System, Communication Of The Acm, 26(1):341-346 (1968).
. Habermann, A.N., Prevention of System Deadlocks, Communications of the ACM, 12(7):373– 377(1969).
. Holt, R.C., Some Deadlock Properties of Computer Systems, ACM Computing Surveys, 4(3):179-196 (1972).
. Nutt, G.J., Some Application of Finite State Automata Theory to the Deadlock Problem, Technical Report CU-CS-017-73, Department of Computer Scince, University of Colorado at Boulder, Colorado, 1973.
. Devillers, R., Game Interpretation of the Deadlock Avoidance Problem, Communication of the ACM, 20(10):741-745(1979).
. Fontao, R.O., A Concurrent Algorithm for Avoiding Deadlocks, Proceedings of the Third ACM Symposium on Operating Systems Principles, 72–79 (1971).
. Frailey, D.J., A Practical Approach to Managing Resources and Avoiding Deadlock, Communications of the ACM, 16(5):323–329(1973).
. Ghaffari, A., Rezg, N., XIe, X.L., Design of a live and maximally permissive Petri net controller using the theory of regions. IEEE Transactions on Robotics and Automation,19(1):137-142 (2003).
. Huang, Y.S., Jeng, M.D., Xie, X.L., Chung, S.L., Deadlock prevention policy based on Petri nets and siphons. International Journal of Production Research, vol.39 (2):283- 305 (2001).
. Huang, Y.S, Jeng, M.D., Xie, X.L, Chung, D.H, Siphon-based deadlock prevention policy for flexible manufacturing systems, IEEE Trans. System, Man, Cybern. A, System, Humans,36(6):1248-1256 (2006).
. Li, Z.W, Zhou, M.C., Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems, IEEE Trans. on System, Man, and Cybern., part A, 34:38-51(2004).
. Park, J., Reveliotis, S.A., Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings. IEEE Transactions on Automatic Control,46(10):1572-1583 (2001).
. Tricas, F., Garcia Valles, F., Colom, J.M., Ezpeleta, J.,An iterative method for deadlock prevention in FMSs, 5th Workshop Discrete Event System, R. Boel and G. Stremersch, Eds., Ghent, Belgium,139-148(2000).
. Tricas, F., Garcia-Valles, F., Colom, J.M., Ezpeleta, J.,A Petri net structure-based deadlock prevention solution for sequential resource allocation systems, IEEE International Conference Robot. Autom., Barcelona, Spain, 271-277 (2005).
. Uzam, M., An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions. International Journal of Advanced Manufacturing Technology, 19(3):192-208(2002).
. Uzam, M., Zhou, M.C., Iterative synthesis of Petri net based deadlock prevention policy for flexible manufacturing systems. In Proc. IEEE International Conference on Systems, Man, and Cybernetics, 4260-4265(2004).
. Xie, X.L., Jeng, M.D., 1999. ERCN-merged nets and their analysis using siphons, IEEE Trans. Robot. Autom., 15(4):692-703(1999).
. David B. Stewart, “Measuring Execution Time and Real-Time Performance” in Embedded Systems Conference, Boston, September 2006.
. Kees van Hee, Alexander Serebrenik, Natalia Sidorova Marc Voorhoeve, Jan van der Wal.,”Scheduling-free resource management” in Science Direct, Data & Knowledge Engineering 61 (2007) 59–75
. Smriti Agrawal, B Madhavi Devi, Ch. Srinivasulu, "A Total Need Based Resource Reservation Technique For Effective Resource Management”, in Int'I Journal of Computer Applications, Volume 67, April 2013.
. B Madhavi Devi, Smriti Agrawal, Ch. Srinivasulu, "An Efficient Resource Allocation Technique for UniProcessor System", in Int' Journal of Advances in Engg & Tech (IJAET) Vol. 6 II, March 2013.
. B Madhavi Devi, Smriti Agrawal, Rajeshwar Rao, “EFFECTIVE RESOURCE MANAGEMENT TECHNIQUES USING RESERVATION POOL” in
IEEE International Conference on Recent Advances & Innovations in Engineering" (ICRAIE-2014), May 09-11, 2014. IEEE Conference Record # 33681.
. Shubham Kumar and Saravanan Chandran, “Modified Execution Time based Resource Reservation (METRR) Algorithm”, presented at ICBIM 2016, 9-11, January 2016, ISBN: 978-1-5090-1228-2, NIT Durgapur, INDIA.
. Xiang Xiao, Jaehwan John Lee.: A parallel multi-unit resource deadlock detection algorithm with O(log2(min(m, n))) overall run-time complexity. J. Parallel Distrib. Comput. 71. pp. 938–954. (2011)
. Youming L, “ A Modified Banker‟s Algorithm”, in Springer Innovations and Advances in Computer, Information, Systems Sciences, and Engineering pp 277-2819(2012)
. Hongwei Wang ; Jinfeng Tian; Mingqi Li ; Weixin Mu; Xiangchuan Gao,” Banker's algorithm based resource allocation in next generation broadcasting wireless systems(2015) . IEEE Proc Int‟l Conf Communications and Networking in China
. H. K. Pyla and S. Varadarajan. Avoiding deadlock avoidance. PACT ‟10, pages 75–86, New York, NY, USA, 2010. ACM
. Operating systems: design and implementation, Andrew s. tanenbaum, prentice hall, 2006.
. Aida.O.Abd EI-Gwad, Ahmed.I.Saleh, Mai.M.AbdEIRazik. "A Novel Scheduling Strategy for an Efficient Deadlock Detection" IEEE. 2009
. Kshipra Dixit, Ajay Khuteta, “A Dynamic and Improved Implementation of Banker‟s Algorithm” in International Journal on Recent and Innovation Trends in Computing and Communication,2017, ISSN: 2321-8169 Volume: 5 Issue: 8 pg 45 – 49 [34]. Pankaj Kawadkar, Shiv Prasad, Amiya Dhar Dwivedi, “Deadlock Avoidance based on Banker‟s Algorithm for Waiting State Processes” in International Journal of Innovative Science and Modern Engineering (IJISME) ISSN: 2319-6386, Volume-2 Issue-12, November 2014
. Aida. O. Abd El-Gwad, Ahmed. I. Saleh, Mai. M. Abd-ElRazik. “A Novel Scheduling Strategy for an Efficient Deadlock Detection” IEEE. 2009
. Zhang, C., Liu, Y., Zhang, T., Zha, Y., Huang, K., “A Deadlock Prevention Approach based on Atomic Transaction for Resource Co-allocation”, First International Conference on Semantics, Knowledge and Grid (SKG'05), 37-39(2005).
. Kim, J. Koh,“An O(1) Time Deadlock Detection Scheme in Single Unit and Single Request Multiprocess System”, Proc. IEEE Region 10 Conf. (TENCON ‟91), pp. 219-223. (1991)
. Cahit, “Deadlock Detection Using (0, 1)-Labelling of Resource Allocation Graphs”, IEEE Proc. Computers and Digital Techniques, pp. 68-72. (1998)
. Shiu, P. Y. Tan, Mooney, “A Novel Parallel Deadlock Detection Algorithm and Architecture”, Proc.Int‟l Conf. Hardware Software Codesign (CODES ‟01), pp. 73-78. (2001)
. Huang, Y.S., Lin, J.H., Hsu, C.N., “Comparison of deadlock prevention policies in FMS based on Petri nets siphons”, In Proc. IEEE International Conference on Systems, Man, and Cybernetics, 4867-4872(2004).
. Kim, J., “Algorithmic Approach on Deadlock Detection for Enhanced Parallelism in Multiprocessing Systems”. Proc. Second AIZU Int‟l
Symp. Parallel Algorithms/Architecture Synthesis (PAS ‟97),pp. 233-238. (1997)
. Yin,W., Stephane, L., Terence, K., Manjunath, K., Scott, M., “The Theory of Deadlock Avoidance via Discrete Control”, 36th annual ACM SIGPLANSIGACT symposium on Principles of programming languages, PoPL,202- 214(2009).
. Zhishuo Zheng , Deyu Qi, Mincong Yu, XinyangWang ,Naqin Zhou, Yang Shen, and Jing Guo, “Optimizing Job Coscheduling by Adaptive
. Deadlock-Free Scheduler, Hindawi Mathematical Problems in Engineering, Volume 2018, Article ID 1438792, 18 pages.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2019 COMPUSOFT: An International Journal of Advanced Computer Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
©2023. COMPUSOFT: AN INTERNATIONAL OF ADVANCED COMPUTER TECHNOLOGY by COMPUSOFT PUBLICATION is licensed under a Creative Commons Attribution 4.0 International License. Based on a work at COMPUSOFT: AN INTERNATIONAL OF ADVANCED COMPUTER TECHNOLOGY. Permissions beyond the scope of this license may be available at Creative Commons Attribution 4.0 International Public License.
