교착상태 deadlock, 자원할당

학습목표

1. 교착상태의 개념을 설명할 수 있다.

2. 교착상태가 발생하기 위한 필요조건을 설명할 수 있다.

3. 자원할당 그래프의 개념을 설명할 수 있다.

4. 교착상태를 방지하는 기법을 설명할 수 있다

5. 교착상태르로 회피하는 기법을 설명할 수 있다.

6. 교착상태를 탐지하고 복구하는 방법을 설명할 수 있다.

 

주용용어

교착상태, 점유대기, 환형대기, 안전 순서열, 은행원 알고리즘

 

5.1 교착상태의 개념

 > 2개 이상의 프로세스가 서로 상대방의 작업이 끝나기만을 기다리고 있는 상태

 > 결과적으로 아무도 완료되지 못함 

참고 : 교착상태와 기아상태는 의미가 다르다.

 

교착상태 : 관련된 모든 프로세스가 무한히 대기상태인 것

(해소될 가능성이 없다)

 

기아상태 : 프로세스가 일부가 지속적으로 대기상태인 것

(해소될 가능성이 있다.)

 

 

5.2 교착상태의 특성

5.2.1 교착상태의 필요조건

네 가지 조건이 동시에 만족될 경우 교착상태가 발생할 수 있음

- 상호배제 조건

- 점유 대기 조건

- 비선점 조건

- 환형 대기 조건

(1) 상호배제 조건 - 프로세스들의 자원에 대한 배타적인 통제권을 요구 - 적어도 하나 이상의 자원은 공동 사용 될 수 없음 - 즉, 필요로 하는 자원을 다른 프로세스가 점유하고 있으면 반드시 대기해야함
(2) 점유 대기 조건 - 프로세스가 이미 다른 자원을 할당받아 배타적으로 점유하고 있는 상황에서 다른 프로세스가 점유하고 있는 자원이 해제되기를 기다리는 상황
(3) 비선점 조건 - 프로세스에 할당된 자원은 그 프로세스가 사용을 마치고 스스로 반환하기 전에 제거되지 않음   - 즉, 다른 프로세스에 의해서 해제되지 않음
(4) 환형 대기 조건 - 프로세스의 자원 점유 및 점유된 자원의 요구 관계가 환형을 이루며 대기

 

5.2.2 자원할당 그래프

교착상태를 명확하게 표현하기 위해 자원할당 그래프를 이용할 수 있다.

자원 할당 (resource allocation) 그래프 G = ( V, E) 란 방향(directed) 그래프이다.

 

 

자원 할당 그래프 G = ( V, E)

V : 정점의 집합. V = P ∪ R 

P = { P1, P2,........., Pn} : n개의 프로세스

R = { r1,r2, ........., rm} : m개의 자원

 

 

E : 방향 있는 간선의 집합. E = Q ∪ S

Q = { (pi, rj) : pi ∈ P, rj ∈ R } : 프로세스 pi가 자원 rj를 요구함 (요구간선)

S = { (rj, pi) : rj ∈ P, pi ∈ R } : 자원 rj가 프로세스 pi에 할당되어 있음 (할당간선)