[운영체제] DeadLock (데드락)

✔︎ DeadLock (데드락)이란 ?

프로세스가 원하는 자원을 얻지 못해 다음 작업 처리를 하지 못하는 상태를 말한다.

'교착 상태'라고 부르며 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다.

 

발생 상황

• 멀티 프로그래밍 환경에서 한정된 자원을 사용하기 위해 서로 경쟁하는 상황에서 발생 가능
• 어떤 프로세스가 자원을 요청했을 때에 그 자원을 사용할 수 없는 상황이 발생할 수 있다. 이 때, 프로세스가 대기 상태로 들어가게 된다. 
• 대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 '교착 상태' 발생 

 

✔︎ DeadLock 발생 조건

발생 조건 4가지가 모두 성립해야 데드락이 발생하며 하나라도 성립하지 않으면 해결 가능하다.

 

1. 상호 배제 (Mutual exclusion)

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

 

2. 점유 대기 (Hold and Wait)

최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 한다. 

 

3. 비선점 (No preemption)

다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음 

 

4. 순환 대기(Circular wait)

대기 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 한다.

 

 

✔︎ DeadLock 해결 방법

해결 방법	특징
예방	교착 상태를 유발하는 4가지 조건 중 하나를 제거하면서 해결한다.  자원 낭비가 심하다는 단점이 있다.
회피	교착 상태가 발생 조건을 없애는 것 보다는 애초에 교착 상태가 발생하지 않도록 알고리즘을 적용하는 방법이다.
검출	탐지 알고리즘 및 자원 할당 그래프를 사용해 교착 상태를 발견한다. 교착 상태가 탐지 되었다면 복구 기법을 통해 교착 상태를 복구한다. 이 방식은 지속적으로 확인하는 작업이 필요하기 때문에 성능 저하가 발생한다.
회복	교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시킨다.

 

1. 교착 상태 예방

교착 상태가 발생하기 위한 4가지 조건 중 하나를 제거한다.

 

상호 배제 예방 : 독점적으로 사용할 수 있는 자원을 없앤다. 즉 시스템 내의 모든 자원을 공유할 수 있다면 교착 상태는 발생하지 않는다.

비선점 예방 : 모든 자원을 빼앗을 수 있도록 만든다.

점유와 대기 예방 : 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 한다.

원형 대기 예방 : 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는다. 

 

2. 교착 상태 회피

프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지를 파악하고 그 수준 이하로 자원을 나누어 주는 방법이다. 미리 할당되는 자원의 수를 조절하여 교착 상태를 피하는 것을 의미한다.

교착 상태 예방은 프로세스 작업 방식을 제한하지만 운영 방식에 변경을 가하지 않기 때문에 좀 더 유연하다.

교착 상태 회피는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태(safe state)와 불안정 상태(unsafe state)로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다.

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

이를 구현하는 방법 중 은행원 알고리즘이 있다. 

 

 

 

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

은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래함
프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사해 교착 상태 회피
안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해제할 때까지 대기 

예를 들어 처음에 시스템 총 12개의 자원을 가지고 있다고 가정해보자. 

(t=t0)	Max	Allocation	Need	Available
P0	10	5	5
P1	4	2	2
P2	9	2	7

P0-2는 프로세스

Max는 각 프로세스마다 최대 자원 요청량

Allocation은 현재 프로세스에 할당 중인 자원의 양 

Need는 남은 필요한 자원의 양(Max-Allocation)이다. 

 

t0일 때 프로세스에 할당된 자원은 합은 5+2+2 = 9개이다. 따라서 현재 Available 자원은 12 - 9 = 3개이다.

여기서 Safe sequence를 찾아보려고 하면 순서가 <P1, P0, P2> 일 때 안전 순서를 만족한다.

 

1. P1은 2개가 이미 할당되어 있고 2개를 추가적으로 할당받기를 (Need) 기다리고 있다. 
2. 현재 Available 자원은 3개이므로, 이 중에 2개를 P1에게 할당한다. => 현재 Available은 3 - 2 = 1개
3. 실행이 끝난 P1은 자신에게 할당되어 있던 자원 4개를 모두 반납한다. => 현재 Available은 1 + 4 = 5개
4. 현재 Available 자원이 5개이고, 이를 P0에게 모두 할당해 주면 P0도 실행 가능해진다. => 현재 Available은 5 - 5 = 0개 가 됩니다.
5. 실행이 끝난 P0은 자신에게 할당되어 있던 자원 10개를 모두 반납한다. => 현재 Available은 0 + 10 = 10개
6. 마지막으로 P2에게 자원 7개를 할당해준다. => 현재 Available은 10 - 7 = 3개
7. 실행이 끝난 P2는 자신에게 할당되어 있던 자원 9개를 모두 반납한다. => 현재 Available은 3 + 9 = 12개

 

이렇게 자원의 부족함 없이 올바르게 할당하여 모든 프로세스가 실행을 할 수 있다.

만약 여기에서 P2 프로세스가 처음에 자원을 하나 더 할당받고 있었다면(즉, 2개가 아니라 3개) 운영체제가 가지고 있는 Available 자원은 12 - (5+2+3) = 2개 였을 것이다. 

이 상황에서는 처음에 P1에게 2개를 모두 주고, P1이 실행이 끝나고 자원을 모두 반납해도 Available 자원은 2 + 2 = 4개 뿐이므로, 이 자원으로는 나머지 P0이나 P2 프로세스를 해결해 줄 수 없다. (모두 4개보다 많은 양의 자원을 필요로 하고 있으므로)

따라서 P0, P2는 자원을 할당받기를 계속 기다려야 할 것이다.

 

운영체제가 사전에 P2 프로세스가 자원을 하나 더 요청했을 때 할당해 주지 않고, P1이 먼저 끝나게 한다면 데드락이 발생하지 않았을 것이다. 그러므로 은행원 알고리즘을 사용해서 자원 할당량을 사전에 파악하고 데드락을 회피할 수 있도록 하면 될 것이다.

 

그러나 은행원 알고리즘의 경우, 이처럼 미리 최대 자원 요구량을 알아야 하고, 할당할 수 있는 자원 수가 일정해야 하는 등 사용에 있어 제약조건이 많고, 그에 따른 자원 이용도 하락 등 단점도 존재한다.

 

• 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 함
• 시스템의 전체 자원 수가 고정적이어야 함
• 자원이 낭비됨 

 

 

3. 교착 상태 검출

교착 상태 예방은 어렵고 교착 상태 회피는 구현할 수 있지만 자원을 낭비한다.

그래서 가장 현실적인 방법은 교착 상태 검출을 하는 방법이다. 

운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방법이다. 교착 상태를 검출하면 교착 상태 회복 단계를 밟는다. 

• 타임아웃을 이용한 교착 상태 검출 : 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주
• 자원 할당 그래프를 이용한 교착 상태 검출 : 자원 할당 그래프를 이용해 교착 상태 발견 
• Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색한다.

 

 

4. 교착 상태 회복 

교착 상태를 검출하고 회복하는 단계이다. 이때 교착 상태를 유발한 프로세스를 강제로 종료한다.

• 교착 상태를 일으킨 모든 프로세스를 동시에 종료
• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료 

이때 강제 종료하는 일 뿐만 아니라 강제 종료된 프로세스가 실행되기 전에 시스템을 복구하는 일도 해야 한다. 

시스템 복구는 명령어가 실행될 때 체크포인트를 만들어 가장 최근 시점으로 돌아가는데 이 작업량이 상당해 무분별하게 사용하면 안되고 선택적으로 사용해야 한다.

 

자원 선점 방법

• 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당 (해당 프로세스 일시정지 시킴)
• 우선 순위가 낮은 프로세스나 수행 횟수가 적은 프로세스 위주로 프로세스 자원 선점 

 

 

✔︎ 식사하는 철학자들 문제

다섯 명의 철학자가 원탁에 앉아있고, 각자의 앞에는 스파게티가 있고 양옆에 포크가 하나씩 있다.

그리고 각각의 철학자는 다른 철학자에게 말을 할 수 없다. 

이때 철학자가 스파게티를 먹기 위해서는 양 옆의 포크를 동시에 들어야 한다. 

이 때 각각의 철학자가 왼쪽의 포크를 들고 그 다음 오른쪽의 포크를 들어서 스파게티를 먹는 알고리즘을 가지고 있으면, 다섯 철학자는 동시에 왼쪽의 포크를 들 수 있으나 오른쪽의 포크는 이미 누군가가 가졌기 때문에 다섯 명 모두가 무한정 서로를 기다리는 교착 상태에 빠질 수 있다. 

 

해결 방법

1. 누군가는 왼쪽 포크를 먼저 집지 않고 오른쪽 포크를 먼저 집어 해결하는 방식 (교착 상태 예방 방식)

에츠허르 데이크스트라의 해결책은 다음과 같다.

각각의 철학자를 P1, P2, P3, P4, P5라고 하고, 각 철학자의 왼쪽 포크를 F1, F2, F3, F4, F5라고 하자 

P5를 제외한 네 명은 먼저 Fn을 집은 후 Fn+1 을 집는 방식을 취한다.

그리고 P5는 이와 반대로 F1(P5의 오른쪽 포크)를 먼저 집은 후 F5를 집는다.

이것은 원래 방식의 대칭성을 제거하고 따라서 교착 상태를 막을 수 있다. 

 

2. 한 철학자가 포크 두개를 모두 집을 수 있는 상황에서만 포크를 집도록 허용 (교착 상태 회피 방식으로 해결)

 

3. n명이 앉을 수 있는 테이블에서 n-1 명만 앉힘 (교착 상태 예방 방식으로 해결)

 

 

참고 

https://ardor-dev.tistory.com/44

https://chanhuiseok.github.io/posts/cs-2/