Deadlock

Background

Deadlock은 liveness failure의 일종으로, 프로세스 집합 내 모든 프로세스가 다른 프로세스에 의해서만 발생할 수 있는 이벤트를 기다리는 상황을 말한다.

멀티프로그래밍 환경에서는, 여러 스레드가 유한한 자원에 대해 경쟁한다. 자원이 가용하지 않으면 스레드는 대기하며, 가끔은 대기 중인 스레드가 다른 대기 중인 스레드가 점유한 자원에 대해 요청하여 끊임없이 대기하는 경우가 생긴다. 이를 Deadlock 상황이라고 한다.

System Model

시스템은 경쟁하는 스레드들에 분배되어야 하는 유한한 자원으로 구성된다. 자원은 여러 타입이나 클래스로 구분되는데, 각 타입은 몇 개의 동일한 인스턴스로 구성된다. 대표적인 자원 타입으로는 CPU 사이클, 파일, I/O 장치 등이 있다. 만약 시스템이 네 개의 CPU로 구성된다면, 자원 타입 CPU는 4개의 인스턴스를 갖는다. 만약 스레드가 자원 타입의 인스턴스를 요청하면 해당 타입에 따른 임의의 인스턴스가 할당된다. Mutex Lock과 Semaphore와 같은 동기화 도구도 시스템 자원이며, deadlock 발생의 가장 일반적인 원인이다.

스레드는 자원을 사용하기 전에 요청하고, 사용이 끝나면 반환해야 한다.

• Request
  • 요청한 자원을 즉시 사용할 수 없다면, 가용할 때까지 대기한다.
• Use
  • 자원이 사용 가능하면 자원에 대한 연산을 수행한다.
• Release
  • 자원을 모두 사용하고 반납한다.

스레드는 작업 수행에 필요한 만큼만 자원을 요청해야 한다. 또한 요청하는 자원의 수는 시스템의 가용 자원의 수를 넘지 못한다.

자원에 대한 request와 release는 system call이다.

• 디바이스 request(), release()
• 파일 open(), close()
• 메모리 allocate(), free()
• Semaphore wait(), signal()
• Mutex Lock acquire(), release()

스레드가 커널에서 관리되는 자원을 사용할 때, OS는 스레드가 요청하고 할당 받았는지 확인한다. 시스템 table의 record로 각 자원의 할당 여부와 어느 스레드에 할당되었는지 기록한다. 다른 스레드에 이미 할당된 자원을 요청하는 스레드는 해당 자원에 대한 waiting 큐에 추가된다.

Deadlock in Multithreaded Applications

Deadlock은 스레드 실행 순서에 따라 일어날 수도 있고, 아닐 수도 있다. 아래 예제에서 스레드 1이 mutex_lock을 acquire하는 과정에서 mutex1과 mutex2를 스레드 2보다 먼저 요청 및 해제한다면 Deadlock이 발생하지 않는다. 특정 스케줄링 상황에서만 발생하는 deadlock에 대한 식별과 검사가 어려운 이유다.

/* thread1 runs in this function */
void *do_work1(void *param) {
   pthread_mutex_lock(&mutex1);
   pthread_mutex_lock(&mutex2);
   /* 임계영역 */
}

/* thread2 runs in this function */
void *do_work2(void *param) {
   pthread_mutex_lock(&mutex2);
   pthread_mutex_lock(&mutex1);
   /* 임계영역 */
}

Livelock

Livelock은 Deadlock과 다른 종류의 liveness failure다. Deadlock과 유사한 점은 두 상황 모두 둘 이상의 스레드가 진행되지 않는다는 것이다. 반면 deadlock과 달리 livelock은 스레드가 실패하는 작업을 계속 시도하는 상황을 뜻한다. Deadlock이 block된 상태에서 진전이 없는 것이라면 livelock은 block되지는 않았지만 진전이 없는 경우다.

두 사람이 복도를 지나가는 상황을 예로 들 수 있다. 두 사람은 서로의 방향에 의해 진로가 방해된다. 하지만 움직일 수는 있다.

Livelock은 스레드가 실패하는 작업을 동시에 재시도할 때 일어나지만 deadlock만큼 흔히 발생하지는 않고, 특정 스케줄링 상황에서만 발생 가능하다. 이 문제를 해결하려면 각 스레드가 랜덤한 시간에 재시도하도록 수정해야 한다. 실제 이더넷 네트워크에서 네트워크 충돌 시 이 방법으로 해결한다. 패킷 전송 과정에 충돌이 생기면 바로 재전송하지 않고 랜덤한 시간만큼 물러났다가 재전송하는 것이다.

Deadlock Characterization

다음 두 가지를 통해 Deadlock을 특정 짓는 조건들에 대해 살펴보자.

1. Necessary Conditions
2. Resource-Allocation Graph

1) Necessary Conditions

다음 네 개의 조건을 동시에 만족하면 deadlock 상황이라고 할 수 있다.

1. Mutual exclusion

   • 최소 하나의 자원은, 사용 중일 때 공유가 불가능하다.
   • 이로써 이미 사용하고 있는 자원을 요청한 스레드는 자원이 해제될 때까지 대기하고 있다.

2. Hold and wait

   • 스레드가 최소 하나의 자원을 사용하고 있는 상황에서 다른 스레드가 사용하고 있는 자원을 추가로 요청하는 상황이다.

3. No preemption

   • 자원이 선점되지 않는다.
   • 해당 자원을 사용하고 있는 스레드가 자발적으로 반납할 때만 자원이 해제된다.

4. Circular wait

   • 스레드 간 waiting이 circular 한 상황이다. 1 -> 2 -> 3 -> 1

네 가지 조건이 모두 독립적이지는 않다. 4번 조건은 2번 조건을 포함하고 있다. 그럼에도 각 조건을 별개로 간주하는 것이 용이하다.

2) Resource-Allocation Graph

Deadlock은 방향 그래프로 더 정확히 기술할 수 있다. 그래프는 정점 집합 V와 간선 집합 E로 구성되는 방향 그래프다.

정점은 다음과 같이 정의된다.

1. 스레드를 나타내는 정점 T.
2. 자원을 나타내는 정점 R.

방향 간선은 다음과 같이 정의된다.

1. Ti -> Rj

   • 스레드 i가 자원 j를 요청

2. Rj -> Ti

   • 자원 j의 인스턴스가 스레드 i에 할당됨

만약 그래프에 사이클이 없으면 시스템 내 어떤 스레드도 deadlock 상황이 아니다. 하지만 사이클이 있으면 deadlock이 있을 수 있다. 각 자원 타입이 정확히 하나의 인스턴스만을 포함하는 상황에 사이클이 존재하면 deadlock이 있다는 뜻이다. 이 경우 사이클은 deadlock의 필요/충분 조건이 된다.

P: Deadlock이 있으면.
Q: 사이클이 있다.

• Deadlock이 있기 위해서는 반드시 사이클이 있어야 한다. Q는 P의 필요조건

• Deadlock이 있다면 항상 사이클이 있다. P는 Q의 충분조건.

Method for Handling Deadlocks

다음 세 가지 방법으로 deadlock을 처리할 수 있다.

1. 무시한다.

   • Deadlock이 일어나지 않은 척 한다.

   • 대부분의 OS에서 사용하는 방법이다.

2. Deadlock을 예방하고 회피함으로써 deadlock 상태가 되지 않도록 보장하는 프로토콜을 사용한다.

   • 커널과 어플리케이션 개발자에게 달렸다.

3. Deadlock되는 상태를 허용한 후, 감지하고 해결한다.

   • 데이터베이스와 같은 시스템이 채택한 방식이다.

무시

만약 deadlock을 감지하고 복구할 수 있는 방법이 없다면, 시스템은 deadlock 상황임을 알 수 없고, 실행될 수 없는 스레드에 의해 자원이 hold된다. 더 많은 스레드가 자원을 요청함에 따라 점점 성능이 저하된다. 이때 1번 방법을 사용해 시스템을 재부팅 할 수 있다. 이 방법이 비용 관점에서 더 효율적이다.

예방 및 회피

그럼에도 시스템 차원에서 deadlock이 발생하지 않도록 보장하려면 deadlock-prevention 혹은 deadlock-avoidance를 적용할 수 있다. Deadlock prevention은 4가지 deadlock의 필요조건 중 최소 하나가 성립하지 않도록 보장하는 방법이다. 자원 요청에 대한 처리를 제한하여 deadlock을 예방한다. Deadlock avoidance는 사전에 스레드가 요청하고 사용하는 자원에 대한 정보를 OS에 제공하고, OS는 각 요청에 대해 스레드가 대기할지 결정한다. 현재 요청에 대한 가용 자원, 현재 할당된 자원, 향후 요청 및 해제를 고려하여 결정한다.

감지 및 해결

예방 및 회피 알고리즘을 사용하지 않으면 deadlock 상황이 일어난다. 시스템은 deadlock이 발생했는지 알기 위해 시스템 상태를 확인하는 알고리즘과, deadlock으로부터 복구하는 알고리즘을 제공함으로써 deadlock 상황을 해결할 수 있다.

Deadlock Prevention

네 가지 deadlock의 필요조건 중 하나 이상을 성립할 수 없도록 함으로써 deadlock을 예방할 수 있다.

1. Mutual exclusion

자원 공유를 허용함으로써 1번 조건이 성립되지 않도록 한다.

읽기 전용 파일과 같이 공유 가능한 자원을 사용할 때는 deadlock 상황에 놓이지 않는다. 하지만 어떤 자원은 근본적으로 공유가 불가능할 수 있다. 예를 들면 mutex lock. 따라서 1번 조건은 성립되어야 한다.

2. Hold and wait

스레드가 자원 요청 시 다른 자원을 hold하지 않도록 보장해야 2번 조건이 성립되지 않는다.

1. 각 스레드가 실행 전에 모든 자원을 요청하고 할당하도록 한다.

   • 자원 요청은 동적으로 이루어지기 때문에 비현실적이다.

2. 각 스레드가 자원을 갖고 있지 않을 때만 요청하도록 한다.

   • 스레드는 자원을 추가로 요청하기 전에 현재 할당된 자원을 해제해야 한다.

두 방법 모두 큰 단점이 있다. 첫 번째 방법은 자원 이용률이 저하된다. 할당은 되었지만 오랫동안 사용되지 않는 자원이 있을 수 있다. Mutex Lock이 스레드의 전체 실행 시간 만큼 할당되었지만 짧은 기간만 사용되는 예시가 있다.

두 번째 방법은 기아 현상이 발생할 수 있다. 여러 자원을 요청할 때 필요한 자원 중 하나가 다른 스레드에 할당되어있으면 무한히 대기할 수 있기 때문이다.

3. No preemption

모든 자원을 선점해서 3번 조건이 성립되지 않도록 한다.

프로토콜 1)

• 만약 스레드가 자원을 hold 한 상태에서 즉시 할당되지 않는 다른 자원을 요청한 경우 해당 스레드는 대기하게 되는데, 이때 대기하는 스레드가 점유한 자원을 해제한다.
• 선점된 자원은 스레드가 waiting 하던 자원 list에 추가된다.
• 새로 요청한 자원과 기존에 점유했던 자원을 모두 얻을 수 있을 때 재시작된다.

프로토콜 2)

• 스레드가 자원을 요청하면 자원이 가용한 지 먼저 확인한다.
• 가용하지 않으면, 추가 자원을 기다리는 다른 스레드에 할당되었는지 확인하고, 참이라면 자원을 선점한다.
• 만약 가용하지 않고, 자원을 기다리는 스레드에 할당되어있지도 않다면 요청한 스레드는 대기한다. 마찬가지로 이 스레드가 대기 중에 다른 스레드가 이 스레드가 점유한 자원을 요청하면 선점된다.
• 새로 요청한 자원과 기존에 점유했던 자원을 모두 얻을 수 있을 때 재시작된다.
• 이 프로토콜은 자원이 쉽게 save, restore 되는 자원에 적용된다. 예) CPU 레지스터, DB 트랜잭션. 하지만 deadlock이 흔하게 일어나는 Mutex Lock, Semaphore에는 적용되지 않는다.

4. Circular wait

앞서 언급한 세 방법은 대부분의 상황에서 비현실적이다. Circular wait chain을 끊는 방법이 가장 실용적인 방법으로 여겨진다. 4번 조건을 무효화하기 위해 모든 자원 유형에 순서를 매기고, 각 스레드가 열거된 오름차순으로 자원을 요청하게 한다.

1:1 함수로 자원에 번호를 맵핑한다. F(USB) = 3, F(mutex1) = 1, F(mutex2) = 2

프로토콜

• 각 스레드는 자원을 오름차순으로만 요청할 수 있다. 자원 Ri의 인스턴스를 요청했다면, 다음 요청 Rj는 F(Ri) < F(Rj)가 성립되어야 한다.
• 자원 Rj의 인스턴스를 요청하는 스레드는 번호가 높은 Ri를 해제해야 한다. F(Ri) >= F(Rj)
• 동일 유형의 자원의 여러 인스턴스가 필요한 경우 한 번의 요청으로 모두 할당 받는다.

증명

Circular wait가 있다고 가정하고 귀류법으로 증명한다.

스레드 집합 {T0, T1, ..., Tn}이 있다. Ti가 Ti+1에게 점유된 자원 Ri를 대기하고 있다. Tn은 T0에게 점유된 자원 Rn을 기다리고 있다. 즉 순환 대기 상황이다.

프로토콜을 적용해보자. 스레드 Ti+1은 자원 Ri를 점유하고 있는데 모든 i에 대해 F(Ri) < F(Ri+1)인 경우에만 자원 Ri+1을 요청할 수 있다. 따라서 F(R0) < F(R1) < ... < F(Rn) < F(R0)을 시도하는 경우, F(Rn)이 F(R0)보다 작을 수 없기 때문에 자원을 요청할 수 없고, 그 결과로 순환 대기를 예방한다.

살펴보았듯이, deadlock prevention은 자원 요청 방법을 제한하여 deadlock을 예방한다. 단점으로는 장치 이용률 저하, 시스템 처리율(throughput) 감소가 있다. 다른 방법으로는 Deadlock Avoidance가 있다.

Deadlock Avoidance

Deadlock Avoidance에서는 자원이 요청에 대한 추가 정보를 요구한다. 예시로, 시스템은 자원 R1과 R2에 대해 스레드 P와 Q가 요청하는 순서를 알아야 한다. 이 정보를 통해 향후 가능한 deadlock을 회피할 수 있게 wait 여부를 결정한다. 각 요청에 대해 시스템은 1) 현재 가용한 자원 2) 현재 할당된 자원 3) 향후 할당 및 해제 등을 고려하여 스레드의 wait 여부를 결정한다.

필요한 정보의 양과 유형에 따라 다양한 회피 알고리즘이 존재한다. 가장 단순하면서도 유용한 모델은 다음과 같다.

• 각 스레드는 자원 유형별로 최대 필요 필요한 자원 수를 선언한다.
• 시스템은 deadlock 상태에 진입하지 않도록 알고리즘을 구성한다.
• 순환 대기가 없도록 자원 할당 상태를 동적으로 확인한다.
• 자원 할당 상태는 [가용한 자원과 할당된 자원의 수, 최대 요구 자원의 수]로 결정된다.

두 개의 deadlock-avoidance 알고리즘에 대해 알아보기 전에 Safe State의 개념을 살펴보자.

Safe State

시스템이 어떤 순서로든 각 스레드에 자원을 할당하면서도 deadlock을 피할 수 있으면 상태가 safe하다. Safe sequence가 있을 때 시스템은 safe state다.

스레드 <T1, T2, ... ,Tn>가 각 스레드 Ti에 대해, Ti가 요청하려는 자원이 현재 가용자원 외에 Tj (j<i) 가 점유한 자원에 의해 만족된다면 이것을 safe sequence라고 한다. 자원이 가용하지 않다면 Ti는 Tj 종료 시까지 기다린다. Tj가 종료되면 Ti는 자원을 획득하여 정상적으로 처리한 뒤 자원을 반납하고 종료된다.

만약 safe sequence가 없다면 시스템의 상태는 unsafe state이다. safe state는 deadlocked state가 아니다. 하지만 deadlocked state는 unsafe state다. 모든 unsafe state가 deadlocked state는 아니다. 하지만 unsafe state는 deadlocked state가 될 수 있다. Safe state에서 OS는 unsafe state를 회피할 수 있으나, unsafe 상태에서 OS는 deadlock을 유발하는 자원요청을 예방할 수 없다.

Avoidance 알고리즘은 시스템이 항상 safe state에 머무르게 함으로써 deadlock에 빠지지 않는 것을 보장한다. 기본 동작은 다음과 같다.

• 처음에 시스템은 safe state다.
• 스레드가 자원을 요청할 때마다 시스템은 자원을 즉시 할당할 지 스레드가 대기해야 할 지 결정된다.
• 자원 요청은 할당 후에 시스템이 safe state일 때만 허락된다.

문제는 가용 자원을 요청하더라도 계속 대기해야 될 수 있다는 점과, 자원 이용률이 낮아진다는 점이다.

Resource-Allocation-Graph Algorithm

자원할당 그래프의 변형이다. 기존 자원 할당 그래프의 정점과 간선 구성은 동일하지만 claim edge(요청 간선)가 추가되었다.

safe state인지 확인하기 위해 사이클 감지 알고리즘을 이용한다. 사이클이 없다면 자원을 할당해도 시스템은 safe state다. 만약 사이클이 감지되면 시스템이 unsafe state에 놓인다. 이때 스레드는 요청이 충족될 때까지 대기해야 한다.

Banker's Algorithm

자원 할당 알고리즘은 인스턴스가 여러 개인 경우 사용이 어렵다. Banker's 알고리즘이라 불리는 deadlock-avoidance 알고리즘은 인스턴스가 여러 개인 경우 사용할 수 있꼬, 은행 시스템에서 더 이상 모든 고객의 요구를 충족시킬 수 없는 상태에서 현금을 지급하지 않도록 보장하기 위해 사용된다.

기본 동작

• 새로운 스레드는 필요한 자원 유형의 최대 인스턴스 수를 시스템에 알려야 한다.
• 필요한 인스턴스 수는 시스템 내 가용한 총 인스턴스 수를 넘기면 안 된다.
• 스레드가 자원을 요청하면 시스템은 해당 자원을 할당해도 safe state를 유지할 수 있는지 판단한다.
• Safe state가 유지된다면 할당하고, 그렇지 않다면 다른 스레드가 자원을 해제할 때까지 스레드는 대기한다.

자료구조

• i: 스레드 번호

• j: 자원 유형 번호

• Available[]: 각 자원 유형별 가용 인스턴스 수

  • Available[j] = k는 자원 j에 k개의 인스턴스가 가용하다는 뜻이다.

• Max[][]: 스레드별 최대 요구 수

  • Max[i][j]는 스레드 i가 자원 j에 대해 최대로 요구하는 수이다.

• Allocation[][]: 스레드별 할당 자원 수

  • Allocation[i][j] = k는 스레드 i에 대해 자원 j가 k개의 인스턴스만큼 할당되었다는 뜻이다.

• Need[][]: 스레드별 추가 필요 자원 수

  • Need[i][j] = k는 스레드 i가 자원 j에 대해 k의 추가 자원이 필요하다는 뜻이다.

다음과 같은 관계를 가진다.

Need[i][j] = MAX[i][j] - Allocation[i][j]

Safety Algorithm

모든 스레드 i에 대해

1. Work 와 Finish를 길이 n과 m의 벡터로 초기화

   • Work = Available, Finish[i] = false for all i

2. 다음의 조건을 모두 만족하는 스레드 i를 찾는다.

   1. 종료되지 않았고 Finish[i] == false
   2. 필요한 모든 자원이 현재 모든 가용 자원보다 작거나 같다 Need_i ≤ Work로,
   • 만족하는 i가 없다면 4번으로.

3. 스레드에 할당된 자원을 회수한다. Work = Work + Allocation_i

   • 스레드 i 종료 처리 Finish[i] = true
   • 2번으로 이동

4. 모든 i에 대해 Finish[i] == true이면 safe state.

만약 2번의 두 조건을 만족하는 i가 없고, Finish[i] == false면 unsafe state.

Resource-Request Algorithm

Resource-Request 알고리즘은 스레드의 자원 요청이 허용되는 지 결정하는 알고리즘이다.

Request_i[j] == k: 스레드 i가 자원 j에 대해 k개의 인스턴스를 요청한다.

스레드 자원 요청 시 동작

1. 만약 Request_i <= Need_i면 2번으로
   • 필요한 자원보다 많이 요청하면 에러를 뱉는다.
2. Request_i <= Available면 3번으로.
   • 가용한 것보다 적게 요청함.
   • 가용한 것보다 많이 요청하면 대기해야 한다.
3. 시스템은 요청한 자원을 스레드 i에 할당한 것처럼 상태값 갱신
   • Available -= Request_i, Allocation_i += Request_i, Need_i -= Request_i

만약 요청 할당 결과의 상태가 safe면 트랜잭션은 완료되고 스레드 i는 자원을 할당 받는다. 하지만 새 상태가 unsafe라면 스레드 i는 대기해야 한다.

Deadlock Detection

만약 시스템이 deadlock-prevention이나 deadlock-avoidance 알고리즘을 활용하지 않는다면 deadlock 상황이 발생할 수 있다. 따라서 deadlock 발생 여부를 결정하기 위해 시스템 상태를 검사하는 Detection 알고리즘과 deadlock으로부터 회복하는 Recovery 알고리즘이 필요하다. Detection-and-recovery 방법은 필수 정보 유지와 탐지 알고리즘 실행에 따른 오버헤드와 deadlock에서 회복할 때의 잠재적인 오버헤드가 필요하다.

다음으로 각 자원 유형에 대해 single/several 인스턴스는 갖는 시스템에서의 요구사항을 살펴본다.

Single Instance of Each Resource Type

각 자원 유형의 인스턴스가 한 개인 경우, 자원-할당 그래프의 변형인 wait-for 그래프를 활용한다.

Wait-for 그래프는 자원-할당 그래프에서 자원과 적절한 간선을 제거한 것이다. 스레드가 어떤 스레드의 자원 방출을 기다리는지 표현하는 용도로 사용된다.

간선 Ti -> Tj: 스레드 i가 스레드 j가 가진 자원을 방출하기를 기다린다는 이며, 만약 wait-for 그래프에 사이클이 있으면 시스템에 deadlock이 존재한다. Deadlock이 있는지 검사하기 위해 시스템은 wait-for 그래프를 유지하고, 그래프에서 사이클을 찾기 위한 알고리즘을 주기적으로 호출해야 한다.

Several Instances of a Resource Type

기본 동작

1. 만약 자원을 점유한 상태라면 Allocation_i != 0, 종료되지 않은 스레드로 초기화 Finish[i] = false
   • 그렇지 않다면 종료된 스레드로 초기화 Finish[i] = true
2. 다음의 조건을 만족하는 스레드 i를 찾는다.
   1. 아직 끝나지 않았고 Finish[i] == false
   2. 가용한 자원보다 작거나 같게 요청함 Request_i <= Work.
   • 만족하는 스레드 i 가 없다면 4번으로
3. Work = Work + Allocation_i로 자원 회수 및 종료 처리 Finish[i] = true
4. 만약 Finish[i] == false 인 스레드가 있다면, 시스템은 deadlock 상태다. 또한 Finish[i] == false인 스레드도 deadlock 되었다.

Detection Algorithm Usage

언제 detection 알고리즘을 실행할까? 다음 두 요소에 따라 좌우된다.

1. 얼마나 자주 deadlock이 발생하는가?
2. 얼마나 많은 스레드가 연관되는가?

Deadlock이 자주 일어난다면 detection 알고리즘도 자주 호출되어야 한다. Deadlock 상황에 놓인 스레드에 할당된 자원은 deadlock이 해결될 때까지 IDLE 상태에 놓인다. deadlock을 방치한다면 deadlock 사이클에 포함된 스레드의 수가 점점 늘어날 것이다.

Deadlock은 어떤 스레드가 즉시 승인될 수 없는 요청을 한 시점에 일어난다. 이 요청이 waiting 스레드 체인을 완성하는 요청일 수 있다. 따라서 detection 알고리즘은 할당 요청이 즉시 승인되지 않을 때마다 호출하고, 일정한 시점마다 추가로 호출해서 deadlock을 감지할 수 있다.

1. 할당 요청이 즉시 승인되지 않을 때
   • Deadlock된 스레드 뿐만 아니라 deadlock을 야기시킨 스레드도 식별 가능하다.
   • 자원 요청에 대한 detection 알고리즘 호출은 오버헤드를 야기한다.
2. 일정한 시점마다
   • 임의로 호출되면 여러 사이클이 포함될 수 있다.
   • 어느 스레드가 deadlock을 야기시켰는지 판단이 불가하다.

Recovery from Deadlock

Detection 알고리즘을 통해 deadlock이 발견되었다면 어떻게 처리해야 할까? 첫째, 운영자에게 통지하여 수작업으로 처리하게 한다. 둘째, 시스템이 자동으로 회복하게 한다. Deadlock을 중지시키기 위해서는 다음 두 가지 옵션이 있다.

1. 스레드/프로세스를 중지시킨다.
2. 자원을 선점한다.

1) 스레드/프로세스 중지

스레드/프로세스 중지는 두 가지 방법으로 할 수 있다.

1. 모든 프로세스를 중지한다.
   • 확실히 deadlock을 중지시킬 수 있으나 비용 관점에서 비효율적이다.
   • 이미 오래 실행된 작업이 있는데 도중에 중지되었다면 재시작할 때 그 작업을 처음부터 다시 해야 할 수 있다.
2. 사이클이 제거될 때까지 하나씩 중지한다.
   • 각 프로세스가 중지될 때마다 알고리즘이 호출되어야 해서 오버헤드가 발생한다.

작업을 강제 중단하는 것은 쉬운 작업이 아니다. 만약 파일을 업데이트하다가 중지된다면 파일은 incorrect state가 될 수 있다. Mutex Lock을 가진 상태에서도 공유 데이터 업데이트를 중지한다면 시스템은 무결성을 보장할 수 없더라도 lock이 가용하도록 복구해야 한다.

만약 하나씩 중지하는 방법을 선택했다면, 어떤 프로세스부터 종료시켜야 할까? 중지시켰을 때 가장 비용이 적게 드는 프로세스를 중지시켜야 한다. 선택에는 다음과 같은 요소가 영향을 준다.

1. 우선순위
2. 연산한 시간, 작업이 끝나기 까지 남은 연산
3. 점유한 자원의 수와 유형
4. 추가 필요 자원
5. 종료되어야 하는 프로세스 수

2) 자원 선점

Deadlock 사이클이 깨질 때까지 자원을 선점하여 다른 프로세스에게 전달한다. 선점을 위해서는 다음을 고려해야 한다.

1. 선점되는 프로세스 선택
   • 비용을 최소화 할 수 있는 선택을 해야 한다.
   • 비용은 프로세스가 점유한 자원 수, 지금까지 소비한 양 등을 고려한다.
2. 선점된 프로세스의 복구
   • Safe state로 rollback되면 그 상태로부터 재시작해야 한다.
   • Safe state의 결정이 어려운 편이다.
   • 가장 단순한 솔루션은 모두 rollback하고 재시작하는 것이다.
   • 하지만 시스템이 모든 상태 정보를 유지해야 하기 때문에 Deadlock을 깰 수 있을 정도만 rollback 하는 것이 효과적이다.
3. 동일 프로세스가 항상 선점되지 않도록 보장
   • 비용 기반으로 선점되는 프로세스를 선택하면 항상 동일한 프로세스가 선택될 수 있다.
   • 항상 선점되는 프로세스는 작업을 마칠 수 없기 때문에 한정된 시간 동안만 희생자로 선정되어야 한다.
   • 비용을 고려할 때 rollback 횟수를 함께 고려하면 해결할 수 있다.