데드락

March 17th, 2021

데드락이란?

흔히 말하는 교착상태라고 하며, 프로세스 A가 자원 C를 사용하고 있는 도중 프로세스 B가 사용하고 있는 자원 D 사용을 요청한다. 이 때 프로세스 B가 자원 C 사용을 요청할 때, 즉 서로가 서로의 자원을 요청할 때 데드락이 발생한다.

데드락의 발생 조건

데드락의 교착 상태는 하나의 시스템 내 다음 네가지 조건이 동시 성립 할 때 발생한다.

상호 배제 :
- 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.
점유 대기 :
- 자원을 최소한 하나 보유하고, 다른 프로세스에 할당한 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
비선점 :
- 이미 할당된 자원을 강제로 빼앗을 수 없다.
순환대기 :
- 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

데드락 해결 방법

데드락은 크게 3가지 방법으로 해결 할 수 있다.

데드락이 발생하지 않도록 예방(prevention)하기
데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance)하기
데드락 발생을 허용하지만 데드락을 탐지(detection)하여 데드락에서 회복하기

그럼 위 세가지 방법에 대해 하나하나씩 알아보도록 하자.

데드락 예방

데드락의 발생 조건 4가지 중 하나라도 발생하지 않게 하는 것이 데드락을 예방하는 방법이다. 즉, 각각의 조건을 방지(부정)해 데드락 발생 가능성을 차단한다.

자원의 상호 배제 방지 : 한 번에 여러 프로세스가 공유 자원을 사용 할 수 있게 한다.
- 동기화 관련 이슈 발생 가능
점유 대기 조건 방지 : 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때 까지 작업을 보류해서, 나중에 또다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 한다.
비선점 조건 방지 : 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 할 때, 높은 우선순위의 프로세스가 해당 자원을 선점 할 수있도록 한다.
순환 대기 조건 방지 : 자원을 순환형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구 할 수 있도록 한다.

이러한 조건을 방지하여 데드락을 예방할 경우, 자원의 낭비가 심하고 시스템 처리량이나 효율성을 떨어트리는 단점이 발생 할 수 있다.

데드락 회피

프로세스가 요청하는 모든 자원에 대해 데드락이 빠질 가능성이 있는지 OS가 검사하고, 빠질 가능성이 없을 경우에만 자원을 할당하는 방법이다. 대표 기법으로는 은행원 알고리즘이 있다.

은행원 알고리즘

다익스트라가 제안한 방법으로, 어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전에, 미리 결정된 모든 자원들의 최대 가능 할당량을 가지고 시뮬레이션하여 Safe State에 들 수 있는지를 검사한다. 즉 대기중인 다른 프로세스들의 활동에 대한 교착 상태 가능성을 미리 조사하는 것이다.

처음에 시스템이 12개의 자원을 가지고 있다고 가정해보자.

(t=t0)	Max	Allocation	Need
p0	10	5	5
p1	4	2	2
p2	9	2	7

여기서 po~p2는 프로세스이고, Max는 각 프로세스별 최대 자원 요청량, Allocation은 현재 프로세스에 할당 중인 자원의 양, Need는 남은 필요한 자원의 양이다.
현재 t0일 때, 프로세스에 할당된 자원의 합은 5+2+2 = 9이다. 따라서, 시스템의 남은 잉여 자원은 12-9 = 3이다. 여기서 우리는 Safe Sequence를 찾아볼 것이다.

p1은 이미 2개가 할당되어있고, 2개를 추가 할당되기를 기다리고 있다. 현재 잉여 자원은 3개이기에, 3개중 2개를 p1에게 할당한다. => 잉여 자원은 3-2 = 1개
실행이 끝난 p1은 자신에게 할당되어 있던 자원 모두 반납한다. => **잉여 자원은 1 + 4 =5개 **
현재 자원이 5개이고, 이를 p0에게 할당하면 실행 가능한 것을 확인 할 수 있다. => 잉여자원은 5-5 =0개
실행이 끝난 p0은 자신에게 할당된 자원 10개를 모두 반납한다. => 잉여 자원은 10개
마지막으로 p2에게 자원을 할당한다. => 잉여 자원은 10 - 7 = 3개
실행이 끝난 p2는 자원을 돌려준다. => 잉여 자원은 3 + 9 = 12개

이렇게 자원의 부족함 없이 모든 프로세스가 실행 할 수 있는 것을 볼 수 있다. 만일, 여기서 p2의 초기 자원 할당(allocation) 값이 3이었다면, Safe Sequence에 도달 할 수 없다. 이렇게 자원 할당량을 사전 파악하고 데드락을 회피할 수 있도록 하는 것이 은행원 알고리즘의 핵심이다.

하지만 이런 은행원 알고리즘도 단점이 존재하는데,

할당할 수 있는 자원의 수가 일정해야 한다
사용자 수가 일정해야 한다
항상 불안전 상태를 방지해야 하므로 자원 이용도가 낮다
최대 자원 요구량을 알아야 한다
프로세스는 유한한 시간 내 자원을 반납해야 한다.

즉, 알고리즘도 너무 복잡하고, 프로세스가 시작 할 때 가지고 있어야 할 자원의 최대 개수를 사전에 파악해야 하기 때문에 실제 프로그램에 적용하기 힘들다. 오버헤드도 크기 때문에 자주 쓰이고 있지는 않다.

데드락 탐지 및 회복

시스템이 데드락 예방 혹은 회피법을 사용하지 않을 경우, 데드락이 발생 할 수 있다. 여기서 회복하기 위해 데드락을 탐지하고, 회복하는 알고리즘을 사용한다.

탐지 기법
- Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색한다..즉, 은행원 알고리즘에서 했던 방식과 유사하게 현 시스템의 자원 할당 상태를 파악한다.
- 자원 할당 그래프를 통해 탐지하는 방법도 있다.
회복 기법 : 순환대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용한다.
- 단순히 프로세스를 1개 이상 중단시키기
  - 교착 상태에 빠진 모든 프로세스 중단 : 연산중이던 프로세스도 일시 중단되어 부분 결과과 폐기 될 수 있음
  - 프로세스를 하나씩 중단 시킬때마다 탐지 알고리즘으로 데드락 탐지하여 회복 : 매번 탐지 알고리즘을 수행해야 하므로 오버헤드가 발생함
- 자원 선점하기
  - 프로세스에 할당된 자원을 선점해서, 교착 상태를 해결할 때 까지 그 자원을 다른 프로세스에 할당해주는 방법