使用RTX5 信号量解决哲学家就餐问题

weiyuliang · 发表于 2020-2-25 21:01:06

1965 年，Dijkstra 提出并解决了一个他称之为哲学家就餐的同步问题。从那时起，每个发明新的同步原语的人都希望通过解决哲学家就餐问题来
展示其同步原语的精妙之处。这个问题可以简单地描述如下：五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一盘通心粉。由于通心粉很滑，
所以需要两把叉子才能夹住。相邻两个盘子之间放有一把叉子，餐桌如图 1 示。
QQ图片20200225205642.png

哲学家的生活中有两种交替活动时段：即吃饭和思考（这只是一种抽象，即对哲学家而言其他活动都无关紧要）。
当一个哲学家觉得饿了时，他就试图分两次去取其左边和右边的叉子，每次拿一把，但不分次序。
如果成功地得到了两把叉子，就开始吃饭，吃完后放下叉子继续思考。
关键问题是：能为每一个哲学家写一段描述其行为的程序，且决不会死锁吗？

声明：以上文字和图片出自《Operating Systems Design and
Implementation》 By Andrew S. Tanenbaum。该实验是对哲学家就餐问题的模拟实现。

《Operating Systems Design and Implementation》中的哲学家就餐问题的就解决方案。

如果读者想要对这个问题进行深入的理解请参考此书 2.3.1 节。

每位哲学家一共有三种状态，分别为思考（THINKING），饥饿（HUNGRY），和进餐（EATING）。

当哲学家从思考中醒来则进入到饥饿状态，他会试图获取餐叉。当获取到两把叉子，则进入进餐状态（EATING）使用一个数组 phd_state[N]，来跟踪每位哲学家的状态，在本实验中， N 为 5。0~4 代表哲学家

一个哲学家只有当两个邻居都没有进餐是才允许进入到进餐状态。哲学家i的两个邻居由 LEFT_PHD(i)和 RIGHT_PHD(i)。

即若 i 为 2，则 LEFT_PHD 为 1，RIGHT_PHD 为 3。该程序使用了一个信号量数组，每个信号量对应一位哲学家，这样在所需的叉子被占用时，想进餐的哲学家就被阻塞。

初始化信号量数组，以及创建 5个哲学家线程。

注意，程序中哲学家状态数组的操作为临界区，需要互斥，这里使用二值信号量 sem_lock 实现（用互斥也可以）。

5 个哲学家线程具有相同的优先级和时间片。

/*
* 程序清单：哲学家就餐问题
* 参考《Operating Systems Design and Implementation》 By Andrew S. Tanenbaum
*/
#include "includes.h"
#define N 5 /* 定义哲学家的数目5 */
osSemaphoreId_t sem[N]; /* 每位哲学家一个信号量 */
osSemaphoreId_t sem_lock; /* 定义二值信号量实现临界区互斥 */
/* 哲学家围绕一个圆桌 */
#define LEFT_PHD(i) ((i+N-1)%N) /* 哲学家i左边的哲学家 */
#define RIGHT_PHD(i) ((i+1)%N) /* 哲学家i右边的哲学家 */
/* 定义使用枚举类型表示哲学家状态*/
enum _phd_state
{
THINKING = 0,
HUNGRY,
EATING,
} phd_state[N]; /* 定义哲学家状态数组 */
const char * status_string[N] =
{
"thinking",
"hungry",
"eating",
};
/* 哲学家处理线程ID */
osThreadId_t tid_Thread01; // thread id
osThreadId_t tid_Thread02; // thread id
osThreadId_t tid_Thread03; // thread id
osThreadId_t tid_Thread04; // thread id
osThreadId_t tid_Thread05; // thread id
const osThreadAttr_t phd01_thread_Attr =
{
.name = "phd01_Thread",
.attr_bits = osThreadDetached,
.priority = osPriorityLow1,
.stack_size = 512,
};
const osThreadAttr_t phd02_thread_Attr =
{
.name = "phd02_Thread",
.attr_bits = osThreadDetached,
.priority = osPriorityLow1,
.stack_size = 512,
};
const osThreadAttr_t phd03_thread_Attr =
{
.name = "phd03_Thread",
.attr_bits = osThreadDetached,
.priority = osPriorityLow1,
.stack_size = 512,
};
const osThreadAttr_t phd04_thread_Attr =
{
.name = "phd04_Thread",
.attr_bits = osThreadDetached,
.priority = osPriorityLow1,
.stack_size = 512,
};
const osThreadAttr_t phd05_thread_Attr =
{
.name = "phd05_Thread",
.attr_bits = osThreadDetached,
.priority = osPriorityLow1,
.stack_size = 512,
};
/* 记录哲学家线程执行进餐概率大致相同 */
uint16_t usEatNum[N];
/* 尝试持有叉子吃饭 */
void take_forks(int i)
{
/* 进入临界区通过一个二值信号量实现 */
osSemaphoreAcquire (&sem_lock, osWaitForever);
phd_state[i] = HUNGRY; /* 处于饥饿状态 -- 线程就绪等待调度 */
/* 隔壁个人均不是吃饭状态同一时间只允许一个人处于吃饭状态 */
if(phd_state[LEFT_PHD(i)] != EATING &&
phd_state[RIGHT_PHD(i)] != EATING)
{
phd_state[i] = EATING;
/* 可以得到叉子，发布对应哲学家线程信号量 */
osSemaphoreRelease(&sem[i]);
}
/* 退出临界区*/
osSemaphoreRelease(&sem_lock);
/* 如果不处于EATING状态则阻塞哲学家 */
osSemaphoreAcquire (&sem[i], osWaitForever); /* 尝试持有信号量 */
}
/* 放下叉子 */
void put_forks(int i)
{
/* 进入临界区*/
osSemaphoreAcquire (&sem_lock, osWaitForever);
/* 切换到思考状态 */
phd_state[i] = THINKING; /* 处于思考状态 -- 线程挂起 */
/* 退出临界区*/
osSemaphoreRelease(&sem_lock);
}
/* 哲学家线程 */
void phd_thread_entry(void* parameter)
{
int i;
int j;
i = (int)parameter;
printf("phd %i starts...\r\n", i);
while(1)
{
/* thinking */
osDelay(OS_TICK_FREQ);
//printf("phd %d is %s\r\n", i, status_string[ phd_state[i] ] );
/* take forks */
take_forks(i);
usEatNum[i]++;
if(i==4)
{
if(usEatNum[4]%20 == 0)
{
printf("phd %i starts...\r\n", i);
for(j=0; j<N; j++)
{
printf("phd %d eatnum %d\r\n", j, usEatNum[i] );
}
printf("\r\n");
}
}
/* eating */
//printf("phd %d is %s\r\n", i, status_string[ phd_state[i] ] );
osDelay(OS_TICK_FREQ);
/* put forks */
put_forks(i);
}
}
int rtx_application_init(void)
{
/* 初始化信号量 */
uint8_t i = 0;
sem_lock = osSemaphoreNew(2U, 2U, NULL);
if (sem_lock == NULL)
{
goto _error; // Semaphore object not created, handle failure
}
for (i=0; i<5; i++)
{
sem[i] = osSemaphoreNew(1U, 1U, NULL); /* 信号量初始值设置成1 */
if (sem[i] == NULL)
{
goto _error;
}
}
/* 创建5个哲学家处理线程 */
tid_Thread01 = osThreadNew(phd_thread_entry, (void *)0, &phd01_thread_Attr);
if (tid_Thread01 == NULL)
{
return(-2);
}
tid_Thread02 = osThreadNew(phd_thread_entry, (void *)1, &phd02_thread_Attr);
if (tid_Thread02 == NULL)
{
return(-2);
}
tid_Thread03 = osThreadNew(phd_thread_entry, (void *)2, &phd03_thread_Attr);
if (tid_Thread03 == NULL)
{
return(-2);
}
tid_Thread04 = osThreadNew(phd_thread_entry, (void *)3, &phd04_thread_Attr);
if (tid_Thread04 == NULL)
{
return(-2);
}
tid_Thread05 = osThreadNew(phd_thread_entry, (void *)4, &phd05_thread_Attr);
if (tid_Thread05 == NULL)
{
return(-2);
}
return 0;
_error:
printf("init semaphore failed.\r\n");
return -1;
}
程序执行结果：5 个哲学家线程完全一致，运行一段时间后，他们进餐的

复制代码

eric2013 · 发表于 2020-2-26 00:22:57

非常感谢楼主分享。

风雨无阻29 · 发表于 2020-2-27 11:16:54

感谢楼主分享

aijinquan · 发表于 2020-5-20 09:09:30

感谢分享~

morning_enr6U · 发表于 2020-5-20 11:03:59

感谢楼主分享，

		自动登录	找回密码
密码			立即注册

[RL-RTX] 使用RTX5 信号量解决哲学家就餐问题

评分

[RL-RTX] 使用RTX5 信号量 解决哲学家就餐问题

评分

[RL-RTX] 使用RTX5 信号量解决哲学家就餐问题