The Dining Philosophers

'철학자들의 만찬'입니다
멀티프로세서를 만드는데 기준이 된다는 파일이라고합니다. 
식사하는 철학자들이 자원을 공유하는 동기화된 병행프로세서를 위한 표준 모델입니다. 
우선 둥그런 탁자가 있죠.. 거기에 다섯명의 철학자들이 밥을 먹으려고 하고 있죠.. 그런데 젖가락은 한 사람앞에 한짝밖에 없어요.. 그러니깐 동시에 밥을 먹을수 있는 인원은 2명이죠.. 각 철학자가 한짝씩 젖가락을 잡으면 한사람도 식사를 할수 없는 교착상태에 빠지게 됩니다. 철학자들은 단지 자신의 오른쪽이나 왼쪽의 젖가락만을 취할수 있죠... 이것은 우선 젖가락을 얻으려고 시도하고 성공하면 되돌려 주려고 다시 생각을 하죠.. 후후후 이것을 이해하려면 8시간은 있어야 한다구 교수님이 그러시더군요... 4시간에 이해하면 이쪽 분야에서 전문가가 된다던가??? 흠 하여간 먹는것을 무한으로 반복하게 되는 프로그램입니다.. 울 시험에서는 여기에 사람 한명이 더추가되고 30번 먹기로 되었죠... 그리고 철학자가 석가, 예수, 알리, 공자, 슈트라, 나로 지정되고 석가는 왼손 잡이라고 정해 주었습니다. 그러니깐 석가는 왼손을 먼저 쓰게 되는것이죠.. 
그리고 나는 다른 사람보다 먼저 식사를 시작할수 없으며 다른사람이 식사를 끝내면 나도 무조건 끝내는 것이었죠.. 하지만 여기 있는 것은 그냥 철학자들의 만찬입니다... 

멀티프로세싱에서는 상당히 유명한 소스라고 하네요... 
 

=======================================================

 

해결책

1. 5명의 테이블에 최대 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.

2. 한 철학자가 젓가랑 두개를 모두 집을 수 있을때만 젓가락을 집도록 허용한다.

-이렇게 하려면 철학자는 임계구역 안에서만 젓가락을 집어야 한다.

3. 비대칭 해결안

- 홀수 번호의 철학자는 먼저 왼쪽 젓가락을 집고 다음에 오른쪽 젓가락을 집는다.

- 짝수 번호의 철학자는 오른쪽 젓가락을 집고 다음에 왼쪽 젓가락을 집는다.

 

기아(starvation)가 생기지 않도록 하는 것도 중요하다.

-교착 상태가 없는 해결안이 반드시 기아의 가능성도 제거하는 것은 아니다.

=======================================================
/* The dining philosopher program. */

#include <stdio.h>
#include <stdlib.h>/* for calloc() and exit() */

#define N 5 /* number of philosophers */
#define Busy_Eating 1 
#define Busy_Thinking 1
#define Left(p) (p) /* chopstick macros */
#define Right(p) (((p) + 1) % N)

typedef int * semaphore;

semaphore chopstick[N]; /* global array */

int fork(void);
semaphore make_semaphore(void);
void philosopher(int me);
void pick_up(int me);
int pipe(int pd[2]);
void put_down(int me);
int read(int fd, void *buf, unsigned len);
void signal(semaphore s);
void sleep(unsigned seconds);
void wait(semaphore s);
int write(int fd, void *buf, unsigned len);

int main(void)
{
int i;

for (i = 0; i < N; ++i) { /* put chopsticks on the table */
chopstick[i] = make_semaphore();
signal(chopstick[i]); 
}
for (i = 0; i < N - 1; ++i) /* create philosophers */
if (fork() == 0)
break;
philosopher(i); /* all executing concurrently */
return 0;
}

/* Acquire chopsticks, input is philosopher number. */

void pick_up(int me)
{
if (me == 0) {
wait(chopstick[Right(me)]);
printf("Philosopher %d picks up right chopstick\n", me);
sleep(1); /* simulate slow picking up to encourage deadlock */
wait(chopstick[Left(me)]);
printf("Philosopher %d picks up left chopstick\n", me);
}
else {
wait(chopstick[Left(me)]);
printf("Philosopher %d picks up left chopstick\n", me);
sleep(1); /* simulate slow picking up to encourage deadlock */
wait(chopstick[Right(me)]);
printf("Philosopher %d picks up right chopstick\n", me);
}
}

/* Relinquish chopsticks, input is the philosopher number. */

void put_down(int me)
{
signal(chopstick[Left(me)]);
signal(chopstick[Right(me)]);
}

/* Philosopher process, input is the philosopher number. */

void philosopher(int me)
{
char *s;
int i = 1;

for ( ; ; ++i) { /* forever */
pick_up(me);
s = i == 1 ? "st" : i == 2 ? "nd" : i == 3 ? "rd" : "th";
printf("Philosopher %d eating for the %d%s time\n", me, i, s);
sleep(Busy_Eating);
put_down(me);
printf("Philosopher %d thinking\n", me);
sleep(Busy_Thinking);
}
}

semaphore make_semaphore(void)
{
int *sema;

sema = calloc(2, sizeof(int)); /* permanent storage */
pipe(sema);
return sema;
}

void wait(semaphore s)
{
int junk;

if (read(s[0], &junk, 1) <= 0) {
printf("ERROR: wait() failed, check semaphore creation.\n");
exit(1);
}
}

void signal(semaphore s)
{
if (write(s[1], "x", 1) <= 0) {
printf("ERROR: write() failed, check semaphore creation.\n");
exit(1);
}
} </stdlib.h></stdio.h>