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

.成绩：课程设计报告课程名称：课程设计（ 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 系统调用创建一个共享内存区， 并将状态数组地址链接到进程地址空间， 成功的解决了该问题。2. 信号量创建及初始化问题问题描述：整个程序使用两个不同的信号量，一个是记录型信号量数组，一个是互斥信号量，并且在信号量创建初就需要对信号量进行初始化，这样才能保证接下来的子进程运行时，五个子进程面对的是相同值的信号量数组。解决方法：父进程通过利用 unix系统进程通信机制中信号量机制的 semget（）系统调用和 semctl() 系统调用，成功创建一个五元素的信号量数组和一个元素的信号量数组，并将其在初始为设计的初始值，保证了程序后续操作的正确。3.p 和 v 原子操作问题问题描述： 在子进程中的对信号量的操作必须是原子操作p和 v，而且由于在动作函数中需要调用p 和 v 原子操作，所以必须保证p 和 v 操作的原子性，否则函数之间参数的传递将出现不一致。解决方法：利用unix系统进程通信机制中信号量机制的semop（）系统调用，封装p 和 v 操作函数，保证了函数的原子性。4. 进程创建的准确时刻问题问题描述：根据设计的描述，程序是通过五个子进程来模拟五个哲学家，但对进程创建的先后顺序没有要求，又由于进程分配到时间片是有限的，并且在创建的过程中要保证五个子进程都是统一父进程创建的，所以对于进程的创建时刻不太容易确定。解决方法：利用的 unix系统的进程创建 fork （）系统调用，创建一个有五个子进程的进程扇，成功的解决创建准确时刻问题5. 哲学家动作函数编译问题问题描述：在哲学家的三个动作函数中需要对两个类型的信号量进行操作，所以不可避免的需要调用p和 v 原子操作。尽管在动作函数定义之前，已经声明了p和 v函数。但是由于其原子性，在动作函数中直接使用p，v 函数导致了严重的编译错误问题。解决方法：通过在各个函数参数列表中添加需要指向将使用的p 和 v 函数指针，并在使用时采用（ *p）和（ *v）形式来解除引用操作，成功的解决了编译错误问题。四、 程序流程图约定：take_forksput_forks函数动作函数动作tkfkptfktest函数动作testthinking思考状态thinkeating进餐状态eatthinkntkfk？yntest ？yeatynptfk？五、 原程序清单#include #include #include #include #include #include #include #include #include #include#define n5#define left(i)(i+n-1)%n#define right(i)(i+1)%n #define thinking0#define eating1/#includebehavior_philosophy.hvoidphilosopher(int,char*,int, int,void(*)(int,int),void(*)(int,int); void take_forks(int , char* , int , int ,void (*)(int, int), void (*)(int, int);void put_forks(int , char* , int , int ,void (*)(int, int), void (*)(int, int);void test(int , char* , int ,void (*)(int, int); void think(int );void eat(int ); void p(int , int ); void v(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); statei = thinking; test(i, state, sem_phiid, v); (*v)(sem_mutexid, 0);(*p)(sem_phiid, i);void put_forks(int i, char* state, int sem_phiid, int sem_mutexid,void (*p)(int, int), void (*v)(int, int)(*p)(sem_mutexid, 0);statei = thinking;test(left(i), state, sem_phiid, v); test(right(i), state, sem_phiid, v);(*v)(sem_mutexid, 0);void test(int i, char* state, int sem_phiid,void (*v)(int, int)if(statei=thinking&stateleft(i)!=eating& stateright(i)!=eating)statei = eating;(*v)(sem_phiid, i);void think(int i)printf(philosopher:%dis thinking.n, i);void eat(int i)printf(im philosopher:%dis eating.and will eating %d seconds!n, i, sleep(2);/*-p,v原子操作*/void p(int semid, int index)struct sembuf sema_buffer; sema_buffer.sem_num = index; sema_buffer.sem_op= -1; sema_buffer.sem_flg = sem_undo; semop(semid, &sema_buffer, 1);void v(int semid, int index) struct sembuf sema_buf; sema_buf.sem_num = index; sema_buf.sem_op= 1;sema_buf.sem_flg = sem_undo; semop(semid, &sema_buf, 1);/*-*/int main( )/*-创建信号量操作*/int sem_phiid;sem_phiid = semget(1008, 5, 0666|ipc_creat); assert(sem_phiid=0);unsigned short array5 = 0, 0, 0, 0, 0; union semunint val;unsigned short *array;semopts; semopts.array=array;int ret1 = semctl(sem_phiid, 0, setall, semopts); assert(ret1 = 0);int sem_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);/*-初始化共享内存*/int shmid; 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(shmget faild!); 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(shmat faild!);exit(1);/*-*/int i, phinum; pid_t pid; for(i=0; i0)while(wait(int *)0) = -1); semctl(sem_phiid, 0, ipc_rmid, 0);semctl(sem_mutexid, 0, ipc_rmid, 0); shmdt(state);printf(hi, game over!);elseph