[공룡책] Ch.8 교착 상태

---

이 글은 공룡책을 읽고 정리한 글입니다.

---

 

 

 

0. 소개

---

다중 프로그래밍 환경에서는 여러 스레드가 한정된 자원을 사용하려고 서로 경쟁할 수 있다. 한 스레드가 자원을 요청했을 때, 그 시각에 그 자원을 사용할 수 없는 상황이 발생할 수 있고, 그러면 스레드는 대기 상태로 변경된다. 이처럼 대기 중인 스레드들이 결코 다시는 그 상태를 변경시킬 수 없는 상황을 교착 상태라고 부른다.

 

책에서는 교착 상태를 프로세스 집합 내의 모든 프로세스가 그 집합의 다른 프로세스에 의해서만 일어날 수 있는 이벤트를 기다리는 상황으로 정의하였다.

 

교착 상태의 가장 좋은 예는 "두 기차가 교차로에서 서로 접근할 때, 둘 다 완전히 정지해야 하며 상대방이 없어지지 않는 한 누구도 다시 출발할 수 없다."이다.

---

 

 

 

1. 시스템 모델

---

시스템은 유한한 수의 자원들로 구성된다. 자원은 여러 개의 유형으로 나눌 수 있으며, 각각의 자원은 동등한 인스턴스들로 구성된다. 만약 한 시스템이 4개의 CPU를 가지면, 자원 유형 CPU는 4개의 인스턴스를 가진다. Mutex 락과 세마포와 같은 동기화 도구도 시스템 자원이며, 현대 컴퓨터 시스템에서는 교착 상태가 가장 많이 일어나는 곳이다.

만일 한 스레드가 어떤 자원 유형의 한 인스턴스를 요청하면, 동일 유형 자원의 임의의 인스턴스를 할당함으로써 요청이 충족된다.

 

프로세스는 다음 순서로 자원을 사용할 수 있다.

1. 요청: 스레드는 자원을 요청하고, 요청이 즉시 허용되지 않으면 자원을 얻을 때까지 대기해야 한다.

2. 사용: 스레드는 자원에 대해 작업을 수행할 수 있다.

3. 방출: 스레드가 자원을 방출한다.

이때 자원의 요청과 방출은 시스템 콜이다.

 

한 스레드 집합 내의 모든 스레드가 그 집합 내의 다른 스레드에 의해서만 발생될 수 있는 이벤트를 기다린다면, 그 스레드 집합은 교착 상태에 있다.

6장에서 설명했던 락킹 도구들은 경쟁 조건을 회피하도록 설계되었지만, 개발자는 락이 획득하고 방출되는 방식에 대해 주의를 기울여야 한다. 그렇지 않으면 아래 내용와 같은 교착 상태가 발생할 수 있다.

---

 

 

 

2. 다중 스레드 응용에서의 교착 상태

---

1) 교착 상태

/* thread_one은 이 함수를 실행 */
void *do_work_one(void *param)
{
	pthread_mutex_lock(&first_mutex);
    pthread_mutex_lock(&second_mutex);
    
    /* do some work */
    
    pthread_mutex_unlock(&second_mutex);
    pthread_mutex_unlock(&first_mutex);
    
    pthread_exit(0);
}

/* thread_two는 이 함수를 실행 */
void *do_work_two(void *param)
{
	pthread_mutex_lock(&second_mutex);
    pthread_mutex_lock(&first_mutex);
    
    /* do some work */
    
    pthread_mutex_unlock(&first_mutex);
    pthread_mutex_unlock(&second_mutex);
    
    pthread_exit(0);
}

위와 같은 코드가 있고 스레드 1은 do_work_one 함수를, 스레드 2는 do_work_two 함수를 동시에 실행한다고 가정하자

이때 이러면 스레드 1은 first_mutex 락을 획득하고, 스레드 2는 second_mutex 락을 획득하는데, 이 다음이 문제이다.

스레드 1은 스레드 2의 second_mutex 락을 해제하기를 기다리고, 스레드 2는 스레드 1의 first_mutex 락을 해제하기를 기다리는데, 서로 계속 기다리는 일 밖에 없으니 교착상태가 일어난다.

---

2) 라이브락 (livelock)

라이브락은 교착 상태와 비슷하지만 다르다.

교착 상태는 어떤 스레드의 집합에 속하는 스레드가 같은 집합에 속한 다른 스레드에 의해서만 발생할 수 있는 이벤트를 기다리면서 봉쇄되면 발생되는 것이지만, 라이브락은 스레드가 실패한 행동을 계속해서 시도할 때 발생한다.

예를 들면 서로 마주보는 방향으로 걸어가서 복도를 통과하려고 하는데, 서로 경로가 겹쳐서 앞으로 진행할 수 없는 것이다. 이 경우 봉쇄되지는 않았지만 진행이 불가능하다.

라이브락은 각 스레드가 실패한 행동을 랜덤한 시간에 실행하도록 하는 것으로 회피할 수 있다.

---

 

 

 

3. 교착 상태 특성

---

2절에서는 교착 상태가 발생할 수 있는 상황에 대해 설명하였고, 이번 절에서는 교착 상태를 특징 짓는 조건에 대해 살펴본다.

---

1) 교착 상태가 일어나는 필요조건들

다음 네 가지 조건이 성립될 때 교착 상태가 발생할 수 있다.

1. 상호 배제 (mutual exclusion)

최소 하나의 자원이 비공유 모드로 점유되어야 하고, 비공유 모드는 한 번에 한 스레드만 그 자원을 사용할 수 있다.

만약 다른 스레드가 그 자원을 요청하면, 요청한 스레드는 자원이 방출될 때까지 기다린다.

2. 점유하며 대기 (hold-and-wait)

스레드는 최소한 하나의 자원을 점유하면서, 다른 스레드에 의해 점유된 자원을 추가로 얻기 위해 대기한다.

3. 비선점 (no preemption)

자원을 선점할 수 없다. (= 자원을 강제로 빼앗기가 불가능하다.)

자원이 강제적으로 방출될 수 없고, 점유하고 있는 스레드가 태스크를 종료한 후 그 스레드에 의해 방출될 수 있다.

4. 순환 대기 (circular wait)

스레드의 집합 [T[0], T[1], ..., T[n]]이 있을 때, T[0]은 T[1]의 자원을 기다리고, T[1]은 T[2]의 자원을 기다리고, ... T[n-1]은 T[n]의 자원을 기다리고, T[n]은 T[0]의 자원을 기다려야 한다.

---

2) 자원 할당 그래프

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

여기서 정점은 스레드와 자원이고, 스레드 → 자원 혹은 자원 → 스레드로 간선을 연결할 수 있다.

이때 스레드 → 자원의 간선은 스레드가 자원을 요청하는 것이므로 요청 간선이라고 부르고, 자원 → 스레드의 간선은 자원을 스레드에 할당하는 것으로 할당 간선이라고 부른다.

정점을 표현할 때, 스레드는 원으로 표현하고, 자원은 사각형으로 표현한다.

여기서 중요한 점은 교착 상태이면 그래프가 사이클을 이룬다. 하지만 그래프가 사이클을 이룬다고 해서 교착 상태가 발생하지는 않는다.

 

상황 1) 교착 상태일 때

스레드 1은 자원 1을 할당 받은 상태이고, 자원 2를 요청한 상태이다.

스레드 2는 자원 2를 할당 받은 상태이고, 자원 1을 요청한 상태이다.

 

- 서로 자원을 요청하고 기다리는 상태이니 상호 배제를 만족한다

- 각 스레드는 자원을 점유한 상태에서 다른 자원을 요청한 상태이니 점유하며 대기를 만족한다.

- 현재 상황은 선점이 없으므로 비선점을 만족한다.

- 스레드 1은 스레드 2의 자원을 기다리고 있고, 스레드 2는 스레드 1의 자원을 기다리므로 순환 대기를 만족한다.

---

상황 2) 교착 상태가 아닐 때

이 상황은 사이클이 없으므로 교착 상태가 일어나지 않는다.

---

 

상황 3) 교착 상태일 때

여기서는 두 개의 사이클이 생기고, 스레드는 모두 교착 상태이다.

T[1] → R[1] → T[2] → R[3] → T[3] → R[2] → T[1]

T[2] → R[3] → T[3] → R[2] → T[2]

 

---

상황 4) 사이클이지만 교착 상태가 아닐 때

사이클: T[1] → R[1] → T[3] → R[2] → T[1]

이때 T[4]가 R[2]의 자원을 방출할 수 있기 때문에 교착 상태가 아니다.

---

 

 

 

4. 교착 상태 처리 방법

---

교착 상태 문제를 처리하는데는 아래와 같은 세 가지 방법이 있다.

- 문제를 무시하고, 교착 상태가 절대 발생하지 않은 척을 한다. (대부분의 운영체제가 사용하는 방법)

- 교착 상태가 발생하지 않기 위해 예방을 하거나 회피하는 프로토콜을 사용한다.

- 교착 상태를 허용하고, 교착 상태를 탐지하여 복구를 하는 방법을 사용한다.

 

교착 상태 예방은 교착 상태가 필요한 네가지 필요조건 중 적어도 하나가 성립하지 않도록 하는 방법이다.

교착 상태 회피는 어떤 스레드가 평생 요구하고 사용할 자원에 대한 정보를 제공하여 미래의 일을 관리할 수 있게 한다.

교착 상태 탐지는 교착 상태가 발생했는지 결정하기 위해 시스템의 상태를 조사하는 알고리즘이다.

교착 상태 회복은 교착 상태로부터 복구하기 위한 알고리즘이다.

 

이것이 전부 없다면 교착 상태가 발생하기 때문에 첫번째 방법이 되는데, 이것은 시스템 성능이 저하될 수 밖에 없다.

첫번째 방법이 많은 운영체제에서 쓰이는 이유는 애초에 교착 상태가 일어나는 것은 드물며, 교착 상태를 무시하는 것이 비용이 더 적게 들기 때문에 쓰인다고 한다.

---

 

 

 

5. 교착 상태 예방

---

교착 상태를 예방하려면 교착 상태를 위한 충분 조건 네 가지중 최소 하나가 성립되지 않도록 만드는 것이다.

하지만 이런 방법은 장치의 이용률이 저하되고, 시스템 총처리율이 감소된다는 단점이 있다.

---

1) 상호 배제

상호 배제를 예방하려면 자원이 공유가 되어야 한다.

하지만 mutex 락과 같은 자원은 동시에 여러 스레드가 공유할 수 없기 때문에 일반적으로 상호 배제를 에방할 수는 없다.

---

2) 점유하며 대기

점유하며 대기를 예방하려면 스레드가 자원을 요청할 때마다 다른 자원을 보유하지 않도록 보장해야 한다.

방법 1) 각 스레드가 실행을 시작하기 전에 모든 자원을 요청하고 할당한다.

방법 2) 스레드가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 한다.

 

하지만 이런 방법은 단점이 있어서 실용적이지 않아 예방하기가 힘들다.

문제 1) 자원이 할당되었지만, 장기간 사용을 하지 않을 수 있어서 자원 이용률이 낮다.

문제 2) 여러 개의 자원이 필요한 스레드는 그 자원 중 적어도 하나는 다른 스레드에 할당되어 기아상태가 될 수 있다.

---

3) 비선점

비선점의 경우엔 선점을 하면 된다. 이때 자원 선점을 하려는 스레드는 선점하기 전에 자기가 가지고 있던 모든 자원을 방출하고, 다시 필요한 자원들을 획득하도록 한다.

이것은 CPU 레지스터나 데이터베이스 트랜잭션처럼 상태가 쉽게 저장되고 복원될 수 있는 자원에 적용된다.

하지만 교착상태가 쉽게 일어나는 mutex 락과 세마포 같은 자원에는 적용될 수 없어서 예방하기가 힘들다.

---

4) 순환 대기

이 조건을 예방하는 것이 현실적으로 가장 실용적인 방법이다.

순환 대기 조건이 성립되지 않도록 하는 방법은 모든 자원 유형에 할당 순서를 부여하여, 각 프로세스가 순서대로 자원을 요청하게 만드는 것이다.

이런 경우 순환 대기가 아닌 순환이 없는 선형 대기가 되어 문제를 해결할 수 있게 된다.

 

하지만 이것도 선형 대기를 만들었다고 무조건 교착 상태를 예방할 수 없는 것에 주의를 해야한다.

---

 

 

 

6. 교착 상태 회피

---

교착 상태를 예방하는 방법에는 단점이 있어서 교착 상태를 회피하는 방법이 고안되었다.

회피하는 방법은 자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구하는 것이다.

 

만약 스레드 1이 자원 A를 요구한 뒤, 자원 B를 요구하는 순서가 있고, 스레드 2는 자원 B를 요구한 뒤, 자원 A를 요구하는 순서를 가진다고 가정하자. 운영체제가 이런 순서를 알고 있다면 교착 상태를 피하고자 하나의 스레드를 대기하게 만들어서 회피할 수 있을 것이다.

 

이런 방법을 사용하는 가장 단순하고 유용한 모델은 각 스레드가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구하는 것이다.

이 경우 각 유형의 자원의 최대 수를 미리 알 수 있으면, 교착 상태에 들어가지 않는 것을 보장하는 알고리즘을 만들 수 있다. 이것을 위해 교착 상태 회피 알고리즘은 순환 대기 상황이 발생하지 않도록 자원 할당 상태를 검사한다.

---

1) 안전 상태

시스템 상태가 안전하다는 것은 시스템이 어떤 순서로든 스레드들이 요청하는 모든 자원을 교착 상태가 일어나지 않게 차례로 모두 할당할 수 있는 것을 말한다. 이런 순서를 안전 순서라고 부른다.

위에 내용을 더 자세하게 말하자면 어떤 스레드 T[i]가 요청하는 자원은 시스템에 남은 자원과 T[i]가 작업하기 전에 스레드 T[j]들이 반납하는 자원들로 T[i]에 자원을 할당할 수 있는 것을 말한다.

 

시스템의 상태가 안전하면 무조건 교착 상태가 아니지만, 시스템의 상태가 불안전하면 교착 상태가 있을 수도 있고 없을 수도 있다.

 

ex) 시스템에 자원은 총 12개, t0 시점에서 T[0], T[1], T[2]의 상황

	최대 소요량	현재 소요량
T[0]	10	5
T[1]	4	2
T[2]	9	2

이 시점에서 시스템은 안전 상태이다.
1. 시스템에 남은 자원은 3개이니 T[1]에 자원 2개를 할당하여 해결한다.
2. 이후 시스템에 남은 자원은 5개이니 T[0]에 자원을 모두 할당하여 해결한다.
3. 이후 시스템에 남은 자원은 10개이므로 T[2]에 자원 7개를 할당하여 해결한다.
따라서 안전 순서는 <T[1], T[0], T[2]>이다.

 

시스템은 안전 상태에 있다가도 불안전 상태로 바뀔 수 있다.

위 예시와 같은 상황인데 어느 시점 t₁에서는 T[2]가 자원을 1개 더 가지고 있는 상황일 때, 시스템은 T[1]은 해결할 수 있으나 T[0]과 T[2]를 해결할 수 없어서 불안전 상태이다.

 

회피 알고리즘의 기본 원칙은 시스템이 안전 상태를 유지할 수 있도록 만드는 것이다.

시스템의 최초 상태는 무조건 안전 상태이다. 이후 스레드들이 자원을 요청하면 시스템은 자원을 할당하거나 대기시키는 것중 안전 상태를 유지할 수 있는 쪽을 선택한다.

하지만 이런 방식을 사용하면 안전 상태를 유지하기 위해 자원이 널널해도 스레드를 가지고 있는 프로세스를 대기시키는 경우가 존재한다. 그렇게 때문에 회피를 하지 않는 것보다 자원 이용률이 낮아질 수 밖에 없다. 

---

2) 자원 할당 그래프 알고리즘

시스템 자원 할당 그래프에서 요청 간선과 할당 간선뿐만 아니라 점선으로 표시하는 예약 간선을 도입한다.

예약 간선은 스레드 → 자원에 사용하는 간선으로 스레드 T가 미래에 자원 R을 요청할 것이라는 의미이다.

시스템은 자원이 필요하면 무조건 예약되어야 하고, 자원 할당도 사이클을 형성되지 않을 때만 자원을 할당할 수 있다.

 

이 경우 스레드 T[2]가 자원 R[2]를 요청하고 있지만, 현재 아무도 사용하지 않는 R[2] 자원을 T[2]에 할당할 경우 사이클이 생기기 때문에 할당할 수 없다.

그래서 이 알고리즘은 사이클 탐지 알고리즘을 통해 안정성을 검사하는데, 해당 알고리즘의 시간복잡도는 O(N^2)이고, 이때 N은 스레드의 수이다.

 

자원 할당 그래프 알고리즘의 치명적 단점은 종류마다 자원이 여러 개 있으면 사용할 수 없다는 것이다. 그래서 이런 상황에서는 은행원 알고리즘을 사용하게 된다.

---

3) 은행원 알고리즘

은행원 알고리즘은 자원 할당 그래프 알고리즘에 비해 효율성은 떨어지지만, 종류마다 자원이 여러 개 있어도 알고리즘을 사용하는데 문제가 없다는 장점이 있다.

왜 은행원 알고리즘이냐면 이 알고리즘을 은행에 적용하면 고객들이 현금을 찾으러 와도 일정한 수선에 의해 모든 고객의 요청을 다 들어줄 수 있기 때문이라고 한다.

 

이 시스템에서는 스레드가 시작할 때, 스레드가 가지고 있어야 할 자원의 최대 개수를 자원 종류마다 미리 신고하여야 한다. 스레드가 자원들을 요청하면 시스템은 스레드에 자원을 할당해도 안전 상태에 머무르는지 확인한다.

계속 안전하면 해당 요청을 들어주고, 아니라면 다른 스레드가 끝날 때까지 기다리게 한다.

 

은행원 알고리즘을 구현하려면 몇 가지 자료구조가 필요하다. (n = 스레드의 수, m = 자원의 종류 수)

- Available: 종류별로 사용 가능한 자원의 개수를 나타내는 벡터로 크기가 m

- Max: 각 스레드가 최대로 필요로 하는 자원의 개수, 크기가 n x m인 행렬

- Allocation: 각 스레드에 현재 할당된 자원의 개수를 나타내는 크기가 n x m인 행렬

- Need: 각 스레드가 향후 요청할 수 있는 자원의 개수를 나타내는 크키각 n x m인 행렬

(이때 Need[i][j] = Max[i][j] - Allocation[i][j])

 

3.1) 안전성 알고리즘

현재 시스템이 안전상태인지 판단하는 알고리즘이다.

1. Work = Available (크기 m 벡터), Finish = false (크기 n 벡터)로 초기값을 오른쪽 항과 맞게 준비한다.

2. Finish[i] == false && Need[i] <= Work인 i값을 찾는다. (i값이 없으면 4번으로)

3. Work = Work + Allocation[i], Finish[i] = true 로 설정하고 2번으로 돌아간다.

4. 모든 i값에 대해 Finish[i] == true이면 시스템은 안전 상태이다.

 

내가 이해한 바로는 Work는 현재 사용한 자원의 종류별 개수이다.

이때 Need[i] <= Work이면 i번째 스레드는 Work에 있는 자원만으로 작업을 마칠 수 있다는 것이다.

이후 작업을 마치면 Work에 있는 자원은 기존에 할당한 자원 뿐만 아니라, 원래 i번째 스레드에서 사용하고 있었던 자원인 Allocation[i]만큼 증가하게 되고, 다시 해당 자원으로 작업을 마칠 수 있는 스레드를 찾는다.

이런 과정을 반복해서 모든 작업을 끝낼 수 있게 되면 이 시스템은 안전 상태임을 뜻한다.

해당 알고리즘의 시간복잡도는 O(m x n^2)이다.

 

3.2) 자원 요청 알고리즘

스레드가 자원을 요청했을 때, 시스템이 해당 스레드에 자원을 할당해도 안전 상태에 머무는지 판단하는 알고리즘이다.

Request[i]는 스레드 T[i]의 요청 벡터이고, Request[i][j] = k라면 스레드 T[i]가 자원 R[j]를 최대 k개 요청한다는 것이다.

1. Request[i] <= Need[i]면 2번 과정으로 가고, 아니라면 안전 상태가 아니다.

2. Request[i] <= Available[i]면 3번 과정으로 가고, 아니라면 아직 자원이 부족하니 기다리게 한다.

3. 시스템이 스레드 T[i]에게 자원을 할당해준 것처럼 시뮬레이션을 돌려보고 안전 상태라면 자원 할당을 허가한다.

(Available -= Request[i], Allocation[i] += Request[i], Need[i] -= Request[i])

---

 

 

 

7. 교착 상태 탐지

---

시스템이 교착 상태 예방, 교착 상태 방지 알고리즘을 사용하지 않는다면 교착 상태가 발생할 수 있다. 그래서 이런 환경에 있으면 다음 알고리즘은 반드지 지원해야 한다.

 

- 교착 상태가 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘

- 교착 상태로부터 회복하는 알고리즘

 

교착 상태 탐지는 각 자원의 유형이 한 개씩 있는 경우, 각 자원의 유형이 여러 개 있는 경우로 나뉘게 된다.

---

1) 각 자원의 유형이 한 개씩 있는 경우

모든 자원이 한 개의 인스턴스만 있다면, 자원 할당 그래프의 변형인 대기 그래프를 사용해 교착 상태 탐지 알고리즘을 정의할 수 있다. 대기 그래프는 자원 노드를 없애고, 적절하게 간선을 결합한 것이다.

 

(a)에 있는 자원 노드를 제거하여 (b)인 대기 그래프를 만든다.

이것도 대기 그래프가 사이클이 존재할 경우 교착상태가 존재할 수 있다. 그래서 여기서도 주기적으로 그래프에서 사이클을 탐지하는 알고리즘을 호출한다. 이 알고리즘의 시간복잡도는 O(N^2)이고, N은 노드의 수이다.

 

하지만 대기 그래프는 각 유형의 자원이 여러 개인 경우 사용할 수는 없다.

---

2) 각 유형의 자원을 여러 개 가진 경우

이때는 은행원 알고리즘과 아주 비슷하게 교착 상태를 확인하는 알고리즘을 사용한다.

- Available: 각 종류의 자원이 현재 몇 개 사용할 수 있는지 나타내는 크기가 m인 벡터

- Allocation: 각 스레드에 현재 할당된 자원의 개수를 나타내는 크기가 n x m인 행렬

- Request: 각 스레드가 현재 요청 중인 자원의 개수를 나타내는 크기가 n x m인 행렬

 

알고리즘은 다음 과정으로 동작한다.

1. Work = Available (크기 m 벡터), Finish(크기 n 벡터)를 만든다. Allocation[i] != 0이면 Finish[i] = false이고, Allocation[i] = 0이면 Finish[i] = true이다.

2. Finish[i] == false && Request[i] <= Work인 i를 찾는다. 없으면 4번으로 넘어간다.

3. Work += Allocation[i], Finish[i] = true로 설정하고 2번으로 돌아간다.

4. Finish[i] = false인 i가 남아있으면 현재 스레드 T[i]가 교착 상태에 빠진 것으로 간주한다.

 

이 알고리즘은 은행원 알고리즘의 안전성 알고리즘과 엄청 비슷하다고 보면 된다.

- 과정1에서 현재 스레드에 할당된 자원이 아예 없으면 그 스레드는 작업을 마친 것으로 간주하는 것

- 은행원 알고리즘의 Need는 미래에 요청할 모든 자원, 이 알고리즘의 Request는 현재 요청중인 자원들

이 차이점만 존재한다.

---

3) 탐지 알고리즘 사용

교착 상태가 일어나는 시점은 어떤 스레드가 자원을 요청했는데, 그것이 즉시 만족되지 못하는 시점이 보통적인 상황이다.

그래서 자원을 요청할 때마다 탐지 알고리즘을 호출하는 경우도 있지만, 이러면 오버헤드가 너무 크다. 교착 상태는 궁극적으로 시스템의 처리율을 감소시키고, CPU 이용률을 떨어뜨리므로 보다 더 효율적인 호출을 위해서 정해진 시간 간격으로 호출하거나, CPU 이용률이 일정 이하로 떨어질 경우 호출하는 방법을 사용한다.

---

 

 

 

8. 교착 상태로부터 회복

---

탐지 알고리즘이 교착 상태가 존재한다고 결정하면, 이를 해결할 방법중 하나가 시스템이 자동으로 교착 상태를 회복하게 만드는 것이다.

교착 상태를 없애는 방법은 두 가지가 있는데, 하나는 순환 대기를 없애기 위해 한 개 이상의 스레드를 중지(abort)하는 방법이고, 나머지 하나는 교착 상태에 있는 하나 이상의 스레드들로부터 자원을 선점(preemp)하는 것이다.

---

1) 프로세스와 스레드의 종료

- 교착 상태 프로세스를 모두 중지: 확실히 교착 상태 사이클을 없앨 수 있지만, 종료하는데 비용이 크다.

- 교착 상태가 제거될 때까지 한 프로세스씩 중지: 프로세스가 중지될 때마다 교착 상태 탐지 알고리즘을 호출하여 비용이 크다.

 

프로세스 중지는 매우 어려운 일이다. 왜냐하면 프로세스가 파일을 갱신하는 도중에 중지하면 파일은 부정확한 상태가 되고, mutex 락을 점유한 상태로 공유 데이터를 갱신하고 있었다면 무결성도 보장할 수 없고, 복구할 때 mutex 락을 사용가능한 상태로 복구해야 한다.

거기다가 한 프로세스씩 중지를 하게 된다면 어떤 프로세스를 중지할지도 결정해야 한다. 

---

2) 자원 선점

자원 선점을 사용하여 교착 상태를 제거한다면, 교착 상태가 깨질 때까지 사이클인 프로세스의 자원을 선점해 다른 프로세스에 할당해야 한다.

 

이때 선점을 한다면 아래 세 가지 상황을 고려해야 한다.

- 희생자 선택: 어느 자원과 어떤 프로세스들이 선점될 것인지?

- 후퇴: 프로세스로부터 자원을 선점하면 이 프로세스는 어떻게 할지?

- 기아 상태: 자원들이 동일한 프로세스로부터 항상 선점되지 않는 것을 어떻게 보장하는지? (기아 상태가 발생하지 않는다는 것을 어떻게 보장하는지?)

---