1. DeadLock

• 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태
• 무한히 다음 자원을 기다리는 상태
• 시스템적으로 한정된 자원을 여러 곳에서 사용할 때 발생

2. DeadLock 발생 조건

4가지 모두 성립해야 데드락 발생

• 상호 배제: 자원은 한번에 한 프로세스만 사용 가능
• 점유 대기: 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당 되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함
• 비선점: 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음
• 순환 대기: 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

3. DeadLock 처리 방법

3.1. 예방/회피 방법

3.1.1. 예방

교착 상태 방생 조건 중 하나를 제거하면서 해결(자원 낭비 심함)

• 상호 배제 부정: 여러 프로세스가 공유 자원 사용
• 점유 대기 부정: 프로세스 실행 전 모든 자원을 할당
• 비선점 부정: 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원을 반납
• 순환대기 부정: 자원에 고유번호 할당 후 순서대로 자원 요구

3.1.2. 회피

교착 상태 발생 시 피해나가는 방법

• 은행원 알고리즘
  • 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착상태 회피
  • 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기
• 자원 할당 그래프 알고리즘
  • 자원과 프로세스에 대해 요청 간선과 할당 간선을 적용하여 교착상태를 회피하는 알고리즘
  • 프로세스가 자원을 요구 시 요청 간선을 할당 간선으로 변경해 사이클을 확인
    • 사이클 생성: 자원에 하나의 인스턴스만 존재한다면 교착 상태로 여러 인스턴스가 존재한다면 교착 상태 가능성으로 판별함
    • 사이클을 생성하지 않음: 자원을 할당

3.2. 탐지/회복 방법

3.2.1. 탐지

• 자원 할당 그래프를 통해 교착상태를 탐지
• 자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드를 발생

3.2.2. 회복

교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법

• 프로세스 종료
  • 교착상태의 프로세스를 모두 중지
  • 교착 상태가 제거될 때까지 하나씩 프로세스 중지
• 자원 선점 방법
  • 교착상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당(들고 있던 프로세스는 일시정지)
  • 우선 순위가 낮은 프로세스나 수행 횟수가 적은 프로세스 위주로 프로세스 자원 선점