프로세스 1이 A라는 자원을 들고 있다.
프로세스 1은 B라는 자원을 원한다.
프로세스 2는 B라는 자원을 들고 있다.
프로세스 2은 A라는 자원을 원한다.
이 경우 두 프로세스는 영원히 기다려야 한다.
이러한 상태를 Deadlock(교착 상태)라고 한다.
데드락 발생 조건
데드락은 다음 4가지 조건을 모두 만족시켰을 때 발생한다.
Mutual Exclusion
매 순간 하나의 프로세스만 자원을 사용할 수 있다.
No Preemption
프로세스는 자원을 강탈당할 수 없다.
Hold and Wait
프로세스는 자원을 가진 채로 기다린다.
Circular wait
자원을 기다리는 프로세스 간에 사이클을 형성한다.
위의 데드락 예시는 4가지 조건을 모두 만족시킨다.
데드락 처리 방법
데드락을 처리하는 방식은 4가지가 있다.
Prevention
데드락을 아예 방지하는 방법이다.
데드락은 4가지 조건을 모두 만족시킬 때 발생한다.
즉, 이 중 1가지를 만족시키지 않으면 데드락은 발생하지 않는다.
-
Mutual Exclusion을 없앤다.
공유되서는 안되는 자원이 있다면 이 방식은 불가능하다. -
No Preemption을 없앤다.
프로세스가 자원을 빼앗아 올 수 있게 만든다. -
Hold and Wait을 없앤다.
프로세스가 자원을 기다리는 경우에는 가진 자원을 모두 반납하고 기다린다. -
Circular wait을 없앤다.
모든 자원을 정해진 순서대로 획득하게 한다.
위의 예시에서 항상 자원 A를 먼저 획득한 후 자원 B를 획득하도록 하면,
Circular wait은 발생하지 않는다.
Avoidance
데드락을 피하는 방법이다.
데드락이 발생하는 상황이 온다면, 자원을 할당하지 않는다.
데드락을 피하는 방법으로 Banker's Algorithm 이 있다.
Banker's Algorithm은 2가지 가정을 전제로 한다.
- 모든 프로세스의 최대 자원 사용량을 안다.
- 프로세스는 요청 자원을 할당받으면 유한시간 내에 반납한다.
이 가정을 바탕으로 전체 프로세스가 완료되는 순서가 존재한다면 자원을 할당한다.
현재 할당된 자원 최대 사용할 자원 현재 남아 있는 자원 필요로 하는 자원
A B C A B C A B C A B C
p1 0 1 0 7 5 3 3 3 2 7 4 3
p2 2 0 0 3 2 2 1 2 2
p3 3 0 2 9 0 2 6 0 0
p4 2 1 1 2 2 2 0 1 1
p5 0 0 2 4 3 3 4 3 1예를 들어 위와 같은 상황이 있다.
p1 ~ p5는 현재 자원을 할당받은 상태고, 최대 사용할 자원을 알고 있다.
필요로 하는 자원이란 '최대 사용할 자원 - 현재 할당받은 자원' 이다.
이 때 '남아 있는 자원'으로 '필요로 하는 자원'을 만족시키는 프로세스에 자원을 할당한다.
이 후 할당된 자원을 반납받고 나머지 프로세스에 대하여 반복한다.
이 때 p2, p4, p5, p3, p1와 같이 프로세스가 완료되는 순서가 존재하므로,
데드락이 발생하지 않는다고 판단한다.
Detection and Recovery
이 방식은 데드락을 예방하거나 피하지 않는다.
언제든지 데드락이 발생한다고 가정하고,
주기적으로 탐지하여 회복하는 방식이다.
데드락을 탐지하는 방법은 Banker's Algorithm과 유사하다.
차이점은 '최대 자원 사용량'을 요구하지 않고,
현재 요청을 만족시키면 할당된 자원을 반납받는 것을 전제로 한다.
요청된 자원을 할당하고 반납받으며 프로세스가 완료되는 순서가 존재한다면,
데드락이 발생하지 않았다고 판단한다.
만약 프로세스가 완료되는 순서가 존재하지 않는다면,
데드락이 발생했다고 판단하여 프로세스를 종료시킨다.
Ignorance
마지막은 그냥 데드락을 무시하는 방식이다.
'데드락에 빠져 멈춰있는 프로세스는 사용자가 알아서 종료시킨다'를 전제로 한다.
많은 범용 OS에서 사용하는 방식이다.
이러한 방식을 사용하는 이유는 다음과 같다.
-
위의 3가지 방식은 overhead가 크다.
-
데드락은 자주 발생하지 않는다.
낮은 확률에 대비하기 위해 큰 overhead를 감수할 필요는 없다.
