maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2014-6-18-30mais-68Research ArticleОригинальные статьиArticlesУправляемые тупики в параллельных ресурсно-ограниченных потоках работControllable Deadlocks in Parallel Resource-Constrained WorkflowsБашкинВладимир АнатольевичBashkinV. A.

докт. физ.-мат. наук, доцент, 150000 Россия, г. Ярославль, ул. Советская, 14

докт. физ.-мат. наук, доцент,

Sovetskaya str., 14, Yaroslavl, 150000, Russia

v_bashkin@mail.ruПанфиловаНадежда ЮрьевнаPanfilovaN. Yu.

магистрант, 150000 Россия, г. Ярославль, ул. Советская, 14

магистрант,

Sovetskaya str., 14, Yaroslavl, 150000, Russia

lillian007@mail.ruЯрославский государственный университет им. П. Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian Federation2014201220142161830Copyright © Башкин В.А., Панфилова Н.Ю., 20142014Башкин В.А., Панфилова Н.Ю.Bashkin V.A., Panfilova N.Y.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/68

Работа посвящена проблеме проверки правильной организованности (бездефектности) сетей потоков работ с ресурсами. Поток работ называется бездефектным, если он может быть корректно завершен от любого достижимого состояния. Рассматривается класс схем ресурсно-ограниченных потоков работ (RCWF-сетей), в которых экземпляры процесса могут использовать внешние ресурсы, но не могут за время своей жизни изменить их количество.

Две бездефектные RCWF-сети, использующие один и тот же набор ресурсов, могут быть запущены параллельно. Подобная параллельная композиция в некоторых случаях может порождать дополнительные тупики, вызванные взаимными блокировками. Мы исследуем проблему обнаружения потенциальных блокировок и предлагаем способы организации такого управления сетью, которое позволило бы их избегать.

We study the verification of the soundness property for workflow nets extended with resources. A workflow is sound if it terminates properly (no deadlocks and livelocks are possible). A class of resource-constrained workflow nets (RCWF-nets) is considered, where resources can be used by a process instance, but cannot be created or spent. Two sound RCWF-nets using the same set of resources can be put in parallel. This parallel composition may in some cases produce additional deadlocks. A problem of deadlock avoidance in parallel workflows is studied, some methods of deadlock search and control are presented.

потоки работресурсбездефектностьпараллельная композициятупикверификацияworkflowresourcesoundnessparallel compositiondeadlockverificationРФФИReferencesВан дер Аалст В., ван Хей К. Управление потоками работ: модели, методы и системы. М.: Научный мир, 2007. (English transl.: van der Aalst W., van Hee K. Workflow Management: Models, Methods and Systems. MIT Press, 2002.)Ван дер Аалст В., ван Хей К. Управление потоками работ: модели, методы и системы. М.: Научный мир, 2007. (English transl.: van der Aalst W., van Hee K. Workflow Management: Models, Methods and Systems. MIT Press, 2002.)Башкин В. А. Сети активных ресурсов // Моделирование и анализ информационных систем. 2007. Т. 14. № 4. С. 13–19.Башкин В. А. Сети активных ресурсов // Моделирование и анализ информационных систем. 2007. Т. 14. № 4. С. 13–19.Башкин В. А. Формализация семантики систем с ненадежными агентами при помощи сетей активных ресурсов // Программирование. 2010. №4. С.3–15. (English transl.: Bashkin V. A. Formalization of semantics of systems with unreliable agents by means of nets of active resources // Programming and Computer Software. 2010. 36(4). P. 187–196.)Башкин В. А. Формализация семантики систем с ненадежными агентами при помощи сетей активных ресурсов // Программирование. 2010. №4. С.3–15. (English transl.: Bashkin V. A. Formalization of semantics of systems with unreliable agents by means of nets of active resources // Programming and Computer Software. 2010. 36(4). P. 187–196.)Van der Aalst W. M. P. The Application of Petri Nets to Workflow Management // The Journal of Circuits, Systems and Computers. 1998. 8(1). P. 21–66.Van der Aalst W. M. P. The Application of Petri Nets to Workflow Management // The Journal of Circuits, Systems and Computers. 1998. 8(1). P. 21–66.Van der Aalst W.M.P., van Hee K.M., Hofstede A.H.M., Sidorova N., Verbeek H.M.W., Voorhoeve M., Wynn M.T. Soundness of workflow nets: classification, decidability, and analysis // Formal Aspects of Computing. 2011. 23(3). P. 333–363.Van der Aalst W.M.P., van Hee K.M., Hofstede A.H.M., Sidorova N., Verbeek H.M.W., Voorhoeve M., Wynn M.T. Soundness of workflow nets: classification, decidability, and analysis // Formal Aspects of Computing. 2011. 23(3). P. 333–363.Barkaoui K., Petrucci L. Structural Analysis of Workflow Nets with Shared Resources // Proc. of Workflow Management: Net-based Concepts, Models, Techniques and Tools (WFM98). Computing Science Reports. Eindhoven University of Technology. 1998. Vol. 98/7. P. 82–95.Barkaoui K., Petrucci L. Structural Analysis of Workflow Nets with Shared Resources // Proc. of Workflow Management: Net-based Concepts, Models, Techniques and Tools (WFM98). Computing Science Reports. Eindhoven University of Technology. 1998. Vol. 98/7. P. 82–95.Barkaoui K., Ben Ayed R., Sba¨ı Z. Workflow Soundness Verification based on Structure Theory of Petri Nets // International Journal of Computing and Information Sciences. 2007. 5(1). P. 51–61.Barkaoui K., Ben Ayed R., Sba¨ı Z. Workflow Soundness Verification based on Structure Theory of Petri Nets // International Journal of Computing and Information Sciences. 2007. 5(1). P. 51–61.Bashkin V. A., Lomazova I. A. Petri nets and resource bisimulation // Fundamenta Informaticae. 2003. Vol. 55. No. 2. P. 101–114.Bashkin V. A., Lomazova I. A. Petri nets and resource bisimulation // Fundamenta Informaticae. 2003. Vol. 55. No. 2. P. 101–114.Bashkin V. A., Lomazova I. A. Resource equivalence in workflow nets // Proc. of Concurrency, Specification and Programming (CS&P’2006). Humboldt Universitat zu Berlin, 2006. Vol. 1. P. 80–91.Bashkin V. A., Lomazova I. A. Resource equivalence in workflow nets // Proc. of Concurrency, Specification and Programming (CS&P’2006). Humboldt Universitat zu Berlin, 2006. Vol. 1. P. 80–91.Bashkin V. A., Lomazova I. A. Soundness of Workflow Nets with an Unbounded Resource is Decidable // Joint Proc. of Petri Nets and Software Engineering (PNSE’13) and Modeling and Business Environments (ModBE’13). 2013. Vol. 989 of CEUR. P. 61–75.Bashkin V. A., Lomazova I. A. Soundness of Workflow Nets with an Unbounded Resource is Decidable // Joint Proc. of Petri Nets and Software Engineering (PNSE’13) and Modeling and Business Environments (ModBE’13). 2013. Vol. 989 of CEUR. P. 61–75.Chrz¸astowski-Wachtel P. Sound Markings in Structured Nets // Proc. of Concurrency, Specification and Programming (CS&P’2005). Warsaw University, 2005. P. 71–85.Chrz¸astowski-Wachtel P. Sound Markings in Structured Nets // Proc. of Concurrency, Specification and Programming (CS&P’2005). Warsaw University, 2005. P. 71–85.Ezpeleta J., Colom J.-M., Martinez J. A Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems // IEEE Transactions on Robotics and Automation. 1995. 11(2). P. 173–184.Ezpeleta J., Colom J.-M., Martinez J. A Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems // IEEE Transactions on Robotics and Automation. 1995. 11(2). P. 173–184.Van Hee K., Serebrenik A., Sidorova N., Voorhoeve M. Soundness of Resource-Constrained Workflow Nets // Proc. of ICATPN 2005. Lecture Notes in Computer Science. 2005. Vol. 3536. P. 250–267.Van Hee K., Serebrenik A., Sidorova N., Voorhoeve M. Soundness of Resource-Constrained Workflow Nets // Proc. of ICATPN 2005. Lecture Notes in Computer Science. 2005. Vol. 3536. P. 250–267.Lomazova I. A., Romanov I. V. Analyzing Compatibility of Services via Resource Conformance // Fundamenta Informaticae. 2013. Vol. 128. No. 1–2. P. 129–141.Lomazova I. A., Romanov I. V. Analyzing Compatibility of Services via Resource Conformance // Fundamenta Informaticae. 2013. Vol. 128. No. 1–2. P. 129–141.Sidorova N., Stahl C. Soundness for resource-contrained workflow nets is decidable // IEEE Transactions on Systems, Man, and Cybernetics: Systems. 2013. 43(3). P. 724–729.Sidorova N., Stahl C. Soundness for resource-contrained workflow nets is decidable // IEEE Transactions on Systems, Man, and Cybernetics: Systems. 2013. 43(3). P. 724–729.

The authors declare that there are no conflicts of interest present.