算法讨论:哲学家就餐问题
In 1965, Dijkstra posed and solved a synchronization problem he called the
dining philosophers problem. ........ The problem can be stated quite simply
as follows. Five philosophers are seated around a circular table. Each philo
sopher has a plate of spaghetti. The spaghetti is so slippery that a philoso
pher needs two forks to eat it. Between each pair of plates is one fork.
The life of a philosopher consists of alternate periods of eating and think
ing. When a philosopher gets hungry, she tries to acquire her left and right
fork, one at a time, in either order. If successful in acquiring two forks,
she eats for a while, then puts down the forks and continues to think. The
key question is: Can you write a program for each philosopher that does what
it is supposed to do and never gets stuck?
--from <Operating Systems: Design and Implementation>
written by Andrew S. Tanenbaum
typed by foolball :-P
Programme provided by ya
: : 法一： 用公共文件，按照严格轮流执行
: : #include <stdio.h>
: : #include <stdlib.h>
: : #include <unistd.h>
: : #include <sys\type.h>
: : #define N 5
: : int i,j,t,status;
: : FILE * f;
: : char *state[N];
: : main()
: : {
: : f=fopen("/share","w+");
: : putc(j,f);
: : if (fork())
: : { if (fork())
: : { if (fork())
: : { if (fork())
: : { if (fork())
: : {waitpid(-1,*status,0);
: : fclose(f);}
: : else
: : philosophy(4);}
: : else
: : philosophy(3);}
: : else
: : philosophy(2);}
: : else
: : philosophy(1);}
: : else
: : philosophy(0);
: : }
: : void philosophy(int i)
: : {
: : state[i ="thinking";
: : printf("%d%s\n",i,"is thinking");
: : for(t=0;t<=rand()+10000;t++);
: : state[i ="hungry";
: : printf("%d%s\n",i,"is hungry");
: : for(t=0;t<=rand()+10000;t++);
: : for(;i!=j;)
: : {fseek(f,0l,0);
: : j=getc(f);}
: : state[i ="eating";
: : printf("%d%s\n",i,"is eating");
: : j=(j+1)% N
: : fseek(f,0l,0);
: : putc(j,f);
: : }
: : 法二：通过文件加锁实现
: : #include <stdio.h>
: : #include <stdlib.h>
: : #define N 4
: : FILE *f;
: : int i, status;
: : char *state[N];
: : void philosofy(int i);
: : void main()
: : {
: : if ((f=fopen("turn", "w+"))==NULL)
: : {
: : printf("Cann't open this file");
: : exit(0);
: : }
: : if (fork())
: : {
: : if(fork())
: : {
: : if(fork())
: : {
: : if(fork())
: : {
: : if(fork())
: : {
: : waitpid(-1, &status, 0);
: : fclose(f);
: : }
: : else
: : philosofy(4);
: : }
: : else
: : philosofy(3);
: : }
: : else
: : philosofy(2);
: : }
: : else
: : philosofy(1);
: : }
: : else
: : philosofy(0);
: : }//end of main
: : void philosophy(int i)
: : { int t;
: : state[i ="thinking";
: : printf("%d%s\n",i,"is thinking");
: : for(t=0;t<=rand()+10000;t++);
: : state[i ="hungry";
: : printf("%d%s\n",i,"is hungry");
: : for(t=0;t<=rand()+10000;t++);
: : while ((f=fopen("turn.lock","r"))!=NULL);
: : link ("turn","turn.lock");
: : state[i ="eating";
: : printf("%d%s\n",i," is eating");
: : for(t=1; t<=10000+rand();t++) ;
: : unlink ("turn");
: : }
