[ 운영체제 ] 데드락(Deadlock) 해결 방법

데드락은 운영체제 입장에서 정말 큰 문제다. 프로세스가 자원을 얻기 위해 영원히 대기하면서 심각한 자원 낭비가 발생하기 때문이다. 따라서 데드락을 제어하는 것은 중요한 이슈다. 데드락을 해결하는 방법은 크게 세 가지로 나뉜다.

1. 데드락에 빠지는 상황을 피하는 방법
---- Deadlock Prevention
---- Deadlock Avoidance

2.  데드락에 빠지면 다시 이전 돌아가는 방법
---- Deadlock Detection
---- Deadlock Recovery

3. 데드락 무시(Ostrich Algorithm)
---- 희박한 교착 상태에 대한 문제를 무시하는 방법

 

3번이 흥미롭다. 우리가 이렇게 데드락에 대해 열심히 배우지만 사실 대부분의 운영체제가 데드락을 무시하고 있다. 발생 확률이 매우 희박하고, 만에 하나 발생하더라도 그냥 껐다가 키는게 구현하는 것보다 비용 측면에서 이득이기 때문이다. 그래도 데드락에 대한 개념은 알아야 하기 때문에 다른 방법들이 어떤 원리로 동작하는지 이해하고 있어야 한다. 이제 하나씩 알아보자.

1. Deadlock Prevention

데드락의 네 가지 조건 중 하나만 어기면 된다는 개념이다. 조건을 하나씩 제거하면서 각 경우에 어떻게 되는지 살펴보자. 

1) No Mutual Esclusion

모든 프로세스가 자원을 동시에 사용할 수 있도록 하는 방법이다. 그런데 이러면 동기화가 불가능하게 된다. 동기화가 불가능하기 때문에 경쟁 상태가 발생할 것이고, 대환장 파티가 될 것이다. 이는 멀티프로그래밍을 포기하겠다는 말인데 현실적으로 말이 안 된다. 무엇보다 프린터와 같은 자원은 애초에 공유가 불가능하기 때문에 상호배제는 반드시 보장되어야 하는 조건이다. 

2) No Hold and Wait

프로세스가 필요한 모든 자원을 한 번에 요청하게 해서 데드락을 해결하는 방법이다. 만약에 우리가 파워포인트를 쓰고 있다고 가정해보자. 파워포인트의 모든 기능은 하나의 '자원'이다. 보통 파워포인트에서 사용하는 기능은 아주 일부분이기 상황에 따라 자원을 요청하는 것이 효율적일 것이다. '도형 만들기' 기능을 쓰다가 다른 기능이 필요하면 그때 가서 요청하면 된다. 그런데 Hold and Wait를 금지하면 도중에 새로운 자원을 요청할 수 없기 때문에 처음 프로그램을 실행할 때 파워포인트의 모~~든 기능을 다 요청해야 한다. 

 

어떤 문제가 발생할까? 우선 자원 분배의 효율성이 매우 떨어진다. 막말로 진짜 너무 무식한 방법이기 때문이다. 프로세스도 굉장히 무거워져서 속도가 엄청나게 느려질 것이다. 또한 기아현상(starvation)이 발생할 수 있다. 우리는 지금 한 가지 조건만 어기고 있으므로 상호배제 조건은 만족하는 상황이라는 것을 기억해야 한다. 따라서 자원의 공유가 불가능한 상황이다. No Hold and Wait이기 때문에 어떤 프로세스가 실행되기 위해서는 필요한 모든 자원을 한 번에 요청해야 한다. 과연 필요한 모든 자원이 free 한 상황이 일어나기는 할지 의문이다. 필요한 모든 자원 중 하나라도 다른 프로세스가 사용중이라면 프로세스는 실행되지 못하는데, 이러면 평생 실행되지 못하는 프로세스가 충분히 생길 수 있다. 

3) Allow Preemption

사실 선점의 허용은 데드락을 예방하는 가장 현실적인 방법이다. 식사하는 철학자 문제에서 포크를 강제로 뺏을 수 있게 하는 것과 같다. 포크를 강제로 뺏을 수 있게 되면 한 명이 식사를 할 수 있게 되고, 식사를 완료하면 포크를 내려놓기 때문에 다른 철학자가 식사를 할 수 있게 된다. 식사하는 철학자 문제가 뭔지 모르겠다면 여기서 확인하기 바란다. 그런데 선점의 허용은 아래와 같은 문제를 발생시킨다.

 

프로세스가 자원A를 요청하면 OS는 자원A를 사용하고 있는 프로세스가 있는지 살펴보기 위해 다른 자원을 block 시키는 문제가 발생하고, 자원을 뺏긴 프로세스는 대기하다가 다시 작업을 하려면 기존에 가지고 있던 old resource + 필요한 새로운 resource를 할당받아야 하는데 이 과정에서 starvation이 생길 수 있다. 만약에 이러한 문제를 해결했다고 해도 작업의 진행 상태를 저장하지 않는 자원의 경우 적용이 어렵다. 따라서 선점의 허용은 레지스터나 메모리와 같이 상태를 쉽게 저장하고 복원하는 자원에는 적용할 수 있지만 프린터와 같은 자원에는 적용할 수 없다. 

4) No Circular Wait

모든 자원에 우선순위를 두면 가능한 방법이다. 우선순위가 높은 자원을 요청하려면, 먼저 우선순위가 낮은 자원을 모두 해제해야 하는 조건이 있으면 데드락을 예방할 수 있다. 식사하는 철학자 문제로 예를 들어보자. 

북쪽에 앉은 철학자는 포크1을 집기 위해 우선 우선순위가 낮은 포크5를 내려놓아야 한다. 포크5를 내려놓으면 북동쪽에 앉은 철학자가 식사를 할 수 있게 되고 데드락은 풀리게 된다. 

 

가능은 하지만 현실적으로 매우 어려운 방법이다. 만약에 우선순위가 높은 자원을 할당받은 상태에서 우선순위가 낮은 자원을 요청하려면 우선순위가 높은 자원을 해제한 다음 우선순위가 낮은 자원을 요청하고 작업 완료 후 해제하고 다시 우선순위가 높은 자원을 요청해야 한다. 굉장히 복잡하다. 또한 새로운 자원이 유입될 경우 새로운 우선순위 번호를 부여해줘야 하는 번거로움도 있다. 

5) Deadlock Prevention의 결론

결론은 데드락을 '예방'하는 방법은 자원의 낭비가 극심하기 때문에 좋은 방법이 아니다.

2. Deadlock Avoidance

데드락 발생 가능성을 계속 검사해서 데드락 발생 가능성이 있다면 회피해버리는 방식이다. 즉, 데드락이 발생하지 않는 쪽으로만 실행시키는 방법이다. 데드락의 발생 가능성을 알기 위해서는 아래의 세 가지 정보와 한 가지 가정을 전제로 해야 한다. 

 

1. 각 자원의 가용 인스턴스 개수
2. 모든 프로세스마다 보유하고 있는 자원 개수
3. 모든 프로세스마다 필요한 자원의 총 개수

가정 : 프로세스는 필요한 자원을 모두 사용하고 한 번에 해제한다

 

예를 들어 프로세스 A가 현재 세 개의 자원을 사용하고 있고 필요한 자원의 총 개수가 다섯 개라면, 두 개의 자원을 추가로 할당받아야 다섯 개의 자원을 해제할 수 있다는 말이다. 

 

위 가정을 바탕으로 데드락 회피를 하기 위해 Safe State와 Unsate State라는 개념이 사용된다. 개념의 정의는 아래와 같다. 

 

Safe State : 데드락이 발생하지 않는 경우가 단 하나라도 있는 상태.
                      데드락이 없는 프로세스 실행 순서를 Safe Sequence라고 한다.

Unsafe State : 데드락에 빠질 가능성이 있는 상태 

 

위 개념에 따라 아래의 명제는 필요충분조건이 된다.

 

Safe Sequence가 하나라도 존재한다 ↔ 그 State는 Safe State이다

 

Safe Sequence

 

Safe State는 Safe Sequence가 존재하기 때문에 데드락이 항상 발생하지 않음을 알 수 있다. 좀전에 Deadlock Avoidance는 데드락 발생 가능성을 계속 검사해서 데드락 발생 가능성이 있다면 회피해버리는 방식이라고 했었다. Safe State만 유지하면 데드락에 빠지지 않음을 보장할 수 있기 때문에 Deadlock Avoidance의 핵심 아이디어는 계속해서 Safe State를 유지하는 것이다. Unsafe State로 가는 요구는 모두 거절한다. 

1) Safe State 예제

사용 가능한 자원은 12개
9개의 자원은 이미 할당, 가용 자원은 3개
세 개의 프로세스 존재 ( P0, P1, P2 )

프로세스(필요한 자원의 총 개수)
: P0(10), P1(5), P2(9)

프로세스(보유하고 있는 자원 개수)
: P0(5), P1(2), P2(2)

time = 0 일 때의 상황

위 상황이 Safe State인지, Unsafe State인지 판별해보자. 먼저 직접 해보기를 바란다. 정답은 아래 더보기란을 펼치면 된다. 

P1 → P0 → P2 순서로 자원을 할당하면 Safe Sequence

 

위와 같이 자원 배분을 P1 → P0 → P2 순서로 할당하면 Safe Sequence이기 때문에 위 시스템은 Safe State. 나머지 모든 요구는 Unsafe State이므로 데드락 회피 알고리즘에 따라 거부한다.

2) Resource Allocation Graph

데드락을 회피하기 위한 다른 방법으로 바로 이전 글에서 다뤘던 Resource Allocation Graph를 사용하는 방법이 있다. 노드와 간선의 정의는 이전 글과 동일한데 여기에 'Claim'이라는 간선만 추가된다. Claim Edge는 그래프에서 점선으로 표현된다. 만약에 프로세스가 자원 요청을 실제로 하면 Claim Edge는 Request Edge로 바뀌고, 프로세스가 자원을 해제하면 다시 Claim Edge로 바뀐다. 그러니깐 Claim Edge는 프로세스 상태가 Unsafe 상태로 가는지 안 가는지 검사하는 일종의 확인 절차라고 생각하면 된다. 

 

 

위와 같은 상황은 가정해보자. Claim Edge가 없으면 위 상태는 Safe한 상태다. 왜냐하면 P1이 R1을 해제하면 P2가 R1을 사용할 수 있기 때문이다. 그런데 Claim Edge를 고려하는 순간 위 상태는 어떤 요구를 취하냐 따라 Safe State 또는 Unsafe State로 갈 수 있다. 

 

가능한 두 가지 케이스

데드락 회피는 안전한 상태로만 가도록 하는 방법이기 때문에 위 예시의 경우 P2 → R2 요구는 기각되고 P1 → R2 요구를 수락하게 된다.

3) Banker's Algorithm

그래프 할당 방법은 자원의 인스턴스가 하나일 때만 사용 가능하다. 자원의 인스턴스가 두 개 이상이면 Banker's Algorithm을 사용해야 한다. Banker's Algorithm은 내용이 좀 길어서 따로 정리했다. 링크 바로가기! 자세히 정리했으니 보면 도움이 될 것이다. 

3. Deadlock Detection

데드락 탐지는 Deadlock Recovery와 세트로 움직인다. 기본적으로 아래 프로세스를 따른다.

 

1. Deadlock Detection 알고리즘으로 현재 시스템에 데드락이 있는지 찾는다
2. Deadlock Recovery 알고리즘으로 데드락 회복

 

Banker's Algorithm과 크게 다르지 않다. 차이점이라면 데드락 상태에 빠지냐 마냐 정도? Banker's Algorithm은 safety algorithm으로 요청이 유효한지 판단할 수 있으므로 데드락을 피할 수 있지만 데드락 탐지는 요청을 일단 하고 현재 시스템이 데드락에 빠졌는지 검사하는 알고리즘이다. 돌다리를 두둘겨 보는지, 일단 건너고 보는지 차이다. 

 

먼저 자원의 인스턴스가 하나일 때 사용하는 Wait-for-Graph에 대해 알아보자. 

Resource-Allocation Graph에서는 자원에 대해 소유하고 있는 상황도 표현했다면 Wait-for Graph에서는 단순히 프로세스끼리 자원을 반납하는 것을 기다리는 상황만을 표현한다. Single instance이기 때문에 Wait-for Graph에 cycle이 형성되어 있으면 데드락이다. 

 

인스턴스가 여러개 존재하는 경우 데드락 탐색 알고리즘을 사용해야 한다. Deadlock Detection Algorithm은 Banker's Algorithm의 Safety Algorithm과 매우 비슷하다. 알고리즘에서 1번과 4번만 다르다. 

 

n = 프로세스 개수
m = 자원 타입 개수

1. Work[m], Finish[n]
--- 초기화
--- Work[m] = Available[m]
--- if Allocation[i] != 0, Finish[i] = false (i = 0, 1, 2, ..., n-1) // 차이점 1
    // 할당된 자원이 없으면 Hold & Wait 위배, 따라서 Deadlock을 유발하지 않는 프로세스로 판단

2. 아래 두 조건을 만족하는 i 탐색
--- a) Finish[i] == false // 아직 덜 끝난 프로세스 찾음
--- b) Need_i <= Work // 가용 자원으로 P_i 끝낼 수 있는지 검사
-- i를 찾을 수 없으면 4번으로, i를 찾았으면 3번으로

3. 
- Work = Work + Allocation_i // P_i 완료시키고 자원 받음
- Finish[i] = true // P_i 완료 처리
- 2번으로

4.
- if Finish[i] = false, P_i는 Deadlock 상태 // 차이점 2

 

Safety Algorithm과 다른점은 주석에 표시해놨다. 현재 시스템에서 데드락의 원인이 되는 프로세스를 탐지하는 알고리즘으로 이해하면 된다. 어떤 시스템 내에서 하나의 프로세스가 데드락에 빠지면 그 시스템은 데드락에 빠진 것이기 때문이다. 

 

탐지 알고리즘을 언제 호출할지 결정하는 기준은 아래와 같다.

 

1. 데드락 발생 빈도수
2. 데드락이 발생했을 때 얼마나 많은 프로세스가 영향을 받는지(롤백해야 하는 프로세스 수)

4. Deadlock Recovery

데드락을 회복하는 방법에는 프로세스를 강제 종료시키는 방법과 자원을 선점하는 방법으로 크게 두 가지가 있다.

1) Process Termination

프로세스를 강제 종료시키는 방법이다. 이는 다시 두 가지로 나뉜다. 

 

1. 데드락의 원인이 되는 프로세스를 모두 종료
2. 한 번에 하나의 프로세스만 종료시키면서 데드락이 풀리는지 check (오버헤드 장난 아님)

 

실행중이던 프로세스를 강제로 종료시키는 것이기 때문에 위험하다. 따라서 어느 프로세스를 중지시킬 것인지 선택하는 요인이 몇 가지 있다. 그 중 6가지만 소개한다.

 

1) 프로세스 우선순위
2) 프로세스 수행 시간, 일을 끝마치기까지 남은 시간
3) 프로세스가 점유하고 있는 자원 타입과 양 (회복하기 쉬운 자원인지)
4) 프로세스가 종료하기까지 남은 자원의 수
5) 얼마나 많은 수의 프로세스를 같이 종료시켜야 하는지
6) 프로세스가 interactive 인지 bath 형태인지

2) Resource Preemption

프로세스의 자원을 선점하는 방법이다. 막말로 자원을 그냥 뺐는 방법. 세 가지 중요한 이슈가 있다. 

 

1. 희생 프로세스 선정
희생 비용을 최소화하기 위해 어느 프로세스의 어떤 자원을 뺐을지 결정해야 한다.

2. 롤백 (Rollback)
어떤 프로세스로부터 자원을 뺐어오면 자원이 뺐긴 프로세스는 나중에 safe state로 롤백하고 다시 재실행 해줘야 한다. 아니면 그냥 처음 상태로 되돌린다.

3. 기아 현상 (Starvation)
우선순위의 기준에 따라 희생 하는 놈만 계속 희생할 수 있다. 선점 횟수에 가중치를 부여해 선점이 많이 된 프로세스에게 우선권을 주는 방식으로 해결할 수 있다.