摘要：如今良好的交互性、并行性、同步性早已是大多數(shù)計(jì)算機(jī)操作系統(tǒng)不可或缺的功能，無論是基于單核還是多核計(jì)算機(jī)，倘若沒有以上幾個(gè)性能，則毫無疑問是糟糕的操作系統(tǒng)。哲學(xué)家就餐問題是操作系統(tǒng)研究領(lǐng)域中一個(gè)著名而有趣的問題，是從計(jì)算機(jī)實(shí)現(xiàn)偽同步并行功能研究中演化而來的經(jīng)典進(jìn)程間通訊問題，對(duì)研究同步性有很大的幫助和啟發(fā)。該文探究了哲學(xué)家問題的原理，并使用C語言對(duì)其進(jìn)行了模擬。

關(guān)鍵詞：操作系統(tǒng)同步性；死鎖競(jìng)爭(zhēng)；哲學(xué)家就餐問題

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）15-3516-06

1965年，著名的數(shù)學(xué)家Dijkstra提出了一個(gè)他稱為“哲學(xué)家就餐”的問題，并親自解決之。自那時(shí)起，每個(gè)發(fā)明同步原語的人都希望通過解決此問題來展示其同步原語的精妙之處。

同步原語這一概念，被用于描述進(jìn)程的執(zhí)行動(dòng)作，在操作系統(tǒng)中的地位舉足輕重，其對(duì)實(shí)現(xiàn)操作系統(tǒng)程序的并行性和同步性有著奠基性的作用。那么，什么是同步原語呢？

在計(jì)算機(jī)的操作系統(tǒng)中，程序一般被抽象成進(jìn)程這一概念。在一臺(tái)計(jì)算機(jī)中，所有存在的進(jìn)程要實(shí)現(xiàn)計(jì)算、訪問資源等一系列復(fù)雜的操作。

當(dāng)今計(jì)算機(jī)能夠依靠相當(dāng)少的CPU（相對(duì)于進(jìn)程龐大的數(shù)量來說，一兩個(gè)或者四個(gè)CPU簡(jiǎn)直少得可憐）實(shí)現(xiàn)程序并行的功能正是基于同步原語：計(jì)算機(jī)內(nèi)的進(jìn)程都被分為運(yùn)行時(shí)間相同的原子執(zhí)行動(dòng)作，即一個(gè)復(fù)雜的動(dòng)作由許多子動(dòng)作組成，這些子動(dòng)作不能再分成更小的子動(dòng)作。同步原語中的原語便是指這些子動(dòng)作。

對(duì)于CPU來說，每次只執(zhí)行一個(gè)原子動(dòng)作，這個(gè)原子動(dòng)作不一定是來自于相同的進(jìn)程，一般按照某種規(guī)則來運(yùn)行原子動(dòng)作，比如在一段時(shí)間內(nèi)，一個(gè)進(jìn)程只能占用CPU運(yùn)行若干個(gè)屬于它自已的原子動(dòng)作。由于CPU的運(yùn)行速度非常快，當(dāng)下普通CPU其一秒內(nèi)的運(yùn)算速度都可以以億為單位計(jì)量，因此在一段時(shí)間內(nèi)，可以讓很多進(jìn)程都完成一部分原子動(dòng)作，在人類的角度看來，就好像程序并行運(yùn)行了。

在這里，就可以看到同步原語的必要性。若無同步原語的話，進(jìn)程便會(huì)胡作非為了，因?yàn)橛?jì)算機(jī)沒有規(guī)定一個(gè)進(jìn)程能執(zhí)行動(dòng)作到何種地步，對(duì)于進(jìn)程間的競(jìng)爭(zhēng)問題和通訊問題，即使有了很好的策略也無法控制進(jìn)程執(zhí)行的結(jié)果。例如，對(duì)于一個(gè)緩沖區(qū)，一個(gè)進(jìn)程獲得了它的修改權(quán)，但是操作系統(tǒng)沒有確定原子動(dòng)作，這個(gè)進(jìn)程不知道會(huì)執(zhí)行到哪一步，于是，在操作系統(tǒng)還沒有來得及告知其他進(jìn)程時(shí)，就可能會(huì)有另一個(gè)無知的進(jìn)程也獲得了該緩沖區(qū)的修改權(quán)，從而與前一個(gè)進(jìn)程一同修改緩沖區(qū)的內(nèi)容，這將會(huì)導(dǎo)致世界大亂。

同時(shí)，毫無疑問，在這里，存在一個(gè)很現(xiàn)實(shí)的問題。

正如上所述，計(jì)算機(jī)中的進(jìn)程數(shù)往往多得驚人，光是操作系統(tǒng)本身就需要并行運(yùn)行眾多進(jìn)程，再加上用戶開啟的各種應(yīng)用進(jìn)程（比如用戶想聽MP3歌曲，便開啟了一個(gè)MP3播放器，這一個(gè)播放器可能包含不止一個(gè)進(jìn)程），其數(shù)目可能會(huì)非常大。然而，計(jì)算機(jī)的硬件設(shè)備卻極其有限，例如，目前的普通計(jì)算機(jī)只有一或者兩個(gè)中央處理器（CPU），只有有限的內(nèi)存，只有一個(gè)顯示器，這么多進(jìn)程要同時(shí)使用這些相對(duì)來說少得可憐的硬件設(shè)備，若沒有一個(gè)優(yōu)秀的訪問機(jī)制，程序間便會(huì)出亂子。例如客戶開啟了一個(gè)文本編輯進(jìn)程用來編寫一篇文章，在某個(gè)時(shí)候，這篇文章的代碼被保存在內(nèi)存中的一些位置上，過了一段時(shí)間，這個(gè)客戶又開啟了一個(gè)視頻播放器，而原先的文本編輯進(jìn)程仍沒有關(guān)閉，播放器要使用的內(nèi)存位置正好與編輯器所占用的位置有沖突，此時(shí)該如何是好？當(dāng)文本編輯程序不適用CPU而讓視屏播放器使用CPU時(shí)，該如何保存文本編輯器的記錄？文本編輯器修改了內(nèi)存上的內(nèi)容，視屏播放器如何知道？如果這些進(jìn)程不相互溝通各自的信息，那相信該用戶不久便會(huì)精神崩潰。

因此，進(jìn)程間必須實(shí)現(xiàn)良好的信息共享策略，哲學(xué)家就餐問題便是研究這類策略的一個(gè)經(jīng)典抽象數(shù)學(xué)問題。

1 哲學(xué)家就餐問題分析

說起哲學(xué)家就餐問題，就不得不與計(jì)算機(jī)操作系統(tǒng)中的進(jìn)程間通訊（ipc）問題掛上鉤。

在進(jìn)程間通訊問題中，有一個(gè)簡(jiǎn)單而基本的模型，就是存在多個(gè)進(jìn)程，而只存在一個(gè)緩沖區(qū)。非常明顯，這個(gè)緩沖區(qū)的數(shù)據(jù)可以被多個(gè)進(jìn)程讀取，這不會(huì)造成任何后果。但是，一旦有進(jìn)程要改寫這個(gè)緩沖區(qū)的內(nèi)容，那麻煩就來了，首先，不能允許多個(gè)進(jìn)程同時(shí)改寫緩沖區(qū)的內(nèi)容，因?yàn)橐坏┯卸鄠€(gè)進(jìn)程同時(shí)修改，那該以哪個(gè)進(jìn)程的操作為準(zhǔn)呢？并且每個(gè)進(jìn)程獲取的緩沖區(qū)內(nèi)容都不是最新的，每個(gè)進(jìn)程也不知道其他進(jìn)程相對(duì)緩沖區(qū)內(nèi)容做什么手腳，最終緩沖區(qū)中的內(nèi)容也不知道會(huì)是什么，因?yàn)檫@些進(jìn)程會(huì)不顧進(jìn)程的感受，自顧自的往緩沖區(qū)儲(chǔ)存自已修改后的數(shù)據(jù)。

對(duì)于上文所描述的進(jìn)程通訊問題，早已有眾多的研究和解決方案誕生于世，在這里就不一一贅述。

哲學(xué)家就餐問題則是對(duì)進(jìn)程間通訊問題的一個(gè)發(fā)展，其有利于解決進(jìn)程間由競(jìng)爭(zhēng)而產(chǎn)生的不良后果，能檢測(cè)和防止進(jìn)程由于競(jìng)爭(zhēng)資源而產(chǎn)生的一系列問題。

哲學(xué)家就餐問題可以簡(jiǎn)單描述如下：五個(gè)哲學(xué)家圍坐在一張圓桌周圍，每個(gè)人面前擺著一盤誘人的意大利通心粉，由于通心粉太滑，必須用兩把叉子才能吃到，同時(shí)，在相鄰的盤子間只有一把叉子。此問題描述的情形可見下圖：

這些哲學(xué)家坐在餐桌邊會(huì)有兩種活動(dòng)：吃飯和思考。每當(dāng)一個(gè)哲學(xué)家感到餓了，他便試圖去拿盤子左邊和右邊的叉子，一次只拿一把，不分左右的次序，若成功的得到了兩把叉子，便開始吃飯，吃完便放下叉子繼續(xù)思考。這里問題的關(guān)鍵是：在進(jìn)程被分為眾多原子動(dòng)作且這些原子動(dòng)作被打亂而不知什么時(shí)候會(huì)被CPU執(zhí)行的情況下，能否為每個(gè)哲學(xué)家寫出一段代表其行為的程序，使得不會(huì)產(chǎn)生令人尷尬的每個(gè)人都無法吃飯的情形？（這可能是死鎖狀態(tài)，例如，每個(gè)哲學(xué)家都拿到了盤子左邊的叉子，于是，沒有一個(gè)人有兩個(gè)叉子，這些可憐的人便陷入了永遠(yuǎn)試圖去拿右邊叉子的境地，導(dǎo)致沒人吃得上飯，也沒人能夠?qū)Ｐ乃伎迹４颂?，哲學(xué)家代表的是進(jìn)程，叉子則代表的是緩沖區(qū)。

幸運(yùn)的是，對(duì)于此問題，還是有解決方法的，為每個(gè)哲學(xué)家所編寫的程序大致代碼如下：

如上所示，其中，justDoIt函數(shù)為每個(gè)哲學(xué)家的主執(zhí)行函數(shù)，take_forks函數(shù)為哲學(xué)家感到饑餓試圖拿起叉子時(shí)的函數(shù)，首先五個(gè)哲學(xué)家先用down這一原語動(dòng)作對(duì)互斥量mutex進(jìn)行測(cè)試，確保只有一個(gè)哲學(xué)家能檢測(cè)叉子的狀態(tài)（因?yàn)閷碛锌赡芨淖儾孀拥臓顟B(tài)，即修改緩沖區(qū)內(nèi)容），然后開始對(duì)叉子的測(cè)試，看是否能拿起兩個(gè)叉子，若可以則拿起叉子吃飯，若不行則放下叉子，為其他人提供機(jī)會(huì)（避免占著資源不用，防止死鎖），最后離開緩沖區(qū)，使用Up這一原語動(dòng)作對(duì)mutex進(jìn)行操作以告知其他哲學(xué)家可以進(jìn)入緩沖區(qū)檢查叉子的狀態(tài)。在test函數(shù)中，使用Up這一原語動(dòng)作對(duì)哲學(xué)家的狀態(tài)進(jìn)行改變，若哲學(xué)家無法吃飯，則take_forks函數(shù)最后的down原語動(dòng)作會(huì)使哲學(xué)家進(jìn)程阻塞，一直保持饑餓想吃飯的狀態(tài)。Put_forks函數(shù)則是哲學(xué)家用餐完后恢復(fù)思考的函數(shù)，首先哲學(xué)家先互斥地進(jìn)入緩沖區(qū)，然后將自已的狀態(tài)改為思考狀態(tài)，再檢查其左右是否可以吃飯，最后離開緩沖區(qū)。

此解決方案使用了兩個(gè)互斥的信號(hào)量：一個(gè)用來互斥地訪問代表叉子是否能用的緩沖區(qū)；另一個(gè)為代表哲學(xué)家狀態(tài)的信號(hào)量數(shù)組，使得只能唯一地修改狀態(tài)，保持每個(gè)哲學(xué)家用test函數(shù)檢測(cè)狀態(tài)的唯一性。

使用這個(gè)解決方案，不僅不會(huì)產(chǎn)生死鎖，還會(huì)使得程序得到最大的并行度。

2 C語言模擬實(shí)現(xiàn)

根據(jù)上文的分析，作者使用了C語言對(duì)解決哲學(xué)家問題的程序進(jìn)行了編程，其源代碼如下：

可以看到，程序完全模擬了每個(gè)哲學(xué)家所執(zhí)行的每一步，并最終每個(gè)哲學(xué)家都用完餐。

3 總結(jié)

本文探討和分析了哲學(xué)家問題，對(duì)其解決方案進(jìn)行了探究，并使用C語言對(duì)此問題進(jìn)行了具體的模擬。

哲學(xué)家問題是進(jìn)程間通訊問題（ipc）中著名且有趣的問題，是解決同步并行問題的經(jīng)典模型之一，適用于很多原語的測(cè)試，是一個(gè)具有啟發(fā)意義的經(jīng)久不衰的問題。

參考文獻(xiàn)：

[1] Andrew S.Tanenbaum&Albert S.Woodhull.操作系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[M].北京：電子工業(yè)出版社，2007.

[2] William Stallings.操作系統(tǒng)：精髓與設(shè)計(jì)原理[M].北京：機(jī)械工業(yè)出版社，2010.

[3] Abraham Silberschatz，Peter Baer Galvin，Greg Gagne.操作系統(tǒng)概念[M].北京：高等教育出版社，2010.

[4] Marshall Kirk McKusick，George V. Neville-Neil. FreeBSD操作系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[M].北京：中國電力出版社，2008.