Controllable Deadlocks in Parallel Resource-Constrained Workflows
https://doi.org/10.18255/1818-1015-2014-6-18-30
Abstract
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.
About the Authors
V. A. Bashkin
P.G. Demidov Yaroslavl State University
Russian Federation
Russian Federation
докт. физ.-мат. наук, доцент,
Sovetskaya str., 14, Yaroslavl, 150000, Russia
N. Yu. Panfilova
P.G. Demidov Yaroslavl State University
Russian Federation
Russian Federation
магистрант,
Sovetskaya str., 14, Yaroslavl, 150000, Russia
References
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.
Review
For citations:
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
Views:
939
Email this article 