교착 상태(Dead Lock) - Philosopher's Dining Problem, 교착 상태 발생 조건 4 가지

도심 속 교통 마비, 실제로 교착이 일어나면 교통 경찰이 오거나 해서 복구되는데 굉장히 오래 걸림

프로세스 실행을 위해서는 자원이 필요한데,

두 개 이상의 프로세스가 각각의 자원을 그저 기다리기만 한다면

어떤 프로세스도 실행되지 못하고 꽉 막혀 멈춰버리는 현상이 발생할 것.

 

---

교착 상태란? 

식사하는 철학자 문제 (Dining Philosopher's Problem)

 

왜 발생하고 어떻게 해결하는지 힌트를 주는 문제.

위 처럼 앉아있을 때 음식을 먹으려면 꼭 두 포크를 사용해야한다.

 

모든 철학자가 모두 동시에 이 프로세스를 진행하게 되면,

그 누구도 식사를 할 수 없다. 계속 생각만 하게 될 것.

 

모두 왼쪽 포크를 들게 되면 놓을 때 까지 오른쪽 포크를 사용할 수 없으니

계속 생각만 하게 될 것.

 

일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상.

• 철학자 = 프로세스, 스레드
• 포크 = 실행에 꼭 필요한 자원
• 식사하는 것 = 실행하는 것

---

컴퓨터 상황으로 예시를 들어보자면

서로가 가진 자원이 할당 해제될 때 까지 무작정 기다려야 한다

---

교착 상태를 해결하기 위해서는?

• 교착 상태가 발생했을 때의 상황을 정확히 표현해보기
• 교착 상태가 일어나는 근본적인 이유 이해하기

---

자원할당 그래프

 

교착 상태가 발생했을 때 상황을 표현하는 그래프

교착 상태 발생 조건 파악 가능

• 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능
• 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능

 

자원 할당 그래프 그리는 법

• 1. 프로세스는 원으로 자원의 종류는 사각형으로 표현
• 2. 사용할 수 있는 자원의 개수는 자원 사각형 내 점으로 표현
• 3. 프로세스가 어떤 자원을 할당 받아 사용중이라면 자원에서 프로세스를 향해 화살표를 표시
• 4.프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시

 

교착 상태가 일어난 그래프의 특징?

자원 할당 그래프가 원의 형태를 띄고 있다!

---

교착 상태가 발생하는 조건 4가지

• 상호 배제 (Mutual Exclusion)
  • 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
• 점유와 대기 (Hold and Wait)
  • 자원을 할당받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
    • 게임과 웹브라우저 예시
    • 왼쪽 포크를 든 채 오른쪽 포크를 기다린 것
• 비선점 (NonPreemtion)
  • 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
    • 철학자가 만약 포크를 뺏었다면 문제는 발생하지 않았을 것
• 원형 대기 (Circular Wait)
  • 프로세스들이 원의 형태로 자원을 대기하는 상태

4가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않고,

위 4가지 조건을 모두 만족하면 교착 상태가 발생할 수 있다.