OS ch07. Deadlocks

이번 장에서는 데드락의 개념과 이를 방지하거나 회피하는 여러 방법들을 소개한다.

Deadlock이란?

Deadlock(교착상태)은 여러 프로세스가 서로가 가진 자원을 기다리면서 더 이상 진행하지 못하는 상태다. 정확히는 blocked 상태의 프로세스 집합이 있고, 그 집합에 속한 각 프로세스가 어떤 자원을 이미 가지고 있으면서 동시에 다른 프로세스가 가진 자원을 기다리는 상황이다.

예를 들어 테이프 드라이브가 2개 있고 P1, P2가 각각 하나씩 가지고 있는데 둘 다 하나가 더 필요하다면, P1은 P2가 가진 자원을 기다리고 P2는 P1이 가진 자원을 기다린다. 아무도 먼저 자원을 놓지 않으면 두 프로세스는 영원히 진행할 수 없다.

세마포어 예시로도 확인해보자. 세마포어 A와 B가 1로 초기화되어 있다고 하자.

P0              P1
wait(A);        wait(B);
wait(B);        wait(A);

P0가 먼저 A를 획득하고, P1이 먼저 B를 획득하면 이런 상황이 된다.

P0: A를 가진 상태로 B를 기다림
P1: B를 가진 상태로 A를 기다림

좀 더 이해하기 쉽게 실생활 예시로 확인해보자.
위 그림처럼 좁은 다리에 양쪽의 차들이 오고가는 상황에서, 각 자동차는 다리의 한 구간을 차지하고 있고, 앞으로 가려면 앞 구간이 비어야 한다.

자동차    = 프로세스
다리 구간  = 자원
구간 차지  = 자원 할당
앞 구간 대기 = 자원 요청

아무도 뒤로 물러나지 않으면 전체가 멈춘다. 이럴때는 차들이 가위바위보를 해서 진 쪽이 후진해야한다. 운영체제 관점에서는 이것을 자원 선점(resource preemption) 또는 rollback이라고 볼 수 있으며, 진 쪽이 후진을 했는데 이긴 쪽에서 차가 끊임없이 몰려오면 starvation이 발생할 수 있다.

---

Deadlock 발생의 4가지 필요 조건

Deadlock은 다음 4가지 조건이 동시에 만족될 때 발생한다.

1. Mutual Exclusion: 하나의 자원을 한 번에 하나의 프로세스만 사용할 수 있는 상태다. 예를 들어 프린터는 여러 프로세스가 동시에 사용할 수 없다.

2. Hold and Wait: 프로세스가 최소 하나의 자원을 이미 가지고 있으면서(hold), 다른 프로세스가 가진 추가 자원을 기다리는(wait) 상태다.

3. No Preemption: 다른 프로세스가 가진 자원을 강제로 빼앗을 수 없는 상태다. 자원을 갖고있는 프로세스가 스스로 반납하기 전까지는 그 자원을 가져올 수 없다.

4. Circular Wait: 프로세스들이 원형으로 서로의 자원을 기다리는 상태다. 아래의 그림처럼 P1이 P6의 자원을 기다리고, P6은 P3의 자원을, P3는 P4의 자원을, P4는 다시 P1의 자원을 기다려 닫힌 고리가 만들어진다.

---

System Model

system model은 데드락 상황을 명확히 묘사하고 분석하기 위해 사용하는 개념으로, 이 모델은 프로세스가 자원을 어떻게 요청하고 사용하는지, 그리고 그 관계를 시각적으로 어떻게 표현하는지를 정의한다.

• 자원 유형 R1,R2,...,Rm: 서로 다른 유형의 자원들을 나타낸다.
• 각 자원 유형 안에는 똑같은 역할을 수행하는 여러 개의 인스턴스(개별 자원 개수)가 포함될 수 있다.
• 각 프로세스는 자원을 다음의 순서로 사용한다.
  • request: 프로세스가 작업을 위해 자원을 요청한다.
  • use: 자원을 성공적으로 확보해 사용한다.
  • release: 프로세스가 작업을 마치고 종료하기 전에 사용했던 자원을 반납한다.

---

Resource-Allocation Graph

자원 할당 그래프란 자원 할당 상태를 보여주는 그래프로, 데드락을 눈으로 확인하기 위한 도구라고 이해하면 좋다.

• 정점
  • P = {P1,P2,...,Pn}: 프로세스 집합
  • R = {R1,R2,...,Rm}: 자원유형 집합
• 간선
  • Pi → Rj : Request Edge (Pi가 Rj를 요청 중, 아직 받지 못한 상태)
  • Rj → Pi : Assignment Edge (Rj의 인스턴스가 Pi에게 할당된 상태)
• 구성요소들의 시각적 표현은 아래와 같다.
  

그래프에서 Deadlock 판단하기

자원할당 그래프를 보고 데드락 가능성을 판단할 수 있다.

위 그림에서 그래프 화살표를 따라가다보면, 빨간색 선과 파란색 선으로 표시해둔것과 같이 cycle이 형성이 된다. 이때 각 프로세스는 이미 각 자원을 확보한 상태에서 다른 자원을 기다리고 있고, 자원을 강제로 뺏을 수도 없는 상태다.

이처럼 cycle이 존재하고, 데드락 발생조건 4가지가 모두 만족되었으므로 시스템은 데드락 상태에 빠진것이다.
이 예시 역시 중간 부분을 보면 cycle이 형성이 되었다. 이때 P2,P4가 자원을 보유하고 있지만, 다른 프로세스의 자원을 추가로 요청해 대기하고 있진 않다. 즉 Hold & Wait 조건을 만족시키지 않는다.

그럼 P2나 P4는 곧 작업을 마치고 갖고있던 자원을 반납할 것이고, 반납된 자원은 대기 중이던 다른 프로세스에게 넘겨질 수 있으므로, 결과적으로 cycle이 깨지게 되며 데드락 상태에 빠지지 않는다.

---

위 예시들을 통해, 자원 할당 그래프에서의 cycle의 유무에 따라 아래처럼 일반화할 수 있다.

• Cycle 없음 → Deadlock 없음
• Cycle 있음 + 자원 인스턴스 1개 → Deadlock 확정
• Cycle 있음 + 자원 인스턴스 여러 개 → Deadlock 가능성만 있음 (cycle 밖 프로세스가 자원을 반납하면 해결될 수 있음)

---

Deadlock Handling 방법

데드락 처리 방법은 결국 데드락 발생조건 4가지를 어떻게 다룰 것인가에 대한 이야기다.

방법	설명
Prevention / Avoidance	Deadlock에 빠지지 않도록 보장
Detection + Recovery	Deadlock 허용 후 감지하고 복구
무시	Deadlock이 없는 것처럼 취급 (대부분의 OS가 사용)

첫번째 두번째 방식들은 지속적으로 자원 상태를 체크해야하므로 시스템에 엄청난 오버헤드(CPU 및 메모리 자원 소모)를 발생시킨다. 따라서 아주 크리티컬한 애플리케이션을 운영하는게 아니라면 그냥 데드락을 무시하는게 더 경제적일 수 있다. 이때는 데드락이 발생해 시스템이 먹통이 되면 사용자가 직접 전원 버튼을 누르거나 리셋을 시킨다.

---

Deadlock Prevention

Prevention은 곧 "원천봉쇄"이다. 4가지 조건 중 하나라도 만족을 못하게끔 하여 데드락에 빠지지 않게 한다.

Mutual Exclusion 제거

공유 가능한 자원(읽기 전용 파일 등)은 mutual exclusion이 필요 없지만, 프린터처럼 공유 불가능한 자원은 반드시 필요하다. 완전 제거는 현실적으로 어렵다.

Hold and Wait 제거

두 가지 방법이 있다.

• 실행 전 모든 자원 한 번에 요청- 자원 이용률이 낮아진다. 나중에 필요한 자원까지 처음부터 잡고 있어야 하기 때문이다.
• 아무 자원도 없을 때만 요청 가능- 자원을 효율적으로 사용하기 어렵고, starvation이 발생할 수 있다.

No Preemption 제거

자발적으로 자원을 반납하게 만들어 실질적으로 자원을 강제로 빼앗는것과 같은 효과를 낸다.

어떤 자원을 이미 쥐고있는 프로세스가 추가로 다른 자원을 요청했는데 그 자원을 즉시 받을 수 없다면 기존에 갖고있던 자원을 모두 반납하게 한다.

해당 프로세스가 작업을 재개하려면, 방금 추가로 요청했던 자원과 기존 자원들을 모두 한꺼번에 확보해야만 실행될 수 있다.

Circular Wait 제거

모든 자원 유형에 고유 번호를 할당한 뒤, 프로세스들이 반드시 번호가 증가하는 방향으로만 자원을 요청할 수 있도록 규칙을 정한다. 이러면 모든 요청이 한쪽 방향으로만 흐르기 때문에 circular wait가 생길 수 없다.

---

Deadlock Avoidance

Aviodance는 "회피"이다.

Prevention이 특정 요청 방식 자체를 금지하는 것과 달리, Avoidance는 요청이 들어올 때마다 안전한지 검사한 뒤 허용한다. Avoidance의 목표는 시스템이 결코 데드락 발생 가능성이 있는 unsafe state에 진입하지 않도록 관리하는 것이다.

이 방식을 사용하기 위해서는 추가적인 사전 정보가 필요하며, 각 프로세스는 작업을 시작하기 전에 자신이 특정 유형의 자원을 최대 몇개까지 사용할 것인지 시스템에 미리 선언해야한다.

Safe State

Safe state란 모든 프로세스를 무사히 끝마칠 수 있는 safe sequence가 존재하는 상태다. 즉 데드락에 빠지지 않으면서 모든 프로세스에게 필요한 자원을 정상적으로 할당하고 종료할 수 있는 상태이다.

<P1,P2,...Pi,...Pn>의 순서열이 safe sequence이려면, 다음 조건을 만족해야한다.

임의의 프로세스 Pi가 추가로 요청할 수 있는 최대 자원량 <= 남아있는 여유자원 + 순서상 앞선 프로세스들에게 현재 할당된 자원

즉 safe state는 데드락이 존재하지 않고, unsafe state는 safe sequence가 존재하지 않아 데드락에 빠질 가능성이 존재하는 상태다.

---

Resource-Allocation Graph Algorithm (단일 인스턴스)

Avoidance를 시각적인 그래프로 하는 방법이다. 이 알고리즘은 각 자원 유형당 인스턴스가 오직 1개씩만 존재하는 시스템에서 데드락을 회피하기 위해 주로 사용된다.

Claim edge (점선): Pi → Rj
  → Pi가 미래에 Rj를 요청할 수 있음을 의미

요청 시:   claim edge → request edge
할당 시:   request edge → assignment edge
반납 시:   assignment edge → claim edge

claim edge의 역할

• 미래의 자원 사용 가능성 사전 선언
  claim edge는 프로세스가 실행되기 전, 미래에 특정 자원을 사용할 수도 있다는 사실을 점선으로 시스템에 미리 선언해두는 역할을 한다. 데드락 회피 방식은 사전에 각 프로세스가 최대 몇개의 자원을 쓸것인지에 대한 추가적인 정보가 반드시 필요한데, claim edge가 이 정보를 시각적으로 표현해준다.
• 자원 할당 전 사전 시뮬레이션
  프로세스가 미래에 자원을 필요로 하게 돼 점선이 request edge(실선)으로 바뀌었을때, 시스템은 즉시 자원을 내어주지않고 가상으로 자원을 할당해본다.
• unsafe state 탐지 및 회피
  가상으로 자원을 할당했다고 가정했을때, 이 claim edge를 포함해 그래프 내 닫힌 원(cycle)이 만들어진다면 시스템은 이를 데드락 위험이 있는 unsafe state로 판단한다.

이 그림은 unsafe state의 예시인데, 이 예시를 통해 자원 할당 그래프 알고리즘의 흐름을 다시 한번 따라가보자.

프로세스가 자원을 요청했을때(요청 간선 발생), 시스템은 프로세스의 요청을 허락해 할당 간선으로 바꿨다고 가정하고 가상의 선을 그려본다.

이때 할당 간선과 그래프 내 모든 선들(claim edge포함)이 연결돼 하나의 cycle이 형성되는지 검사한다.

만약 cycle이 만들어진다면, 시스템은 이를 unsafe state로 판단해 자원을 당장 주지 않고, safe state가 유지될때까지 자원 할당을 미룬다.

---

Banker's Algorithm

Banker's Algorithm은 자원 타입마다 인스턴스가 여러 개 있을 때 사용하는 deadlock avoidance 알고리즘이다. 은행이 고객한테 돈을 빌려줄 때 고객이 자산관리를 잘 못해서 파산하진 않을지 계산한 뒤 돈을 빌려주는 것처럼, 특정 프로세스가 자원을 요청했을 때 자원을 할당해줘도 시스템이 safe state를 유지할 수 있는지 체크하는 개념이다.

사용 조건은 다음과 같다.

• 각 프로세스는 자신의 최대 자원 사용량을 미리 사전에 선언해야 한다.
• 프로세스는 자원을 얻기 위해 대기해야할 수도 있다.
• 자원을 다 사용한 후에는 정해진 시간 내에 모두 반납해야 한다.

자료구조

이 알고리즘은 시스템의 자원 상태를 파악하기 위해 아래의 4가지 자료구조를 사용한다.

프로세스 수를 n, 자원 타입 수를 m이라고 하자.

• Available(여유분): 현재 남아있는 여유 자원의 개수
  Available[j] = k→ 자원 타입 Rj의 사용 가능한 인스턴스가 k개라는 뜻

• Max(최대 요청량): 각 프로세스가 최대로 필요로 하는 자원의 개수
  Max[i, j] = k→ 프로세스 Pi가 자원 Rj를 최대 k개까지 요청할 수 있다는 뜻

• Allocation(할당량): 각 프로세스에 이미 할당돼있는 자원의 개수
  Allocation[i, j] = k → 프로세스 Pi에게 현재 자원 Rj가 k개 할당돼있다는 뜻

• Need(추가 요구량): 프로세스가 앞으로 추가적으로 더 요구할 수 있는 자원의 개수
  Need[i, j]→ 프로세스 Pi가 작업 완료를 위해 Rj가 앞으로 k개 더 필요하다는 뜻

  Need = Max - Allocation

---

Safety Algorithm

현재 상태가 safe state인지 검사하는 알고리즘이다.
즉 Banker's algorithm은 자원 요청을 승인할지 결정하는 알고리즘이며, 그 과정에서 safety algorithm을 사용한다.

흐름은 아래와 같다.

현재 남아있는 여유분(Available)으로 특정 프로세스의 추가 요구량(Need)을 만족시킬 수 있는지 확인한다.

만족시킬 수 있다면, 해당 프로세스에게 자원을 줬다고 가정하고, 이 프로세스가 무사히 작업을 마치면 기존에 갖고있던 자원(Allocation)까지 모두 반납해 시스템의 여유분이 다시 늘어난것으로 계산한다.

이러한 과정을 반복해 모든 프로세스를 다 만족시킬 수 있는 처리 순서가 존재한다면, 시스템은 safe state에 있다고 판단하며, 반대로 끝까지 처리하지 못하는 프로세스가 남는다면 unsafe state가 된다.

무슨말인지 모르겠으니까 예시를 통해 알아보자.

---

Banker's Algorithm 예시

먼저 5개의 프로세스(P0~P4)와 3가지의 자원 유형(A,B,C)이 있는 시스템을 가정한다.
전체 자원 개수는 A 10개, B 5개, C 7개이며, 현재 여유분(Available)은 A 3개, B 3개, C 2개라 하자.
각 프로세스의 현재 상태는 다음과 같다.

Available = (3, 3, 2)

        Allocation   Max         Need
        A  B  C     A  B  C     A  B  C
P0      0  1  0     7  5  3     7  4  3
P1      2  0  0     3  2  2     1  2  2
P2      3  0  2     9  0  2     6  0  0
P3      2  1  1     2  2  2     0  1  1
P4      0  0  2     4  3  3     4  3  1

Safety Algorithm 동작 과정

현재의 여유분 (3,3,2)를 가지고 어떤 프로세스의 요구량을 만족시켜줄수있는지 차례대로 확인한다.

• P0 확인: 요구량(7,4,3)이 현재 여유분(3,3,2)보다 크기 때문에 자원을 줄 수 없다. 다음으로 넘어간다.
• P1 확인: 요구량(1,2,2)이 여유분(3,3,2)보다 작거나 같으므로 만족시켜 줄 수 있다. P1에게 자원을 할당해주면 작업을 무사히 마치고 원래 갖고있던 자원까지 모두 반납한다. 결과적으로 여유분은 (5,3,2)로 늘어난다.
• P2 확인: A자원이 6개 필요한데 현재 여유분은 5개이므로 만족시킬 수 없다. 넘어간다.
• P3 확인: 요구량(0,1,1)을 여유분(5,3,2)으로 충분히 줄 수 있다. P3가 자원을 쓰고 모두 반납하면 여유분은 (7,4,3)이 된다.
• P4 확인: 요구량(4,3,1)을 여유분(7,4,3)으로 줄 수 있다. P4가 종료 후 자원을 반납하면 여유분은 (7,4,5)가 된다.
• 다시 P0 확인: 아까는 못 줬지만, 이제 여유분이 (7,4,5)로 늘어났으므로 P0의 요구량(7,4,3)을 만족시킬 수 있다. P0가 종료 후 반납하면 여유분은 (7,5,5)가 된다.
• 다시 P2 확인: 마찬가지로 이제 여유분이 (7,5,5)로 늘어났으므로 처리해줄 수 있다. P2가 자원을 모두 반납하면 최종 여유분은 (10,5,7)이 된다.

-> 모든 프로세스를 성공적으로 끝마쳤으며, 최종 여유분(10,5,7)이 시스템의 초기 전체 자원 개수와 정확히 일치한다. 모든 프로세스를 만족시켜줄 수 있는 safe sequence(P1,P3,P4,P0,P2)가 존재하므로, 이 시스템은 현재 safe state에 있다고 판단한다.

---

Resource-Request Algorithm

resource-request algorithm은 특정 프로세스가 실제로 자원을 요청했을 때 승인 여부를 판단하는 알고리즘이다. Pi의 요청 벡터를 Request_i라고 하자.
Request_i[j] = k→ 프로세스 Pi가 자원 Rj를 k개 요청했다는 뜻

흐름은 아래와 같다.

요청한 자원 수가 자신이 사전에 신고한 남은 필요량(Need)보다 작거나 같은지, 현재 시스템의 여유분(Available)보다 작거나 같은지 확인한다.

위 조건을 만족하면, 일단 자원을 줬다가 가정하고 Available, Allocation, Need 변수값을 업데이트한다.

변수를 업데이트한 상태에서, safety algorithm을 돌려본다.

그 결과 시스템이 여전히 safe state에 있다고 판명되면 실제로 자원을 할당해준다. 만약 unsafe state에 빠지게 되면 요청을 허락하지 않고, 변경했던 변수들을 모두 예전 값으로 복원시킨다.

이 역시 무슨 말인지 잘 모르겠으니 아래 예시를 통해 알아보자.

P1 Request 예제

만약 위 예시와 같이 safe state에서 P1 프로세스가 갑자기 A 1개, C 2개를 추가로 요청했다고 가정하자.

아래와 같이 조건을 검증한다.

Need(P1)    = (1, 2, 2)
Request     = (1, 0, 2)
Available   = (3, 3, 2)

Request <= Need      ✓
Request <= Available ✓

일단 유효한 요청으로 통과된다.
이제 진짜로 주기 전에 일단 줬다고 가정해본다. 그럼 여유분은 (3,3,2)에서 (1,0,2)를 뺀 (2,3,0)으로 줄어든다.

Available = (3, 3, 2) - (1, 0, 2) = (2, 3, 0)

이제 변경된 여유분(2,3,0)을 가지고 safety algorithm을 돌려본다.

Safety Algorithm 실행 → <P1, P3, P4, P0, P2> safe sequence 존재
→ 요청 (1, 0, 2) 승인

변경된 여유분으로도 P1의 남은 요구량(0,2,0)을 만족시킬 수 있으므로 P1을 먼저 종료시키고, P1이 끝나고 반납하는 자원이 합쳐지면 여유분이 다시 늘어나고, 연쇄적으로 아까처럼 다른 프로세스들도 모두 무사히 종료시킬 수 있음을 확인할 수 있다.

즉 가상으로 자원을 할당해봐도 여전히 시스템이 safe state를 유지한다는 것이 증명됐으므로, P1의 요청을 거절하지 않고 실제로 자원을 할당해준다.

---

Deadlock Detection

여태까지는 Deadlock Avoidance에 대해 학습하였다. 이제 avoidance 방식과 달리 시스템이 데드락에 빠지는 것을 미리 막지 않고 허용하되, 데드락에 빠졌음을 detect하고 이를 recovery하는 Deadlock Detection에 대해 알아보자.

deadlock detection 방식은 자원 유형의 인스턴스 개수에 따라 두가지 방식으로 나뉜다.

Single Instance- Wait-for Graph

자원 유형마다 인스턴스가 하나뿐인 경우 wait-for graph를 사용한다. Wait-for Graph는 Resource-Allocation Graph(자원 할당 그래프)를 단순화해 자원 노드를 빼고 프로세스 노드만 남긴 형태다.

그림은 아래와 같다.
(a): Resource-Allocation Graph
(b): Wait-for Graph
시스템은 주기적으로 이 그래프를 검사해 cycle이 존재하는지 확인한다. 인스턴스가 하나일때는 cycle의 존재가 곧 데드락 발생을 의미한다.

Resource-Allocation Graph: Pi → Rk → Pj
Wait-for Graph:            Pi → Pj

Cycle in wait-for graph → Deadlock

Cycle을 찾는 알고리즘의 시간 복잡도는 O(n²)이다. (정점 n개)

---

Multiple Instances- Detection Algorithm

자원 유형마다 인스턴스 개수가 여러 개면 wait-for graph만으로는 충분하지 않다. 이때는 다음 자료구조를 사용해 Detection Algorithm을 적용한다.

• Available: 각 자원 유형별 사용 가능한 자원 수
• Allocation: 각 프로세스가 현재 할당받은 자원 수
• Request: 각 프로세스가 현재 추가로 요청 중인 자원 수

Detection Algorithm은 Safety Algorithm과 매우 유사하지만 목적이 다르다. Safety Algorithm은 safe state인지 확인하고, Detection Algorithm은 현재 deadlock에 빠진 상태인지 확인한다.

흐름은 아래와 같다.

이미 할당받은 자원(Allocation)이 있는 프로세스들은 아직 작업이 안끝난것으로 간주하고, 아무 자원도 갖고 있지 않은 프로세스는 데드락에 관여하지 않는다고 본다.

아직 끝나지 않았고, 현재 여유분으로 요청(Request)을 만족시킬 수 있는 프로세스를 찾는다.

만족시킬 수 있다면, 해당 프로세스가 종료되어 자원을 반납한다고 가정하고 여유분에 더한다.

이런 과정을 반복했을 때, 끝까지 여유분으로 만족시켜주지 못해 끝나지 않은 프로세스가 남아있다면 시스템은 데드락 상태에 빠진것이라 판단하며, 해당 프로세스들이 데드락 유발 당사자임을 알 수 있다.

무슨 말인지 모르겠다. 이 역시 예시를 통해 살펴보자.

Detection 예시1- Deadlock 없는 경우

프로세스 P0~P4, 자원 A/B/C, 전체 (7, 2, 6), Available = (0, 0, 0)

P0 Request = (0, 0, 0) → 즉시 종료 가능
P0 종료 후: Work = (0, 0, 0) + (0, 1, 0) = (0, 1, 0)

이후 P2, P3, P1, P4 순서로 실행 가능
Safe sequence: <P0, P2, P3, P1, P4>
→ Deadlock 없음

Detection 예시2- Deadlock 발생한 경우

P2가 C 자원을 하나 더 요청: P2 Request = (0, 0, 1)

Available = (0, 0, 0)

P0 종료 후: Work = (0, 1, 0)

남은 프로세스 Request:
P1 = (2, 0, 2)
P2 = (0, 0, 1)
P3 = (1, 0, 0)
P4 = (0, 0, 2)

Work = (0, 1, 0)로 어떤 요청도 만족 불가

→ Deadlocked: P1, P2, P3, P4

즉 시스템은 남아있는 프로세스들이 무사히 끝날 수 있는지 아래와 같이 detection algorithm을 돌리낟.

• P0 종료: 현재 추가 요청량이 0인 P0는 가지고 있던 자원만 쓰고 종료할 수 있다. P0가 종료되면서 원래 갖고있던 자원 (0,1,0)을 반납해 시스템의 새로운 여유분이 된다.
• 나머지 프로세스 확인: 이제 여유분 (0,1,0)을 갖고 다른 프로세스들의 요청을 해결해줄 수 있는지 확인한다.
• 자원 부족: P2는 C 자원 1개 (0,0,1)을 더 달라고 요청했지만, 현재 여유분에는 C 자원이 없기 때문에 P2의 요청을 들어줄 수 없다. 마찬가지로 P1,P3,P4 역시 현재의 빈약한 여유분 (0,1,0)으로는 각자의 요구량을 채울 수 없다.
• 블록 상태: 결국 충분한 자원이 없어 P0를 제외한 P1,P2,P3,P4 모두가 작업을 진행하지 못하고 무한정 기다리는 블록 상태에 빠지게 된다.

-> detection algorithm은 가상으로 할당을 진행해본 결과 끝까지 만족시켜 주지 못하는 프로세스들이 남아있다는 것을 확인하고, 이를 통해 시스템은 현재 데드락이 발생했음을 감지하며, P1,P2,P3,P4가 그 범인들이라고 최종 판단한다.

---

Detection Algorithm Usage

Deadlock Detection Algorithm을 수행하는 빈도는 아래 두가지를 고려해 결정해야한다.
1. 데드락이 얼마나 자주 발생하는가
2. 데드락 발생 시 뒤로 돌려야하는(rollback) 프로세스가 얼마나 많은가

• Deadlock이 자주 발생한다면 detection도 자주 해야 하지만, 너무 자주 실행하면 오버헤드가 커진다.
• Detection을 임의의 시점에 실행하면 resource graph에 너무 많은 cycle이 존재할 수 있어 어떤 프로세스가 deadlock을 유발했는지 판단하기 어렵다.

즉 Detection은 정확성뿐 아니라 실행 비용과 시점도 중요하다.

---

Recovery from Deadlock

이제 데드락 감지 후 recovery하는 법에 대해 알아보자. 방법은 두 가지다.

1. Process Termination

방법	설명	단점
모든 deadlocked process 강제로 종료	확실하게 해결	이미 계산한 작업 전부 손실
deadlock이 풀릴때까지 한번에 하나씩 종료	비용 절감 가능	어떤 프로세스를 먼저 종료할지 결정 필요

종료할 프로세스 선택 기준:

• 프로세스 우선순위
• 지금까지 실행 시간 / 완료까지 남은 시간
• 사용 중인 자원 수 / 추가로 필요한 자원 수
  • 많은 자원을 가진 프로세스를 종료해야 단번에 자원 부족 해결이 가능하다.
• 종료해야 하는 프로세스 개수
• interactive process인가 batch process인가
  • interactive 작업은 강제로 종료시키더라도 곧바로 이어서 다시 실행되면 되므로 타격이 작다.
  • batch 작업은 한번 실행해두고 밤새 오랫동안 돌아가는 작업일 가능성이 높은데, 이처럼 처리해야할 일의 양이 많고 오랜 시간 진행된 작업을 강제로 종료하게 되면 타격이 매우 크다.

2. Resource Preemption

프로세스 자체를 죽이진 않고, 특정 프로세스(victim)가 갖고있던 자원만 강제로 빼앗아 deadlock을 해결하는 방식이다.

Victim Selection- 비용이 최소가 되는 프로세스를 victim(희생양)으로 선택한다.

Rollback- 자원을 빼앗긴 프로세스는 정상 실행이 불가능하므로 자원을 잃기 전의 safe state로 rollback한 뒤 나중에 다시 요청해 시작해야 한다.

Starvation- 만약 cost가 가장 적다는 이유로 동일 프로세스만 계속해서 희생양이 된다면, 해당 프로세스는 영원히 작업을 마치지 못하는 starvation 상태에 빠질 수 있다. 이를 방지하기 위해 특정 프로세스가 희생양으로 선택될 수 있는 횟수를 제한하는 등의 조치가 필요하다.