OS - 哲學家問題
這學期有修資工必修的作業系統，本來想先整理作業一的觀念，結果作業二先寫完了，造就這篇的產生。
題目
Write a program to simulate the dining philosopher problem mentioned in the textbook using the Pthreads API on Linux.
Make sure that your implementation is able to handle 5 philosophers and is free of race condition.
Dining philosopher problem
中文翻作哲學家問題，今天有一群哲學家在餐桌上圍成圓圈想事情，他們想一想會肚子餓，肚子餓要吃東西，但一個人吃東西時需要拿左邊和右邊的筷子，兩個人中間只會有一隻筷子，一隻筷子同時最多一人使用。
假設有三位哲學家，依照座位編號分別為 1, 2, 3，則 1 號的右邊的筷子和 2 號的左邊的筷子是同一隻、2 號右邊的等於 3 號左邊的、3 號右邊的等於 1 號左邊的。
Race condition
以哲學家問題解釋，就是 1 號要拿右邊的筷子、2 號要拿左邊的筷子，造成一隻筷子同時被兩個人使用的錯誤情況。
分析
本題要解決的是五個人的哲學家問題，可以由哲學家問題的定義先知道程式主要流程是：
1. 想事情 -> 2. 肚子餓 -> 3. 吃東西 -> 1. 想事情 -> … 狀態只能從左到右，所以不會肚子餓一餓回去想事情。
但要如何解決搶同一個筷子的問題呢？pthread 有個叫做 mutex 的東西，A 可以用 mutex 把 x 鎖起來，B 就不能使用 x，而 A 把 x 解鎖後，B 才可以用，看起來就是我們需要的東西！
- 路人甲：「管理員！我想看《X》這本書！
- 管理員：「好，暫時先借你。」
- 路人乙：「我要借《X》這本書！」
- 管理員：「不行，有人借走了。」
- 路人甲：「《X》這本書還你。」
- 管理員：「好。」
- 路人乙：「我要借《X》這本書！」
- 管理員：「好，暫時先借你。」
此時，會遇到下一個問題：如果所有人同時拿右邊的筷子，會發現左邊的筷子都不能使用，所以他們放下右邊的筷子，過一段時間後又拿起右邊的筷子，不斷 loop。
我的解決方法是讓編號為奇數的人先拿左邊的筷子、偶數的拿右邊的筷子，這樣至少會有一個人是可以吃飯的。
實作
每個哲學家都是一個人(執行緒, thread)，筷子一次一個人用(鎖, lock)。
筷子編號 0 ~ 4 的話，編號 i 的左筷子編號是 i - 1，右筷子編號是 i % 5。
使用 sleep 模擬狀態轉移的等待時間。
剩下的應該是語法問題，要小心的是 printf 可能會因為執行過快，導致變數安插時被插隊，有必要的話可以選擇上一個輸出的鎖。
程式碼
#include <iostream>
#include <unistd.h>
#include <pthread.h>
#include <cstdlib>
#include <ctime>
using namespace std;
const int number = 5;
pthread_mutex_t lock[number];
pthread_t tids[number];
int name[number];
int state[5];
void* solve(void *args);
int main() {
srand(time(0));
for(int i=0; i<number; i++) {
state[i] = 0;
pthread_mutex_init(&lock[i], NULL);
}
for(int i = 0; i<number; i++) {
name[i] = i + 1;
pthread_create(&tids[i], NULL, solve, (void*)(&name[i]));
}
for(int i=0; i<number; i++) {
pthread_join(tids[i], NULL);
}
pthread_exit(NULL);
}
void* solve(void *args) {
int num = *(int*)args;
int left = num - 1, right = num % number;
while(true) {
if (state[num-1] == 0) {
printf("Philosopher %d is tkinking\n", num);
sleep(rand() % 3 + 1);
state[num-1] = 1;
printf("Philosopher %d is hungry\n", num);
sleep(rand() % 3 + 1);
}
if (state[num-1] != 1) continue;
if (pthread_mutex_trylock(&lock[num % 2 ? left : right])) {
continue;
}
if (pthread_mutex_trylock(&lock[num % 2 ? right : left])) {
pthread_mutex_unlock(&lock[num % 2 ? left : right]);
continue;
}
state[num-1] = 2;
printf("Philosopher %d is eating\n", num);
//for(int i=0; i<5; i++) cout << state[i] << " \n"[i==4];
sleep(rand() % 3 + 1);
pthread_mutex_unlock(&lock[num % 2 ? left : right]);
pthread_mutex_unlock(&lock[num % 2 ? right : left]);
state[num-1] = 0;
}
}