사나이들의 자강두천, 데드락 (DeadLock)

간단 요약

• 둘 이상의 프로세스가 특정 자원을 얻지 못해서 다음 명령을 처리 못하는 상태 (교착상태)
• 한정된 자원을 여러 곳에서 사용하려고 할 때 발생

데드락이 일어나는 경우

사진과 같이, 프로세스 1과 2가 자원 1, 2 를 모두 얻어서 작업을 수행해야하는 상황이다. 시간 순서대로 상황을 정리하자면 다음과 같다.

T1 : 프로세스 1이 자원 1을 얻고, 프로세스 2가 자원 2를 얻음
T2 : 프로세스 1이 자원 2를 기다리고, 프로세스 2는 자원 1을 기다림

그런데 이 때, 서로 요청한 자원은 이미 상대방에게 점유되어 있는 상황이 발생한다. 두 프로세스는 자원 1, 2를 모두 얻어야 작업이 마무리가 가능하기 때문에 무한정 자원을 기다리게 되는데, 이 상황을 바로 DeadLock 이라고 한다.

절대 자신이 갖고있는 자원은 내려놓을 생각 없이 끝까지 버티는 자강두천 그 자체이다.

주로 이런 상황에서 발생하곤 한다

• 멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황
• 한 프로세스가 자원을 요청했을 때, 갑자기 해당자원을 사용할 수 없는 상황이 발생
  → 이럴 때 해당 프로세스는 대기 상태로 들어감
• 대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 데드락 발생

발생 조건

데드락은 4가지 조건을 모두 만족해야 발생하게 되는데, 하나라도 조건을 만족하지 않으면 문제를 해결할 수 있는 상황이다. 그 조건들은 아래와 같다.

1. 상호 배제 (Mutual Exclusion)

자원은 한 번에 한 프로세스만 사용할 수 있음. 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 함.

2. 점유 대기 (Hold and wait)

최소한 하나의 자원을 점유한 채로 다른 프로세스에 할당되어 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함

3. 비선점 (No Preemption)

이미 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 뺏을 순 없음 (삥 뜯기 불가능)

4. 순환 대기 (Circular wait)

대기중인 프로세스 집합에서 순환 형태로 자원을 대기하고 있어야 함

데드락을 해결하는 방안

데드락 상황을 해결하기 위한 방안으로는 예방, 회피, 탐지, 회복 이렇게 4가지가 존재한다.

즉, 데드락이 발생하지 않도록 예방하거나, 발생 가능성을 인정하면서도 적절히 회피하거나, 데드락 발생을 완전히 허용하지만 데드락을 탐지하여 회복하는 방안이다.

예방 (Prevention)

데드락 발생 조건 중 하나를 제거하며 데드락을 예방하는 방법이다.

• 상호배제 부정 : 여러 프로세스가 공유 자원 사용 가능

• 점유대기 부정 : 프로세스 실행 전 모든 자원을 한 번에 요구하고 허용할 때까지 작업 보류
  → 나중에 또 다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 함
  → "진짜 이것만 필요한 거지? 나중에 딴 소리 하지마라.." 마인드
  

• 비선점 부정 : 자원을 점유 중인 높은 우선순위의 프로세스가 다른 자원 요구할 때 해당 자원 반납 (삥 뜯기)

• 순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구

하지만 이렇게 데드락을 예방하게 되면 시스템의 처리량이나 효율성은 떨어진다. 아래에서 소계하는 데드락 회피법은 예방법보단 조금 덜 제한적인 방법을 활용하여, 예방법의 단점을 일부 해결한다.

회피 (Avoidance)

데드락이 발생했을 때 피해나가는 방법이다. 데드락 회피법에서는 안정 상태 가 핵심 키워드이다.

프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례대로 모두에게 할당해줄 수 있는 상태라면 이것을 안정 상태 에 있다고 말한다.

그리고 이처럼, 특정한 순서로 프로세스들에게 자원을 할당하고 실행, 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면, 그것을 안전 순서 라고 부른다.

반대로 불안정 상태는 안정 상태가 아닌 상황을 이야기하는데, 즉 데드락이 발생할 수 있는 상황인 것이다.

데드락 회피법은, 자원을 할당한 후에도 시스템이 항상 안정 상태에 있을 수 있도록 할당을 허용하는 것이 기본 특징이다. 이러한 특징을 살린 대표적인 알고리즘으로 '은행원 알고리즘'이 있다.

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

• 킹갓스트라 (다익스트라) 형님이 고안한 알고리즘
• 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
• 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 데드락 회피
• 안정 상태라면 자원을 할당하고, 아니라면 다른 프로세스들이 자원을 해제할 때까지 대기

탐지 (Detection)

자원 할당 그래프를 통해 데드락을 탐지한다.
→ 자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생

회복 (Recovery)

위 탐지 기법에 따라 데드락을 발견했다면, 데드락을 일으킨 프로세스를 종료하거나, 할당된 자원을 반납하게끔 하여 데드락 상황을 해결하는 방법이다.

1. 프로세스 종료 방법

1. 데드락 발생한 프로세스 모두 정지
   → 연산중이던 프로세스들이 모두 중단되기 때문에 부분 연산 결과가 폐기될 수 있음

2. 데드락이 제거될 때까지 하나씩 프로세스 중지
   → 하나 중지시키고 탐지 알고리즘 돌리고, 하나 중지시키고 또 탐지 돌리고 ...
   → 데드락이 회복되는 시점까지 이를 반복하기 때문에 시스템적으로 고비용 작업임

2. 자원 선점 방법

• 데드락 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당
  → 해당 프로세스를 일시 정지시킴

• 우선 순위가 낮은 프로세스나, 수행 횟수가 적은 프로세스 위주로 프로세스 자원 선점