一、实验目的：

（1）实现哲学家就餐问题，要求不能出现死锁。

（2）通过本实验熟悉Linux系统的基本环境，了解Linux下进程和线程的实现。

二、实验原理：

（1）问题描述：五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取其左右最靠近它的筷子，只有他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。

（2）拿起筷子和放下筷子的操作如何实现：筷子是临界资源，拿起筷子操作就哲学家（不同任务）之间是对临界资源的互斥访问，放下筷子就是对临界资源的释放，在Linux中可以通过多种机制来实现：

1）互斥量（加锁，解锁），适用于线程

2）POSIX信号量（P操作，V操作），无名信号量适用于线程，命名信号量适用于进程/线程

3）XSI信号量集（P操作，V操作），同时适用于进程与线程

（3）预防死锁的实现方法:破坏“循环等待条件”，对哲学家编号，奇偶号哲学家拿起筷子的顺序不同。规定：奇数编号哲学家先拿左边筷子再拿右边筷子，偶数编号哲学家先拿右边筷子再拿左边筷子。

（4）避免死锁的实现方法：再创建一个任务，哲学家拿起筷子时向该任务发起申请，由该任务对当前筷子的分配情况进行判断，判定系统是否由安全状态向不安全状态转换，从而允许或拒绝该次申请

三、实验内容：

（1）在linux系统下实现教材2.5.2节中所描述的哲学家就餐问题。要求显示出每个哲学家的工作状态，如吃饭，思考。连续运行30次以上都未出现死锁现象。

（2）熟悉Ubuntu系统下的多线程编程。

1）使用“Ctrl+Alt+T”打开终端；

2）使用gedit或vim命令打开文本编辑器进行编码 “gedit 文件名.c”

3）编译程序： “gcc 文件名.c -o 可执行程序名”（如果只输入gcc 文件名.c，默认生成可执行程序名为a.out）使用线程库时，gcc编译需要添加-lpthread

4）执行程序：./可执行程序名

四、实验器材（设备、元器件）：

1. 学生每人一台PC，安装Windows8操作系统。
2. 个人PC安装VMware虚拟机和Ubuntu系统。

五、实验步骤：

（1）在Ubuntu系统中使用“Ctrl+Alt+T”打开终端；

（2）使用vim命令打开文本编辑器进行编码 “vim lab1.c”

（3）编写lab.c源程序实现哲学家就餐问题

（4）编译程序：“gcc lab1.c -o test”

（5）执行程序：./test

六、具体代码

        为解决哲学家就餐问题中出现死锁的情况，从0开始依次对每个哲学家进行编号，并规定：奇数编号哲学家先拿左边筷子再拿右边筷子，偶数编号哲学家先拿右边筷子再拿左边筷子，这样就不会出现死锁现象了，奇偶编号预防死锁发生代码如下所示：

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include <unistd.h>
// 利用互斥量实现哲学家就餐问题
//规定奇数哲学家先拿左边筷子再拿右边筷子，偶数哲学家先拿右边筷子再拿左边筷子
pthread_mutex_t chopstick[5]; // 定义互斥量
void *func(void*);// 线程函数
void init();
int main(){
	init();//初始化互斥量 
	pthread_t p1,p2,p3,p4,p5; // 定义哲学家
	pthread_create(&p1,NULL,func,"0");
	pthread_create(&p2,NULL,func,"1");
    pthread_create(&p3,NULL,func,"2");
	pthread_create(&p4,NULL,func,"3");
	pthread_create(&p5,NULL,func,"4");
    pthread_join(p1,NULL);
	pthread_join(p2,NULL);
	pthread_join(p3,NULL);
	pthread_join(p4,NULL);
	pthread_join(p5,NULL);
	return 0;
} 
void init(){
	int i = 0;
	for(;i < 5; i++){
		chopstick[i] = (pthread_mutex_t)PTHREAD_MUTEX_INITIALIZER;
	}
}
void *func(void *arg){
	int i = 0;
    int num = atoi((char *)arg);
	do{
		printf("哲学家%d正在思考\n",num + 1);
		sleep(1);
        if(num % 2 == 0){ //偶数哲学家
            pthread_mutex_lock(&chopstick[(num + 1) % 5]);
		    pthread_mutex_lock(&chopstick[num]);
			printf("哲学家%d正在就餐\n",num + 1);
			sleep(1);
			pthread_mutex_unlock(&chopstick[(num + 1) % 5]);
			pthread_mutex_unlock(&chopstick[num]);
        } else{ //奇数哲学家
            pthread_mutex_lock(&chopstick[num]);
		    pthread_mutex_lock(&chopstick[(num + 1) % 5]);
			printf("哲学家%d正在就餐\n",num + 1);
			sleep(1);
			pthread_mutex_unlock(&chopstick[num]);
			pthread_mutex_unlock(&chopstick[(num + 1) % 5]);
        }
		
		i++;
	} while(i < 30);
} 

七、总结及心得体会：

        通过本次实验，我熟悉了Linux系统的基本环境，了解了如何在Linux下实现线程的创建、终止以及互斥量的初始化、上锁、解锁、销毁。同时也能够利用Linux的线程、互斥量机制实现哲学家就餐问题，并且知道了如何能够是程序不出现死锁现象。

八、对本实验过程及方法、手段的改进建议：

        本实验也可使用破坏“请求和保持条件”的方法来使得程序不出现死锁，即哲学家如果无法同时拿起两支筷子，则放下已经拿起的筷子，等待一段时间再尝试，利用POSIX API中的非阻塞操作pthread_mutex_trylock实现对能否拿起筷子的判断。相较于为每个哲学家编号，上述方法更容易理解与实现，破坏请求和保持条件预防死锁代码如下所示：

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include <unistd.h>
// 利用互斥量实现哲学家就餐问题
pthread_mutex_t chopstick[5]; // 定义互斥量
void *philosopher1(void);// 哲学家1 
void *philosopher2(void);// 哲学家2 
void *philosopher3(void);// 哲学家3 
void *philosopher4(void);// 哲学家4 
void *philosopher5(void);// 哲学家5 
void init();

int main(){
	init();//初始化互斥量 
	pthread_t p1,p2,p3,p4,p5;
	pthread_create(&p1,NULL,(void*)philosopher1,NULL);
	pthread_create(&p2,NULL,(void*)philosopher2,NULL);
	pthread_create(&p3,NULL,(void*)philosopher3,NULL);
	pthread_create(&p4,NULL,(void*)philosopher4,NULL);
	pthread_create(&p5,NULL,(void*)philosopher5,NULL);
	pthread_join(p1,NULL);
	pthread_join(p2,NULL);
	pthread_join(p3,NULL);
	pthread_join(p4,NULL);
	pthread_join(p5,NULL);
} 

void init(){
	int i = 0;
	for(;i < 5; i++){
		chopstick[i] = (pthread_mutex_t)PTHREAD_MUTEX_INITIALIZER;
	}
}

void *philosopher1(void){
	int i = 0;
	do{
		printf("哲学家1正在思考\n");
		sleep(1);
		pthread_mutex_trylock(&chopstick[0]);
		if(pthread_mutex_trylock(&chopstick[1]) != 0){
			pthread_mutex_unlock(&chopstick[0]);
			continue;
		}
		printf("哲学家1正在就餐\n");
		sleep(1);
		pthread_mutex_unlock(&chopstick[0]);
		pthread_mutex_unlock(&chopstick[1]);
		i++;
	} while(i < 30);
} 
void *philosopher2(void){
	int i = 0;
	do{
		printf("哲学家2正在思考\n");
		sleep(1);
		pthread_mutex_trylock(&chopstick[1]);
		if(pthread_mutex_trylock(&chopstick[2]) != 0){
			pthread_mutex_unlock(&chopstick[1]);
			continue;
		}
		printf("哲学家2正在就餐\n");
		sleep(1);
		pthread_mutex_unlock(&chopstick[1]);
		pthread_mutex_unlock(&chopstick[2]);
		i++;
	} while(i < 30);
}
void *philosopher3(void){
	int i = 0;
	do{
		printf("哲学家3正在思考\n");
		sleep(1);
		pthread_mutex_trylock(&chopstick[2]);
		if(pthread_mutex_trylock(&chopstick[3]) != 0){
			pthread_mutex_unlock(&chopstick[2]);
			continue;
		}
		printf("哲学家3正在就餐\n");
		sleep(1);
		pthread_mutex_unlock(&chopstick[2]);
		pthread_mutex_unlock(&chopstick[3]);
		i++;
	} while(i < 30);
}
void *philosopher4(void){
	int i = 0;
	do{
		printf("哲学家4正在思考\n");
		sleep(1);
		pthread_mutex_trylock(&chopstick[3]);
		if(pthread_mutex_trylock(&chopstick[4]) != 0){
			pthread_mutex_unlock(&chopstick[3]);
			continue;
		}
		printf("哲学家4正在就餐\n");
		sleep(1);
		pthread_mutex_unlock(&chopstick[3]);
		pthread_mutex_unlock(&chopstick[4]);
		i++;
	} while(i < 30);
}
void *philosopher5(void){
	int i = 0;
	do{
		printf("哲学家5正在思考\n");
		sleep(1);
		pthread_mutex_trylock(&chopstick[4]);
		if(pthread_mutex_trylock(&chopstick[0]) != 0){
			pthread_mutex_unlock(&chopstick[4]);
			continue;
		}
		printf("哲学家5正在就餐\n");
		sleep(1);
		pthread_mutex_unlock(&chopstick[4]);
		pthread_mutex_unlock(&chopstick[0]);
		i++;
	} while(i < 30);
}