데드락 개념부터 예제, 해결방법까지

데드락(Deadlock)이란 교착 상태를 뜻하는데

여러 프로세스가 같은 리소스에 접근할 때 발생하게 된다

 

이게 뭐가 문제지 싶겠지만

A는 1,2을 사용해야 하고

B도 1,2을 사용해야 하는데

 

A가 먼저 들어와 1을 사용하고

그 다음으로 B가 들어와 2를 사용할 경우

서로 작업을 끝마치기 위해서는

각자가 들고 있는 값이 필요한데

 

이미 서로에게 물려있는 상태이므로

모두 멈추는 사태가 발생하게 되는데

위와 같은 원인으로

진행이 안되는 상태가 바로 데드락이 되겠다

 

데드락은 다음 4가지 조건이 '동시에' 만족할 때

일어나게 되는데

 

1. 상호 제외(Mutual Exclusion)

- 리소스당 하나의 프로세스만 사용 가능할 경우

 

2. 보류 및 대기(Hold and Wait)

- 프로세스가 하나의 리소스를 보유하면서

다른 리소스를 기다리고 있는 경우

 

3. 선점 없음(No Preemption)

프로세스가 리소스를 놓지 않는 한

해당 프로세스에서 리소스를 가져오지 못함

 

4. 순환 대기(Circular Wait)

여러 프로세스가 순환 형태로

서로가 종료되길 기다리고 있는 경우

 

이런 상황에 처하게 되면

강제로 프로세스 하나를 종료시키는 방법 외에는

방법이 없으므로

 

데드락을 최대한 피해야 하는데

방법으로는

교착 상태 예방(Prevention) 방법,

회피(Avoidance) 방법이 있다

 

교착 상태 예방방법

 

1. 상호 제외 제거

- 리소스를 여러 프로세스에서 쓸 수 있도록 공유

(프린터와 같은 리소스는 본질적으로 공유 불가능함에 유의)

 

2. 보류 및 대기 제거

- 프로세스 수행 전 필요한 모든 리소스를 미리 할당

(한 프로세스가 모두 끝날 때까지

나머지 리소스들이 대기하게 되어 사용률이 떨어짐)

 

- 타 프로세스들은 현재 리소스를 모두 할당 해제한 후

다시 리소스를 요청하게 되기 때문에

선점에 의해 순서가 계속 뒤로 밀려

리소스를 할당받지 못하는

기아(starvation) 상태에 처할 수 있음

 

3. 선점 없음 제거

- 우선순위가 더 높은 프로세스에서

동일한 리소스가 필요할 경우

타 프로세스의 리소스를 할당 해제하고

리소스를 선점시킴

 

4. 순환 대기 제거

- 각 리소스에 숫자를 할당한 뒤

프로세스별로 숫자를 올리거나 내려가면서

필요한 리소스 할당받아 수행

 

교착 상태 회피방법

 

은행원 알고리즘(Banker's Algorithm)

프로세스에서 리소스 요구 시

프로세스에 리소스를 할당한 후에도 이상이 없으면

리소스를 할당하고 그렇지 않으면 할당하지 않는다

 

은행원 알고리즘은 다음과 같은 정보가 필요한데

> 각 프로세스별로 필요한 최대 리소스

> 각 프로세스별로 현재 할당된 리소스

> 시스템에서 최대 가용 가능한 리소스

 

프로세스에서 위 정보들을 보내오면

 

프로세스에서 요청한 리소스가

최대 리소스 필요량보다 작을 경우

 

프로세스에서 요청한 리소스가

시스템에서 최대 지원 가능한 리소스보다

작은 경우일 경우에만 리소스를 보내주게 된다