패트리 넷에서의 교착 상태 확인 알고리즘 성능분석

• 영문명: An Performance Evaluation of the Deadlock Detection Algorithm in Petri Nets
• 발행기관: 한국시뮬레이션학회
• 저자명: 김종욱(Jongwoog Kim) 이종근(Jongkun Lee)
• 간행물 정보: 『한국시뮬레이션학회 논문지』제18권 제1호, 9~16쪽, 전체 8쪽
• 주제분류: 공학 > 기타공학
• 파일형태: PDF
• 발행일자: 2009.03.30

국문 초록

본 연구에서는 교착상태 확인 알고리즘의 성능분석을 위하여 사이폰(siphon) 알고리즘, DAPN알고리즘과 추이적 행렬 알고리즘을 상호 비교한다. 이를 위하여 비교 모델을 설정하여 각 알고리즘을 활용한 결과를 복잡도, 이해도 그리고 신속성 등의 3가지 함수를 이용하여 성능을 분석한다. 서로 다른 개념의 알고리즘을 비교분석에 한계성이 있으나, 동일한 모델에 적용하여 그 효율성을 비교 분석하여 각 알고리즘의 특성들을 분석한다.

영문 초록

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. About the deadlock detection analysis methods are may divide like as Siphon, DAPN and transitive matrix, but it’s very difficult to evaluate the performance. Since DES (Discrete Event Systems) is NP-hard, and these detection and avoidance methods used various factors in each technique, it’s made difficult to compare with each other’s. In this paper, we are benchmarked these deadlock detection analyze methods based on the complexity, the detection time and the understanding after approached to one example.

목차

1. 서론

2. 예시 모델

3. 비교분석 알고리즘

4. 알고리즘 벤치마킹

5. 결론 및 향후 연구

키워드

알고리즘 교착회피 패트리 넷 교착상태 교착자유상태 패트리 넷 사이폰 추이적행렬 Algorithm DAPN Deadlock Deadlock free Petri nets Siphon Transitive matrix