[운영체제] 교착 상태 (DeadLock)

교착 상태란

프로세스를 실행하기 위해서는 자원이 필요합니다. 만약 두 개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다린다면 그 어떤 프로세스도 더이상 진행할 수 없는 교착 상태가 됩니다.

 

식사하는 철학자 문제

 

식사하는 철학자 문제는 교착 상태를 설명하기 위한 아주 고전적이고 재미있는 문제 상황입니다. 먼저 위 그림과 같이 상황을 가정하고, 아래와 같은 순서로 식사를 진행한다고 했을 때 이 철학자들은 식사를 무사히 마칠 수 있을 지에 대한 문제입니다.

1. 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
2. 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
3. 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다.
4. 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
6. 다시 1. 번부터 반복한다.

이 내용만 보면 아무런 문제가 없어 보이지만 만약 모든 철학자가 동시에 왼쪽 포크를 집어들면 모두가 오른쪽 포크를 집어 들 수 없기 때문에 모든 철학자가 다른 철학자가 포크를 내려놓을 때까지 기다리는 교착 상태가 발생하게 됩니다.

 

프로세스 혹은 스레드를 철학자, 자원은 포크, 자원을 기다리는 것은 생각하는 행위라고 하고 포크는 하나의 프로세스 혹은 스레드만 접근할 수 있으니 임계 구역이라고 볼 수 있습니다.

---

자원 할당 그래프

교착 상태는 자원 할당 그래프를 통해 단순하게 표현할 수 있습니다. 그리고 아래와 같은 규칙을 따라 나타낼 수 있습니다.

 

첫째, 프로세스는 원으로 자원의 종류는 사각형으로 표현합니다.

둘째, 사용할 수 있는 자원의 개수는 사각형 내에 점으로 표현합니다.

셋째, 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시합니다.

넷째, 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시합니다.

 

이를 바탕으로 식사하는 철학자 문제를 나타내면 아래와 같은 그림을 그릴 수 있습니다.

 

그리고 이것을 통해 우리는 교착 상태가 일어난 그래프의 특징이 원의 형태를 띄고 있다는 것을 알 수 있습니다.

---

교착 상태 발생 조건

상호 배제

만일 식사하는 철학자 문제에서 하나의 포크를 여러 명이 동시에 사용할 수 있었다면 교착 상태는 발생하지 않았을 것입니다. 프로세스도 마찬가지로 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때, 즉 상호 배제 상황에서 교착 상태가 발생할 수 있습니다.

 

점유와 대기

식사하는 철학자 문제에서 자원을 보유한 채 다른 자원을 '기다렸기 때문'에 문제가 발생했습니다. 이렇게 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태를 점유와 대기라고 합니다. 

 

비선점

앞서 비선점이란 프로세스가 끝나야만 다음 프로세스가 자원을 이용할 수 있는 것을 말했습니다. 즉, 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못했기 때문에 교착 상태가 발생했다고 볼 수 있습니다.

 

원형 대기

교착 상태가 발생한 마지막 이유는 프로세스들과 프로세스가 요청 및 할당받은 자원이 원의 형태를 이루었기 때문입니다. 그리고 프로세스들이 원의 형태로 자원을 대기하는 것을 원형 대기라고 합니다.

---

교착 상태 해결 방법

운영체제가 교착 상태를 해결하는 방법으로 예방, 회피, 검출, 회복이 있습니다.

 

교착 상태 예방

교착 상태를 예방하는 방법으로는 앞서 얘기한 교착 상태 발생 조건인 상호 배제, 점유와 대기, 비선점, 원형 대기 중 하나를 충족하지 못하게 하는 것입니다.

---

교착 상태 회피

교착 상태 회피는 교착 상태가 발생하지 않을 정도로만 조심 조심 자원을 할당하는 방식입니다. 즉, 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주합니다.

 

우선 교착 상태를 회피하는 방법을 학습하기 위해서는 안전 상태와 불안전 상태, 그리고 안전 순서열이라는 용어를 알아야합니다.

 

안전 상태

교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당 받고 종료될 수 있는 상태를 안전 상태라고 부릅니다.

 

불안전 상태

교착 상태가 발생할 수도 있는 상황을 불안전 상태라고 부릅니다.

 

안전 순서열

안전 순서열은 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미합니다.

---

교착 상태 검출 후 회복

검출 후 회복 방식에서 운영체제는 프로세스들이 자원을 요구할 때마다 그때그때 모두 할당하며, 교착 상태 발생 여부를 주기적으로 검사합니다. 그리고 교착 상태가 검출되면 그때 비로소 다음과 같은 방식으로 회복합니다.

 

선점을 통한 회복

선점을 통한 회복은 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식입니다. 즉, 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당하는 방식입니다.

 

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

프로세스 강제 종료를 통한 회복은 가장 단순하면서 확실한 방식입니다. 교착 상태에 놓인 프로세스를 모두 강제 종료할 수도 있고 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료할 수 있습니다. 전자는 작업 내역을 잃게 될 가능성이 있고 후자는 교착 상태 확인 과정에서 오버헤드를 야기합니다.

 

교착 상태 무시

드물게 발생하는 잠재적 문제를 무시로 대처하는 방식으로 타조 알고리즘이라고도 불립니다. 납득할 수 없는 방식일지 모르나, 문제 발생의 빈도나 심각성에 따라 때때로 적합할 때도 있습니다.