13.Deadlock

The Deadlock Problem

• Deadlock?
  일련의 프로세스들이 서로가 가진 자원을 기다리며 blcok된 상태
• Resource(자원)
  1. 하드웨어, 소프트웨어 등을 포함하는 개념

  2. I/O device, CPU cycle, memory 공간, semaphore 등..

  3. 프로세스가 자원을 사용하는 절차

     • Request, Allocate, Use, Release

Deadlock 발생의 4가지 조건

• Mutual exclusion(상호 배제)
  매 순간 하나의 프로세스만이 자원을 사용할 수 있음

• Nopreemption(비선점) = 빼앗기지 않는다
  프로세스는 자원을 스스로 내어놓을 뿐 강제로 뺏지못한다

• Hold and wait(보유대기)
  자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

• Circular wait(순환대기)
  자원을 기다리는 프로세스간에 사이클이 형성되어야 함
  ex)
  프로세스 P_a,P_b,P_c이 있을때
  P_a는 P_b의 자원을 기다림
  P_b는 P_c의 자원을 기다림
  P_c는 P_a의 자원을 기다림

  Resource-Allocation Graph

  

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

• 그래프에 cycle이 있으면
  - instance가 하나일 경우 deadlock

  • instance가 여러개일 경우 일수도있고 아닐수되;.....

Deadlock의 처리 방법

• Deadlock prevention
  자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록함
• Deadlock Avoidance
  Deadlock의 가능성이 없는 경우에만 자원을 할당
• Deadlock Detection and recover
  Deadlock 발생은 허용하나 detection 루틴을 두어 발견시 recover
• Deadlock Ignorance
  그냥 놔둠
  

Deadlock Avoidance

• instance가 자원유형당 하나일 경우
  Resource Allocation Graph algorithm 사용
  
• 자원유형당 instance가 다양할 경우
  Banker's Algorithm 사용

Banker's Algorith

Banker 알고리즘은 시스템이 안전한 상태에 있는 경우에만 프로세스의 리소스 요청이 허용되도록 보장하여 시스템의 교착 상태를 방지하도록 설계되었습니다. Edsger Dijkstra가 소개했습니다.