식사하는 철학자
식사하는 철학자라는 유명한 데드락 문제를 해결해보자.
<문제상황>
같은 집에 살고있는 5명의 철학자의 삶은 매우 단조롭다.
사색과 식사로만 이루어져있다.
철학자들은 스파게티가 사색에 도움이 된다는 사실을 알아냈고
스파게티를 먹기위해서는 2개의 포크를 사용해야한다.
철학자들은 테이블에 앉아 사색을 하다 배가고파지면 포크를 2개들고 스파게티를 먹는다.
포크는 사람의 수만큼 준비되어 있으며
1. 임계영역이 지켜져야한다. 즉, 철학자는 같은 포크를 사용치 못한다.
2. 데드락 또는 기아(starvation) 상태에 빠지면 안된다.
이 조건에서 모든 철학자가 스파게티를 먹을수 있는 방법은?세마포를 활용한 방법
첫번째 (데드락 발생)
/* program diningphilosophers */
semaphore fork[5] = {1};
int i;
void philosopher(int i) {
while (true) {
think();
wait(fork[i]);
wait(fork[(i+1) % 5]);
eat();
signal(fork[(i+1) % 5]);
signal(fork[i]);
}
}
void main() {
parbegin(philosopher(0), philosopher(1),
philosopher(2), philosopher(3), philosopher(4));
}
포크는 5개 존재하며 이 포크를 세마포라 생각하면 된다.
i번째 철학자는 사색을하다가 배가 고프면 내 포크(왼편)을 들고
오른쪽의 포크를 쥐고 밥을 먹는다.
밥을 다 먹으면 오른편의 포크와 내 포크를 반납한다.
언듯보면 문제가 해결된거 같으나 이 경우에는 Deadlock 발생 위험이 있다.데드락 발생 상황
데드락이 발생하는 상황은 다음과 같다.
0번째 철학자가 0번 포크를 쥐고 타임아웃 된다.
1번째 철학자가 1번 포크를 쥐고 타임아웃 된다.
2번째 철학자가 2번 포크를 쥐고 타임아웃 된다.
3번째 철학자가 3번 포크를 쥐고 타임아웃 된다.
4번째 철학자가 4번 포크를 쥐고 타임아웃 된다.
다시 0번째 철학자가 1번 포크를 요청한다.
1번째 철학자가 2번 포크를 요청한다.
2번째 철학자가 3번 포크를 요청한다.
3번째 철학자가 4번 포크를 요청한다.
4번째 철학자가 0번 포크를 요청한다.
이 경우 원형 대기 상태가 발생함으로 데드락 상태에 빠지게 된다.2번째 방법
위에서 발생한 문제를 해결하기 위해서 이번에는 room이라는 세마포를 하나더 사용한다.
/* program diningphilosophers */
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);
}
}
void main()
{
parbegin (philosopher (0), philosopher (1), philosopher (2),
philosopher (3), philosopher (4));
}
room은 철학자들이 들어가서 밥을 먹을수 있는 방의 정원을 의미한다.
철학자들은 사색을하다 배가 고프면 방에 들어가 포크를 쥐고 밥을 먹게된다.
이때 방에는 4명만 진입이 가능하다.
첫번째 방식에서 Deadlock이 발생한 상황은 모든 철학자들이
각자 자신의 포크를 쥐었을때 인데
이 방법에서는 애초에 4명만 포크에 접근이 가능하기에 데드락이 발생하지 않는다.
***
이때 room의 값은 3이던 2이던 1이던 상관없다.
하지만 철학자의 수보다 같거나 크면
결국 모든 철학자가 방에 들어와 포크를 쥐기에 Deadlock 발생 가능성이 존재한다.모니터를 이용한 방법
monitor dining_controller ;
cond ForkReady[5]; /* 동기화를 위한 조건 변수 */
boolean fork[5] = {true}; /* 각 포크 사용 가능 여부 */
void get_forks(int pid) /*pid는 철학자 id를 의미*/
{
int left = pid;
int right = (++pid) % 5;
/* 왼쪽 포크에 접근 */
if (!fork[left]) // 누가 왼쪽포크(내 포크)를 쓰고 있다면
cwait(ForkReady[left]); /* 조건 변수에서 대기 */
fork[left] = false;
/* 오른쪽 포크에 접근 */
if (!fork[right]) //오른쪽 포크(남의 포크)가 사용중이라면
cwait(ForkReady[right]); /* 조건 변수에서 대기 */
fork[right] = false;
}
void release_forks(int pid) {
int left = pid;
int right = (++pid) % 5;
/* 왼쪽 포크 반납 */
if (empty(ForkReady[left])) /* 대기하는 프로세스 없음*/
fork[left] = true;
else
csignal(ForkReady[left]); /* 대기하는 프로세스 깨움 */
/* 오른쪽 포크 반납 */
if (empty(ForkReady[right])) /* 대기하는 프로세스 없음 */
fork[right] = true;
else
csignal(ForkReady[right]); /* 대기하는 프로세스 깨움*/
}
void philosopher[k=0 to 4] /* 5명의 철학자 존재 */ {
while (true) {
think();
get_forks(k); /* 철학자가 모니터를 통해 2개의 포크 요청 */
eat_spaghetti();
release_forks(k); /* 철학자가 모니터를 통해 2개의 포크 반납 */
}
}
<코드 설명>
get_forks()
왼쪽과 오른쪽 포크가 사용가능한지 확인하며 불가하다면
불가능한 포크에 해당하는 대기 queue에서 대기한다.
release_forks()
밥을 다 먹고 포크를 반납하는데 만약 대기중인 사람이 있다면 깨워주고
없다면 그냥 포크를 반납한다.
대기 하는 사람이 있을때 그냥 깨우기만 하는 이유는
위 getfork 코드에서 깨어난다면
fork(left)=false 또는 fork(right)=false 작업을 할것이기 때문에 상관없다.
eat_spaghetti()
스파게티를 먹는 것은 모니터 밖에서 한다.
한 철학자가 포크 2개를 잡더라도 한명은 더 2개의 포크를 가질수 있기에
동시에 먹는 상황이 가능하다. 그렇기에 모니터 밖에 스파게티를 먹을수 있게한다.세마포 vs 모니터
세마포에서는 deadlock이 발생할 가능성이 있었지만
모니터에서는 deadlock이 발생하지 않는 이유는 무엇일까?
1. 포크를 왼쪽 -> 오른쪽 순으로 잡고 오른쪽 -> 왼쪽으로 놓기 때문에 세마포에서는 데드락이 걸리는 것인가?
-> 아니다 포크를 쥐는 순서든 놓는 순서를 바꾸던 상관없다.
2. 모니터에는 한번에 한 프로세스만 들어가기 때문인가?
-> 부족한 설명이다. 단순히 모니터에 한 프로세스만 접근이 가능해서 라고 한다면
포크를 쥐는 함수를 get_left_fork와 get_right_fork로 나누었을때
데드락이 발생하는 것을 설명할수 없다.
<이유>
세마포에서 데드락이 발생하는 상황을 살펴보자면
내가 오른편 포크를 사용가능한데도 불구하고
time-out 때문에 오른편 포크를 빼앗겨서 발생한다.
room을 이용하여 해결하였지만 내 오른편 포크를 사용가능한데 빼앗기더라도
하나이상의 포크가 남아서 누군가는 밥을 먹을수 있다 라는 해결책이였다.
하지만 모니터에서는 내가 왼쪽 포크를 손에 쥔다면
time-out이 걸리더라도 모니터 안에 존재하게 되기에
무조건 오른편 포크를 사용가능한지 아닌지 검사하게 된다.
따라서 오른편 포크가 사용가능함에도 빼앗기는 경우가 존재하지 않기에
데드락이 발생 가능성이 없다.
<get_left_fork(), get_right_fork()>
그렇다면 포크를 잡는 함수를 두개로 나눈다면 어떻게 될까???
메인 함수에서 왼편 포크를 잡고 모니터를 나와 오른편 포크에 접근하는것이다.
이렇게 된다면 time-out등의 이유로 내가 오른편 포크를
사용가능함에도 빼앗기는 상황이 발생한다.
이때문에 함수를 둘로 나눈다면 데드락 발생가능성이 존재한다.
학생