操作系统_用多线程同步方法解决哲学家就餐问题.doc

课 程 设 计课程名称 操作系统原理 题 目 用多线程同步方法解决哲学家就餐问题专 业 班 级 学 号 姓 名 成 绩 _指导教师 2010 年 1 月 15日1 需求分析1.1 课程设计题目用多线程同步方法解决哲学家就餐问题1.2 课程设计任务及要求1.2.1设计目的1.巩固和加深课堂所学知识；2.学习掌握一般的软硬件的设计方法和查阅、运用资料的能力；3.熟悉LINUX系统下运用C语言编程及调试1.2.2功能要求用多线程同步方法解决哲学家就餐问题5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处，如何保证哲学家们的动作有序进行？通过对操作系统这门课第二章的学习后，要求我们能够深刻理解和应用有关经典进程的同步和互斥问题。而在就餐问题的设计中，需要我们了解进程同步的概念，理解信号量机制的原理和一般方法，了解系统实现“阻塞”和“唤醒”功能的方法和技巧，掌握运用信号量解决进程同步问题的方法，同时掌握进程同步和互斥的概念和实现技术进而学会运用进程的同步与互斥解决就餐的冲突问题。1.2.3技术要求：1）为每个哲学家产生一个线程，设计正确的同步算法2）每个哲学家取得一双筷子开始用餐后，即时显示“Dining”和该哲学家的自定义标识符以及餐桌上所有几位哲学家标识符及其所坐的位置。3）设定共有5个哲学家需用餐。每位用餐耗时10秒钟以上。4）多个哲学家须共享操作函数代码。1.4 软件运行环境Linux操作系统 2 概要设计2.1设计思想假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左侧筷子， 等一会儿，又同时拿起左侧筷子，如此这般，永远重复。对于这种情况，即所有的程序都在无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。只允许四个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入餐厅的哲学家进入座位的等待队列，根据FIFO 的原则，总会进入到餐厅就餐，因此不会出现饿死和死锁的现象。 Share data Semaphore chopstick5;Initially all values are 1Philosopher i:DoWait(chopsticki)Wait(chopstick(i+1)%5)EatSignal(chopsticki)Signal(chopstick(i+1)%5);Thinkwhile(1);2.1主要数据结构与模块说明Pthread_creat()函数功能: 该函数用来创建新的线程.函数原型:int pthread_create(pthread_t *restrict thread,const pthread_attr_t *restrict attr,void*(*start_routine),void*restrict arg);函数参数:thread用于保存线程的线程变量;attr为要设置的线程属性.start_routine用于指向线程执行时调用的函数arg为线程要执行函数的调用参数.返回值:如果成功,则返回0;否则返回-1.失败时将不会创建新的线程.Pthread_join():函数功能:用来等待一个线程的结束.函数原型:int pthread_join(Pthread_t thread,void *value_ptr);函数参数:pthread参数为被等待的线程标识符Value_ptr为一个用户定义的指针,指向一个保存等待线程的完整退出状态的静态区域.返回值:如果执行成功,则返回0;否则返回非0值.Pthread_mutex_init()函数功能:实现互斥锁的初始化函数原型:pthread_mutex_init(Pthtead_mutex_t *restrict mutex.Const pthread_mutexattr_t *restrict attr);函数参数:mutex是指向要初始化的互斥锁的指针;attr是指向属性对象的指针,如果指针为NULL,则使用缺省的属性.返回值: 成功返回0,否则返回非0值.Pthread_mutex_lock()函数功能:用于对互斥锁进行加锁操作函数原型:pthread_mutex_lock( pthread_mutex_t *mutex);函数参数:mutex为指向要锁定的互斥锁的指针.返回值: 成功返回0,否否则返回指明错误的错误编号。Pthread_mutex_unlock()函数功能:对互斥锁进行解锁操作函数原型:pthread_mutex_unlock(pthread_mutex_t *mutex)函数参数:mutex指向要解锁的互斥锁的指针返回值: 成功返回0,否则返回指明错误的错误编号。Sem_init()函数功能：初始化信号量函数原型：sem_init(sem_t *sem,int pshared,unsigned int value);函数参数：第一个参数是一个类型为sem的指针返回值：成功返回0，否则返回其它值Sem_wait()函数功能：阻塞减少信号量函数原型：sem_wait(sem_t *sem);函数参数：参数是一个类型为sem的指针返回值：成功返回0，否则返回其它值Sem_post()函数功能：增加sem所指示的信号量函数原型：sem_post(sem_t *sem);函数参数：参数是一个类型为sem的指针返回值：成功返回0，否则返回其它值Sem_destroy()函数功能：销毁信号量状态函数原型：sem_destroy(sem_t *sem);函数参数：参数是一个类型为sem的指针返回值：成功返回0，否则返回其它值3.流程图 4哲学家进餐问题(1) 在什么情况下5 个哲学家全部吃不上饭？考虑两种实现的方式，如下：A.算法描述：void philosopher(int i) /*i：哲学家编号，从0 到4*/while (TRUE) think( ); /*哲学家正在思考*/take_fork(i); /*取左侧的筷子*/take_fork(i+1) % N); /*取左侧筷子；为取模运算*/eat( ); /*吃饭*/put_fork(i); /*把左侧筷子放回桌子*/put_fork(i+1) % N); /*把右侧筷子放回桌子*/分析：假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子，如此这般，永远重复。对于这种情况，即所有的程序都在无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。B算法描述：规定在拿到左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则先放下左侧筷子，等一段时间再重复整个过程。分析：当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子如此这样永远重复下去。对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿，所有的哲学家都吃不上饭。(2) 描述一种没有人饿死（永远拿不到筷子）算法。考虑了四种实现的方式（A、B、C、D）：A原理：至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room 作为信号量，只允许4 个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入餐厅的哲学家进入room 的等待队列，根据FIFO 的原则，总会进入到餐厅就餐，因此不会出现饿死和死锁的现象。伪码：semaphore chopstick5=1，1，1，1，1;semaphore room=4;void philosopher(int i)while(true)think();wait(room); /请求进入房间进餐wait(chopsticki); /请求左手边的筷子wait(chopstick(i+1)%5); /请求右手边的筷子eat();signal(chopstick(i+1)%5); /释放右手边的筷子signal(chopsticki); /释放左手边的筷子signal(room); /退出房间释放信号量roomB原理：仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。方法1：利用AND 型信号量机制实现：根据课程讲述，在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。当某些资源不够时阻塞调用进程;由于等待队列的存在，使得对资源的请求满足FIFO 的要求，因此不会出现饥饿的情形。伪码：semaphore chopstick5=1，1，1，1，1;void philosopher(int I)while(true)think();Swait(chopstick(I+1)%5,chopstickI);eat();Ssignal(chopstick(I+1)%5,chopstickI);方法2：利用信号量的保护机制实现。通过信号量mutex对eat（）之前的取左侧和右侧筷子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。伪码：semaphore mutex = 1 ;semaphore chopstick5=1，1，1，1，1;void philosopher(int I)while(true)think();wait(mutex);wait(chopstick(I+1)%5);wait(chopstickI);signal(mutex);eat();signal(chopstick(I+1)%5);signal(chopstickI);C原理：规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。伪码：semaphore chopstick5=1，1，1，1，1;void philosopher(int i)while(true)think();if(i%2 = 0) /偶数哲学家，先右后左。wait (chopstick i + 1 mod 5) ;wait (chopstick i) ;eat();signal (chopstick i + 1 mod 5) ;signal (chopstick i) ;Else /奇数哲学家，先左后右。wait (chopstick i) ;wait (chopstick i + 1 mod 5) ;eat();signal (chopstick i) ;signal (chopstick i + 1 mod 5) ;D利用管程机制实现（最终该实现是失败的，见以下分析）：原理：不是对每只筷子设置信号量，而是对每个哲学家设置信号量。test()函数有以下作用：a. 如果当前处理的哲学家处于饥饿状态且两侧哲学家不在吃饭状态，则当前哲学家通过test()函数试图进入吃饭状态。b. 如果通过test()进入吃饭状态不成功，那么当前哲学家就在该信号量阻塞等待，直到其他的哲学家进程通过test()将该哲学家的状态设置为EATING。c. 当一个哲学家进程调用put_forks()放下筷子的时候，会通过test()测试它的邻居，如果邻居处于饥饿状态，且该邻居的邻居不在吃饭状态，则该邻居进入吃饭状态。由上所述,该算法不会出现死锁，因为一个哲学家只有在两个邻座都不在进餐时，才允许转换到进餐状态。该算法会出现某个哲学家适终无法吃饭的情况，即当该哲学家的左右两个哲学家交替处在吃饭的状态的时候，则该哲学家始终无法进入吃饭的状态，因此不满足题目的要求。但是该算法能够实现对于任意多位哲学家的情况都能获得最大的并行度，因此具有重要的意义。伪码：#define N 5 /* 哲学家人数*/#define LEFT (i-1+N)%N /* i的左邻号码 */#define RIGHT (i+1)%N /* i的右邻号码 */typedef enum THINKING, HUNGRY, EATING phil_state; /*哲学家状态*/monitor dp /*管程*/phil_state stateN;semaphore mutex =1;semaphore sN; /*每个哲学家一个信号量，初始值为0*/void test(int i)if ( statei = HUNGRY &stateLEFT(i) != EATING &stateRIGHT(i) != EATING )statei = EATING;V(si);void get_forks(int i)P(mutex);statei = HUNGRY;test(i); /*试图得到两支筷子*/V(mutex);P(si); /*得不到筷子则阻塞*/void put_forks(int i)P(mutex);statei= THINKING;test(LEFT(i); /*看左邻是否进餐*/test(RIGHT(i); /*看右邻是否进餐*/V(mutex);哲学家进程如下：void philosopher(int process)while(true)think();get_forks(process);eat();put_forks(process);5.源代码源代码为：#include#include#include#includePthread_mutex_t lock;Sem_t chopstick5;Sem_t chair;Int share4=-1,-1,-1,-1;Int count=0;Int n=1;Void *philosopher(void *args)int id,index,I;Id=* ( ( int *) args );Sem_wait(&chair);Count+;while( share index%4 = -1 ) share ( index +) %4 =1;For( i=0;i4;i+) If ( share I = -1) index=I;share I = id ; break;printf (“ the %d th philosopher is sitting at %dn” , id , index);sleep(i);Sem_wait(&chopstick index);Sem_wait(&chopstick ( index+1 )%5 );printf (“the %d th philosopher is eating %d n” , id ,count);Print(“ (%d)-dining: %d th philosopher | the total num %d-n” ,n+, id ,count);For ( i=0;i4;i+) If( share i ! = -1) Printf(“the %d philosopher is sitting at %dn”, share I , I );Printf(“.n”);Sleep(10);Sem_post ( &chopstick ( index+1 )%5 );Sem_post ( &chopstick index );Share index = -1;Count-;Sem_post(&chair);main()Int I;Pthread_t id1,id2;Sem_init( &chair, 0 , 4);For(i=0;i5;i+) sem_init ( & chopstick i, 0, 1);For(i=0; I10; i+) pthread_create(&id1,NULL, (void*)philosopher,(void*)&i);Pthread_join(id1,NULL);6.运行结果6.1运行结果截图调试如下：以下是在调试过程中出现的一些错误：由于是自己的机器上装的LINUX，而且对该系统的操作还不够熟练，导致许多问题的发生，程序上也许有些许缺陷，但是进过多次检查后虽然找出一些错误，但还是没能让程序成功运行7.心得体会虽然本次课程设计中所需做的实验耗时一星期，但是我也查了很多的相关书籍，这次的课程设计给我们很大的收获，使我们对操作系统的基本知识有了进一步的提高，并在实践