[OS] Deadlocks

박시은·2023년 12월 9일

OS

목록 보기

26/27

▶ Deadlocks

▷ 개요

개념
- 교착상태
- 두 개 이상의 프로세스가 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에, 무한 대기 상태에 빠지는 상태
- 한정된 자원을 프로세스가 사용하려고 할 때 발생한다.
프로세스는 아래와 같은 순서로만 자원을 사용할 수 있다.
- Request (요청)
- Use (사용)
- Release (방출)

▷ 데드락 발생조건⭐⭐

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

① 상호 배제

상호 배제
- 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다.
- 다른 프로세스가 그 자원을 사용하려 할 경우, 그 프로세스는 자원의 사용이 끝날 때까지 지연되어야 한다.

② 점유 대기

점유 대기
- 프로세스가 최소한 한 개의 자원은 점유해야 하고, 점유한 자원을 얻기 위해 대기하는 프로세스가 존재해야 한다.
- 아래 그림에서 볼 수 있듯, P₀ 이 R₀를 사용하고 있는 상태에서 R₁을 요구하고 있는 것을 확인할 수 있다.
  (하나 이상의 자원을 가지고 있는 상태에서 공유 자원을 요청한 상황)

③ 비선점

비선점 (No preemption)
- 프로세스가 사용하는 자원을 중간에 다른 프로세스가 가져갈 수 없다.
- 프로세스가 작업 종료 후에 자발적으로 자원을 방출한다.

④ 순환 대기

순환 대기
- 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.
- 아래 그림에서 볼 수 있듯 P₁이 R₁을 사용하고 있고, P₀가 R₀을 사용하고 있는 상태에서 서로 자원을 요구하고 있는 것을 알 수 있다. 이때, P₀과 P₁은 교착상태에 해당한다.

▷ 자원 할당 그래프(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
- 즉, 각 자원 유형이 여러 개의 인스턴스가 존재하면, 사이클이 반드시 교착상태가 발생했음을 의미하지는 않는다. (가능성만 존재)
- ex. P1 -> R1 -> P3 -> R2 -> P1인 상황에서 R2는 2개의 인스턴스를 갖고있다.

▶ 데드락 해결 방법

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

▷ 예방

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

상호 배제 부정
- 여러 개의 프로세스가 동시에 공유자원을 사용할 수 있게 한다. → but 상호 배제 제한 불가능
점유 대기 부정
- 프로세스가 자원을 요청할 때마다 다른 자원을 보유하지 않도록 보장해야 한다.
- 또는 자원을 전혀 소유하지 않은 프로세스만 자원을 요청하게 해야한다.
비선점 부정
- 할당 받을 수 없는 자원을 요청할 때 점유하고 있는 모든 자원을 반납하고 대기하게 한다.
순환 대기 부정
- 자원 타입에 순서를 매기고, 일정한 한 쪽 방향(오름차순)으로만 자원을 요구할 수 있도록 한다.

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

▷ 회피

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

데드락 회피를 위한 조건
- 각 프로세스가 필요한 각 자원의 최대 인스턴스를 선언한다.
- 자원할당 상태를 검사하여 순환대기 상태가 없도록 한다.
- 자원 할당 상태는 ‘사용가능한 자원 수’ 와 ‘할당된 자원 수’ 와 ‘프로세스의 최대 요구 자원 수’ 에 의해 정의된다.
안전상태(Safe State)⭐
- 안전한 상태일 때에만 자원 할당
- 시스템의 프로세스들이 요청하는 모든 자원을 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있다면 안전상태이다.
- ex. 시스템에 12개의 자원이 있고, 현재 사용량이 9라면 가용 자원은 3이다.
  - 이때, 특정 순서로 실행했을 때 데드락이 걸리지 않는다면 안전상태
  - 어떤 순서로 실행해도 안전 상태가 아닐 때 불안전한 상태 → 데드락 발생
  - 데드락은 불안전한 상태일 때만 발생하므로, 안전한 상태만 유지하면 데드락 회피 가능
정리
- 시스템이 안전 상태인 경우 ⇒ 교착 상태가 발생하지 않는다.
- 시스템이 안전하지 않은 상태일 경우 ⇒ 교착 상태가 발생할 가능성이 존재한다. (무조건 발생하는 것이 아님⭐)
- 회피란 ⇒ 시스템이 안전하지 않은 상태로 들어가지 않도록 하는 것이다.

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

① RAM : 회피 알고리즘

RAG의 간선 종류
- 요청 간선
- 할당 간선
- 예약 간선 ➡️ 예약 간선이 추가됨!!!!
예약간선
- Pi → Rj 는 프로세스 Pi 가 미래에 자원 Rj 를 요청하는 의미
- 시스템에서 자원은 반드시 미리 예약되어야 한다.
간선의 변환
- 프로세스가 자원을 요청할 때 예약 간선이 요청 간선으로 변환
- 자원이 프로세스에 할당되면 요청 간선이 할당 간선으로 변환
- 자원이 프로세스에 의해 방출되면, 할당 간선은 예약 간선으로 재 전환
예시
- 프로세스 Pi 가 자원 Rj를 요청한다고 가정하자.
- 요청 간선 Pi → Rj 를 할당 간선 Rjh → Pi 로 변환해도, 자원 할당 그래프에 사이클을 형성하지 않을 경우에만 자원 요청을 허용한다. 이것이 RAG 알고리즘이다.

② 은행원 알고리즘⭐⭐⭐

매우중요!!!!!!!!!!!!!!!! ⭐⭐⭐🏦🪙🤑🤑🤑🤑💲💲💸💸💰💱⭐⭐⭐⭐⭐⭐⭐⭐

개념
- 자원의 다중 인스턴스가 있을 경우에 사용한다.
- 은행이 대출을 해주는 방식, 즉 대출 금액이 대출 가능한 범위 내이면(안전 상태이면) 허용되지만, 그렇지 않으면 거부되는 것과 유사해서 은행원 알고리즘이라고 불리게 되었다.
- 우동 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에게 추가 자원 할당 불가하다.

③ 탐지 및 회복

탐지
- 대기 그래프
  - 자원 타입의 노드를 제거하고, 간선들을 결합
- 대기 그래프의 사이클을 탐지하는 알고리즘을 주기적으로 호출 → 사이클이 있으면 교착상태 존재
- 오버헤드 발생
탐지 시 회복
- 죽일 프로세스 결정 → 프로세스를 다 죽이거나 또는 한 개씩 죽임 → 데드락이 해결되었다면 종료, 해결되지 않았다면 계속 죽임
- starvation 가능