Process Synchronization - Dining-Philosophers Problem

개요

'식사하는 철학자 문제'라고 하며 철학자는 1. 밥먹기 2. 생각하기 2가지 일을 할 수 있다. 반면 젓가락의 갯수(공유자원)는 제한되어 있다. 이 문제의 해결법을 코드로 살펴보자.

 

Solution A

Initialization

/* 최초 값은 모두 1이다. */
semaphore chopstick[5];

• 철학자는 5명으로 가정하고 젓가락은 5개가 있다고 가정하자.

Philosopher i(i번째 철학자)

do {
    //왼쪽, 오른쪽 젓가락을 잡는 연산
    P(chopstick[i]);
    P(chopstick[(i + 1) % 5]);

    //식사
    eat();

    //왼쪽, 오른쪽 젓가락 놓는 연산
    V(chopstick[i]);
    V(chopstick[(i + 1) % 5]);

    think();

} while(1);

각각 왼쪽, 오른쪽 젓가락을 잡는 연산(P)와 놓는 연산(V)를 통해서 공유 변수를 제어하고 있다. 하지만 이와 같은 코드는 Deadlock의 가능성이 존재한다. 만약, 모든 철학자가 동시에 배가 고파져서 왼쪽 젓가락을 집게 되는 경우가 그 예라고 할 수 있다.

해결 방안

• 4명의 철학자만이 테이블에 동시에 앉을 수 있도록한다.
• 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
• 비대칭 - 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록한다.

 

`젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.`의 경우 강의에서 세마포어로 해결하는 코드가 나오지만 세마포어 변수로 공유자원이 있는지 확인하는 것이 아니라 해당 자원이 사용 중인지 확인하는 방식이라 세마포어로는 약간 이해하기 힘들다고 한다.

그래서 패스. (Monitor라는 방식을 사용하면 해결 가능하다고 한다.)

 

 

 

출처

반효경, "운영체제 2014-1", KOCW, http://www.kocw.net/home/cview.do?cid=3646706b4347ef09