[혼자 공부하는 컴퓨터 구조 + 운영체제] 13강 교착 상태

교착 상태란

도로에 차가 꽉 막혀 꼼짝달싹 못하는 상황을 본 적이 있을 것이다. 프로세스 실행 과정에서도 비슷한 문제가 있다. 두 개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다린다면 그 어떤 프로세스도 진행할 수 없는 교착 상태가 된다. 교착상태가 정확히 무엇이고, 언제 어떻게 발생하는지 알아보자.

식사하는 철학자 문제

식사하는 철학자 문제(dining philosophers problem)는 교착 상태를 설명하기 위한 고전적인 시나리오이다.

동그란 원탁에 다섯 명의 철학자가 앉아있다. 철학자들의 앞엔 식사가 있고, 철할자들 사이에는 식사에 필요한 포크가 있다. 철학자들 앞에 있는 식사는 두 개의 포크로 먹을 수 있는 음식이라 가정해보자.

그리고 철학자들은 다음과 같은 순서로 식사를 한다.

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

이는 문제가 없어보인다. 실제로도 한 두 명의 철학자가 식사를 할 때는 아무런 문제가 없다. 하지만 모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황이 발생할 수 있다. 만약 모든 철학자가 왼쪽 포크를 집어들면 오른쪽 포크를 집어들 수 없기 때문이다.

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

식사하는 철학자 문제에서 철학자를 프로세스 혹은 스레드, 포크를 자원, 생각하는 행위를 자원을 기다리는 것에 빗대어 볼 수 있다. 포크는 한 번에 하나의 프로세스 혹은 스레드만 접근할 수 있으므로 임계 구역이라고 볼 수 있다.

교착 상태는 아주 다양한 상황에서 발생한다. 뮤텍스 락에서도 교착 상태는 발생할 수 있다.

// func1
lock1 = true;
while (lock2 == true) {}
// 임계 구역 작업
lock1 = false;

// func2
lock2 = true;
while (lock1 == true) {}
// 임계 구역 작업
lock2 = false;

위의 상황일 때 lock1과 lock2가 동시에 잠긴다면(true가 된다면), 프로세스가 멈추게 될 것이다.

이러한 교착 상태를 해결하기 위해서는 두 가지가 지켜져야한다.

1. 교착 상태가 발생했을 때의 상황을 매우 정확히 표현해본다.
2. 교착 상태가 일어나는 근본적인 이유에 대해 알아야 한다.

교착 상태가 발생했을 때의 상황을 한 눈에 보기 쉽게 그래프로 표현하는 방법을 알아보자

자원 할당 그래프

교착 상태는 자원 할당 그래프(resource-allocation graph)를 통해 단순하게 표현할 수 있다. 자원 할당 그래프는 어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 간단한 그래프이다.

자원 할당 그래프는 아래와 같은 규칙으로 그려진다.

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

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

같은 종류의 자원이라 할지라도 사용 가능한 자원의 개수는 여러개일 수 있기 때문에 점으로 표현한다. (3개의 프린터기 혹은 2개의 CPU가 있는 경우)

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

아래 그림은 ‘하드디스크 자원 하나는 프로세스 A에 할당되었고, CPU는 프로세스 B, C에 할당되었음’을 표현할 자원 할당 그래프이다. 프로세스가 자원 이용을 끝내고 운영체제에 자원을 반납하면 화살표는 삭제된다.

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

아래 그림은 ‘프로세스 D가 CPU의 할당을 기다리고 있음’을 나타낸 그래프이다.

이제 앞서 설명해본 식사하는 철학자 문제도 자원 할당 그래프로 표현해보자. 포크는 자원, 철학자는 프로세스와 같으며 모든 철학자가 왼쪽 포크를 든 채로 오른쪽 포크를 기다리고 있는 상황이므로 아래와 같이 표현할 수 있다.

위의 상황은 교착 상태가 발생한 모습을 자원 할당 그래프로 그린 것이다. 자원 할당 그래프가 원의 형태를 띠면 교착 상태가 발생할 수 있게 된다.

교착 상태 발생 조건

교착 상태가 발생할 조건에는 네 가지가 있다. 이 조건중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만, 모두 만족한다면 교착 상태가 발생할 가능성이 생긴다고 보면 된다.

• 상호 배제
  • 교착 상태의 근본적인 원인은 자원을 한 번에 하나의 프로세스만 이용 가능하기 때문이다. 만약 식사하는 철학자 문제에서 하나의 포크를 여러명이 동시에 사용할 수 있었다면 교착 상태는 발생하지 않았을 것이다. 즉, 상호배제 상황에서 교착 상태가 발생할 수 있다.
• 점유와 대기
  • 점유와 대기는 ‘자원을 할당받은 상태에서 다른 자원을 할당받기 기다리는 상태’를 의미한다. 식사하는 철학자 문제에선 ‘왼쪽 포크를 들고’ 다른 철학자의 포크를 기다렸기 때문에 교착 상태가 발생한 것이다.
• 비선점
  • 만약 철학자들 중 누군가가 다른 철학자의 포크를 강제로 빼앗을 수 있었다면 교착상태는 발생하지 않았을 것이다. 하지만 모든 철학자들은 그저 포크를 기다리기만 했다.
  • 교착 상태가 발생하게 된 또 다른 문제는 프로세스가 자원을 비선점하기 때문이다.
• 원형 대기
  • 프로세스들과 프로세스가 요청 및 할당받은 자원이 원의 형태를 이뤘기 때문이다. 다시 말해 자원 할당 그래프가 원의 형태로 그려지면 교착 상태가 발생할 수 있다. 이렇게 프로세스들이 원의 형태로 자원을 대기하는 것을 원형 대기라고 한다.
  • 자원 할당 그래프가 원형을 띈다고 해서 반드시 교착 상태가 발생하지는 않는다.

교착 상태 해결 방법

운영체제가 교착상태를 해결하는 방법으로는 크게 세 가지가 있다.

• 예방
  • 교착 상태가 일어나지 않도록 교착 상태 발생 조건에 부합하지 않게 자원을 분배하여 교착 상태를 예방한다.
• 회피
  • 교착 상태가 발생하지 않을 정도로 조금씩 자원을 할당하다가 교착 상태의 위험이 있다면 자원을 할당하지 않는 방식으로 교착 상태를 회피한다.
• 검출 후 회복
  • 교착 상태가 검출되면 교착 상태를 회복하는 방법을 취할 수도 있다.

교착 상태 예방

교착 상태 예방하는 방법은 교착 상태 발생 필요 조건 네 가지 중 하나를 충족하지 못하게 하는 방법이다.

• 상호 배제 없애기
  • 상호 배제를 없앤다는 말은 모든 자원을 공유 가능하게 만든다는 말과 같다. 다만 방식은 교착 상태를 없앨 수 있지만, 현실적으로 모든 자원의 상호 배제를 없애기는 어렵다.
• 점유와 대기를 없애자
  • 철학자 문제 속 철학자들이 한 손에 포크를 들고 다른 포크를 기다리지 못하게 금지하는 것과 같다. 포크를 동시에 들거나, 아니면 아예 들지 못하게 하는 것이다. 점유와 대기를 없애면 운영체제는 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다.
  • 이 방식은 이론적으로는 교착 상태를 해결할 수 있지만, 단점도 있다. 자원을 몰아주기 때문에, 자원이 필요해도 기다릴 수밖에 없으면서 활용성이 낮아진다. 게다가 점유와 대기를 금지하면 많은 자원을 사용하는 프로세스는 불리해진다. 동시에 사용할 타이밍을 확보하기가 어려워지기 때문이다. 이는 많은 자원을 필요로 하는 프로세스가 무한정 기다리게 되는 기아 현상을 야기할 우려가 있다.
• 비선점 조건 없애기
  • 비선점 조건을 없애면 이용중인 프로세스로부터 자원을 빼앗을 수 있다. 이 방식은 선점하여 사용할 수 있는 일부 자원(CPU)에 대해서는 효과적이다.
  • 하지만 모든 자원이 선점 가능한 것은 아니다. 한 프로세스의 작업이 끝날 때 까지 다른 프로세스가 기다려야 하는 자원도 있기 때문이다. 따라서 비선점 조건을 없애 모든 자원을 빼앗을 수 있도록 하여 교착 상태를 예방하는 방법은 다소 범용성이 떨어지는 방안이다.
• 원형 대기 조건 없애기
  • 원형 대기 조건을 없애는 방법은 간단하다. 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않는다.
  • 예를들어 철할자 문제에서 모든 포크에 1번부터 5번까지 번호를 붙이고, 철할자들로 하여금 번호가 낮은 포크부터 높은 포크 순으로 집어들게 한다면 원형 대기는 발생하지 않는다. 5번 포크를 집어들고 1번 포크를 집어들 수 없기 때문이다. 이는 마치 철학자들이 일렬로 앉아 식사하는 상황과 유사하다.

원형 대기를 없앰으로써 교착 상태를 예방하는 방식은 앞선 세 방식에 비하면 비교적 현실적이고 실용적이지만, 단점이 있다. 모든 컴퓨터 시스템 내에 존재한느 수많은 자원에 번호를 붙이는것은 간단하지 않으며, 자원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수 있다.

이렇듯 교착 상태의 발생 조건을 원천적으로 제거하여 교착 상태를 사전에 방지하는 예방 방식은 교착 상태가 발생하지 않음을 보장할 수는 있지만 여러 부작용이 따른다.

교착 상태 회피

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

프로세스에 할당할 수 있는 자원이 충분한 상태에서 프로세스가 적은 자원만을 요구한다면 교착 상태가 발생하지 않는다. 철학자 문제에서 포크가 100개, 1000개 있고 철학자가 한두 개의 포크를 요구한다면 교착 상태는 발생하지 않는다. 그렇기 때문에 프로세스들에 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분 하는것이 교착 상태 회피이다.

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

• 안전 상태 : 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
• 불안전 상태 : 교착 상태가 발생할 수도 있는 상황
• 안전 순서열 : 교착 상태 없이 프로세스들에 자원을 할당할 수 있는 순서

만약 웹 브라우저, 메모장, 게임이 동시에 자원을 요청한 상황에서 웹 브라우저 → 메모장 → 게임 순으로 자원을 할당하면 교착 상태가 발생하지 않는다면, 이 것이 안전 순서열이 된다.

안전상태는 안전 순서열대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태이며, 불안전 상태는 안전 순서열이 없는 상태이다. 시스템이 불안전 상태이면 교착 상태가 발생할 수 있는 위험이 있다.

이는 예시를 통해 이해하는것이 중요하다.

할당 가능한 자원이 12개가 있고, 3개의 프로세스가 있다. 프로세스는 각각 10개, 4개, 9개의 자원을 요구하고 있으며, 각각 5, 2, 2 만큼의 자원을 이미 사용중이다.

프로세스	요구량	현재 사용량
P1	10	5
P2	4	2
P3	9	2

• 할당 가능 자원 : 12
• 할당한 자원(P1, P2, P3 현재 사용량의 총합) : 9
• 남은 자원(할당 가능 자원 - 할당한 자원) : 3

이는 안전 상태이다. P2 → P1 → P3이라는 안전 순서열이 있기 때문이다.

P2를 먼저 처리 하면 2개의 자원을 넘겨주게되고, P2가 작업을 마치면 4개의 자원을 반환하면서 5개의 자원이 남는다. 그리고 P1를 처리하면 5개의 자원을 넘겨주게되고, P1이 작업을 마치면 5개의 자원을 반환하여 10개의 자원이 남는다. P3를 처리하기 위해 7개의 자원을 넘겨주고, P3가 작업을 마치면 9개의 자원을 반환하여 12개의 자원이 남게된다.

만약 P3에 자원을 하나 넘겨주게 된다면, 남은 자원이 2개가 되면서 안전 순서열이 사라지면서 불안전 상태가 된다. 즉, 교착 상태가 발생할 위험이 있다.

프로세스	요구량	현재 사용량
P1	10	5
P2	4	2
P3	9	3

운영체제가 교착 상태를 회피하기 위해서는 시스템 상태가 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하면 된다. 즉, 교착 상태 회피 방식은 항시 안전 상태를 유지하도록 자원을 할당하는 방식이라고 볼 수 있다.

교착 상태 검출 후 회복

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

• 선점을 통한 회복
  • 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식이다. 교착 상태가 해결될때까지 다른 프로세스로부터 자원을 강제로 빼앗는 방식이다.
• 프로세스 강제 종료를 통한 회복
  • 가장 단순하면서 확실한 방식이다. 교착 상태에 놓인 프로세스를 모두 강제 종료할 수도 있고, 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료할 수도 있다.
  • 전자는 한 방에 교착 상태를 해결할 수 있지만, 그만큼 프로세스들이 작업 내역을 잃을 가능성이 있고, 후자는 작업 내역을 잃는 프로세스를 최대한 줄일 수 있지만, 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드를 야기합니다.

실은 교착 상태를 아예 무시하는 방법도 있다. 드물게 발생하는 잠재적 문제를 무시로 대처하는 타조 알고리즘이라는 거창한 이름을 방식이다.

완벽을 추구하는 과학자나 수학자 입장에서는 납득할 수 없는 방식일지 모르나, 문제 발생의 빈도나 심각성에 따라 최대 효율을 추구하는 엔지니어 입장에서는 때때로 이 방식이 적합할 때도 많다.