ДІАГНОСТУВАННЯ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ ІЗ ЗАГАЛЬНОЮ ПАМ'ЯТТЮ ЗА ДОПОМОГОЮ МЕРЕЖ ПЕТРІ
DOI:
https://doi.org/10.31471/1993-9981-2023-1(50)-20-30Ключові слова:
паралельне програмування, мережі Петрі, примітиви синхронізації, відсутність тупиків, математичне програмування.Анотація
З розробкою швидкодіючих ЕОМ застосовність і корисність моделювання значно зросли. Подання системи математичною моделлю, перетворення цієї моделі в команди для ЕОМ і виконання програми уможливили моделювання більших і складніших систем, ніж раніше. Це призвело, в результаті, до значних досліджень методів моделювання на ЕОМ та самих ЕОМ, оскільки вони беруть участь у моделюванні у двох ролях: як обчислювальні засоби та як об'єкт моделювання. Одним із найпоширеніших сучасних методів формалізації моделювання та аналізу обчислювальних систем є мережі Петрі. Сьогодні існує велика кількість як теоретичних досліджень у цій галузі, так і реалізацій практичних інструментаріїв для розробки розподілених алгоритмів, заснованих на мережах Петрі. Розробляється міжнародний стандарт мереж Петрі. Разом із тим, відчувається необхідність розвитку формалізму для більш адекватного та зручного представлення систем зі складною структурою. Сучасні системи часто є мультиагентними і мають ієрархічну, багаторівневу структуру. У зв'язку з цим останнім часом проводяться дослідження щодо розширення формалізму мереж Петрі за рахунок ідей об'єктно-орієнтованого підходу з метою отримання моделей, що явно відображають ієрархічну та мультиагентну структуру системи. Класичне послідовне програмування не може забезпечити створення програм, які ефективно використовують ресурси сучасних обчислювальних систем. Багатопотокові програми, що працюють з даними у спільній пам'яті, часто недостатньо ефективні, оскільки надмірно використовують примітиви синхронізації. При недостатньому використанні примітивів є ризик отримати програму, яка має проблеми із синхронізацією. Засоби динамічного аналізу паралельних програм не завжди можуть вирішити ці проблеми. Для низки програм потрібен статичний аналіз паралельних алгоритмів. Найбільш складною проблемою є діагностування можливості тупиків. У даній роботі розглядаються аспекти, пов'язані із застосуванням мереж Петрі для виявлення проблем синхронізації у програмах з спільною пам'яттю. Наводяться схеми перетворення основних примітивів синхронізації у модель мережі Петрі, і зведення розв'язання задач про відсутність тупиків у мережі Петрі до задачі математичного програмування.
Завантаження
Посилання
Peterson J. Petri net theory and the modeling of systems, Prentice Hall; 1St Edition, 1981, 290 p.
Murata T. Petri Nets: Properties, Analysis and Applications. Proceedings of the IEEE. 1989. Vol. 77, No 4. P. 109-118.
Vallejo F., Gregorio J, Gonzalez Harbour M., Drake J. Shared Memory Multiprocessor operating System with Extended Petri Net Model IEEE transactions on parallel and distributing systems. 1994. Vol. 5, No 7. P. 88-94.
Feng Chu, Xiao-lan Xie D. Analysis of Petri Nets За допомогою Siphons і Mathematical Programming. IEEE Transactions of Robotics and Automation. 1997. Vol. 13, No. 6, P. 105-112.
Govindarajan F., Suciu W. Timed Petri NetModels з Multithreaded Multiprocessor Architectures, IEEE Preceedings if the 7-th International Workshop на Petri Nets and Performance Models. 1998 Vol. 12, No. 6, P. 125-130.
Takaoka T. A Systematic Approach Parallel Verification, Department of Computer Science of University of Ibaraki. 1995. Vol. 10, No. 6, P. 125-130.
Pommereua F. Petri Nets Executable Specifications of High-Level Timed Parallel Systems. Science of University of Ibaraki. 2005. Vol. 7, No. 5, P. 25-30.
Bruce P. Detection of Control Flow Errors in parallel Programs at Compile Time. International Journal of Distributed and parallel Systems (IJDPS). 2010. Vol. 1, N 2, 115-123.
Padidar S. Parallel Program verification: A Brief Introduction. International Journal of Parallel Programming 2010.Vol. 30, No 5. P. 1-23,
Kavi K, Moshtaghi A., Deng-Jyi C. Modeling Multithreaded application using Petri nets. International Journal of Parallel Programming. 2002. Vol. 30, No 5. P. 1-23,
Kavi K, Bukhles P., Bhat U. Isomorphism Between Petri net and Dataflow Graphs. IEEE Transactions on Software Engineering. 1987. Vol. 13, № 10. P. 36-42.
Stetsenko V., Dorosh V.., Dyfuchyn Anton Petri-object simulation: sofyware package and complexity. Intelligent Data Acquisition and Advanced Computing Sysytems: Technology and Applications (IDAACS), 2015 IEEE 8th International Conference. IEEE, 2015. Vol.1. N 10. P. 56-44.
Minoux M. Programmation Mathematique: Theorie and Algorithms. - Dunod, Paris, France, 1983. 313 p.
Dietsch D., Heizmann M., Klumpp D., Naouar M., Podelski A.. Verification, Model Checking, and Abstract Interpretation: 22nd International Conference, VMCAI 2021, Copenhagen, Denmark, January 17–19, 2021. P. 112-120.