교착 상태 (Deadlock) — 자원 할당 그래프와 네 가지 발생조건

이번 글에서는 교착 상태(Deadlock)가 무엇인지, 어떤 상황에서 발생하는지, 그리고 이를 표현하는 자원 할당 그래프(Resource Allocation Graph)와 교착 상태 발생 조건을 정리한다. 구체적인 해결 방법은 다음 글에서 다룬다.

 

---

교착 상태란?

교착 상태(Deadlock)란 두 개 이상의 프로세스 또는 스레드가 서로가 가진 자원을 기다리면서, 아무도 더 이상 실행을 진행할 수 없는 상태를 의미한다.

즉, 모두가 무언가를 기다리고 있지만 그 기다림이 끝날 수 없어서 시스템이 멈춰버리는 상황이다.

 

---

식사하는 철학자 문제

교착 상태를 설명할 때 가장 대표적으로 나오는 예시가 식사하는 철학자 문제(Dining Philosophers Problem)이다.

 

원탁에 다섯 명의 철학자가 앉아 있고, 철학자들 사이에는 포크가 하나씩 놓여 있다고 가정한다.

각 철학자는 식사를 하려면 왼쪽 포크와 오른쪽 포크, 총 두 개의 포크가 모두 필요하다.

그런데 모든 철학자가 동시에 왼쪽 포크만 먼저 집은 뒤, 오른쪽 포크를 기다린다면 어떻게 될까?

• 각 철학자는 포크 하나를 이미 점유하고 있다.
• 하지만 식사를 하려면 나머지 포크 하나가 더 필요하다.
• 그런데 그 포크는 옆 철학자가 이미 들고 있다.
• 결국 모든 철학자가 서로를 기다리게 된다.

즉, 모두가 왼쪽 포크를 든 채 오른쪽 포크를 기다리고 있는 상태가 된다.

이처럼 서로가 점유하고 있는 자원을 서로가 기다리며, 일어나지 않을 사건을 기다린 채 멈춰버리는 현상이 바로 교착 상태이다.

 

---

교착 상태를 왜 분석해야 할까?

교착 상태를 이해하려면 단순히 “멈췄다” 정도로 보는 것이 아니라, 누가 어떤 자원을 가지고 있고, 누구가 무엇을 기다리고 있는지를 정확히 표현할 수 있어야 한다.

 

교착 상태를 분석할 때 중요한 흐름은 다음과 같다.

1. 교착 상태가 발생한 상황을 정확히 표현한다.
2. 교착 상태가 발생하는 근본적인 원인을 파악한다.

이때 자주 사용하는 표현 방법이 자원 할당 그래프(Resource Allocation Graph)이다.

 

---

자원 할당 그래프란?

자원 할당 그래프는 프로세스와 자원의 관계를 그림으로 나타낸 것이다.

이를 통해 다음 내용을 확인할 수 있다.

• 어떤 프로세스가 어떤 자원을 할당받아 사용 중인지
• 어떤 프로세스가 어떤 자원을 기다리고 있는지
• 교착 상태가 발생할 가능성이 있는지

즉, 자원 할당 그래프는 교착 상태를 시각적으로 표현하고 분석하기 위한 도구라고 볼 수 있다.

 

자원 할당 그래프 그리는 방법

1. 프로세스는 원으로 표현한다.
2. 자원의 종류는 네모로 표현한다.
3. 사용할 수 있는 자원의 개수는 자원 사각형 안의 점으로 표현한다.
4. 프로세스가 어떤 자원을 할당받아 사용 중이라면, 자원 → 프로세스 방향으로 화살표를 그린다.
5. 프로세스가 어떤 자원을 기다리고 있다면, 프로세스 → 자원 방향으로 화살표를 그린다.

 

식사하는 철학자 문제를 자원 할당 그래프로 보면

식사하는 철학자 문제를 자원 할당 그래프로 표현하면, 각 철학자는 프로세스가 되고 각 포크는 자원이 된다.

교착 상태가 발생한 상황에서는 자원 할당 그래프가 원(cycle) 형태를 띠게 된다.

 

다만 자원 개수가 여러 개인 경우, 단순히 원형이 있다고 해서 교착 상태라고 단정할 수는 없다.

---

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

운영체제에서는 교착 상태가 발생하기 위해 필요한 조건을 보통 네 가지로 설명한다.

 

중요한 점은 다음과 같다.

• 네 가지 조건 중 하나라도 만족하지 않으면 교착 상태는 발생하지 않는다.
• 반대로 네 가지 조건을 모두 만족하면 교착 상태가 발생할 수 있다.

 

[1] 상호 배제 (Mutual Exclusion)

한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태이다.

예를 들어 프린터, 포크, 특정 파일 접근 권한처럼 한 번에 하나만 사용할 수 있는 자원이 이에 해당한다.

 

[2] 점유와 대기 (Hold and Wait)

프로세스가 이미 어떤 자원을 할당받아 점유한 상태에서, 다른 자원을 추가로 기다리는 상태이다.

예를 들어 철학자가 왼쪽 포크를 들고 있으면서 오른쪽 포크를 기다리는 상황이 여기에 해당한다.

 

[3] 비선점 (Nonpreemptive)

한 프로세스가 가진 자원을 다른 프로세스가 강제로 빼앗을 수 없는 상태이다.

즉, 자원은 사용 중인 프로세스가 스스로 반납해야만 다른 프로세스가 사용할 수 있다.

 

[4] 원형 대기 (Circular Wait)

프로세스들이 원의 형태로 서로가 가진 자원을 기다리는 상태이다.