[운영체제] 고전적 동기화 문제-3 : 식사하는 철학자 문제(The Dining-Philosophers Problem)

참고도서: Operating System Concepts (10/E) Abraham Silberschatz, Peter B. Galvin, Greg Gagne

식사하는 철학자들

철학자들이면서 너무 단순 무식하다.. 식사하는 철학자들 문제는 이렇다. 식사를 하기 위해 모인 철학자 N 명이 있고, 각 철학자들 사이에는 젓가락이 하나씩 총 5개가 있다. 철학자들은 밥을 먹기위해서 두 개의 젓가락을 사용해야하는데, 하나의 젓가락을 바로 옆에 있는 철학자와 공유(…)하기 때문에 문제가 발생하게 된다.

만약 한번에 N명의 철학자들이 모두 자신의 왼쪽에 있는 젓가락을 집으려고 하는 상황을 상상해보자. 모양새가 웃기긴 하겠지만 각 철학자들은 왼쪽에 있던 젓가락 하나씩을 확보했다. 그리고 밥을 먹기위해서 오른쪽에 있는 젓가락을 들려고 했는데, 자신의 오른편에 있던 젓가락은 자신의 이전 사람이 왼손에 들고있기 때문에 그 사람이 젓가락을 놓길 기다리게 된다. 이렇게 모든 철학자들이 자신의 오른편에 있는 사람의 작업이 끝나길 기다리게 되기 때문에 교착상태(Deadlock) 상황에 빠지게 된다. 모든 철학자들이 굶어죽게(Starvation) 되는 것이다..

이 문제를 세마포어를 사용해서 해결해보자

Data Structure

일단 공유자원인 젓가락을 선언해보자 만약 다섯명의 철학자가 있다고 한다면,

semaphore chopstick[5];

이렇게 5개의 세마포어를 만들 수 있다. 배열의 인덱스는 각 젓가락들의 번호를 의미하고 각 젓가락은 한번에 한명만 집어들 수 있기 때문에 1로 초기화 된다.

Solution?

do {
    wait(chopstick[i]);         // 왼쪽에 있는 젓가락을 들 수 있는지 확인
    wait(chopstick[(i+1) % 5]); // 오른쪽에 있는 젓가락을 들 수 있는지 확인
    ...

    /* 식사(작업) */

    ...
    signal(chopstick[i]);           // 왼쪽 젓가락 내려놓기
    signal(chopstick[(i+1) % 5]);   // 오른쪽 젓가락 내려놓기
    ...

    /* 멍때리기 */

    ...
} while (true)

위 코드를 해석해보면 흐름은 아래와 같다.

1. 왼쪽에 있는 젓가락을 들 수 있는지 확인한다.
2. 들 수 있다면 오른쪽 젓가락을 들기위해 계속 진행하고, 다른 철학자가 오른쪽 젓가락을 들고 있다면 내려놓을 때까지 대기한다.
3. 두 개의 젓가락을 모두 획득했다면 작업을 수행한다.
4. 작업을 마치고 두 젓가락을 모두 내려놓는다.

세마포어를 사용해서 위와 같이 구현하게 되면 동시에 여러 철학자들이 한 젓가락에 접근하는 것은 막을 수 있다. 그렇다면 정말 동기화 문제가 해결이 된 것일까? 그렇지 않다. 초입에서 설명했던 것 처럼 만약에 모든 철학자들이 왼쪽에 있는 젓가락을 획득하게된다면, 5]); 코드에 의해서 누군가 오른쪽 젓가락을 내려놓는 signal 을 실행할때까지 대기하게 된다. 이때, 모든 철학자들이 이것을 위해 대기 큐에서 대기하게되기 때문에 Deadlock 상태에 빠지게 된다.

Possible Solutions

결론적으로 세마포어를 사용하는 것 만으로는 식사하는 철학자 문제를 해결할 수 없다. Deadlock을 해결하기 위한 몇가지 전략을 생각해보자

숫가락 갯수 - 1 명의 철학자만 식사자리에 초대하기

N개의 젓가락이 있다면, N-1명의 철학자만 함께 식사를 할 수 있게 한다. 이렇게 하면, 모두 동시에 왼쪽 젓가락을 들더라도, 한개의 여유 젓가락이 생기게 되고 한명의 최악의 경우에도 한명의 철학자가 식사를 시작하고 마칠 수 있게 된다.

동시에 양옆의 젓가락을 집을 수 있을 때만 젓가락을 집기

왼쪽과 오른쪽 젓가락이 모두 사용이 가능할 때만 젓가락을 집게한다. 지금 문제가 일단 왼쪽 젓가락은 무조건 집고 오른쪽을 확인하기 때문에 교착상태가 발생하는데, 두개가 모두 사용가능할 때만 젓가락을 획득하게하면 교착상태는 일어나지 않는다.

짝수번째 철학자와 홀수번째 철학자의 젓가락 집는 방향을 반대로 하기

홀수번째에 있는 철학자들은 왼쪽 젓가락을 먼저 집고, 짝수번째에 있는 철학자들은 오른쪽 젓가락을 먼저 집게한다. 이 규칙을 만들면 모든 철학자가 자신의 양옆에 있는 철학자들과 젓가락을 집는 방향이 달라지게되기 때문에 서로가 한쪽을 바라보며 서로를 기다려야하는 상황이 발생하는 않는다.