1. 哲學家進餐問題:

問題描述: 五個哲學家在一個圓桌上進餐，每人的面前放了一盤意大利面，兩個盤子之間有一個叉子，但是由于盤子里面的面條十分光滑，需要兩個叉子才能進行就餐行為。餐桌的布局如下圖所示:

假設哲學家的生活中只有兩個活動：吃飯和思考[吃飯維持自身之生存，思考探究生存之意義]，當然這樣的哲學家在現實之中是不存在的。當一個哲學家在殫精竭慮之時，饑餓感隨之而來，這是他會拿起左右手邊的兩個叉子來想享用這俗世之中的美味。酒足飯飽之后，又"躲進小樓成一統，管他春夏與秋冬"去了。問題是：%20怎樣才能保證每個哲學家都能拿到兩個筷子而不會出現死鎖的情形呢?[一個典型的死鎖情形是:%20每個哲學家同時拿起右手邊的叉子，都得不到左手邊的叉子。]

上述死鎖情形可以通過下面的代碼描述:

%201%20#define%20N%205%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20number%20of%20philosophers%20*/%202%20%203%20void%20philosopher(int%20i)%20%20%20%20%20%20%20%20%20%20%20%20/*%20i:%20philosopher%20number:%20from%200%20to%204%20*/%204%20{%205%20%20%20%20%20%20%20while(TRUE):%206%20%20%20%20%20%20%20{%207%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20think();%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20philosppher%20is%20thinking%20*/%208%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20take_fork(i);%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20take%20the%20left%20fork%20*/%209%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20take_fork((i+1)%20%%20N);%20%20%20%20%20/*%20take%20right%20fork;%20%%20is%20a%20modulo%20Operator%20*/10%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20eat();%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20yum-yum,%20spaghetti%20*/11%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20put_fork(i);%20%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20put%20back%20the%20left%20fork%20on%20the%20tabel%20*/12%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20put_fork((i+1)%20%%20N);%20%20%20%20%20%20/*%20put%20back%20the%20right%20fork%20on%20the%20table%20*/13%20%20%20%20%20%20%20}%20%20%20%20%20%20%20%2014%20}%20%20%20%20%20%20%20%20%20%20%20%20

那么如何解決這個問題呢?%20我們經過一番思考得到下面一些方案:

方案1：%20當一個哲學家拿起左手邊的叉子的時候，判斷他是否可以拿到右手邊的叉子;%20如果右手邊的叉子正被別人使用著，那么他就放下左手邊的叉子，等待一段時間之后，重復上面的過程。[這個方案仍然解決不了死鎖問題，如果五個哲學家同時執行上述過程，都得不到叉子，然后放下，等待相同的一段時間后在重復上述過程......然后是沒完沒了的重復：Until%20the%20end%20of%20the%20world(直到世界末日)]

方案2%20:%20將上述方案中等待一定量的時間改為等待隨機一段時間。[看上去這個方案可以解決死鎖問題，但是我們不能依賴這個隨機值，況且計算機世界里面哪有什么絕對的隨機數呢？我們不能因為一件事發生的概率極小而斷定這件事不會發生，這在賭徒們的牌桌上是可以存在的，但作為一個理性的人，這個念頭是荒謬可笑的，就像是將頭埋在沙子里的鴕鳥。試想一段控制核電站堆芯工作的程序使用上述策略，那么人類的滅亡也就不遠了。]

方案3：%20在上面的代碼的think()語句作為一個關鍵代碼段，用一個互斥信號量(mutex)來控制每個哲學家進程對關鍵代碼段的訪問。[從理論上來說，這個方案是可行的;但從實際效率上考慮，這個方案是不合理的：一段時間內至多只有一個哲學家在進餐。]

方案4：

%201%20#define%20N%20%20%20%20%20%20%20%20%20%20%20%205%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20number%20of%20philosophers%20*/%202%20#define%20LEFT%20%20%20%20%20%20%20%20(i-1)%20%%20N%20%20%20%20%20/*%20number%20of%20i's%20left%20neighbor%20*/%203%20#define%20RIGHT%20%20%20%20%20%20%20%20(i+1)%20%%20N%20%20%20%20%20/*%20number%20of%20i's%20right%20neighbor%20*/%204%20#define%20THINKING%20%20%20%200%20%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20philosopher%20is%20thinking%20*/%205%20#define%20HUNGRY%20%20%20%20%20%201%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20philosopher%20is%20trying%20to%20get%20forks%20*/%206%20#define%20EATING%20%20%20%20%20%202%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20philosopher%20is%20eating%20*/%207%20%208%20typedef%20int%20semaphore;%20%20%20%20%20%20%20%20%20%20%20%20/*%20semaphores%20are%20a%20special%20kind%20of%20int%20*/%209%20int%20state[N];%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20array%20to%20keep%20track%20of%20every%20philospphers'%20state%20*/10%20semaphore%20mutex%20=%201;%20%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20mutual%20exclusion%20for%20critical%20regions%20*/11%20semaphore%20s[N];%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20one%20semaphore%20per%20philosopher%20*/12%2013%20void%20philosopher(int%20i)14%20{15%20%20%20%20%20while(TRUE)16%20%20%20%20%20{17%20%20%20%20%20%20%20%20%20think();18%20%20%20%20%20%20%20%20%20take_forks(i);19%20%20%20%20%20%20%20%20%20eat();20%20%20%20%20%20%20%20%20%20put_forks(i);21%20%20%20%20%20}22%20}23%2024%20void%20take_forks(int%20i)25%20{26%20%20%20%20%20down(&mutex);27%20%20%20%20%20state[i]%20=%20HUNGRY;28%20%20%20%20%20test(i);29%20%20%20%20%20up(&mutex);30%20%20%20%20%20down(&s[i]);%20%20%20%20%20%20%20[如過沒有請求到叉子，那么阻塞]31%20}32%2033%20void%20put_forks(int%20i)34%20{35%20%20%20%20%20down(&mutex);36%20%20%20%20%20state[i]%20=%20THINKING;37%20%20%20%20%20test(LEFT(i));38%20%20%20%20%20test(RIGHT(i));39%20%20%20%20%20up(&mutex);40%20}41%2042%20void%20test(i)43%20{44%20%20%20%20%20if(state[i]%20==%20HUNGRY%20&&%20state[LEFT(i)]%20!=%20EATING%20&&%20state[RIGHT(i)]%20!=%20EATING)45%20%20%20%20%20{46%20%20%20%20%20%20%20%20%20state[i]%20=%20EATING;47%20%20%20%20%20%20%20%20%20up(&s[i]);48%20%20%20%20%20}49%20}

[注意這里并沒有將一個哲學家所能執行的所有動作都放在一個關鍵代碼段中，而是用互斥信號量控制take_forks和get_forks過程，以保證每次只有一個哲學家在申請叉子或釋放叉子。但可以有多個哲學家處于EATING的狀態。]

2.%20讀者和寫者問題:

哲學家進餐問題描述的是多個進程對有限資源的互斥訪問問題，另外一個問題是"讀者--寫者"問題，描述的是多個進程對數據訪問的問題。

要求:%20可以有多個用戶同時讀取數據，但一個時刻只能有一個用戶在更新數據，并且在更新數據期間，不容許其他用戶更新或讀取數據。

下面是解決讀者--寫者問題的一個方案:

%201%20typedef%20int%20semaphore;%202%20semaphore%20mutex%20=%201;%20%20%20%20%20%20%20%20%20%20%20%20/*%20[控制對讀者計數器rc的訪問]%20*/%203%20semaphore%20db%20=%201;%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20[控制對數據的訪問]%20*/%204%20int%20rc%20=%200;%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20[讀者數計數器，初始化為0]%20*/%205%20%206%20void%20reader(void)%207%20{%208%20%20%20%20%20while(true)%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20["久到離譜，一直停不下來"]%20*/%209%20%20%20%20%20{10%20%20%20%20%20%20%20%20%20down(&mutex);%20%20%20%20%20%20%20%20%20%20%20/*%20[對讀者數計數器互斥訪問]%20*/11%20%20%20%20%20%20%20%20%20rc%20=%20rc%20+%201;%20%20%20%20%20%20%20%20%20%20%20%20/*%20[讀者計數器+1]%20*/12%20%20%20%20%20%20%20%20%20if%20(rc%20==%201)%20down(&db);%20/*%20[當有用戶在讀取數據時，沒有人可以修改數據]%20*/13%20%20%20%20%20%20%20%20%20up(&mutex);14%2015%20%20%20%20%20%20%20%20%20read_data();%20%20%20%20%20%20%20%20%20%20%20%20/*%20[讀取數據]%20*/16%2017%20%20%20%20%20%20%20%20%20down(&mutex);18%20%20%20%20%20%20%20%20%20rc%20=%20rc%20-%201;%20%20%20%20%20%20%20%20%20%20%20%20/*%20[讀取數據完畢，離開]%20*/19%20%20%20%20%20%20%20%20%20if(rc%20==%200)%20up(&db);%20%20%20%20/*%20[如果當前沒有用戶讀取數據，那么容許其他用戶的修改]%20*/20%20%20%20%20%20%20%20%20%20up(&mutex);21%20%20%20%20%20%20%20%20%20use_data_read();22%20%20%20%20%20}23%20}24%2025%20void%20writer(void)26%20{27%20%20%20%20%20while(true)%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20/*%20[you%20konw%20that]%20*/28%20%20%20%20%20{29%20%20%20%20%20%20%20%20%20think_up_data();%20%20%20%20%20%20%20/*%20[準備好要更新的數據]%20*/30%20%20%20%20%20%20%20%20%20down(&db);31%20%20%20%20%20%20%20%20%20write_data();32%20%20%20%20%20%20%20%20%20up(&db);33%20%20%20%20%20}34%20}

當然，這個方案也存在一些問題：當有讀者在讀取數據，并且有其他讀者源源不斷的到來的時候，寫者進程將永遠處于阻塞狀態。[當每2秒出現一個讀者，而每個讀者的平均讀取時間是5秒時就會出現這個情形。]

　　解決這個問題的一種方案是當寫者進程出現時，寫者進程之后到來的讀者進程都被阻塞，當先前讀者讀取完畢后寫者就可以修改數據了。這個方案雖然可以保證寫者不會處于饑餓狀態，但卻以破壞系統中程序的并發性為代價。

%20%20%20另一種解決方案參見"讀者--寫者"問題的提出者Courtois的論文:cs.nyu.edu/~lerner/sPRing12/Read04-ReadersWriters.pdf;

3.%20睡覺的理發師問題:

 1 #define       CHAIRS        5   /* [等待區座椅數目] */ 2  3 typedef int semaphore; 4  5 semaphore customers = 0;        /* [客戶信號量：初始化為0] */ 6 semaphore barbers = 0;          /* [理發師信號量: 初始化為0] */ 7 semaphore nutex = 1;            /* [互斥信號量: 初始化為1] */ 8  9 void barber(void)10 {11     while(true)12     {13         down(&customers);        /* [如果customers = 0 那么理發師就回去睡覺] */14         down(&mutex);            /* [獲取對waiting變量的訪問權限] */15         waiting = waiting - 1;16         up(&barbers);            /* [一個理發師來給用戶理發] */17         up(&mutex);18         cut_hair();19     }20 }21 22 void customer(void)23 {24     down(&mutex);25     if(waiting < CHAIRS)        /* [如果空閑區沒有椅子，那么客戶離開] */26     {27         waiting = waiting + 1;  /* [增加等待理發的客戶數目] */28         up(customers);          /* [喚醒理發師] */29         up(mutex);30         down(barbers);          /* [使用一個理發師] */31         get_haircut();    32     }33     else34     {35         up(&mutex);36     }37 }