DIAGNOSING COMPUTER SYSTEMS WITH SHARED MEMORY USING PETRI NETS
Keywords:паралельне програмування, мережі Петрі, примітиви синхронізації, відсутність тупиків, математичне програмування.
With the development of high-speed computers, the use and usefulness of simulations has increased significantly. Representing a system as a mathematical model, converting this model into commands for a computer, and executing a program on a computer made it possible to simulate larger and more complex systems than before. This has resulted in considerable research into computer simulation methods and computers themselves, as they participate in simulation in two roles: as computational tools and as the object of simulation. Petri nets are one of the most common modern methods of formalization of modeling and analysis of computer systems. Currently, there is a large amount of both theoretical research in this field and the implementation of practical tools for the development of distributed algorithms based on Petri nets. An international standard for Petri nets is being developed. At the same time, there is a need to develop formalism in order to more adequately and conveniently present systems with a complex structure. Modern systems are often multi-agent and have a hierarchical, multi-level structure. In this regard, research has recently been conducted on extending the formalism of Petri nets due to the ideas of an object-oriented approach in order to obtain models that clearly reflect the hierarchical and multi-agent structure of the system. Classical sequential programming no longer leads to the creation of programs that efficiently use the resources of modern computer systems. Multi-threaded programs working with data in shared memory are often inefficient because they overuse synchronization primitives. If you don't use synchronization primitives enough, you run the risk of getting a program that has some kind of synchronization problem. Means of dynamic analysis of parallel programs cannot always solve these problems. A number of applications require static analysis of parallel algorithms. The most difficult problem is diagnosing the possibility of dead ends. This paper considers the aspects related to the use of Petri nets to detect synchronization problems in parallel programs that use shared memory. Schemes for converting the main primitives of synchronization into a Petri net model are presented, the mechanism of siphons for determining the activity of the Petri net is considered, and even the reduction of solving the problem of the absence of dead ends in the Petri net to the problem of mathematical programming.
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.