Deadlock이란?
대기 중인 스레드들이 그들이 요청한 자원들이 다른 스레드들에 의해서 점유되어 있고 그들도 다 대기 상태에 있기 때문에 결코 다시는 그 상태를 변경시킬 수 없는 상태를 말한다.
쉽게 말해, 두 기차가 교차로에서 서로 접근할 때 둘 다 완전히 정지해야 하며 상대방이 없어지지 않는 한 누구도 다시 출발할 수 없는 상태와 같다.

8.1 System Model

시스템은 유한한 수의 자원들로 구성되어 있고, 이것은 경쟁하는 스레드들 사이에 분배되어야 한다. 이들 자원은 다수의 유형으로 분할되며, 이들 각각은 동등한 다수의 인스턴스들로 구성된다. 만일 한 스레드가 어떤 자원 유형의 한 인스턴스를 요청하면, 동일 유형 자원의 임의의 인스턴스를 할당함으로써 요청이 충족된다.

스레드는 자원을 사용하기 전에 반드시 요청해야 하고, 사용 후에는 반드시 방출해야 한다. 스레드는 지정된 task를 수행하기 위해 필요한 만큼의 자원을 요청할 수 있다. 명백히 요청된 자원의 수는 시스템에서 사용 가능한 전체 자원의 수를 초과해서는 안된다.

정상적인 작동 모드 하에서, 프로세스는 다음 순서로만 자원을 사용할 수 있다.

1. Request(요청) : 스레드는 자원을 요청한다. 요청이 즉시 허용되지 않으면, 요청 스레드는 자원을 얻을 때까지 대기해야 한다.
2. Use(사용) : 스레드는 자원에 대해 작업을 수행할 수 있다.
3. Release(방출) : 스레드가 자원을 방출한다.

자원의 요청과 방출은 시스템 콜이고, 그런 예들로는 장치의 request()와 release(), 파일의 open()과 close(), 그리고 allocate()와 free(), 세마포의 획득과 방출은 세마포에 대한 wait()와 signal(), mutex lock의 획득과 방출은 acquire()와 release() 등이 있다.

8.2 Deadlock in Multithread Applications

deadlock 상태 문제를 식별하고 관리하는 방법을 알아보기 전에, 먼저 POSIX mutex 락을 사용하여 다중 스레드 Pthread 프로그램에서 어떻게 deadlock 상태가 발생할 수 있는지 설명하고자 한다.

• pthread_mutex_init() 함수는 가용한 mutex를 초기화한다.
• mutex 락은 각각 pthread_mutex_lock()과 pthread_mutex_unlock() 함수를 이용하여 획득되고 방출된다.
• 한 스레드가 잠긴 mutex 락을 획득하려고 시도하면, pthread_mutext_lock() 함수 호출은 mutex 락의 소유주가 pthread_mutext_unlock() 함수를 호출할 때까지 이 스레드를 block한다.

두 스레드(thread_one과 thread_two)가 생성되고 두 스레드는 mutex 락에 대한 접근 권한을 가진다.

위의 예시 코드에서 thread_one은 (1) first_mutex, (2) second_mutex 순서로 mutex 락을 획득하려고 하고 동시에 thread_two는 (1) second_mutex, (2) first_mutex 순서로 mutex 락을 획득하려고 한다.

thread_one이 first_mutex를 획득하고 thread_two가 second_mutex를 획득하게 되면 deadlock 상태가 가능하다. deadlock 상태가 가능하더라도 thread_two가 락을 획득하려고 시도하기 전에 thread_one이 first_mutex와 second_mutex를 획득하고 방출할 수 있다면 deadlock 상태가 발생하지 않는다.

8.2.1 Livelock

livelock이란?
또 다른 형태의 라이브니스 장애로, deadlock 상태와 유사하다.

livelock과 deadlock 둘 다 두 개 이상의 스레드가 진행되는 것을 방해하지만 진행할 수 없는 이유가 서로 다르다. deadlock 상태가 어떤 스레드 집합의 모든 스레드가 같은 집합에 속한 다른 스레드에 의해서만 발생할 수 있는 이벤트를 기다리면서 block되는 반면에, livelock은 스레드가 실패한 행동을 계속해서 시도할 때 발생한다.

livelock의 가장 쉬운 예시로, 두 사람이 복도를 지나가려고 할 때 한 사람은 오른쪽으로 움직이고 다른 한 사람은 왼쪽으로 움직이면서 계속 서로의 진행을 방해하는 상황을 들 수 있다. (block 되진 않았지만 앞으로 진행될 수 없는 상황)

8.3 Deadlock Characterization

deadlock 상태를 특징 짓는 조건을 자세히 살펴보자.

8.3.1 Necessary Conditions

1. Mutual Exclusion (상호 배제)
: 최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 비공유 모드에서는 한 번에 한 스레드만이 그 자원을 사용할 수 있다. 다른 스레드가 그 자원을 요청하면, 요청 스레드는 자원이 방출될 때까지 반드시 지연되어야 한다.
2. Hold-and-Wait (점유하며 대기)
: 스레드는 최소한 하나의 자원을 점유한 채, 현재 다른 스레드에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다.
3. No Preemption (비선점)
: 자원들을 선점할 수 없어야 한다. 즉, 자원이 강제적으로 방출될 수 없고, 점유하고 있는 스레드가 태스크를 종료한 후 그 스레드에 의해 자발적으로만 방출될 수 있다.
4. Circular Wait (순환 대기)
: 대기하고 있는 스레드의 집합 {T_0, T_1, T_2 ,,,, T_n}에서 T_0는 T_1이 점유한 자원을 대기하고, T_1은 T_2가 점유한 자원을 대기하고 ,,, T_n-1은 T_n이 점유한 자원을 대기하며, T_n은 T_0가 점유한 자원을 대기한다.

8.3.2 Resource-Allocation Graph

deadlock 상태는 시스템 자원 할당 그래프라고 하는 방향 그래프로 더욱 정확하게 기술할 수 있다.

이 그래프는 vertex V의 집합과 edge E의 집합으로 구성된다.
V의 집합은 시스템 내의 모든 활성 스레드의 집합인 T = {T_1, T_2, ,,,, , T_n} (원으로 표현)과 시스템 내의 모든 자원 유형의 집합인 R = {R_1, R_2, ,,, , R_n} (사각형으로 표현)의 두 가지 유형으로 구별된다.

• Request edge (요청 간선)
  : 스레드 T_i로부터 자원 유형 R_j로의 방향 간선(directed edge)는 T_i -> R_j로 표현하며, 이건은 스레드 T_i가 자원 유형 R_j의 인스턴스를 하나 요청하는 것으로 현재 이 자원을 기다리는 상태이다.

• Assignment edge (할당 간선)
  : 자원 유형 R_j로부터 스레드 T_j로의 방향 간선은 R_j -> T_i로 표현하며, 이것은 자원 유형 R_j의 한 인스턴스가 스레드 T_i에 할당된 것을 의미한다.

할당 간선은 반드시 사각형 안의 하나의 점을 지정해야 하지만, 요청 간선은 사각형 R_j만을 가리킨다는 것에 유의하자.

스레드 T_i가 자원 유형 R_j의 한 인스턴스를 요청하면, 요청 간선이 자원 할당 그래프 안에 삽입된다. 이 요청이 만족할 수 있으면, 요청 간선은 즉시 할당 간선으로 변환된다. 스레드가 자원에 대한 접근을 더 해야 하지 않으면 자원을 방출하고 할당 간선은 삭제된다.

자원 할당 그래프에서 cycle을 포함하지 않으면 시스템 내 어느 스레드도 deadlock 상태가 아니다. 반면, 그래프가 cycle을 포함하면 deadlock 상태가 존재할 수 있다. (가능성이 있다는 것, 100% 존재가 아님)

8.4 Methods for Handling Deadlocks

원칙적으로 deadlock 문제를 처리하는 데는 다음과 같은 세 가지 방법이 있다.

• 문제를 무시한다. (Ignore)
• 시스템이 결코 deadlock 상태가 되지 않도록 보장하기 위해 deadlock 상태를 예방하거나 회피하는 프로토콜을 사용한다. (deadlock prevention & deadlock avoidance)
• 시스템이 교착 상태가 되도록 허용한 다음에 복구시킨다.

첫 번쨰 해결안인 Ignore은 Linux와 Windows를 포함해 대부분의 운영체제가 사용하는 방법이다.
(deadlock 상태가 자주 발생하지 않고, deadlock 상태를 무시하는 것이 다른 처리 방법과 비교했을 때 비용이 적게 들어서)

8.5 Deadlock Prevention

deadlock이 발생하려면 네 가지의 필요조건 각각이 성립해야 한다. 이들 조건 중에서 최소한 하나가 성립하지 않도록 보장함으로써, deadlock 발생을 예방할 수 있다. 이들 네 가지 조건을 각각 별도로 검토함으로써 이 접근 방식을 구체화해보자

8.5.1 Mutual Exclusion

상호 배제 조건이 성립되어야 한다. 즉 적어도 하나의 자원은 공유가 불가능한 자원이어야 한다. 반면에 공유 가능한 자원들은 배타적인 접근을 요구하지 않으며, 따라서 deadlock 상태에 관련될 수 없다. 읽기 전용 파일이 공유 가능한 자원의 좋은 예이다.

8.5.2 Hold and Wait

시스템에서 점유하며 대기 조건이 발생하지 않도록 하려면 스레드가 자원을 요청할 때마다 다른 자원을 보유하지 않도록 보장해야 한다. 우리가 사용할 수 있는 하나의 프로토콜은 각 스레드가 실행을 시작하기 전에 모든 자원을 요청하고 할당해야 한다.

8.5.3 No preemption

이미 할당된 자원이 선점되지 않아야 한다. 이 조건이 성립되지 않을 것을 보장하기 위해, 다음의 프로토콜을 사용할 수 있다. 만일 어떤 자원을 점유하고 있는 스레드가 즉시 할당할 수 없는 다른 자원을 요청하면(즉, 스레드가 반드시 대기해야 하면), 현재 점유하고 있는 모든 자원이 선점된다. 즉, 이들 자원들이 묵시적으로 방출된다. 선점된 자원들은 그 스레드가 기다리고 있는 자원들의 리스트에 추가된다. 스레드는 자신이 요청하고 있는 새로운 자원은 물론 이미 점유했던 옛 자원들을 다시 획득할 수 있을 때만 다시 시작될 것이다.

8.5.4 Circular wait

위의 세 가지 조건은 대부분 상황에서 일반적으로 실용적이지 않다. 이 조건은 필요한 조건 중 하나를 무효화해서 실용적인 해결책을 제공할 수 있도록 한다. circular wait가 성립되지 않도록 하는 한 가지 방법은 모든 자원 유형을 정렬해서 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요구하도록 하는 것이다.

8.6 Deadlock Avoidance

deadlock prevention의 부수적인 문제점은 장치의 이용률이 저하되고 시스템의 throughoutput(총처리율)이 감소한다는 것이다. 다른 방법으로는 자원이 어떻게 요청될 것인지에 대한 추가 정보를 제공하도록 요구하는 것이다.

이 방법을 사용하는 다양한 알고리즘들은 필요한 정보의 양과 유형에서 차이가 있다. 가장 단순하고 제일 유용한 모델은 각 스레드가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구하는 것이다.

deadlock avoidance 알고리즘은 시스템에 circular wait 상황이 발생하지 않도록 자원 할당 상태를 검사한다. 자원 할당 상태는 가용 자원의 수, 할당된 자원의 수, 그리고 스레드들의 최대 요구 수에 의해 정의된다.

8.6.1 Safe State

시스템 상태가 safe 하다는 말은 시스템이 어떤 순서로든 스레드들이 요청하는 모든 자원을 (최대 요구 수를 요구하더라도) deadlock을 일으키지 않고 차례로 모두 할당해 줄 수 있다는 것을 뜻한다. 즉, 시스템이 safe sequence (안전 순서)를 찾을 수 있다면 시스템은 safe 하다고 한다.

반대로, 모든 스레드를 무사히 마칠 수 있는 sequence를 찾을 수 없다면 unsafe 하다고 한다.

시스템의 상태가 safe 하다면 물론 deadlock 상태가 아니다. 반대로 deadlock 상태에 있는 시스템은 unsafe 상태에 있다. 그렇지만 시스템 상태가 unsafe 하다고 해서 반드시 deadlock 상태로 간다는 것을 뜻하는 것은 결코 아니다. 시스템이 unsafe 하다는 말은 앞으로 deadlock 상태로 가게 될 수도 있다는 뜻이다.

8.6.2 Resource-Allocation Graph Algorithm

만약 각 자원 유형마다 단지 하나의 인스턴스를 갖는 자원 할당 시스템을 갖고 있다면, 우리는 deadlock 상태를 피하기 위해 8.3.2절에서 정의한 자원 할당 그래프의 변형을 사용할 수 있다.

요청 간선과 할당 간선에 예약 간선(claim edge) 이라는 새로운 타입의 간선을 도입한다.

• Claim edge (예약 간선)
  : 예약 간선 T_i -> R_j 는 P_i가 미래에 자원 R_j를 요청할 것이라는 의미이다. 이 간선의 방향은 요청 간선과 유사하지만 점선으로 표시한다. 프로세스 T_i가 자원 R_j를 요청하면, 예약 간선 T_i -> R_j는 요청 간선으로 변환된다. 마찬가지로 T_i가 자원 R_j를 방출할 때, 할당 간선 R_j -> T_i는 예약 간선 T_i -> R_j로 다시 변환된다.

T_2가 R_2를 요청한다고 가정하자. R_2가 현재는 가용 상태이지만, 우리는 이를 T_2에 할당할 수 없다. 할당할 경우, 그래프에 사이클이 생기기 때문이다. 사이클은 시스템이 unsafe한 상태에 있음을 의미한다. 만일 T_1이 R_2를 요청하고 T_2가 R_1을 요청하면 deadlock 상태가 발생한다.

8.6.3 Banker's Algorithm

이 알고리즘의 이름이 이렇게 붙여진 이유는,, 이 알고리즘을 은행에 적용하면 고객들이 현금을 찾으러 와도 일정한 순서에 의해 모든 고객의 요청을 다 들어줄 수 있게 되기 때문이다.

이 시스템에서는 스레드가 시작할 때 스레드가 가지고 있어야 할 최대 개수를 자원 종류마다 미리 신고해야 한다. 물론 이 숫자가 자원의 총 보유 수를 넘어서면 안된다. 스레드가 자원들을 요청하면 시스템은 그것을 들어주었을 때 시스템이 계속 safe 상태에 머무르게 되는지 여부를 판단해야 한다. 계속 safe 상태라면 그 요청을 들어주고, 그렇지 않다면 이 스레드의 요청은 허락되지 않은 채 다른 스레드가 끝날 때까지 기다리게 된다.

Banker's Algorithm을 구현하려면 몇 가지의 자료구조가 필요하다. 이 자료구조들은 시스템이 자원을 할당하고 있는 상태를 나타내게 된다. n이 스레드 수이고, m이 자원의 종류 수라고 하자.

• Available : 각 종류별로 가용한 자원의 개수를 나타내는 벡터로 크기가 m이다. Available[j] = k라면 현재 R_j를 k개 사용할 수 있다는 뜻이다.
• Max : 각 스레드가 최대로 필요로 하는 자원의 개수를 나타내는 행렬로 크기가 nxm이다. Max[i][j] = k라면 스레드 T_i가 R_j를 최대 k까지 요청할 수 있음을 의미한다.
• Allocation : 각 스레드에 현재 할당된 자원의 개수를 나타내는 행렬로 크기가 nxm이다. Allocation[i][j] = k라면 현재 스레드 T_i가 R_j를 k개 사용 중임을 뜻한다.
• Need : 각 스레드가 향후 요청할 수 있는 자원의 개수를 나타내는 행렬로 크기가 nxm이다. Need[i][j] = k라면 스레드 T_i가 향후 R_j를 k개까지 더 요청할 수 있음을 뜻한다. Need[i][j] = Max[i][j] - Allocation[i][j] 관계가 있음을 알 수 있다.

8.6.3.1 Safety Algorithm

8.6.3.2 Resource-Request Algorithm

8.7 Deadlock Detection

만일 시스템이 deadlock prevetion이나 deadlock avoidance 알고리즘을 사용하지 않는다면, deadlock 상태가 발생할 수 있으므로 다음 알고리즘들을 반드시 지원해야 한다.

• deadlock이 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘
• deadlock 상태로부터 회복하는 알고리즘

8.7.1 Single Instance of Each Resource Type

모든 자원이 한 개의 인스턴스만 있다면 wait-for graph (대기 그래프)라고 하는, 자원 할당 그래프의 변형을 사용해 deadlock 상태 탐지 알고리즘을 정의할 수 있다.

wait-for graph에서 T_i에서 T_j로의 간선은 프로세스 T_j가 가지고 있는 자원들에 대해 프로세스 T_i가 그 자원이 필요하여 방출하기를 기다리는 것이다. 간선 T_i -> T_j는 해당 자원 할당 그래프가 자원 R_q에 대해 두 개의 간선 T_i -> R_q와 R_q -> T_j를 포함하는 경우에만 wait-for graph에 존재한다.

앞에서와 마찬가지로, wait-for graph에 사이클이 존재하는 경우에만 시스템에 deadlock 상태가 존재한다.

8.7.2 Several Instances of a Resource Type

wait-for graph는 종류마다 자원이 여러 개씩 존재하는 상황에서는 사용할 수 없다. 아래의 기법은 이러한 상황에서 deadlock 상태를 탐지할 수 있다.

• Available : 각 종류의 자원이 현재 몇 개가 가용한지를 나타내는 벡터로 크기가 m이다.
• Allocation : 각 스레드에 현재 할당된 자원의 개수를 나타내는 행렬로 크기가 nxm이다.
• Reqeust : 각 스레드가 현재 요청 중인 자원의 개수를 나타내는 행렬로 크기가 nxm이다. Request[i][j] == k라면 현재 T_i가 R_j를 k개 요청 중임을 뜻한다.

8.8 Recovery from Deadlock

탐지 알고리즘이 deadlock 상태가 존재한다고 결정하면, 여러 대안의 처리 방법이 있다.

8.8.1 Process and Thread Termination

프로세스 또는 스레드를 중지(abort)시킴으로써 deadlock 상태를 제거하기 위해 두 방법의 하나를 사용한다. 두 방법 모두 종료된 프로세스에 할당되었던 모든 자원을 시스템이 회수한다.

• deadlock 상태 프로세스를 모두 중지
  : 이 방식은 확실하게 deadlock 상태의 사이클을 깨뜨리지만 그 비용이 크다. 왜냐하면 이들 프로세스가 오랫동안 연산했을 가능성이 있고, 이들 부분 계산의 결과들을 반드시 폐기해야 하며, 아마도 후에 다시 계산해야 하기 때문이다.
• deadlock 상태가 제거될 때까지 한 프로세스씩 중지
  : 이 방법은 각 프로세스가 중지될 때마다 deadlock 상태 탐지 알고리즘을 호출해 프로세스들이 아직도 deadlock 상태에 있는지 확인해야 하므로 상당한 오버헤드를 유발한다.

프로세스를 중지시키는 일은 쉽지 않다. 어떤 프로세스를 우선으로 중지시켜야 할지를 반드시 결정해야 한다. 프로세스들을 중지시켰을 때 유발되는 비용이 최소인 프로세스들을 중지시켜야 하는데, 다음과 같은 많은 요인들이 있다.

1. 프로세스의 우선순위가 무엇인지
2. 지금까지 프로세스가 수행된 시간과 지정된 일을 종료하는 데 더 필요한 시간
3. 프로세스가 사용한 자원 유형과 수 (예를 들어, 자원들을 선점하기가 단순한지 여부)
4. 프로세스가 종료하기 위해 더 필요한 자원의 수
5. 얼마나 많은 수의 프로세스가 종료되어야 하는지

8.8.2 Resource Preemption

자원 선점을 이용해 deadlock 상태를 제거하려면, deadlock 상태가 깨질 때까지 프로세스로부터 자원을 계속 선점해 이들을 다른 프로세스에 주어야 한다. 만일 deadlock 상태를 해결하기 위해 preemption이 필요하다면, 다음의 세 가지 사항들을 고려해야 한다.

1. selection of victim (희생자 선택)
   : 어느 자원과 어느 프로세스들이 선점될 것인가? 프로세스 종료에서와 같이 비용을 최소화하기 위해 선점의 순서를 결정해야 한다.
2. rollback (후퇴)
   : 프로세스로부터 자원을 선점하려면, 그 프로세스를 어떻게 해야 하는가? 확실한 것은 필요한 자원이 부족하여 이 프로세스를 계속 정상적으로 실행할 수 없다는 것이다. 우리는 이 프로세스를 안전한 상태로 후퇴시키고, 그 상태로부터 다시 시작해야 한다.
3. starvation (기아)
   : 기아 상태가 발생하지 않는 것을 어떻게 보장하는가? 즉, 자원들이 동일한 프로세스로부터 항상 선점되지 않는다는 것을 어떻게 보장하는가? 희생자 선택이 주로 비용 요인에 근거한 시스템에서는 동일한 프로세스가 항상 희생자로 선택될 수도 있다. 일반적인 해결방법은 비용 요소에 후퇴의 횟수를 포함한다.