[OS] #25 Deadlocks

1. Deadlocks

1.1 개요

개념

• 교착상태
• 두 개 이상의 프로세스가 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에, 무한 대기 상태에 빠지는 상태
• 한정된 자원을 프로세스가 사용하려고 할 때 발생한다.
  
  

프로세스는 아래와 같은 순서로만 자원을 사용할 수 있다.

• Request (요청)
• Use (사용)
• Release (방출)

1.2 데드락 발생조건⭐⭐

(4가지 조건을 동시에 충족해야 발생)

1.2.1 상호 배제

한 번에 프로세스 하나만 해당 자원을 사용할 수 있다.

다른 프로세스가 그 자원을 사용하려 할 경우, 그 프로세스는 자원의 사용이 끝날 때까지 지연되어야 한다.

1.2.2 점유 대기

프로세스가 최소한 한 개의 자원은 점유해야 하고, 점유한 자원을 얻기 위해 대기하는 프로세스가 존재해야 한다.

• 아래 그림에서 볼 수 있듯, P₀ 이 R₀를 사용하고 있는 상태에서 R₁을 요구하고 있는 것을 확인할 수 있다.
• 하나 이상의 자원을 가지고 있는 상태에서 공유 자원을 요청한 상황
  
  

1.2.3 비선점

프로세스가 사용하는 자원을 중간에 다른 프로세스가 가져갈 수 없다.

프로세스가 작업 종료 후에 자발적으로 자원을 방출한다.

1.2.4 순환 대기

대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

• 아래 그림에서 볼 수 있듯 P₁이 R₁을 사용하고 있고, P₀가 R₀을 사용하고 있는 상태에서 서로 자원을 요구하고 있는 것을 알 수 있다.
• 이때, P₀과 P₁은 교착상태에 해당한다.
  
  

1.3 자원 할당 그래프(RAG)

자원 할당 그래프(RAG, Resource-Allocation Graph)

• 교착상태를 그래프로 그리는 방법을 말한다.
• RAG 구성요소 (출처 : 도리의 디지털라이프)
  • 아래에 사각형 점은 인스턴스이다.
    
    
    

데드락(교착상태) 찾기⭐ → 사이클을 보면 된다!

• 사이클이 없다면, 데드락이 발생하지 않는다.
• 자원의 인스턴스가 하나밖에 없는 경우, 사이클 형성 시, 무조건 데드락이 발생한다.
• 자원의 인스턴스가 여러개 있는 경우, 사이클 형성 시, 데드락 발생 가능성⭐이 있다.

예시1 (데드락 발생 x)

• P, R, E가 다음과 같을때,

  • P = {P1, P2, P3}
  • R = {R1, R2, R3, R4}
  • E = {P1->R1, P2->R3, R1->P2, R2->P2, R2->P1, R3->P3}
    

  ① P1은 R2에게 자원 요청 ② P2는 R1에게 자원 요청 ③ R1은 P1에게 자원 할당 ④ R2는 P2에게 자원 할당

  ➡️ 사이클 형성X, 데드락 발생X

  

예시2 (데드락 발생 o)

• 아래 그림에서는 사이클이 두 개 존재
  • P1 -> R0 -> P2 -> R2 -> P3 ➡️ 교착상태
  • P2 -> R2 -> P3 -> R1 (R2가 이미 P1, P2에게 자원 할당 해준 상태여서 남는 자원이 없는데 P3가 요청 -> 교착상태)
    
    

예시3 (사이클 존재하는데 데드락(교착상태) 발생x)

• 아래 그림에서는 P4가 작업이 끝난 상태이므로 사이클이 형성 되었음에도 교착상태 발생X
• 즉, 각 자원 유형이 여러 개의 인스턴스가 존재하면, 사이클이 반드시 교착상태가 발생했음을 의미하지는 않는다. (가능성만 존재)
• e.g., P1 -> R1 -> P3 -> R2 -> P1인 상황에서 R2는 2개의 인스턴스를 갖고있다.
  
  

2. 데드락 해결 방법

3가지의 방법이 존재한다.

• 데드락이 발생하지 않도록 예방(prevention) 하기
• 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance) 하기
• 데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 데드락에서 회복하기

2.1 예방

데드락의 발생조건 4가지 중 하나라도 발생하지 않게 하여 데드락 발생 가능성을 차단한다.

기법	설명
상호 배제 부정	여러 개의 프로세스가 동시에 공유 자원을 사용할 수 있게 한다. (상호 배제 제한 불가능)
점유 대기 부정	프로세스가 자원을 요청할 때 다른 자원을 보유하지 않도록 보장하거나, 자원을 소유하지 않은 프로세스만 요청 가능
비선점 부정	할당 불가능한 자원을 요청하면 점유 중인 모든 자원을 반납하고 대기하게 한다.
순환 대기 부정	자원 타입에 순서를 매기고, 일정한 방향(예: 오름차순)으로만 자원을 요구하도록 한다.

➡️ 이러한 조건을 방지해서 데드락을 예방하는 방법은 자원 낭비나 기아 상태가 발생한다는 단점이 존재한다.

2.2 회피

2.2.1 회피란?

교착상태가 발생하기 전 교착상태를 예측하고 회피하는 방법

• 데드락 회피를 위한 조건
  • 각 프로세스가 필요한 각 자원의 최대 인스턴스를 선언한다.
  • 자원할당 상태를 검사하여 순환대기 상태가 없도록 한다.
  • 자원 할당 상태는 ‘사용가능한 자원 수’ 와 ‘할당된 자원 수’ 와 ‘프로세스의 최대 요구 자원 수’ 에 의해 정의된다.

2.2.2 안전상태 (Safe State)⭐

안전한 상태일 때에만 자원 할당

• 시스템의 프로세스들이 요청하는 모든 자원을 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있다면 안전상태이다.
• e.g.,
  • 시스템에 12개의 자원이 있고, 현재 사용량이 9라면 가용 자원은 3이다.
  • 이때, 특정 순서로 실행했을 때 데드락이 걸리지 않는다면 안전상태
  • 어떤 순서로 실행해도 안전 상태가 아닐 때 불안전한 상태 → 데드락 발생
  • 데드락은 불안전한 상태일 때만 발생하므로, 안전한 상태만 유지하면 데드락 회피 가능

2.2.3 정리

• 시스템이 안전 상태인 경우 ⇒ 교착 상태가 발생하지 않는다.
• 시스템이 안전하지 않은 상태일 경우 ⇒ 교착 상태가 발생할 가능성이 존재한다. (무조건 발생하는 것이 아님⭐)
• 회피란 ⇒ 시스템이 안전하지 않은 상태로 들어가지 않도록 하는 것이다.
  
  

• 회피 알고리즘
  • 단일 인스턴스 자원일 때 : RAG 사용 하여 데드락 회피
  • 다중 인스턴스 자원일 때 : 은행원 알고리즘을 사용 하여 데드락 회피

2.2.4 RAM : 회피 알고리즘

RAG의 간선 종류

• 요청 간선
• 할당 간선
• 예약 간선 ➡️ 예약 간선이 추가됨!!!!

예약간선

• Pi → Rj 는 프로세스 Pi 가 미래에 자원 Rj 를 요청하는 의미
• 시스템에서 자원은 반드시 미리 예약되어야 한다.

간선의 변환

• 프로세스가 자원을 요청할 때 예약 간선이 요청 간선으로 변환
• 자원이 프로세스에 할당되면 요청 간선이 할당 간선으로 변환
• 자원이 프로세스에 의해 방출되면, 할당 간선은 예약 간선으로 재 전환

예시

• 프로세스 Pi 가 자원 Rj를 요청한다고 가정하자.
• 요청 간선 Pi → Rj 를 할당 간선 Rjh → Pi 로 변환해도, 자원 할당 그래프에 사이클을 형성하지 않을 경우에만 자원 요청을 허용한다. 이것이 RAG 알고리즘이다.
  
  

2.2.5 은행원 알고리즘⭐⭐⭐

개념

• 자원의 다중 인스턴스가 있을 경우에 사용한다.
• 은행이 대출을 해주는 방식, 즉 대출 금액이 대출 가능한 범위 내이면(안전 상태이면) 허용되지만, 그렇지 않으면 거부되는 것과 유사해서 은행원 알고리즘이라고 불리게 되었다.
• 우동 10인분과 스파게티 20인분을 만들 수 있는 분량의 재료가 있고, 12명의 사람이 있을 때 12명이 모두 우동을 시키면 문제가 될 것이다. 이와 같은 문제를 해결하는 알고리즘이다.

은행원 알고리즘 변수

변수	설명
n	프로세스의 수
m	자원의 종류 수
Total (전체 자원)	시스템 내의 전체 자원의 수
Available (가용 자원)	시스템 내 현재 사용할 수 있는 자원의 수 (가용 자원 = 전체 자원 - 모든 프로세스의 할당 자원)
Max (최대 자원)	각 프로세스가 필요로하는 최대 자원의 수 Max[i,j] = k 일 때, 프로세스i가 자원j를 최대 k개까지 요청할 수 있다.
Allocation (할당)	각 프로세스에 현재 할당된 자원의 수 Allocation[i,j] = k 일 때, 프로세스i가 자원j를 최대 k개 사용 중이라는 것이다.
Need (기대 자원)	각 프로세스가 향후 요청할 수 있는 자원의 수 Need[i,j] = k 일 때, 프로세스i가 자원j를 k개 더 요청한다는 것이다. (기대 자원 = 최대 자원 - 할당 자원)

은행원 알고리즘 예시1

• 전제

  • 프로세스 : P0 ~ P4까지 총 5개의 프로세스

  • 자원 : 총 3 종류의 자원 (A, B, C)

    • A=10개 인스턴스, B=5개 인스턴스, C=7개 인스턴스
      
      

    
    

• Step1. Need 구하기

  • Need = MAX - Allocation
    
    

  
  

• Step2. 안전 순서 찾기

  • 각 프로세스가 필요로하는 Need의 수와 Available을 비교했을 때, Need<= Available를 만족한다면 실행 가능, 아니라면 다음 프로세스로 순서 넘어간다.
  • 만족한 프로세스가 없다면, 그 시스템은 불안전한 시스템이다.
    
    

• 안전 상태인가?
  • <P1, P3, P4, P2, P0> 순서대로 실행 시, 안전 상태가 될 수 있다.
  • <P1,P3,P4,P0,P2> 순서로 실행해도 시스템은 안전 상태이다.
  • 즉, 모든 프로세스가 Available 범위내에서 실행되었으므로 시스템은 처음부터 끝까지 안전 상태이다.

은행원 알고리즘 예시 2

• P1이 자원(1, 0, 2)를 추가로 요청한 상황, 과연 안전할까?
  
  

  
  

  • Step1. Reqeust₁ <= Need₁ // 유효한 요청인가?
    • (1 ,0, 2) <= (1, 2, 2) ➡️ TRUE!
      
  • Step2. Reqeust₁ <= Available // 들어줄 수 있는 요청인가?
    • (1 ,0, 2) <= (3, 3, 2) ➡️ TRUE!
      
  • Step3. 요청 수락을 가정하고 안전 순서 찾기
    • <P1, P3, P4, P0, P2> 순서대로 실행 시, 안전 상태가 될 수 있다.

은행원 알고리즘 예시 3

• P4가 자원(3, 3, 0)를 추가로 요청한 상황, 과연 안전할까? (3, 3, 0) <= (2, 3, 0) ➡️ false : 가용 자원이 모자라기 때문

은행원 알고리즘 예시 4

• P0가 자원(0, 2, 0)를 추가로 요청한 상황, 과연 안전할까?
  
• Step1. Reqeust <= Need // 유효한 요청인가?
  • (0 ,2, 0) <= (7, 4, 3) ➡️ TRUE!
    
• Step2. Reqeust <= Available // 들어줄 수 있는 요청인가?
  • (0 ,2, 0) <= (2, 3, 0) ➡️ TRUE!
    
• Step3. 요청 수락을 가정 ➡️ 불안정 상태가 되므로 P0에게 추가 자원 할당 불가하다.
  
  

2.2.6 탐지 및 회복

탐지

• 대기 그래프
  • 자원 타입의 노드를 제거하고, 간선들을 결합
    
    
• 대기 그래프의 사이클을 탐지하는 알고리즘을 주기적으로 호출 → 사이클이 있으면 교착상태 존재
  
  
• 오버헤드 발생

탐지 시 회복

• 죽일 프로세스 결정 → 프로세스를 다 죽이거나 또는 한 개씩 죽임 → 데드락이 해결되었다면 종료, 해결되지 않았다면 계속 죽임
• starvation 가능