Deadlock: Dining Philosophers

Backstory

테이블을 둘러싸고 몹시 배고픈 철학자들이 앉아서 뭔가를 먹는다고 생각해 봅시다. 각각의 철학자들은 동일한 instruction set을 가지고 있어 다른 철학자들이 무언가를 하거나 모든 홀수 철학자에게 무언가를 하도록 할 수 없습니다.

Failed Solutions

Left-Right Deadlock

void* philosopher(void* forks){
     info phil_info = forks;
     pthread_mutex_t* left_fork = phil_info->left_fork;
     pthread_mutex_t* right_fork = phil_info->right_fork;
     while(phil_info->simulation){
          pthread_mutex_lock(left_fork);
          pthread_mutex_lock(right_fork);
          eat(left_fork, right_fork);
          pthread_mutex_unlock(left_fork);
          pthread_mutex_unlock(right_fork);
     }
}

위 코드는 문제가 있습니다. 모든 사람이 왼쪽 포크를 잡고 오른쪽 포크를 기다리면 어떻게 될까요? 프로그램이 데드락에 걸리게 됩니다. 항상 데드락이 발생하지 않도록 하는 것이 중요합니다. 이 해결책에서는 철학자의 수가 증가할 수록 데드락의 가능성이 줄어듭니다. 하지만 진짜 중요한 점은 결국 이 해결책은 데드락이 발생하고, 스레드가 굶어죽게 됩니다.

Trylock? More like livelock

그렇다면 conffman condition을 깨는 방법을 생각해 봅시다.

• Mutual Exclusion
• NO Preemption
• Hold and wait
• Circular wait

두 철학자가 동시에 포크를 사용하게 할 수는 없으니 mutual exclusion은 제외합시다. 현재 단순한 모델로는 철학자가 일단 mutex lock을 잡으면 놓을 수 없으므로 이 문제를 해결해 봅시다.

Hold and wait을 깨 봅시다!

void* philosopher(void* forks){
     info phil_info = forks;
     pthread_mutex_t* left_fork = phil_info->left_fork;
     pthread_mutex_t* right_fork = phil_info->right_fork;
     while(phil_info->simulation){
          pthread_mutex_lock(left_fork);
          int failed = pthread_mutex_trylock(right_fork);
          if(!failed){
               eat(left_fork, right_fork);
               pthread_mutex_unlock(right_fork);
          }
          pthread_mutex_unlock(left_fork);
     }
}

이제 철학자들은 왼쪽 포크를 집고 오른쪽 포크를 집으려고 시도할 것입니다. 만약 가능하다면, 식사를 하고, 불가능하다면 왼쪽 포크를 내려놓고 다시 시도합니다. 이런 경우 데드락이 발생하지 않습니다!

하지만 역시 문제점이 남아있습니다. 모든 철학자들이 동시에 왼쪽 포크를 들고, 오른쪽 포크를 잡으려고 시도한다면, livelock에 걸리게 됩니다.

Viable Solution

Arbitrator( Naive and Advanced).

The naive arbitrator solution은 한 명의 중재자를 가지고 있습니다(예를 들어 mutex). 각각의 철학자는 중재자에게 먹어도 되는지 허가를 구합니다. 이 해결 방법은 한 번에 한 철학자만 식사가 가능합니다. 식사가 끝나면 다른 철학자가 허가를 구합니다.

이 해결 방법은 circular wait이 없어 데드락을 해결할 수 있습니다.

더 발전된 중재자 해결책은 클래스를 구현해 철학자의 포크가 중재자의 소유인지 결정하게 합니다. 만약 그렇다면, 중재자들은 포크를 철학자들에게 줘서 먹을 수 있게 하고, 포크를 돌려받습니다. 이렇게 한다면 동시에 여러 철학자가 먹을 수 있습니다.

Problems:

• 이 해결책은 느립니다.
• 하나의 실패 지점이 존재해서, 중재자가 bottle neck이 됩니다.
• 중재자는 공정해야 하고, 두 번째 방법에서 deadlock을 판단할 수 있어야 합니다.
• 실제 시스템에서는 중재자는 프로세스 스케쥴링 때문에 방금 식사를 한 철학자에게 반복적으로 포크를 주려는 경향이 있습니다.

Leaving the Table (Stallings' solution)

왜 첫 번째 방법이 데드락이었나요? N명의 철학자에게 N개의 젓가락이 주어졌기 때문입니다. 만약 1명의 철학자만 테이블에 남아있다면 데드락이 발생할 수 없을 것입니다.

Stallings's solution은 deadlock이 불가능할 때까지 철학자를 줄이는 것입니다. 테이블에 있는 철학자의 매직 넘버를 생각해봅시다. 실제 시스템에서 구현 방법은 세마포어를 통해 특정한 수의 철학자만 지나가게 하는 것입니다.

Problems:

• 이 해결책은 CPU의 소모가 큰 context switching이 자주 필요합니다.
• 철학자의 숫자를 줄이기 전에 resources의 숫자를 알아야 합니다.
• 이미 식사를 마친 철학자에게 우선 순위가 부여됩니다.

Partial Ordering (Dijkstra's Solution)

왜 첫번째 방법이 데드락이었을까요? Dijikstra는 왼쪽 포크를 집어든 마지막 철학자(첫 번째 방법을 데드락으로 만든)가 오른쪽 포크도 집어야 한다고 생각했습니다. 그는 포크들에게 번호를 부여하고 각각의 철학자들에게 더 낮은 번호의 포크를 선택하도록 했습니다.

데드락이 다시 발생하는지 살펴봅시다. 모두가 처음에 낮은 번호의 포크를 집으려고 합니다. 철학자 1은 1번 포크, 철학자 2는 2번 포크.... 이렇게 N명의 철학자가 포크를 잡습니다. 이렇게 된다면 포크1은 이미 철학자 1이 집었기 때문에 포크를 집을 수 없고, 마지막 철학자는 N번째 포크를 잡지 않습니다. 이렇게 함으로서 Circular wait을 어기게 됩니다. 즉, 데드락이 불가능해 집니다.

Problems:

• 철학자는 리소스를 잡기 전에 리소스의 집합을 순서대로 알고 있어야 합니다.
• 모든 자원에 부분적인 순서를 정의해야 합니다.
• 이미 식사를 한 철학자가 우선순위를 가집니다.