一肴楷、問題描述
五個沉默的哲學(xué)家圍坐在一個圓桌旁鸟妙，桌上放著幾碗意大利面。叉子被放置在每一對相鄰的哲學(xué)家之間奶甘。每個哲學(xué)家必須交替地思考和進(jìn)餐篷店。然而蔚龙，哲學(xué)家只能在有左右叉子的情況下才能吃意大利面炉菲。每個叉子只能被一個哲學(xué)家拿著，所以一個哲學(xué)家只能在沒有被另一個哲學(xué)家使用的情況下使用它矿辽。當(dāng)一位哲學(xué)家吃完飯后钉赁，他們需要把兩把叉子放下蹄殃，這樣其他人就可以享用這些叉子了。哲學(xué)家只能在他們有空的時候拿右手或左手的叉子你踩，在拿兩副叉子之前他們不能開始吃東西诅岩。每個哲學(xué)家有3種狀態(tài){thinking讳苦，trying，eating}吩谦。吃東西不受剩余的意大利面或胃空間的限制鸳谜，假設(shè)有一個無限的供給和一個無限的需求。問題是如何設(shè)計一種行為準(zhǔn)則(并發(fā)算法)式廷，以確保沒有哲學(xué)家挨餓咐扭；也就是說，每一種都可以永遠(yuǎn)在吃飯和思考之間交替懒棉，假設(shè)沒有一個哲學(xué)家可以知道其他人什么時候可能想吃飯或思考草描。
二、概要設(shè)計
編程語言使用IEEE Posix Thread庫與C語言實現(xiàn)策严。本次實驗采用多線程解決哲學(xué)家就餐問題穗慕。由于哲學(xué)家的刀叉是共享變量，所以使用信號量實現(xiàn)互斥妻导。線程個數(shù)(-n)即為哲學(xué)家個數(shù)逛绵，同時為每個叉子定義對應(yīng)的信號量。每個哲學(xué)家在試圖使用餐叉的時候需要先進(jìn)行sem_wait倔韭，當(dāng)拿到兩個餐叉后术浪，哲學(xué)家就能eating，eating完之后使用sem_post解鎖這兩個餐叉寿酌。
三胰苏、避免死鎖的策略
method1：
解法：允許最多 thread_count - 1 個哲學(xué)家同時進(jìn)入餐廳嘗試獲取餐叉，剩下的一個哲學(xué)家只有在有人吃完出去的時候才進(jìn)去醇疼。這樣就能保證起碼有一個人能夠同時獲得兩個餐叉硕并，從而eating，避免大家都處于trying的狀態(tài)秧荆。這種解法也能理解為引入一個餐廳服務(wù)生倔毙，哲學(xué)家必須經(jīng)過他的允許才能拿起餐叉。當(dāng)同時有 thread_count - 1 個餐叉被請求時乙濒，若是其他哲學(xué)家請求最后一個餐叉陕赃，服務(wù)生會讓他等待。
實現(xiàn)方法：增加一個信號量sem_waiter颁股，其初始值為thread_count - 1么库，每個線程trying時會先sem_wait(&sem_waiter)，在請求到兩個餐叉并且eating后甘有，再解鎖兩個叉子并使用sem_post(&sem_waiter)通知服務(wù)生廊散。
method2：
解法：使用非對稱解決方案。即單號的哲學(xué)家先拿起左邊的叉子梧疲，接著右邊的叉子允睹；而雙號的哲學(xué)家先拿起右邊的叉子运准，接著左邊的叉子。
實現(xiàn)方法：獲取當(dāng)前線程的編號缭受，如果是奇數(shù)號線程就先請求左邊的餐叉胁澳，然后請求右邊的餐叉；如果是偶數(shù)好線程就先請求右邊的餐叉米者，然后請求左邊的餐叉韭畸。
四、實驗
編譯：gcc -g -Wall -o philosopher philosopher.c -lpthread
運行：./philosopher -normal n 哲學(xué)家個數(shù) ./philosopher -method1 n 哲學(xué)家個數(shù) ./philosopher -method2 n 哲學(xué)家個數(shù)
五蔓搞、分析
1. -normal
正常狀態(tài)下哲學(xué)家遵守以下規(guī)則：
哲學(xué)家在左邊的叉子可用（沒有其他人拿起）之前處于思考狀態(tài)胰丁。如果左邊的叉子可用，就拿起來喂分。
哲學(xué)家等待右邊的叉子可用锦庸。如果右邊的叉子可用，就拿起來蒲祈。
如果兩個叉子都已經(jīng)拿起來甘萧，開始吃意大利面，每次吃面都花費同樣的時間梆掸。
吃完后先放下左邊的叉子扬卷。
然后放下右邊的叉子。
-
開始思考（進(jìn)入一個循環(huán)）
但這種解法是失敗的酸钦，當(dāng)每個哲學(xué)家都拿起左側(cè)的叉子怪得，等待右側(cè)的叉子可用時，就會進(jìn)入死鎖狀態(tài)卑硫，每個哲學(xué)家將永遠(yuǎn)都在等待（右邊的）另一個哲學(xué)家放下叉子汇恤。
2. -method1
至多只允許四個哲學(xué)家同時進(jìn)餐，以保證至少有一個哲學(xué)家能夠進(jìn)餐拔恰，最終總會釋放出他所使用過的兩支筷子，從而可使更多的哲學(xué)家進(jìn)餐基括。以下將sem_waiter作為信號量颜懊，只允許thread_count - 1個哲學(xué)家同時進(jìn)入餐廳就餐，這樣就能保證至少有一個哲學(xué)家可以就餐风皿，而申請進(jìn)入餐廳的哲學(xué)家進(jìn)入sem_waiter的等待隊列河爹，根據(jù)FIFO的原則，總會進(jìn)入到餐廳就餐桐款，因此不會出現(xiàn)餓死和死鎖的現(xiàn)象咸这。
3.-method2
規(guī)定奇數(shù)號的哲學(xué)家先拿起他左邊的筷子，然后再去拿他右邊的筷子魔眨；而偶數(shù)號的哲學(xué)家則相反媳维。按此規(guī)定酿雪，將是1、2號哲學(xué)家競爭1號筷子侄刽，3指黎、4號哲學(xué)家競爭3號筷子。即五個哲學(xué)家都競爭奇數(shù)號筷子州丹，獲得后醋安，再去競爭偶數(shù)號筷子，最后總會有一個哲學(xué)家能獲得兩支筷子而進(jìn)餐墓毒。而申請不到的哲學(xué)家進(jìn)入阻塞等待隊列吓揪，根FIFO原則，則先申請的哲學(xué)家會較先可以吃飯所计，因此不會出現(xiàn)餓死的哲學(xué)家柠辞。
六、源代碼
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#include <string.h>
long thread_count; //線程個數(shù)醉箕，即哲學(xué)家個數(shù)
sem_t *sem_fork; //定義一組餐叉的信號量
sem_t sem_waiter; //method1中用到的信號量钾腺，用于確保至少一個人不能進(jìn)餐
void *Philo_normal(void *rank); //一般方法，會陷入死鎖
void *Philo_method1(void *rank); //方法1讥裤，服務(wù)生方法
void *Philo_method2(void *rank); //方法2放棒，非對稱解決方案
int main(int argc, char *argv[])
{
long thread;
pthread_t *thread_handles;
//獲取線程個數(shù)，本實驗中也代表哲學(xué)家人數(shù)
thread_count = strtol(argv[2], NULL, 10);
thread_handles = malloc (thread_count * sizeof(pthread_t));
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);
}
//創(chuàng)建線程
for(thread = 0; thread < thread_count; thread++ ){
//根據(jù)參數(shù)進(jìn)入相應(yīng)的處理函數(shù)
if(strcmp(argv[1], "-normal") == 0)
pthread_create(&thread_handles[thread], NULL, Philo_normal, (void *)thread);
else if(strcmp(argv[1], "-method1") == 0)
pthread_create(&thread_handles[thread], NULL, Philo_method1, (void *)thread);
else if(strcmp(argv[1], "-method2") == 0)
pthread_create(&thread_handles[thread], NULL, Philo_method2, (void *)thread);
}
//停止線程
for(thread = 0; thread < thread_count; thread ++ )
pthread_join(thread_handles[thread], NULL);
//銷毀餐叉信號量
for(long i = 0; i < thread_count; i ++ ){
sem_destroy(&sem_fork[i]);
}
//銷毀服務(wù)生信號量
sem_destroy(&sem_waiter);
//釋放空間
free(thread_handles);
free(sem_fork);
return 0;
}
//一般方法己英，會陷入死鎖
void *Philo_normal(void *rank)
{
long my_rank = (long)rank;
long my_left_fork, my_right_fork; //表示每個哲學(xué)家左右的叉子
my_left_fork = my_rank;
my_right_fork = (my_rank + 1) % thread_count;
while(1){
printf("Philosopher %ld is thinking\n", my_rank);
//把進(jìn)程掛起一段時間间螟， 單位是微秒（百萬分之一秒）；
//usleep( (rand()%91 + 10)*1000 );
//本來應(yīng)該隨機掛起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厢破，服務(wù)生方法
void *Philo_method1(void *rank)
{
long my_rank = (long)rank;
//哲學(xué)家左右的叉子
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信號量確保每個時刻最少一個人沒有進(jìn)去就餐
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 *rank)
{
long my_rank = (long)rank;
//表示哲學(xué)家左右的叉子
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]);
}
}
七摩泪、參考
維基百科-Dining_philosophers_problem：http://en.wikipedia.org/wiki/Dining_philosophers_problem
哲學(xué)家就餐問題解釋：https://wenku.baidu.com/view/df1a6a4e2b160b4e767fcf4c.html
