Wednesday , April 24 2024

Deadlock Detection and Avoidance Algorithm in Petri Nets Using the Resource Sharing Matrix

Jong Kun LEE
LIS/Computer Engineering Dept, Changwon National University
Salim-dong 9, Changwon, Kyungnam, Korea

Sang Hwan KIM
CIO/executive director, Daehan Calsonic Co.
Ho-tang li 340, Ip-jang myun, Chunan, Chungbuk, Korea

Abstract: This paper considers deadlock detection problem for FMS (Flexible Management System) based on the relationship of the resource share places in Petri Nets model. Since a deadlock is a condition in which the excessive demand for the resources being used by others causes activities to stop, it is very important to detect and prevent a deadlock. In this paper, after analyzing the relation of resource-share places in Petri Nets, we study the deadlock condition in FMS. This paper intends to review and compare these deadlock detection and avoidance methods based on the complexity, the effect value and the algorithm understanding.

Keywords: Avoidance, benchmark, DAPN, deadlock, Petri-nets, resource sharing, siphon, transitive matrix.

Lee Jong-kun has been a professor and Ph.D. supervisor at Changwon National University (CNU), Korea since 1983. He received his B. Sc. degree in Computer Science from Soongsil University, and the M. Engineering degree in Computer Engineering from Soongsil University, MBA from the Korea University, and Ph.D. in Computer engineering from the Ecole Centrale Paris. He is also director of NEXUS center of CNU, and chairman of Kyungnam Smart home technique Forum in Kyungnam. Currently, his research interests include concurrent model analysis and performance evaluation, Scheduling analysis in FMS, Mobile security and Petri nets theory.

Kim Sang-hwan is a Ph.D. in Computer Engineering from Chungbuk National University, Korea. He is also general manager of Daihan Calsonic Co., manufacturing air-condition system of Nissan Motor Company in Korea. His research interests include Petri net, Semantic Grid and workflow theory.

>>Full text
CITE THIS PAPER AS:
Jong Kun LEE, Sang Hwan KIM, Deadlock Detection and Avoidance Algorithm in Petri Nets Using the Resource Sharing Matrix, Studies in Informatics and Control, ISSN 1220-1766, vol. 17 (3), pp. 259-272, 2008.

1. Introduction

While deadlock problem is one of the important properties for analyzing the Petri nets, at the same time, it also could be one of the critical points in the scheduling problem of FMS (flexible Management System). Deadlock is a stopping status of the flow of a marking due to a resource waiting. Deadlock usually appears in contain subsystem which is run in parallel and resources share places.

The approaches to address deadlock are classified as prevention, avoidance, and detection/resolution. Deadlock prevention is a static server allocation approach, and averts deadlock by ensuring that the necessary conditions for deadlock cannot occur. Examples of preventive measures in a manufacturing system include uni-directional batching of jobs and providing a large number of in-process buffers. Deadlock avoidance is a dynamic server allocation approach that prevents the sufficient conditions for deadlock from occurring. Also, deadlock detection/resolution is a recovery procedures which detect deadlock occurs and restore the system operation [20]. Most of technical literatures have been used Petri nets to derive deadlock prevention and avoidance algorithms [1-3, 6, 9-11,13-19]. Deadlock avoidance methods are in many cases related to a set of sequential process sharing common resources of [15]. Xing et al. proposed a necessary and sufficient liveness condition based on the deadlock structure [16]. Moreover, J.park and S.A. Reveliotis [19] present deadlock avoidance policies for system with multiple resource acquisition and flexible routing, called conjunctive/disjunctive resource allocation system. Control places were also used for siphon control in [7,8,15]. However, while many researches on an application of the DES (Discrete Event System) to need a real time process have been studied, the proposed studies failed to ease an understanding and application of a system included many processes. Our method for deadlock prevention is based on the structural property. It considers Petri nets component such as transition and place invariant. Since this method may detect the deadlock status and avoid schedule in the transitive matrix directly, it’s easy to find the deadlock property. In this paper, we propose a method to analyze the deadlock problem and to avoid problem in Petri nets using the transitive matrix. Also, this paper is an extended variant of a work in [18].

This paper is organized as follows; some definitions of Petri Nets and transitive matrix are given in section 2. In section 3, we show a deadlock detection algorithm, and show an illustration model with one example. In section 4, their performance is analyzed and evaluated. Finally, in section 5, concludes the paper and suggests directions for future study.

5. Conclusion

In this paper, we focused on the avoidance policy of the deadlock problem in Petri nets using the transitive matrix. The transitive matrix explained all relationship between the places and transitions in the net. By these relationships, we can find deadlock status based on the relation between the resource share places. Finally, it can be said that it is easy to find the deadlock status and modify the deadlock status in the net. In this work, a simple example has been shown to compare three algorithms: siphon, DAPN and the proposed approach. After applying to a system with two machines and two jobs, we compared the results based on the three factors like as time, complexity and understandings. These results indicated that our method could be an easily understandable tool to find deadlock and to compute feasibility time.

Acknowledgement

We thank the LT 2007 staffs for recommending this work to the editors of SIC, as Prof. Niculescu and Prof. Jung for valuable comments and suggestions.

REFERENCES

  1. Corbett, J.C., Evaluating Deadlock detection methods for concurrent software, IEEE tr. Sof. Eng. Vol. 22(3), 1996, pp. 161-180.
  2. Damasceno, B.C. and Xie X, Petri nets and deadlock-free scheduling of multiple-resource operations, In: IEEE SMC’99, 1999, pp. 878-883.
  3. Ezpleta, J., Colom J.M., Martinez J., A Petri net based deadlock prevention policy for flexible manufacturing systems, IEEE tr. Robotics and Automat., Vol. 11, No. 2, 1995, pp. 173-184.
  4. Liu, J., Itoh Y., Miyazawa I., Seikiguchi T., A Research on Petri nets Properties using Transitive matrix, In: Proceeding IEEE SMC99, 1999, pp. 888-893.
  5. Lee, J., Korbaa O., Scheduling analysis of FMS: An unfolding time Petri nets approach, mathematics and Computer simulation, 70, 2006, pp. 419-432.
  6. Melzer, S. and Romer S., Deadlock checking using net Unfoldings, In: Proc. of the Conf. on Computer-Aided Verfication (CAV’97), 1997.
  7. Murata, T., Petri Nets: Properties, Analysis an Applications, Proceedings of the IEEE, 77(4), IEEE, USA, 1989, pp. 541-580.
  8. Peterson, J.L., Petri Net Theory and the Modeling of Systems, Englewood Cliffs, N.J.: Prentice-Hall, Inc., 1981.
  9. Shatz, S.M., Tu S., Murata T., An application of Petri net reduction for Ada Tasking Deadlock Analysis, In: IEEE Trans. on Parallel and Distributed Systems, Vol. 7, No. 12, 1996, pp. 1307-1322.
  10. Xiong, H.H., Zhou M.C., Deadlock free scheduling of an automated manufacturing system based on Petri nets, In: IEEE ICRA’97, 1997, pp. 945-950.
  11. Lee, J., Deadlock find algorithm using the Transitive Matrix, In: Proceeding CIE’04, 2004.
  12. A. Giua, et elc., observer-Based state-feedback control of timed Petri nets with deadlock recovery, In: IEEE Trans. on Automatic control, Vol. 49, No. 1, 2004, pp. 17-29.
  13. Ke-Yi, X., Hu BS, Chen HX, Deadlock Avoidance Policy for Petri net Modeling of Flexible Manufacturing Systems with Shared resources, In: IEEE Trans. on Automatic control, Vol. 41, No. 2, 1996, pp. 289-295.
  14. basil, F., A. Giua, C. Seatzu, Observer-based state-feedback control of time Petri nets with deadlock recovery: theory and implementation, In: Proceed. Of Symp. On Discrete events in Industrial and manufacturing systems, CESA 2003, 2003.
  15. Chu, F., X. Xie, Deadlock Analysis of Petri Nets using siphons and mathematical programming, In: IEEE Trans on Robotica and Automation, Vol.13, No. 6, 1997, pp. 793-804.
  16. Yujin, Song and Jongkun Lee, The study on the Deadlock Avoidance using the DAPN and the Adjacency Matrix, In Journal of the Korea Society for simulation, vol. 15, no. 3, 2006, pp. 1-10.
  17. Kim, S.-H., S-H Lee, J-K. Lee, Deadlock analysis of Petri nets based on the Resource Share Places Relationship, In Studies in Informatics and control, vol. 16, no. 1, 2007, pp. 33-44.
  18. Kim, S.-H., J-K. Lee, Benchmark Study of Deadlock analysis methods in FMS, In: proceeding of LT2007, Tunis, 2007, pp. 363-368.
  19. Park, J., S. A. Reveliotis, Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible manufacturing, In: IEEE tr. Robotics and Automat., Vol. 46, 2001, pp. 1572-1583.
  20. Dotoli, M., M.P. Fanti, Deadlock Detection and Avoidance strategies for Automated Storage and Retrieval Systems, In: IEEE Trans. on SMC-C, Vol. 37, No. 4, 2007, pp. 541-552.
  21. Li, ZW, MC Zhou, Elementary Siphons of Petri Nets and Their Application to deadlock prevention in Flexible manufacturing Systems, In: IEEE Trans. on SMC-A, Vol. 34, No. 1, 2004, pp. 38-51.
  22. Abdallah, I.B., H.A. ElMaraghy, Deadlock Prevention and Avoidance in FMS: A Petri Net Based Approach , In: J. Adv. Manuf. Technol., Vol. 14, 1998, pp. 704-715.
  23. Girault, C., R. Valk, Petri Nets for Systems Engineering, Springer-Verlag, Berlin Heidelberg, 2003.
Designed by | ICI Bucharest
© Copyright 2024, All Rights Reserved