운영체제 Deadlock (발생 원인, 조건, Mutual exclusion, Hold and wait, Circular wait )

Deadlock

 

Deadlock이란 이미 다른 프로세스에 할당된 resource를 얻기 위해 다른 프로세스들이 대기하는데 이 대기시간이 무제한일 때를 의미한다. 

 

간단한 예를 들어보자,

- resource1과 resource2는 하나의 프로세스에게만 할당될 수 있다. 

- 각각 프로세스1과 프로세스2는 자원 1과 자원 2가 있어야 동작할 수 있다. 

- 프로세스1은 resource1을 가지고 있다.

- 프로세스2는 resource2를 가지고 있다.

 

이런 상황을 deadlock이라고 한다. 즉 교착상태로 이러지도 저러지도 못하는 상황이다. resource1을 얻기 위해선 프로세스 1이 내놔야 하는데 그러기 위해선 resource2가 필요하고 프로세스2도 마찬가지다.

 

 

 

프로세스는 resource을 3단계로 처리한다.

1. request

- 말 그대로 요청하는 것이다. 이 resource는 이용 가능해야 한다.

2. use

- 이용 가능한 resource를 얻으면 hold 하고 있는 상태다. 즉 자원을 쓰고 있다.

3. release

- 다 쓴 자원을 내놓는다.

 

 

Deadlock 조건

 

Deadlock은 어떤 조건에서 실행될까?? 4가지 조건을 만족하면 Deadlcok에 걸린다. 이중에 하나라도 해당하지 않으면 deadlock에 걸리지 않는다.

 

1. Mutual exclusion :

- 하나의 resource에는 하나의 프로세스만 할당할 수 있다.

 

2. Hold and wait :

- 프로세스가 이미 resource를 가지고 있고 다른 프로세스가 보유한 resource가 필요하다면 기다린다.

 

3. No preemption :

- 이미 할당된 자원은 다른 프로세스에 의해 회수될 수 없다.

 

4. Circular wait :

- P0가 필요한 resource는 P1가 가지고 있고 P1이 필요한 resource는 P2가 가지고 있고... 이런 식으로 다른 프로세스에 의해 자원이 결정되는 상태를 말한다. 위에서 원그림을 그리는 현상이다. 

 

Graph로 나타낼 수 있는데 Resource Allocation Graph라고 부른다.

아래 3가지 경우에 그래프가 있다. 하나하나 보자

 

Deadlock 왼쪽부터 No Yes No

 

T는 task로 프로세스와 혼용하여 사용한다.

검은색 점은 instance다. 

회색 박스가 resource다.

 

예를 들면, GPU가 회색 박스고 검은 점이 GPU 개수 같은 느낌이다. GPU가 하나의 프로세스만 구동할 수 있다고 가정하고, 내 컴퓨터에는 GPU가 2개 있다고 하면 resource는 GPU지만 돌릴 수 있는 instance는 2개다.

 

그래프로 보자, 위에 그림 순으로 나타냈다.

Deadlock??	No	Yes	No
Mutual exclusion	R1, R2, R3, R4	R1, R2, R3, R4	R1, R2
Hold and wait	T1, T2	T1, T2, T3	T1, T3
No preemption	assuming yes	assuming yes	assuming yes
Circular wait	No	Yes	Yes

 

3번째 그림을 보면 Circular wait가 성립하지만 Deadlock은 아니다. 꼭 Circular wait가 성립한다고 해서 deadlock은 아니다. 하지만 성립하지 않는다면 무조건 deadlock이 아니다.