System Model

• modeling :
  있는 그대로를 다 고려하여 일을 진행할 수 없다. 주변을 깨끗하게 정리하고 일을 체계적으로 만든다.

• System Modeling :
  현대의 모든 OS에 deadlock이 있다.
  안 생기게 할 수도 있다. 그런데 왜 생길까?
  ➡️ 우선 deadlock이 해결되기 위해서 deadlock을 정의해야 하고,
  정의하기 위해서 System을 Modeling해야 한다.

• System을 Modeling해보자.
  • process가 있다.
  • process는 resource를 가진다. resource는 instance로 구성된다
    (ex. resource : CPU, memory, I/O, etc)
    (ex. resource : HDD, instance : instance1, instance2, ...)
    
    
  • request : 각각의 process가 resource를 필요로 한다
  • use(=allocation) : process가 resource를 사용하고 있다.
  • release : process가 resource 사용이 끝나면 해제한다.

---

Deadlock Characterization

Necessary Conditions

• 필요조건들 :
  Deadlock은 한 system에 다음 4가지 조건이 동시에 성립될 때 발생할 수 있다.
  Deadlock인 상태가 발생하면 다음 4가지가 모두 발생되어 있다.
  4가지 중 하나도 발생하지 않았다면 절대 Deadlock이 안 걸린다.
  1. Mutual Exclusion
     : 하나의 process는 하나의 resource를 가진다
  2. Hold and Wait :
     process는 적어도 하나의 resource를 가지고 있다.
     추가로 resource가 필요하다면 기다려야 한다.
  3. No preemption :
     기다려야 한다. 강제로 resource를 뺐지 않는다.
  4. Circular Wait :
     A는 B를 기다리고, B는 C를 기다리고, C는 A를 기다린다.

Resource-Allocation Graph

• Vertex : Vertex에 올 수 있는 것은 Process or Resource

  • Process는 원으로 표현
    
  • Resource는 사각형
    

• Edge(Directed Edge)

  • Request Edge : $P_i$ ➡️ $R_j$ : $P_i$ Process가 $R_j$ Resource를 원한다.
  • Assignment Edge: $R_j$ ➡️ $P_i$ : $R_j$ Resource가 $P_i$에 할당 되었다.

Example 1

• Example 1
  
  • $T_1$은 $R_2$의 2번째 instance를 hold하고 있다.
  • 동시에 $T_1$은 $R_1$을 request하고 있다.
  • 하지만 $R_1$은 $T_2$에 의해 allocation되고 있다.
  • 동시에 $T_2$는 $R_3$를 request하고 있다.
  • 하지만 $R_3$는 $T_3$에 의해 allocation되고 있다.
  • $P_3$는 request하고 있는 Resource가 없다.
    
    
  1. Mutual Exclusion 만족
  2. Hold and Wait 만족
  3. No Preemption 만족
     ➡️ 1, 2, 3은 일반적인 system에서 거의 만족한다.
     그렇다면 4. Circular Wait 만족?
  4. Circular Wait 만족 X
     ➡️ Why?
     $T_1$, $T_2$는 기다리는 Resource가 있지만
     $T_3$는 기다리는 Resource가 없다.
     $T_3$가 끝나면 $R_3$를 release, $R_3$는 $T_2$가 allocation, $T_1$은 $R_1$을 allocation
     결국 $T_3$는 느슨하게 풀어져 있어 Circular Wait을 만족하지 못한다.

     1, 2, 3 조건이 만족하지만 4 조건이 만족하지 않아 Deadlock 상태에 빠지지 않는다.

• Example 1이 Cicurlar Wait을 만족하도록 만들면?
  
  • $T_1$, $T_2$, $T_3$는 어떠한 Resource를 기다리고 있기 때문에 Circular Wait을 만족한다.

    1, 2, 3, 4를 모두 만족하기 때문에 Deadlock 상태가 발생할 가능성이 있다.
    
    위 예제에서는
    $R_2$를 $T_3$가 requset하는 순간,
    $R_2$는 더 이상 받을 수 없어 $T_3$는 기다림,
    $T_2$는 $T_3$에 allocation된 $R_3$를 기다림,
    $T_1$은 $T_2에$ allocation된 $R_1$을 기다림.
    ➡️ Deadlock 상태에 빠짐

Example 2

• Example 2
  

  • $R_2$의 두번째 instance를 Circular와 상관없는 $T_4$가 allocation하고 있다.

  • $R_1$의 첫번째 instance를 Circular와 상관없는 $T_2$가 allocation하고 있다.

  • 위 그래프에서는 다음과 같은 cycle을 갖는다.
    $T_1$ ➡️ $R_1$ ➡️ $T_3$ ➡️ $R_2$ ➡️ $T_1$

    • 하지만 deadlock 상태에 빠지지 않는다.
      Proces $T_4$가 $R_2$ resource를 release한다면,
      $T_3$는 $R_2$의 instance를 use할 수 있을 것이다.
      마찬가지로
      Proces $T_2$가 $R_1$ resource를 release한다면,
      $T_1$은 $R_1$의 instance를 use할 수 있을 것이다.

    당장은 Deadlock 상태가 가능할 것처럼 보이지만,
    $T_2, T_4$가 release하면 Deadlock 상황이 안 생기기 때문에
    위 그래프는 Deadlock 상황이 생기지 않는 그래프이다.
    만약 $R_1$의 instacne가 1개였거나 $R_2$의 instance가 1개였다면 Deadlock이 생겼을 것이다.

Basic Facts

1. If graph contains no cycle? No Deadlock.
2. If graph contains a cycle?
   • if only one instance per resource type? Definitely Deadlock.
   • if several instances per resource type? Possibility of Deadlock

---

Method for Handling Deadlocks

• 그러면 Deadlock이 발생하는 이유를 알았고 발생하지 않도록 하는 방법도 알았는데,
  해결할 수 있는가?
  • 해결할 수 있다.
    하지만 OS 입장에서 매우 비효율적이므로 Deadlock이 발생하지 않도록 하지는 않는다.
    현대의 OS는 Deadlock 문제가 여전히 존재하고, 문제가 없는 척, 모른 척 한다.
    ➡️ 왜 그러는가?
    Deadlock은 OS가 죽는게 아니라 해당 process가 일을 못하는 상황이다.
    OS 입장에서는 전체 process들 중에 아주 일부의 process만 일을 진행하지 못하고 있는 상황이다.
    이러한 상황을 막기 위해 OS는 매순간 deadlock 발생 가능성을 확인하고 관리해야 하는데,
    이렇게 된다면 OS의 효율이 매우 떨어진다.(OS는 바빠지고 resource가 많이 필요해진다.)
  • 교통사고를 안나게 할 수는 있지만, 현실적으로 매우 어렵다.
    그래서 경찰이 하는 일은 사고를 아예 안나게 하는 것이 아니라, 사고가 나면 처리를 해준다.

---

Deadlock Prevention

• Deadlock을 Prevention하기 위해
  4가지 중 하나만 발생하지 않게 하여 Deadlock이 발생하지 않도록 할 수 있다.

  1. Mutual Exclusion
     : 한 개의 Resource를 한 개의 Process만 가지도록 한다.
     ➡️ 비공유 resource를 전제로 한다.
     ➡️ 비현실적
     ➡️ 안 발생하게 할 수 없다.

  2. Hold and Wait
     : Process가 Resource를 request할 때마다 다른 Resource들을 점유하지 않도록 보장해야 한다.
     ➡️ 한 두개의 process 때문에 나머지 모든 Process가 starvation 상태.
     ➡️ 비효율적
     ➡️ 안 발생하게 할 수 없다.

  3. No Preemption
     : Resource를 사용하고 Process가 있는데,
     똑같이 그 Resource를 필요로 하는 Process가 있으면 뺐어옴.
     ➡️ 질서가 없어짐. 비효율, 비현실적
     ➡️ 안 발생하게 할 수 없다.

  4. Ciruclar Wait
     : 순환대기가 발생하지 않도록 하는 것.
     ➡️ 가장 현실적인 방법
     ➡️ 하지만 OS가 모든 Process간의 관계를 계속 살펴봐야 하고, 모든 Resource를 파악해야 한다.
     ➡️ OS의 Resource 낭비가 매우 심하다.

1, 2, 3, 4 모두 문제가 발생하지 않도록 하여 Deadlock을 안생기게 할 수는 있지만,
Deadlock 하나 안생기게 하기 위해서 전체 system이 엉망이 된다.
그래서 Deadlock이 안생기게 할 수는 있지만 현실적으로는 Prevention을 하지 않는다.

그렇다면 Deadlock을 완전히 막는 Prevention보다
Resource를 덜 사용하더라도 Deadlock이 발생할 것 같은 순간에만 회피시키도록 Avoidance하는 것은 어떨까?

---

Deadlock Avoidance

Safe State

• 어떠한 System에 State를 정의하자.
  
  • unsafe : Deadlock이 언제든지 생길 수 있는 상태
  • safe : Deadlock이 절대 안 생기는 상태.
• 비용이 덜 드는 범위 내에서 가능한 safe state로 만들어보자.
• safe state : 모든 Process에 safe sequence가 존재하면 시스템은 safe state에 있다고 한다.

Safe Sequence

• Resource가 Magnetic Tape이고, instance가 12개인 System이 있다고 가정.
• Process(Task)는 3개가 있다.
  
• 현재 12개 instance 중에 9개를 사용하고 있고, 3개의 여유가 남아 있다.
• 이 System에 Deadlock이 생길 수가 있다. 왜?
  • $T_0, T_1, T_2$이 동시에 최대 23개를 request할 수 있지만,
    총 instance는 12개이다.
    하지만 그렇다고 해서 23개의 Instance를 계속 가지고 있을 수는 없으니까
    Deadlock이 생길 수 있는 상황인 것이다.
• 그렇다면 항상 Deadlock이 생기는가? 아니다
  • $T_1$의 최대 수요 4, 사용가능 3이기 때문에 $T_1$을 먼저 allocation할 수 있다.
  • $T_1$의 instance 사용이 끝나면, release하여 사용가능 : 7
  • $T_0$은 이제 사용가능 7 중에 5를 사용할 수 있게 된다.
  • $T_0$가 수행 완료되면, instance를 release하여 $T_2$는 최대 수요를 사용할 수 있게 된다.
    
    순서 : $T_1$ ➡️ $T_0$ ➡️ $T_2$
    순서를 정해줌으로써 절대 Deadlock을 안 생기게 할 수 있고,
    이러한 순서를 Safe Sequence라고 한다.
    Safe Sequence가 존재하면, 그 system은 Safe State에 있다고 한다.
• 장점 : Deadlock이 안 생긴다.
• 단점 : Process가 대기해야 한다. (속도보다 안전이 우선시 되어)

Resource-Allocation Graph Algorithm

• 실선 : allocation or reqeust하고 있다.
• 점선 : 아직은 아닌데 allocation or request할 수 있다.
  

Unsafe State in Resource-Allocation Graph

• $T_1$이 $R_2$에 요청하는 순간, deadlock이 생길 수 있다 == unsafe state가 된다.

Banker's Algorithm

• 새로운 process가 system에 들어가면, 필요로하는 resource의 형태들의 최대수를 선언해야 한다.
  safe sequence 유지

• process가 resource를 요구할 때,
  system은 resource를 할당한 다음에도 safe state로 남아 있는지를 결정해야 한다.

• safe state로 남아 있으면 할당하고,
  그렇지 않으면 다른 process들이 resource를 충분히 해제할 때까지 대기해야 한다.

Safety Algorithm

Example of Banker's Algorithm

• Resource는 3개 : A, B, C
• A의 Instance 10개 / B의 Instance 5개 / C의 Instance 7개
• Process는 5개 : $T_0$ ~ $T_4$
• A : 10개, A Max Need : 25개
• B : 5개, B Max Need : 12개
• C : 7개, C Max Need : 15개
  ➡️ Process마다 그 어떤 것도 A, B, C의 Max Need는 Available A, B, C보다 크면 안 된다.
  

  • $T_0$를 봤을 때, MAX가 [7, 5, 3]이고,
    Allocation [0, 1, 0]이므로
    언제든지 언제든지 [7, 4, 3]을 요구할 수 있다.
    ➡️ 시작을 $T_0$로 하면 부도가 난다.
    
    

  • 그래서 $T_1$부터 시작하면, MAX [3, 2, 2]이고,
    Allocation [2, 0, 0]이므로
    언제든지 [1, 2, 2]를 요구할 수 있다.
    ➡️ Available [3, 3, 2]이기 때문에 [1, 2, 2]를 빌려줄 수 있다.
    ➡️ $T_1$이 끝나고 resource를 release하면, Available [5, 3, 2]가 된다.
    
    

  • 다음으로 $T_2$는 [6, 0, 0]을 요구할 수 있고, Available은 [5, 3, 2]이므로 빌려줄 수 없다.
    
    

  • 그래서 다음으로 $T_3$은 Max[2, 2, 2]이고,
    Alloaction [2, 1, 1]이므로 언제든지 [0, 1, 1]을 요구할 수 있다.
    ➡️ Available [5, 3, 2]이기 때문에 [0, 1, 1]를 빌려줄 수 있다.
    ➡️ $T_3$이 끝나고 resource를 release하면, Available [7, 4, 3]가 된다.
    
    

  • 다음으로 $T_4$는 Max[4, 3, 3]이고,
    Allocation [0, 0, 2]이므로 언제든지 [4, 3, 1]을 요구할 수 있다.
    ➡️ Available [7, 4, 3]이기 때문에 [4, 3, 1]를 빌려줄 수 있다.
    ➡️ $T_4$이 끝나고 resource를 release하면, Available [7, 4, 5]가 된다.
    
    

  • 다음으로 $T_0$는 Max[7, 5, 3]이고,
    Allocation [0, 1, 0]이므로 언제든지 [7, 4, 3]을 요구할 수 있다.
    ➡️ Available [7, 4, 5]이기 때문에 [7, 4, 3]를 빌려줄 수 있다.
    ➡️ $T_0$이 끝나고 resource를 release하면, Available [7, 5, 5]가 된다.
    
    

  • 다음으로 $T_2$는 Max[9, 0, 2]이고,
    Allocation [3, 0, 2]이므로 언제든지 [6, 0, 0]을 요구할 수 있다.
    ➡️ Available [7, 5, 5]이기 때문에 [6, 0, 0]를 빌려줄 수 있다.
    ➡️ $T_2$이 끝나고 resource를 release하면, Available [10, 5, 7]가 된다.

    Safe Sequence :
    $T_1$ ➡️ $T_3$ ➡️ $T_4$ ➡️ $T_2$ ➡️ $T_0$
    $T_1$ ➡️ $T_3$ ➡️ $T_4$ ➡️ $T_0$ ➡️ $T_2$
    (더 있을 수도? 계산은 안 해봄)
    이러한 Safe Sequence대로 하면, Deadlock은 절대 안 생긴다.
    $5!$ 경우 중에 Safe Sequence는 여러 개 있을 수 있다.

---

Deadlock Detection

• Allow System to enter deadlock state
• Detection Algorith,
• Recovery scheme

➡️ Deadlock을 Prevention할 수 없으니까,
발생하게 내버려 두고 Detection하여 회복해야 한다.
Detection하기 위해서는 modeling이 또 필요하다.

Single Instance of Each Resource Type

• wait-for graph
  : instance가 하나 일 때, Deadlock Detection 방법.
  대기하는 그래프로 deadlock 상태를 Detection할 수 있다.
  
  • Resource를 뭘 쓰는지가 중요한게 아니라(a) ➡️ 서로 request 관계만 남겨보자(b)
  • (b) : 순환 관계만 따지거자 resource allocation이 아닌 process간의 순환 관계만 정의

    이렇게 요청관계만 남겨보니, Circulation이 있는지를 알아보기 쉽다.
    (Circulation이 있으면 Deadlock이 생길 수 있다. )
    (Criculation이 없으면 Deadlock이 절대 없다.)
    이러한 wait-for graph의 용도는 Deadlock Detection이다.

Several Instance of a Resource Type

• Instance가 여러 개일 때,
  Detection Algorithm은 Banker's Algorithm과 매우 유사하다.
  

Detection-Algorithm Usage

• 언제 Detection Algorithm을 호출할 것인가는 다음 두 가지 요인에 의해 좌우된다.
  1. Deadlock 상태의 빈도수
  2. Deadlock이 발생했했을 때, 영향을 받는 Process 수

---

Recovery from Deadlock

Process and Thread Termination

• process들끼리 서로 연관되어 있기 때문에 문제가 되는 process를 찾는 것은 쉽지 않다.
• 따라서 다음의 근거를 갖고 victim(희생자) process을 찾아보자.

1. Prioirty of the process
2. How long process has computed, and how much longer to completion
3. Resources the process has used
4. Resources process needs to complete
5. How many processes will need to be terminated
6. Is process interactive or batch?

Victim process를 중지(abort)시킴으로써 Deadlock 상태를 제거한다.
➡️ Victim process는 Deadlock만 생기면 abortion당하니까 Starvation이 생김.

Resource Preemption

자원 선점을 이용해 교착 상태를 제거하려면, 교착 상태가 깨어질 때까지 프로세스로부 터 자원을 계속 선점해 이들을 다른 프로세스에 주어야 한다.

• Selecting a victime : minimize cost
• Rollback : return to some safe state, restart process for that state
  ➡️ safe state로 되돌려 process를 다시 실행
• Starvation : same process may always be picked as victim, include number of rollback in cost factor
  ➡️ deadlock 상태에 빠지면 starvation이 생길 수 있다.