교착상태(Deadlack)란?

교착상태(Deadlock)란 멀티프로세스나 멀티스레드 환경에서 발생할 수 있는 상황으로, 각 프로세스 또는 스레드가 서로가 가지고 있는 자원을 점유한 채로 다른 프로세스 또는 스레드가 필요로 하는 자원을 기다리는 상태를 말합니다. 이러한 상태에서는 모든 프로세스 또는 스레드가 무한히 기다리는 현상이 발생하며, 작업이 진행되지 않고 시스템이 정체되는 문제가 발생할 수 있습니다.

식사하는 철학자들 문제는 교착상태를 설명하는 대표적인 예시입니다.

다섯 명의 철학자가 하나의 원탁에 앉아 식사를 한다. 각각의 철학자들 사이에는 포크가 하나씩 있고, 앞에는 접시가 있다. 접시 안에 든 요리는 스파게티 같은 면 요리이기 때문에 식사를 하기 위해서는 동시에 두 개의 포크가 필요하다. 그리고 각각의 철학자는 다른 철학자에게 말을 할 수 없으며, 번갈아가며 각자 식사하거나 생각하는 것만 가능하다. 따라서 식사를 하기 위해서는 왼쪽과 오른쪽의 인접한 철학자가 모두 식사를 하지 않고 생각하고 있어야만 한다. 또한 식사를 마치고 나면, 왼손과 오른손에 든 포크를 다른 철학자가 쓸 수 있도록 내려놓아야 한다. 이 때, 어떤 철학자도 굶지 않고 식사할 수 있도록 하는 방법은 무엇인가?

철학자들이 다음의 과정을 통해 식사를 한다고 가정해 봅시다.

① 일정 시간 생각을 한다.
② 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
③ 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
④ 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
⑤ 오른쪽 포크를 내려놓는다.
⑥ 왼쪽 포크를 내려놓는다.
⑦ 다시 1번으로 돌아간다.

이 경우 모든 철학자가 왼쪽 포크를 들고 오른쪽 포크를 기다린다면 어떠한 경우에서도 식사를 할 수 없는 상태가 되는데, 이것이 교착상태 입니다.

자원 할당 그래프

교착상태를 파악하기 위해서는 자원 할당 그래프를 그려서 어떤 프로세스가 어떤 자원을 할당받아 사용 중인지 확인할 수 있습니다. 자원할당 그래프는 프로세스를 원으로, 자원을 사각형으로 표현합니다.

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

프로세스가 자원을 할당받았다면 자원에서 프로세스로 화살표를 그려 표시합니다.

프로세스가 자원을 할당받기 위해 기다린다면 프로세스에서 자원으로 화살표를 그려 표시합니다. 아래 그림은 프로세스4가 자원2를 할당받기 위해 대기상태인 경우입니다.

식사하는 철학자 문제를 자원할당 그래프로 나타내면 다음과 같이 나타낼 수 있습니다.

교착상태 발생 조건

교착상태가 발생하기 위해서는 다음의 네 가지 조건이 동시에 충족되어야 합니다.

1. 상호 배제(Mutual Exclusion): 자원은 한 번에 하나의 프로세스 또는 스레드만이 사용할 수 있어야 합니다.

2. 점유와 대기(Hold and Wait): 프로세스 또는 스레드가 이미 자원을 할당받았는데 추가적인 자원을 기다리는 상태여야 합니다.

3. 비선점(No Preemption): 다른 프로세스 또는 스레드가 점유하고 있는 자원을 강제로 빼앗을 수 없어야 합니다.

4. 원형 대기(Circular Wait): 프로세스 또는 스레드 간에 자원을 기다리는 원형 형태의 사슬이 형성되어야 합니다.

식사하는 철학자 문제에서 포크는 한 번에 한 철학자만 사용할 수 있으며, 각 철학자는 왼쪽 포크를 점유하면서 오른쪽 포크를 기다리고 있습니다. 또한 포크를 강제로 뺏을 수 없으며, 자원 할당 그래프에서 본 것과 같이 원형 형태로 자원을 대기하고 있으므로 교착 상태에 있다고 볼 수 있습니다.

교착상태 해결법

교착상태 예방(Deadlock Prevention)

교착상태 예방(Deadlock Prevention)은 교착상태가 발생되지 않도록 사전에 예방하는 방법입니다. 교착상태가 발생하는 조건 중 적어도 하나가 성립하지 않게 만들면 교착상태를 해결할 수 있습니다.

상호 배제 조건을 없애기 위해는 여러 프로세스가 공유자원을 사용할 수 있도록 하면 되지만, 동기화 문제가 발생할 수 있습니다. 또한 식사하는 철학자 문제의 경우와 같이 하나의 포크를 여러 철학자가 동시에 사용하는 것은 현실적으로 불가능 합니다.

점유와 대기 조건을 없애기 위해서는 프로세스 실행에 필요한 모든 자원을 한꺼번에 할당받거나 할당받지 않으면 됩니다. 예를 들어 식사하는 철학자 문제에서 오른쪽 포크와 왼쪽 포크를 한꺼번에 점유하도록 한다면 식사를 할 수 있습니다. 그러나 이것은 자원의 활용률을 낮출 수 있다는 단점이 있습니다. 어떤 철학자는 배가 많이 고파서 식사를 빨리 할 필요가 있지만 포크를 가지지 못하여 식사를 못할 수도 있고, 어떤 철학자는 오른손잡이라서 왼쪽 포크의 활용이 낮아 왼쪽 포크의 사용률이 낮아질 수 있습니다.

비선점 조건을 없애는 방법은 선점이 가능한 자원에 한해서는 효과적일지는 몰라도 모든 자원이 선점 가능한 것이 아니라는 단점이 있습니다. 한 철학자가 포크를 가지고 있으면 다른 철학자는 해당 포크를 점유할 수 없습니다.

원형 대기 조건을 없애기 위해서는 자원에 순서를 부여하고, 각 프로세스가 오름차순으로만 자원을 요청할 수 있도록 하면 됩니다. 예를 들어 아래 자원 할당 그래프와 같이 철학자1이 처음에 순서가 높은 포크5를 점유하지 못하게 하면 철학자5 → 철학자4 → 철학자3 → 철학자2 → 철학자1 순서로 식사를 할 수 있게 됩니다.

교착상태 회피(Deadlock Avoidance)

교착상태 회피(Deadlock Avoidance)는 교착상태를 무분별한 자원 할당으로 인해 발생했다고 간주하며 교착상태가 발생하는 조건인지 확인하면서 적절히 회피하는 방법입니다.

이 방법은 원형 대기가 발생하지 않도록 자원 할당 상태를 검사하면서 시스템이 안전 상태인지 확인합니다. 안전 상태는 교착상태가 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태를 말합니다.

예를 들어 자원이 12개이고 프로세스 P1, P2, P3가 각각 5개, 2개, 2개의 자원을 할당받았고, 각각 최대 10개, 4개, 9개의 자원을 요구한다고 가정합시다. 이 상태에서 운영체제가 할당할 수 있는 자원은 3개가 남습니다.

이때 P2에 2개의 자원을 할당하면 P2가 종료되고 자원을 반환하여 남은 자원은 5개가 됩니다(3 - 2 + 4 = 5). 그 후 P1에 5개의 자원을 할당하면 P1이 종료되고 자원을 반환하여 남은 자원은 10개가 되며(5 - 5 + 10 = 10), 마지막으로 P3에 7개의 자원을 할당하면 모든 프로세스가 자원을 할당받고 종료될 수 있습니다.

P2 → P1 → P3 순서로 프로세스에게 자원을 할당하면 안전 상태가 되는데, 이 순서를 안전 순서열이라고 합니다. 즉, 교착상태 회피는 안전 상태를 유지하도록 안전 순서열인지 검사하면서 자원을 할당합니다. 안전 순서열을 찾아내는 대표적인 알고리즘으로는 은행원 알고리즘(Banker's Algorithm)이 있습니다.

교착상태 탐지 및 회복(Deadlock Detection & Recovery)

교착상태 탐지 및 회복(Deadlock Detection & Recovery)은 교착상태의 발생을 인정하고 사후에 조치하는 방법입니다. 프로세스가 자원을 요구하면 우선 할당하며, 교착상태가 탐지되면 이를 회복하는 알고리즘을 사용합니다.

교착상태를 회복하는 방식에는 선점을 통한 회복과 프로세스의 강제 종료를 통한 회복이 있습니다.

선점을 통한 회복은 교착상태가 회복될 때까지 한 프로세스에게 자원을 몰아줍니다.

프로세스의 강제 종료를 통한 회복은 교착상태에 있는 모든 프로세스를 강제 종료하거나 교착상태가 해결될 때까지 한 프로세스씩 강제로 종료합니다. 전자의 경우 작업 내역을 한번에 잃어버릴 수 있는 위험이 있으며, 후자의 경우 오버헤드가 발생할 위험이 있습니다.

교착상태 무시((Deadlock Ignorance)

교착상태 무시((Deadlock Ignorance)는 교착상태를 무시하고 특별한 조치를 취하지 않는 방법입니다. 이를 타조 알고리즘이라고 하며, 교착상태의 발생 확률이 낮은 상황에서 효율적인 방법입니다. 유닉스(UNIX), 윈도우(Windows) 등 대부분의 운영체제는 이 방법을 사용합니다.