7. Deadlocks

Deadlocks

The Deadlock Problem

• Deadlock: 일련의 프로세스들이 서로가 가진 자원을 기다리며 Block된 상태
• Resource
  • 하드웨어, 소프트웨어 등을 포함하는 개념
  • ex) I/O device, CPU Cycle, Memory space, Semaphore 등
  • 프로세스가 자원을 사용하는 절차
    • Request, Allocate, Use, Release
• Deadlock example 1
  • 시스템에 2개의 Tape drive가 있음
  • 프로세스 P1과 P2 각각이 하나의 Tape drive를 보유한 채 다른 하나를 기다림
• Deadlock example 2

Deadlock 발생의 4가지 조건

• Mutual exclusion
  • 매 순간 하나의 프로세스만이 자원의 사용 가능
• No preemption
  • 프로세스는 자원을 강제로 빼앗기지 않음
• Hold and wait
  • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 기다림
• Circular wait
  • 자원을 기다리는 프로세스 간 사이클이 형성됨
  • 프로세스 P0, P1, ..., Pn이 있을 때
    • P0은 P1이 가진 자원을 기다림
    • P1은 P2가 가진 자원을 기다림
    • Pn-1은 Pn이 가진 자원을 기다림
    • Pn은 P0이 가진 자원을 기다림

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

• Deadlock 여부를 확인하기 위한 그래프

Deadlock의 처리 방법

• Deadlock Prevention
  • 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
• Deadlock Avoidance
  • 자원 요청에 대한 부가적 정보를 이용해서 Deadlock의 가능성이 없는 경우에만 자원 할당
  • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
• Deadlock Detection and recovery
  • Deadlock 발생은 허용하되 그에 대한 Detection 루틴을 두어 Deadlock 발견 시 Recovery
• Deadlock Ignorance
  • Deadlock을 시스템이 책임지지 않음
  • UNIX를 비롯한 대부분의 OS가 채택

Deadlock Prevention

• Mutual exclusion
  • 반드시 성립해야 하는 조건
• Hold and wait
  • 1. 프로세스 시작 시 모든 필요한 자원을 할당 받게 하는 방법
  • 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
• No preemption
  • 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원은 다른 프로세스에 의해 선점됨
  • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작
  • state를 쉽게 저장하고 복구할 수 있는 자원에서 주로 사용(CPU, memory)
• Circular wait
  • 모든 자원 유형에 할당 순서 정하여 정해진 순서대로만 자원 할당
• 생기지도 않을 Deadlock의 고려로 인해 비효율적 시스템 설계로 이어질 수 있음

Deadlock Avoidance

• 자원 요청에 대한 부가정보를 이용해서 자원을 할당하는 것이 Deadlock으로부터 안전한지를 조사해서 안전한 경우에만 할당
• 가장 단순하고 일반적 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법
• Safe State
  • 시스템 내의 프로세스들에 대한 Safe Sequence가 존재하는 상태
• Safe Sequence
  • 프로세스의 Sequence가 Safe하려면 Pi의 자원 요청이 가용 자원 + 모든 Pj(j < i)의 보유 자원에 의해 충족되어야 함
  • 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
    • Pi의 자원 요청이 즉시 충족될수 없으면 모든 Pj가 종료될 때 까지 기다림
    • Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행

Resource Allocation Graph Algorithm

• 점선은 프로세스가 평생에 한 번은 해당 자원을 사용할 수 있다는 것을 의미

Banker's Algorithm

• 가정
  • 모든 프로세스는 자원의 최대 사용량을 미리 명시
  • 프로세스가 요청 자원을 모두 할당 받은 경우 제한된 시간 안에 이들 자원을 다시 반납
• 방법
  • 기본 개념: 자원 요청 시 safe 상태를 유지할 경우에만 할당
  • 총 요청 자원의 수가 가용 자원의 수 보다 적은 프로세스를 선택 (해당 프로세스 없으면 unsafe 상태)
    • 그런 프로세스가 있으면 그 프로세스에게 자원 할당
  • 할당 받은 프로세스가 종료되면 모든 자원 반납
  • 모든 프로세스가 종료될 때 까지 이 과정 반복

Deadlock Detection and recovery

• Deadlock Detection
  • Resource type 당 single instance인 경우
    • 자원 할당 그래프에서의 cycle이 곧 deadlock을 의미
  • Resource type 당 multiple instance인 경우
    • Banker's algorithm과 유사한 방법 활용
      • 사실 single instance인 경우에도 이 방법 활용하는 것이 더 효율적
    • 낙관적으로 Request가 없는 프로세스는 소유한 자원을 반납할 것이라고 가정
• Wait-for graph Algorithm
• Resource type 당 single instance인 경우
• Wait-for graph

• 자원 할당 그래프의 변형
• 프로세스만으로 node 구성
• Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk -> Pj
• Algorithm
  • Wait-for graph에 cycle이 존재하는지를 주기적으로 조사
  • O(n^2): n(n-1) 만큼의 화살표가 존재할 수 있기 때문
• Recovery
  • Process termination
    • 1. Deadlock에 연루된 모든 프로세스 종료
    • 2. Deadlock cycle이 제거될 때 까지 한 번에 하나의 프로세스씩 종료
  • Resource Preemption
    • 비용을 최소화 할 Victim의 선정
    • Safe state로 Rollback하여 프로세스 재시작
    • Starvation 문제
      • 동일 프로세스가 계속해서 Victim으로 선정되는 경우
      • -> Cost factor에 Rollback 횟수도 같이 고려!

Deadlock Ignorance

• Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
• 만약 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 느낀 프로그래머가 직접 프로세스를 죽이는 등의 방법으로 대처