데드락 (Deadlock) 의미 & 조건

데드락(Deadlock)이란?

멀티 프로그래밍 또는 멀티 스레드 환경에서는 여러 프로세스 또는 스레드가 한정된 자원을 동시에 사용하기 위해 항상 경쟁 상태에 놓여 있고 프로세스가 필요한 자원을 획득하지 못하고 영원히 자원을 기다리는 상태이다.

시스템 모델 설명

자원이란 CPU, 파일, 메모리, 락객체(세마포어나 뮤텍스 같은 Synchronize Object) 등등 컴퓨터 시스템에서 여러분이 사용할 수 있는 모든 것들을 총칭하는 추상적인 용어다. 

1. 요청(Request) : 프로세스가 특정 자원을 시스템에게 요청하면 시스템은 현재 이 자원이 사용 가능하다면 프로세스에게 할당 한다. 불가능하다면 자원이 사용 가능해 질 때까지 기다린다(Wait state).
2. 사용(Use) : 자원에 대한 허가가 떨어지면 프로세스는 자원을 사용 할 수 있다.
3. 해제(Release) : 프로세스는 자원의 사용이 끝나면 시스템에게 반환 요청을 한다. 

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

데드락(Deadlock)의 조건

• 상호 배제(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 파일이 좋은 예다. 파일에 변경이 없으니 여러 프로세스가 동시에 이 파일에 접근 가능하고, 이는 자원을 점유하기 위해 대기하는 프로세스가 없다는 뜻이다.

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

점유 대기란 프로세스가 자원을 소유한 상태에서 다른 추가 자원을 요청하기 때문에 발생한다. 여러 자원에 대해 일관성을 보장해야 하는 작업의 경우는 여러 자원을 동시에 접근하여 업데이트 해야만 하므로 이 방법을 적용 할 수 없다. 일관성을 보장하기 위한 방법으로는 마치 여러 자원들을 하나의 묶음 처럼 필요한 자원을 모두 한 번에 할당할 수도 있다. 하지만 이 방법 역시 당장 사용하지 않는 자원을 작업이 끝날때까지 불필요하게 점유하고 있을 수 있는 성능상 단점이 있다.

비선점 방지(Non Preemption Prevention)

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

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

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

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

순환 대기 방지(Circular Wait Prevention)

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

데드락 회피(Deadlock Avoidance)

데드락 회피 알고리즘들은 자원 요청 시 '추가 정보(알고리즘 마다 다름)'도 함께 요구한다. 그 '추가 정보'들을 바탕으로 현재 자원 할당 상태를 검사하여 순환 대기 상태가 발생하는 것을 원천적으로 막는다. 예를 들어 각 프로세스들은 작업을 완료하는데 필요한 최대 자원의 갯수를 시스템에게 알려주고, 시스템이 현재 자원 할당 상태를 보고 판단하여 각 프로세스들에게 자원을 순서대로 할당한다면, 프로세스들이 경쟁적으로 점유하는 동안 낭비되는 자원을 줄일 수 있어 보다 효율적일 수 있다.

안전 상태(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개를 반납한다.

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

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

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

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

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

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

자원 타입 하나당 여러개의 자원 인스턴스가 있어도 적용이 가능하다. 단, 인스턴스가 여러개인 자원타입에 대해서도 적용이 가능하다는 장점이 있지만, 아래와 같은 단점들도 있다.

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

그래서 일반 프로그래밍 영역 보다는 위 조건들이 맞는 OS 구현 레벨에서 제한적으로 사용된다.

은행원 알고리즘의 구현을 위해서는 다음과 같은 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 로 초기화 된다

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

1. 만일 모든 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

 

출처: https://kukuta.tistory.com/281 [HardCore in Programming:티스토리]