7. Deadlocks

The Deadlock Problem

• 리소스를 보유한 상태로 다른 프로세스가 가진 리소스를 기다리는 프로세스 집합이 있을 때, 이들 사이에서 교착 상태(deadlock)가 발생함
• 예시:
  • 시스템에 테이프 드라이브가 2개 있음
  • $P_1$, $P_2$는 각각 하나의 드라이브를 점유하고 있으며, 상대방의 드라이브도 필요로 함
• 세마포어 예시:
  • 세마포어 A와 B는 1로 초기화됨

P_0:
  P(A);
  P(B);

P_1:
  P(B);
  P(A);

Deadlock Characterization

Deadlock은 다음의 네 가지 조건이 동시에 만족될 때 발생할 수 있음 (필수 조건):

• Mutual exclusion: 하나의 리소스는 오직 한 프로세스만 사용할 수 있음
• No preemption: 리소스는 그것을 보유한 프로세스가 작업을 마치고 자발적으로 해제할 때만 회수될 수 있음
• Hold and wait: 최소 하나의 리소스를 보유한 프로세스가, 다른 리소스를 기다리는 상태
• Circular wait: 프로세스 집합 $\{P_0, P_1, \dots, P_n\}$이 존재하며,
  • $P_0$는 $P_1$이 보유한 리소스를 기다리고,
  • $P_1$은 $P_2$가 보유한 리소스를 기다리며,
  • ...
  • $P_n$은 $P_0$이 보유한 리소스를 기다리는 순환 대기 상태가 존재함

Traffic Deadlock

차량이 사방에서 진입하면서 서로를 막고 있어 한 대도 앞으로 나아가지 못하는 상태
이는 deadlock의 실질적인 예시이며, circular wait과 유사한 형태임

(해당 슬라이드에는 사거리 교차로에서 발생한 교착 상태를 보여주는 일러스트가 포함되어 있음)

Real World Traffic Deadlock

실제 도로에서 발생한 교통 교착 상태의 사진
차량이 서로 교차지점에서 멈춰 다른 차량의 이동을 막고 있음

Resource-Allocation Graph

• 정점 $V$와 간선 $E$로 구성된 그래프
• $V$는 두 가지 유형으로 나뉨:
  • $P = \{P_1, P_2, \dots, P_n\}$: 시스템 내의 프로세스 집합
  • $R = \{R_1, R_2, \dots, R_m\}$: 시스템 내의 리소스 유형 집합
• 간선의 유형:
  • 요청 간선 (request edge): $P_i \rightarrow R_j$
  • 할당 간선 (assignment edge): $R_j \rightarrow P_i$
• 프로세스: 원형으로 표현됨
• 리소스 유형 (4개의 인스턴스): 사각형 내부에 점으로 표현됨
• $P_i$가 $R_j$의 인스턴스를 요청:
  $P_i \rightarrow R_j$
• $P_i$가 $R_j$의 인스턴스를 보유:
  $R_j \rightarrow P_i$

Example of a Resource Allocation Graph

그래프 예시:

• $P_1$, $P_2$, $P_3$는 각각 리소스를 요청 또는 보유하고 있음
• $R_1$부터 $R_4$까지 다양한 리소스가 있음
• 각 리소스 유형은 여러 인스턴스를 가질 수 있으며, 점(dot)으로 표현됨

Basic Facts

• 그래프에 cycle(사이클)이 없으면 → deadlock 발생 불가
• 그래프에 cycle이 있으면 → 다음 조건에 따라 다름:
  • 리소스 유형당 인스턴스가 1개뿐이면, 반드시 deadlock
  • 리소스 유형당 인스턴스가 여러 개면, deadlock 가능성 존재

Resource Allocation Graph with a Deadlock

deadlock이 발생한 상태의 그래프 예시

• $P_1$, $P_2$, $P_3$는 각기 리소스를 요청 중이나 서로의 점유 상태가 막고 있음
• cycle이 형성되어 있음
• 모든 리소스가 1개 인스턴스를 가짐

Resource Allocation Graph with a Cycle But No Deadlock

cycle은 존재하지만 deadlock이 아닌 경우의 예시

• $P_1 \rightarrow R_1 \rightarrow P_2$
• $P_2 \rightarrow R_2 \rightarrow P_4$
• $P_3$는 $R_1$ 요청 중

$R_1$, $R_2$ 모두 여러 인스턴스를 가지므로
실제로 deadlock은 발생하지 않음

Methods for Handling Deadlocks

• 시스템이 절대 deadlock 상태에 진입하지 않도록 보장 (예방 또는 회피)
• 시스템이 deadlock 상태에 진입하게 한 뒤,
  이를 감지하고 복구 (사후 대응)
• 문제를 무시하고 deadlock이 존재하지 않는 것처럼 처리
  → 대부분의 운영체제(예: UNIX)는 이 방법을 사용

Deadlock Prevention

• 요청 방식에 제약을 두어 필수 조건 중 하나라도 만족하지 않도록 만듦
• Mutual Exclusion
  • 공유 가능한 리소스는 필요 없음
  • 공유 불가능한 리소스는 반드시 mutual exclusion을 강제해야 함
    (내재적으로 공유 불가능한 경우는 불가능)
• Hold and Wait
  • 프로세스가 리소스를 요청할 때, 다른 리소스를 점유하고 있지 않아야 함
  • 실행 전에 필요한 모든 리소스를 한꺼번에 요청하고 할당받도록 요구하거나,
    아무 리소스도 보유하지 않을 때만 리소스를 요청할 수 있도록 함
  • 리소스 활용률이 낮아지고 starvation 가능성 존재
• No Preemption
  • 어떤 프로세스가 리소스를 점유한 상태에서 다른 리소스를 요청했는데
    즉시 할당될 수 없다면, 기존 리소스를 모두 반납해야 함
  • 반납된 리소스는 해당 프로세스가 대기 중인 리소스 목록에 추가됨
  • 프로세스는 기존 리소스와 새로운 리소스를 모두 획득할 수 있을 때 재시작됨
• Circular Wait
  • 모든 리소스 유형에 대해 총체적 순서를 부여하고,
    각 프로세스가 오름차순 순서로만 리소스를 요청하도록 제한함

단점: 낮은 리소스 활용률, 시스템 처리량 감소

Deadlock Avoidance

• 시스템이 사전에 추가적인 정보(a priori information)를 가지고 있어야 함
• 가장 단순하고 실용적인 모델:
  각 프로세스가 각 리소스 유형마다 최대 요구량을 명시
• deadlock-avoidance 알고리즘은
  자원의 할당 상태를 동적으로 검사하여
  circular wait 조건이 절대 발생하지 않도록 보장
• 자원 할당 상태(resource-allocation state)는
  사용 가능/할당된 자원 수와 프로세스의 최대 요구량에 의해 정의됨

Safe State

• 프로세스가 리소스를 요청하면, 시스템은 즉시 할당 시 safe 상태를 유지할 수 있는지 확인해야 함
• 시퀀스 $\langle P_1, P_2, \dots, P_n \rangle$이 존재하고
  각 $P_i$에 대해 다음이 성립하면 safe 상태임:
  • $P_i$의 리소스 요청량 ≤ 현재 가용 자원 + $\{P_j \mid j < i\}$가 보유 중인 리소스
  • 만약 자원이 즉시 사용 불가해도, $P_i$는 선행 프로세스가 종료될 때까지 기다릴 수 있음
  • $P_i$가 종료되면, 리소스를 반환하고 다음 프로세스가 요청 가능
• 시스템이 safe 상태이면, 모든 프로세스가 종료 가능한 시퀀스가 존재함

Basic Facts

• 시스템이 safe 상태 → deadlock 없음
• 시스템이 unsafe 상태 → deadlock 가능성 존재
  • 모든 프로세스가 최대량의 리소스를 요청할 경우 발생 가능
• Avoidance 기법은 시스템이 unsafe 상태에 진입하지 않도록 보장함

"요청이 safe 상태를 유지하는 경우에만 승인하라,
그렇지 않으면 거부하라"

Safe, Unsafe, Deadlock State Spaces

상태 공간은 다음과 같이 구분됨:

• Safe: deadlock 발생 가능성 없음
• Unsafe: deadlock 발생 가능성 있음
• Deadlock: 실제 deadlock 발생

(도표로 safe ⊂ unsafe ⊂ 전체 공간을 나타냄)

Avoidance Algorithms

• 하나의 인스턴스만 존재하는 리소스 유형:
  • resource-allocation graph 사용
• 여러 인스턴스가 존재하는 리소스 유형:
  • Banker's Algorithm 사용

Case A: One instance per resource type : Resource Allocation Graph Algorithm

• Claim edge
  • $P_i \rightarrow R_j$는 $P_i$가 $R_j$를 요청할 수 있음을 나타냄 (점선)
• Request edge
  • 프로세스가 실제로 리소스를 요청하면, claim edge → request edge로 변환됨
• Assignment edge
  • 리소스가 프로세스에 할당되면, request edge → assignment edge로 변환됨
  • 프로세스가 리소스를 반환하면, assignment edge → claim edge로 되돌아감
• 알고리즘 (모든 리소스는 사전에 claim 되어 있어야 함):
  • $P_i$가 $R_j$를 요청할 때,
  • 해당 request edge를 assignment edge로 바꾸더라도 그래프에 cycle이 생기지 않아야 요청을 수락

Resource-Allocation Graph for Deadlock Avoidance

예시 상황:

• $P_1$은 $R_1$ 보유
• $P_2$는 $R_2$를 요청
• $R_2$를 할당하면, 사이클이 형성되어 unsafe 상태가 됨

P2 requests R2
If we grant it,
A cycle is formed
→ unsafe

Unsafe State in a Resource-Allocation Graph

• 사이클이 없는 경우: safe, 요청을 grant
• 사이클이 생기는 경우: unsafe, 요청을 deny

Case B: Multiple Instances per Resource Types : Banker's Algorithm

• 각 프로세스는 최대 요구량을 사전에 명시
• 프로세스가 리소스를 요청하면, 대기할 수도 있음
• 모든 리소스를 할당받은 프로세스는 일정 시간 내에 반환해야 함

Data Structures for the Banker's Algorithm

• $n$: 프로세스 수
• $m$: 리소스 유형 수
• vector: Available
  • Available[j] = k: 리소스 $R_j$의 인스턴스 $k$개가 현재 사용 가능
• $n \times m$ matrix
  • Max[i][j] = k: 프로세스 $P_i$가 리소스 $R_j$를 최대 $k$개까지 요구할 수 있음
  • Allocation[i][j] = k: $P_i$가 리소스 $R_j$를 현재 $k$개 보유 중
  • Need[i][j] = Max[i][j] - Allocation[i][j]:
    $P_i$는 리소스 $R_j$를 최대 $k$개 더 요청할 수 있음

Safety Algorithm

1. 길이 $m$, $n$인 벡터 Work, Finish를 초기화:
   • Work = Available
   • Finish[i] = \text{false} for $i = 1, 2, ..., n$
2. 다음 조건을 만족하는 인덱스 $i$를 찾음:
   • Finish[i] == false
   • Need_i \leq Work 존재하지 않으면 step 4로 이동
3. • Work = Work + Allocation_i
   • Finish[i] = true
   • step 2로 돌아감
4. • 모든 $i$에 대해 Finish[i] == true이면, 시스템은 safe 상태

Resource-Request Algorithm for Process $P_i$

• Request_i는 $P_i$의 요청 벡터로, 각 리소스 유형 $R_j$에 대해 요청량을 나타냄
• 요청 처리 단계:
  1. Request_i \leq Need_i
     • 만족하지 않으면 에러 (최대 요구량 초과)
  2. Request_i \leq Available
     • 아니면 $P_i$는 대기
  3. 요청을 일시적으로 할당한 것처럼 상태를 갱신:

     Available = Available - Request
     Allocation_i = Allocation_i + Request
     Need_i = Need_i - Request
     
     • safe 상태이면 요청을 실제로 할당
     • unsafe 상태이면 할당을 취소하고 이전 상태로 복원

Example of Banker’s Algorithm

• 5개 프로세스: $P_0$ ~ $P_4$
• 3개 리소스 유형: A(10), B(5), C(7)

시점 $T_0$의 상태:

• 시스템은 safe 상태:
  시퀀스 $\langle P_1, P_3, P_4, P_0, P_2 \rangle$가 safety 기준 만족

Example (Cont.): $P_1$ request (1, 0, 2)

• $Request \leq Available \Rightarrow (1, 0, 2) \leq (3, 3, 2)$ → True

업데이트된 상태:

• 시퀀스 $\langle P_1, P_3, P_4, P_0, P_2 \rangle$는 safety 조건 만족

추가 질문:

• $P_0$이 (3, 3, 0)을 요청할 수 있는가?
• $P_0$이 (0, 2, 0)을 요청할 수 있는가?

Deadlock Detection

• 시스템이 deadlock 상태에 진입하도록 허용
• 감지 알고리즘과 복구 절차 필요
• 2가지 case:
  • A: 리소스 유형당 인스턴스 1개 → cycle ⇒ deadlock
  • B: 리소스 유형당 인스턴스 다수 → ?

Single Instance of Each Resource Type

• wait-for graph 유지
  • 노드는 프로세스
  • $P_i \rightarrow P_j$: $P_i$가 $P_j$가 보유한 리소스를 기다리는 중
• cycle 탐지 알고리즘 실행
  • 그래프에서 cycle 탐지는 $O(n^2)$ 시간복잡도
    ($n$은 그래프 정점 수)

Resource-Allocation Graph and Wait-for Graph

• 좌측: Resource-Allocation Graph
• 우측: 해당 그래프를 변환한 Wait-for Graph

Wait-for Graph는 프로세스 간 대기 관계만 표시
(리소스 노드를 제거하고 간선으로 대기 관계만 유지)

Several Instances of a Resource Type

• Deadlock Detection Algorithm 사용
• 사용되는 자료구조:
  • Available: 각 리소스 유형별 현재 사용 가능한 인스턴스 수를 나타내는 벡터
  • Allocation: $n \times m$ 행렬, 각 프로세스에 현재 할당된 리소스 수
  • Request: $n \times m$ 행렬, 각 프로세스가 현재 요청 중인 리소스 수
    • Request[i][k] = x: $P_i$는 리소스 $R_k$를 $x$개 요청 중

Detection Algorithm

1. 벡터 Work, Finish 초기화:
   • Work = Available
   • $i = 1, ..., n$에 대해
     • Finish[i] = false (만약 Allocation[i] \ne 0)
     • Finish[i] = true (만약 Allocation[i] = 0)
2. 다음 조건을 만족하는 인덱스 $i$를 찾음:
   • Finish[i] == false
   • Request[i] \leq Work 없으면 step 4로 이동
3. • Work = Work + Allocation[i]
   • Finish[i] = true
   • step 2로 이동
4. • 어떤 $i$에 대해 Finish[i] == false이면 시스템은 deadlock 상태
   • 특히, Finish[i] == false인 프로세스 $P_i$는 deadlock 상태에 있음

Example of Detection Algorithm

• 프로세스 $P_0$ ~ $P_4$, 리소스 A(7), B(2), C(6)

시간 $T_0$의 상태:

• 시퀀스 $\langle P_0, P_2, P_3, P_1, P_4 \rangle$ → 모든 Finish[i] = true

Detection Algorithm (Cont.)

• 알고리즘 수행 비용:
  • $O(m \times n^2)$
  • $m$: 리소스 유형 수
  • $n$: 프로세스 수

문제: 얼마나 자주 deadlock 탐지를 실행할 것인가?

• 모든 요청마다? (오버헤드 큼)
• 자원이 할당되지 않을 때마다?
• 주기적으로? (deadlock 확률이 낮을 경우 적절)

Recovery from Deadlock: Process Termination

• 모든 deadlock된 프로세스를 종료하거나,
• 하나씩 종료하여 deadlock 사이클 제거

어떤 프로세스를 종료할지 결정 기준:

• 프로세스 우선순위
• 이미 소요된 실행 시간 및 남은 시간
• 사용한 리소스 수
• 필요한 리소스 수
• 종료되어야 할 프로세스 수
• 프로세스가 대화형(interactive)인지 배치형(batch)인지

Recovery from Deadlock: Resource Preemption

• 희생자 선택 (victim selection):
  • 비용(cost)을 최소화하는 방식으로 선택
• Rollback
  • 안전한 상태(safe state)로 되돌아감
  • 해당 상태에서 프로세스를 다시 시작함
• Starvation
  • 동일한 프로세스가 반복적으로 희생자로 선택될 수 있음
  • 롤백 횟수를 비용 요소로 포함시켜 고려해야 함

Avoidance vs. Detection

두 알고리즘의 차이점

• Avoidance:
  • 프로세스가 최악의 행동(worst case)을 한다고 가정
    • 모든 프로세스가 최대 리소스를 동시에 요청한다고 가정
    • 이 최악의 시나리오에서도 safe sequence가 보장될 경우에만 리소스 할당
    • 리소스 낭비가 발생할 수 있음
• Detection:
  • 모든 프로세스가 대기 상태(dormant)라고 가정
    • 즉, 더 이상 추가 리소스를 요청하지 않는다고 가정 (최선의 시나리오)
    • 현재 상태에 기반해 deadlock 여부를 판단함