[OS] 교착상태 (Deadlock)

교착상태(Deadlock)란?

정상적인 시스템에서 프로세스는 요청 → 사용 → 방출 순서로 자원을 사용한다.

• 요청: 프로세스는 자원을 요청한다. 요청이 즉시 처리되지 않는 경우(ex. 다른 프로세스가 해당 자원을 사용 중인 경우) 프로세스는 자원을 얻을 때까지 대기해야 한다.
• 사용: 자원에 대한 작업을 실행한다.
• 방출: 자원을 방출한다.

자원의 요청과 방출은 시스템 콜이다. 예시로는 디바이스의 request()와 release(), 파일의 open() 과 close(), 메모리의 allocate()와 free() 등이 있다.

OS가 관리하지 않는 자원의 요청과 방출은 세마포어에 대한 wait() & signal() 또는 뮤텍스 락의 획득과 방출을 통해서 이루어질 수 있다.

커널이 관리하는 자원을 프로세스가 사용할 때는 시스템 테이블이 어떤 프로세스가 어떤 자원을 사용 중이고, 대기 중인지 등 모든 사항을 기록한다.

만약 아래와 같이 임의의 프로세스 P1과 P2가 각각 자원 A, B를 점유한 채로 B, A를 사용하기 위해 대기 중이라면

이때 두 프로세스는 교착 상태에 있다고 말한다. P1은 자원 B에 대한 요청이 처리될 때까지 A를 점유하고 있고, P2는 자원 A에 대한 요청이 처리될 때까지 B를 점유하고 있다. 결국 두 프로세스는 옴짝달싹 못한 채로 무한히 대기하게 된다.

교착상태의 필요 조건

교착 상태는 다음 네 가지 조건이 모두 만족할 때, 발생할 가능성이 있다. 주의할 점은 네 가지 조건을 모두 만족할 때 반드시 일어나는 것이 아니라 발생할 가능성이 생기는 것이다.

1. 상호 배제(mutual exclusion): 최소 하나의 자원이 한 프로세스에 의해 상호 배제 상태로 점유되어야 한다.
2. 점유하며 대기(hold-and-wait): 프로세스는 최소 하나의 자원을 점유한 채로 다른 프로세스가 점유 중인 자원을 대기해야 한다.
3. 비선점(no preemption): 자원들을 선점할 수 없다. 즉 다른 프로세스가 점유 중인 자원을 강제로 뺏을 수 없고, 해당 프로세스가 자원을 자발적으로 방출할 때까지 기다리는 상태여야 한다.
4. 순환 대기(circular wait): 대기 중인 프로세스, 점유 당하고 있는 자원의 관계가 원형을 이루어야한다. 아래 그림 참조

이때, 자원에서 프로세스로 향하는 간선(R → P)은 P가 R을 점유 중이라는 뜻이고 프로세스에서 자원으로 향하는 간선(P → R)은 P가 R을 대기 중이라는 뜻이다. 프로세스는 동그라미, 자원은 네모로 나타낸다.

이렇게 자원과 프로세스의 관계를 그래프로 나타내는 것을 자원 할당 그래프(Resource Allocation Graph)라고 한다.

교착상태 처리 방법

교착상태를 처리하는 데는 네 가지 방법이 있다.

1. 예방(Prevention)
2. 회피(Avoidance)
3. 검출 및 복구(Detection & Recovery)
4. 무시(Ignorance)

UNIX와 Windows를 포함한 대부분의 운영체제가 네 번째 방법을 사용한다. 교착상태 무시란 말 그대로 교착상태에 대해 아무런 대응도 하지 않는 것이다. 교착상태는 자주 일어나지는 않는데다가 예방 및 처리에 비용이 많이 들기 때문에 이 방법은 꽤나 경제적일 수 있다 (만약 교착상태가 일어났다면 해당 프로세스를 강제 종료 후 재시작하면 된다^^).

사실 우리가 사용하는 운영체제(매우 정교하게 작성된!)의 커널 레벨에서 교착상태가 일어날 일은 거의 없다. 보통 교착상태는 잘못 작성된 멀티스레드 어플리케이션에서 일어나는데, 이때 교착상태에 대한 책임은 응용 프로그램 개발자에게 있다.

그런데 교착상태를 무시해서는 안되는 경우가 있다. 예를 들어 우주 항공 산업에 쓰이는 시스템의 경우, 데드락이 한번이라도 일어나면 대참사가 일어날 수 있기 때문에 무시하고 넘어갈 수가 없다.

교착상태 예방

교착상태 예방은 앞서 살펴본 교착상태 필요조건 네 가지 중 적어도 하나가 성립하지 않도록 보장하는 일련의 방법들이다.

Mutual Exclusion

자원에 대한 상호 배제를 인정하지 않음으로써 교착 상태를 예방하는 것이다. 읽기 전용 파일 등의 자원은 공유가 가능하기 때문에 교착 상태가 일어날 수가 없다. 근데 애초에 공유가 불가능한 자원이 존재할 수 있기 때문에 이 방법만으로 모든 교착상태를 예방하는 것은 불가능하다.

Hold-and-Wait

프로세스가 자원을 요청하려면 다른 자원들을 가지고 있지 않다는 것을 보장함으로써 교착상태를 예방한다. 두 가지 프로토콜이 가능한데, 첫 번째 방법은 프로세스가 실행되기 전에 반드시 모든 자원을 요청하여 할당받게 하는 것이고, 두 번째는 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 강제하는 것이다.

두 번째 방법은 쉽게 이해가 가는데, 첫 번째 방법은 잘 이해가 가지 않을 수 있다. 예를 들어 설명하면 다음과 같다.

DVD 드라이브로부터 디스크 파일로 자료를 복사하여 디스크 파일을 정렬하고, 그 후에 프린터에 결과를 인쇄하는 프로세스가 있다고 생각해보자.

첫 번째 방식은, 프로세스가 시작할 때 DVD 드라이브, 디스크 파일, 프린터에 요청을 모두 보내는 것이다. 비록 DVD 드라이브 → 디스크 파일 → 프린터 순으로 작업을 수행하지만 미리 요청을 해놓음으로써 다른 프로세스들이 점유하지 못하도록 하는 것이다. 반면 두 번째 방식은 DVD 드라이브를 사용하고나면 드라이브 자원을 모두 방출한 뒤 디스크 파일에 대한 요청을 하는 것이다.

이 방식의 단점은 자원 활용률이 저하되고 기아 상태가 발생할 수 있다는 점 등이 있다.

No Preemption

자원을 선점 가능하게 한다. 즉 어떤 프로세스가 하나의 자원을 점유하고 있는 상태에서 즉시 할당할 수 없는 다른 자원(무조건 대기해야하는 자원)에 대해 요청을 하면, 현재 점유 중인 자원이 선점되게 하는 것이다. 이 역시 불가능한 상황이 존재한다. 예를 들어 프린터의 경우, 선점 당하면 하나의 페이지에 여러 프로세스의 작업이 프린트 될 수 있으므로 선점 당할 수 없는 자원에 해당한다.

Circular Wait

환형 대기 조건은 자원에 순서를 매기고 그 순서대로 접근하도록 강제함으로써 차단할 수 있다.

예를 들어 뮤텍스 두 개에 대해 다음과 같이 고유의 정수 번호를 부여한다.

first_mutex = 1
second_mutex = 5

second_mutex에 대한 요청은 반드시 first_mutex를 획득한 뒤 이루어져야한다. 이렇게 설정하면 아래와 같이 교착상태가 발생할 수 있는 코드 작성이 불가능해진다.

/* thread_one runs in this function */
void *do_work_one(void *param)
{
    pthread_mutex_lock(&first_mutex);
    pthread_mutex_lock(&second_mutex);
    /*
    Do some work
    */
    pthread_mutex_unlock(&second_mutex);
    pthread_mutex_unlock(&first_mutex);
}

/* thread_two runs in this function */
void *do_work_two(void *param)
{
    pthread_mutex_lock(&second_mutex);
    pthread_mutex_lock(&first_mutex);
    /*
    Do some work
    */
    pthread_mutex_unlock(&first_mutex);
    pthread_mutex_unlock(&second_mutex);
}

교착상태 회피

교착상태 회피는 자원이 어떻게 요청될지에 대한 정보를 미리 파악하고 회피 알고리즘을 통해 교착 상태가 일어나지 않도록 자원을 할당하는 방식이다. 교착상태 예방은 교착상태가 발생할 수 있는 조건을 원천 차단하는 것이고, 교착상태 회피는 조건을 차단하는 것이 아니라, 정보를 미리 파악하고 교착상태가 일어나지 않는 방향으로 자원을 할당하는 것이다.

이는 교착상태 예방 방식에서 일어날 수 있는 이용률 저하와 처리율 감소를 피할 수 있다는 장점이 있다(회피 방식에 이용률 저하가 없다는 것은 아니다, 모든 방식은 각기 장단점이 있으며 상황에 맞는 최적의 방식을 구현해야한다).

교착상태 회피 알고리즘에서는 각 프로세스가 자신이 필요한 자원의 최대치를 선언하도록 요구한다(단일 프로세스 기준). 이 값을 바탕으로 OS는 현재 요청이 들어온 프로세스에게 자원을 할당해야 할지, 대기시켜야 할지를 결정한다.

안정 상태 vs 불안정 상태

안정 상태는 안정 순서를 찾을 수 있는 경우이다. 안정 순서란 프로세스들이 요청한 모든 자원들을 교착 상태 발생 없이 할당할 수 있는 순서를 말한다. 즉 다시 말하면 안정 상태란 프로세스가 순서만 잘 조정해주면 교착 상태가 일어나지 않는 상태를 말한다.

불안정 상태는 반대로 안정 순서를 찾을 수 없는 경우이다. 불안정 상태라고해서 무조건 교착 상태가 발생하는 것은 아니며, 교착 상태가 발생할 수 있는 가능성을 내포하고 있는 상태이다. 예시를 통해 확인해보자.

할당 가능한 자원의 수: 12개

Process	Max needs	Current needs
P0	10	5
P1	4	2
P2	9	2

P0,P1,P2가 요구하는 자원의 최대치는 각각 10, 4, 9개이고 현재 필요한 자원은 5, 2, 2개이다.이때의 안정 순서는

P0 > P1 > P2 > P1 > P2 > P0 > P2 가 된다.

순서대로 살펴보면, 우선 P0에게 5개, P1에 2개, P2에 2개를 할당한다. 7개를 할당했으므로 남는 자원은 3개가 된다. 여기서 P1에게 2개를 더 할당한다. P1은 필요한 자원의 최대치를 다 받았으므로 작업을 마치고 4개의 자원을 반환한다. 따라서 남는 자원은 다시 5개가 된다. 이 자원을 이제 P0에게 할당한다. P1도 필요한 자원의 최대치를 다 받으므로 작업을 마치고 10개의 자원을 반환한다. 나머지 자원을 P2에게 할당하면 모든 프로세스가 교착 상태 없이 작업을 마칠 수 있다.

다른 조건은 모두 같은 상황에서 P2가 현재 필요한 자원만 3개로 바꿔보자.

Process	Max needs	Current needs
P0	10	5
P1	4	2
P2	9	3

이때, P0, P1, P2에게 각각 현재 필요한 자원을 할당하고나면 2개의 자원이 남는다. 여기서 P1에게 나머지 자원을 할당한다. P1이 작업을 마친 후 4개의 자원을 반환하면 4개의 자원이 남는다. 그런데 P0와 P2가 작업을 마치기 위해서 필요한 자원은 각각 5개, 6개이므로 남는 자원을 어느쪽으로 할당하든 작업을 마칠 수 없다. 어느 한 쪽이 자원을 선점하지 않는 한 두 개의 프로세스는 각기 자원을 점유한 채로 무한히 대기하게 되므로 교착 상태가 발생한다. 즉 처음 세 개의 프로세스에게 5, 2, 3개의 자원을 할당하는 순간 불안정 상태가 된다.

자원 할당 그래프 알고리즘

교착상태 회피 알고리즘은 두 가지로 나누어서 생각해볼 수 있다. 각 자원의 유형마다 하나의 인스턴스를 갖는 경우, 자원 할당 그래프 알고리즘으로 교착상태를 회피할 수 있다. 각 자원의 유형마다 다수의 인스턴스를 갖는 경우에는 자원 할당 그래프로 해결하기 어렵기 때문에 은행원 알고리즘을 이용한다.

자원 할당 그래프 알고리즘은 앞서 잠깐 살펴본 자원 할당 그래프를 이용해 교착 상태를 회피하는 것이다.

방법은 다음과 같다.

1. 자원 할당 그래프에 예약 간선(claim edge)이라는 새로운 타입의 간선을 도입한다. 예약 간선은 점선으로 나타내며 P1 ⇢ R1 은 프로세스 P1이 미래에 R1을 요청할 것이라는 것을 의미한다.
2. P1이 R1을 요청하면 예약 간선을 요청 간선으로 바꾼다.(P1 ➞ R1)
3. R1이 P1에 할당되면 요청 간선을 할당 간선으로 바꾼다.(R1 ➞ P1)
4. P1이 R1을 방출하면 할당 간선을 다시 예약 간선으로 바꾼다.
5. 요청 간선을 할당 간선으로 바꿔도 사이클이 생기지 않을 때만 자원을 할당한다.

조금 복잡해보이지만 직접 그림을 그려가며 천천히 생각해보면 어렵지 않다.

만약 P1이 R1을 점유하고 있고 P2가 R1을 요청하고 있는 상태에서, P1과 P2 모두 미래에 R2를 요청할 계획이라고 해보자. 이때 상황을 자원 할당 그래프로 나타내면 다음과 같다.

이때 P2에 R2를 할당하면 그래프에 아래처럼 사이클이 형성된다.

사이클이 생긴다는 건, 불안정 상태라는 뜻이므로 P2에 R2를 할당해서는 안된다. 대신 P1에 할당하면 사이클이 생기지 않으므로 안전하다.

이 그래프에서 사이클을 탐지하는 알고리즘은 $$n^{2}$$의 연산이 필요하다(n은 프로세스의 수).

은행원 알고리즘(Banker's Algorithm)

은행가 알고리즘은 각 자원의 유형마다 여러 인스턴스가 존재하는 경우에 사용한다. 프로세스 시작 시에 각 프로세스는 자신에게 필요한 각 자원의 최대치를 미리 선언한다. 각 프로세스가 자원을 요청하면 요청을 수락했을 때 안정 상태가 유지되는지를 판단하고 아니라면 해당 프로세스를 대기시킨다. 자원 할당 그래프 기법보다 효율성이 떨어진다.

은행가 알고리즘의 적용 방법은 동영상으로 대체

교착상태 탐지

교착 상태가 일어나는 것을 허용하는 시스템, 즉 교착상태 회피나 예방을 하지 않는 시스템이다. 대신 교착상태가 일어난다면 교착상태를 탐지해 그에 대한 적절한 처리를 해준다.

• 구성 방법
  • 탐지 알고리즘: 시스템을 검사해 교착상태 발생 여부 결정
  • 복구 기법: 교착상태로부터의 회복
• 탐지 알고리즘의 사용(언제 호출해야하나?)
  • 자원을 요청했는데 즉시 할당되지 못하고 있는 경우
  • 일반적으로 CPU 사용률이 40% 이하로 떨어지는 경우

복구 기법

시스템 운영자에게 통지하여 수작업으로 처리하거나 시스템이 자동적으로 회복하는 방법 두 가지가 있다.

교착 상태를 깨뜨리는 방법은 프로세스를 강제 종료시키거나, 교착상태에 있는 한 개 이상의 프로세스의 자원을 선점하는 방법이 있다.

프로세스를 전체를 강제 종료하는 방법도 있지만 부담이 크다. 보통 사이클이 깨질때까지 하나씩 종료한다.

선점하는 방법에는 victim을 어떻게 선정할지, 복구(rollback)은 어떻게 처리할지, 기아 상태는 어떻게 해결할지 등의 이슈가 있다.