[운영체제] 7. 데드락

7. 데드락

The Deadlock Problem

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

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

Deadlock 발생의 4가지 조건

• Mutual Exclusion (상호 배제) - 하나의 프로세스만이 자원 사용 가능
• No Preemption (비선점) - 자원을 강제로 빼앗기지 않음
• Hold and Wait (보유 대기) - 보유 자원을 놓지 않고 계속 가지고 있음
• Circular Wait (환형 대기) - 자원을 기다리는 프로세스 간에 사이클 형성

4가지 조건을 모두 만족해야 Deadlock 발생

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

Vertex (Process, Resource)
Edge (request edge, assignment edge)

• 그래프에 cycle이 없으면 deadlock 아님
• 그래프에 cycle이 있으면
  • 자원의 인스턴스가 1개 - deadlock
  • 자원의 인스턴스가 여러개 - deadlock 가능성 있음

Deadlock Prevention

Deadlock의 4가지 필요 조건 중 하나가 만족되지 않도록 하는 것

• Mutual Exclusion - 반드시 성립
• Hold and Wait
  • 프로세스 시작 시 모든 자원을 할당받게 하는 방법 (자원 낭비)
  • 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
• No Preemption
  • 빼앗을 수 있는 자원 (CPU, Memory - state 쉽게 저장 가능) 한정되어 있음
• Circular Wait
  • 모든 자원에 할당 순서(우선순위)를 정해 순서대로만 자원 할당

→ utilization 저하, throughput 감소, starvation 문제

Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용해서 deadlock 가능성이 없는 경우에만 자원 할당

safe state - 자원 할당, unsafe state - deadlock 가능성 있음
시스템이 unsafe state에 들어가지 않는 것을 보장

safe sequence - 프로세스의 자원 요청이 가용 자원 + 작업이 완료된 모든 프로세스의 보유 자원에 의해 충족

• Resource Allocaion Graph algorithm
  Multiple instances per resource types
  Claim edge P → R
  프로세스 P가 자원 R을 미래에 요청할 수 있음 (점선)
  프로세스가 해당 자원 요청 시 request edge로 바뀜 (실선)
  자원이 release 되면 assignment edge → claim edge
  점선을 포함해서 cycle이 생기지 않는 경우에만 request edge → assignment edge 변경

• Banker’s Algorithm
  Multiple instances per resource types
  가용 자원 내에서 프로세스의 최대 요청을 처리할 수 있는 경우에만 할당
  → 프로세스 종료 후 자원 반납 → 가용 자원 늘어남
  프로세스의 최대 자원 요청량을 미리 안다는 것을 전제
  

Deadlock Detection and Recovory

• Deadlock Detection
  • Single instance
    Resource Allocation Graph algorithm
    → Wait-for graph (프로세스만으로 노드 구성)
  • Multiple instance
    자원 요청이 없는 프로세스가 가진 자원을 내어놓는다고 가정
    → 현재 요청된 자원을 만족할 수 있는 Sequence가 존재
    → No deadlock (현재)
• Recovery
  • Process termination
    Abort All
    Abort one process at a time (데드락이 없어질 때 까지)
  • Resource Preemption
    비용을 최소화하는 victim 선정 → safe state로 restart
    Starvation - 동일한 프로세스가 계속 victim으로 선정
    → rollback 횟수도 같이 고려

Deadlock Ignorance

Deadlock이 매우 드물게 발생하므로 조치를 취하는 것이 더 큰 overhead가 될 수 있음 → 아무런 조치 X
대부분의 현대의 범용 운영체제가 채택
사람이 직접 프로세스를 죽이는 등의 방법으로 대처