[운영체제] Part 3 - 프로세스 동기화:: 교착 상태

서정범·2024년 2월 26일

운영체제

목록 보기

9/16

교착상태(Deadlock)는 여러 프로세스나 스레드가 서로가 보유하고 있는 자원을 요청하면서, 무한히 대기하는 상황을 말합니다. 이 상태에 빠지면, 해당 프로세스들은 더 이상 진행할 수 없게 되고, 시스템의 자원도 낭비하게 됩니다.

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

상호 배제(Mututal Exclusion): 한 번에 하나의 프로세스만이 자원을 사용할 수 있습니다.
점유 대기(Hold and Wait): 프로세스가 최소한 하나의 자원을 점유한 채로, 다른 프로세스가 점유한 자원을 추가로 기다립니다.
비선점(No Preemption): 자원을 점유하고 있는 프로세스가 스스로 자원을 방출하기 전까지, 다른 프로세스가 그 자원을 빼앗을 수 없습니다.
순환 대기(Circular Wait): 각 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있어, 무한 대기 상태가 발생합니다.

1. 시스템 모델

시스템은 경쟁하는 스레드들 사이에 분배되어야 할 유한산 수의 자원들로 구성됩니다.

따라서, 여러 스레드들은 자원을 공유해서 사용하게 되며 때때로 경쟁 상태에 놓이게 됩니다.

공유하는 자원에 대해서 정상적인 동작을 보장하기 위해서 락 기법과 같은 방법을 사용하고 이것은 액세스를 보호하는데 사용됩니다.

정상적인 작동 모드하에서, 프로세스는 다음 순서로만 자원을 사용할 수 있습니다.

요청: 스레드가 자원을 요청합니다. 요청이 즉시 허용되지 않으면 요청 스레드는 자원을 얻을 때까지 대기해야 합니다.
사용: 스레드은 자원에 대해 작업을 수행할 수 있습니다.
방출: 스레드가 자원을 방출합니다.

자원의 요청과 방출은 시스템 콜입니다.

예로 보자면,

장치의 request()와 release()
파일의 open()과 close()
파일의 allocate()와 free()
세마포어의 wait()와 signal()
Mutex 락의 acquire()와 release()

이러한 것들이 존재합니다.

2. 다중 스레드 응용에서의 교착 상태

아주 간단한 예시로, POSI mutex 락을 사용하여 다중 스레드 Pthread 프로그램에서 교착 상태가 일어나는 상황을 확인해 보자.

pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;

pthread_mutex_init(&first_mutex, NULL);
pthread_mutex_init(&second_mutex, NULL);

 . . . 
 
 /* thread_one은 이 함수를 실행 */
 void *do_work_one(void *param)
 {
 	pthread_mutex_lock(&first_mutex);
    prhread_mutex_lock(&second_mutex);
    
    /**
     * Do some work
     */
    pthread_mutex_unlock(&second_mutex);
    pthread_mutex_unlock(&first_mutex);
    
    pthread_exit(0);
}
/* thread_two은 이 함수를 실행 */
 void *do_work_two(void *param)
 {
    prhread_mutex_lock(&second_mutex);
    pthread_mutex_lock(&first_mutex);
    
    /**
     * Do some work
     */
    pthread_mutex_unlock(&first_mutex);
    pthread_mutex_unlock(&second_mutex);
    
    pthread_exit(0);
}

이러한 상황에서 두 스레드가 거의 동시에 실행되어 thread_one은 first_mutex 락을 획득하고, thread_two는 second_mutex 락을 획득한 상황이라면 교착상태가 발생할 것입니다.

2.1 라이브락

라이브락(livelocK)은 또 다른 형태의 라이브니스 장애입니다.

이것은 교착 상태와 유사하지만 스레드가 진행할 수 없는 원인이 다릅니다.

교착 상태의 경우에는 어떤 스레드 집합의 모든 스레드가 같은 집합에 속한 다른 스레드에 의해서만 발생할 수 있는 이벤트를 기다리면서 봉쇄되면 발생하는 반면, 라이브락은 스레드가 실패한 행동을 계속해서 시도할 때 발생합니다.

라이브락은 두 사람이 지나가려고 할 때 발생하는 상황과 유사합니다. 한 사람이 오른쪽으로 움직이고 다른 한 사람은 왼쪽으로 움직인다면 서로의 진행을 방해하게 됩니다. 그런 다음 한 사람은 왼쪽으로 이동하고 다른 한 사람은 오른쪽으로 움직입니다. 봉쇄되지는 않았지만 앞으로 진행할 수 없습니다.

코드의 예시를 확인하기 위해서 Pthread의 pthread_mutex_trylock()을 사용한 코드를 확인해 봅시다.

/* thread_one runs in this function */
void *do_work_one(void *param)
{
	int done = 0;
    
    while(!done) {
    	pthread_mutex_lock(&first_mutex);
        if (pthread_mutex_trylock(&second_mutex)) {
        	/**
             * Do some work
             */
            pthread_mutex_unlock(&second_mutex);
            pthread_mutex_unlock(&first_mutex);
        	done = 1;
        }
        else
        	pthread_mutex_unlock(&first_mutex);
    }
    
    pthread_exit(0);
}
/* thread_two runs in this function */
void *do_work_two(void *param)
{
	int done = 0;
    
    while(!done) {
    	pthread_mutex_lock(&second_mutex);
        if (pthread_mutex_trylock(&first_mutex)) {
        	/**
             * Do some work
             */
            pthread_mutex_unlock(&first_mutex);
            pthread_mutex_unlock(&second_mutex);
        	done = 1;
        }
        else
        	pthread_mutex_unlock(&second_mutex);
    }
    
    pthread_exit(0);
}

이 코드를 보면, 자원 호출에 실패하여, 각자의 락을 해제한 후 동일한 행동을 무한정 반복하는 상황을 그려볼 수 있습니다. 이것이 라이브락입니다.

라이브락은 일반적으로 스레드가 실패한 작업을 동시에 재시도할 때 발생합니다.

따라서 일반적으로 각 스레드가 실패항 행동을 재시도하는 시간을 무작위로 정하면 회피할 수 있습니다.

이 방법은 정확히 네트워크 충돌이 발생할 때 Ethernet 네트워크가 취하는 접근법입니다.

3. 교착 상태 특성

3.1 필요 조건들

이것은 앞서 정리를 했습니다. 4가지 조건들이 있는 것을 확인할 수 있었습니다.

상호 배제(mutual exclusion)
점유하며 대기(hold-and-wait)
비선점(no preemption)
순환 대기(circular wait)

네 조건이 완전히 독립적인 것은 아니지만, 별개로 간주하는 것이 유용합니다.

3.2 자원 할당 그래프

교착 상태는 시스템 자원 할당 그래프라고 하는 방향 그래프로 더욱 정확하게 기술할 수 있습니다.

먼저 아래 그림을 확인해 봅시다.

스레드 $T_i$ 로부터 자원 유형 $R_j$ 로의 방향 간선(directed edge)은 $T_i → R_j$ 로 표현하며, 이것은 스레드 $T_i$ 가 자원 유형 $R_j$ 의 인스턴스를 하나 요청하는 것으로 현재 이 자원을 기다리는 상태입니다.

$T_i → R_j$ 는 요청 간선(request edge)이라 부르고, $R_j → T_i$ 는 할당 간선(assignment edge)이라고 합니다.

아래 사진은 교착 상태를 갖는 자원 할당 그래프입니다.

만약 각 자원 유형이 정확하게 하나의 인스턴스만을 가지고 있으며, 사이클을 형성하고 있다면 이것은 교착 상태가 발생한 것입니다.

하지만 만일 각 자원 유형이 여러 개의 인스턴스를 가지면, 사이클은 반드시 교착 상태가 발생했음을 의미하지 않습니다.

4. 교착 상태 처리 방법

원칙적으로 교착 상태 문제를 처리하는 데는 다음과 같은 세 가지 다른 방법이 있습니다.

문제를 무시하고, 교착 상태가 시스템에서 절대 발생하지 않는 척합니다.
시스템이 결코 교착 상태가 되지 않도록 보장하기 위하여 교착 상태를 예방하거나 회피하는 프로토콜을 사용합니다.
시스템이 교착 상태가 되도록 허용한 다음에 복구시키는 방법이 있습니다.

Linux와 Windows를 포함해 대부분의 운영체제는 첫 번재 해결안을 선택하여 사용하고 있고 프로그램을 작성하는 것은 응용 개발자의 몫입니다.

통상 두 번째 해결안에 개략적으로 설명된 접근법을 사용하며, 데이터베이스와 같은 일부 시스템은 세 번째 해결안을 채택하여 교착 상태의 발생을 허용하고 복구 작업을 수행합니다.

교착 상태가 발생하지 않도록 하기 위해 시스템은 교착 상태 예방(prevention), 혹은 회피(avoidence) 기법의 하나를 사용할 수 있습니다.

교착 상태 예방은 4가지 필요조건 중 하나가 성립하지 않도록 보장하는 일련의 방법입니다.

교착 상태 회피는 스레드가 평생 요구하고 사용할 자원에 대한 부가적인 정보를 미리 제공할 것을 요구합니다. 이러한 추가적인 지식을 가지고, 운영체제는 각 요청을 위해 그 스레드가 기다려야 할지 않을지를 결정할 수 있습니다.

이러한 교착 상태 예방 혹은 교착 상태 회피 알고리즘을 적용하는 것은 교착 상태의 발생을 피할 수 있다는 측면에서는 효과적일 수 있지만, 이것은 분명한 오버헤드로 추가 비용이 발생하는 것입니다.

많은 시스템에서 교착 상태는 드물게 발생하기 때문에 다른 처리 방법을 사용하는 부가적인 비용은 그만한 가치가 없을 수 있습니다.

5. 교착 사태 예방

여기서는 네 가지 조건을 각각 별도로 검토함으로써 교착 상태 발생을 예방하는 접근 방식을 구체화합니다.

5.1 상호 배제

적어도 하나의 자원은 공유가 불가능한 자원이어야 합니다.

공유 가능한 자원들은 배타적인 접근을 요구하지 않으며, 따라서 교착 상태에 관련될 수 없습니다.

이를테면 읽기-전용 파일은 공유 가능한 자원이지만 동시 접근을 허용하기 때문에 교착 상태를 발생시키지 않습니다.

그렇다면, 파일들에 대해 동시 접근을 모두 허용함으로써 상호 배제 조건을 거부할 수 있나? 그럴 순 없다.

쓰기를 위한 접근과 같은 경우에 파일에 대한 수정이 이루어지고 있으며 이 과정에서 동시에 접근하는 것은 이루어 질 수 없기 때문에 피해야 합니다. 따라서, 이것을 위한 도구 중 하나인 mutex 락 기법과 같은 경우에도 여러 스레드가 공유할 수 없도록 되어 있습니다.

5.2 점유하며 대기

이 조건이 충족되지 않으려면 스레드가 자원을 요청할 때마다 다른 자원을 보유하지 않도록 보장해야 합니다.

스레드가 추가 자원을 요청할 수 있으려면, 자신에게 할당된 모든 자원을 먼저 방출해야 합니다.

이러한 프로토콜은 두 가지 주요 단점이 있습니다.

자원 이용률 문제: 자원이 할당되었지만 장기간 사용되지 않을 수 있기 때문에 자원 이용률이 낮을 수 있습니다.
기아 발생: 인기 있는 여러 개의 자원이 필요한 스레드는 필요한 자원 중 적어도 하나는 항상 다른 스레드에 할당되므로 무한정 대기해야할 수 있다.

5.3 비선점

이 필요조건은 이미 할당된 자원이 선점되지 않아야 한다는 것니다.

이 조건이 성립되지 않을 것을 보장하기 위해 다음과 같은 프로토콜을 고려해볼 수 있습니다.

만일 어떤 자원을 점유하고 있는 스레드가 즉시 할당할 수 없는 다른 자원을 요청하면(즉, 스레드가 반드시 대기해야 하면), 현재 점유하고 있는 모든 자원이 선점됩니다.

즉, 이들 자원들이 묵시적으로 방출됩니다. 선점된 자원들은 그 스레드가 기다리고 있는 자원들의 리스트에 추가됩니다.

다른 대안도 비슷한데 만약 자원을 점유하고 있는 스레드가 다른 추가의 자원을 대기하고 있다면 선점하고 아니라면 대기하는 방식입니다.

결국 이러한 방식들은 CPU 레지스터나 데이터베이스 트랜잭션처럼 그 상태가 쉽게 저장되고 후에 복원될 수 있는 자원에 종종 적용됩니다.

이것은 일반적으로 mutex 락과 세마포어 같은 자원에는 적용될 수 없습니다.

5.4 순환 대기

순환 대기 조건이 성립되지 않도록 하는 한 가지 방법은 모든 자원 유형에 전체적인 순서를 부여하여, 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구하는 것입니다.

각 스레드는 오름차순으로만 자원을 요청할 수 있는 것입니다. 즉, 스레드는 초기에 자원 $R_i$ 의 인스턴스(instance)를 요청할 수 있고 그 후에는 그 스레드는 $F(R_j) > F(R_i)$ 이고, 또한 그러할 때만 자원 $R_i$ 의 인스턴스를 요청할 수 있습니다.

만일 동일한 자원 유형의 인스턴스가 여러 개 필요하다면, 이들 모두에 대한 하나의 요청이 주어져야 합니다.

대안으로, 스레드가 자원 유형 $R_i$ 의 인스턴스를 요청할 때마다, $F(R_i) >= F(R_j)$ 인 모든 자원 $R_i$ 를 방출하도록 요구하는 방법이 있습니다.

이러한 프로토콜들을 사용하면 순환 대기 조건이 발생하지 않습니다.

6. 교착 상태 회피

교착 상태 예방은 필요조건 중 적어도 한 가지는 성립하지 않도록 보장합니다. 하지만 이런 방식으로 교착 상태를 예방할 때 가능한 부수적인 문제는 장치의 이용률이 저하되고 시스템 총처리율이 감소한다는 것입니다.

교착 상태를 회피하는 다른 대안은 자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구하는 것입니다.

가장 단순하고 제일 유용한 모델은 각 스레드가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구하는 것입니다.

교착 상태 회피 알고리즘은 시스템에 순환 대기 상황이 발생하지 않도록 자원 할당 상태를 검사합니다.

6.1 안전 상태

시스템 상태가 안전(safe)하다는 말은 시스템이 어떤 순서로든 스레드들이 요청하는 모든 자원(최대 요구 수를 요구하더라도) 교착 상태를 야기시키지 않고 차례로 모두 할당해 줄 수 있다는 것을 뜻합니다.

즉, 시스템이 안전 순서(safe sequence)를 찾을 수 있다면 시스템은 산전하다고 말합니다.

$<T_1, T_2, ..., T_n>$ 과 같은 스레드 순서가 안전하다는 말은 그 $T_i$ 가 요청하는 자원을 시스템에 현재 남아있는 자원과 앞에서 수행을 마칠 모든 스레드 $T_j$ 들이(j < i) 반납하는 자원들로 만족시켜 줄 수 있음을 뜻합니다.

즉, 현재 남아 있는 자원과 앞으로 받을 수 있는 자원들로 할당치를 채울 수 있다는 것을 의미합니다.

만약 모든 스레드를 무사히 마칠 수 있는 시퀀스를 찾을 수 없다면 불안전(unsafe)하다고 합니다.

시스템이 안전하다는 것은 교착 상태가 아니라는 것을 의미하지만, 시스템이 불안전하다는 것이 교착 상태를 의미하는 것은 아닙니다. 다만, 앞으로 교착 상태가 발생할 수 있음을 나타냅니다.

예시로 확인을 해봅시다.

시스템에 자원이 12개가 있고, $T_0$ , $T_1$ , $T_2$ 세 개의 프로세스가 있다고 합시다.

임의의 시점 $t_0$ 에서 $T_0$ 가 5개, $T_1$ 이 2개, $T_2$ 가 2개의 자원을 보유 중입니다. (따라서 남은 자원은 3개입니다.)

	최대 소요량	현재 사용량
$T_0$	10	5
$T_1$	4	2
$T_2$	9	2

현재 시스템의 상태는 안전합니다. $<T_1, T_0, T_2>$ 순서가 있습니다.

하지만 만약 $t_1$ 에서 $T_2$ 가 자원 한 개를 추가로 요청하여 그것을 주었다고 한다면, 시스템 상태는 더 이상 안전하지 않습니다. 이것은 교착 상태로 이어집니다.

기본 원칙은 시스템의 상태가 항상 안전 상태를 떠나지 않도록 고수하는 것입니다.

자원 할당을 요구받으면 즉시 할당할 수 있는지 대기해야 하는지 결정하는 것을 이 기준에 맞춰서 결정합니다.

6.2 자원 할당 그래프 알고리즘

앞서 정의한 자원 할당 그래프의 변형을 사용할 수 있는데, 요청 간선과 할당 간선에 추가하여 예약 간선(claim edge)이라는 새로운 타입의 간선을 도입합니다.

이것은 점선(dashed line)으로 표시합니다.

중요한 것은 예약 간선까지 활용함으로써 우리는 사이클 탐지(cycle detection)를 할 수 있게 되었다는 것입니다.

사이클 탐지 알고리즘을 이용해 안전성을 검사합니다.

6.3 은행원 알고리즘

교착 상태 회피 알고리즘의 대표적인 예는 은행원 알고리즘(Banker's Algorithm)입니다.

이것은 다음과 같은 정보를 기반으로 동작합니다.

각 스레드의 최대 자원 요구량[Max]
각 자원 유형별로 시스템에 존재하는 총 자원의 수[Available]
현재 각 스레드에게 할당한 자원의 수[Allocation]
각 스레드가 향후 필요한 자원의 수[Need]

스레드가 자원을 요청할 때 시스템은 다음과 같이 판단합니다.

요청된 자원이 스레드의 최대 요구량을 초과하지 않는지 확인합니다.
요청이 승인했을 때 시스템이 안전 상태를 유지할 수 있는지 시뮬레이션합니다.
a. 즉, 현재의 자원 할당과 가능한 모든 자원 요청 시나리오를 고려합니다.
b. 모든 스레드가 최대 자원 요구량을 만족시키면서 완료될 수 있는 순서가 있는지 확인합니다.
안전 상태를 유지할 수 있다면 요청을 승인하고 자원을 할당합니다. 안전 상태를 유지할 수 없다면 요청한 스레드는 대기합니다.

이점과 한계

이점: 이 방법은 시스템이 교착 상태 없이 자원을 효율적으로 할당할 수 있도록 돕습니다.
한계:
- 스레드가 요구할 수 있는 자원의 양을 미리 알아야 하며, 이는 항상 가능하지 않을 수 있습니다.
- 계산 오버헤드가 크며, 자원 활용도를 낮출 수 있어 실제 시스템에서 구현과 적용이 복잡할 수 있습니다.

안전성 알고리즘은 시스템이 안전한지 아닌지 알아낼 수 있는 알고리즘으로, 스레드가 끝나지 않았으며, 필요로 하는 자원을 할당 할 수 있는지 계속해서 탐색해가는 작업을 의미하고 할당 가능하다면 할당해주고 다시 재귀적으로 반복해서 탐색합니다. 모든 i 값에 대해서 Finish[i] == true이면 안전상태에 있다고 판단합니다.

자원 요청 알고리즘은 자원 요청이 안전하게 들어줄 수 있는지를 검사하는 알고리즘으로, 필요로 하는 자원의 개수보다 적게 요청했는지 확인하고 할당 가능한지 확인해주는 절차를 통해 요청을 처리해줄 수 있는지 확인합니다.

7. 교착 상태 탐지

만일 시스템이 교착 상태 예방이나 교착 상태 방지 알고리즘을 사용하지 않는다면, 교착 상태가 발생할 수 있습니다.

이러한 환경에서는 시스템은 다음 알고리즘들을 반드시 지원해야 합니다.

교착 상태가 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘
교착 상태로부터 회복하는 알고리즘

7.1 각 자원 유형이 한 개씩 있는 경우

모든 자원이 한 개의 인스턴스만 있다면, 대기 그래프(wait-for graph)라고 하는, 자원 할당 그래프의 변형을 사용해 교착 상태 탐지 알고리즘을 정의할 수 있습니다.

자원 할당 그래프로부터 자원 유형의 노드를 제거하고 적절한 간선들을 결합함으로써 대기 그래프를 얻을 수 있습니다.

7.2 각 유형의 자원을 여러 개 가진 경우

대기 그래프는 종류마다 자원이 여러 개씩 존재하는 상황에서는 사용할 수 없습니다.

아래의 기법은 이러한 상황에서 교착 상태를 탐지할 수 있습니다.

Available: 각 종류의 자원이 현재 몇 개가 가용한지를 나타내는 벡터로 크기가 m입니다.
Allocation: 각 스레드에 현재 할당된 자원의 개수를 나타내는 행렬로 크기가 n x m 입니다.
Request: 각 스레드가 현재 요청 중인 자원의 개수를 나타내는 행렬로 크기가 n x m 입니다. Request[i][j] == k라면 현재 $T_i$ 가 $R_j$ 를 k개 요청 중입을 뜻합니다.

여기서 기술하는 탐지 알고리즘의 원리는 가능한 모든 할당 순서를 조사해보는 방식입니다.

Work와Finish는 크기가 m과 n인 벡터입니다. Work = Available로 초기 값을 줍니다. i = 0, 1, ..., n - 1에 대해서 $Allocation_i ≠ 0$ 이면 Finish[i] = false입니다. 그렇지 않으면 Finish[i] = true입니다.
아래 두 조건을 만족시키는 i 값을 찾습니다.
a. $Finish[i] == false$
b. $Request_i ≤ Work$
그러한 i 값을 찾을 수 없다면 4번으로 갑니다.
$Work = Work + Allocation_i$
$Finish[i] = true$
2번으로 갑니다.
어떠한 i 값에 대해 $(0 ≤ i < n)$ $Finish[i] == false$ 이면 이 시스템은 교착 상태에 빠져 있는 것입니다. 그리고 $T_i$ 가 교착 상태에 빠져있습니다.

이 탐지 알고리즘을 실행하는 데에믄 $m * n^2$ 개의 연산이 필요합니다.

여기서 3번은 자원을 충분히 할당할 수 있고 할당을 한다면 작업을 완료하고 가지고 있던 자원들을 반납할 것이기 때문에 자원을 회수하는 과정을 표현한 것입니다.

교착 상태로부터의 회복은 스레드를 종료하는 방법과 자원 선점하는 두 방법으로 나눌 수 있는데, 모든 스레드를 종료하는 방법을 제외하곤 어떠한 스레드 혹은 자원을 선택할지와 그것을 선택하여 원하는 방식대로 진행했을 때 교착 상태가 끝날지도 확인해야되기 때문에 상당한 오버헤드를 동반할 수 있다는 것을 명심해두자.

참고한 자료

운영체제[공룡책]

서정범

개발정리블로그

이전 포스트

[운영체제] Part 3 - 프로세스 동기화:: 동기화 예제

다음 포스트