7강) 데드락 (Deadlock - 교착상태)

** KOCW에서 반효경 교수님의 운영체제(2014년) 강의를 수강한 내용을 정리한 글입니다.

운영체제

 

 

The Deadloc Problem

• Deadlock
  • 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
• Resource
  • 하드웨어, 소프트웨어 등을 포함하는 개념
    • I/O device, CPU cycle, Memory space, Semaphore 등
  • 프로세스가 자원을 사용하는 절차는 Request, Allocate, Use, Release

 

Deadlock 발생의 4가지 조건 (&조건)

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

 

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

• P→R 화살표 : 요청
• R→P 화살표 : 할당
• Cycle이 없으면 deadlock이 아니다
• Cycle이 있으면 (No preemption, Hold and wait 가정)
  • 하나의 리소스에 하나의 인스턴스만 있다면 (cycle에서 사용하는 점이 하나라면) → Deadlock
• 왼쪽 그림
  • Cycle 2개가 각각 Mutual exclusion을 만족 → 남은 Resource가 없음
• 오른쪽 그림
  • P2에게 할당되어 있는 R1, P4에게 할당되어 있는 R2 → P2, P4가 R1 또는 R2를 반납하면 Deadlock이 해소됨 → Deadlock이 아님

 

Deadlock의 처리 방법

• Deadlock Prevention
  • 자원 할당 시 Deadlock의 4가지 필요 조건 중 하나가 만족되지 않도록 하는 것
• Deadlock Avoidance
  • 자원 요청에 대한 부가 정보를 통해 deadlock 가능성이 없을 때만 자원 할당
  • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
• Deadlock Detection and recovery
  • Deadlock 발생은 허용하되, 그에 대한 detection 루틴을 두어 발견 시 recover
• Deadlock Ignorance
  • Deadlock을 시스템이 책임지지 않음
  • UNIX를 포함한 대부분의 OS가 채택
    • 미연에 방지하는 것이 손해!
  • 작동 안 하면 사람이 알아서 프로세스를 종료하든 한다!

 

Deadlock Prevention

• Mutual Exclusion
  • 공유해서는 안되는 자원의 경우 만족할 수밖에 없음
• Hold and Wait
  • 프로세스가 자원을 요청할 때 다른 자원을 가지고 있지 않게 한다
  • 방법 1 : 프로세스 시작 시 필요한 모든 자원 할당
  • 방법 2 : 자원이 필요할 경우 보유 자원을 모두 놓기;
• No Preemption
  • 프로세스가 자원을 기다릴 때, 이미 보유한 자원이 선점됨
  • 모든 필요한 자원을 얻을 수 있을 때 프로세스 다시 시작
  • State를 쉽게 save, restore할 수 있는 자원에서 주로 사용 (CPU, Memory)
• Circular Wait
  • 모든 자원 유형에 할당 순서를 정한다.
    • 순서가 3인 Ri를 보유 중인 프로세스가, 순서가 1인 자원 Rj를 할당 받기 위해서는 Ri를 우선 release해야 한다

→ Utilization 저하, Throughput 감소, Starvation 문제

발생하지 않을 Deadlock을 위해 제약 조건을 달아놓아야 해서 비효율적이다.

 

Deadlock Avoidance

• Available이 Max보다 큰 프로세스에 대해서만 자원을 할당해준다
• P1 → P3 → P4 → P2 → P0 순서로 수행가능하므로 deadlock이 절대 생기지 않음 (다른 순서도 가능)
• 작은 Deadlock 가능성만 가지고도 할당을 하지 않으므로 비효율적

 

Deadlock Detection and Recovery

• Recovery
  • Process termination
    • Deadlock에 연루된 프로세스를 모두 종료
    • Deadlock cycle이 소멸될 때까지 프로세스를 하나씩 종료
  • Resource Preemption
    • 비용을 최소화 할 victim 선정
    • Safe state로 rollback하여 프로세스를 재시작
    • Starvation 문제
      • 동일한 프로세스가 계속 victim으로 선정되는 경우
        • Cost factor에 rollback 횟수도 같이 고려

 

Deadlock Ignorance

• Deadlock은 매우 드물게 발생 → 조치 자체가 더 큰 Overhead일 수 있음
• Deadlock 발생 → 시스템 비정상 작동 사람이 감지 → 직접 Process 종료 등
• UNIX, Windows 등 대부분의 범용 OS가 채택