Data Structure Driven Probabilistic Deadlock Resolution in Multiprocessor Systems

Year : 2026 | Volume : 04 | Issue : 01 | Page : 11 20
    By

    Kakinada Mahitha Sri Ishwarya,

  • Chegondi Revathi,

  • Manas Kumar Yogi,

  1. Student, Department of Computer Science and Engineering, Pragati Engineering College (A), Surampalem, Andhra Pradesh, India
  2. Student, Department of Computer Science and Engineering, Pragati Engineering College (A), Surampalem, Andhra Pradesh, India
  3. Assistant Professor, Department of Computer Science and Engineering, Pragati Engineering College (A), Surampalem, Andhra Pradesh, India

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: Resource allocation graph, wait-for graph, Bayesian inference, deadlock resolution, multiprocessor systems, priority queue, process scheduling

[This article belongs to International Journal of Data Structure Studies ]

How to cite this article:
Kakinada Mahitha Sri Ishwarya, Chegondi Revathi, Manas Kumar Yogi. Data Structure Driven Probabilistic Deadlock Resolution in Multiprocessor Systems. International Journal of Data Structure Studies. 2026; 04(01):11-20.
How to cite this URL:
Kakinada Mahitha Sri Ishwarya, Chegondi Revathi, Manas Kumar Yogi. Data Structure Driven Probabilistic Deadlock Resolution in Multiprocessor Systems. International Journal of Data Structure Studies. 2026; 04(01):11-20. Available from: https://journals.stmjournals.com/ijdss/article=2026/view=241169


References

  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 Trans Very Large Scale Integr VLSI Syst. 2025;33: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 Robot Autom Lett. 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. In: Tari Z, Li K, Wu H, editors. Algorithms and Architectures for Parallel Processing: 23rd International Conference, ICA3PP 2023, Tianjin, China. 2024. p. 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. In: Vo NS, Tran HA, editors. Industrial Networks and Intelligent Systems. INISCOM 2023. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering. 531. Cham: Springer Nature Switzerland; 2023. p. 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 Trans Probab Mach Learn. 2024;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. In: Huang DS, Chen W, Pan Y, Chen H, editors. Advanced Intelligent Computing Technology and Applications. ICIC 2025. Lecture Notes in Computer Science. Vol. 15851. Singapore: Springer; 2025. p. 1–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 Trans Veh Technol. 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: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. In: Mohanty SN, Garcia Diaz V, Satish Kumar GAE, editors. Intelligent Systems and Machine Learning: First EAI International Conference, ICISML 2022, Hyderabad, India. Switzerland: Springer Nature. 2023. p. 325–334. doi:10.1007/978-3-031-35081-8_27.
  12. Mandal SK, Ogras UY, Doppa JR, Ayoub RZ, Kishinevsky M, Pande PP. Online adaptive learning for runtime resource management of heterogeneous SoCs. 57th ACM/IEEE Design Automation Conference (DAC), San Francisco, California, USA. 2020. p. 1–6. doi:10.1109/DAC18072.2020.9218604.
  13. Lee JJ, Mooney VJ III. Hardware/software partitioning of operating systems: focus on deadlock detection and avoidance. IEE Proc Comput Digit Tech. 2005;152(2):167–182. 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 Trans Comput. 2009;58:1485–1499. doi:10.1109/TC.2009.44.
  15. Helmy T. An improved deadlock detection and resolution algorithm for distributed computing systems. Preprints. 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. Int J Simul Model. 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 Trans Autom Sci Eng. 2025;22:9275–9284. doi:10.1109/TASE.2024.3504714.
  19. Rogalska M, Hejducki Z, Kostrzewa-Demczuk P. Causal reasoning in construction process scheduling. Appl Sci. 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. Int J Parallel Emergent Distrib Syst. 2016;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), Austin, TX, USA. 2017. p. 397–408. doi:10.1109/HPCA.2017.12.
Regular Issue Subscription Review Article
Volume 04
Issue 01
Received 29/03/2026
Accepted 04/04/2026
Published 28/04/2026
Publication Time 30 Days
104

Login


My IP

PlumX Metrics