【作業系統】“哲學家進餐”問題

“哲學家進餐”問題

有五個哲學家,他們的生活方式是交替地進行思考和進餐。他們共用一張圓桌,分別坐在五張椅子上。

在圓桌上有五個碗和五支筷子,平時一個哲學家進行思考,飢餓時便試圖取用其左、右最靠近他的筷子,只有在他拿到兩支筷子時才能進餐。進餐完畢,放下筷子又繼續思考。

圖示

哲學家進餐問題可看作是併發程序併發執行時處理共享資源的一個有代表性的問題。

圖示

此演算法可以保證不會有相鄰的兩位哲學家同時進餐。

若五位哲學家同時飢餓而各自拿起了左邊的筷子,這使五個訊號量 chopstick 均為 0,當他們試圖去拿起右邊的筷子時,都將因無筷子而無限期地等待下去,即可能會引起死鎖。

哲學家進餐問題的改進解法

  • 方法一:至多隻允許四位哲學家同時去拿左筷子,最終能保證至少有一位哲學家能進餐,並在用完後釋放兩隻筷子供他人使用。
  • 方法二:僅當哲學家的左右手筷子都拿起時才允許進餐。
  • 方法三:規定奇數號哲學家先拿左筷子再拿右筷子,而偶數號哲學家相反。

方法一

至多隻允許四位哲學家同時去拿左筷子,最終能保證至少有一位哲學家能進餐,並在用完後釋放兩隻筷子供他人使用。

設定一個初值為 4 的訊號量 r,只允許 4 個哲學家同時去拿左筷子,這樣就能保證至少有一個哲學家可以就餐,不會出現餓死和死鎖的現象。

原理:至多隻允許四個哲學家同時進餐,以保證至少有一個哲學家能夠進餐,最終總會釋放出他所使用過的兩支筷子,從而可使更多的哲學家進餐。

圖示

方法二

僅當哲學家的左右手筷子都拿起時才允許進餐。

解法 1:利用 AND 型訊號量機制實現。

原理:多個臨界資源,要麼全部分配,要麼一個都不分配,因此不會出現死鎖的情形。

圖示

解法 2:利用訊號量的保護機制實現。

原理:通過互斥訊號量 mutex 對 eat() 之前取左側和右側筷子的操作進行保護,可以防止死鎖的出現。

圖示

方法三

規定奇數號哲學家先拿左筷子再拿右筷子,而偶數號哲學家相反。

原理:按照下圖,將是 2,3 號哲學家競爭 3 號筷子,4,5 號哲學家競爭 5 號筷子。1 號哲學家不需要競爭。最後總會有一個哲學家能獲得兩支筷子而進餐。

圖示

圖示