前言
使用OpenMP解決哲學家就餐問題，其實感覺和通過pthreads解決哲學家就餐問題的作業(yè)類似叉跛，核心算法不變，只需要改變創(chuàng)建線程的方法筷厘，而OpenMP比pthreads層次更高鸣峭，編寫一些并行行為更容易。
一酥艳、問題描述
五個沉默的哲學家圍坐在一個圓桌旁摊溶，桌上放著幾碗意大利面充石。叉子被放置在每一對相鄰的哲學家之間。每個哲學家必須交替地思考和進餐拉岁。然而惰爬，哲學家只能在有左右叉子的情況下才能吃意大利面。每個叉子只能被一個哲學家拿著撕瞧，所以一個哲學家只能在沒有被另一個哲學家使用的情況下使用它。當一位哲學家吃完飯后丛版，他們需要把兩把叉子放下，這樣其他人就可以享用這些叉子了锌半。哲學家只能在他們有空的時候拿右手或左手的叉子寇漫，在拿兩副叉子之前他們不能開始吃東西。每個哲學家有3種狀態(tài){thinking州胳，trying，eating}遍膜。吃東西不受剩余的意大利面或胃空間的限制，假設(shè)有一個無限的供給和一個無限的需求瓢颅。問題是如何設(shè)計一種行為準則(并發(fā)算法)，以確保沒有哲學家挨餓翰意；也就是說信柿，每一種都可以永遠在吃飯和思考之間交替，假設(shè)沒有一個哲學家可以知道其他人什么時候可能想吃飯或思考渔嚷。
二、概要設(shè)計
編程語言使用OpenMP與C語言實現(xiàn)客年。本次實驗采用多線程解決哲學家就餐問題漠吻。由于哲學家的刀叉是共享變量量瓜，所以使用信號量實現(xiàn)互斥侥猩。線程個數(shù)(-n)即為哲學家個數(shù)抵赢，同時為每個叉子定義對應的信號量。每個哲學家在試圖使用餐叉的時候需要先進行sem_wait铅鲤，當拿到兩個餐叉后，哲學家就能eating鹏往，eating完之后使用sem_post解鎖這兩個餐叉。
三伊履、避免死鎖的策略
method1：
解法：允許最多 thread_count - 1 個哲學家同時進入餐廳嘗試獲取餐叉款违，剩下的一個哲學家只有在有人吃完出去的時候才進去。這樣就能保證起碼有一個人能夠同時獲得兩個餐叉插爹，從而eating，避免大家都處于trying的狀態(tài)力穗。這種解法也能理解為引入一個餐廳服務生，哲學家必須經(jīng)過他的允許才能拿起餐叉够坐。當同時有 thread_count - 1 個餐叉被請求時超全，若是其他哲學家請求最后一個餐叉，服務生會讓他等待嘶朱。
實現(xiàn)方法：增加一個信號量sem_waiter，其初始值為thread_count - 1脉课，每個線程trying時會先sem_wait(&sem_waiter)财异，在請求到兩個餐叉并且eating后，再解鎖兩個叉子并使用sem_post(&sem_waiter)通知服務生呈驶。
method2：
解法：使用非對稱解決方案疫鹊。即單號的哲學家先拿起左邊的叉子，接著右邊的叉子拆吆；而雙號的哲學家先拿起右邊的叉子，接著左邊的叉子霉晕。
實現(xiàn)方法：獲取當前線程的編號捞奕，如果是奇數(shù)號線程就先請求左邊的餐叉，然后請求右邊的餐叉颅围；如果是偶數(shù)好線程就先請求右邊的餐叉，然后請求左邊的餐叉扒俯。
四、實驗
編譯：gcc -g -Wall -fopenmp -o philosopher philosopher.c
運行：./philosopher -normal n 哲學家個數(shù) ./philosopher -method1 n 哲學家個數(shù) ./philosopher -method2 n 哲學家個數(shù)
五夺姑、分析
1. -normal
正常狀態(tài)下哲學家遵守以下規(guī)則：
哲學家在左邊的叉子可用（沒有其他人拿起）之前處于思考狀態(tài)掌猛。如果左邊的叉子可用，就拿起來荔茬。
哲學家等待右邊的叉子可用。如果右邊的叉子可用丐黄，就拿起來孔飒。
如果兩個叉子都已經(jīng)拿起來，開始吃意大利面桂对，每次吃面都花費同樣的時間鸠匀。
吃完后先放下左邊的叉子。
然后放下右邊的叉子缀棍。
-
開始思考（進入一個循環(huán)）
但這種解法是失敗的，當每個哲學家都拿起左側(cè)的叉子诽凌，等待右側(cè)的叉子可用時坦敌，就會進入死鎖狀態(tài)痢法，每個哲學家將永遠都在等待（右邊的）另一個哲學家放下叉子。
2. -method1
至多只允許四個哲學家同時進餐蘸炸，以保證至少有一個哲學家能夠進餐尖奔，最終總會釋放出他所使用過的兩支筷子穷当，從而可使更多的哲學家進餐淹禾。以下將sem_waiter作為信號量，只允許thread_count - 1個哲學家同時進入餐廳就餐铃岔，這樣就能保證至少有一個哲學家可以就餐，而申請進入餐廳的哲學家進入sem_waiter的等待隊列智嚷，根據(jù)FIFO的原則纺且，總會進入到餐廳就餐，因此不會出現(xiàn)餓死和死鎖的現(xiàn)象摇天。
3.-method2
規(guī)定奇數(shù)號的哲學家先拿起他左邊的筷子恐仑，然后再去拿他右邊的筷子；而偶數(shù)號的哲學家則相反裳仆。按此規(guī)定，將是1纯丸、2號哲學家競爭1號筷子静袖，3、4號哲學家競爭3號筷子坠陈。即五個哲學家都競爭奇數(shù)號筷子捐康，獲得后，再去競爭偶數(shù)號筷子解总，最后總會有一個哲學家能獲得兩支筷子而進餐。而申請不到的哲學家進入阻塞等待隊列刻盐，根FIFO原則，則先申請的哲學家會較先可以吃飯壤追，因此不會出現(xiàn)餓死的哲學家供屉。
六、源代碼
#include <stdio.h>
#include <stdlib.h>
#ifdef _OPENMP
#include <omp.h>
#endif
#include <semaphore.h>
#include <unistd.h>
#include <string.h>
sem_t *sem_fork; //定義一組餐叉的信號量
sem_t sem_waiter; //method1中用到的信號量伶丐，用于確保至少一個人不能進餐
void *Philo_normal(); //一般方法，會陷入死鎖
void *Philo_method1(); //方法1肛走，服務生方法
void *Philo_method2(); //方法2录别，非對稱解決方案
int Gene_random() {
return rand()%91 + 10;
}
int main(int argc, char *argv[])
{
//獲取線程個數(shù)，本實驗中也代表哲學家人數(shù)
long thread_count = strtol(argv[2], NULL, 10);
sem_fork = malloc (thread_count * sizeof(sem_t));
//初始化waiter信號量
sem_init(&sem_waiter, 0, thread_count-1);
//初始化所有叉子信號量
for(long i = 0; i < thread_count; i ++ ){
sem_init(&sem_fork[i], 0, 1);
}
//根據(jù)參數(shù)進入相應的處理函數(shù)
if(strcmp(argv[1], "-normal") == 0){
# pragma omp parallel num_threads(thread_count)
Philo_normal();
}
else if(strcmp(argv[1], "-method1") == 0){
# pragma omp parallel num_threads(thread_count)
Philo_method1();
}
else if(strcmp(argv[1], "-method2") == 0){
# pragma omp parallel num_threads(thread_count)
Philo_method2();
}
//銷毀餐叉信號量
for(long i = 0; i < thread_count; i ++ ){
sem_destroy(&sem_fork[i]);
}
//銷毀服務生信號量
sem_destroy(&sem_waiter);
//釋放空間
free(sem_fork);
return 0;
}
//一般方法葫男，會陷入死鎖
void *Philo_normal(void)
{
# ifdef _OPENMP
long my_rank = omp_get_thread_num();
long thread_count = omp_get_num_threads();
# else
long my_rank = 0;
long thread_count = 1;
# endif
long my_left_fork, my_right_fork; //表示每個哲學家左右的叉子
my_left_fork = my_rank;
my_right_fork = (my_rank + 1) % thread_count;
while(1){
printf("Philosopher %ld is thinking\n", my_rank);
//把進程掛起一段時間梢褐， 單位是微秒（百萬分之一秒）赵讯；
//usleep( (rand()%91 + 10)*1000 );
//本來應該隨機掛起10-100ms,這里為了更快的檢測死鎖，將時間改為固定的50ms
usleep(50);
printf("Philosopher %ld is trying\n", my_rank);
sem_wait(&sem_fork[my_left_fork]);
sem_wait(&sem_fork[my_right_fork]);
printf("Philosopher %ld is eating\n", my_rank);
//usleep( (rand()%91 + 10)*1000 );
usleep(100);
sem_post(&sem_fork[my_left_fork]);
sem_post(&sem_fork[my_right_fork]);
}
}
//方法1边翼，服務生方法
void *Philo_method1(void)
{
# ifdef _OPENMP
long my_rank = omp_get_thread_num();
long thread_count = omp_get_num_threads();
# else
long my_rank = 0;
long thread_count = 1;
# endif
//哲學家左右的叉子
long my_left_fork, my_right_fork;
my_left_fork = my_rank;
my_right_fork = (my_rank + 1) % thread_count;
while(1){
printf("Philosopher %ld is thinking\n", my_rank);
//usleep( (rand()%91 + 10)*1000 ); //think 10-100 ms
usleep(50);
printf("Philosopher %ld is trying\n", my_rank);
//添加一個waiter信號量確保每個時刻最少一個人沒有進去就餐
sem_wait(&sem_waiter);
sem_wait(&sem_fork[my_left_fork]);
sem_wait(&sem_fork[my_right_fork]);
printf("Philosopher %ld is eating\n", my_rank);
//usleep( (rand()%91 + 10)*1000 ); //eating 10-100 ms
usleep(100);
sem_post(&sem_fork[my_left_fork]);
sem_post(&sem_fork[my_right_fork]);
sem_post(&sem_waiter);
}
}
//方法2组底，非對稱解決方案
void *Philo_method2(void)
{
# ifdef _OPENMP
long my_rank = omp_get_thread_num();
long thread_count = omp_get_num_threads();
# else
long my_rank = 0;
long thread_count = 1;
# endif
//表示哲學家左右的叉子
long my_left_fork, my_right_fork;
//奇數(shù)先左叉后右叉，偶數(shù)先右叉后左叉
if(my_rank % 2 == 1){
my_left_fork = (my_rank + 1) % thread_count;
my_right_fork = my_rank;
}
else{
my_left_fork = my_rank;
my_right_fork = (my_rank + 1) % thread_count;
}
while(1){
printf("Philosopher %ld is thinking\n", my_rank);
//usleep( (rand()%91 + 10)*1000 ); //think 10-100 ms
usleep(50);
printf("Philosopher %ld is trying\n", my_rank);
sem_wait(&sem_fork[my_left_fork]);
sem_wait(&sem_fork[my_right_fork]);
printf("Philosopher %ld is eating\n", my_rank);
//usleep( (rand()%91 + 10)*1000 ); //eating 10-100 ms
usleep(100);
sem_post(&sem_fork[my_left_fork]);
sem_post(&sem_fork[my_right_fork]);
}
}
