13. 교착상태

1. 교착 상태란?

1.1 식사하는 철학자 문제

"식사하는 철학자 문제(dining philosophers problem)" 는 교착 상태를 설명하기 위한 아주 고전적이고 재미있는 문제 상황이다.

자, 동그란 원탁에 다섯 명의 철학자가 앉아 있다. 이 철학자를 앞에는 맛있는 식사가 있고, 철학자들 사이 사이에는 식사에 필요한 포크가 있다. 그리고 철학자들 앞에 있는 식사는 두 개의 포크로 먹을 수 있는 음식이라 가정하다면, 모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황이 발생할 수 있다.

이렇게 일어나지 않을 사건을 기다리면 진행을 멈춰 버리는 현상을 "교착 상태(dead lock)" 이라고 한다.

이는 마치 게임 프로세스는 자원 A를 점유한 채 웹 브라우저 프로세스가 점유하고 있는 자원 B의 사용이 끝나길 기다리고, 웹 브라우저 프로세스는 자원 B를 점유한 채 게임 프로세스의 자원 A 사용이 끝나길 기다리는 상황과 같다. 이 경우 게임과 웹 브라우저 프로세스는 상대방이 가진 자원을 기다리기만 하다가 결국 실행 한번 못하는 상황이 벌어진다. 이를 교착 상태라고 한다.

교착 상태는 아주 다양한 상황에서 발생한다.

이러한 교착 상태를 해결하기 위해서는

1. 교착 상태가 발생했을 때의 상황을 정확히 표현하고, (자원 할당 그래프)

2. 교착 상태가 일어나는 근본적인 이유에 대해 알아야 한다. (교착 상태 발생 조건)

1.2 자원 할당 그래프

1.3 교착 상태 발생 조건

상호 배제

우선 교착 상태가 발생한 근본적인 원인은 해당 자원을 한 번에 하나의 프로세스만 이용 가능했기 때문이다. 조금 우스운 이야기이지만, 만일 식사하는 철학자 문제에서 하나의 포크를 여러 명이 동시에 사용할 수 있다면 교착 상태는 발생하지 않았다. 프로세스도 마찬가지로 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때, 즉 "상호 배제" 상황에서 교착 상태가 발생할 수 있다.

점유와 대기

식사하는 철학자 문제에서 누구도 식사를 이어갈 수 없었던 이유는 '왼쪽 포크를 들고' 다른 철학자의 포크를 기다렸기 때문이다. 다시 말해 자원을 보유한 채 다른 자원을 기다렸기 때문이다. 프로세스도 마찬가지로 어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있다. 이렇게 '자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태' 를 점유와 대기라고 한다.

비선점

교착상태가 발생하는 또 하나의 근본적인 이유는 프로세스가 자원을 비선점하고 있었기 때문이다. 비선점 자원은 그 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이용할 수 있다. 즉, 어떤 프로세스도 자원을 강제로 빼앗지 못했기 때문에 교착 상태가 발생했다고 볼 수 있다.

원형 대기

교착 상태가 발생한 마지막 이유는 프로세스들과 프로세스가 요청 및 할당받은 자원이 원의 형태를 이루었기 때문이다. 다시 말해 자원 할당 그래프가 원의 형태로 그려지만 교착상태가 발생할 수 있다.