[논문]자원 공유 플레이스 추이적 행렬을 이용한 효율적인 교착상태 확인 정책

김종욱; 이종근

초록
AI-Helper

여러 개의 작업이 동시에 작동 할 때 서로 다른 작업에서 공유자원을 사용하기 위하여 상대방의 작업이 끝나기를 기다리는 상태를 교착상태라 하며 이는 시스템의 효율성과 경제성 제고에 가장 중요한 문제 중 하나이다. 지금까지 이러한 교착상태 확인은 도달성(reachability)기법이나 서브 넷(Subnet)으로 분리하여 분석하는 기법 등이 가장 많이 사용되었으나, 분석에 필요한 시간과 노력, 복잡성과 효율성에 있어서 효과적이지 못한 단점을 가지고 있다. 본 연구는 패트리 넷(Petri Net)에서 모든 플레이스(Place) 간의 관계를 나타내는 추이적(Transitive)행렬을 이용하여 교착상태가 나타날 가능성이 있는 자원공유 플레이스를 분석하여 교착상태를 검증하는 정책을 제시한다. 이를 위하여 교착상태를 확인할 수 있는 자원공유 플레이스의 관계를 정의하고, 유연생산시스템 모델을 이용하여 제안한 알고리즘의 성과를 검증한다.

Abstract ▼ AI-Helper

A deadlock is a condition in which the excessive demand for the resources being used by others causes activities to stop and it is one of the important problems in process control system to detect and prevent deadlocks. While the reachability analyze methods or divide subnets for analyzing methods a...

A deadlock is a condition in which the excessive demand for the resources being used by others causes activities to stop and it is one of the important problems in process control system to detect and prevent deadlocks. While the reachability analyze methods or divide subnets for analyzing methods are well used, it requires a lot of times and effects to analyze the detection of the deadlock status. Furthermore, it could not be effective if the model is complex or huge. Therefore, it is necessary to develop a new and more efficient deadlock detection algorithm. In this paper, a deadlock detection conditions after analyzed the Petri Net using the transitive matrix has been proposed to solve these problems. For presenting the results, the suggested deadlock detection algorithm was also adapted to an illustrated FMS (Flexible Manufacturing System) model.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서 추이적 행렬을 기반으로 하여 패트리 넷의 교착상태 문제 분석과 추이적 행렬을 기반으로 하는 자원공유 플레이스의 교착상태 조건을 제안하였다. 교착 상태 문제는 충돌 플레이스에 기반한 두 개 이상의 트랜지션 관계에서 발생하였다.

제안 방법

교착 상태 문제는 충돌 플레이스에 기반한 두 개 이상의 트랜지션 관계에서 발생하였다. 그러므로 입력 토큰의 수가 출력 토큰의 수 보다 작으면 공유 플레이스에서 교착이 발생하였고, 충돌 플레이스내 입력토큰과 출력토큰의 관계를 이용한 교착상태 조건을 제안하였다. 또한 추이적 행렬을 이용하여 공유 플레이스의 교착상태 여부를 판단하는 수리적 판별식을 제안하였으며 그 실효성을 위하여 여러 예제에 적용하여 교착상태 및 교착자유상태 여부를 검증하였다.
추이적 행렬이란, 패트리 넷의 플레이스와 트랜지션간의 관계를 모두 표현함으로 토큰의 흐름을 행렬을 통하여 분석이 가능하며, 모든 형태의 플레이스 확인이 가능하고, 또한 흐름의 제반 내용을 표를 통하여 분석 가능한 특징을 가지고 있다. 따라서, 교착 가능한 플레이스는 자원공유 플레이스임에 착안하여 공유 플레이스간의 관계를 수리적으로 분석하여 교착상태 발생 가능한 위치를 확인함으로 시스템의 성질 분석 및 검증이 용이하도록 알고리즘을 제안한다.
그러므로 입력 토큰의 수가 출력 토큰의 수 보다 작으면 공유 플레이스에서 교착이 발생하였고, 충돌 플레이스내 입력토큰과 출력토큰의 관계를 이용한 교착상태 조건을 제안하였다. 또한 추이적 행렬을 이용하여 공유 플레이스의 교착상태 여부를 판단하는 수리적 판별식을 제안하였으며 그 실효성을 위하여 여러 예제에 적용하여 교착상태 및 교착자유상태 여부를 검증하였다. 제안 된 교착상태 감지 알고리즘은 다른 분석 알고리즘에 비해 쉽고 간단하게 교착 여부를 판별 가능 한 특성을 가지나 회피를 위한 후속 작업 즉 회피와 방지 알고리즘이 아직 제시가 되지 못한 한계점을 갖는다.
그러나 초기 모델이 크거나 복잡한 경우 도달성 그래프가^[25]거대하여 지고 복잡하여져 분석에 많은 시간과 노력이 필요하게 된다. 본 연구에서는 패트리 넷에서의 플레이스와 트랜지션간의 관계를 표현 하는 추이적 행렬^[14,15,16] 을 이용하여 자원공유 플레이스간의 산술적 해석으로 교착상태를 확인하는 알고리즘을 제안한다. 추이적 행렬이란, 패트리 넷의 플레이스와 트랜지션간의 관계를 모두 표현함으로 토큰의 흐름을 행렬을 통하여 분석이 가능하며, 모든 형태의 플레이스 확인이 가능하고, 또한 흐름의 제반 내용을 표를 통하여 분석 가능한 특징을 가지고 있다.
본 연구에서 제안한 추이적 행렬을 이용한 교착상태 확인 알고리즘은 행렬 자체에서 교착여부 확인이 가능한 장점을 가진다. 즉 기존의 siphon이나 도달성 트리의 경우 패트리 넷에서 마킹의 흐름을 전부 확인하여야 교착 여부 확인이 가능한데, 제안한 알고리즘은 공유 플레이스를 기준으로 수리적인 판별식으로 분석하는 관계로 모든 마킹의 흐름을 분석하는 노력과 시간의 절약이 가능하다. 기존의 추이적 행렬을 이용한 알고리즘의 경우^[10,15,25]작업 별로 구분 되어진 서브 넷의 마킹 흐름을 도달성 트리 형식으로 분석하여 교착상태를 결정하였으나, 제안한 알고리즘은 이러한 작업 별 서브 넷의 분리 작업 없이 행렬에서 수리적 산술법으로 교착여부 확인이 가능하여 더욱 빠르게 교착여부를 확인 할 수가 있었다.

대상 데이터

FMS의 사례 모델은 2개의 기기 M1과 M2가 존재하며, 한 개의 로봇과 두 개의 이동 포트가 있다. 또한 두 개의 작업 Job 1과 Job 2가 존재하는데 Job1은 기기M1→ M2의 순으로 Job2는 기기M2→M1의 순으로 각각 작업에 사용된다.

성능/효과

1) 마킹 M으로부터 어떠한 트랜지션으로 점화가능하지 못하다면, 그 트랜지션은 교착 트랜지션이라 한다.
즉 기존의 siphon이나 도달성 트리의 경우 패트리 넷에서 마킹의 흐름을 전부 확인하여야 교착 여부 확인이 가능한데, 제안한 알고리즘은 공유 플레이스를 기준으로 수리적인 판별식으로 분석하는 관계로 모든 마킹의 흐름을 분석하는 노력과 시간의 절약이 가능하다. 기존의 추이적 행렬을 이용한 알고리즘의 경우^[10,15,25]작업 별로 구분 되어진 서브 넷의 마킹 흐름을 도달성 트리 형식으로 분석하여 교착상태를 결정하였으나, 제안한 알고리즘은 이러한 작업 별 서브 넷의 분리 작업 없이 행렬에서 수리적 산술법으로 교착여부 확인이 가능하여 더욱 빠르게 교착여부를 확인 할 수가 있었다. 그러나 제안한 알고리즘에서는 교착상태여부를 빠르게 인지가 가능한 반면 교착상태 회피를 위한 알고리즘은 아직 제시되지 못하는 한계점이 있다.
본 연구에서 제안한 추이적 행렬을 이용한 교착상태 확인 알고리즘은 행렬 자체에서 교착여부 확인이 가능한 장점을 가진다. 즉 기존의 siphon이나 도달성 트리의 경우 패트리 넷에서 마킹의 흐름을 전부 확인하여야 교착 여부 확인이 가능한데, 제안한 알고리즘은 공유 플레이스를 기준으로 수리적인 판별식으로 분석하는 관계로 모든 마킹의 흐름을 분석하는 노력과 시간의 절약이 가능하다.
위의 마킹 흐름과 같이 모든 플레이스의 점화가 가능하며 특히 플레이스 p3은 계속해서 토큰의 수가 증가하게 되어 제한적이지 않은 성질을 갖게 됨을 확인 할 수가 있다.

후속연구

기존의 추이적 행렬을 이용한 알고리즘의 경우^[10,15,25]작업 별로 구분 되어진 서브 넷의 마킹 흐름을 도달성 트리 형식으로 분석하여 교착상태를 결정하였으나, 제안한 알고리즘은 이러한 작업 별 서브 넷의 분리 작업 없이 행렬에서 수리적 산술법으로 교착여부 확인이 가능하여 더욱 빠르게 교착여부를 확인 할 수가 있었다. 그러나 제안한 알고리즘에서는 교착상태여부를 빠르게 인지가 가능한 반면 교착상태 회피를 위한 알고리즘은 아직 제시되지 못하는 한계점이 있다.
또한 추이적 행렬을 이용하여 공유 플레이스의 교착상태 여부를 판단하는 수리적 판별식을 제안하였으며 그 실효성을 위하여 여러 예제에 적용하여 교착상태 및 교착자유상태 여부를 검증하였다. 제안 된 교착상태 감지 알고리즘은 다른 분석 알고리즘에 비해 쉽고 간단하게 교착 여부를 판별 가능 한 특성을 가지나 회피를 위한 후속 작업 즉 회피와 방지 알고리즘이 아직 제시가 되지 못한 한계점을 갖는다. 향후 다른 교착상태 감지 알고리즘과의(siphon, 도달성 트리 등) 성능분석을 통한 활용성 검증, 추이적 행렬을 이용한 일반적 패트리 넷 모델 확장 및 FMS의 교착상태회피에 의한 사이클릭 스케쥴링(cyclic scheduling) 연구로 확장해 나갈 필요가 있다.
제안 된 교착상태 감지 알고리즘은 다른 분석 알고리즘에 비해 쉽고 간단하게 교착 여부를 판별 가능 한 특성을 가지나 회피를 위한 후속 작업 즉 회피와 방지 알고리즘이 아직 제시가 되지 못한 한계점을 갖는다. 향후 다른 교착상태 감지 알고리즘과의(siphon, 도달성 트리 등) 성능분석을 통한 활용성 검증, 추이적 행렬을 이용한 일반적 패트리 넷 모델 확장 및 FMS의 교착상태회피에 의한 사이클릭 스케쥴링(cyclic scheduling) 연구로 확장해 나갈 필요가 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	교착상태란?	교착상태란 시스템의 공정 중에 포함 된 여러 작업에서 공동으로 사용되는 공유 자원을 각 작업에서 상호적으로 사용을 기다려 시스템의 작업 공정이 중단 된 상태를 의미하며, 현대의 많은 기술 시스템인 자동생산시스템, 데이터 통신, 다중처리 운영시스템과 분산 데이터 베이스 시스템 등에서 가장 잘 알려진 문제이다. 다양한 시스템 에서 교착상태 발생은 시스템 관리와 작업과정 등에서 효율적인 처리 과정을 중단시키거나 무력화 시키며 특히 자원 공유 체제를 붕괴 시키는 중대한 결함을 야기시킨다[17].
	교착상태가 많이 발생되는 곳은?	교착상태란 시스템의 흐름에서 서로가 대기상태가 되어 마킹의 흐름이 정지 될 경우 이를 교착상태라 한다. 또한 이러한 상태는 주로 자원공유 플레이스에서 많이 발생되는 성질이 있다. 즉 자원공유 플레이스에서의 입출력 토큰의 수가 음수이거나 정수가 되지 못하면 자력으로 점화가 불가하므로 교착상태 가능성이 있다.
	교착상태 발생은 시스템에서 무엇을 야기하는가?	교착상태란 시스템의 공정 중에 포함 된 여러 작업에서 공동으로 사용되는 공유 자원을 각 작업에서 상호적으로 사용을 기다려 시스템의 작업 공정이 중단 된 상태를 의미하며, 현대의 많은 기술 시스템인 자동생산시스템, 데이터 통신, 다중처리 운영시스템과 분산 데이터 베이스 시스템 등에서 가장 잘 알려진 문제이다. 다양한 시스템 에서 교착상태 발생은 시스템 관리와 작업과정 등에서 효율적인 처리 과정을 중단시키거나 무력화 시키며 특히 자원 공유 체제를 붕괴 시키는 중대한 결함을 야기시킨다[17]. 이러한 교착 문제를 해결하기 위한 교착상태 확인 및 회피 방법에 대하여 많은 연구가 제안 되어 왔는데, 대표적인 분석기법으로 패트리 넷(Petri Net)을 활용하는 연구가[1-3,5-7,9-13,15,17,19,22-25] 활발하다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

자원 공유 플레이스 추이적 행렬을 이용한 효율적인 교착상태 확인 정책
An Efficient Deadlock Detection Policy Using the Transitive Matrix of Resource Share Places 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

성능/효과

후속연구

질의응답

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

연관된 기능

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

자원 공유 플레이스 추이적 행렬을 이용한 효율적인 교착상태 확인 정책 An Efficient Deadlock Detection Policy Using the Transitive Matrix of Resource Share Places 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

성능/효과

후속연구

질의응답

이 논문을 인용한 문헌

저자의 다른 논문 :

김종욱 (2) 이종근 (26)

관련 콘텐츠

원문 보기

연관된 기능

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

자원 공유 플레이스 추이적 행렬을 이용한 효율적인 교착상태 확인 정책
An Efficient Deadlock Detection Policy Using the Transitive Matrix of Resource Share Places 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper