К вопросу о разрешении проблемы конкурирующих процессов в процесс-ориентированном программировании

В современном мире значительная часть фабрик и промышленных производств уже управляются программируемыми микроконтроллерами и число такого рода производств непрерывно растет. Данный процесс тесно взаимосвязан с идеями Индустрии 4.0, а если быть точнее – с идеей полной автоматизации производственных процессов для облегчения принятия решений человеку. И одновременно уменьшения числа принимаемых человеком решений вплоть до полного отсутствия человека в роли принимающего решения. Для этого требуются управляющие алгоритмы, которые должны работать по событиям, учитывать наличие и тесный контакт с внешней средой и иметь повышенные требования к устойчивости к внутренним отказам и отказам оборудования. Разработанная в Институте автоматики и электрометрии СО РАН процесс-ориентированная парадигма программирования, рассматриваемая в данной статье, прекрасно подходит для разработки управляющих алгоритмов такого рода. Данная парадигма учитывает тот факт, что производственный процесс представляет собой очень большое число одновременно работающих процессов, тесно связанных с элементами реального мира. Отсюда вытекает необходимость решения проблемы конкурирующих процессов для обеспечения требуемой степени устойчивости к отказам. В данной статье будет поставлена и проанализирована проблема конкурирующих процессов. Для этого в работе был произведен анализ существующих решений проблемы конфликтов при параллельной работе произвольного числа процессов с целью анализа применимости данных методов для процесс-ориентированных программ или же возможности адаптации некоторых методов. В результате будет получен ответ на вопрос, насколько эффективно процесс-ориентированная парадигма позволяет решать конфликты при параллельном исполнении программы и насколько сильно удовлетворяет требованию отказоустойчивости.

1. John K. H., Tiegelkamp M. Programming Industrial Automation Systems // IEC 61131-3. 2010. DOI: 10.1007/978-3-642-12015-2

2. Зюбин В. Е. Язык Рефлекс. Математическая модель алгоритмов управления // Датчики и системы. 2006. № 5. С. 24–30.

3. Зюбин В. Е. Статическая балансировка вычислительных ресурсов в процесс-ориентированном программировании // Вестник НГУ. Серия: Информационные технологии. 2012. Т. 10. Вып. 2. С. 44–54.

4. Зюбин В. Е. и др. Базовый модуль, управляющий установкой для выращивания монокристаллов кремния //Датчики и системы. 2004. №. 12. С. 17–22.

5. Булавский Д. В. и др. Автоматизированная система управления установкой для выращивания монокристаллов кремния //Автометрия. 1996. №. 2. С. 26.

6. Dijkstra E. W. Solution of a Problem in Concurrent Programming Control, Pioneers and Their Contributions to Software Engineering, p. 289–294, 2001, 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, vol. 9, no. 5, p. 321–322, May 1966, 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, vol. 1, no. 1, p. 6–16, 1990, 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, vol. 9, no. 1, p. 21–65, Feb. 1991, DOI: 10.1145/103727.103729

10. Kim Y.-J., Anderson J. H. A spaceand time-efficient local-spin spin lock, Information Processing Letters, vol. 84, no. 1, p. 47–55, Oct. 2002, DOI: 10.1016/s0020-0190(02)00224-7

11. Lamport L. A fast mutual exclusion algorithm, ACM Transactions on Computer Systems, vol. 5, no. 1, p. 1–11, Jan. 1987, 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, May 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, May 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, Jun. 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, vol. 8, no. 1, p. 1–17, Aug. 1994, 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, p. 193–208, 2018, 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, vol. 33, no. 2, p. 313–326, Apr. 1986, DOI: 10.1145/5383.5384

21. Lamport L. The mutual exclusion problem: Part II Statement and solutions, Journal of the ACM, vol. 33, no. 2, p. 327–348, Apr. 1986, 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, vol. 509, p. 40–50, Oct. 2013, 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, arXiv.org, 24-Feb-2022. [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, vol. 25, no. 2, p. 5, 2007