Linux经典问题—五哲学家就餐问题

http://m.blog.csdn.net/aspenstars/article/details/70149038

一、问题介绍

       由Dijkstra提出并解决的哲学家进餐问题(The Dinning Philosophers Problem)是典型的同步问题。该问题是描述有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。

二、POSIX中的互斥量

1、库文件：#include <pthread.h>

2、数据类型：

pthread_mutex_t       //互斥量

pthread_mutexattr_t   //互斥量的属性

3、互斥量相关的函数：

① i nt pthread_mutex_init(pthread_mutex_t*mutex,constpthread_mutexattr_t *attr);//对一个互斥量进行初始化

② i nt pthread_mutex_destroy(pthread_mutex_t*mutex);//销毁一个互斥量；返回值：成功则返回0，否则返回错误编号

③ intpthread_mutex_lock(pthread_mutex_t *mutex);

④ intpthread_mutex_trylock(pthread_mutex_t *mutex);

⑤ intpthread_mutex_unlock(pthread_mutex_t *mutex);//返回值：成功则返回0，否则返回错误编号;这三个函数用于对互斥量进行加锁解锁。其中pthread_mutex_trylock是非阻塞的加锁函数，若加锁失败，则立即返回EBUSY。

4、示例

//…

pthread_mutex_tmutex;

pthread_mutex_init(&mutex, NULL);

pthread_mutex_lock(&mutex);

//do something

pthread_mutex_unlock(&mutex);

pthread_mutex_destroy(&mutex);

//…

三、POSIX线程函数

1、库文件：#include<pthread.h>

2、数据类型：pthread_t;线程ID

3、线程相关函数：

① pthread_t pthread_self ();// 返回调用线程的线程 ID

② int pthread_create ( pthread_t  * tidp ,  const pthread_attr_t attr , void *(* start_rtn )(void*), void * arg );//线程创建函数，tidp，用于返回线程ID；attr，线程属性，若设为NULL,则线程使用默认属性；start_rtn是线程例程函数，arg为线程函数参数。

③ void pthread_exit (void * rval_ptr );//rval_ptr指向线程返回值。

线程退出有以下几种情况：

a. 线程从例程函数返回。

b. 线程被其它线程取消。

c. 线程调用 pthread_exit () 主动退出。

④ int pthread_join ( pthread_t  thread, void ** rval_ptr );//返回值：成功返回0，错误返回错误编号;此函数用于等待指定线程（由参数thread指定）运行结束，期间，调用线程将会阻塞。rval_ptr参数用于获取线程返回值。

四、Linux信号量

1、库文件：#include<semaphore.h>

2、信号量数据类型：sem_t

3、主要函数：

① sem_init(sem_t*sem, int pshared, unsigned int value);// 初始化一个无名信号量

② sem_destroy(sem_t*sem);// 销毁一个无名信号量；返回值：成功返回 0；错误返回 -1，并设置errno 

③ sem_post ( sem_t  * sem );// 信号量值加 1 。若有线程阻塞于信号量 sem ，则调度器会唤醒对应阻塞队列中的某一个线程。

④ sem_wait ( sem_t  * sem );// 若 sem 小于 0 ，则线程阻塞于信号量 sem ，直到 sem 大于 0 。否则信号量值减 1 。

⑤ sem_trywait ( sem_t  * sem );// 功能同 sem_wait () ，但此函数不阻塞，若 sem 小于 0 ，直接返回；返回值：成功返回0，错误返回-1，并设置errno 

4、示例

sem_tsem;

sem_init(&sem,0, 1);//初始化一个值为1的信号量

sem_wait(&sem);//获取信号量

//dosomthing

sem_post(&sem);//释放信号量

sem_destroy(&sem);//销毁一个无名信号量

五、流程图

六、代码示例

使用互斥量：

#include <stdio.h> #include <stdlib.h> #include <memory.h> #include <pthread.h> #include <errno.h> #include <math.h> //筷子作为mutex pthread_mutex_t chopstick [ 6 ] ; void * eat_think ( void * arg ) { char phi = * ( char * ) arg ; int left , right ; //左右筷子的编号 switch ( phi ){ case 'A': left = 5 ; right = 1 ; break ; case 'B': left = 1 ; right = 2 ; break ; case 'C': left = 2 ; right = 3 ; break ; case 'D': left = 3 ; right = 4 ; break ; case 'E': left = 4 ; right = 5 ; break ; } int i ; for (;;){ usleep ( 3 ); //思考 pthread_mutex_lock ( & chopstick [ left ]); //拿起左手的筷子 printf ( "Philosopher %c fetches chopstick %d \n " , phi , left ); if ( pthread_mutex_trylock ( & chopstick [ right ]) == EBUSY ){ //拿起右手的筷子 pthread_mutex_unlock ( & chopstick [ left ]); //如果右边筷子被拿走放下左手的筷子 continue ; } // pthread_mutex_lock(&chopstick[right]); //拿起右手的筷子，如果想观察死锁，把上一句if注释掉，再把这一句的注释去掉 printf ( "Philosopher %c fetches chopstick %d \n " , phi , right ); printf ( "Philosopher %c is eating. \n " , phi ); usleep ( 3 ); //吃饭 pthread_mutex_unlock ( & chopstick [ left ]); //放下左手的筷子 printf ( "Philosopher %c release chopstick %d \n " , phi , left ); pthread_mutex_unlock ( & chopstick [ right ]); //放下左手的筷子 printf ( "Philosopher %c release chopstick %d \n " , phi , right ); pthread_mutex_destroy ( & chopstick [ left ]); pthread_mutex_destroy ( & chopstick [ right ]); } } int main (){ pthread_mutex_t A , B , C , D , E ; //5个哲学家 int i ; for ( i = 0 ; i < 5 ; i ++ ) pthread_mutex_init ( & chopstick [ i ], NULL ); pthread_create ( & A , NULL , eat_think , "A" ); pthread_create ( & B , NULL , eat_think , "B" ); pthread_create ( & C , NULL , eat_think , "C" ); pthread_create ( & D , NULL , eat_think , "D" ); pthread_create ( & E , NULL , eat_think , "E" ); pthread_join ( A , NULL ); pthread_join ( B , NULL ); pthread_join ( C , NULL ); pthread_join ( D , NULL ); pthread_join ( E , NULL ); return 0 ; }

 来自CODE的代码片

Phli.c

使用信号量：

#include <stdio.h> #include <stdlib.h> #include <pthread.h> #include <semaphore.h> sem_t chopstick [ 6 ] ; void * eat_think ( void * arg ) { char phi = * ( char * ) arg ; int left , right ; switch ( phi ){ case 'A': left = 5 ; right = 1 ; break ; case 'B': left = 1 ; right = 2 ; break ; case 'C': left = 2 ; right = 3 ; break ; case 'D': left = 3 ; right = 4 ; break ; case 'E': left = 4 ; right = 5 ; break ; } int i ; for (;;){ usleep ( 3 ); sem_wait ( & chopstick [ left ]); printf ( "Philosopher %c fetches chopstick %d \n " , phi , left ); if ( sem_trywait ( & chopstick [ right ]) < 0 ){ sem_post ( & chopstick [ left ]); continue ; } printf ( "Philosopher %c fetches chopstick %d \n " , phi , right ); printf ( "Philosopher %c is eating. \n " , phi ); usleep ( 3 ); sem_post ( & chopstick [ left ]); printf ( "Philosopher %c release chopstick %d \n " , phi , left ); sem_post ( & chopstick [ right ]); printf ( "Philosopher %c release chopstick %d \n " , phi , right ); } } int main (){ pthread_t A , B , C , D , E ; int i ; for ( i = 0 ; i < 5 ; i ++ ) sem_init ( & chopstick [ i ], 0 , 1 ); pthread_create ( & A , NULL , eat_think , "A" ); pthread_create ( & B , NULL , eat_think , "B" ); pthread_create ( & C , NULL , eat_think , "C" ); pthread_create ( & D , NULL , eat_think , "D" ); pthread_create ( & E , NULL , eat_think , "E" ); pthread_join ( A , NULL ); pthread_join ( B , NULL ); pthread_join ( C , NULL ); pthread_join ( D , NULL ); pthread_join ( E , NULL ); return 0 ; }