[운영체제] Deadlock

Deadlock

교착 상태 (deadlock)

• 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태
• 리소스 (자원)
  • 하드웨어, 소프트웨어 등을 포함하는 개념
  • I/O device, CPU cycle 등

데드락 발생의 4가지 조건

1. Mutual Exclusion (상호 배제)
   1. 매 순간 하나의 프로세스만이 자원 사용 가능
2. No Preemption (비선점)
   1. 자원을 스스로 내놓고 강제로 뺴앗기지 않음
3. Hold and Wait (보유 대기)
   1. 보유 자원을 놓지 않고 계속 가지고 있음
4. Circular Wait (순환 대기)
   1. 자원을 기다리를 프로세스간에 사이클이 형성됨

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

• 동그라미 : 프로세스
• 네모 : 자원
• p → R : 프로세스가 해당 자원을 요청함
• R → P : 해당 프로세스가 해당 자원을 가지고 있음
• 자원 안의 점 : 인스턴스의 수
• Cycle이 없으면 데드락이 아님
• Cycle이 있으면
  • 만약 리소스당 하나의 인스턴스만 있으면, 데드락
  • 자원에 여러 인스턴스가 있으면, 데드락이 발생할 수도 있음

데드락 처리 방법

• Prevention (예방)
  • 4가지 조건중 하나를 민족되지 않게 만들기
• Avoidance (회피)
  • 자원 요청에 대한 부가 정보를 이용하여 데드락 가능성 없을때만 자원 할당
  • 시스템 state가 원래 state로 돌아올 수 있을때만 자원 할당
• Detection and Recovery (탐지 및 회복)
  • 데드락 발생은 허용하되 그에 대한 탐지 루틴을 두어 발견 시 recover
• Ignorance (무시)
  • 데드락을 시스템이 책임지지 않음
  • 대부분의 OS가 채택
• 위 둘은 미연에 방지, 아래 둘은 방목형

데드락 예방

• Mutual Exclusion
  • 공유해서는 안되는 자원의 경우 반드시 성립해야함
  • 막을 수 없는 조건
• Hold and Wait
  • 프로세스가 자원 요청 시 다른 어떤 자원도 안 가져야 함
  • 방법 1 : 프로세스 시작 시 모든 필요한 자원을 할당받게
  • 방법 2 : 자원 필요 시 보유 자원을 모두 놓고 다시 요청
• No Preemption
  • process가 어떤 자원을 기다리는 경우 이미 보유한 자원이 선점됨
  • 모든 필요한 자원을 얻을 수 있을 때 프로세스 다시 시작
  • State를 쉽게 save하고 restore할 수 있는 자원에 주로 사용 (CPU, Memory)
• Circular Wait
  • 모든 자원에 할당 순서 정해서 그 순서대로만 자원 할당

→ Utilization 저하, throughput 감소, starvation 문제 발생 가능

데드락 회피

• 자원 요청 부가 정보를 이용해서 자원 할당이 안전(safe)한지를 동적으로 판단
• unsafe state라고 해서 무조건 데드락 발생은 아님
• 그러나 회피 방법은 아예 unsafe state로 가지 않게 만드는 방법
• 자원마다 인스턴스 하나
  • Resource Allocation Graph algorithm
• 자원마다 인스턴스 둘 이상
  • Banker’s algorithm

RAGA

• 자원 할당 그래프와 거의 일치
• 점선 추가(Claim edge, P → R) : 이 프로세스가 적어도 한번은 해당 자원을 사용할 경우가 있다(미래에)
  • 자원 요청 시 실선으로 바뀜
• 사이클 생성 여부 조사시 프로세스 수가 n일 때 O(N^2) 시간 소요

은행원 알고리즘

• 최대 사용 자원 양을 미리 계산
• Need는 최악의 경우 이렇게 한번에 요청할 수 있음을 나타냄
• Allocation은 현재 할당된 상태를 의미
• 항상 최대 요청을 할것이라는 가정 → Need 보다 Available이 커야만 할당해줌
• 효과적이나 비효율적임

데드락 탐지 및 회복

• 탐지
  • 자원당 하나의 인스턴스만 → wait-for graph로 확인
    • 회피와 다른점 → 자원의 최대 사용량을 미리 알 필요 없음 → 그래프에 점선이 없음 (Wait for 그래프)
    • O(n^2) 시간이 걸림
  • 자원 당 여러 인스턴스 → 은행원 알고리즘과 유사한 방법으로 탐지
    • 역시 최대 사용량을 미리 알 필요 없음
    • Request는 추가 요청 가능량이 아니라 현재 실제로 요청한 자원량임
    • Allocation은 현재 할당되어있는 상태를 나타냄
• 회복
  • 프로세스 종료
    1. 데드락에 연루된 모든 프로세스 죽이기
    2. 연루된 프로세스 하나씩 죽이면서 사이클 사라질때까지
  • 자원 선점
    • 희생양 찾아서 자원을 뺏어서 데드락 없앰
    • 기아 문제
      • 동일 프로세스가 계속 victim으로 선정되는 경우
      • cost factor에 rollback 횟수도 같이 고려해야함

데드락 무시

• 데드락에 대해 아무런 조치를 취하지 않음
• 데드락이 매우 드문데 조치 자체가 더 큰 오버헤드가 될 수 있으므로
• 발생 경우 사람이 직접 process 를 죽이는 등 알아서