On Solving Concurrent Process Problem in Process-Oriented Programs
https://doi.org/10.25205/1818-7900-2023-21-2-5-17
Abstract
Prevailing portion of the factories and manufacturers are controlled by programming microcontrollers in the modern world. And the portion keeps growing which is closely tied to processes of the Fourth Industrial Revolution. Precisely, with an idea of fully automated manufactures to help humans to make less decisions and make them faster. Or to exclude humans from the decision making process at all. Due to that, there is a need for the controlling algorithms which should react to the different events, be aware of the external world and be tolerant to both internal and hardware failures. There is a process-oriented paradigm which was developed in Institute of Automation and Electrometry SB RAS and suits perfectly for automatization of such algorithms. This is achieved by splitting the algorithm into huge amounts of the small parallel processes highly tied to the elements of the real world. Which is how real processes on real manufactures work. This is where the conflicts during concurrent programming appear. And because there is a fault tolerance requirement there is a need to solve those conflicts. This work presents the analysis of already existing solutions to the conflicts during concurrent programming with the goal of either reusing those solutions in process-oriented programming or adapting them to it. As a result, there is an answer on how effective the process-oriented paradigm is in solving those kinds of conflicts and how fault tolerant those programs are.
About the Author
D. A. Permiashkin
Institute of Automation and Electrometry SB RAS
Russian Federation
Russian Federation
Dmitry A. Permyashkin, Senior Engineer of Huawei Tech Company LLC
Novosibirsk
Moscow
References
1. John K. H., Tiegelkamp M. Programming Industrial Automation Systems // IEC 61131-3. 2010. DOI: 10.1007/978-3-642-12015-2
2. Zyubin V. E. Reflex Language. Mathematical model of control algorithms // Sensors and Systems. 2006. Vol. 5. Pp. 24–30. (in Russ.)
3. Zyubin V. E. Static balancing of computing resources in process-oriented programming // Vestnik NSU. Series: Information Technologies. 2012. Vol. 10, no. 2. Pp. 44–54. (in Russ.)
4. Zyubin V. E. et al. Basic module controlling the installation for growing single crystals of silicon // Sensors and Systems. 2004. Vol. 12. Pp. 17–22. (in Russ.)
5. Bulavskiy D. V. et al. Automated control system for a facility for growing single crystals of silicon // Autometric. 1996. Vol. 2. P. 26. (in Russ.)
6. Dijkstra E. W. Solution of a Problem in Concurrent Programming Control // Pioneers and Their Contributions to Software Engineering. 2001. Pp. 289–294. DOI: 10.1007/978-3-642-48354-7_10
7. Knuth D. E. Additional comments on a problem in concurrent programming control // Communications of the ACM. 1966. Vol. 9, no. 5. Pp. 321–322. DOI 10.1145/355592.365595
8. Anderson T. E. The performance of spin lock alternatives for shared-money multiprocessors // IEEE Transactions on Parallel and Distributed Systems. 1990. Vol. 1, no. 1. Pp. 6–16. DOI: 10.1109/71.80120
9. Mellor-Crummey J. M., Scott M. L. Algorithms for scalable synchronization on shared-memory multiprocessors // ACM Transactions on Computer Systems. 1991. Vol. 9, no. 1. Pp. 21–65. DOI: 10.1145/103727.103729
10. Kim Y.-J., Anderson J. H. A space- and time-efficient local-spin spin lock // Information Processing Letters. 2002. Vol. 84, no. 1. Pp. 47–55. DOI: 10.1016/s0020-0190(02)00224-7
11. Lamport L. A fast mutual exclusion algorithm // ACM Transactions on Computer Systems. 1987. Vol. 5, no. 1. Pp. 1–11. DOI: 10.1145/7351.7352
12. Afek Y., Attiya H., Fouren A., Stupp G., Touitou D. Long-lived renaming made adaptive // Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing. 1999. DOI: 10.1145/301308.301335
13. Afek Y., Merritt M. Fast, wait-free (2k-1)-renaming // Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing. 1999. DOI: 10.1145/301308.301338
14. Attiya H., Fouren A. Adaptive long-lived renaming with read and write operations (No. CS Technion report CS0956). Computer Science Department, Technion, 1999.
15. Michael M. M., Scott M. L. Fast Mutual Exclusion // Even with Contention. 1993. DOI: 10.21236/ada272947
16. Styer E. Improving fast mutual exclusion, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing. PODC’92, 1992. DOI: 10.1145/135419.135453
17. Choy M., Singh A. K. Adaptive solutions to the mutual exclusion problem // Distributed Computing. 1994. Vol. 8, no. 1. Pp. 1–17. DOI: 10.1007/bf02283567
18. Alur R., Attiya H., Taubenfeld G. Time-adaptive algorithms for synchronization // Proceedings of the twenty-sixth annual ACM symposium on Theory of computing. STOC’94, 1994. DOI: 10.1145/195058.195464
19. Kuhn F., Maus Y., Weidner S. Deterministic Distributed Ruling Sets of Line Graphs // Lecture Notes in Computer Science. 2018. Pp. 193–208. DOI: 10.1007/978-3-030-01325-7_19
20. Lamport L. The mutual exclusion problem: part I – A theory of interprocess communication // Journal of the ACM. 1986. Vol. 33, no. 2. Pp. 313–326. DOI: 10.1145/5383.5384
21. Lamport L. The mutual exclusion problem: Part II – Statement and solutions // Journal of the ACM. 1986. Vol. 33, no. 2. Pp. 327–348. DOI: 10.1145/5383.5385
22. Schneider J., Elkin M., Wattenhofer R. Symmetry breaking depending on the chromatic number or the neighborhood growth // Theoretical Computer Science. 2013. Vol. 509. P. 40–50. DOI: 10.1016/j.tcs.2012.09.004
23. Daymude J. J., Richa A. W., Scheideler C. Local mutual exclusion for dynamic, anonymous, bounded memory message passing systems [Online]. URL: https://arxiv.org/abs/2111.09449 (accessed on: 19.02.2023).
24. Fraser K., Harris T. Concurrent programming without locks // ACM Transactions on Computer Systems. 2007. Vol. 25, no. 2. P. 5.
Review
For citations:
Permiashkin D.A. On Solving Concurrent Process Problem in Process-Oriented Programs. Vestnik NSU. Series: Information Technologies. 2023;21(2):5-17. (In Russ.) https://doi.org/10.25205/1818-7900-2023-21-2-5-17
Views:
152
Email this article 