Управляемые тупики в параллельных ресурсно-ограниченных потоках работ
https://doi.org/10.18255/1818-1015-2014-6-18-30
Аннотация
Работа посвящена проблеме проверки правильной организованности (бездефектности) сетей потоков работ с ресурсами. Поток работ называется бездефектным, если он может быть корректно завершен от любого достижимого состояния. Рассматривается класс схем ресурсно-ограниченных потоков работ (RCWF-сетей), в которых экземпляры процесса могут использовать внешние ресурсы, но не могут за время своей жизни изменить их количество.
Две бездефектные RCWF-сети, использующие один и тот же набор ресурсов, могут быть запущены параллельно. Подобная параллельная композиция в некоторых случаях может порождать дополнительные тупики, вызванные взаимными блокировками. Мы исследуем проблему обнаружения потенциальных блокировок и предлагаем способы организации такого управления сетью, которое позволило бы их избегать.
При поддержке: РФФИ
Об авторах
Владимир Анатольевич Башкин
Ярославский государственный университет им. П. Г. Демидова
Россия
докт. физ.-мат. наук, доцент, 150000 Россия, г. Ярославль, ул. Советская, 14
Россия
докт. физ.-мат. наук, доцент, 150000 Россия, г. Ярославль, ул. Советская, 14
Надежда Юрьевна Панфилова
Ярославский государственный университет им. П. Г. Демидова
Россия
магистрант, 150000 Россия, г. Ярославль, ул. Советская, 14
Россия
магистрант, 150000 Россия, г. Ярославль, ул. Советская, 14
Список литературы
1. Ван дер Аалст В., ван Хей К. Управление потоками работ: модели, методы и системы. М.: Научный мир, 2007. (English transl.: van der Aalst W., van Hee K. Workflow Management: Models, Methods and Systems. MIT Press, 2002.)
2. Башкин В. А. Сети активных ресурсов // Моделирование и анализ информационных систем. 2007. Т. 14. № 4. С. 13–19.
3. Башкин В. А. Формализация семантики систем с ненадежными агентами при помощи сетей активных ресурсов // Программирование. 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.)
4. 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.
5. 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.
6. 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.
7. 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.
8. Bashkin V. A., Lomazova I. A. Petri nets and resource bisimulation // Fundamenta Informaticae. 2003. Vol. 55. No. 2. P. 101–114.
9. 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.
10. 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.
11. Chrz¸astowski-Wachtel P. Sound Markings in Structured Nets // Proc. of Concurrency, Specification and Programming (CS&P’2005). Warsaw University, 2005. P. 71–85.
12. 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.
13. 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.
14. Lomazova I. A., Romanov I. V. Analyzing Compatibility of Services via Resource Conformance // Fundamenta Informaticae. 2013. Vol. 128. No. 1–2. P. 129–141.
15. 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.
Рецензия
Для цитирования:
Башкин В.А., Панфилова Н.Ю. Управляемые тупики в параллельных ресурсно-ограниченных потоках работ. Моделирование и анализ информационных систем. 2014;21(6):18-30. https://doi.org/10.18255/1818-1015-2014-6-18-30
For citation:
Bashkin V.A., Panfilova N.Yu. Controllable Deadlocks in Parallel Resource-Constrained Workflows. Modeling and Analysis of Information Systems. 2014;21(6):18-30. (In Russ.) https://doi.org/10.18255/1818-1015-2014-6-18-30
Просмотров:
922
Послать статью по эл. почте 