📑 본 글은 <혼공컴운>을 읽고 정리한 글입니다.

1. 교착 상태란

1-1. 식사하는 철학자 문제

식사하는 철학자 문제(dining philosophers problem) : 교착 상태를 설명하는 고전 문제

동그란 원탁 / 5명의 철학자 / 식사 5개, 포크 5개

왼쪽 포크 들기 → 오른쪽 포크 들기 → 밥 먹기 → 다 먹으면 오른쪽 포크 내려놓기 → 왼쪽 내려놓기

모든 철학자가 왼쪽 포크를 든다면?

교착 상태

• 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상
• 상대방이 가진 자원을 서로 기다리다가 결국 실행을 하지 못하는 상황

1-2. 자원 할당 그래프

교착 상태를 표현하는 그래프

→ 사이클이 있으면 교착 상태가 발생할 수 있다.

1-3. 교착 상태 발생 조건

상호 배제(mutual exclusion)

점유와 대기(hold and wait) : 자원을 할당받은 상태에서 다른 걸 기다림

비선점(non-preemtive) : 자원을 강제로 뺏을 수 없음

원형 대기(circular wait) : 자원 할당 그래프가 원의 형태

2. 교착 상태 해결 방법

2-1. 교착 상태 예방

교착 상태 발생 조건 4가지 중 하나라도 만족하지 못하게 만들기

• 상호 배제
  • 모든 자원을 공유 가능하게? 말이 안 된다.
• 점유와 대기
  • 포크를 둘 다 들거나 아예 못 들거나
  • 자원의 활용률이 낮아진다. & 기아 현상 우려
• 비선점
  • 뺏기 가능하게
  • CPU에는 효과적 ← 선점할 수 있는 자원
  • 프린터 같은 애들은 그럴 수 없다.
• 원형 대기
  • 사이클 없애기
  • 모든 자원에 번호를 붙이고, 오름차순으로 자원 할당
  • 수많은 자원에 번호 붙일 수 있을까??

⇒ 교착 상태를 예방하는 방식은 부작용이 심하다.

2-2. 교착 상태 회피

교착 상태가 발생하지 않을 정도로만 조심히 자원을 할당한다.

• 안전 상태
  • 안전 순서열대로 프로세스에 자원을 배분하여 교착 상태가 발생하지 않는 상태
• 불안전 상태
  • 안전 순서열이 없는 상황, 교착 상태 발생 가능
• 안전 순서열
  • 교착 상태 없이 프로세스에 자원을 할당할 수 있는 순서

프로세스 | 최대 요구량 | 현재 사용량

머 이런 표로 해서 자원 할당하는 부분

항시 안전 상태를 유지하도록 자원을 할당하는 방식
⇒ 비효율적임 어차피 별로 안 난다 교착상태는

2-3. 교착 상태 검출 후 회복

교착 상태 발생을 인정하고 사후에 조치하는 방식

자원 요구하면 요구하는 대로 다 준다.

교착 상태 발생 여부를 주기적으로 검사한다.

검출되면 그 때 대처한다.

선점을 통한 회복

• 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아준다.

프로세스 강제 종료를 통한 회복

• 모두 강제 종료하거나 하나씩 강제 종료한다.

🦃🦃 타조 알고리즘(ostrich algorithm) 🦃🦃← 운체 pick!

• 드물게 발생하는 잠재적 문제를 무시로 대처한다.