STM Journals Peer-reviewed research from Consortium e-Learning Network

International Journal of Data Structure Studies Review Article

Data Structure Driven Probabilistic Deadlock Resolution in Multiprocessor Systems

  1. Kakinada Mahitha Sri Ishwarya Department of Computer Science and Engineering, Pragati Engineering College (A), Surampalem
  2. Chegondi Revathi Department of Computer Science and Engineering, Pragati Engineering College (A), Surampalem
  3. Manas Kumar Yogi Department of Computer Science and Engineering, Pragati Engineering College (A), Surampalem

Abstract

Deadlock resolution in multiprocessor systems is fundamentally a graph-theoretic and probabilistic decision problem. Existing victim selection heuristics, such as youngest, oldest, and lowest priority, apply static rules that overlook the dynamic runtime state of processes, leading to unnecessary computational loss. This paper reframes the inference-guided preemption (IGP) algorithm as a data-structure-centric solution, highlighting how resource allocation graphs, wait-for graphs, adjacency lists, min-heaps, and hash-based evidence stores interact to enable efficient deadlock detection and cost-minimized victim selection via Bayesian inference. A probabilistic cost model over three latent factors, such as remaining execution time, resource holding cost, and process criticality, drives a min-heap selection mechanism that selects the optimal victim in O(n log n). Simulation experiments using SimPy demonstrate a 34% reduction in resolution overhead relative to the best baseline heuristic, with comparable fairness and significantly faster workload shift adaptation, validating the structural and probabilistic design choices.

Keywords

References (22)

  1. Zhang J, Chen Z, Ye Y, Chen H, Han X, Jiang J, et al. IPDR: An Inter-Chiplet Priority-Driven Deadlock Resolution for 2-D/2.5-D Multichiplet Systems. IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2025;33(9):2424-2437. doi:10.1109/tvlsi.2025.3583289
  2. Müller M. Multi-agent reinforcement learning for deadlock handling among autonomous mobile robots [Preprint]. 2025. arXiv:2511.07071. doi:10.48550/arXiv.2511.07071
  3. Chen Y, Wang C, Guo M, Li Z. Multi-Robot Trajectory Planning With Feasibility Guarantee and Deadlock Resolution: An Obstacle-Dense Environment. IEEE Robotics and Automation Letters. 2023;8(4):2197-2204. doi:10.1109/lra.2023.3248377
  4. Yang Y, Li T, Dai Y, Wang B, Ma S, Sun Y. Absorb: Deadlock Resolution for 2.5D Modular Chiplet Based Systems. Lecture Notes in Computer Science. 2024:474-487. doi:10.1007/978-981-97-0834-5_27
  5. (2017). Resource allocation graph (RAG) [Online]. GeeksforGeeks. Available from: https://www.geeksforgeeks.org/operating-systems/resource-allocation-graph-rag-inoperat ing-system/.
  6. Le Ngoc H, Cong HT. Enhancing Load Balancing in Cloud Computing Through Deadlock Prediction. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering. 2023:257-274. doi:10.1007/978-3-031-47359-3_19
  7. Wijnings PWA, Roa-Villescas M, Stuijk S, de Vries B, Corporaal H. On the Importance of the Execution Schedule for Bayesian Inference. ACM Transactions on Probabilistic Machine Learning. 2024;1(1):1-28. doi:10.1145/3690830
  8. Tang S, Wu T, Tian Y, Wang H, Wu Y, Jiang R, et al. A Bayesian Inference-Enhanced Evolutionary Algorithm for Sleep Scheduling of Software-Defined Radio Sensors. Lecture Notes in Computer Science. 2025:3-14. doi:10.1007/978-981-96-9849-3_1
  9. Peng B, Xie Y, Seco-Granados G, Wymeersch H, Jorswieck EA. Communication Scheduling by Deep Reinforcement Learning for Remote Traffic State Estimation With Bayesian Inference. IEEE Transactions on Vehicular Technology. 2022;71(4):4287-4300. doi:10.1109/tvt.2022.3145105
  10. Kim DY, Kim RG, Kwak HS. A Closed-Loop Scheduling Framework for Prefabricated Bridge Girders: Bayesian Regression and TCTO-Based Optimization. Buildings. 2025;15(22):4168. doi:10.3390/buildings15224168
  11. Nguyen Trong T, Cuong NHV, Pham TV, Cuong NHH, Khiet BT. An Approach to New Technical Solutions in Resource Allocation Based on Artificial Intelligence. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering. 2023:325-334. doi:10.1007/978-3-031-35081-8_27
  12. Mandal SK, Ogras UY, Rao Doppa J, Ayoub RZ, Kishinevsky M, Pande PP. Online Adaptive Learning for Runtime Resource Management of Heterogeneous SoCs. 2020 57th ACM/IEEE Design Automation Conference (DAC). 2020:1-6. doi:10.1109/dac18072.2020.9218604
  13. Lee JJ, Mooney VJ. Hardware/software partitioning of operating systems: focus on deadlock detection and avoidance. IEE Proceedings - Computers and Digital Techniques. 2005;152(2):167. doi:10.1049/ip-cdt:20045078
  14. Shankaran N, Kinnebrew JS, Koutsoukas XD, Lu C, Schmidt DC, Biswas G. An Integrated Planning and Adaptive Resource Management Architecture for Distributed Real-Time Embedded Systems. IEEE Transactions on Computers. 2009;58(11):1485-1499. doi:10.1109/tc.2009.44
  15. Helmy T. An Improved Deadlock Detection and Resolution Algorithm for Distributed Computing Systems. 2024. doi:10.20944/preprints202403.1310.v1
  16. Shanu S, Sastry HG, Marriboyina V. Optimal solution approach on large scale data to avoid deadlocks in resource allocations. Mater Today Proc. 2021;47:7162–7166. doi:10.1016/j. 2021.06.357.
  17. Luo XG, Zhou L, Wang R. Manufacturing Process Based on Recognition Rules and Bayesian Networks. International Journal of Simulation Modelling. 2025;24(1):135-146. doi:10.2507/ijsimm24-1-co2
  18. Feng Y, Ren S, Cao Y, Xing K, Yang Y. Deadlock Control for Flexible Assembly Systems With Multiple Resource Requirements and Separately-Loaded Parts. IEEE Transactions on Automation Science and Engineering. 2025;22:9275-9284. doi:10.1109/tase.2024.3504714
  19. Rogalska M, Hejducki Z, Kostrzewa-Demczuk P. Causal Reasoning in Construction Process Scheduling. Applied Sciences. 2025;16(1):207. doi:10.3390/app16010207
  20. Venkatesh S, Smith JS. A graph-theoretic, linear-time scheme to detect and resolve deadlocks in flexible manufacturing cells. J Manuf Syst. 2003;22(3):220–238. doi:10.1016/S0278-6125(03) 90022-7.
  21. Gabriel PHR, Albertini MK, Castelo A, de Mello RF. Min-heap-based scheduling algorithm: an approximation algorithm for homogeneous and heterogeneous distributed systems. International Journal of Parallel, Emergent and Distributed Systems. 2015;31(1):64-84. doi:10.1080/17445760.2015.1009067
  22. Naithani A, Eyerman S, Eeckhout L. Reliability-Aware Scheduling on Heterogeneous Multicore Processors. 2017 IEEE International Symposium on High Performance Computer Architecture (HPCA). 2017:397-408. doi:10.1109/hpca.2017.12