Data Structure-Driven Probabilistic Deadlock Resolution in Multiprocessor Systems

Notice

This is an unedited manuscript accepted for publication and provided as an Article in Press for early access at the author’s request. The article will undergo copyediting, typesetting, and galley proof review before final publication. Please be aware that errors may be identified during production that could affect the content. All legal disclaimers of the journal apply.

Year : 2026 | Volume : 04 | 01 | Page :
    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—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-minimised victim selection via Bayesian inference. A probabilistic cost model over three latent factors—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

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):-.
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):-. Available from: https://journals.stmjournals.com/ijdss/article=2026/view=241169


References

  1. Zhang 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:1–12.
  2. Yang Y, et al. Absorb: deadlock resolution for 2.5D modular chiplet based systems. In: Proceedings of the International Conference on Algorithms and Architectures for Parallel Processing; 2023. Springer Nature Singapore.
  3. Chen Y, et al. Multi-robot trajectory planning with feasibility guarantee and deadlock resolution: an obstacle-dense environment. IEEE Robotics and Automation Letters. 2023;8(4):2197–204.
  4. Helmy T. An improved deadlock detection and resolution algorithm for distributed computing systems. Journal of Network and Computer Applications. 2024;215:1–14.
  5. Feng Y, et al. Deadlock control for flexible assembly systems with multiple resource requirements and separately-loaded parts. IEEE Transactions on Automation Science and Engineering. 2024;22:9275–84.
  6. Müller M. Multi-agent reinforcement learning for deadlock handling among autonomous mobile robots [Internet]. arXiv; 2025.
  7. Wijnings PWA, et al. On the importance of the execution schedule for Bayesian inference. ACM Transactions on Probabilistic Machine Learning. 2024;1(1):1–28.
  8. Tang S, et al. A Bayesian inference-enhanced evolutionary algorithm for sleep scheduling of software-defined radio sensors. In: Proceedings of the International Conference on Intelligent Computing; 2025. Springer Nature Singapore.
  9. Peng B, et al. Communication scheduling by deep reinforcement learning for remote traffic state estimation with Bayesian inference. IEEE Transactions on Vehicular Technology. 2022;71(4):4287–300.
  10. Luo XG, Zhou L, Wang R. Manufacturing process based on recognition rules and Bayesian networks. International Journal of Simulation Modelling. 2025;24(1):1–18.
  11. 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.
  12. Nguyen TT, et al. An approach to new technical solutions in resource allocation based on artificial intelligence. In: Proceedings of the International Conference on Intelligent Systems and Machine Learning; 2022. Springer Nature Switzerland.
  13. Khaga SY, George R. Topological quantification and resolution of concurrency deadlocks: an Alexander polynomial approach to resource allocation graphs. Journal of Parallel and Distributed Computing. 2025:1–19.
  14. Henriksson R. Resource allocation graphs: theory and implementation. Journal of Systems and Software. 2025:1–22.
  15. Rogalska M, Hejducki Z, Kostrzewa-Demczuk P. Causal reasoning in construction process scheduling. Applied Sciences. 2025;16(1):207.
  16. Gharib H, Naji HR. Adaptive deadlock avoidance using machine learning in cloud computing environments. Future Generation Computer Systems. 2023;138:1–14.
  17. Ramírez LA, García AL. Online learning strategies for dynamic resource allocation in multiprocessor operating systems. Journal of Systems Architecture. 2023;134:1–12.
  18. Silberschatz A, Galvin PB, Gagne G. Deadlock detection and recovery in modern operating systems. ACM Computing Surveys. 2023;56(2):1–38.
  19. Chen X, Zhang W. Probabilistic resource management for real-time embedded multiprocessor systems. IEEE Transactions on Computers. 2024;73(4):1022–36.
  20. Gupta P, Sharma S. Priority-aware deadlock resolution with graph-theoretic cost minimisation. IEEE Access. 2024;12:54321–35.
  21. Park JH, Jung SY. A min-heap approach to efficient victim selection in resource-constrained concurrent systems. Journal of Parallel and Distributed Computing. 2023;181:1–10.
  22. Verma R, Singh A. Bayesian workload characterisation for adaptive scheduling in heterogeneous multicore processors. Concurrency and Computation: Practice and Experience. 2024;36(3):e7812.
Ahead of Print Subscription Review Article
Volume 04
01
Received 29/03/2026
Accepted 04/04/2026
Published 28/04/2026
Publication Time 30 Days
34

Login


My IP

PlumX Metrics