死锁问题.doc

哲学家就餐问题与死锁
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()同时申请两份资源，具体解法如下所示。
#define N 5
typedef enum{thinking, hungry, eating}status;
status state[N];
semaphore self[N];
semaphore mutex = 1;

void test(int i)
{
if((state[i] == hungry)&&
(state[(i-1)%N] != eating)&&
(state[(i+1)%N] != eating)){
state[i] = eating;
V(self[i]);
}
}

void pick_chopsticks(int i)
{
P(mutex);
state[i] = hungry;
test(i);
V(mutex);
P(self[i]);
}

void put_chopsticks(int i)
{
P(mutex);
state[i] = thinking;
test((i-1)%N);
test((i+1)%N);
V(mutex);
}

void philosopher(int i)
{
while(1){
think();
pick_chopsticks(i);
eat();
put_chopsticks(i);
}

void main
{
int i;
for(i=0;i<5;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.1 windows下的参考源程序
#include
#include
#include
#include <stdio.h>
#include
#include
#include
#define MAX_PHILOSOPHERS 5 //待测试的哲学家数
#define ZERO 48 //数字0的ASCII码
#define DELAY rand()%25

HANDLE h_mutex_chopsticks[MAX_PHILOSOPHERS]; //互斥体数组，每根筷子需要一个互斥体
int thread_number[MAX_PHILOSOPHERS]={0,1,2,3,4};

//会产生死锁的哲学家线程
int deadlock_philosopher(LPVOID data){
int philosopher_number=*(int *)(data); //哲学家编号
for(;;)
{
srand( (unsigned)time( NULL ) * ( philosopher_number+ 1) );
Sleep(DELAY);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",(ZERO+philosopher_number));
WaitForSingleObject(h_mutex_chopsticks[philosopher_number], INFINITE);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," got chopstick ",(ZERO+philosopher_number));

Sleep(DELAY/4);

printf("s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",(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," got chopstick ",(ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS));

printf("%s%c%s\n","Philosopher ",ZERO+philosopher_number," is eating.");

Sleep(DELAY);

ReleaseMutex(h_mutex_chopsticks[philosopher_number]);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," released chopstick ",ZERO+philosopher_number);
ReleaseMutex(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," released chopstick ",(ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS));

Sleep(DELAY);
} // end for

return 0;
}

//死锁时的初始化程序
void deadlock(){
int i=0;
HANDLE h_thread[MAX_PHILOSOPHERS];
printf("可能出现死锁的哲学家就餐问题\n");
for(i=0;ieThread(NULL,0,(LPTHREAD_START_ROUTINE)(deadlock_philosopher),&thread_number[i],0,NULL);
};

WaitForMultipleObjects(MAX_PHILOSOPHERS,h_thread,TRUE,-1);
}

//通过按序分配资源预防死锁的哲学家线程
int ordered_allocation_philosopher(LPVOID data){
int philosopher_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," is waiting chopstick ",(ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS));
WaitForSingleObject(hmutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS], INFINITE);
Sleep(DELAY/4);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+philosopher_number);
WaitForSingleObject(h_mutex_chopsticks[philosopher_number], INFINITE);

}
else{
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+philosopher_number);
WaitForSingleObject(h_mutex_chopsticks[philosopher_number], INFINITE);
Sleep(DELAY/4);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS);
WaitForSingleObject(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS], INFINITE);
}
printf("%s%c%s\n","Philosopher ",ZERO+philosopher_number," is eating.");

SleepDELAY);

printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is releasing chopstick ",ZERO+philosopher_number);
ReleaseMutex(h_mutex_chopsticks[philosopher_number]);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is releasing chopstick ",ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS);
ReleaseMutex(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]);

Sleep(DELAY);
} // end for

return 0;
}

//通过按序分配资源预防死锁的初始化程序
void ordered_allocation(){
int i=0;
HANDLE h_thread[MAX_PHILOSOPHERS];

printf("可能出现死锁的哲学家就餐问题\n");
for(i=0;iRS,h_thread,TRUE,-1);
}

//通过资源预分配法预防死锁的哲学家线程
int pre_alloction_philosopher(LPVOID data){
int philosopher_number=*(int *)(data);
HANDLE h_mutex_leftandright_chopsticks[2];
h_mutex_leftandright_chopsticks[0]=h_mutex_chopsticks[philosopher_number];
h_mutex_leftandright_chopsticks[1]=h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS];

for(;;)
{
srand( (unsigned)time( NULL ) * ( philosopher_number+ 1) );
Sleep(DELAY);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+philosopher_number);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS);
WaitForMultipleObjects(2, h_mutex_leftandright_chopsticks, TRUE, INFINITE);
printf("%s%c%s\n","Philosopher ",ZERO+philosopher_number," is eating.");
Sleep(DELAY);

printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is releasing chopstick ",ZERO+philosopher_number);
ReleaseMutex(h_mutex_chopsticks[philosopher_number]);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is releasing chopstick ",ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS);
ReleaseMutex(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]);

Sleep(DELAY);
} // end for

return 0;
}

//通过资源预分配法预防死锁的初始化程序
void pre_alloction(){
int i=0;
HANDLE h_thread[MAX_PHILOSOPHERS];

printf("可能出现死锁的哲学家就餐问题\n");
for(i=0;iad,TRUE,-1);
}

//主程序
int main(int argc,char *argv[]){
char select;
while(1){
printf("|-------------------------------------------------------------|\n");
printf("| 1:deadlock |\n");
printf("| 2:non_deadlock by ordered allocation |\n");
printf(" 3:non_deadlock by pre_allocation |\n");
printf("| 4:exit |\n");
printf("|--------------------------------------------------------------|\n");
printf("select a function(1~4):");
do{
select=(char)getch();
}while(select!='1'&&select!='2'&select!='3'&&select!='4');
system("cls");
switch(select){
case '1':
deadlock();
break;
case '2':
ordered_allocation();
break;
case '3':
pre_alloction();
break;
case '4':
return 0;
}
printf("\nPress any key to return to main menu.");
getch();
system("cls");
}
return 0;
}
2.3.4 测试程序

图2-2 程序主界面
图2-3 死锁情况

程序运行的主界面如图2-2所示，输入1后，可以看到屏幕输出一些提示信息后就不再更新了，程序也停止不动了，这说明发生了死锁，如图2-3所示。分析提示信息可以了解死锁的详情，即每个哲学家都得到了左边的筷子，又都在等待右边的筷子。按ctrl+c终止程序。重新运行程序，输入2或者3，可以看到屏幕一直更新提示信息，说明没有死锁发生，程序将一直运行下去，要想结束程序必须按ctrl+c。
2.4 不足与改进
该程序虽然能防止死锁，但是可能存在饿死现象，请读者改进程序使之既没有死锁，也没有饿死现象。

THANKS !!!

致力为企业和个人提供合同协议，策划案计划书，学习课件等等
打造全网一站式需求

欢迎您的下载，资料仅供参考

-可编辑修改-