교착상태 탐지

교착상태 탐지 알고리즘

쇼사니(Shoshani)와 포크만(Coffman)이 제안.

다음과 같은 자료구조들을 사용함.

Available : 자원 형태마다 사용 가능한 자원 수를 표시하는 길이가 m인 벡터.

Allocation : 각 프로세스에 현재 할당된 각 형태들의 자원 수를 표시하는 n ⅹ m 행렬.

Request : 각 프로세스의 현재 요청을 표시하는 n ⅹ m 행렬.

Request[i, j] : 프로세스 Pi가 필요한 자원 수가 k 개라면 프로세스 Pi는 자원 형태 Rj의 자원을 k개 더 요청함.

남아있는 프로세스들에 대한 할당 가능 순서를 모두 찾음.

1단계 : Work과 Finish는 각각 길이가 m과 n인 벡터로, ‘Work := Available’로 초기화 함.

- (i = 1, 2, …, n)일 때 ‘Allocationi ≠ 0’이면 ‘Finish[i] := false’이고, 아니면 ‘Finish[i] := true’.

2단계 : 다음과 같은 조건을 만족하는 색인 i를 찾으며, 조건에 맞는 i가 없으면 4단계로 이동.

- Finish[i] = false, Requesti ≤ Work

3단계 : 다음이 일치하는지 여부를 판단하여 2단계로 이동.

- Work := Work + Allocationi

- Finish[i] := true

4단계 : Finish[i] = false라면, 1 ≤ i ≤ n인 범위에서 시스템과 프로세스 Pi는 교착상태임.

교착상태 탐지 알고리즘 예

P0에서 P4까지의 프로세스 5개와 자원 형태 3개, A, B, C를 가진 시스템이 있다 가정함.

자원 형태 A는 자원을 7개, 자원 형태 B는 2개, C는 6개를 가지고 있음.

t0 시간에 다음과 같은 자원 할당 상태가 된다 가정함.

대표

사진 설명을 입력하세요.

현재 시스템은 교착상태가 아니며, <P0, P2, P3, P1, P4>는 모든 i에 대하여 ‘Finish[i] = ture’임.

프로세스 P2가 자원 형태 C의 자원을 1개 더 요청한다 가정함.

Request 행렬은 다음과 같이 수정됨.

현재 시스템은 교착상태임.

프로세스 P0이 점유하고 있는 자원을 요청하더라도 가용한 자원 수는다른 프로세스들의 요청을 충족시킬 만큼 충분하지 않음.

따라서 프로세스 <P1, P2, P3, P4>로 구성된 교착상태가 존재함.

교착상태 탐지 알고리즘 사용 횟수

탐지 알고리즘 호출 문제는 교착상태 발생 빈도수와 교착상태 발생 시 영향을 받는 프로세스의 수에 따라 결정.

교착상태가 자주 발생하면 탐지 알고리즘도 자주 호출됨.

요청을 할 때마다 교착상태 탐지 알고리즘 호출 시 연산 시간 부담이 큼.

경제적인 방법은 호출 빈도를 줄이는 것으로, 한 시간마다 또는 CPU 이용률이 40%로 저하될 때마다 호출.