首页 > 代码库 > 哲学家进餐问题解析

哲学家进餐问题解析

2024-07-07 07:45:19   232人阅读

这篇文章将给出POSIX的pthread实现，c++11的thread库的实现方式。部分源码内容可能摘抄自他人博客，表示此篇文章非绝对原创，感谢。

 

1. 问题描述

场景：5个哲学家，5把叉子，5盘意大利面（意大利面很滑，需要两把叉子才能拿起）大家围绕桌子，进行思考与进食的活到，如下图所示。

哲学家的活动方式为：要么放下左右手刀叉进行思考，要么拿起刀叉开始吃饭（刀叉拿起时，必须拿两把，而且只能左右手依次拿，先左手拿左边，后右手拿右边，或者先右手拿右边，左边拿左边）。其只有这两种交替状态。

哲学家们面临的问题为：如何安排哲学家们一致的行动逻辑，保证他们至少有人且尽可能两个人能同时拿到两把叉子开始吃饭，而不会发生“死锁”，“饥饿”，“干等”的状态。需要注意的是，大家想吃饭的时机是随机的，想思考的时机也是随机的，这个不受控制，不可能由“你”来安排哲学家们哪几个先吃，哪几个后吃，他们不受你控制，但你要赋予他们一种性格，或者说思考方式，保证他们自主的思考，自主的解决问题。

  • 死锁：大家都同时想吃饭，结果同时拿起左手边叉子，发现同时右边没有叉子，然后各怀私心，僵持者希望有人能放下他左手边叉子，然后抢夺之，开始吃意大利面，结果大家都没放。。。
  • 饥饿：大家都同时想吃饭，结果同时拿起左手边叉子，发现同时右边没有叉子，然后都很慷慨，结果大家同时放下左手边叉子，然后大家发现有叉子了，又同时开始拿起左手边叉子，又同时放下，如此反复。。。
  • 干等：假设想拿叉子这个想法的产生是一个“原子”操作，即不可同时发生，不可中断，然后一旦有人想拿，就进化为X教授，然后用能力控制了其他人处于僵化状态，然后开始独享，独享完后放下叉子想思考了，立即丧失超能力，于是其余四人回归正常，然后5人中再次有人想拿叉子，进化为教授，周而复始。但是这样，尼玛一个人吃，其余四个干看着啊。。怎么说也有5把叉子，5盘意大利面，至多可以两个人同时吃的。

 

2. 解决方法

1）服务生解法

2）资源分级解法

3）Chandy/Misra解法

　　

3.Posix的pthread实现

pthreadc()为主函数。

 1 #include <stdio.h>
 2 #include <semaphore.h>
 3 #include <pthread.h>
 4 #include <unistd.h>
 5 
 6 //宏定义信号量个数为5,宏定义0表示思考,宏定义1表示饿,宏定义2表示吃,宏定义(ph_num+4)%N表示左,宏定义(ph_num+1)%N表示右
 7 #define N 5
 8 #define THINKING 0
 9 #define HUNGRY 1
10 #define EATING 2
11 #define LEFT (ph_num+4)%N
12 #define RIGHT (ph_num+1)%N
13 
14  //声明操作函数,取叉函数,放叉函数,测试函数
15 void* philospher(void *num);
16 void takeFork(int);
17 void putFork(int);
18 void test(int);
19 int pthreadc();
20 
21 //声明互斥锁 ,声明数组
22 sem_t mutex;
23 sem_t S[N];
24 
25 int state[N];//定义整型数组
26 int phil_num[N] = { 0, 1, 2, 3, 4 };//初始化数组
27 
28 int pthreadc()
29 {
30     int i;
31     pthread_t thread_id[N];//声明线程ID数组
32     sem_init(&mutex, 0, 1);//初使化信号量的状态为1，并且信号量在一个进程的线程间进行共享
33 
34     for (i = 0; i<N; i++)//初始化s数组
35         sem_init(&S[i], 0, 0);//初始化S[i]的值为零
36 
37     for (i = 0; i<N; i++)
38     {
39         pthread_create(&thread_id[i], NULL, philospher, &phil_num[i]);//创建哲学家线程函数
40         printf("Philosopher %d is ready to grab folks\n", i + 1);
41     }
42 
43     for (i = 0; i<N; i++)
44         pthread_join(thread_id[i], NULL);//等待thread_id[i]线程结束
45 }
46 
47 
48 void* philospher(void *num)
49 {
50     while (1)
51     {
52         int *i = (int*)num;
53         sleep(1);//调整频率
54         takeFork(*i);//申请叉子
55         sleep(0);//放弃当前线程执行的时间片，把自身放到等待队列之中。
56         putFork(*i);//放下叉子
57     }
58 
59     return nullptr;
60 }
61 
62 
63 void takeFork(int ph_num)
64 {
65     sem_wait(&mutex);//给信号量的值减上一个“1”
66     state[ph_num] = HUNGRY;//初始化状态为HUNGRY（饿）
67     printf("Philosopher %d want to eat\n", ph_num + 1);
68     test(ph_num);//测试函数
69     sem_post(&mutex);//给信号量的值加上一个“1”
70     sem_wait(&S[ph_num]);//给信号量的值减上一个“1”
71     sleep(1);//调整频率
72 }
73 
74 
75 //******************能够吃就改变信号量的值和状态**********************************************
76 void test(int ph_num)
77 {    /*如果state[ph_num]状态为HUNGRY并且state[LEFT]和state[RIGHT]的状态都不等于EATING*/
78     if (state[ph_num] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING)
79     {
80         state[ph_num] = EATING;//将state[ph_num]状态置为EATING（吃饭）
81         sleep(2);//调整频率
82         printf("Philosopher %d is eating now\n", ph_num + 1);
83         sem_post(&S[ph_num]);//给信号量的值加上一个“1”
84     }
85 }
86 
87 
88 //******************************************************************************************
89 void putFork(int ph_num)
90 {
91     sem_wait(&mutex);//信号量减1
92     state[ph_num] = THINKING;//将state[ph_num]状态置为THINKING（思考）
93     printf("Philosopher %d is thinking now\n", ph_num + 1);
94     test(LEFT);
95     test(RIGHT);
96     sem_post(&mutex);//给信号量的值加上一个“1”
97 }

 

 

　　

 


联系
我们