哲学家进餐问题解决方案

原 作者 郑天 | 发表于 | 分类于 2020级

文章目录

问题描述

  • 哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。哲学家就餐问题有时也用米饭和筷子而不是意大利面和餐叉来描述，因为很明显，吃米饭必须用两根筷子。
    哲学家从来不交谈，这就很危险，可能产生死锁，每个哲学家都拿着左手的餐叉，永远都在等右边的餐叉（或者相反）。即使没有死锁，也有可能发生资源耗尽。例如，假设规定当哲学家等待另一只餐叉超过五分钟后就放下自己手里的那一只餐叉，并且再等五分钟后进行下一次尝试。这个策略消除了死锁（系统总会进入到下一个状态），但仍然有可能发生“活锁”。如果五位哲学家在完全相同的时刻进入餐厅，并同时拿起左边的餐叉，那么这些哲学家就会等待五分钟，同时放下手中的餐叉，再等五分钟，又同时拿起这些餐叉。
    在实际的计算机问题中，缺乏餐叉可以类比为缺乏共享资源。一种常用的计算机技术是资源加锁，用来保证在某个时刻，资源只能被一个程序或一段代码访问。当一个程序想要使用的资源已经被另一个程序锁定，它就等待资源解锁。当多个程序涉及到加锁的资源时，在某些情况下就有可能发生死锁。例如，某个程序需要访问两个文件，当两个这样的程序各锁了一个文件，那它们都在等待对方解锁另一个文件，而这永远不会发生。

普通解决方法

/* 哲学家问题，一般方法会有五个哲学家同时拿走右边的筷子，从而导致死锁 */

#include<pthread.h>
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<pthread.h>


#define     N   5  //总的哲学家的数量



pthread_mutex_t  mutex;
pthread_mutex_t forks[5] = {
   PTHREAD_MUTEX_INITIALIZER};
typedef struct Cthread{
   
    pthread_t thinkerID;
    int i;
}thread;




void thinking(int id){
   
    printf("thinker %d is thinking!\n",id);
   
}

void eating(int id){
   
    printf("thinker %d is eating!\n",id);
    
}

void take_chopstick(int id){
   
    pthread_mutex_lock(&forks[(id+N-1)%5]);    //哲学家右手筷子
    pthread_mutex_lock(&forks[(id+1)%5]);      //哲学家左手筷子
    printf("the thinker %d take_chopsticks\n",id);
    return;
}


void put_downcps(int id){
   
    printf("the thinker %d put_downcps\n",id);
    pthread_mutex_unlock(&forks[(id+N-1)%5]);
    pthread_mutex_unlock(&forks[(id+1)%5]);
    return;
}

void  *thinker_work(void * arg){
   
    thread *id = (thread*)arg;
    
    printf("thinker init[%d]\n",id->i);
    while(1){
   
        thinking(id->i);
        //pthread_mutex_lock(&mutex);    //在这里添加互斥锁后，线程将一个一个进行工作，不会有多个线程同时取筷子而阻塞该进程，有效防止了死锁，但是其效率较低
        take_chopstick(id->i);
        //pthread_mutex_unlock(&mutex);
        eating(id->i);
        put_downcps(id->i);
    }  

}

int main(void){
   

    thread *th = (thread *)malloc(5*sizeof(thread));

    
    for(int i = 0;i < 5; i++){
   
    th[i].thinkerID = 0;
    th[i].i = i;
    }
    for(int i = 0;i < 5;i++){
   
    if(pthread_create(&(th[i].thinkerID),NULL,thinker_work,&th[i]) < 0)
      printf("created pthread failed\n");
    }
    for(int i = 0;i< 5;i++){
   
    pthread_join((th[i].thinkerID),NULL);
    }
    
    
    return 0;
}

方法一：单个执行

/* 哲学家问题，一般方法会有五个哲学家同时拿走右边的筷子，从而导致死锁
解决方案一：重新定义一个锁，在取筷子时加锁，这样取筷子的人数只有一个人，可以防止多个线程同时取筷而导致的死锁*/

#include<pthread.h>
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<pthread.h>


#define     N   5  //总的哲学家的数量



pthread_mutex_t  mutex;
pthread_mutex_t forks[5] = {
   PTHREAD_MUTEX_INITIALIZER};
typedef struct Cthread{
   
    pthread_t thinkerID;
    int i;
}thread;




void thinking(int id){
   
    printf("thinker %d is thinking!\n",id);
   
}

void eating(int id){
   
    printf("thinker %d is eating!\n",id);
    
}

void take_chopstick(int id){
   
    pthread_mutex_lock(&forks[(id+N-1)%5]);    //哲学家右手筷子
    pthread_mutex_lock(&forks[(id+1)%5]);      //哲学家左手筷子
    printf("the thinker %d take_chopsticks\n",id);
    return;
}


void put_downcps(int id){
   
    printf("the thinker %d put_downcps\n",id);
    pthread_mutex_unlock(&forks[(id+N-1)%5]);
    pthread_mutex_unlock(&forks[(id+1)%5]);
    return;
}

void  *thinker_work(void * arg){
   
    thread *id = (thread*)arg;
    
    printf("thinker init[%d]\n",id->i);
    while(1){
   
        thinking(id->i);
        pthread_mutex_lock(&mutex);    //在这里添加互斥锁后，线程将一个一个进行工作，不会有多个线程同时取筷子而阻塞该进程，有效防止了死锁，但是其效率较低
        take_chopstick(id->i);
        pthread_mutex_unlock(&mutex);
        eating(id->i);
        put_downcps(id->i);
    }  

}

int main(void){
   

    thread *th = (thread *)malloc(5*sizeof(thread));

    
    for(int i = 0;i < 5; i++){
   
    th[i].thinkerID = 0;
    th[i].i = i;
    }
    for(int i = 0;i < 5;i++){
   
    if(pthread_create(&(th[i].thinkerID),NULL,thinker_work,&th[i]) < 0)
      printf("created pthread failed\n");
    }
    for(int i = 0;i< 5;i++){
   
    pthread_join((th[i].thinkerID),NULL);
    }
    
    
    return 0;
}

方法二：利用信号量控制线程数量

/* 哲学家问题，一般方法会有五个哲学家同时拿走右边的筷子，从而导致死锁
解决方案四：利用信号量来进行对线程数的控制*/
#include<semaphore.h>
#include<pthread.h>
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<pthread.h>


#define     N   5  //总的哲学家的数量;
sem_t      sem ;
pthread_mutex_t  mutex;
pthread_mutex_t forks[5] = {
   PTHREAD_MUTEX_INITIALIZER};
typedef struct Cthread{
   
    pthread_t thinkerID;
    int i;
}thread;




void thinking(int id){
   
    printf("thinker %d is thinking!\n",id);
    //sleep(2);
   
}

void eating(int id){
   
    printf("thinker %d is eating!\n",id);
    //sleep(3);
    
}

void take_chopstick(int id){
   
    pthread_mutex_lock(&forks[(id+N-1)%5]);    //哲学家右手筷子
    pthread_mutex_lock(&forks[(id+1)%5]);      //哲学家左手筷子
    printf("the thinker %d take_chopsticks\n",id);
    return;
}


void put_downcps(int id){
   
    printf("the thinker %d put_downcps\n",id);
    pthread_mutex_unlock(&forks[(id+N-1)%5]);
    sem_post(&sem);
    pthread_mutex_unlock(&forks[(id+1)%5]);

    return;
}

void  *thinker_work(void * arg){
   
    thread *id = (thread*)arg;
    
    printf("thinker init[%d]\n",id->i);
    while(1){
   
       
        thinking(id->i);
        sem_wait(&sem);                  //利用信号量来控制线程的个数
        //pthread_mutex_lock(&mutex);    //在这里添加互斥锁后，线程将一个一个进行工作，不会有多个线程同时取筷子而阻塞该进程，有效防止了死锁，但是其效率较低
        take_chopstick(id->i);
        //pthread_mutex_unlock(&mutex);
        eating(id->i);
        put_downcps(id->i);
        
    }  

}

int main(void){
   

    thread *th = (thread *)malloc(5*sizeof(thread));
    sem_init(&sem,0,4);                           //初始化信号量
    
    for(int i = 0;i < 5; i++){
   
    th[i].thinkerID = 0;
    th[i].i = i;
    }
    for(int i = 0;i < 5;i++){
   
    if(pthread_create(&(th[i].thinkerID),NULL,thinker_work,&th[i]) < 0)
      printf("created pthread failed\n");
    }
    for(int i = 0;i< 5;i++){
   
    pthread_join((th[i].thinkerID),NULL);
    }
    
    
    return 0;
}

方法三：利用回退机制进行操作

/* 哲学家拿筷子时每次都进行判断是否左手有筷子,如果左手有筷子则将其剥夺--基于回退机制解决哲学家问题 */
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<pthread.h>
#include<errno.h>

#define     N   5  //总的哲学家的数量



pthread_mutex_t  mutex;
pthread_mutex_t forks[6] = {
   PTHREAD_MUTEX_INITIALIZER};
typedef struct Cthread{
   
    pthread_t thinkerID;
    int i;
}thread;




void thinking(int id){
   
    printf("thinker %d is thinking!\n",id);
   
}

void eating(int id){
   
    printf("thinker %d is eating!\n",id);
    
}



void  *thinker_work(void * arg){
   

    thread *id = (thread*)arg;
    int left,right;
    printf("thinker init[%d]\n",id->i);
    switch(id->i)
	{
   
		case 0:
			left = 5;
			right = 1;
			break;
		case 1:
			left = 1;
			right = 2;
			break;
		case 2:
			left = 2;
			right = 3;
			break;
		case 3:
			left = 3;
			right = 4;
			break;
		case 4:
			left = 4;
			right = 5;
			break;
		default:
			break;
	}



    while(1){
   
        thinking(id->i);
        sleep(2);   //这里等待了两秒，所有线程都会创建好在这里睡眠
        pthread_mutex_lock(&forks[right]); //右手取到筷子
        printf("thinker %d carry the  right chopstick\n",id->i);


        if(pthread_mutex_trylock(&forks[left]) == EBUSY){
   


            pthread_mutex_unlock(&forks[right]);
            printf("unluckly ...\n");
            continue;
        }


            //pthread_mutex_lock(&forks[left]);
            printf("thinker %d carry chopstick %d\n",id->i,left);
		    eating(id->i);
		    sleep(2);  //吃饭
		
		    pthread_mutex_unlock(&forks[right]);  //放下右边的筷子
		    printf("thinker %d release the chopstick %d\n",id->i,right);
		    pthread_mutex_unlock(&forks[left]);  //放下左边的筷子
		    printf("thinker %d release the chopstick %d\n",id->i,left);

    }
}

int main(void){
   

    thread *th = (thread *)malloc(5*sizeof(thread));
   
    
    for(int i = 0;i < 5; i++){
   
    th[i].thinkerID = 0;
    th[i].i = i;
    }
    for(int i = 0;i < 5;i++){
   
    if(pthread_create(&(th[i].thinkerID),NULL,thinker_work,&th[i]) < 0)
      printf("created pthread failed\n");
    }
    for(int i = 0;i< 5;i++){
   
    pthread_join((th[i].thinkerID),NULL);
    }
    return 0;
}

方法四：对哲学家进行信号标记

/* 简化方案，不对筷子进行标记，而是对哲学家进行信号标记 */
#include <pthread.h>
#include <stdio.h>
#include<stdlib.h>
#include<unistd.h>


#define N 5
#define LEFT (signo+N-1)%N
#define RIGHT (signo+1)%N
#define THINK_TIME 2
#define EAT_TIME 1

enum {
   EATING,HUNNGRY,THINKING} state[N];//用枚举对哲学家的状态进行初始化

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER,thinker[N];

/* 这里对每个哲学家的左右都进行检测，如果左右两边哲学家都处于EATING状态，则自身放弃eating（解锁） */
void test(int signo){
   
    printf("the thinker %d is trying to take the chopsticks\n",signo);
    if(state[signo] == HUNNGRY  &&
       state[LEFT]  != EATING   &&
       state[RIGHT] != EATING     ){
   
           state[signo] = EATING;
           pthread_mutex_unlock(&thinker[signo]);
       }
}


void take_chopsticks(int signo){
   
    pthread_mutex_lock(&mutex);
    state[signo]= HUNNGRY;
    test(signo);
    pthread_mutex_unlock(&mutex);
    pthread_mutex_lock(&thinker[signo]);
}


void put_chopsticks(int signo){
   
    pthread_mutex_lock(&mutex);
    state[signo]= THINKING;
    test(LEFT);
    test(RIGHT);
    pthread_mutex_unlock(&mutex);
}

void think(int signo){
   
    printf("the think %d is thinking\n",signo);
    sleep(THINK_TIME);
}

void eating(int signo){
   
    printf("the think %d is eating\n",signo);
    sleep(EAT_TIME);
}

void *work(void * argc){
   
    int i = *(int *)argc;
    while(1){
   
        think(i);
        take_chopsticks(i);
        eating(i);
        put_chopsticks(i);
    }
}



int main(void){
   
    pthread_t th[N] = {
   0};
    for(int i = 0;i < 5; i++)
        pthread_create(&th[i],NULL,work,(void*)(&i));
    for(int i = 0;i < 5; i++)
        pthread_join(th[i],NULL);
    return 0;
}

方法五：规定先例来防止死锁

/* 规定一个先例，偶数哲学家先左后右，奇数哲学家先右后左,这样总能保证一个哲学家先拿到筷子吃完，不会造成阻塞死锁 */
#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<unistd.h>

#define   N    5

pthread_mutex_t chopsticks[N] = {
   PTHREAD_MUTEX_INITIALIZER};

void eat(int i){
   
    printf("thinker %d eat eat eat\n",i);
    //sleep(2);
}




void *work(void *argc){
   
    int i = *(int*)argc;
    int left = i;
    int right = (i+1)%N;
    while (1) {
   
        printf("哲学家%d正在思考问题\n", i);
        //sleep(2);

        printf("哲学家%d饿了\n", i);
        if (i % 2 == 0) {
   //偶数哲学家，先右后左
            pthread_mutex_lock(&chopsticks[right]);
            pthread_mutex_lock(&chopsticks[left]);
            eat(i);
            pthread_mutex_unlock(&chopsticks[left]);
            pthread_mutex_unlock(&chopsticks[right]);
        } else {
   //奇数哲学家，先左后又
            pthread_mutex_lock(&chopsticks[left]);
            pthread_mutex_lock(&chopsticks[right]);
            eat(i);
            pthread_mutex_unlock(&chopsticks[right]);
            pthread_mutex_unlock(&chopsticks[left]);
        }
    }
}




int main(){
   
    pthread_t threadID[N];
    for(int i = 0;i < 5;i++)
    pthread_create(&threadID[i],NULL,work,(void *)(&i));
    for(int i = 0;i<5;i++)
    pthread_join(threadID[i],NULL);
}