Deadlock 해결 방법으론 다음 세가지가 존재한다
Deadlock Prevention methods: 예방
Deadlock Avoidance methods: 회피
Deadlock detection and recovery methods: 탐지 및 복구

Deadlock Prevention methods:

데드락 예방

4개의 dead lock 발생 필요 조건 중 하나를 제거
그렇다면 Deadlock이 절대 발생하지 않는다

Exclusive use of resources
Non-preemitible resources
Hold and wait
Circular wait

1. 모든 자원을 공유 허용

Exclusive use of resources 조건을 제거
현실적으로 불가능하다

2. 모든 자원에 대한 선점 허용

Non-preemitible resources 조건을 제거
누구던지 자원을 뺏어갈 수 있게 만든다.
현실적으로 불가능

유사한 방법으로 구현할 수는 있다.

프로세스가 할당 받을 수 없는 자원을 요청한 경우,
기존에 가지고 있던 자원을 모두 반납하고 작업을 취소.
이후 처음 혹은 체크포인트부터 다시 시작

이는 심각한 자원 낭비를 발생시키므로 비현실적이다

3. 필요한 자원을 한번에 모두 할당

=Totally allocation
Hold and wait 조건 제거
필요하지 않은 순간에도 자원을 가지고 있어야 하므로 자원 낭비 발생
무한 대기 현상이 발생할 수 있다.

4. Circular wait 조건 제거

3번 Totally allocation을 일반화 한 방법
자원들에게 순서를 부여하고, 프로세스는 자원 순서의 증가 방향으로만 자원 요청 가능
Deadlock을 완벽하게 예방할 수 있지만, 자원 낭비 발생

Deadlock Avoidance methods

데드락 회피
Deadlock의 발생을 막을 수 있지만
항상 시스템을 감시하고 있어야 하므로 overhead가 높으며,
Safe state유지를 위해 사용되지 않는 자원이 존재하므로 자원사용률이 낮아진다.
또한 프로세스수와 자원수가 고정되어 있으며 필요한 최대 자원 수를 알고 있어야 한다는
가정이 필요하므로 비현실적이다.

시스템의 상태를 계속 감시하다가
시스템이 deadlock상태가 될 가능성이 있는 자원 할당 요청을 보류한다.
시스템을 항상 safe state로 유지한다.

Safe state

모든 프로세스가 정상적 종료 가능한 상태를 말하며
deadlock상태가 되지 않을 수 있음을 보장하는 Safe sequence가 존재하다면
Safe state라고 말할 수 있다.

Unsafe state

deadlock 상태가 될 가능성이 있는 상태이며
unsafe state에서 반드시 deadlock이 발생한다는 의미는 아니다.

작동 예제

Deadlock avoidance를 설명하기 위해 다음과 같은 가정을 하자.
1. 프로세스의 수가 고정됨
2. 자원의 종류와 수가 고정됨
3. 프로세스가 요구하는 자원 및 최대 수량을 알고 있음
4. 프로세스는 자원을 사용 후 반드시 반납한다
(현실적인 조건은 아님)

다익스트라 알고리즘-Banker's algorithm

Deadlock avoidance를 위한 간단한 이론적 기법
한 종류의 자원이 여러개 존재한다고 가정하고
시스템을 항상 safe state로 유지하는 알고리즘이다.

같은 타입의 자원 10개와 프로세스 3개가 존재한다고 가정하자.
Max. Claim: 최대 필요수
Cur. Alloc.: 현재 할당량
Additional Need: 앞으로 필요한 수

현재 3개의 프로세스에 할당된 자원의 수는 8. 즉 2개의 할당가능한 자원이 남아있을때,
1. P1에 2개의 자원을 할당하여 Max를 맞춰 실행. 이후 반납(남은 자원 3)
2. 남은 자원 3개를 P3에 할당하여 Max를 맞춰 실행 이후 반납(남은 자원 5)
3. 남은 자원 5개 중 4개를 P2에 할당하여 Max를 맞춰 실행 이후 반납(남은 자원 10)

이때 실행 종료 순서는 P1->P3->P2이고 이는 곧 Safe sequence이다.
즉 프로세스들이 모두 자기 일을 마칠 수 있는 순서가 안전 순서이며,
현재 상태에서 Safe sequence가 하나 이상 존재하면 안전 상태라고 말할 수 있다.

다음 상황에서 남은 자원은 2개. 하지만 세 프로세스의 앞으로 필요한 자원의 수가
모두 2 이상이므로 세 프로세스 중 어느 하나의 프로세스도 Max를 맞춰줄 수 없다.

이 상태에서 Safe sequence를 찾을 수 없으므로 Unsafe state가 되고,
임의의 순간에 세 프로세스들이 모두 세개 이상의 단위자원을 요청하는 순간
시스템은 Deadlock에 빠지게 된다.

Banker's Algorithm은 Unsafe state를 만들지 않기 위해 자원 할당을 요청 받았을 때 시뮬레이션을 돌려본다.
State - 1 상태에서, P1이 1의 자원을 요구했다고 가정하면,
자원을 줬다고 가정하고, 주고 난 후 상황에서 Safe sequence가 존재하는지 여부를 시뮬레이션 돌려본다.
주고 난 후 상황인 1-1에서 Safe sequence가 존재하므로(P1->P3->P4)
자원할당을 Accept한다.

P2가 자원을 요구하는 1-2상황에서는 Safe sequence가 존재하지 않는 Unsafe state 상황이 발생하므로,
자원할당을 거부Reject한다.

Habermann's algorithm

다익스트라 알고리즘의 확장이며, 여러 종류의 자원을 고려한다.
여러 타입의 자원과 각 타입마다 자원의 수가 다를 때도 사용할 수 있다.
마찬가지로 시스템을 항상 safe state로 유지하는 알고리즘이다.

이번엔 자원의 종류가 Ra, Rb, Rc 세 종류가 있으며,
각 자원의 개수는 (10, 5, 7)개이다.
Babker's algorithm과 동일한 방법으로, 현재 남은 자원의 수로
Safe sequence가 존재하는지 여부를 검사해서, 존재한다면 Safe state가 된다.
단지 자원의 종류와 그 수만 달라졌을 뿐이다.

Deadlock Detection and Recovery methods

예방도, 회피도 안된다면, 그냥 deadlock이 발생하게 두고 해결하겠다.
이를 위해 deadlock탐지와 해결 두가지 단계로 이루어진다.

Deadlock Detection

deadlock 검출을 위해 사용되는 방법들

Resource Allocation Graph(RAG)

deadlock model인 graph model을 좀 더 확장하여 사용
방향성이 있는 bipartite Graph를 사용한다.

bipartite Graph
이분그래프
https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

그래프 G는 N와 E로 구성된다.
N은 Node. 프로세스 노드Np와 리소스 노드Nr들의 집합이다.

E는 Edge.
e(Pi, Rj) 즉 P노드에서 R노드로 향하는 엣지는 자원을 요청함을 의미하고
e(Rj, Pi) 즉 R노드에서 P노드로 향하는 엣지는 자원을 할당했음을 의미한다.

이분그래프이기 때문에 Np->Nr / Nr->Np로 향하는 엣지만 존재한다.

자원은 여러개의 타입이 있을 수 있다.
Rk는 K타입의 자원R을 의미하고,
Tk는 Rk의 단위자원 수를 의미한다. 즉 K타입의 자원이 몇개 있는가를 의미한다.
∣(a,b)∣는 a에서 b로 향하는 엣지의 수를 의미한다.

RAG를 사용하여 표현한 자원의 요청/할당이다.
R노드 안에 존재하는 동그라미가 자원. 동그라미의 수는 자원의 숫자T이며
P노드에서 R노드로 향하는 화살표는 자원을 요청했음을 표현한다.

RAG를 사용한 deadlock 감지

Graph Reduction

주어진 RAG에서 edge를 하나씩 지워가는 방법이다.

edge를 하나씩 지워나갔는데, 모든 edge가 제거되었다면
Completely reduced라 하고, Deadlock에 빠진 프로세스가 없음을 알 수 있다.

반대로 지울 수 없는 edge가 존재한다면 Irreducible이라 하고
하나 이상의 프로세스가 deadlock상태임을 의미한다.

지울수 있는 edge를 판별하는 법은 다음과 같다.
필요한 자원을 모두 할당받을 수 있는 프로세스를 Unblocked process라 하고,
Unblocked process에 연결된 edge를 모두 지우는 방법이다.

위 수식을 해석하자면
프로세스 Pi는 다음 조건을 만족할 때 Unblocked process이다.

∀
for all. 모든것에 대하여 라는 의미

프로세스가 요구하는 모든 자원에 대해, 남은 자원의 수(Tj - Rj. Rj는 할당된 수를 의미)가 더 클 때
프로세스 Pi는 Unblocked process이다.


위와 같은 그래프에서 Unblocked 프로세스는 하나는 P1이다.
그러면 P1에 연결된 모든 간선을 제거한다.

이 상태에서 다시 Unblocked Process를 찾는다.
이 상황에서 P2는 Unblocked Process이다.

모든 간선이 지워졌으므로, 이 RAG는 Deadlock이 검출되지 않았다.

다른 예제를 보자.
이 상황에서 Unblocked Process는 P3이다.

P3에 연결된 간선들을 지우고 다시 Unblocked Process를 찾았으나, 찾지 못하였다.
이러한 상황은 Deadlock Process가 존재한다고 알 수 있다

이렇게 RAG를 통해 Deadlock을 찾는다.
이 방법은 일정 주기에 따라 수행하기 때문에, 검사 주기에 영향을 받고
Node 수가 많은 경우 Overhead가 크다.

Deadlock avoidance와의 차이점은 다음과 같다.
avoidance는 최악의 경우를 생각하여 앞으로 일어날 일을 고려한다.
detection은 최선의 경우를 생각하여 현재 상태만 고려한다.
avoidance는 절대 deadlock이 발생하지 않지만, Detection은 발생할 수 있으므로
Recovery 과정이 필요하다.

Deadlock Recovery

Deadlock을 검출한 후 해결하는 과정이다.

1. Process termination

Deadlock상태에 있는 프로세스들 중 일부를 종료시킨다.
강제종료된 프로세스는 이후에 재시작된다.

Deadlock상태에 빠져 있는 프로세스들 중 누구를 종료시킬지 결정하기 위한 기준이 필요하다.
이를 Termination cost model이라 한다.
이 cost model은 우선순위, 종류, 총수행시간, 남은 수행시산, 종료비용 등
다양한 종류가 있으며 적절한 조건을 선택하여 기준으로 삼는다.

Lowest termination cost process first

종료비용이 가장 적은 프로세스를 먼저 종료시킨다.
가장 심플하고 오버헤드가 적지만 이 프로세스를 종료시켜도 deadlock상태가 해소되지 않는,
불필요한 프로세스들이 종료될 가능성이 높은 단점이 있다.

Minimum cost recovery

최소 비용으로 deadlock상태를 해소할 수 있는 process를 선택한다.
모든 경우의 수를 고려해야 하므로 복잡하고 오버헤드가 크다 O(2^n)

2. Resource preemption

Deadlock상태 해결을 위해 선점할 자원을 선택한다.
선정 된 자원을 가지고 있는 프로세스에서 자원을 빼았는다.
(자원을 빼앗긴 프로세스는 강제종료된다)
Deadlock상태가 아닌 프로세스가 종료될 수도 있다.

마찬가지로 선점할 자원을 선택하는데 필요한 기준이 필요하다.

따라서 Preemption cost model이 필요하며,
이는 Minimum cost recovery method를 사용하는데,
Resource preemption의 시간복잡도는 O(r)이다.
-why? 하나씩 뺏어보면서 확인하면 되니까

Checkpoint restart method

프로세스의 수행 중 특정지점마다 context를 저장하여
Rollback을 위해 사용한다.
프로세스 강제종료 후 가장 최근의 checkpoint에서 재시작한다.