Chapter 6: 교착 상태(Dead Lock)

6.1 교착 상태

둘 이상의 프로세스가 각자 가지고 있던 자원을 보유한 채로 외부적 조치가 없는 한 영원히 그 상태에서 기다리고 있는 상황

 

근본 원인

• 시스템이 가지고 있는 한정적인 자원보다 사용하고자 하는 프로세스들의 요청이 더 많아서 생김

 

문제점

• 프로세스들이 더 이상 실행되지 못하여 사용자들에게 응답해 주지 못한다.
• 보유된 자원들이 교착 상태에서 벗어나기 전까지 전혀 활용되지 못한다.

 

자원 (Resource)

선점 가능(Preemptible)	선점 불가능(Nonpreemptible)
운영체제에 의해 사용 도중 뺏길 수 있음	선점이 불가능(뺏길 시 정상 진행 포기해야함)

 

공유 가능 자원(Sharable)	배타적 사용 자원(Exclusive)
동시에 사용가능	한번에 하나씩 사용
공유가능 프로그램, 공유 데이터	CPU, 메모리, 테이프, 버퍼, 키보드, 모니터

 

순차적 재사용 가능 자원(Serially Reusable)	소모성 자원(Consumable)
아무리 사용채도 없어지지 않고 영구히 존재	사용 후 사라짐
CPU, 메모리, 테이프, 하드디스크, 버퍼, 프로그램	시그널, 메세지

 

 

프로세스

(요청과 반납은 시스템콜을 함으로써 운영체제에서 이루어짐, 대기상태 깨우기도 운영체제)

• 필요한 자원에 대한 요청(Request)
  • 사용 가능(Available) = 자원 할당 후 사용
  • 사용 중 = 반납되어질 때까지 대기
  • → 대기 중에서는 자력으로 그 상태에서 벗어날 수 없음
• 사용이 끝난 자원의 반납

 

🚫 교착 상태의 원인

4가지 조건 모두 갖춰질 때 데드락

1. 자원의 배타적 사용
   • 상호배제 조건
2. 자원의 부분 할당 (Particial Allocation)
   • 이미 확보한 자원들을 소유한 채 대기, 보유와 대기 (Hold & Wait)
3. 자원의 선점 불가능성
   • 비선점 조건
4. 자원의 환형 대기 (Circular-Wait)
   • 사이클이 생긴다

• 자원의 배타적 사용 조건을 배제 (불가능)
• 자원의 부분 할당을 배제 (all at once) (all or none)
  • 필요한 모든 자원 미리 할당
  • 자원의 심각한 낭비
  • 무한대기 초래
• 자원의 선점 불가능을 배제
  • 비정상 종료 / 다시 시작
  • 자원의 낭비 & 무한 (다시 시작) 대기
• 자원의 환형 대기 상황을 배제 (linear ordering)
  • 순서를 지키기 위해 당장 필요 없는 자원 먼저 할당
  • 실제 필요한 순서X → ordering된 순서대로 자원 받는다

6.2 교착 상태의 해결

💡 예방(Prevention) 데드락 발생 X

• 자원의 배타적 사용 조건을 배제 (불가능)
• 자원의 부분 할당을 배제 (all at once) (all or none)
  • 필요한 모든 자원 미리 할당
  • 자원의 심각한 낭비
  • 무한대기 초래
• 자원의 선점 불가능을 배제
  • 비정상 종료 / 다시 시작
  • 자원의 낭비 & 무한 (다시 시작) 대기
• 자원의 환형 대기 상황을 배제 (linear ordering)
  • 순서를 지키기 위해 당장 필요 없는 자원 먼저 할당
  • 실제 필요한 순서X → ordering된 순서대로 자원 받는다

💡 회피(Avoidance) 데드락 발생X

• 안전 상태(safe state)
• Dijkstra의 은행가 알고리즘

•  

 

탐지와 복구는 보통 같이 사용

 

 💡 탐지(Detection) 데드락 발생O

• 자원 할당 그래프 (Resource Allocation Graph, RAG)
  • 방향성 이분 그래프
  • 활동 가능한 프로세스 = 싱크(sink)
  • 탐색 도중 싱크가 발견되면 교착상태가 없다.
  • 모든 가능 경로 탐색 후 싱크 없으면 교착상태다.
  • 노트(knot) 발견 = 교착상태 발견

 💡 복구(Recovery)데드락 발생O

• 프로세스의 종료 (Process Termination)
  • 종료 비용이 최소인 프로세스부터 종료한다.
    • 비교적 간단
    • 종료할때마다 데드락 제거되었는지 확인
  • 최소의 비용이 드는 부분집합에 속하는 프로세스들을 한꺼번에 종료
    • 최소 비용 고를 수 있음
    • 모든 부분집합에 대해 비용 계산 힘듦
• 자원 선점에 의한 방식
  • 필요한 자원을 가지고 있는 프로세스로부터 강제로 선점하여 교착상태 해결
  • 검사점(Checkpoint): 강제 종료 시 낭비 줄이기 위함