| 초록 |
본 논문에서는 다중처리 시스템(Multiprocessing system)하에서 발생되는 노트(Knot)를 발생 즉시에 탐지함으로써 교착상태의 발견을 병렬적으로 수행할 수 있는 방법을 제시하였다. 제시된 방법은 모든 프로세스가 한번에 하나의 자원씩만 요청할 수 있도록 하였으며 즉시 할당상태로 가정하였다. 제시된 방법은 현재까지 알려진 노트 발견기법들이 사용한 대기 그래프(Wait-for-graph)대신 다른 자료구조를 사용하여 노트의 발견을 0(1)으로 가능하게 하였으며, 노트 판단후의 작업과 자원의 반납시에는 n과 m을 시스템내의 프로세스와 자원의 개수로 나타낼 때 0(nm)의 수행시간을 요구한다. 따라서, n과 m의 크기에 무관하게 교착상태의 판단을 즉각 할 수 있으며, 0(nm) 작업들은 교착상태가 아닐 경우의 작업들이므로 다중처리 시스템하에서 여분의 프로세서(Processors)를 사용하여 다른 작업에 영향을 주지않고 병렬 수행이 가능하게 된다. 응용 환경에 따라서는 이러한 수행시간의 예측성과 비 지연성이 매우 중요하다. |
