데드락(Deadlock) 개념 정리

데드락을 온 몸으로 표현하는 짤

오늘 다뤄볼 내용은 이름만 들어도 프로그래머의 가슴을 답답하게 만드는 '데드락(Deadlock)'이다.
이 포스트를 통해서 우리는 데드락의 기본 개념, 데드락 발생 조건, 데드락 탐지, 데드락 방지, 데드락 회피, 데드락에서 벗어나는 법을 알아 볼 것이다.

데드락(Deadlock)이란?

멀티 프로그래밍 환경 또는 멀티 스레드 환경에서는 여러 프로세스 또는 스레드가 한정된 자원을 동시에 사용하기 위해 항상 경쟁 상태에 놓여 있다. 이 때, 어떠한 이유로든 프로세스가 필요한 자원을 획득하지 못하고 영원히 자원을 기다리는 상태로 남아 있는 것을 데드락이라고 한다. 어떻게 보면 자원을 획득하지 못하고 있다는 점에서 기아상태(starvation state)와 비슷하지만 이것은 영원히 헤어 나올 수 없는 상태라는 점에서 차이가 있다.

※ 자원을 획득하기 위해 경쟁하는 주체는 프로세스, 스레드 등 여러 가지가 있지만 아래 부터는 설명의 편리를 위해 프로세스만 언급하도록 하겠다. 아래에서 프로세스라 언급 되면 자원 획득을 위해 경쟁하는 모든 개체라고 생각하면 된다. 

시스템 모델 설명

데드락을 이해하기 위해서는 컴퓨터 시스템에서 자원을 획득하는 과정을 먼저 알아야 한다. 이걸 알아야 나중에 설명 될 데드락 탐지와 회피 등의 고급 기술을 이해 할 수 있다. 여기서 자원이란 CPU, 파일, 메모리, 락객체(세마포어나 뮤텍스 같은 Synchronize Object) 등등 컴퓨터 시스템에서 여러분이 사용할 수 있는 모든 것들을 총칭하는 추상적인 용어다. 

1. 요청(Request) : 자원을 사용하기 위해서는 무엇보다도 가장 먼저 요청이 있어야 한다. 프로세스가 특정 자원을 시스템에게 요청하면 시스템은 현재 이 자원이 사용가능 한지 그렇지 않은지 판단 후, 사용 가능하다면 프로세스에게 할당 한다. 만일 자원이 다른 프로세스에 의해 이미 점유 되어 있는 경우 요청 프로세스는 자원이 사용 가능해 질 때까지 기다린다(Wait state).
2. 사용(Use) : 자원에 대한 허가가 떨어지면 프로세스는 자원을 사용 할 수 있다.
3. 해제(Release) : 프로세스는 자원의 사용이 끝나면 시스템에게 반환 요청을 한다. 시스템은 자원을 반환 받아 다른 필요한 프로세스가 있다면 해당 프로세스에게 할당해준다.

예를 들어 프로세스가 파일(자원)에 대한 권한을 획득하고 돌려주기 위해 open과 close 시스템 콜을 호출 한다던지, 메모리(자원)를 확보하고 해제하기 위해 allocate와 free를 호출하는 것과 같은 모든 행동들이 위에서 언급한 '요청 -> 사용 -> 해제' 과정에 속하는 것들이다. 

데드락은 특정 셋(set)에 속한 모든 프로세스가 '자원이 사용 가능해 질때까지 기다리는 상태', 즉, 대기 상태(wait state) 상태에서 빠져 나오지 못하는 상태를 말한다.

데드락(Deadlock)의 조건

위에서 데드락이란 프로세스가 대기 상태에 빠져 영원히 풀려나지 못하는 상태라고 이야기 했다. 그럼 어떻게 프로세스는 이런 데드락에 빠지게 되는 것일까?

이미지 출처 : https://www.youtube.com/watch?v=FVmwvZNQgt0

프로세스가 데드락에 빠지기 위해선 아래 네가지 조건이 모두 충족 되어야 한다. 아래 중 하나라도 충족하지 않는다면 데드락은 발생하지 않는다.

• 상호 배제(Mutual exclusion) : 프로세스는 최소한 하나의 공유 되지 않는 자원을 가지고 있어야 한다.
  공유 되지 않는 자원이란 한번에 딱 하나의 프로세스만이 소유 할 수 있는 자원을 말한다. 만일 이 자원이 어떤 프로세스에게 할당 되어 있는 중 다른 프로세스가 이 자원에 대한 요청(Request)를 한다면, 그 '다른' 프로세스는 현재 프로세스가 자원을 반환 할 때 까지 대기 상태에 있게 된다.
• 점유와 대기(Hold and wait) : 프로세스는 최소한 하나의 자원을 소유하고 있는 상태에서 다른 프로세스에 의해 소유 되어어 있는 추가 자원을 요청 해야 한다.
• 선점 불가(No preemption) : 자원을 획득함에 있어 우선권이 없다. 그 어떤 프로세스도 다른 프로세스가 소유하고 있는 자원을 강제로 뺏아 올 수 없다. 자원을 획득 할 수 있는 유일한 방법은 다른 어떤 프로세스도 해당 자원을 점유하고 있지 않을 때 뿐이다.
• 순환 대기(Circular wait) : 프로세스들이 상대방이 필요한 자원을 점유 한 상태로 상대방이 가지고 있는 자원을 요청하고 있는 상태다. 예를 들어 프로세스 P1, P2, P3..이 있다면 P1은 P2가 가지고 있는 자원이 해제 되길 기다리고, P2는 P3이 가진 자원, P3은 그 다음, 그 다음..과 같은 형식으로 가장 마지막의 프로세스 P_n가 다시 P1이 가진 자원을 요청하고 해제 되길 기다리는 형태가 아래 그림 처럼 하나의 순환 구조를 이룬다.
  

  

  누군가가 자원을 해제하길 기다리는 중

데드락이 발생하기 위해선 위 네가지 조건이 모두 만족 되어야 한다고 했다. 데드락에 빠지는 필요 조건이 네 가지나 된다고 하니 데드락 상태에 빠지는게 쉽지 않다 생각 되는가? 글쎄..그게 의외로 쉽게 모든 데드락 조건이 만족 된다. 예를 들어 서큘라 웨이트 상태, 그러니까 순환 대기 상태는 점유 대기 상태에서 발생하는 것 처럼 각 조건들이 확실한 개성을 가진 독립적 조건이 아니라 어느 정도 서로 겹쳐 있어서 한 가지 조건이 발생하면 다른 조건이 만들어 지기 쉽다.

※ 영어로 만들어진 개념을 한글로 쓰려니 어색하다. 어지간하면 상호 배제, 점유와 대기..이렇게 기억하지 말고 영어로 기억해두자.

자원 할당 그래프(Resource-Allocation Graph)

자원 할당 그래프란, 프로세스가 자원을 요청하고 자원이 프로세스에게 할당 되는 '방향성을 가진 그래프'로써, 데드락 발생 여부를 탐지 할 수 있는 그래프다. 뒤에 더 자세히 설명 되는 데드락 탐지와 방지등을 설명하기 위해 꼭 필요한 개념이니 주의 깊게 살펴 보도록 하자.

자원 할당 그래프(Resource-Allocaction Graph)

• 동그라미로 그려진 P1, P2, P3는 프로세스를 의미한다.
• 사각형으로 그려진 R1, R2, R3, R4는 자원 타입을 의미한다.
• 각 '자원 사각형' 안의 점들은 각 자원 타입이 할당 가능한 자원 인스턴스 갯수를 의미한다.
  ※ 여기서 언급 되는 자원들은 모두 상호 배제(Mutual exclusion). 즉, 여러 프로세스에 의해 공유 될 수 없는 자원들이라고 정의한다.
• P에서 부터 R로 그려진 파란 화살표^[각주:1]는 프로세스가 R타입의 자원을 '요청 중' 인것을 의미하는 '요청 화살표(request edge)'라고 하겠다. 파란색 화살표는 요청만 하고 아직 자원을 할당 받지 못한 상태로써 프로세스가 '대기 상태'에 있음을 의미한다.
• R에서 부터 P로 그려진 빨간 화살표는 자원이 프로세스에 '할당 되었음'을 의미 하는 '할당 화살표(assignment edge)'라고 하겠다. 

위 그래프를 살펴 보면 아래와 같다.

• P1은 R2의 자원을 점유하고 R1의 자원을 대기 중이다 - 점유 대기(Hold and wait)
• P2는 R1과 R2의 자원을 점유하고 R3의 자원을 대기 중이다 - 점유 대기(Hold and wait)
• P3은 R3의 자원을 가지고 있지만 아무런 추가 자원을 요청하지 않는다.

P1과 P2는 점유 대기 상태에 있지만 P3가 아무런 자원을 요청하지 않고 있으므로 순환 대기(Circular wait) 상태가 아니다. 그래서 위 상황은 데드락 상태가 아니다.

그럼 위의 그래프에 P3이 R2의 자원을 요청하는 것을 추가 해보자.

데드락 상태에 빠진 자원 할당 그래프

P3은 R2의 자원을 요청했으나 R2는 이미 할당 할 수 있는 자원을 모두 사용 했으므로, P3은 대기 상태에 빠지게 된다. 여기서 R2는 P2에게 할당 되었고, P2는 R3을 기다리고 있다. 하지만 R3은 이미 P3에게 할당 되어 있어 순환 대기 상태에 빠지게 되었다.

• P3 -> R2 -> P2 -> R3 -> P3
• P3 -> R2 -> P1 -> R1 -> P2 -> R3 -> P3

데드락이 발생 했다!!!!

데드락이라니!!!

반면, 아래의 그래프는 순환 대기 상태에 빠져 데드락인것 처럼 보이지만 사실 데드락은 아니다.

순환 대기 상태지만 데드락은 아닌 그래프

P1 -> R1 -> P2 -> R2 -> P1으로 얼핏 보면 순환대기 상태가 만들어졌다. 하지만 R1타입의 자원은 인스턴스가 두개고 하나는 점유 대기 상태에 빠져 있는 P2에게 점유되어 있지만, 다른 하나는 P3에게 점유되어 있다. P3에서 작업이 완료 되고 자원을 해제하면 P1에게 할당 될 수 있다. R2 타입의 자원 역시 마찬가지로 P4에서 작업이 완료 되고 자원을 해제하면 P2에게 할당 될 수 있으므로 순환 대기 상태가 아니다.

데드락 방지(Deadlock Prevention)

데드락 방지의 기본 개념의 출발은 간단하다(개념이 간단하다고 했지 적용이 쉽다고 하진 않았다). 위에서 데드락이 발생하기 위해서는 네가지 조건이 모두 만족 되어야 한다고 했다. 그렇다면 그 네가지 조건 중 한가지만이라도 발생하지 못하도록 막으면 되는것 아닌가?

상호 배제 방지(Mutual Exclusion Prevention)

상호 배제(mutual exclusion)이라는 것은 공유가 불가능한 자원을 소유하고 있는것을 말한다. 그렇다면 자원을 공유 가능하도록 만들면 데드락은 발생하지 않는다. Read-only 파일이 좋은 예다. 만일 업데이트가 필요 없는 파일이라면 read-only권한으로 자원을 점유 할 수 있다. 파일에 변경이 없으니 여러 프로세스가 동시에 이 파일에 접근 가능하고, 이는 자원을 점유하기 위해 대기하는 프로세스가 없다는 뜻이다. 이로써 상호 배제 조건이 만족하지 않으므로 데드락은 발생 할 수 없다.

하지만 업데이트가 필요한 파일과 같이 어떠한 이유로든 동시에 접근하는 것을 허용하지 못하는 자원의 경우 상호 배제 방지는 적용 할 수 없다.

점유 대기 방지(Hold and Wait Prevention)

점유 대기란 프로세스가 자원을 소유한 상태에서 다른 추가 자원을 요청기 때문에 발생한다. 만일 한 프로세스가 동시에 점유 할 수 있는 자원이 하나로 제한 된다면 다른 자원을 획득하기 위해서는 가지고 있는 자원을 해제 해야만 하기에 점유 대기 방지 상태는 발생하지 않는다.

하지만 여러 자원에 대해 일관성을 보장해야 하는 작업의 경우는 여러 자원을 동시에 접근하여 업데이트 해야만 하므로 이 방법을 적용 할 수 없다.

일관성을 보장하기 위한 방법으로는 마치 여러 자원들을 하나의 묶음 처럼 필요한 자원을 모두 한 번에 할당할 수도 있다. 하지만 이 방법 역시 당장 사용하지 않는 자원을 작업이 끝날때까지 불필요하게 점유하고 있을 수 있는 성능상 단점이 있다.

비선점 방지(Non Preemption Prevention)

비선점(Non-Preemption)이라는 것은 한번 점유된 자원은 반환 하기 전까지 다른 프로세스에 의해 점유 될 수 없다는 것이다.

첫번째 방법으로는, 어떤 자원을 이미 점유하고 있는 프로세스가 당장 할당 받을 수 없는 다른 추가 자원을 요청한다면 요청 프로세스가 가지고 있는 모든 자원들을 선점형으로 바꾸어 버리는 방법이 있다. 달리 말하면 요청 대기 상태에 빠지는 프로세스의 모든 자원을 암묵적으로 해제(Release)해버리는 것이다. 해제된 리소스들은 요청 대기 자원 리스트에 들어가고, 프로세스는 새로 요청한 자원과 이전에 가지고 있던 자원 모두를 획득 했을 때만 대기 상태에서 벗어나 작업을 다시 시작 할 수 있다.

다른 방법으로는, 프로세스가 자원을 요청하면

• 대상 자원이 현재 아무런 프로세스에게 할당 되어있지 않은지 확인 한다. 어떤 프로세스도 해당 자원을 점유하고 있지 않다면 요청 프로세스에게 자원을 할당 한다.
• 만일 대상 자원이 이미 다른 프로세스에게 할당 되어 있고, 그 다른 프로세스가 추가 자원을 대기 중이라면, 다른 프로세스로 부터 해당 자원을 빼앗아 요청 프로세스에게 할당 한다.
• 만일 대상 자원이 이미 다른 프로세스에 의해 사용 중이라면 요청 프로세스는 대기 상태로 빠진다.
• 이 상태에서 만일 다른 프로세스가 요청 프로세스가 가지고 있는 자원을 요구하면 그 자원을 해제하여 선점 가능하도록 변경한다.
• 요청 프로세스는 필요한 모든 자원이 할당 될때까지 대기 상태에 있는다.

순환 대기 방지(Circular Wait Prevention)

순환 대기 상태는 내가 필요한 자원을 다른 프로세스에서 선점하고 있고, 그 다른 프로세스가 필요한 자원을 내가 선점하고 있을 때 발생한다. 이를 방지하는 첫번째 방법은, 모든 프로세스가 획득 하는 자원의 순서를 동일하게 맞추는 것이다. 모든 자원마다 고유의 번호를 부여하고 필요한 자원을 번호가 작은 것 부터 큰 순서대로 획득하도록 한다면 추가로 필요한 자원들이 어떠한 프로세스에게도 점유 되어 있지 않음을 보장한다.

순환 대기 상태를 제거하기 위한 방법을 C++ 코드로 구현한 예제를 [여기]에 올려 놓았다. 실제 예제를 통해 이해를 높이도록 하자.

데드락 회피(Deadlock Avoidance)

데드락 회피

앞서 살펴본 데드락 방지(Deadlock Prevent)는 데드락 발생 조건 중의 하나를 제거하여 데드락이 발생하는 상황 자체를 막아 버린다. 이를 위해 프로세스는 당장 사용하지 않는 자원을 점유하고 있어야 하거나, 이미 할당 되었던 자원을 반납해야 하는 등의 전체 성능을 낮추어야 하는 단점이 있었다.

그에 대한 대안^[각주:2]으로 데드락 회피(Deadlock Avoidance)가 있다. 데드락 회피 알고리즘들은 자원 요청 시 '추가 정보(알고리즘 마다 다름)'도 함께 요구한다. 그 '추가 정보'들을 바탕으로 현재 자원 할당 상태를 검사하여 순환 대기 상태가 발생하는 것을 원천적으로 막는다.

예를 들어 각 프로세스들은 작업을 완료하는데 필요한 최대 자원의 갯수를 시스템에게 알려주고, 시스템이 현재 자원 할당 상태를 보고 판단하여 각 프로세스들에게 자원을 순서대로 할당한다면, 프로세스들이 경쟁적으로 점유하는 동안 낭비되는 자원을 줄일 수 있어 보다 효율적일 수 있다^[각주:3].

이번 장에서는 데드락 회피 알고리즘들을 살펴 보도록 한다.

안전 상태(Safe State)

데드락 회피 알고리즘들을 이해하기 위해서(특히, 뒤에 소개 될 은행원 알고리즘에서는 더욱!) 우리는 먼저 '안전 상태'에 대한 개념을 알아야 한다. '안전 상태'라는 것은 시스템이 각 프로세스들에게 데드락을 피할 수 있는 안전한 순서(saf sequence)로 자원을 배분 할 수 있는 상태를 의미한다. 예를 들어 시스템에 12개의 자원과 프로세스 P0, P1, P2 이렇게 3개가 있다고 가정하자. 프로세스는 자기가 맡은 작업을 처리하기 위해 아래와 같은 개수의 자원을 필요로 한다.

• P0은 작업을 마치기 위해 10개의 자원이 필요하다고 시스템에 요청했다.
• P1은 작업을 마치기 위해 4개의 자원이 필요하다고 시스템에 요청했다.
• P2는 작업을 마치기 위해 9개의 자원이 필요하다고 시스템에 요청했다.

이렇게 프로세스가 작업을 마치기 위해 총 몇개의 자원이 필요한지가 위에서 언급한 '자원 요청시 요구 되는 추가 정보'의 일종이다(이는 알고리즘 마다 다르다). 아뭏튼, 각 프로세스들이 작업을 마치기 위해 필요한 자원은 위와 같고 특정 시점 'T0'에서 시스템이 파악한 자원 할당 상태는 아래와 같다.

• P0은 지금 5개의 자원을 가지고 있다. 작업을 마치기 위해 5개의 자원이 더 필요 하다.
• P1은 지금 2개의 자원을 가지고 있다. 작업을 마치기 위해 2개의 자원이 더 필요 하다.
• P2은 지금 2개의 자원을 가지고 있다. 작업을 마치기 위해 7개의 자원이 더 필요 하다.
• 시스템에는 현재 12개의 자원 중 3개의 자원이 남아 있다.

이 상태에서 시스템은 P1 -> P0 -> P2 순서로 자원을 할당하여 안전 상태를 유지 할 수 있다. 

1. 시스템에는 3개의 여유 자원이 있다. P1이 필요 자원 2개를 할당 받아 작업을 처리하고 자신이 가진 자원 4개를 반납한다.
2. 시스템에는 5개의 여유 자원이 있다. P0이 필요 자원 5개를 할당 받아 작업을 처리하고 자신이 가진 자원 10개를 반납한다.
3. 시스템에는 10개의 여유 자원이 있다. P2이 필요 자원 7개를 할당 받아 작업을 처리하고 자신이 가진 자원 9개를 반납한다.

이로써 데드락 상황이 발생하지 않고 모든 프로세스들이 작업을 완료 했다. 이렇게 데드락 회피는 프로세스가 자원을 요청 할 때 마다 '안전 상태'를 유지 할 수 있을 경우에만 자원을 할당하고, 그렇지 않을 경우 프로세스를 기다리게 함으로써 데드락을 피해간다.

만일 시스템이 위와 다른 순서로 자원을 할당 한다고 하면 모든 프로세스들이 작업을 마치기 위한 자원을 제대로 할당 받지 못하는 경우가 발생할 수 있다. 이를 안전하지 않은 상태(Unsafe state)라고 하며 데드락이 발생할 가능성이 있는 상태다(안전하지 않은 상태라고 무조건 데드락이 발생하는 것은 아니다, 이에 대해서는 조금 뒤에 좀더 자세히 다룰 것이다). 

자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)

자원 타입 당 사용 할 수 있는 인스턴스가 하나일 경우 사용할 수 있는 알고리즘이다(대부분의 경우 자원 타입 당 사용 할 수 있는 인스턴스가 하나다). 위에서 우리는 '자원 할당 그래프'를 이미 살펴 보았다. 자원 할당 그래프 알고리즘의 경우 이전에 언급된 그래프 예제의 '요청 화살표(request edge)', '할당 화살표(assignment edge)'에 더하여 '클레임 화살표(claim edge)'^[각주:4]의 개념이 더 추가 된다. 클레임 화살표는 프로세스가 미래 언젠가 자원을 요청 할 수도 있다는 것을 나타낸다.

※ 이전 장 '안전 상태'에서 프로세스가 작업을 처리하기 위해 필요한 전체 자원의 수가 '요청 시 추가 요구 되는 정보'였다면, 이번 장 '자원 할당 그래프 알고리즘'에서는 클레임 화살표가 추가 요구 되는 정보다.

클레임 화살표는 프로세스가 실행 되기 전에 아래의 그래프 예제 처럼 자원 할당 그래프에 추가 되어져야 한다. 프로세스가 자원을 요청하면 클레임 화살표는 요청 화살표로 바뀌고(물론, 자원 할당이 되면 할당 화살표로 변경 된다), 프로세스에 의해 자원이 반환 될때 다시 클레임 화살표로 변경된다.

시스템은 위와 같은 그래프를 유지하며, 프로세스로 부터 자원에 대한 요청을 받으면 순환 대기 상태가 발생하지 않는 경우에만 자원을 할당 한다. 참고로 순환 대기 상태를 탐지하기 위해서는 써클 탐지(circle-detection) 알고리즘을 사용하며 이는 n² 복잡도를 가진다. 여기서 n은 프로세스 개수를 의미한다.

이해를 위해 위 그래프를 다시 살펴 보자. 위 예에서 프로세스P2가 자원 R2에 대한 요청을 한다면, 시스템은 현재 R2가 어떠한 프로세스에게 할당 되지 않은 상태라고 할지라도 P2에게 바로 할당해주지 않고, 대기 시킨다.

이유는 P1에서 R2로 그려져 있는 클레임 화살표 때문이다. 이는 언제든지 프로세스 P1이 R2의 자원을 요청 할 수 있다는 것을 의미하고,만일 그 시점이 P2가 R2를 할당 받고 난 후라면, P1이 자원을 추가 요청함으로써 순환 대기 상태가 발생한다. 시스템은 이를 막기 위해 애초에 P2의 요청을 거절해 버림으로써 데드락을 회피한다.

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

위에서 설명된 자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)의 경우는 각 자원 타입 마다 사용할 수 있는 인스턴스가 하나인 경우에만 적용 가능하다. 하지만 지금 부터 소개할 은행원 알고리즘은 자원 타입 하나당 여러개의 자원 인스턴스가 있어도 적용이 가능하다. 단, 인스턴스가 여러개인 자원타입에 대해서도 적용이 가능하다는 장점이 있지만, 아래와 같은 단점들도 있다.

• 할당 할 수 있는 자원의 수가 일정해야 함
• 시스템의 프로세스 갯수가 일정해야 함
• 불안전 상태 방지를 위해 자원 이용도가 낮음

그래서 일반 프로그래밍 영역 보다는 위 조건들이 맞는 OS 구현 레벨에서 제한적으로 사용된다. 하지만 공부는 공부고 알아둬서 손해 볼것은 없으니 가볍게라도 아래 항목들은 읽고 넘어가자.

은행원 알고리즘의 목적 역시 자원 할당 그래프 알고리즘과 마찬가지로 시스템이 각 프로세스에게 자원을 할당 할 때 데드락이 발생할 상황을 만들지 않도록 하는 것이다. 이를 위해 우리가 위에서 살펴본 '안전 상태(safe state)'와 '안전 하지 않은 상태(unsafe state)'의 개념을 이용하여 시스템이 프로세스에게 자원을 할당했을 때 안전 상태가 유지되는 경우만 자원을 할당하고 그렇지 않은 경우 프로세스는 자원 요청을 하지 않고 대기 하게 된다.

은행원 알고리즘의 구현을 위해서는 다음과 같은 4개의 자료구조가 필요하다.

• Available(가용자원) : 'Available[자원 타입 갯수]' 로 정의 되는 1차원 배열. 각 자원 타입 마다 현재 사용가능한 갯수를 저장한다. 만일 Avaiable[j] = k 라면, 자원 타입 Rj의 현재 사용 가능한 인스턴스가 k개라는 의미다
• Max(최대 요구 가능 자원) : 'Max[프로세스 갯수, 자원 타입 갯수]' 로 정의 되는 2차원 배열. 각 프로세스가 요구 할 수 있는 최대 자원 갯수를 나타낸다. 만일 Max[i, j] = k 라면, 프로세스 Pi는 Rj타입의 자원을 최대 k개 까지 요구 할 수 있다는 의미다.
• Allocation(현재 할당 자원) : 'Allocation[프로세스 갯수, 자원 타입 갯수]' 로 정의 되는 2차원 배열. 각 프로세스 별 현재 할당 되어 있는 자원 갯수를 나타낸다. 만일 Allocation[i, j] = k 라면, 프로세스 Pi에게 Rj타입의 자원이 k개 할당 되어 있다는 의미다.
• Need(필요 자원) : 'Need[프로세스 갯수, 자원 타입 갯수]' 로 정의 되는 2차원 배열. 각 프로세스 별 작업을 완료하기 위해 추가로 필요한 자원 갯수를 나타낸다. 만일 Need[i, j] = k 라면, 프로세스 Pi가 작업을 완료하기 위해서는 Rj타입의 자원이 k개 더 필요하다는 의미다.

안전 상태 판단 알고리즘(Safety Algorithm)

현재 시스템의 상태가 안전 상태인지 그렇지 않은지 판단하기 위해서 아래와 같은 프로세스를 따른다. 설명의 편의를 위해 자원을 갯수를 m, 프로세스의 갯수를 n, 배열의 인덱스 i는 1부터 2, 3, .... n까지 순차 증가하는 for문의 인덱스라고 정의한다.

1. Work[m], Finish[n]. 이렇게 두개의 1차원 배열이 있다.
   알고리즘이 시작 되면 Work := Available로, Finish[i] := false 로 초기화 된다

2. 각 프로세스가 아래의 두 조건에 해당하는지 검사한다.
   • Finish[i] = false
   • Need_i <= Work
   조건에 부합한다면 3번으로, 만일 조건에 부합하는 i가 하나도 없다면 4번으로
3. Work := Work + Allocation_i
   Finish[i] := true
   2번 과정으로 이동

4. 만일 모든 Finish[i]가 true면 현재 상태는 안전한 상태다.

위 알고리즘은 안전 상태를 결정하기 위해 m x n² 만큼의 오퍼레이션이 필요 할 수 있다.

자원 요청 알고리즘(Resource-Request Algorithm)

아래는 임의 프로세스 P_i의 자원 요청 Request_i가 이루어 지는 과정을 설명한 것이다.

1. 만일 요청 자원이 필요 자원이 보다 작거나 같다면(Request_i <= Need_i) 2번 과정으로 이동. 그렇지 않다면 프로세스 최대 필요 자원양 보다 많이 요청한 것이므로 에러를 발생 시킨다.
2. 만일 요청 자원이 가용 자원이 보다 작거나 같다면(Request_i <= Available) 3번 과정으로 이동. 그렇지 않다면 현재 가용 자원이 부족한 상태이므로 P_i는 대기한다.
3. 아래와 같이 '자원 할당 상태'를 수정하여 시스템이 요청된 리소르를 할당한 척 하도록 한다.
   Available := Available - Request_i
   Allocationi := Allocationi + Requesti
   Needi := Needi - Requesti

3번 과정에서 '할당한 척'이라고 표현한 이유는 아직 시스템은 프로세스에게 자원을 할당한 상태는 아니고, 이렇게 자원을 할당해도 안전 상태가 유지되는지를 확인하기 위해 '자원 할당 상태'만 업데이트 했기 때문이다.

3번 과정까지 진행 한 후 이전 장에서 살펴본 안전 상태 판단 알고리즘을 이용해, 현재 상태가 '안전 상태'인 경우라면 드디어 시스템은 프로세스에게 자원을 할당해주고 트랜잭션을 완료 한다. 하지만 안전 상태가 아닌 경우 프로세스 P_i는 자원을 요청 할 수 있는 상태가 될때 까지 대기하며, '자원 할당 상태'는 이전 상태로 복구 된다.

은행원 알고리즘의 구현에 관련된 자세한 사항은 지면상 관계 [여기]에 따로 정리 했다. 위의 슈도 코드만으로는 이해가 가지 않는 부분이 많을것 같아 실제 코드를 통해 예제를 만들어 놓았으니 살펴 보길 바란다.

이상 데드락의 정의와 발생 조건, 데드락 방지, 데드락 회피의 개념과 방법에 대해 알아 보았다. 이어지는 포스트로는 데드락 탐지, 복구 방법을 다루도록 하겠다. 이 포스트가 도움이 되었다면 좋아요와 짧은 댓글 하나 정도 남겨 주면 다음 포스트를 쓰는데 큰 힘이 될 것이다. 그럼 이만.

부록 1. 같이 보면 좋은 글

• [C++] 데드락 방지 락 가드(deadlock free lock guard)
• 데드락 회피 - 은행원 알고리즘

---

1. 방향성 간선이라고 표현할까 하다 너무 말이 어려워 화살표를 사용함 [본문으로]
2. 사실 필자의 본심을 쓰자면 운영 체제 관점이나 알고리즘 관점에서 보았을 때야 방지와 회피가 다를 수 있지만 사용자 입장에서 보면 '방지'나 '회피'나 데드락 상황을 만들지 않도록 억제한다는 개념인 관점으로는 차이가 없어 보인다. 혹시 데드락 개념을 처음 공부하시는 분들은 방지와 회피의 차이가 뭐지? 라고 너무 고민의 늪에 빠져 공부하는 시간을 낭비 하시기 보다는 둘다 데드락 상태가 발생하지 않도록 하는 도구라는 것에 집중하셨으면 한다.
   다만 방금 말했듯이 방지와 회피는 확실히 차이가 있다. 방지의 경우 read-only, 선점 같은 OS에서 제공하는 시스템 속성을 이용하는 하고, 자원을 몰아서 가져가거나, 순서대로 자원에 접근하는 등의 프로세스 입장에서 경쟁을 해야 하지만, 회피의 경우는 은행원 알고리즘, 자원 할당 그래프 알고리즘들을 이용해 시스템에서 애초에 데드락이 발생하지 안도록 자원을 배분해 준다는 것이다.
   지극히 개인적 사설이라 혹시 이 글을 읽으시는 분들의 개념 형성에 나쁜 영향을 줄까봐 걱정되어 첨언을 할까 말까 많이 고민 했지만 중요하지 않은 부분에 시간을 너무 낭비 할까 걱정되어 사족을 남긴다. 그냥 잡설 정도로 치부하고 넘어가셔도 된다. [본문으로]
3. 어쩌면 상태 판단에 들어가는 비용이 더 클 수도 있다 [본문으로]
4. claim을 한글로 번역하면 request와 너무 비슷해서 어쩔수 없이 영어 그대로 읽기로 했다 [본문으로]