교착상태 (Deadlocks)

정의

둘 이상의 프로세스나 스레드가 자원을 점유한 상태에서 서로 다른 프로세스나 스레드가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상

발생 조건

• 상호 배제(Mutual Exclusion) : 한번에 하나의 프로세스나 스레드만이 자원에 접근할 수 있음
• 비선점(No Preemption) : 다른 프로세스나 스레드의 자원을 뺏을 수 없음
• 점유와 대기(Hold and Wait) : 자원을 가진 상태에서 다른 자원을 기다림
• 순환 대기(Circular Wait) : 순환 형태로 자원을 대기

위의 4가지 조건이 모두 성립되는 경우에만 교착상태가 발생할 가능성이 있으며 4가지 조건 중 하나라도 성립하지 않는다면 교착상태가 발생하지 않는다.

---

자원

자원의 사용

요청(Request) -> 사용(Use) -> 반납(Release)

자원 할당도 (Resource Allocation Graph)

• 어떤 자원이 어떤 프로세스에게 할당되었는가?
• 어떤 프로세스가 어떤 자원을 할당 받으려고 기다리고 있는가?
• 자원 : 사각형 / 프로세스 : 원 / 할당 : 화살표

---

교착상태 처리

🐾 교착상태 방지 (Deadlock Prevention)

교착상태의 4가지 필요조건 중 한 가지 이상 불만족하도록 한다.

• 상호 배제(Mutual Exclusion)
  - 자원을 공유 가능하게
• 비선점(No Preemption)
  - 자원을 가지고 있으면서 다른 자원을 기다리지 않게
  - 단점 : 자원 활용률 저하, 기아(Starvation)
• 점유와 대기(Hold and Wait)
  - 자원을 선점 가능하게
• 순환 대기(Circular Wait)
  - ex) 자원에 번호 부여 후 오름차순으로 자원 요청
  - 단점 : 자원 활용률 저하

🐾 교착상태 회피 (Deadlock Avoidance)

교착상태가 발생하지 않도록 한다. (ex. 안전한 할당)

• 은행원 알고리즘 : 어떤 자원을 할당하기 전에 할당 후에도 안정 상태로 있을 수 있는지 검사 후 할당
• 은행원 알고리즘의 한계
  - 할당할 수 있는 자원수가 일정 해야함
  - 항상 불안전 상태를 방지해야 하므로 자원 이용도가 낮다
  - 최대 자원 요구량을 미리 알아야 한다.
  - 프로세스들은 유한한 시간 안에 자원을 반납해야 한다.

🐾 교착상태 검출 및 복구 (Deadlock Detection & Recovery)

• 교착상태가 일어나는 것을 허용
• 주기적 검사
• 교착상태 발생 시 복구

검출

• 검사에 따른 추가 부담 (Overhead) : 계산, 메모리

복구

프로세스 종료 방법

• 교착 상태의 프로세스를 모두 중지
• 교착 상태가 제거될 때까지 하나씩 프로세스 중지

자원 선점 방법

• 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당 (해당 프로세스 일시정지 시킴)
• 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점

🐾 교착상태 무시 (Don't Care)