[CS 상식 - 운영체제] 교착 상태

---

01. 식사하는 철학자 문제 (Dining Philosophers Problem)

• 교착 상태를 설명하기 위한 고전적인 상황
• 교착상태의 상황의 발생 원인과 해결 방안을 설명하는 가상의 문제 시나리오
• 상황: 동그란 원탁에 다섯 명의 철학자와 식사, 포크가 존재
• 순서
  1. 계속 생각을 하다가 왼쪽 포크가 사용이 가능하면 집어듦
  2. 계속 생각을 하다가 오른쪽 포크가 사용이 가능하면 집어듦
  3. 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 진행
  4. 식사 시간이 끝나면 오른쪽 포크를 내려놓음
  5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓음
  6. 다시 1번부터 반복
• 문제 발생: 모든 철학자가 동시에 포크를 집어 식사를 하는 경우
  • 어떤 철학자도 식사를 할 수 없고 영원히 기다려야하는 상황 발생
  • 모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다려야함
• 교착 상태 (deadlock): 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상
• 운영체제로 빗대어 보기
  • 철학자: 프로세스 혹은 스레드
  • 포크: 자원, 임계 구역
  • 생각하는 행위: 자원을 기다리는 것
• 교착 상태의 해결 방법
  1. 교착 상태가 발생했을 때의 상황을 정확히 표현
  2. 교착 상태가 일어나는 근본적인 이유 파악

---

02. 자원 할당 그래프(reqource-allocation graph)

• 자원 할당 그래프: 어떤 프로세스가 어떤 자원을 사용하고 있고, 어떤 프로세스가 자원을 기다리고 있는지 표현하는 그래프
• 규칙
  1. 프로세스는 원, 자원의 종류는 사각형으로 표현
  2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
  3. 프로세스가 어떤 자원을 할당받아 사용 중일 경우, 자원 → 프로세스를 향해 화살표 표시
  4. 프로세스가 어떤 자원을 기다리는 상황이라면 프로세스 → 자원으로 화살표 표시
• 그래프가 원의 형태를 띄고 있다면 교착 상태 발생할 수도 았음

03. 교착 상태 발생 조건

• 발생 조건 4가지
  1. 상호 배제 (mutual exclusion): 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때
  2. 점유와 대기 (hold and wait): 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
  3. 비선점 (nonpreemptive): 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하기 때문
  4. 원형 대기 (circular wait): 프로세스들이 원의 형태로 자원을 대기하는 것
     • 원의 형태라고 반드시 교착상태가 발생하는 것이 아님

---