[운영체제] 데드락 (Deadlock)

✅ 교착상태 (Deadlock)란?

: 일련의 프로세스 혹은 스레드들이 서로가 점유한 자원을 기다리며 무한 대기하는 상태

 

자원: 하드웨어, 소프트웨어 등을 포함하는 개념 
ex) I/O 장치, CPU cycle, Semaphore 등

 

다중 프로그래밍에서는 여러 스레드가 자원을 두고 경쟁하게 된다.

스레드는 필요한 자원을 요청하며, 요청한 자원이 현재 사용 불가능하면 waiting 상태가 된다.

 

그런데 요청한 자원이 다른 대기 중인 스레드에 의해 점유되고 있다면,
서로가 서로의 자원을 기다리면서 모든 스레드가 다시 활성 상태로 전환되지 못하는 교착 상태(deadlock)가 발생한다.

 

---

 

✅ 교착상태 발생 조건 4가지

 

📍 상호 배제 (Mutual Exclusion)

: 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

 

프로세스에는 자원이 공유 불가능한 상태로 할당되어 있어야 한다.

만약 다른 프로세스가 점유한 자원을 요청하면, 요청한 프로세스는 해당 자원이 해제될 때까지 대기해야 한다.

 

---

 

📍 점유 및 대기 (Hold and Wait)

: 프로세스가 할당된 자원을 가진 상태에서, 다른 자원을 기다림

 

프로세스는 이미 하나의 자원을 점유한(hold) 상태에서 다른 프로세스가 점유하고 있는 자원을 추가로 기다린다.(wait)

 

---

 

📍비선점 (Non-Preemption)

: 프로세스가 어떤 자원의 사용을 끝날 때까지 그 자원을 뺏을 수 없음

 

자원은 강제로 빼앗을 수 없다.

자원을 반환하는 것은 오직 해당 자원을 점유하고 있는 프로세스만 할 수 있다.

 

---

 

📍 순환 대기 (Circular Wait)

: 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 갖고 있음

 

프로세스들이 순환 형태로 서로의 자원을 기다린다.

 

대기 중인 스레드들의 집합 {T₀, T₁,..., Tₙ}이 존재하면

• T₀는 T₁이 점유하고 있는 자원을 기다리고,
• T₁은 T₂가 점유하고 있는 자원을 기다리고,
• ...
• Tₙ은 다시 T₀가 점유하고 있는 자원을 기다린다.

 

---

✅ 교착상태 해결법 4가지

📍 예방

: 데드락 발생 조건 4가지 중 최소 1가지 이상 성립하지 않도록 하기

 

데드락은 앞서 말했던 4가지 조건이 동시에 성립할 때만 발생한다.

따라서 하나라도 충족하지 않으면 데드락은 구조적으로 발생할 수 없다.

 

조건	예방 방법
상호 배제	X (공유 불가능한 자원은 반드시 성립해야 함)
점유 및 대기	프로세스가 자원을 요청할 때 다른 자원을 점유하고 있지 않아야 한다.
비선점	다른 프로세스가 선점 가능하도록 한다.
순환 대기	모든 자원에 할당 순서를 정해서, 정해진 순서대로만 자원을 할당한다.

 

 

주로 순환 대기를 방지하는 방법을 통해 데드락을 예방한다.

---

 

📍 회피

: 데드락의 가능성이 없는 경우만 자원을 할당

 

실행 환경에서 자원 요청에 대한 부가적인 정보(현재 사용 가능한 자원, 이미 할당된 자원 등)를 이용해서 데드락의 가능성이 없는지 판단한다.

데드락의 가능성이 없다는 것은 안전한 상태(safe state)를 의미하고, safe sequence가 존재하여 모든 프로세스가 정상적으로 종료할 수 있는 상태를 말한다.

 

safe sequence
: <T1, T2,..., Tn>처럼 스레드들의 순서를 정해놓고,
이 순서에서 각 스레드 Ti가 필요로 하는 자원이 현재 가용 자원 + 이전 스레드들이 해제한 자원을 통해 충족될 수 있는 경우

 

 

예를 들어, 다음과 같은 상황은 safe state라고 할 수 있다.

• 시스템에 총 12개의 자원, 3개의 스레드(T0, T1, T2)가 존재
• 각 자원별 요구량은 다음과 같음
  • T0: 최대 10개
  • T1: 최대 4개
  • T2: 최대 9개
• t0 시점의 상황은 다음과 같음
  • T0가 5개의 자원 점유
  • T1이 2개의 자원 점유
  • T2가 2개의 자원 점유
  • 3개의 자원 사용 가능 상태

=> safe sequence <T1, T0, T2>가 존재하기 때문에 safe state라고 할 수 있다.

1. 현재 3개의 자원 가용
2. T1은 추가로 2개로 더 필요, 사용가능한 자원을 할당받고 작업 완료 (5개의 자원 가용)
3. T0는 추가로 5개의 자원 필요, 사용가능한 자원을 할당받고 작업 완료 (10개의 자원 가용)
4. T2는 추가로 5개의 자원 필요, 사용가능한 자원을 할당받고 작업 완료 

 

safe state는 데드락의 가능성이 없고, unsafe state는 데드락의 가능성이 있다.

(unsafe state는 항상 데드락인 것은 아니다.)

출처: "Operating System Concepts", Abraham Silberschatz

 

 

교착 상태 회피 알고리즘에는 대표적으로 은행원 알고리즘이 있다.

 

🔖 Banker Algorithm (은행원 알고리즘) 

: 자원 요청을 허락했을 때 데드락 발생 가능성이 있다면, 자원을 할당해도 안전할 때까지 계속 요청을 거절하는 알고리즘

 

각 자원마다 다수의 인스턴스가 존재하는 경우, 은행원 알고리즘으로 교착 상태를 회피할 수 있다.

• 프로세스 시작 시, 자신이 필요한 자원의 최대 개수를 미리 선언
• 각 프로세스에서 자원 요청이 있을 때, 요청 승인 후 safe state로 유지되는 경우만 자원 할당
• unsafe state가 예상되면 다른 프로세스가 끝날 때까지 대기

 

---

 

📍 탐지와 회복

: 데드락 발생은 허용하되, 그에 대해 탐지하는 루틴을 둬서 데드락 발견 시 회복

 

데드락 발생 시 회복 전략은 다음과 같다.

• 데드락에 빠진 프로세스는 모두 강제 종료한다.
• 자원의 일시적인 선점을 허용한다.

---

 

📍 무시

: 데드락을 시스템이 책임지지 않음

 

대부분의 OS가 이 방식을 채택한다.

 

---

✨ 데드락 추가 질문

 

[ 왜 현대 OS는 Deadlock을 적극적으로 처리하지 않을까? ]

- 데드락을 감지하고 복구하는 비용이 크다 -> 모든 프로세스의 자원 상태를 계속 모니터링해야 함
- 데드락 발생 빈도가 낮다 -> 대부분 프로그램은 데드락이 일어나지 않도록 설계함

=> 따라서 현대 OS는 데드락을 예방하거나 회피하는 대신, 개발자가 Deadlock-Free 한 코드를 작성하도록 요구한다.