Аналіз методів та моделей вирішення задачі взаємоблокування процесів у комп’ютерних системах

АНАЛІЗ МЕТОДІВ ТА МОДЕЛЕЙ ВИРІШЕННЯ ЗАДАЧІ ВЗАЄМОБЛОКУВАННЯ ПРОЦЕСІВ У КОМП’ЮТЕРНИХ СИСТЕМАХ

ANALYSIS OF METHODS AND MODELS FOR SOLVING THE PROCESS DEADLOCK PROBLEM IN COMPUTER SYSTEMS

Сторінки: 27-31. Номер: №5, 2021 (301)
 Автор:
МОСТОВИЙ С.В.
Хмельницький національний університет
ORCID ID: 0000-0002-9505-3206
e-mail: serhii.mostovyi@khmnu.edu.ua
MOSTOVYI SERHII V.
Khmelnytskyi National University
DOI: https://www.doi.org/10.31891/2307-5732-2021-301-5-27-31
Рецензія/Peer review : 06.09.2021р.
Надрукована/Printed : 10.10.2021 р.
Анотація мовою оригіналу
У статті проведено аналіз причин, умов та механізмів виникнення взаємоблокувань процесів у сучасних багатозадачних комп’ютерних системах. Розглянуто класифікацію системних ресурсів за фізичною природою, можливістю спільного використання, можливістю примусового вилучення та кількістю екземплярів. Проаналізовано сучасні графові та стохастичні моделі ресурсної взаємодії, зокрема класичні графи розподілу ресурсів, графи очікування та марковські моделі станів комп’ютерної системи. Детально досліджено чотири основні групи методів боротьби із взаємоблокуваннями: ігнорування (алгоритм страуса), запобігання (шляхом порушення умов Коффмана), уникнення (включаючи алгоритм банкіра) та виявлення з подальшим усуненням критичних станів. Обґрунтовано науково-технічне протиріччя між реактивним характером більшості традиційних підходів та необхідністю проактивного оцінювання ризиків. Доведено доцільність переходу до методів завчасного прогнозування стану взаємоблокування на основі сигнатур процесів, нечіткої кластеризації Fuzzy C-Means та нечіткого логічного висновку.
Ключові слова: комп’ютерні системи, взаємоблокування процесів, системні ресурси, графи розподілу ресурсів, граф очікування, марковські моделі, умови Коффмана, алгоритм банкіра, прогнозування ризику.

 Розширена анотація англійською мовою

The article analyzes the causes, conditions, and mechanisms of process deadlocks in modern multitasking computer systems. The classification of system resources is examined based on their physical nature, shareability, preemptibility, and the number of instances. Modern graph-based and stochastic models of resource interaction are analyzed, specifically classical resource allocation graphs, wait-for graphs, and Markov models of computer system states. Four main groups of deadlock handling methods are investigated in detail: ignoring (the ostrich algorithm), prevention (by violating Coffman conditions), avoidance (including the banker’s algorithm), and detection followed by the elimination of critical states. A scientific and technical contradiction between the reactive nature of most traditional approaches and the need for proactive risk assessment is substantiated. The feasibility of transitioning to methods for the early prediction of deadlock states based on process signatures, Fuzzy C-Means clustering, and fuzzy logic inference is demonstrated.
Keywords: computer systems, process deadlock, system resources, resource allocation graphs, wait-for graph, Markov models, Coffman conditions, banker’s algorithm, risk prediction.

References

1. Dychka, I. A. Orhanizatsiia obchysliuvalnykh protsesiv u paralelnykh ta rozpodilenykh komp’iuternykh systemakh. Komp’iuterna Inzheneriia. – 2018. – № 2. – P. 45–52.
2. Mukhin, V. Ye., & Volokita, A. M. Metody ta zasoby adaptyvnoho upravlinnia resursamy v rozpodilenykh komp’iuternykh merezhakh. Naukova Dumka, 2020. – 240 p.
3. Melnyk, A. O. Arkhitektura komp’iuternykh system ta yikhnikh komponentiv: pidruchnyk. Lviv Polytechnic Publishing House, 2019. – 412 p.
4. Coffman E. G. System Deadlocks / E. G. Coffman, M. J. Elphick, A. Shoshani // ACM Computing Surveys. – 1971. – Vol. 3, No. 2. – P. 67–78.
5. Dijkstra E. W. Co-operating sequential processes / E. W. Dijkstra // Programming Languages / Academic Press. – 1968. – P. 43–112.
6. Holt R. C. Some Deadlock Properties of Computer Systems / R. C. Holt // ACM Computing Surveys. – 1972. – Vol. 4, No. 3. – P. 179–196.
7. Tanenbaum A. S. Modern Operating Systems: 4th Edition / A. S. Tanenbaum, H. Bos. – Boston: Pearson, 2015. – 1136 p.
8. Stallings W. Operating Systems: Internals and Design Principles: 9th Edition / W. Stallings. – New York: Pearson, 2018. – 864 p.
9. Chandy K. M. Distributed Deadlock Detection / K. M. Chandy, J. Misra, L. M. Haas // ACM Transactions on Computer Systems. – 1983. – Vol. 1, No. 2. – P. 144–156.
10. Mathur U. Dynamic Deadlock Detection for Concurrent Programs / U. Mathur, A. Pavlogiannis, M. Viswanathan // Proceedings of the ACM on Programming Languages. – 2020. – Vol. 4 (POPL). – P. 1–30.