[OS] Deadlock

Deadlock?

• 정의?
  every process in a set of processes is waiting for an event that can be caused only by another process in the set.

Livelock?

• Deadlock과 마찬가지로 Liveness failure를 일으키지만, deadlock은 blocked 상태로 프로세스가 진전되지 못하는 상태를 의미하지만, livelock의 경우 blocked 상태는 아니고, 계속 실패하는 동작을 반복하는 경우 발생한다.

아래의 예를 통해 둘의 차이를 알 수 있다.

• deadlock example
  프로세스 A, B가 mutex C, D를 각각 점유중일 때, A는 mutex_lock(D), B는 mutex_lock(C)를 하는 경우
  즉, A와 B는 wait 중이므로 blocked 상태이다.
• livelock example
  프로세스 A, B가 자원 C, D를 각각 점유중일 때, A는 mutex_trylock(D), B는 mutex_trylock(C)를 while문을 계속 돌면서 실행하는 경우
  A, B 둘 다 blocked 상태는 아니지만 계속 실패하는 행동을 반복하므로 결국 진전이 일어나지 않는다.

Deadlock의 필요 조건. (만족한다고 항상 deadlock이 일어나지는 않지만 deadlock이 일어난다면 만족하게 된다.)

• Mutual exclusion
  한 프로세스가 자원에 접근중일 때 다른 프로세스는 접근할 수 없다.
• Hold and wait
  프로세스는 자원을 점유한 상태로 다른 프로세스가 소유중인 자원을 기다린다.
• No preemption
  자원은 preempt되지 않는다. 즉, 자원을 소유중인 프로세스가 스스로 자원을 반납할 때 까지 release되지 않는다.
• Circular wait
  A set $\{T_0, T_1, ..., T_n\}$ of waiting threads must exist such that
  $T_0$ is waiting for a resource held by $T_1$, $T_1$ is waiting for a resource held by $T_2$, ..., $T_{n−1}$ is waiting for a resource held by $T_n$, and $T_n$ is waiting for a resource held by $T_0$

Resource Allocation Graph

• 프로세스가 점유중인 자원을 그래프로 나타낼 수 있다.
• 각 노드는 프로세스 혹은 자원의 인스턴스를 의미한다.
• directed edge는 두 가지 존재하는데,
  1. 자원에서 시작해서 프로세스를 가리킴 (assignment edge)
     -> 프로세스가 해당 자원을 점유중임
  2. 프로세스에서 시작해서 자원을 가리킴 (request edge)
     -> 프로세스가 해당 자원을 request 했고, 기다리는 중임

예시)

• 그래프 상에서 cycle이 존재하면 deadlock일 수도, 아닐 수도 있다.
• 만약 resource의 종류마다 instance가 하나씩 있다면, cycle과 deadlock은 동치이다.
• instance가 둘 이상인 instance가 있다면, cycle은 deadlock의 필요조건이다.

Methods for Handling Deadlocks

Deadlock Prevention

deadlock의 발생을 원천 차단하는 방법.
앞서 언급했던 deadlock의 필요조건 4개 중 1개를 항상 만족시키지 못하게 하여 deadlock이 발생하지 않게 한다.

• Mutual exclusion
  애초에 여러 스레드가 동시에 실행되는 환경에서는 race condition을 방지하기 위해 mutual exclusion이 필요한데, 이 조건을 만족시키지 않는다는 것은 사실상 nonsense 이다.

• Hold and wait

  1. 실행 전에 모든 자원을 다 할당받기?
  2. 자원을 소유하고 있지 않을 때에만 자원 요청하기?
  • 단점 : resource utilization이 구림, starvation 가능.

• No Preemption

  1. 스레드가 자원을 wait하는 상황이 발생한다면, wait하는 동안 그 스레드가 가지고 있던 자원을 모두 preempt되도록 하고, 만약 그 자원이 preempt된다면, waiting리스트에 추가시킨다.
  2. 스레드가 자원을 요청했을 때 만약 다른 스레드가 그 자원을 점유중이라면, 자원을 점유중인 스레드가 wait 상태라면 preempt, 그렇지 않다면 wait시키고, 마찬가지로 자신도 wait 상태가 되었기 때문에 자원을 preempt 가능한 상태로 냅둔다.

• Circular wait

  1. 자원 종류별로 우선순위를 매긴다.
     Let $R\ =\ \{R_1, R_2, ..., R_m\}$ be the set of resource types.
     Define one-to-one function $F:R \rightarrow \N$.
  2. 프로세스는 위의 enumeration에 대해 strictly increasing order를 따라서 자원 할당을 요청할 수 있다. 즉, $R_i,R_j$순서로 자원을 요청한다면, $F(R_i) < F(R_j)$여야 한다.
     그러므로 만약 $R_i$를 요청한다면, 이전에 $F(R_j) \ge F(R_i)$인 모든 $j$에 대해서 이미 할당 해제를 했어야 한다.
     또, 하나의 자원종류의 여러 instance를 요청한다면, 하나씩이 아닌 한꺼번에 요청을 해야 한다.

  이 방식대로 하면 circular wait는 만족되지 않는다.
  증명) 귀류법 사용 -> circular wait이 존재한다고 가정.

  1. circular wait이 존재한다? -> there exists a set $C=\{C_1, C_2, ..., C_n\}$ such that $C_i$ waits for the resource $C_{(i + 1)\ \%\ n}$ is holding for all $i=1, 2, ..., n$
  2. Let $R=\{R_1, R_2, ..., R_n\}$, where $R_i$ is the resource $C_i$ is holding for all $1 \le i \le n$.
  3. $C_i$가 $C_j$로부터 자원을 요청했다는 것은 $F(R_i) < F(R_j)$임을 의미한다.
  4. 결국, $F(R_1) < F(R_2) < ... < F(R_n) < F(R_1)$이 되고, 이는 $F(R_1)< F(R_1)$을 의미하므로 모순이다.

  당연히, 우선순위가 dynamically 매겨지게 되면 deadlock이 발생할 수 있다.

Deadlock Avoidance

Deadlock prevention의 단점 : 효율이 구림.
process가 어떤 자원을 요청할 것인지, 현재의 상태 등을 알고 있으면 deadlock avoidance algorithm을 통해서 deadlock이 발생하지 않게 할 수 있다.

Safe state

• Safe sequence
  A sequence of threads $<T_1, T_2, ..., T_n>$ is a safe sequence for the current allocation state if, for each $T_i$, the resource requests that $T_i$ can still make can be satisfied by the currently available resources plus the resources held by all $T_j$, with $j < i$.
• Safe state
  system에 safe sequence가 존재한다면, 그 system은 safe state에 있다고 한다.
  그렇지 않다면, system은 unsafe라고 한다.

항상 safe state에만 머무르게 하는 방법. 물론 그렇기 때문에 효율성이 떨어지게 된다.

Resource-Allocation-Graph Algorithm

• claim edge
  Thread $T_i$에서 자원 $R_j$를 향해서 그려지는 edge.
  언젠가 $T_i$가 $R_j$를 요청할 것이라는 의미이다.
  즉, $T_i$가 $R_j를 요청하는 시점이 오면 request edge로 변하고, assignment가 끝나면 assignment edge에서 claim edge로 변한다.

이 알고리즘은 resource type마다 instance가 하나 존재할 때 쓰이게 된다.

• 작동 원리
  • 모든 프로세스들의 필요 자원에 대한 정보를 알아내고, claim edge를 미리 연결시켜 놓는다.
  • 프로세스가 동작하면서 자원 할당에 대한 사항이 바뀔 때 마다 그래프를 업데이트한다.
  • 그래프 상에 cycle이 존재하는지 확인한다. $(O(n^2))$
  • cycle이 없다면 (safe state), 그대로 할당.
  • cycle이 있다면 (unsafe state), 해당 프로세스는 wait하게 된다.

Banker's Algorithm

• 어원 : 은행에서는 고객들의 요구를 충족시키지 못하게 돈 관리를 해서는 안 된다 -> 이 때 쓰일 수 있는 알고리즘.

• 정의

  • Available
    • 사이즈 m의 벡터 (전체 자원 종류는 m가지라고 한다.)
    • 현재 남아있는 할당가능한 자원의 양
  • Max
    • n x m 행렬
    • 각 스레드의 최대 자원 요구량을 나타냄.
    • $Max_{ij}$ : $T_i$ 스레드의 $R_j$ 자원에 대한 최대 요구량
  • Allocation
    • n x m 행렬
    • 각 스레드의 현재 자원 할당량을 나타냄
    • $Allocation_{ij}$ : $T_i$ 스레드가 현재 점유중인 $R_j$ 자원의 양
  • Need
    • n x m 행렬
    • 각 스레드의 필요 자원량을 나타냄
    • $Need_{ij}$ : $T_i$ 스레드가 현재 요구하는 $R_j$ 자원의 양
    • $Need_{ij}=Max_{ij}-Allocation_{ij}$이다.

• Safety Algorithm
  

  시간 복잡도 : $O(mn^2)$

• Resource-Request Algorithm
  

  결과적으로 safe state가 된다면, 허용.
  unsafe state가 된다면, 이전 상태로 되돌리고, wait한다.

Deadlock Detection

Single Instance of Each Resource Type

• wait-for graph
  resource-allocation graph에서 자원 node를 뺀 그래프

• an edge $T_i \rightarrow T_j$ exists in a wait-for graph if and only if the corresponding resource-allocation graph contains two edges $T_i \rightarrow R_q$ and $R_q \rightarrow T_j$ for some resource $R_q$.
• 이 간소화된 그래프 상에서 cycle이 존재하면 (iff) deadlock이 발생하는 것이므로 주기적으로 cycle이 있는지 $(\ O(n^2)\ )$ 확인한다.
• 그래프를 간소화시켜서 n 자체를 줄인다는 것에 의미가 있는건가..? 정확히는 잘 모르겠음.

Several Instances of a Resource Type

banker's algorithm에서 나왔던 방법과 유사하다.

• Available : 이전과 동일.
• Allocation : 이전과 동일.
• Request : 이전과 동일.

• 시간 복잡도 : $O(mn^2)$
• 3번에서, 이전과는 다르게 현재 $Request_i$만 조건을 만족하면 $T_i$는 성공이라고 가정하고, 자원을 반납한다. -> optimistic approach
• 어찌 되었든 만약 deadlock 상태라면 낙관적으로 봤을 때에도 $Request_i > Work$가 되므로 실제 낙관적인 경우가 아니라고 할 지라도 일단 "현재" 기준에서는 deadlock이 아니라는 것은 확실하다.
• 문제가 발생한다면 다음 detection에 탐지될 거니까..

Recovery from Deadlock

Deadlock으로부터 복구하는 방법?

Process and Thread Termination

• 모든 deadlock된 프로세스 abort
  • 모든 프로세스를 abort 시켜야 함 -> 엄청난 overhead
• 하나씩 abort 시키면서 deadlock이 풀리는지 확인
  • 매 순간마다 cycle algorithm 실행시켜야 함 -> 이 또한 overhead.

적절히 잘 선택해야 한다~~

Resource Preemption

• Selecting a victim
• Rollback
• Starvation

이 세 가지를 주의해서 실행해야 한다~~

참고 자료

• Operating System Concepts - 10th edition