[OS] 데드락 (Deadlock , 교착 상태)

데드락(Deadlock, 교착 상태)란 ?

운영체제에서 데드락(교착상태)이란, 시스템 자원에 대한 요구가 뒤엉킨 상태로 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한대기에 빠지는 상황을 말한다.

 

데드락 발생 조건

• 상호 배제(Mutual Exclusion) : 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다.
• 점유 대기(Hold and Wait) : 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
• 비선점(Non-Preemption) : 이미 할당된 자원을 강제로 빼앗을 수 없다.
• 순환 대기(Circular Wait) : 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

 

데드락 해결 방법

• 데드락이 발생하지 않도록 예방(Prevention)
• 데드락 발생 가능성을 인정하면서 적절히 회피(Avoidance)
• 데드락 발생을 허용하지만 데드락을 탐지 및 발견(Detection)하여 데드락 회복(Recovery)

 

💡 데드락 예방(Prevention)

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

 

상호 배제 방지: 한 번에 여러 프로세스가 자원 공유

점유 대기 방지: 프로세스 실행에 필요한 자원을 한꺼번에 요구 

비선점 방지 : 높은 우선순위 프로세스가 자원을 선점할 수 있도록 함

순환 대기 방지 : 순환 형태가 아닌 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 함

 

 

--> 시스템의 처리량이나 효율성을 떨어뜨리는 단점이 발생할 수 있다.

 

 

💡 데드락 회피(Avoidance)

데드락 회피법에는 Safe Sequence , Safe State 등이 키워드이다.

 

시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서 차례로 모두 할당해 줄 수 있다면 안정 상태(safe state)에 있다고 한다.

 

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

 

회피 알고리즘은 자원을 할당한 후에도 시스템이 항상 Safe State에 있을 수 있도록 할당을 허용하자는 것이 기본 특징이다. 이러한 특징일 살린 알고리즘으로 유명한 것이 은행원 알고리즘 이다.

 

 

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

은행원 알고리즘(Banker's Algorithm)
: 어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시물레이션 해서 Safe State에 들 수 있는지 여부를 검사한다.

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

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

P0~P2는 프로세스이고, Max는 각 프로세스마다 최대 자원 요청량, Allocation은 현재 프로세스에 할당 중인 자원의 양, Need는 남은 필요한 자원의 양(Max-Allocation)이다.

 

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

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

 

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

 

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

 

만약 여기서 P2프로세스가 처음에 자원을 하나 더 할당받고 있었다면 (2개가 아니라 3개) 운영체제가 가지고 있는 Available 자원은 12 - (5+2+3) = 2개로 프로세스를 해결할 수 있는 방법이 존재하지 않는다.

 

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

 

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

 

 

💡 데드락 탐지(Detection) 및 회복 (Recovery)

먼저 시스템이 데드락 예방이나 회피법을 사용하지 않으면 데드락이 발생할 수 있으니 회복하기 위해 데드락을 탐지하고 회복하는 알고리즘을 사용한다.

 

탐지 기법 

• Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색 (은행원 알고리즘과 비슷)

 

회복 기법

• 데드락을 탐지 기법을 통해 발견했다면, 순환 대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용 
• 단순히 프로세스 1개 이상 중단시키기
  • 교착 상태에 빠진 모든 프로세스를 중단 시키는 방법 : 계속 연산중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있는 부작용이 발생할 수 있음
  • 프로세스를 하나씩 중단 시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법 : 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있음
• 자원 선점하기
  • 프로세스에 할당된 자원을 선점하여 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해 주는 방법

---

 

참고 자료

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

[운영체제] 데드락(Deadlock, 교착 상태)이란?