데드락

Contents

1. 개념

2. 발생 조건

3. 해결 전략

---

1. 개념

두 개 이상의 프로세스 혹은 스레드가 서로가 가진 자원을 기다리며 무한히 대기하는 상태

---

2. 발생 조건

아래 4가지가 모두 만족되면 데드락 발생 가능

1. Mutual Exclusion
   • 한번에 하나의 프로세스·스레드만 리소스를 사용할 수 있다.
2. Hold and Wait
   • 자원을 하나 이상 보유한 상태에서 다른 자원을 기다린다.
3. No Preemption
   • 다른 프로세스의 자원을 강제로 빼앗을 수 없다.
4. Circular Wait
   • 프로세스들이 순환 형태로 서로 자원을 기다린다.

---

3. 해결 전략

3.1 예방(Deadlock Prevention)

4가지 조건 중 하나를 깨트려 데드락을 원천적으로 방지한다.

1. Mutual Exclusion 제거
   • 현실적으로 어렵다.(critical section, lock 등은 반드시 상호배제가 필요함)
2. Hold and Wait 제거
   • 모든 자원을 한번에 요청
   • 리소스 사용 효율이 떨어짐, starvation 발생 가능
3. No preemption 제거
   • 자원의 강제 회수를 허용
   • 프로세스가 하나 이상의 자원을 소유하고 있고, 즉시 할당받을 수 없는 다른 자원을 요청한다면 소유하고 있는 모든 자원을 반납한다.
   • rollback 필요
4. Circular Wait 제거
   • 자원에 순서를 부여하고 순서대로 요청

3.2 회피(Deadlock Avoidance)

시스템의 현재 상태외 미래 자원 요청을 고려하여 데드락이 발생하지 않는 경우에만 자원을 할당하는 전략

자원을 요청할 때마다 현재 상태와 미래 요청 가능성을 함께 고려한다.

• 시스템을 항상 Safe State(안전 상태) 로 유지
• 현재 이용 가능한 자원, 각각의 프로세스에 할당되어 있는 자원, 반납할 자원들의 정보를 바탕으로 잠재적 데드락의 유무를 판단
• 데드락을 완전히 방지하는 것이 아니라, 발생 가능성이 있는 상태(unsafe state)를 피하는 전략

Safe State:

• 모든 프로세스가 순서대로 자원을 할당받아 정상적으로 종료할 수 있는 상태

Banker’s Algorithm:

• 자원 요청을 허용했을 때 시스템이 안전 상태인지 검사한 뒤 할당하는 알고리즘

1. 데드락이 발생할 지 검사
   • R2를 P1과 P2가 요청할 때 P2에게 할당을 해주면 사이클이 생기며 데드락에 빠지는 것을 확인
2. R2를 P1에거 먼저 할당
3. P1이 작업 완료하고 R1와 R2를 반납
4. 반납된 자원으로 P2가 작업 수행(Safe State Sequence: P1 → P2)

3.3 감지 및 복구(Detection & Recovery)

데드락 발생을 허용하고, 발생 시 이를 감지하고 복구하는 전략

3.3.1 감지(Detection)

시스템이 현재 데드락 상태인지 판단

방법:

• Resource Allocation Graph(RAG)
  • 자원에 대한 소유하고 있는 상황도 표현
  • cycle 존재 → 데드락
• Wait-for-Graph
  • 프로세스 간 대기 관계만 표현
  • cycle 존재 → 데드락
• 다중 인스턴스 자원
  • Banker’s와 유사한 알고리즘으로 검사

특징:

• 데드락을 막지 않음
• 대신 발생 여부를 주기적으로 검사 → 비효율

3.3.2 복구(Recovery)

데드락 발생 후 이를 해소하는 방법

어떤 프로세스를 종료하거나 자원을 회수할지 선택하는 비용이 중요함 잘못 선택하면 starvation 발생 가능

프로세스 종료(Process Termination):

• 모든 프로세스 종료 or 하나씩 종료하며 데드락 해소
• 우선순위 / 작업 진행 정도 / 비용 등을 고려함
• 작업 유실 위험 있음

자원 선점(Resource Preemption):

• 데드락이 발생하기 전 상태로 Rollback
• 특정 프로세스로부터 자원을 강제로 회수
• 다른 프로세스에 재할당

3.4 무시(Ignore)

데드락이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는 방식

데드락이 매우 드물게 발생하기 때문에 이에 대한 조치 자체가 더 큰 오버헤드일 수 있다.

---

Prevention은 데드락의 발생 조건인 상호 배제, 점유 및 대기, 비선점, 순환 대기 중 하나를 제거해서 데드락 자체가 발생하지 않도록 하는 방법이고,

Avoidance는 자원을 할당하기 전에 시스템이 안전 상태인지 확인하고 unsafe state할 가능성이 있다면 자원을 할당하지 않는 방식이다.