[Operating Systems] Deadlock

동기화의 정의를 다시 되새겨 보면 동시에 실행되는 여러 프로세스가적절한 순서로 실행하는 것을 보장하고 레이스 컨디션이 생기지 않도록 하는 것이다.
동기화 기법에는 피터슨 같은 소프트웨어 기법, Testandset 같은 것을 사용하는 하드웨어 기법 등이 있다.

자, 다시 동기화의 전통적인 문제로 되돌아 가보자.
우선 첫째로 Bounded Buffer 문제이다.
이 문제는 버퍼의 크기가 한정되어 있고 그것을 접근할 때 버퍼가 오버플로 나지 않도록 하는 방법이다.
이것은 버퍼에 접근하는 부분 앞에 세마포어와 같은 동기화 메커니즘을 이용하고 버퍼의 크기 만큼 자원이 획득 가능하도록 하면 된다. Readers and Writers Problem도 마찬가지로 동기화 메커니즘을 사용해 해결 가능하다.

하지만 세번째 식사하는 철학자 문제(Dining Philosopher's problem) 같은 경우는 단순한 동기화 메커니즘 사용만으로 문제 해결이 불가능한 경우가 생긴다.
일단 문제가 무엇인지 파악해보자.
이 문제는 n명의 철학자와 n개의 젓가락이 있을때 각각의 철학자가 밥을 먹기위해 두개의 젓가락을 필요로 하는 상황이다.
그런데 'n번째 젓가락 얻고 그다음 얻으면 되지' 라고 단순히 생각하여 프로그램을 다음과 같이 짜면 문제가 발생한다.

do { 
   wait( chopstick[i] );
   wait( chopstick[(i+1)%n] );

   //  먹자

   signal( chopstick[i] );
   signal( chopstick[(i+1)%n] );
} while(true);

하나의 철학자가 하나의 프로세스라고 가정했을 때 2번째 줄까지 실행하고 컨텍스트 스위칭 되고가 반복되었다고 가정해 보자.
그러면 어느 프로세스도 먹는 부분(크리티컬 섹션)에 들어가지 못하고 대기하는 상태가 된다.
이러한 상황을 데드락이라고 한다.

데드락 문제(Deadlock Problem)는 여러개의 경쟁하는 프로세스가 다른 프로세스가 끝나기를 바라지만, 아무도 끝나지 않는 상황을 말한다. 이러한 데드락이 발생하게 되는 조건은 다음의 4가지이며 이 네가지가 충족되어야 데드락이 발생한다.

1. Mutual Exclusion : 자원은 한 프로세스만이 독점한다.
2. Hold and Wait : 각 프로세스는 자원을 가진 상태로 다른 자원을 위해 대기한다.
3. No preemption : 자원은 자원을 가진 프로세스에 의해서만 반납 가능하다.(강제로 안됨)
4. Circular Wait : 각각의 자원을 요청하는 프로세스는 원형 구조를 띈다.

일단 본래의 식사하는 철학자 문제로 되돌아가서, 해결책을 살펴보면
첫번째 방법은 하나의 chopstick을 추가하거나, 혹은 한 명의 철학자를 없앤다.
두번째 방법은 두개의 chopstick이 이용 가능할 때에만 그 chopstick을 획득하도록 하는 것이고
마지막 방법은 asymmetric solution인데 홀수 번째 철학자는 왼쪽 chopstick을 먼저 획득하도록 하고, 짝수 번째 철학자는 오른쪽 chopstick을 먼저 획득하도록 한다.

이러한 데드락이 발생하는 것을 확인하기 위하여 프로세스간 자원 요청 관계를 Resource Allocation Graph로 나타낼 수 있으며 다음과 같은 모양으로 나타나진다.

이러한 RAG에서 사이클이 생긴다면 데드락이 생기거나, 데드락이 생길 가능성이 있다.(instance의 수에 따라 다름)


데드락을 다루는 방법으로 크게 두가지가 있다.
1. Proactive한 방법 -> Deadlock Prevention
2. Reactive한 방법 - > Deadlock detection & recovery

1번 방법은 데드락이 생기지 않도록 하는 것이고
2번 방법은 시스템이 데드락 상태로 들어가면 회복시키는 것이다. 

1번 방법인 데드락 프리벤션은 deadlock avoidance로 볼 수 있는데
deadlock state와 non-deadlock state로 나눈 후에 시스템이 데드락 상태로 들어갈 것인지 안들어갈 것인지 결정한다.
(이 부분이 제일 어렵다.)
그 이후에 시스템이 데드락 상태로 들어가지 않도록 무엇인가를 하는 과정을 거친다.

safe state는 데드락을 발생시키지 않고 어떤 순서로 자원을 할당할 수 있으면 safe state라고 한다.
싱글 인스턴스 같은 경우에는 RAG를 이용해서 상태를 판단하고
멀티플 인스턴스의 경우에는 banker's algorithm을 이용하여 상태를 판단한다.

2번 방법의 경우에는 데드락이 detect될경우,
어떠한 프로세스를 종료시키거나, victim을 선정하고 강제로 자원을 획득함으로써 문제를 해결할 수 있다.