一、问题描述
看上图，有五位哲学家，面前都有一个盘子，盘子左边和右边都有一根筷子，他们在吃面之前需要先拿起左边的筷子再拿起右边的筷子，有了一双筷子就可以吃面了。
二、流程
- 先拿起左手的筷子
- 然后拿起右手的筷子
- 如果筷子被人使用了，那就等别人用完
- 吃完后，把筷子放回原位
三、死锁的产生
由图可知，生动形象
四、整体代码
#include <unistd.h>
#include <pthread.h>
#include <stdlib.h>
#include <curses.h>
#include <time.h>
#include <semaphore.h>
#include <string.h>
#define MAX_PHILOSOPHERS 5
#define ZERO 48
#define DELAY (rand()%25)/1000
//为什么要转换字符串
//在使用像 printw 这样的函数打印字符串时，我们通常需要将所有内容转换为字符或字符串。如果 philosopher_number 是一个整数，直接加入字符串会造成问题，因为它会被解释为一个非字符值。
//通过将 philosopher_number 加上 ZERO，我们将数字转换为其字符表示，从而可以将其正确地嵌入到要打印的字符串中。
typedef enum {thinking,hungry,eating}status;
status state[MAX_PHILOSOPHERS];
pthread_mutex_t pre_mutex;
sem_t pre_self[MAX_PHILOSOPHERS];
pthread_mutex_t h_mutex_chopsticks[MAX_PHILOSOPHERS];
int thread_number[MAX_PHILOSOPHERS]={0,1,2,3,4};
void pre_test(int i);
void pre_pick_fork(int i);
void pre_put_fork(int i);
void* deadlock_philosopher(void* data){
int philosopher_number=*(int *)(data);
int i=0;
for(;;)
{
srand( (unsigned)time( NULL ) * ( philosopher_number+ 1) );
sleep(DELAY);
if(i>=5){
i=0;
clear();
refresh();
}
else
i++;
printw("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+philosopher_number);
refresh();
pthread_mutex_lock(&h_mutex_chopsticks[philosopher_number]);
sleep(DELAY/4);
printw("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS);
refresh();
pthread_mutex_lock(&h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]);
printw("%s%c%s\n","Philosopher ",ZERO+philosopher_number," is eating.");
refresh();
sleep(DELAY);
printw("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is releasing chopstick ",ZERO+philosopher_number);
refresh();
pthread_mutex_unlock(&h_mutex_chopsticks[philosopher_number]);
printw("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is releasing chopstick ",ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS);
refresh();
pthread_mutex_unlock(&h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]);
sleep(DELAY);
}
return 0;
}
void deadlock(){
int i=0;
pthread_t h_thread[MAX_PHILOSOPHERS];
printw("deadlock possible.\n");
refresh();
for(i=0;i<MAX_PHILOSOPHERS;i++){
pthread_mutex_init(&h_mutex_chopsticks[i],NULL);
};
for(i=0;i<MAX_PHILOSOPHERS;i++){
pthread_create(&h_thread[i],NULL,deadlock_philosopher,&thread_number[i]);
};
for(i=0;i<MAX_PHILOSOPHERS;i++){
pthread_join(h_thread[i],NULL);
}
}
void* ordered_allocation_philosopher(void* data){
int philosopher_number=*(int *)(data);
int i=0;
for(;;) //模拟哲学家不断重复的思考和就餐行为。
{
srand( (unsigned)time( NULL ) * ( philosopher_number+ 1) );
sleep(DELAY);
if(i>=5){
i=0;
clear();
refresh();
}
else //处理最后一个哲学家
i++;
if(philosopher_number==MAX_PHILOSOPHERS-1){
printw("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS);
refresh();
pthread_mutex_lock(&h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]);
//尝试获取右边的筷子 使用互斥锁 确保同时只有一个哲学家可以持有特定的筷子。如果该筷子已被其他哲学家持有，这个调用将阻塞，直到筷子可用。
sleep(DELAY/4); //模拟哲学家等待筷子的时间。
printw("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+philosopher_number);
refresh();
pthread_mutex_lock(&h_mutex_chopsticks[philosopher_number]);//尝试获取左边的筷子
}
else{
printw("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+philosopher_number);
refresh();
pthread_mutex_lock(&h_mutex_chopsticks[philosopher_number]);
sleep(DELAY/4);
printw("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS);
refresh();
pthread_mutex_lock(&h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]);
}
printw("%s%c%s\n","Philosopher ",ZERO+philosopher_number," is eating.");
refresh();
sleep(DELAY);
printw("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is releasing chopstick ",ZERO+philosopher_number);
refresh();
pthread_mutex_unlock(&h_mutex_chopsticks[philosopher_number]);
printw("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is releasing chopstick ",ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS);
refresh();
pthread_mutex_unlock(&h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]);
sleep(DELAY);
}
return 0;
}
void* ordered_allocation(){
int i=0;
pthread_t h_thread[MAX_PHILOSOPHERS];
printw("orderded allocation:deadlock impossible.\n");
refresh();
for(i=0;i<MAX_PHILOSOPHERS;i++){
pthread_mutex_init(&h_mutex_chopsticks[i],NULL);
};
for(i=0;i<MAX_PHILOSOPHERS;i++){
pthread_create(&h_thread[i],NULL,ordered_allocation_philosopher,&thread_number[i]);
};
for(i=0;i<MAX_PHILOSOPHERS;i++){
pthread_join(h_thread[i],NULL);
}
}
void* pre_allocation_philosopher(void* data){
int philosopher_number=*((int*)(data));
int i=0;
for(;;)// 模拟哲学家思考时间
{
srand( (unsigned)time( NULL ) * ( philosopher_number+ 1) ); //确保每个哲学家线程产生的随机数序列是不同的。
sleep(DELAY); //模拟了哲学家的思考时间。
if(i>=10){
i=0;
clear();
refresh();
}
else
i++;
printw("%s%c%s\n","Philosopher ",ZERO+philosopher_number," is thinking ");
refresh();
state[philosopher_number]=thinking;
pre_pick_fork(philosopher_number);
printw("%s%c%s\n","Philosopher ",ZERO+philosopher_number," is eating.");
refresh();
state[philosopher_number]=eating;
sleep(DELAY);
pre_put_fork(philosopher_number);
sleep(DELAY);
}
return 0;
}
void pre_pick_fork(int i){
pthread_mutex_lock(&pre_mutex); //使用互斥锁 保证当一个哲学家改变状态或尝试拿起筷子时，不会有其他哲学家同时进行类似的操作
state[i]=hungry;
printw("%s%c%s\n","Philosopher ",ZERO+i," is hungry. "); //ZERO+i 可能是将整数转换为对应的字符形式，用于显示。
pre_test(i); //检查哲学家 i 是否可以开始就餐。
pthread_mutex_unlock(&pre_mutex);//释放互斥锁 pre_mutex。以便其他哲学家可以进行自己的操作
sem_wait(&pre_self[i]); //控制哲学家的行为 如果哲学家 i 不能立即就餐该信号量会阻塞哲学家 i 的线程，直到哲学家 i 可以开始就餐时被唤醒
}
void pre_put_fork(int i){
pthread_mutex_lock(&pre_mutex); //使用互斥锁 pre_mutex 来保证当一个哲学家改变状态或尝试拿起筷子时，不会有其他哲学家同时进行类似的操作
state[i]=thinking;
pre_test((i-1)%MAX_PHILOSOPHERS); //会检查哲学家 i 的左右两边是否有其他哲学家正在就餐，
pre_test((i+1)%MAX_PHILOSOPHERS); //个函数会检查哲学家 i 的左右两边是否有其他哲学家正在就餐，
pthread_mutex_unlock(&pre_mutex); //释放互斥锁 pre_mutex。以便其他哲学家可以进行自己的操作
}
void pre_test(int i){
if((state[i]==hungry)
&&(state[(i-1)%MAX_PHILOSOPHERS]!=eating)
&&(state[(i+1)%MAX_PHILOSOPHERS]!=eating)){
state[i]=eating;
sem_post(&pre_self[i]);
}
}
void pre_alloction(){
int i=0;
pthread_t h_thread[MAX_PHILOSOPHERS]; //哲学家的数量
pthread_mutex_init(&pre_mutex,NULL); //初始化互斥锁 控制对共享资源的访问以避免并发问题。
printw("pre_allocation:deadlock impossible.\n");
refresh();
for(i=0;i<MAX_PHILOSOPHERS;i++){ //所有哲学家一开始都处于思考状态。
sem_init(&pre_self[i],0,0);
state[i]=thinking;
};
for(i=0;i<MAX_PHILOSOPHERS;i++){ //创建哲学家线程
pthread_create(&h_thread[i],NULL,pre_allocation_philosopher,&thread_number[i]);
};
for(i=0;i<MAX_PHILOSOPHERS;i++){
pthread_join(h_thread[i],NULL); //确保主线程会等待每个哲学家线程结束。
}
pthread_mutex_destroy(&pre_mutex); //清理并销毁互斥锁
}
int main(int argc,char *argv[]){
char select;
bool end=false;
initscr();
while(!end){
clear();
refresh();
printw("|-----------------------------------------|\n");
printw("| 1:deadlock |\n");
printw("| 2:non_deadlock by ordered allocation |\n");
printw("| 3:non_deadlock by pre_allocation |\n");
printw("| 4:exit |\n");
printw("|-----------------------------------------|\n");
printw("select a function(1~4):");
do{
select=(char)getch();
}while(select!='1'&&select!='2'&&select!='3'&&select!='4');
clear();
refresh();
switch(select){
case '1':
deadlock();
break;
case '2':
ordered_allocation();
break;
case '3':
pre_alloction();
break;
case '4':
end=true;
}
printw("\nPress any key to return to main menu.");
getch();
clear();
refresh();
}
endwin();
return 0;
}五、资源有序分配法预防死锁和预先分配法代码区别
资源有序分配法
资源有序分配法的核心思想是强制所有资源（在哲学家就餐问题中是筷子）按照一定的顺序进行分配。通常，这意味着每个哲学家首先尝试获取编号较低的筷子，然后再尝试获取编号较高的筷子。
代码实现特点:
- 有序获取筷子：哲学家首先尝试获取其左边和右边中编号较低的筷子，然后再尝试获取另一根。
- 避免循环等待：由于所有哲学家都遵循相同的顺序获取筷子，循环等待的条件被破坏，从而避免了死锁。
预先分配法
预先分配法则是指在哲学家开始就餐之前，必须一次性获取到所有需要的资源（两根筷子）。如果不能获取到全部资源，则不会开始就餐，而是释放已持有的资源。
代码实现特点:
- 原子性资源请求：哲学家在尝试就餐前会一次性请求两根筷子。如果不能同时获取到两根筷子，他们不会持有任何一根筷子。
- 避免死锁：由于哲学家要么同时持有两根筷子，要么一根也不持有，因此避免了因部分资源被持有而导致的死锁。
区别
-
资源获取策略：
- 资源有序分配法：哲学家按顺序获取单根筷子。
- 预先分配法：哲学家尝试一次性获取两根筷子。
-
实现复杂度：
- 资源有序分配法通常实现起来较为简单，因为它只需要改变获取资源的顺序。
- 预先分配法可能需要更复杂的逻辑来处理一次性获取所有资源的情况。
-
对哲学家行为的影响：
- 资源有序分配法可能导致某些哲学家更频繁地就餐（特别是那些两边筷子编号差异大的哲学家）。
- 预先分配法可能导致更多的等待，因为哲学家需要两根筷子同时可用才能开始就餐。
六、采用预先分配法预防死锁的哲学家就餐问题
在资源分配法中，系统的设计是让哲学家们不是直接尝试拿起两根筷子，而是首先请求整体资源（即两根筷子）。如果一位哲学家能同时获取到左右两根筷子，他就可以开始就餐；如果不能，则他会等待，直到这两根筷子都可用。这种方式可以防止死锁
例子： 假设有五位哲学家围坐在一张圆桌旁，编号为1到5。每位哲学家在他们右边有一根筷子，左边有另一根筷子。每位哲学家在思考结束后，会尝试拿起两根筷子。
- 哲学家1请求使用1号和2号筷子。
- 同时，哲学家3请求使用3号和4号筷子。
- 因为1号和2号筷子都可用，哲学家1可以开始就餐。
- 同时，3号和4号筷子也都可用，所以哲学家3也可以开始就餐。
- 哲学家1和3就餐完毕后，放下筷子。
- 然后，哲学家2可以请求2号和3号筷子，哲学家4可以请求4号和5号筷子。
代码如下：
void* pre_allocation_philosopher(void* data){
int philosopher_number=*((int*)(data));
int i=0;
for(;;)
{
srand( (unsigned)time( NULL ) * ( philosopher_number+ 1) );
sleep(DELAY);
if(i>=10){
i=0;
clear();
refresh();
}
else
i++;
printw("%s%c%s\n","Philosopher ",ZERO+philosopher_number," is thinking ");
refresh();
state[philosopher_number]=thinking;
pre_pick_fork(philosopher_number);
printw("%s%c%s\n","Philosopher ",ZERO+philosopher_number," is eating.");
refresh();
state[philosopher_number]=eating;
sleep(DELAY);
pre_put_fork(philosopher_number);
sleep(DELAY);
}
return 0;
}
void pre_pick_fork(int i){
pthread_mutex_lock(&pre_mutex);
state[i]=hungry;
printw("%s%c%s\n","Philosopher ",ZERO+i," is hungry. ");
pre_test(i);
pthread_mutex_unlock(&pre_mutex);
sem_wait(&pre_self[i]);
}
void pre_put_fork(int i){
pthread_mutex_lock(&pre_mutex);
state[i]=thinking;
pre_test((i-1)%MAX_PHILOSOPHERS);
pre_test((i+1)%MAX_PHILOSOPHERS);
pthread_mutex_unlock(&pre_mutex);
}
void pre_test(int i){
if((state[i]==hungry)
&&(state[(i-1)%MAX_PHILOSOPHERS]!=eating)
&&(state[(i+1)%MAX_PHILOSOPHERS]!=eating)){
state[i]=eating;
sem_post(&pre_self[i]);
}
}
void pre_alloction(){
int i=0;
pthread_t h_thread[MAX_PHILOSOPHERS];
pthread_mutex_init(&pre_mutex,NULL);
printw("pre_allocation:deadlock impossible.\n");
refresh();
for(i=0;i<MAX_PHILOSOPHERS;i++){
sem_init(&pre_self[i],0,0);
state[i]=thinking;
};
for(i=0;i<MAX_PHILOSOPHERS;i++){
pthread_create(&h_thread[i],NULL,pre_allocation_philosopher,&thread_number[i]);
};
for(i=0;i<MAX_PHILOSOPHERS;i++){
pthread_join(h_thread[i],NULL);
}
pthread_mutex_destroy(&pre_mutex);
}
代码解释
-
pre_allocation_philosopher函数：- 这是哲学家线程执行的函数。每个哲学家线程都会不断地循环执行思考、尝试拿起筷子、就餐、放下筷子的过程。
philosopher_number是哲学家的编号。- 在尝试拿起筷子之前，哲学家处于思考状态（
state[philosopher_number]=thinking）。 - 调用
pre_pick_fork函数尝试拿起筷子，然后进入就餐状态（state[philosopher_number]=eating）。 - 就餐结束后，调用
pre_put_fork放下筷子。
-
pre_pick_fork和pre_put_fork函数：pre_pick_fork函数在尝试拿起筷子之前设置哲学家的状态为饥饿（state[i]=hungry），并调用pre_test函数检查是否可以就餐。pre_put_fork函数在放下筷子后，更新哲学家的状态为思考，并通知相邻的哲学家他们可以尝试拿起筷子。
-
pre_test函数：- 此函数检查哲学家
i是否可以开始就餐。哲学家可以就餐的条件是他处于饥饿状态且两边的哲学家都没有在就餐。 - 如果条件满足，哲学家
i的状态设置为就餐，同时使用信号量sem_post(&pre_self[i])唤醒哲学家。
- 此函数检查哲学家
-
互斥锁和信号量：
- 使用
pthread_mutex_lock和pthread_mutex_unlock来确保对哲学家状态的修改是互斥的。 - 使用信号量
pre_self来控制每个哲学家的就餐行为。
- 使用
-
pre_allocation函数：- 初始化互斥锁和信号量，创建哲学家线程并启动它们。
- 在所有哲学家线程结束后，销毁互斥锁。
-
srand( (unsigned)time( NULL ) * ( philosopher_number+ 1) );- 这行代码设置了随机数生成器的种子。
srand用于初始化随机数生成器，它的参数是一个种子值。这里，种子值是当前时间（time(NULL)返回的是自1970年1月1日以来的秒数）乘以哲学家的编号（philosopher_number + 1）。这样做可以确保每个哲学家线程产生的随机数序列是不同的。
- 这行代码设置了随机数生成器的种子。
-
sleep(DELAY);- 这行代码使线程暂停一段时间，其中
DELAY是预先定义的延迟时间。这个延迟模拟了哲学家的思考时间。
- 这行代码使线程暂停一段时间，其中
-
if(i>=10){ i=0; clear(); refresh(); } else i++;- 这段代码是一个计数器，用于控制屏幕上显示的信息。当计数器
i达到10时，它会重置为0，并清除屏幕（clear()），然后刷新显示（refresh()）。如果计数器i小于10，它就简单地增加1。这可能用于限制屏幕上显示的信息数量，防止信息溢出屏幕。
- 这段代码是一个计数器，用于控制屏幕上显示的信息。当计数器
-
printw("%s%c%s\n","Philosopher ",ZERO+philosopher_number," is thinking ");printw函数类似于printf，但它是用于在屏幕上显示信息。这行代码显示哲学家的编号和他们正在思考的信息。ZERO+philosopher_number可能是将整数哲学家编号转换为字符形式，例如，如果ZERO被定义为 '0'，那么ZERO+1会是字符 '1'。
-
refresh();- 最后，
refresh()函数刷新屏幕，以便新的输出信息能够显示出来。
- 最后，
七、采用有序分配法预防死锁的哲学家就餐问题
略，上面已经提及到了
