8.1 System Model

시스템은 경쟁하는 스레드들 사이에 분배되어야 할 유한한 수의 자원들로 구성
자원은 인스턴스들로 구성됨

프로세스는 다음 순서로만 자원을 사용 간으
1. 요청 : 요청 스레드는 자원을 얻을 때까지 대기
2. 사용 : 자원에 대해 수행
3. 방출 : 스레드가 자원 방출

이런 정보들은 기록됨

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

8.3 Deadlock Characterization

8.3.1 Necessary Conditions

교착 상태는 한 시스템에 다음의 조건이 동시에 성립될 때 발생

1. mutual exculsion : 최소한 하나의 자원이 비공유 모드로 점유되어야 한다.
   비공유 모드에서는 한 번에 한 스레드만 그 자원을 사용가능
2. Hold and wait : 스레드는 최소한 하나의 자원을 점유한 채, 현재 다른 스레드에 의해 점유된 자원을 추가로 얻디 위해 반드시 대기
3. 비선점 : 자원들을 선점할 수 없어야 한다.
4. 순환 대기 : 대기하고 있는 스레드의 집합에서 점유한 자원을 대기할 경우

8.3.2 Resource-Allocation Graph

자원 할당 그래프에서 사이클을 포함하지 않으면, 시스템 내에 어느 프로세스도 교착상태가 아님

resource type이 여러 개의 인스턴스를 가지면, 사이클이 반드시 교착상태는 아님

8.4 Methods for Handling Deadlocks

1. 문제를 무시하고, 교착 상태가 시스템에서 절대 발생하지 않는 척한다.
2. 교착 상태 예방, 회피
3. 교착 상태를 허용한 후, 다음에 복구

교착 상태 예방은 위의 4가지 조건 중 적어도 1개라도 성립되지 않도록 하는 것
교착 상태 회피는 스레드가 사용할 자원에 대한 부가적인 정보를 미리 제공할 것을 요구

8.5 Deadlock Prevention

8.5.1 Mutual Exclusion

상호 배제 조건인 적어도 하나의 자원은 공유가 불가능한 자원이어야 한다.
공유 가능한 자원은 배타적인 접근을 요구하지 않는다.

8.5.2 Hold and Wait

프로세스가 자원을 요청할 때, 다른 자원을 점유하지 않을 것을 보장한다.
1. 스레드가 자원을 전혀 갖고 있지 않을때만 자원 요청 가능
(다른 추가 자원을 요청 시, 갖고 있던 자원을 모두 방출

자원이 할당되었지만 장기간 사용되지 않을 수 있어서 자원 이용률이 낮다.
기아 문제가 발생할 수 있음

8.5.3 비선점

이미 할당된 자원이 선점되지 않아야 교착 상태가 된다.
어떤 자원을 점유하고 있는 스레드가 즉시 할당할 수 없는 다른 자원을 요청하면, 현재 점유하고 있는 모든 자원이 선점된다.

8.5.4 Circular Wait

모든 자원 유형에 전체적인 순서를 부여하여, 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구하는 것

8.6 Deadlock Avoidance

교착 상태를 예방하는 것은 4가지 조건 중 한개라도 허용하지 않으면 되지만, 성능 저하가 됨

교착 상태를 회피하는 방법은 자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구하는 것이다.
가장 단순하고 유용한 모델은 각 스레드가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구하는 것이다.
각 스레드가 요청할 각 유형의 자원의 최대 수 정보를 미리 안다면, 교착 상태에 들어가지 않는다.

8.6.1 Safe State

시스템 상태가 안전하다는 말은 시스템이 어떤 순서로든 스레드들이 요청하는 모든 자원을 교착 상태를 야기시키지 않고 차례로 모두 할당해 줄 수 있다는 것

시스템이 안전 순서를 찾으면 안전하다.
찾을 수 없다면 교착 상태가 될 수 있는 확률이 있다.

안전한 알고리즘을 짜서, 프로세스의 안전 순서를 실행시키면 되지만, 시스템이 더 많은 자원을 갖고있더라도 때에 따라 프로세스를 기다리게 할 수도 있음.

8.6.2 Resource Allocation Graph Algorithm

사이클이 안생기게 하여 교착상태를 피할 수 있음.

요청, 할당, 예약 간선

8.6.3 Banker's Algorithm

자원 할당 그래프 알고리즘은 종류마다 자원이 여러 개씩 있게되면 사용할 수 없다.
은행원 알고리즘에서는 자원이 여러 개씩 있더라도 사용가능

스레드가 시작할 때 스레드가 가지고 있어야 할 자원의 최대 개수를 자원 종류마다 미리 신고하여야 한다. 시스템은 안전 상태에 머무르게 되면, 자원 요청을 들어주고, 그렇지 않으면 그 스레드는 다른 스레드가 끝날 때까지 기다리게 된다.

8.7 Deadlock Detection

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

8.7.1 각 자원 유형이 1개씩 있는 경우

모든 자원들이 1개의 인스턴스만 있다면, 대기 그래프를 이용하여 교착 상태 탐지 알고리즘을 정의 가능

사이클을 탐지하는 알고리즘이 있어얗마

8.7.2 각 자원 유형이 여러 개인 경우

대기 그래프는 사용 못함
은행원 알고리즘을 사용해야함

8.7.3 Detection-Algorithm Usage

교착 상태가 얼마나 자주일어나는지
몇개의 스레드가 연루되는지

교착 상태가 자주 일어난다면, 탐지 알고리즘도 자주 돌려야함
오버헤드가 너무 크게 됨

8.8 Recovery from Deadlock

자동으로 교착상태로부터 회복되게 하는 것
스레드를 중지시키거나 하나 이상의 스레드들로부터 자원을 선점하는 것

8.8.1 Process and Thread Termination

1. 교착 상태 프로세스를 모두 중지 : 비용이 크긴함, 프로세스가 오랫동안 연산했을 가능성도 있고 결과들은 반드시 폐기해야함

2. 교착 상태가 제거될 때까지 한 프로세스씩 중지 : 각 프로세스가 중지될 대마다 탐지 알고리즘을 호출해야 하므로 오버헤드가 큼

프로세스의 우선순위
일을 종료하는데 필요한 시간
프로세스가 사용한 자원 유형과 수
프로세스가 종료되기 위해 더 필요한 자원의 수
얼마나 많은 수의 프로세스가 종료되어야 하는지

8.8.2 Resource Preemption

자원 선점을 이용하여 데드록을 제거하려면, 교착 상태가 깨어질때까지 프로세스로부터 자원을 계속 선점해나가야 함

1. 희생자 선택
2. 후퇴
3. 기아상태