利用信号量机制解决哲学家进餐问题

PAGE2成绩：成绩：课程设计报告课程名称：课程设计（UNIX程序设计）设计题目：利用信号量机制解决哲学家进餐问题姓名：专业：网络工程班级：学号：计算机科学与技术学院网络系2013年12月28日哈尔滨理工大学计算机科学与技术学院网络系实验室实验报告哈尔滨理工大学计算机科学与技术学院网络系课程设计报告设计项目：利用信号量机制解决哲学家进餐问题选题背景1965年，数学家迪杰斯特拉提出，并成为经典的IPC问题—哲学家进餐问题。该问题的简单描述如下：五个哲学家围坐在一张圆桌周围，每个哲学家面前都一盘通心粉。由于通心粉很滑，需要两把叉子才能夹住。哲学家的生活中有两种交替活动时段，吃饭（EATING）和思考（THINKING）。当一个哲学家觉得饿了时，他就试图分两次去取左手边和右手边的叉子，每次拿一把，但不分次序。如果成功拿到两把叉子，就进入吃饭状态，吃完后放下叉子继续思考。设计思路1.每个哲学家的行为活动状态为两种：进餐（EATING）和思考（THINKING）。因此创建一个有5个元素的状态数组，每个数组元素的状态值为EATING或者THINKING。2.五个哲学家围坐成一圈，每两个人中间有一个叉子，即每个哲学家的边和右边有一个叉子，但这个叉子需要和旁边的邻居竞争使用。对于每一个哲学家来说，其只有成功获得两个叉子，才能进入进餐状态。在进完餐后，需要成功放下手中的两个叉子，才能进入思考的状态。换个角度的描述就是，每个哲学家查询左右边的邻居当前状态，如果左右的邻居当前状态都为THINKING，则该哲学家可以进餐；如果左右邻居当前状态不都是THINKING，则哲学家不能进餐。因此可以为每一个哲学家设置一个信号量，来描述哲学家的活动状态。3.因为五只叉子做多只能允许两个哲学家进餐，所以可以将桌子作为一个临界资源。通过设置一个互斥信号量来限制对临界资源的访问数。4.创建两个动作函数，对应于每个哲学家的获取两把叉子和放下两把叉子的动作。而每个动作都需要对互斥信号量和哲学家信号量进行访问操作，因此创建原子操作P和原子操作V，来执行对信号量的消耗和释放操作。5.利用父进程创建五个子进程来模拟五个哲学家，在每个子进程中执行PHILOSOPHER（phi_num）函数来模拟每个哲学家进入哲学家进餐问题活动。主要问题的解决方法和关键技术1.共享状态数组问题。问题描述：因为状态数组是共享的，而每个模拟哲学家的子进程是相互独立的，有自己的地址空间，在进程之间共享使用状态数组出现问题。解决方法：父进程通过利用UNIX系统进程通信机制中共享内存机制的shmget()和shmat系统调用创建一个共享内存区，并将状态数组地址链接到进程地址空间，成功的解决了该问题。#include<stdlib.h>#defineN5#defineLEFT(i)(i+N-1)%N#defineRIGHT(i)(i+1)%N#defineTHINKING0#defineEATING1//#include"behavior_philosophy.h"voidphilosopher(int,char*,int,int,void(*)(int,int),void(*)(int,int));voidtake_forks(int,char*,int,int,void(*)(int,int),void(*)(int,int));voidput_forks(int,char*,int,int,void(*)(int,int),void(*)(int,int));voidtest(int,char*,int,void(*)(int,int));voidthink(int);voideat(int);voidP(int,int);voidV(int,int);/*哲学家动作*/voidphilosopher(inti,char*state,intsem_phiid,intsem_mutexid,void(*P)(int,int),void(*V)(int,int)){sleep(1);think(i);while(1){take_forks(i,state,sem_phiid,sem_mutexid,P,V);eat(i);put_forks(i,state,sem_phiid,sem_mutexid,P,V);think(i);}}voidtake_forks(inti,char*state,intsem_phiid,intsem_mutexid,void(*P)(int,int),void(*V)(int,int)){(*P)(sem_mutexid,0);state[i]=THINKING;test(i,state,sem_phiid,V);(*V)(sem_mutexid,0);(*P)(sem_phiid,i);}voidput_forks(inti,char*state,intsem_phiid,intsem_mutexid,void(*P)(int,int),void(*V)(int,int)){(*P)(sem_mutexid,0);state[i]=THINKING;test(LEFT(i),state,sem_phiid,V);test(RIGHT(i),state,sem_phiid,V);(*V)(sem_mutexid,0);}voidtest(inti,char*state,intsem_phiid,void(*V)(int,int)){if(state[i]==THINKING&&state[LEFT(i)]!=EATING&&state[RIGHT(i)]!=EATING){state[i]=EATING;(*V)(sem_phiid,i);}}voidthink(inti){printf("philosopher:%d>>>>>isTHINKING.\n",i);}voideat(inti){printf("I'mphilosopher:%d>>>>>isEATING.andwilleating%dseconds!\n",i,sleep(2));}/*P,V原子操作*/voidP(intsemid,intindex){structsembufsema_buffer;sema_buffer.sem_num=index;sema_buffer.sem_op=-1;sema_buffer.sem_flg=SEM_UNDO;semop(semid,&sema_buffer,1);}voidV(intsemid,intindex){structsembufsema_buf;sema_buf.sem_num=index;sema_buf.sem_op=1;sema_buf.sem_flg=SEM_UNDO;semop(semid,&sema_buf,1);}/**/intmain(){/*创建信号量操作*/intsem_phiid;sem_phiid=semget(1008,5,0666|IPC_CREAT);assert(sem_phiid>=0);unsignedshortarray[5]={0,0,0,0,0};unionsemun{intval;unsignedshort*array;}semopts;semopts.array=array;intret1=semctl(sem_phiid,0,SETALL,semopts);assert(ret1==0);intsem_mutexid;sem_mutexid=semget(0x225,1,0666|IPC_CREAT);assert(sem_mutexid>=0);semopts.val=1;intret2=semctl(sem_mutexid,0,SETVAL,semopts);assert(ret2==0);/*初始化共享内存*/intshmid;char*state;if((shmid=shmget(IPC_PRIVATE,N,0600|IPC_CREAT))==-1){semctl(sem_phiid,0,IPC_RMID,0); semctl(sem_mutexid,0,IPC_RMID,0); perror("shmgetfaild!"); exit(1);}if((state=shmat(shmid,0,0))==(char*)-1){semctl(sem_phiid,0,IPC_RMID,0); semctl(sem_mutexid,0,IPC_RMID,0); perror("shmatfaild!"); exit(1);}/**/inti,phinum;pid_tpid;for(i=0;i<5;i++){while((pid=fork())==-1); if(!pid){ phinum=i; signal(SIGINT,SIG_DFL); break; }}if(pid>0){while(wait((int*)0)==-1); semctl(sem_phiid,0,IPC_RMID,0); semctl(sem_mutexid,0,IPC_RMID,0); shmdt(state); printf("Hi,GAMEOVER!");}elsephilosopher(phinum,state,sem_phiid,sem_mutexid,P,V);}程序运行结果