데드락(Deadlock, 교착상태)에 대해

데드락이란, 둘 이상의 프로세스가 서로 상대방의 작업이 끝나기만을 기다리며 무한 대기에 빠지는 상황을 말한다.

 

 

데드락의 발생 조건

• 상호 배제(Mutual exclusion)
  한 번에 하나의 프로세스만 해당 자원을 사용할 수 있다.
• 점유 대기(Hold and wait)
  자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 기다린다.
• 비선점(non-preemptive)
  다른 프로세스의 사용이 끝날 때까지 자원을 빼앗을 수 없다.
• 순환 대기(Circular wait)
  각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

 

데드락의 관리 방법

1. 예방 : 발생조건의 제거

• 상호 배제(Mutual exclusion) 제거
  한 번에 여러 프로세스가 공유 자원을 사용할 수 있도록 변경한다
  - 동기화 문제를 해결해야 함
• 점유 대기(Hold and wait) 제거
  프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고, 허용될 때까지 작업을 보류한다
• 비선점(non-preemptive) 제거
  높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 변경한다
• 순환 대기(Circular wait) 제거
  순환형태로 대기하지 않게 하기 위해, 일정한 한 쪽 방향으로만 자원을 요구하도록 변경한다
  

  

2. 회피

자원을 할당한 후에도 항상 안전상태에 있을 수 있도록 자원을 할당하는 방법

- 안전 상태(Safe State) : 프로세스들이 요청하는 모든 자원을 데드락 없이 차례로 모두에게 할당할 수 있는 상태

- 안전 순서(Safe sequence) : 프로세스에 자원을 할당할 때 데드락이 발생하지 않는 순서

 

- 은행원 알고리즘 참고

다익스트라가 제안한 기법으로, 어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전에, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션 해서 Safe state에 들 수 있는지 여부를 검사하는 방법

- Max(최대 요구 가능 자원)

- Allocation(현재 할당 자원)

- Available(가용자원)

- Need(필요 자원)

 

 

3. 탐지

- 자원 할당 그래프 알고리즘

자원 할당 그래프란, 프로세스가 자원을 요청하고 자원이 프로세스에게 할당되는 방향성을 가진 그래프로 데드락을 탐지할 수 있는 그래프다.

데드락에 빠지지 않은 / 데드락에 빠진 자원 할당 그래프

P는 프로세스, R은 자원, 빨간 색 화살표는 할당된 상태, 파란색 화살표는 자원 요청 후 대기 상태를 의미한다.

우측 그래프는 데드락에 빠진 경우의 자원 할당 그래프이다.

• P3 -> R2 -> P2 -> R3 -> P3
• P3 -> R2 -> P1 -> R1 -> P2 -> R3 -> P3

4. 회복

- 프로세스 중단 : 교착상태에 빠진 모든 프로세스를 중단하거나, 하나씩 중단시키며 데드락을 탐지, 회복하는 방법

- 자원 선점하기 : 프로세스에 할당된 자원을 선점하여, 교착상태가 해결될 때까지 자원을 다른 프로세스에 할당해주는 방법 

 

---

참고

ChanBLOG - [운영체제] 데드락(Deadlock, 교착 상태)이란?

코딩팩토리 - [OS] 교착상태란 무엇인가?

진리는어디에 - 데드락(Deadlock) 개념 정리

양햄찌가 만드는 세상 - [운영체제] 교착상태 회피-은행원 알고리즘