使用RTX5 信号量 解决哲学家就餐问题
1965 年，Dijkstra 提出并解决了一个他称之为哲学家 就餐的同步问题。从那时起，每个发明新的同步原语的人都希望通过解决哲 学家就餐问题来展示其同步原语的精妙之处。这个问题可以简单地描述如 下：五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一盘通心粉。由 于通心粉很滑，
所以需要两把叉子才能夹住。相邻两个盘子之间放有一把 叉子，餐桌如图 1 示。
哲学家的生活中有两种交替活动时段：即吃饭和思考（这只是一种抽象，即对哲学家而言其他活动都无关紧要）。
当一个哲学家觉得饿了时， 他就试图分两次去取其左边和右边的叉子，每次拿一把，但不分次序。
如 果成功地得到了两把叉子，就开始吃饭，吃完后放下叉子继续思考。
关键 问题是：能为每一个哲学家写一段描述其行为的程序，且决不会死锁吗？
声明：以上文字和图片出自《Operating Systems Design and
Implementation》 By Andrew S. Tanenbaum。 该实验是对哲学家就餐问题的模拟实现。
《Operating SystemsDesign andImplementation》中的哲学家就餐问题的就解决方案。 如果读者想要对这个问题进行深入的理解请参考此书 2.3.1节。 每位哲学家一共有三种状态，分别为思考（THINKING），饥饿（HUNGRY），和进餐（EATING）。当哲学家从思考中醒来则进入到饥饿状态，他会试图 获取餐叉。当获取到两把叉子，则进入进餐状态（EATING）使用一个数组 phd_state，来跟踪每位哲学家的状态，在本实验中， 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; /* 每位哲学家一个信号量 */
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; /* 定义哲学家状态数组 */
const char * status_string =
{
"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;
/* 尝试持有叉子吃饭 */
void take_forks(int i)
{
/* 进入临界区通过一个二值信号量实现 */
osSemaphoreAcquire (&sem_lock, osWaitForever);
phd_state = HUNGRY; /* 处于饥饿状态 -- 线程就绪等待调度 */
/* 隔壁个人均不是吃饭状态 同一时间只允许一个人处于吃饭状态 */
if(phd_state != EATING &&
phd_state != EATING)
{
phd_state = EATING;
/* 可以得到叉子，发布对应哲学家线程信号量 */
osSemaphoreRelease(&sem);
}
/* 退出临界区*/
osSemaphoreRelease(&sem_lock);
/* 如果不处于EATING状态则阻塞哲学家 */
osSemaphoreAcquire (&sem, osWaitForever); /* 尝试持有信号量 */
}
/* 放下叉子 */
void put_forks(int i)
{
/* 进入临界区*/
osSemaphoreAcquire (&sem_lock, osWaitForever);
/* 切换到思考状态 */
phd_state = 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 ] );
/* take forks */
take_forks(i);
usEatNum++;
if(i==4)
{
if(usEatNum%20 == 0)
{
printf("phd %i starts...\r\n", i);
for(j=0; j<N; j++)
{
printf("phd %d eatnum %d\r\n", j, usEatNum );
}
printf("\r\n");
}
}
/* eating */
//printf("phd %d is %s\r\n", i, status_string[ phd_state ] );
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 = osSemaphoreNew(1U, 1U, NULL); /* 信号量初始值设置成1 */
if (sem == 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 个哲学家线程完全一致，运行一段时间后，他们进餐的
非常感谢楼主分享。 感谢楼主分享 感谢分享~:):):) 感谢楼主分享，{:7:}
页:
[1]