死锁问题

哲学家就餐问题与死锁2.1设计目的理解死锁的概念，掌握死锁预防方法。死锁是进程并发执行过程中可能出现的现象，哲学家就餐问题是描述死锁的经典例子。假设有几位哲学家围坐在一张餐桌旁，桌上有吃不尽的食品，每两位哲学家之间摆放着一根筷子，筷子的个数与哲学家的数量相等，每一位哲学家要么思考，要么等待，要么拿起左右两根筷子进餐。本设计假设有五个哲学家和五根筷子，它们的编号都是从0到4。如果每位哲学家都拿起左边的筷子，就会发生死锁。为了防止死锁，可以采用资源预分配法或者资源按序分配法。资源预分配法是指进程在运行前一次性地向系统申请它所需要的全部资源，如果系统当前不能够满足进程的全部资源请求，则不分配资源,此进程暂不投入运行，如果系统当前能够满足进程的全部资源请求,则一次性地将所申请的资源全部分配给申请进程。资源按序分配法是指事先将所有资源类全排序,即赋予每一个资源类一个唯一的整数，规定进程必需按照资源编号由小到大的次序申请资源。在哲学家就餐问题中，要采用资源预分配法只需让每个哲学家同时申请左右两根筷子。要采用资源按序分配法只需规定每个哲学家先申请左右两根筷子中编号小的筷子，再申请编号大的筷子。2.2设计要求利用多线程技术编写哲学家就餐程序，使之在运行时能演示产生死锁的情况，也能演示采用死锁防止方法后不产生死锁的情况。程序要采用简单的控制台界面，运行后在屏幕上显示功能菜单，列出该程序具有的功能，供用户选择，用户选择功能后应该转到相应的处理程序。程序应该包括以下功能：（1）演示死锁现象；（2）通过资源按序分配法防止死锁；（3）通过资源预分配法防止死锁；（4）退出。2.3设计步骤2.3.1程序结构设计程序需要六个线程，主线程用于显示主菜单，接收用户的功能选择；五个哲学家线程用于模拟哲学家的活动，即不停地思考、饥饿、进食。相邻的两个哲学家线程需要共享他们中间的同一根筷子，因此对每一根筷子的使用要互斥，用互斥体数组h_mutex_chopsticks来实现。主线程创建五个哲学家线程后要等待所有哲学家结束，用线程句柄数组h_thread来表示五个线程，主线程通过等待这五个线程句柄来实现同步。该程序共有7个函数，这些函数可以分成4组。各组包含的函数及其功能如表2-1所示。组别包括函数函数功能一main()显示主菜单，接收用户的选择并执行相应的功能。二deadlock_philosopher()deadlock()演示死锁情况的哲学家线程函数初始化函数：创建五个哲学家并等待它们结束三ordered_allocation_philosopher()ordered_allocation()通过按序分配法防止死锁的哲学家线程函数初始化函数：创建五个哲学家并等待它们结束四pre_allocation_philosopher()pre_allocation()通过预先分配法防止死锁的哲学家线程函数初始化函数：创建五个哲学家并等待它们结束图2-1函数及其功能2.3.2算法设计下面给出主要函数的算法描述。（1）deadlock_philosopher函数{while(1){随机等待一段时间；提示等待左边筷子；申请左边筷子；随机等待一段时间；提示等待右边筷子；申请右边筷子；提示正在进餐；放下左边筷子；放下右边筷子；}}（2）ordered_allocation_philosopher函数{while(1){随机等待一段时间；提示等待左右两边编号较小的筷子；申请编号较小的筷子；随机等待一段时间；提示等待左右两边编号较大的筷子；申请编号较大的筷子；提示正在进餐；放下编号较小的筷子；放下编号较大的筷子；}}（3）pre_allocation_philosopher函数{while(1){提示等待左边筷子；提示等待右边筷子；同时申请左边和右边两根筷子；提示正在进餐；随机等待一段时间；放下左边筷子；放下右边筷子；}}（4）deadlock函数{为每根筷子创建一个互斥信号量；创建五个可能产生死锁的哲学家线程；等待五个哲学家线程结束；}其他的初始化函数与deadlock()的算法相同，只不过在创建线程时使用不同的线程函数。在windows中可以用系统调用WaitForMultipleObjects()同时申请两份资源，具体解法如下所示。#defineN5typedefenum{thinking,hungry,eating}status;statusstate[N];semaphoreself[N];semaphoremutex=1;voidtest(inti){if((state[i]==hungry)&&(state[(i-1)%N]!=eating)&&(state[(i+1)%N]!=eating)){state[i]=eating;V(self[i]);}}voidpick_chopsticks(inti){P(mutex);state[i]=hungry;test(i);V(mutex);P(self[i]);}voidput_chopsticks(inti){P(mutex);state[i]=thinking;test((i-1)%N);test((i+1)%N);V(mutex);}voidphilosopher(inti){while(1){think();pick_chopsticks(i);eat();put_chopsticks(i);}voidmain{inti;for(i=0;i5;i++){state[i]=thingking;self[i].value=0;}}在上述程序中,自定义数据类型status用来枚举哲学家的状态，数组state用来存放五个哲学家的状态，由于该数组是全局变量，所以用信号灯变量mutex实现对它的互斥访问。信号量数组self包含五个元素，每个元素的初始值皆为0，当第i号哲学家不具备进食条件时，会将自己阻塞在信号量self[i]上。函数test用于测试i号哲学家是否具备进食的条件。i号哲学家可以进食必须同时满足以下条件：i号哲学家饥饿，左边哲学家不在进食，右边哲学家不在进食。2.3.3参考源代码2.3.3.1windows下的参考源程序#includewindows.h#includeconio.h#includestdlib.h#includestdio.h#includetime.h#includeio.h#includestring.h#defineMAX_PHILOSOPHERS5//待测试的哲学家数#defineZERO48//数字0的ASCII码#defineDELAYrand()%25HANDLEh_mutex_chopsticks[MAX_PHILOSOPHERS];//互斥体数组，每根筷子需要一个互斥体intthread_number[MAX_PHILOSOPHERS]={0,1,2,3,4};//会产生死锁的哲学家线程intdeadlock_philosopher(LPVOIDdata){intphilosopher_number=*(int*)(data);//哲学家编号for(;;){srand((unsigned)time(NULL)*(philosopher_number+1));Sleep(DELAY);printf(%s%c%s%c\n,Philosopher,ZERO+philosopher_number,iswaitingchopstick,(ZERO+philosopher_number));WaitForSingleObject(h_mutex_chopsticks[philosopher_number],INFINITE);printf(%s%c%s%c\n,Philosopher,ZERO+philosopher_number,gotchopstick,(ZERO+philosopher_number));Sleep(DELAY/4);printf(%s%c%s%c\n,Philosopher,ZERO+philosopher_number,iswaitingchopstick,(ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS));WaitForSingleObject(h_mutex_chopsticks[((1+philosopher_number)%MAX_PHILOSOPHERS)],INFINITE);printf(%s%c%s%c\n,Philosopher,ZERO+philosopher_number,gotchopstick,(ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS));printf(%s%c%s\n,Philosopher,ZERO+philosopher_number,iseating.);Sleep(DELAY);ReleaseMutex(h_mutex_chopsticks[philosopher_number]);printf(%s%c%s%c\n,Philosopher,ZERO+philosopher_number,releasedchopstick,ZERO+philosopher_number);ReleaseMutex(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]);printf(%s%c%s%c\n,Philosopher,ZERO+philosopher_number,releasedchopstick,(ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS));Sleep(DELAY);}//endforreturn0;}//死锁时的初始化程序voiddeadlock(){inti=0;HANDLEh_thread[MAX_PHILOSOPHERS];printf(可能出现死锁的哲学家就餐问题\n);for(i=0;iMAX_PHILOSOPHERS;i++){h_mutex_chopsticks[i]=CreateMutex(NULL,FALSE,NULL);};for(i=0;iMAX_PHILOSOPHERS;i++){h_thread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(deadlock_philosopher),&thread_number[i],0,NULL);};WaitForMultipleObjects(MAX_PHILOSOPHERS,h_thread,TRUE,-1);}//通过按序分配资源预防死锁的哲学家线程intordered_allocation_philosopher(LPVOIDdata){intphilosopher_number=*(int*)(data);for(;;){srand((unsigned)time(NULL)*(philosopher_number+1));Sleep(DELAY);if(philosopher_number==MAX_PHILOSOPHERS-1){printf(%s%c%s%c\n,Philosopher,ZERO+philosopher_number,iswaitingchopstick,(ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS));WaitForSingleObject(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS],INFINITE);Sleep(DELAY/4);printf(%s%c%s%c\n,Philosopher,ZERO+philosopher_number,iswaitingchopstick,ZERO+philosopher_n