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

1、利用信号量机制解决哲学家进餐问题作者:日期:电金座外二文咨课程设计报告课程名称:设计题目:姓名:专业:班级:学号:课程设计UNIX程序设计利用信号量机制解决哲学家进餐问网络工程计算机科学与技术学院网络系2021年12月28日设计工程:利用信号量机制解决哲学家进餐问题一、选题背景1965年,数学家迪杰斯特拉提出,并成为经典的IPC问题一哲学家进餐问题.该问题的简单描述如下：五个哲学家围坐在一张圆桌周围,每个哲学家面前都一盘通心粉.由于通心粉很滑,需要两把义子才能夹住.哲学家的生活中有两种交替活动时段,吃饭(EATING)和思考(THINKING).当一个哲学家觉得饿了时,他就试图分两次去取左手边

2、和右手边的义子,每次拿一把,但不分次序.如果成功拿到两把义子,就进入吃饭状态,吃完后放下叉子继续思考.二、设计思路1 .每个哲学家的行为活动状态为两种：进餐(EATING)和思考(THINKING)<.因此创立一个有5个元素的状态数组,每个数组元素的状态值为EATING或者THINKINGo2 .五个哲学家围坐成一圈,每两个人中间有一个义子,即每个哲学家的边和右边有一个义子,但这个义子需要和旁边的邻居竞争使用.对于每一个哲学家来说,其只有成功获得两个义子,才能进入进餐状态.在进完餐后,需要成功放下手中的两个义子,才能进入思考的状态.换个角度的描述就是,每个哲学家查询左右边的邻居当前状态,

3、如果左右的邻居当前状态都为THINKING,那么该哲学家可以进餐；如果左右邻居当前状态不都是THINKING,那么哲学家不能进餐.因此可以为每一个哲学家设置一个信号量,来描述哲学家的活动状态.3 .由于五只又子做多只能允许两个哲学家进餐,所以可以将桌子作为一个临界资源.通过设置一个互斥信号量来限制对临界资源的访问数.4 .创立两个动作函数,对应于每个哲学家的获取两把义子和放下两把义子的动作.而每个动作都需要对互斥信号量和哲学家信号量进行访问操作,因此创立原子操作P和原子操作V,来执行对信号量的消耗和释放操作.5 .利用父进程创立五个子进程来模拟五个哲学家,在每个子进程中执行PHILOSOPHE

4、R(phi_num)函数来模拟每个哲学家进入哲学家进餐问题活动.三、主要问题的解决方法和关键技术1 .共享状态数组问题.问题描述：由于状态数组是共享的,而每个模拟哲学家的子进程是相互独立的,有自己的地址空间,在进程之间共享使用状态数组出现问题.解决方法：父进程通过利用UNIX系统进程通信机制中共享内存机制的shmget()和shmat系统调川创立一个共享内存区,并将状态数组地址链接到进程地址空间,成功的解决了该问题.2 .信号量创立及初始化问题问题描述：整个程序使用两个不同的信号量,一个是记录型信号量数组,一个是互斥信号量,并且在信号量创立初就需要对信号量进行初始化,这样才能保证接下来的子进程

5、运行时,五个子进程面对的是相同值的信号量数组.解决方法：父进程通过利用UNIX系统进程通信机制中信号量机制的semget()系统调用和semctl()系统调用,成功创立一个五元素的信号量数组和一个元素的信号量数组,并将其在初始为设计的初始值,保证了程序后续操作的正确.3 .P和V原子操作问题问题描述：在子进程中的对信号量的操作必须是原子操作P和V,而且由于在动作函数中需要调用P和V原子操作,所以必须保证P和V操作的原子性,否那么函数之间参数的传递将出现不一致.解决方法：利用UNIX系统进程通信机制中信号量机制的semop()系统调用,封装P和V操作函数,保证了函数的原子性.4 .进程创立的准确

6、时刻问题问题描述：根据设计的描述,程序是通过五个子进程来模拟五个哲学家,但对进程创建的先后顺序没有要求,乂由于进程分配到时间片是有限的,并且在创立的过程中要保证五个子进程都是统一父进程创立的,所以对于进程的创立时刻不太容易确定.解决方法：利用的UNIX系统的进程创立fork()系统调用,创立一个有五个子进程的进程扇,成功的解决创立准确时刻问题5 .哲学家动作函数编译问题问题描述：在哲学家的三个动作函数中需要对两个类型的信号量进行操作,所以不可防止的需要调用P和V原子操作.尽管在动作函数定义之前,已经声明了P和V函数.但是由于其原子性,在动作函数中直接使用P,V函数导致了严重的编译错误问题.解决

7、方法：通过在各个函数参数列表中添加需要指向将使用的P和V函数指针,并在使用时采用(*P)和(*v)形式来解除引用操作,成功的解决了编译错误问题.四、程序流程图约定：Take_forks函数动作TKFKPut_forks函数动作PTFKTest函数动作TESTTHINKING思考状态THINKEATING进餐状态EAT五、原程序清单#include<stdio.h>#include<unistd.h>#include<assert.h>#include<sys/types.h>#include<sys/ipc.h>#include<

8、;sys/sem.h>#include<assert.h>#include<sys/shm.h>#include<signal.h>#include<stdlib.h>#defineN5defineLEFT(i)(i+N-l)%NSdefineRIGHT(i)(i+l)%NSdefineTHINKING0SdefineEATING1/#include,zbehavior_philosophy.hvoidphilosopher(int,char*,int,int,void(*)(int,int),void(*)(int,int);voidta

9、ke_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(*

10、P)(int,int),void(*V)(int,int)sleep(l);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);stateEi二THINKING;test(i

11、,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);stateEi=THINKING;test(LEFT(i),state,sem-phiid,V);test(RIGHT(i),state,sem_phiid,V);(*V)(sem_mutexid,0);)voidtest(inti,char*state,

12、intsem_phiid,void(*V)(int,int)if(stateEi=THINKING&&stateLEFT(i)!=EATING&&stateRIGHT(i)!=EATING)stateEi=EATING;(*V)(sem_phiid,i);)voidthink(inti)printf(''philosopher：%d»»>isTHINKING.n,z,i);)voideat(inti)printf(/zrmphilosopher：%d»»>isEATING,andwilleati

13、ng%dseconds!nz/,i,sleep(2);)/*P,V原子操作*/voidP(intsemid,intindex)structsembufsema_buffer;semabuffer,semnum=index;sema_buffer.sem-op=-1;sema_buffer.sem_flg=SEM_UND0;semop(semid,&sema_buffer,1);)voidV(intsemid,intindex)structsembufsema-buf;semabuf.semnum=index;sema_buf.sem_op=1;sema_buf.sem_flg=SEM_

14、UND0;semop(semid,&sema_buf,1);)/*/intmain()(/*创立信号量操作*/intsem_phiid;sem_phiid=semget(1008,5,0666IPC_CREAT);assert(sem_phiid>=0);unsignedshortarray5=0,0,0,0,0;unionsemunintval;unsignedshort*array;Jsemopts;semopts.array=array;intretl=semctl(sem_phiid,0,SETALL,semopts);assert(retl=0);intsem_mute

15、xid;sem_mutexid=semget(0x225,1,0666IPC_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,0600IPC.CREAT)=-1)semctl(sem_phiid,0,IPC_RMID,0);semctl(sem_mutexid,0,IPC_RMID,0);perror(/zsh

16、mgetfaild!)；exit(l);)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(l);)/*/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)=T);

17、semctl(sem_phiid,0,IPC_RMID,0);semctl(sem_mutexid,0,IPC_RMID,0);shmdt(state);printf(z,Hi,GAMEOVER!);elsephilosopher(phinum,state,sem_phiid,sem_mutexid,P,V);六、程序运行结果截图一C643>力wen卦叫mjb堂m文件aww彩潮1孙爱Ulie»e5l一国!11mphiIosopher:3»»>isEATING.andiphilosopher:3>»»isTHIbKING.rmp

18、hiIosopher:0»»>isEATING.andiphilosopher:0»»>isTHIhKING.I*mphiIosopher:2»»>isEATING.andiphilosopher:2»»>isTHINKING.I'mphilosopherEATING.andiphilosopher:4»»>isTHINKING.rmphilosopher:1»»>isEATING.andiphiIosopher:1»&#

19、187;>isTHINKING.rmphiIosopher:3»»>i$EATING.andiphilosopher:3»»>isTHIhKING.I*mphiIosopher:0»»>isEATING.andiphilosopher:0»»>isTHIbKING.I'mphiIosopher:2»»>isEATING.andiwillwillwillwillwillwillwillwill9r0ot<§)localhast：-Ajni

20、xjxoject应用程序,philosopher:3»»>isTHIbKING.rmphiIosopher:0»»>isEATING.andiphilosopher:0>»»isTHINKING.rmphiIosopher:2»»>isEATING.andiphilosopher:2»»>isTHINKING.I'mphiIosopher:4»»>isEATING.andiphilosopher:4»»>isTHIbKING.rmphilosopher:1»»>isEATING.andiphilosopher:1»»