[OS] 교착 상태

1. 교착 상태

• 교착 상태 (deadlock) : 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상 ex) 식사하는 철학자 문제

자원 할당 그래프

• 교착 상태 표현 방법
• 어떤 프로세스가 어떤 자원 사용 중, 어떤 자원 기다리는 중 표현 그래프
  1. 프로세스는 원으로, 자원 종류는 사각형으로 표현
  2. 사원 가능 자원 갯수는 자원 사각현 내 점으로 표현
  3. 프로세스가 자원 할당 받아 사용중이면 자원 → 프로세스 화살표 표시
  4. 프로세스가 자원 기다리는 중이면 프로세스 → 자원 화살표 표시

교착 상태 발생 조건

1. 상호 배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때
2. 점유와 대기 : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
3. 비선점 : 다른 프로세스의 자원을 강제로 빼앗기 불가능
4. 원형 대기 : 프로세스들이 원의 형태로 자원 대기

   2. 교착 상태 해결 방법

교착 상태 예방

• 상호 배제 없애기 → 현실성 X
• 점유와 대기 없애기
  • 특정 프로세스에 자원 모두 할당 or 아예 할당 X
  • 자원 활용율 ↓, 기아 현상 야기 우려
• 비선점 조건 없애기
  • CPU 대해서 효과정
  • 범용성 ↓
• 원형 대기 조건 없애기
  • 모든 자원에 번호 붙이고, 오름차순으로 자원 할당
  • 현실적, 실용적
  • 번호 붙이기, 어떻게 붙일지 간단 X

    교착 상태 회피

• 교착 상태가 발생하지 않을 정도로만 자원 할당
• 안전 상태 (safe state) : 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원 할당 · 종료 가능 상태
  • 안전 순서열 (safe sequence) : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
• 불안전 상태 (unsafe state) : 교착 상태 발생 가능 상황
  • 안전 순서열 없는 상태

    교착 상태 검출 후 회복

• 상태 발생 인정 → 사후 조치

  선점 통한 회복

• 교착 상태 해결될 때까지 한 프로세스씩 자원 몰아주기

  프로세스 강제 종료

• 교착 상태 놓인 프로세스 모두 강제 종료
  • 해결 확실 / 작업 내역 잃어버릴 가능성
• 교착 상태 없어질 때까지 한 프로세스씩 강제 종료
  • 작업 내역 최대 보존 / 교착 상태 확인 과정 오버헤드

    타조 알고리즘 Ostrich Algorithm

• 교착 상태 무시하기