[OS] Deadlock II (Dining Philosopher Problem, Banker's Algorithm)

식사하는 철학자 문제

 유명한 컴퓨터 공학자인 Dijikstra 께서 고안한 문제이다. 5명의 철학자가 있고, 5개의 포크가 테이블에 있다. 이때 철학자가 식사하기 위해서는 2개의 포크가 필요하다. 어떤 철학자라도 하나의 포크를 동시에 사용할 수 없다. 즉 포크는 Critical Resource로 Mutual Exclusion을 보장해줘야하는 존재이다. 식사하는 철학자의 문제는 Deadlock을 막기 위함이다. 식사하는 철학자 문제를 컴퓨터 공학적 관점에서 바라본다면, 철학자는 Process, 포크를 Resource로 바라보면 되겠다. 철학자는 단순히 다음과 같은 동작을 수행한다. 생각하고 -> 포크를 잡고 -> 먹고 -> 포크를 내려놓고. 즉 코드로 이를 정리해보자면 아래와 같을 것이다. 역시 뇌를 사용하면 배가 고파진다. 

while(true) {
    think();
    getfork();
    eat();
    putfork();
}

 이를 대충 수코도드만 적어본다면 아래와 같다. 

semaphore fork[5] = {1};
int i;
void philosopher(int i) {
	while(true) {
    	think();
        wait(fork[i]);
        wait(fork[(i + 1) mod 5]);
        eat();
        signal(fork[(i + 1) mod 5]);
        signal(fork[i]);
    }
}

int main() {
    threads_begin:
    	philosopher(0);
        philosopher(1);
        philosopher(2);
        philosopher(3);
        philosopher(4);
}

 쓰레드로 실행하기 때문에 철학자들이 포크를 내려놓지 않고 잡고잡고잡는 상태가 일어난다면 당연히 Deadlock을 일으킬 것이다. 여기에서 modular 연산을 해준 이유는 당연히 5번째 즉, philosopher(4)는 0번 포크를 잡아야하기 때문이다. 

 

Solution 1

가장 간단한 솔루션 중 하나는 애초에 room이라는 semaphore를 사용해서 room = 4를 설정하면 해당 room에는 4명밖에 들어갈 수 없다. 즉 다시말해 테이블에 앉힐 수 있는 철학자의 수 자체를 제한하는 것이다. 이는 단순히 mutex로 구현한다. 

semaphore fork[5] = {1};
semaphore room = 4;
int i;
void philosopher(int i) {
	while(true) {
    	think();
        wait(room);
        wait(fork[i]);
        wait(fork[(i + 1) mod 5]);
        eat();
        signal(fork[(i + 1) mod 5]);
        signal(fork[i]);
        signal(room);
    }
}

int main() {
    threads_begin:
    	philosopher(0);
        philosopher(1);
        philosopher(2);
        philosopher(3);
        philosopher(4);
}

 그러나 이렇게 구현하게 된다면 당연히 병행성은 떨어지게 된다. room이라는 Mutex Variable을 통해 들어오는 철학자의 수를 제한하여 Deadlock은 발생하지 않는다. 결국 병행성과 Deadlock의 Trade-off라고 생각하자. 

Solution 2

 다음은 Deadlock의 조건 중 하나인 Hold and Wait을 제거하는 방식이다. 

semaphore fork[5] = {1};
semaphore once = 1;
int i;
void philosopher(int i) {
	while(true) {
    	think();
        wait(once);
        wait(fork[i]);
        wait(fork[(i + 1) mod 5]);
        signal(once);
        eat();
        signal(fork[(i + 1) mod 5]);
        signal(fork[i]);
    }
}

int main() {
    threads_begin:
    	philosopher(0);
        philosopher(1);
        philosopher(2);
        philosopher(3);
        philosopher(4);
}

 이렇게 구현하면 한 번에 request를 보낼 수 있다. once라는 Semaphore 변수를 초기화 해서 fork를 잡을 때 왼쪽 포크와 오른쪽 포크를 한 번에 잡을 수 있도록 Mutex를 통해 request를 처리할 수 있다. 이렇게 하면 당연히 Hold and Wait이라는 Deadlock의 조건을 위배하는 것이기에 Deadlock이 발생하지 않는다. 문제는 역시 Concurrency이다. 추가적인 Mutex를 사용할 때 어떤 한 명이 포크를 잡을 때 다른 철학자들이 진입하지 못하므로 Concurrency의 문제는 피해갈 수 없다. 이 역시 Trade-off의 문제이다. 

Solution 3

마지막으로는 Circular Wait을 해결하는 것이다. 우리는 Resource Ordering이라는 기법을 사용한다. Resource Ordering이란 resource에 선형적인 번호를 매기는 것이다. 다시말해 포크와 철학자에 번호를 매겨주는 것이다. 문제가 되었던 것은 위의 코드는 철학자의 번호와 맟는 포크를 집고, 그 다음 번호의 포크를 집었다. 그러나 마지막 4번 철학자에게 있어서 얘는 오른쪽을 먼저 집게 한 후에 자신의 번호의 포크를 잡게 한다면 Deadlock은 발생하지 않는다. 

semaphore fork[5] = {1};
int i;
void philosopher(int i) {
	while(true) {
    	think();
        if (i < 4) {
        	wait(fork[i]);
        	wait(fork[(i + 1) mod 5]);
        }
        else {
        	wait(fork[(i + 1) mod 5]);
        	wait(fork[i]);
        }
        eat();
        signal(fork[(i + 1) mod 5]);
        signal(fork[i]);
    }
}

int main() {
    threads_begin:
    	philosopher(0);
        philosopher(1);
        philosopher(2);
        philosopher(3);
        philosopher(4);
}

 추가적인 lock을 사용하지 않기 때문에 당장은 이 Deadlock을 해결할 수 있는 Optimal한 Solution으로 보일 수 있다. 그러나 문제는 철학자가 더 있다면 어떻게 될까. Process의 개수가 더 추가된다면 우리는 또 코드를 고쳐야한다. 만약 프로그램이 엄청 크다면 이를 컴파일 하는데에만 한 세월일 것이다. 따라서 이같은 방식 역삭 미래의 문제에 대해 Concurrency 문제가 발생한다고 볼 수 있다. 

Deadlock Avoidance

 지금까지 Dining Philosopher 문제를 해결하는데 Deadlock Prevention 기법을 사용해봤다. Prevention 방식들을 Resouce의 사용 방법들에 대한 제약이었다. 따라서 이는 결국 Concurrency가 떨어진다는 Side Effect가 확인되었다. 반면 Avoidance는 Resource의 Request를 일단 받고 얘를 request를 Approve했을 때 Deadlock이 발생할지 안할지 판단한다. state를 보고 safe하다고 판단되면 request를 Approve하고, unsafe하다고 판단하면 Reject해버린다. 이 state는 앞선 포스팅에서 살펴본 Resource Allocation Graph Algorithm에서 사용된 것과 동일하다. 다시 정리하자면 Safe Status는 Deadlock이 발생하지 않는 다는 것을 Guarantee해주는 상태이며, Unsafe Status는 Deadlock이 발생할 수도 있는 상태이다. 따라서 Deadlock Avoidance는 Deadlock이 발생할 수도 있는 상태 자체를 진입시키지 않음으로서 문제를 그냥 회피를 해버릴 수 있다. 그러나 Resource Allocation Graph에서 instance가 여러개하면 이 알고리즘을 사용하지 않는다. 따라서 Deadlock Avoidance를 위해 Process Initiaion Denial 방식과 Resource Allocation Denial 즉 프로세스 시작 거부 방법과 자원 할당 거부 방식을 사용한다. 

Process Initiaion Denial

 n개의 process와 m개의 다른 자원의 타입이 있다고 해보자. 그러면 시스템에 있는 총 자원의 대한 Vector 즉 Resource Vector가 있다. 그리고 각 자원이 현재 사용될 수 있는 Available Vector 역시 존재한다. 그리고 요구 행렬이 존재한다. nXm 사이즈의 요구행렬은 Cij 라고 표현할 때 i의 Process가 j라는 resource를 사용하고 싶다 라고 하는 정보의 행렬이다. 마지막으로 nXm의 사이즈의 Allocation Vector 즉 할당 행렬이 존재한다. Aij라고 표현했을 때 i의 Process가 j의 resource를 얼마나 현재 가지고 있는지에 대한 현재 상황을 보여준다. 

 이렇게 글로 작성하면 이해하기가 어려울 수 있으니 표로 이를 다시 정리해보겠다. 

 따라서 이와 같은 부등식들이 나오게 되는데, 첫 번째 부등식은 뭐 당연하다. 이제 아래의 부등식을 보면 되는데 새로운 Process는 아래의 부등식을 먼저 체크를 한다. 이 부등식을 만족할 때만 Process는 진입할 수 있고 아니라면 Deny된다. 이렇게 먼저 자원에 대한 판단을 먼저 수행하고 Process를 시작할지 말지 결정한다면 Deadlock을 미리 회피할 수 있다. 그러나 이 분석은 어디까지나 Worst Case에 대한 분석이다. 따라서 Claim이 Maximal하게 들어올 수 있다는 것이다. 

Resource Allocation Denial

 Flow를 조금 따라온다면 이는 Process의 진입이 아닌 자원을 할당하는 것에 대한 판단이다. 따라서 Request가 올 때마다 Safe한 Status인지를 항상 체크하고 Allocate을 안다. 만약 그게 아니라면 단순히 한 사이클 정도 wait하면 된다. Resource Allocation Denial을 사용하는 유명한 알고리즘증 하나는 Banker's Algorithm인다. 은행원 알고리즘이라고도 하는데 아래의 그림을 보자.

 어떤 시스템의 Snapshot이라고 하자. 3개의 Process가 있고, 12개의 Resource가 있다고 하자. 현재 Allocation Vector의 합은 9. 따라서 현재 Available Vector의 수는 12 - 9 = 3이 된다. 여기서 이제 Claim - Allocation이라는 Column의 정차는 각 Process에서 추가적으로 요구할 수 있는 자원의 worst case의 수이다. 이제 이 알고리즘이 어떻게 진행되는지 살펴보자. 만약 현재 P1이나 P3에게 자원을 할당한다면 당연히 Deadlock에 빠질 것이다. 왜냐면 Claim - Allocation만 보아도 현재 Available한 자원의 수를 넘어가기 때문이다. 반면 P2는 가능하다. C-A가 2이기 때문에 Claim이 4라고 현재 2가 할당되어 있고 추가적으로 2만큼만 할당해주면 되는 문제이기 때문이다. 따라서 이를 할당해준다. 그렇다면 P2는 다 끝내고 총 4개의 Resource를 반환하며, 이때 Available Vector에서 사용가능한 Resource는 1 + 4 = 5가된다. 이제 P2는 Request를 하지 않는다고 가정하고, 우리는 이제 P1에게 Allocate 할 수 있다. 할당하고 P1이 끝나면 Resource가 Release되어 Available Vector는 10개의 Resource가 있을 것이다. 마지막으로 이제 P3에게 Allocate해주면 V = 12로 모든 자원을 정상적으로 회수할 수 있다. 따라서 Ci - Ai <= V일때만 자원을 할당한다고 생각하면 편하다. 

 이 알고리즘으로 부터 얻을 수 있는 것은 바로 Allocation을 할 수 있는 Sequence가 존재한다는 것이다. 따라서 방금 언급한 부등식이 매우 중요하다고 할 수 있다. 

 

https://www.youtube.com/watch?v=iA4BBwWEEiM 

Banker's Algorithm을 직접 구현해본 영상이다. 혹시 Banker's Algorithm의 코드가 필요하다면 댓글을 남겨주세요.