저번 시간에 멀티 프로세스, 멀티 스레드 환경에서 발생하는 경쟁 상황과 그에 따른 문제에 대해서 알아봤다.
또한 해당 문제를 해결하기 위한 동기화 기법들도 알아봤다.
이번에는 "교착 상태(Deadlock)"라는 문제에 대해서 알아보고, 해결하는 방법도 알아보자.
교착 상태(Deadlock)
스레드들이 특정 자원을 무한히 기다리고 있는 상태를 말한다.
스레드가 실행되기 위해 특정 자원이 필요한데, 해당 자원을 무한히 기다리면서 멈추는 상태를 말한다.
교착 상태의 예시를 알아보자.
위의 그림에서, 프로세스 P1은 R1을 가지고 있는 상태로 R2를 기다린다.
프로세스 P2는 R2를 가지고 있는 상태로 R1을 기다린다.
이렇게 서로 다른 프로세스가 특정 자원을 할당 받은 채로, 다른 프로세스에 할당된 자원을 무한히 기다리는 상황이 교착 상태이다.
코드로 한번 알아보자
#include <stdio.h>
#include <pthread.h>
#include <stdbool.h>
int num = 0;
void* thread_1(void* arg)
{
pthread_mutex_t* mutex = arg;
while(true)
{
pthread_mutex_lock(&(mutex[0]));
pthread_mutex_lock(&(mutex[1]));
num++;
printf("num = %d\n", num);
pthread_mutex_unlock(&(mutex[0]));
pthread_mutex_unlock(&(mutex[1]));
}
return NULL;
}
void* thread_2(void* arg)
{
pthread_mutex_t* mutex = arg;
while(true)
{
pthread_mutex_lock(&(mutex[1]));
pthread_mutex_lock(&(mutex[0]));
num++;
printf("num = %d\n", num);
pthread_mutex_unlock(&(mutex[1]));
pthread_mutex_unlock(&(mutex[0]));
}
return NULL;
}
int main()
{
pthread_t threads[2];
pthread_mutex_t mutex[2];
for (int i = 0; i < 2; i++)
{
pthread_mutex_init(&(mutex[i]), NULL);
}
pthread_create(&(threads[0]), NULL, thread_1, &mutex);
pthread_create(&(threads[1]), NULL, thread_2, &mutex);
for (int i = 0; i < 2; i++)
{
pthread_join(threads[i], NULL);
}
for (int i = 0; i < 2; i++)
{
pthread_mutex_destroy(&(mutex[i]));
}
return 0;
}
위의 코드에서 각 스레드는 2개의 mutex lock을 획득 후에 num 값을 1 올리고 출력한다.
스레드 1은 mutex[0] 부터 할당 받도록 하고, 스레드 2는 mutex[1] 부터 할당 받는다.
이때, 스레드 1이 mutex[0]을 할당 받고 문맥 교환이 일어나서 스레드 2가 mutex[1]을 할당 받게 되면, 각 스레드는 상대방 스레드의 mutex를 무한정 기다리는 교착 상태에 빠진다.
아래의 결과를 보자.
결과에서 볼 수 있듯이, 전역 변수 num 값이 273 까지 올랐다가 모든 스레드가 교착 상태에 빠져 프로그램이 멈춰버렸다.
이처럼 멀티 프로세스 환경에서는 교착 상태가 발생할 수 있는 가능성이 열려있기 때문에, 잘 고려하여 프로그래밍 해야 한다.
교착 상태의 조건
교착 상태가 발생할 수 있는 조건을 알아보자.
아래의 조건들을 전부 만족할 때, 교착 상태가 발생한다.
아래 조건들 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않는다.
상호 배제(Mutual exclusion)
mutex, semaphore 등의 동기화 기법을 사용해서, 스레드들이 상호 배제되는 것을 말한다.
점유와 대기(Hold and wait)
스레드가 자원을 점유한 채 다른 자원을 대기하는 상황을 말한다.
비선점(Nopreemption)
다른 스레드가 가지고 있는 자원을 선점하지(뺏지) 못한다.
즉, 점유하고 있는 자원은 해당 스레드에 의해 반납되어야 사용 가능해진다.
원형 대기(Circular wait)
자원 할당 그래프가 원형을 이루는 것을 말한다.
자원 할당 그래프
스레드와 자원들의 관계를 나타내는 그래프이다.
--
교착 상태 해결 방법
교착 상태를 해결하기 위한 방법 중 "교착 상태 예방", "교착 상태 회피"에 대해서 알아보자.
교착 상태 예방
교착 상태 예방은 교착 상태 발생 조건 네 가지 중 하나가 성립하지 않도록 하는 것이다.
교창 상태 발생 조건 중 하나만 만족하지 않아도 교착 상태는 발생하지 않는다.
상호 배제 없애기
현실적으로 불가능하다.
상호 배제를 없애면, race condition 상황이 일어나고 자원의 일관성이 깨진다.
점유와 대기 없애기
스레드가 자원을 요청할 때, 필요한 모든 자원을 요청하고 할당 받도록 한다.
이러한 방식은 대부분의 프로그램에서 실용적이지 않다.
또한 자원의 활용률이 떨어질 수 있다.
비선점 없애기
CPU와 같이 선점 가능한 자원에 대해서는 사용 가능하지만, 모든 자원이 선점 가능하지는 않다(mutex 같은 자원).
원형 대기 없애기
위의 세 가지 방법은 그다지 실용적이지 않다.
그러나 원형 대기를 없애는 방법은 실용적인 해결책을 제공할 수 있는 기회를 제공한다.
원형 대기를 없애는 알고리즘을 짜는 것은 어렵고, 어떻게 짜느냐에 따라 자원 활용률이 달라진다.
교착 상태 회피
교착 상태 회피는 스레드가 사용할 자원에 대한 정보를 미리 알고, 운영체제가 스레드가 기다려야 할지 않을지를 결정한다.
대표적으로 은행원 알고리즘이 있다.
자원을 필요로 하는 스레드 개수와, 현재 사용 가능한 자원의 개수를 사용하여 안전 상태, 불안전 상태를 계산하고, 자원을 조심조심 할당한다.
교착 상태가 되지 않을 만큼만 자원을 할당한다.
교착 상태 탐지
만일 교착 상태 예방이나 교착 상태 회피 알고리즘을 사용하지 않는다면, 교착 상태가 발생할 수 있다.
이러한 환경에서는 다음과 같은 알고리즘을 반드시 지원해야 한다.
- 교착 상태 탐지 알고리즘
- 교착 상태 회복 알고리즘
탐지와 회복 알고리즘은 각각의 역할을 위한 비용과 오버헤드가 필요할 수 있다.
교착 상태 회복
교착 상태 탐지 알고리즘이 교착 상태가 존재한다고 하면, 교착 상태를 회복해야 한다.
한 가지 방법은 운영자에게 알려서 수작업으로 처리하게 하는 것이다.
다른 방법은 시스템이 자동으로 교착 상태를 회복하는 방법이다.
교착 상태를 깨뜨리는 데에는 두 가지 방법이 있다.
- 한 개 이상의 스레드를 중지시켜 원형 대기 깨뜨리기
- 교착 상태에 있는 스레드의 자원 선점하기
두 방식 모두 각각의 역할을 수행하기 위한 비용이 많이 들고, 작업 중이던 자원의 내용이 부정확해질 수 있다.
