---

DeadLock (교착상태)

DeadLock Problem

DeadLock

• 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

Resource

• 하드웨어, 소프트웨어 등을 포함하는 개념 (ex. I/O device, CPU cycle, memory space, semaphore)

• 프로세스가 자원을 사용하는 절차 (Request, Allocate, Use, Release)

DeadLock Example1

• 시스템에 2개에 tape drive가 있다.

• 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다.

DeadLock Example2

• Binary semaphores A and B
  

DeadLock 발생 조건

• 1. Mutual exclusion (상호 배제)
     매 순간 하나의 프로세스만이 자원을 사용할 수 있음
• 2. No preemption (비선점)
     프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
• 3. Hold and wait (보유대기)
     자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
• 4. Circular wait (순환대기)
     자원을 기다리는 프로세스간에 사이클이 형성되어야 함
     ex) 프로세스 P0, P1, ... , Pn이 있을때
     P0은 P1이 가진 자원을 기다리고, P1은 P2가 가진 자원을 기다리고...

Resource-Allocation Craph (자원 할당 그래프)

• 그래프에 cycle이 없으면 deadlock이 아님

• 그래프에 cycle이 있으면

  1. 자원당 인스턴스가 1개이면, 사이클은 deadlock이다.
  2. 자원당 인스턴스가 여러개이면 데드락일 가능성이 있다.

Deadlock 처리 방법

방지

1. Deadlock Prevention

자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

조건

• 1. Mutual exclusion (상호 배제)
     공유해서는 안되는 자원의 경우 반드시 성립해야함
• 2. No preemption (비선점)
     process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
     모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다
     State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory)
• 3. Hold and wait (보유대기)
     프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다

     1. 프로세스가 시작 시 모든 필요한 자원을 미리 할당받게 하는 방법
     2. 자원이 필요한 경우 자원을 모두 놓고 다시 요청

• 4. Circular wait (순환대기)
     모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
     예를 들어 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj를 할당받기 위해서는 우선 Ri를 release해야 한다

=> Utilization저하, throughput감소, starvation문제

2. Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

• 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로 부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법
• 시스템이 unsafe state에 들어가지 않는 것을 보장
• 2가지 경우 avoidance 알고리즘 사용

Single instance per resource types (Resource Allocation Graph algorithm 사용)

request의 assignment변경 시 cycle이 생기지 않는 경우에만 요청 자원을 할당
Cycle 생성 여부 조사시 프로세스의 수가 n일 때 O(n제곱)의 시간이 걸린다

Multiple instances per resource types (Banker's Algorithm 사용)

후처리

3. Deadlock Detection and recovery

Deadlock 발생은 허용하되, 그에 대한 detection루틴을 두어 deadlock 발견시 recover

1. Resource-Allocation Graph
   

• Resource당 single instance인 경우
  자원할당 그래프에서의 cycle이 곧 Deadlock
• Resource type당 multiple instance인 경우
  Banker's algorithm과 유사한 방법 활용
  

2. Corresponding wait-for graph
   

• Resource type 당 single instance인 경우

• wait-for graph
  자원할당 그래프의 변형
  프로세스만으로 node구성
  Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk->Pj

• Algorithm
  Wait-for-graph에 사이클이 존재하는지를 주기적으로 조사
  O(n제곱)시간 소요

• Recovery
  ○Process termination
  deadlock 프로세스 전부 제거
  deadlock사이클이 제거될 때까지 한번에 한 프로세스씩 제거

  ○Resource Preemption
  비용을 최소화할 희생양 선정
  safe state로 rollback하여 프로세스 시작
  Starvation문제
  동일한 프로세스 연속 희생양 선정
  비용 요소에 rollback횟수 고려

4. Deadlock ignorance (현재 주요 사용)

Deadlock을 시스템이 책임지지 않음
대부분의 OS가 채택

• Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음

  매우 드물게 발생하므로 조치 자체가 더 큰 overhead라고 생각
  만약 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 방법 등으로 대체

---