추이적 행렬을 이용한 사이폰 감지 정책

A Policy to Find All Siphons using Transitive Matrix

교착이란 일반적으로 병행과 자원공유 모듈에 의한 서브 시스템에서 발생한다. 사이폰과 트랩은 패트리 넷의 교착 상태를 잘 나타낸다. 사이폰은 많은 연구자들에게 교착을 감지하고 방지하는데 사용되어진 개념이다. 그러나 모든 사이폰 서브넷을 감지하는데는 많은 시간과 노력이 필요하다. 추이적 행렬은 플레이스와 트랜지션간의 관계를 표현하므로 추이적 행렬과의 관계를 분석하여 모든 사이폰 서브 넷을 감지하는 알고리즘을 제안한다. 또한 제안한 알고리즘의 성능을 사례를 들어 검증한다.

Deadlock usually appears in contain subsystem which is run in parallel and resources share modules. Siphons and traps have been well introduced to characterize deadlocks of Petri nets. Siphon concept be well used for proposing the detect and prevent deadlock by the pleasure researchers. But it s need many times and efforts to detect all siphon sub-nets in the Petri model. Since transitive matrix could explain all relations between the place and transitions in Petri nets, we propose an algorithm to detect all siphon sub-nets after analyzed the transitive matrix s properties. Examples are givens to illustrate the method.