哲学家就餐问题

1、(2013-2014 学年第二学期 )重庆理工大学研究生课程论文课程论文题目 ：基于 ucos-ii 操作系统解决哲学家就餐问题(Problem of Philosophers Dining)课程名称嵌入式系统实验与实践课程类别学位课非学位课任课教师万文略所在学院电子学院学科专业仪器仪表工程姓名王小辉学号51307260101提交日期2014年6月27日注意事项：1、以上各项由研究生认真填写；2、研究生课程论文应符合一般学术规范，具有一定学术价值，严禁网上下载或抄袭；凡检查或抽查不合格者，一律取消该门课程成绩和学分，并按有关规定追究相关人员责任；3、论文得分由批阅教师填写（见封底） ，并签字确

2、认；批阅教师应根据作业质量客观、公正的在文后签写批阅意见；4、原则上要求所有课程论文均须用A4 纸打印，加装本封面封底，左侧装订；5、课程论文由各学院（部）统一保存，以备查用。4、卷纸不够写，可另附纸。基于 ucos-ii的哲学家就餐解决方案摘要：针对经典的哲学家进餐问题，对多任务同步运行进行了研究。介绍了基于ucos-ii的多任务程序设计和任务间的通信机制，列举了可行的实现方法。并给出了最后的运行结果，使得哲学家能够正常进餐，不被饿死。关键词：互斥同步 多任务任务间通信顺序一、问题陈列哲学家进餐问题是荷兰学者 Dijkstra 提出的经典问题之一 , 它是一个信号量机制问题的应用 , 在操作

3、系统文化史上具有非常重要的地位。假设有 5 个哲学家，他们花费一生中的时光思考和吃饭。 这些哲学家共用一个圆桌， 每个哲学家都有一把椅子。 在桌子中央是一碗通心面， 在桌子上放着 5 只筷子。哲学家感到饥饿时，并试图拿起与他相近的两只筷子（他与邻近左、右之间的筷子）吃饭。要求：哲学家一次只能拿一只筷子, 且必须拥有两只筷子才能吃饭。如果筷子已被别人拿走，必须等到别人吃完放下才能拿到筷子。每个哲学家在没拿到第二只筷子时，不会放弃手中已拿到的一只筷子。假定哲学家每次吃饭的时间长度为单位1，吃完一次后则放下两只筷子。如果等待 l0 个单位时间长度之后，哲学家仍没有得到筷子吃饭，则被饿死。设计一种方法

4、使得任何一个哲学家都不被饿死。二、问题分析对问题分析可知，目前问题的瓶颈在于：死锁。死锁的发生必须满足以下四个必要条件：互斥：至少有一个资源每次只能被一个进程使用， 即非共享模式。 这里指每只筷子只能被一个哲学家持有。占有并等待。一个进程因请求资源而阻塞时，对已获得的资源保持不放。这里指哲学家在没拿到第二只筷子时，不会放弃手中已拿到的一只筷子。不剥夺条件 : 进程已获得的资源，在末使用完之前，不能强行剥夺。这里指哲学家不能去抢别人的筷子。循环等待条件 : 若干进程之间形成一种头尾相接的循环等待资源关系。这四个条件是死锁的必要条件， 只要系统发生死锁， 这些条件必然成立， 而只要上述条件之一不满

5、足，就不会发生死锁。在系统设计、进程调度等方面注意避免让这四个必要条件成立， 如何确定资源的合理分配算法， 避免进程永久占据系统资源。 此外，也要防止进程在处于等待状态的情况下占用资源。即，对资源的分配要给予合理的规划。三、方案设计要避免死锁，最好的方法是复制原本需要互斥访问的资源， 这样每个进程都拥有一个资源的私有副本。 每个进程访问自己的副本， 从而可以避免使用锁。 这种不使用锁的方法， 从根本上消除了死锁存在的可能， 并进一步提高了可扩展性和该组件的可组装型。 即本问题可以通过增加筷子数而避免死锁， 但与解题要求不符，所以另寻他法。既然资源无法被复制， 按一定的顺序获取资源锁， 也可以避

6、免死锁。 这里我们可以通过设置各任务挂起顺序而避免死锁， 也可以通过为每个资源锁分配一个唯一的整数，再允许用户比较各资源锁以确定其先后顺序。对于哲学家晚餐的问题， 我是选取的最后这种方法， 即为每个任务分配了唯一的门槛整数， 是它就运行相应程序， 不是就得释放资源等待时机， 为其他任务运行腾资源。由于问题中有五只筷子， 也就是说两不相邻的哲学家可以同时吃， 所以出于资源充分利用原则， 我让一个任务运行处理两个哲学家的吃饭问题， 当然这两个哲学家必须是不相邻的。 其实建立三个这样的任务， 就能保证哲学家不饿死 （任务一：处理哲学家 1、3；任务二：处理哲学家 2、4；任务三：处理哲学家 3、5；

7、）。但出于公平考虑，我建立了五个这样任务，既任务一：处理哲学家 1、 3；任务二：处理哲学家 2、 4；任务三：处理哲学家 3、5；任务四：处理哲学家 4、1；任务二：处理哲学家 5、2，这样一个循环下来，每人吃饭 2 次，且时间间隔也一致，更具人性化。四、源程序代码#include <ucos_ii.h>#include <stm32f10x.h>#include <stdio.h>#ifdef _GNUC_/* With GCC/RAISONANCE,small printf(option LD Linker->Libraries->Smal

8、lprintf set to 'Yes') calls _io_putchar() */#define PUTCHAR_PROTOTYPE int _io_putchar(int ch)#else#define PUTCHAR_PROTOTYPE int fputc(int ch, FILE *f)#endif /* _GNUC_ */OS_STK philosopher1and3_Stack100; /建立哲学家任务块堆栈OS_STK philosopher2and4_Stack100; /建立哲学家任务块堆栈OS_STK philosopher3and5_Stack100;

9、 /建立哲学家任务块堆栈OS_STK philosopher4and1_Stack100; /建立哲学家任务块堆栈OS_STK philosopher5and2_Stack100; /建立哲学家任务块堆栈OS_STK conduct_stack100;/建立门槛设置任务块堆栈OS_EVENT *stick5;/五个筷子事件#define PHILOSOPHER11/哲学家编号#define PHILOSOPHER22/哲学家编号#define PHILOSOPHER33/哲学家编号#define PHILOSOPHER44/哲学家编号#define PHILOSOPHER55/哲学家编号con

10、st INT8U philosopher5=8,9,10,11,12;int swich=0;/门槛整数int end_flag=5;/门槛整数void task_philosopher1and3(void); /定义哲学家任务void task_philosopher2and4(void); /定义哲学家任务void task_philosopher3and5(void); /定义哲学家任务void task_philosopher4and1(void); /定义哲学家任务void task_philosopher5and2(void); /定义哲学家任务void task_conduct(

11、void);/定义门槛设置任务void think(int i);/定义哲学家思考函数void Take_fork(int i);/定义哲学家拿筷子函数void Eat(int i);/定义哲学家吃饭函数void Put_fork(int i);/定义哲学家放筷子函数static void systick_init(void); /定义系统时钟函数int main()int i;INT8U err;USART_InitTypeDefUSART_InitStructure;GPIO_InitTypeDef GPIO_InitStructure;RCC_APB2PeriphClockCmd(RCC

12、_APB2Periph_GPIOA| RCC_APB2Periph_AFIO|RCC_APB2Periph_USART1 , ENABLE);GPIO_InitStructure.GPIO_Mode = GPIO_Mode_AF_PP;GPIO_InitStructure.GPIO_Pin = GPIO_Pin_9;GPIO_InitStructure.GPIO_Speed = GPIO_Speed_50MHz;GPIO_Init(GPIOA, &GPIO_InitStructure);GPIO_InitStructure.GPIO_Mode = GPIO_Mode_AF_PP;GPI

13、O_InitStructure.GPIO_Pin = GPIO_Pin_10;GPIO_InitStructure.GPIO_Speed = GPIO_Speed_50MHz;GPIO_Init(GPIOA, &GPIO_InitStructure);USART_InitStructure.USART_BaudRate = 115200;USART_InitStructure.USART_WordLength = USART_WordLength_8b;USART_InitStructure.USART_StopBits = USART_StopBits_1;USART_InitStr

14、ucture.USART_Parity = USART_Parity_No; USART_InitStructure.USART_HardwareFlowControl=USART_HardwareFlowContr ol_None;USART_InitStructure.USART_Mode = USART_Mode_Rx |USART_Mode_Tx; USART_Init(USART1, &USART_InitStructure); USART_Cmd(USART1, ENABLE);OSInit();for(i=0;i<5;i+)sticki=OSMutexCreate(

15、i,&err);/建立五根筷子互斥量OSTaskCreate(task_philosopher1and3,(void *)0,&philosopher1and3_Stack99, 8);/建立第一个哲学家任务，优先级最高OSStart();/启动任务函数调用void task_philosopher1and3 (void)OSTaskCreate(task_philosopher2and4,(void *)0,&philosopher2and4_ Stack99, 13);OSTaskCreate(task_philosopher3and5,(void *)0,&

16、;philosopher3and5_ Stack99, 12);OSTaskCreate(task_philosopher4and1,(void *)0,&philosopher4and1_ Stack99, 11);OSTaskCreate(task_philosopher5and2,(void *)0,&philosopher5and2_ Stack99, 10);OSTaskCreate(task_conduct,(void *)0,&conduct_stack99, 9);systick_init();while(1)if(swich=0)/门槛整数think(

17、PHILOSOPHER1);think(PHILOSOPHER3);Take_fork(PHILOSOPHER1); Take_fork(PHILOSOPHER3);Eat(PHILOSOPHER1);Eat(PHILOSOPHER3);Put_fork(PHILOSOPHER1);Put_fork(PHILOSOPHER3);end_flag=0;/门槛整数OSTimeDlyHMSM(0,0,0,300);/延时300ms以释放资源void task_philosopher2and4 (void)while(1)if(swich=1)/门槛整数think(PHILOSOPHER2);thin

18、k(PHILOSOPHER4);Take_fork(PHILOSOPHER2); Take_fork(PHILOSOPHER4);Eat(PHILOSOPHER2);Eat(PHILOSOPHER4);Put_fork(PHILOSOPHER2);Put_fork(PHILOSOPHER4);end_flag=1;/门槛整数OSTimeDlyHMSM(0,0,0,300);/延时300ms以释放资源void task_philosopher3and5 (void)while(1)if(swich=2)/门槛整数think(PHILOSOPHER3);think(PHILOSOPHER5);Ta

19、ke_fork(PHILOSOPHER3); Take_fork(PHILOSOPHER5);Eat(PHILOSOPHER3);Eat(PHILOSOPHER5);Put_fork(PHILOSOPHER3);Put_fork(PHILOSOPHER5);end_flag=2;/门槛整数OSTimeDlyHMSM(0,0,0,300);/延时300ms以释放资源void task_philosopher4and1 (void)while(1)if(swich=3)/门槛整数think(PHILOSOPHER4);think(PHILOSOPHER1);Take_fork(PHILOSOPHE

20、R4); Take_fork(PHILOSOPHER1);Eat(PHILOSOPHER4);Eat(PHILOSOPHER1);Put_fork(PHILOSOPHER4);Put_fork(PHILOSOPHER1);end_flag=3;/门槛整数OSTimeDlyHMSM(0,0,0,300);/延时300ms以释放资源void task_philosopher5and2 (void)while(1)if(swich=4)/门槛整数think(PHILOSOPHER5);think(PHILOSOPHER2);Take_fork(PHILOSOPHER5); Take_fork(PHI

21、LOSOPHER2);Eat(PHILOSOPHER5);Eat(PHILOSOPHER2);Put_fork(PHILOSOPHER5);Put_fork(PHILOSOPHER2);end_flag=4;/门槛整数OSTimeDlyHMSM(0,0,0,300);/延时300ms以释放资源void task_conduct(void)/门槛整数设置函数while(1)if(end_flag=0) swich=1;if(end_flag=1) swich=2;if(end_flag=2) swich=3;if(end_flag=3) swich=4;if(end_flag=4) swich=

22、0;OSTimeDlyHMSM(0,0,0,300);void think(int i)printf("philosopher %d is thinkingn",i);void Take_fork(int i)INT8U err;OSMutexPend(sticki,100,&err);/if(err=OS_ERR_TIMEOUT)printf("philosopher %d is hungryn",i);OSTimeDly(10);OSMutexPend(stick(i+1)%5,100,&err);if(err=OS_ERR_TIME

23、OUT)等待存取筷子信号量语句printf("philosopher %d is deadn",i);OSTaskDel(philosopheri);/删除哲学家任务语句elseprintf("philosopher %d got the forkn",i);void Eat(int i)printf("philosopher %d is eattingn",i);void Put_fork(int i)/放筷子函数OSMutexPost(sticki);OSMutexPost(stick(i+1)%5);printf("p

24、hilosopher %d put the forkn",i);static void systick_init(void)/时钟设置函数RCC_ClocksTypeDef rcc_clocks;RCC_GetClocksFreq(&rcc_clocks);SysTick_Config(rcc_clocks.HCLK_Frequency / OS_TICKS_PER_SEC);PUTCHAR_PROTOTYPE/* Place your implementation of fputc here */* e.g. write a character to the USART *

25、/USART_SendData(USART1, (uint8_t) ch);/* Loop until the end of transmission */while (USART_GetFlagStatus(USART1, USART_FLAG_TC) = RESET)return ch;五、运行结果pilosopher 1 is thinkingphilosopher 3 is thinkingphilosopher 1 got the forkphilosopher 3 got the forkphilosopher 1 is eattingphilosopher 3 is eattingphilosopher 1 put the forkphilosopher 3 put the forkphilosopher 2 is thinkingphilosopher 4 is thinkingphilosopher 2 got the forkphilosopher 4 got the forkphilosopher 2 is eattingphilosopher 4 is eattingphilosopher 2 put the forkphilosopher 4 put the forkphil