經典同步問題的死鎖解決方案

謝士春

宿州學院信息工程學院,安徽宿州,234000

?

經典同步問題的死鎖解決方案

謝士春

宿州學院信息工程學院,安徽宿州,234000

哲學家就餐問題和吸煙者問題是兩個經典的進程同步問題模型，它們均是對多個競爭進程互斥地訪問有限資源(例如I/O設備)問題的建模。針對這兩類進程步問題，分析不合理地使用PV操作導致死鎖產生的原因，提出了阻止死鎖產生的詳細方案。對此類問題的深度剖析有助于學生深刻地理解操作系統原理中的資源共享、進程同步及死鎖等重要概念。

死鎖；進程同步；信號量；哲學家就餐問題；吸煙者問題

1 預備知識

在多道程序環境下，進程有異步和同步兩種并發執行方式。異步執行是指運行中的各進程在操作系統的調度下以不可預知的速度向前推進。異步執行的進程大多沒有時序要求，不存在“執行結果與語句的特定執行順序有關”的條件競爭。然而存在一類協作進程，“保證數據的一致性”的前提要求它們必須按某種特定順序執行，并且遵守如下兩種限制[2]。

(1)R1(順序化執行)：進程A的eventA事件必須發生在進程B的eventB事件之前；

(2)R2(互斥執行)：進程A的eventA事件與進程B的event事件B不能同時發生。

把上述限制下多進程的運行狀態叫作進程的同步執行。進程同步執行時因存在著明顯的執行上的時序要求而相互等待。如果說進程異步是進程并發執行的自然結果，那么進程同步則需要程序員通過準確嵌入一些諸如加解鎖、信號量、管程等關鍵技術來確保實現。

信號量無疑是一個較為理想的同步工具。它最早由荷蘭科學家Edsger Dijkstra于1965年提出，該工具具有如下三個優點[2]：(1)僅需要兩個基本操作即可完成進程的同步和互斥，而且兩個原子操作代碼簡潔高效，易于擴充；(2)精心設計的信號量對象類似一條條“觸發器”規則，加上信號量機制的強制作用可以幫助程序員少犯錯誤；(3)信號量已在很多系統中實現，解決方案中有意識地選用信號量無疑將使進程更“瘦身”，運行更高效。

信號量技術的引入是對早期忙等型(busy waiting)進程控制變量(例如各種軟件鎖、Dekker算法和Peterson算法中各類標志變量)是個巨大的提升，但在使用過程中仍然存在不少缺點：一是不能隨時讀取信號量的值，必要時須重復定義一個跟蹤信號量值的普通變量，二是程序員對信號量的PV操作的正確使用與否沒有任何控制和保證(后來引入管程和條件變量，PV操作完全由編譯器而非程序員安排)，不合理地使用將導致進程饑餓甚至死鎖。

死鎖應盡可能阻止。系統死鎖導致諸進程將進入無法向前推進的僵持狀態，除非借助于外力[3]。死鎖的原因除了系統資源偏少之外，更多的是進程推進速度不當，或者說進程申請和釋放信號量的順序不合理所致，畢竟系統提供的資源是有限的。以哲學家就餐問題為例，若派發給每位哲學家一雙筷子(更準確地說，6支就足夠)，則一定不會死鎖。事實上，若信號量的PV操作順序處置得當，5支筷子同樣也可以保證不會發生死鎖。

其實，隨著時代的變遷和交通、印刷業、傳媒業的迅猛發展，再加上跨地域之間的藝術交流的日趨頻繁，早年以地域為特征的所謂“南宗”“北宗”乃至“海派”“浙派”，其地域特征和藝術分野正在慢慢消弭，如果溯本求源，有些流派本來就是同源同宗，一些流派之間不過是同干異枝或是同源異流的關系。

2 經典同步問題的死鎖解決方案

2.1 哲學家就餐問題

哲學家就餐問題(The Dinning Philosophers Problem)是經典的同步問題之一，對于多個競爭進程互斥地訪問有限資源(例如I/O設備)這一類問題的建模非常有用。用信號量機制解決本問題的基本算法[2-4]見表1。

表1 有死鎖風險的方案

當5個哲學家進程并發執行時，某個時刻恰好每個哲學家進程都執行語句2，并且成功申請到第i支筷子(相當于5個哲學家同時拿起他左邊的筷子)，接著他們又都執行語句3，申請第i+1支筷子。此時每個哲學家僅拿到一支筷子，另外一支只得無限等待下去，引起死鎖。在給出幾種有效阻止死鎖的方案之前，首先給出兩個斷言：

(1)系統中有N個并發進程。若規定每個進程需要申請2個某類資源，則當系統提供N+1個同類資源時，無論采用何種方式申請資源，一定不會發生死鎖。

分析：N+1個資源被N個進程競爭，由抽屜原理可知，則至少存在一個進程獲得2個以上的同類資源。這就是前面提到的哲學家就餐問題中5個哲學家提供6支筷子時一定不會發生死鎖的原因。

(2)系統中有N個并發進程。若規定每個進程需要申請R個某類資源，則當系統提供K=N*(R-1)+1個同類資源時，無論采用何種方式申請使用，一定不會發生死鎖。

分析：在最壞的情況下，每個進程都申請到R-1個同類資源，此時它們均阻塞。試想若系統再追加一個同類資源，則N個進程中必有一個進程獲得R個資源，死鎖解除。

結合以上分析，哲學家就餐問題可以被抽象描述為：系統中有5個并發進程，規定每個進程需要申請2個某類資源。若系統提供5個該類資源，在保證一定不會產生死鎖的前提下，最多允許多少個進程并發執行？假設允許N個進程，將R=2，K=5帶入上述公式，有N*(2-1)+1=5 ，所以N=4。也就意味著，如果在任何時刻系統最多允許4個進程并發執行，則一定不會發生死鎖。大多數哲學家就餐問題死鎖阻止算法都是基于這個結論。

方案1：增加一個信號量，控制最多有4個進程并發執行，算法見表2。

表2 無死鎖風險的方案之一

方案2：從5位哲學家中選擇其中一位改變申請筷子的次序，比如先右后左，其余哲學家仍采用先左后右，算法見表3。

當5個進程并發執行時，某時刻0號進程與4號進程均執行語句2，同時競爭0號筷子，爭奪結果必然會造成一方阻塞，從而導致整個系統變成4個哲學家競爭5支筷子的局面，則一定不會發生死鎖。

塔內鮑姆(Tanenbau)提供了一個阻止死鎖的算法[5]。該算法設置一個狀態變量，用來指明每個哲學家的狀態是思考中、就餐中，還是等待就餐(饑餓中)；一個信號量用來互斥訪問此狀態變量；另一信號量指示哲學家是否可以開始就餐(僅當左右筷子均可用時才可以)。需要注意的是第二個信號量不再代表筷子資源，而是“左右筷子均可用”的標志，這里不再贅述。除此之外，還有規定奇數號哲學家與偶數號哲學家采用不同的申請次序等算法。判定此類算法性能優劣的標準之一是能否達到最多允許4個哲學家同時就餐這一最大并發度，其次信號量的使用是否高效，是否存在著誤用和濫用問題也是設計算法時所要考慮的。

2.2 吸煙者問題(CigaretteSmokersProblem)

問題描述：一個煙草代理商和三個抽煙者。抽煙者若要抽煙，必須具有煙葉、煙紙和火柴。三個抽煙者中，一個有煙葉、一個有煙紙、一個有火柴。煙草代

表3 無死鎖風險的方案之二

理商會源源不斷地分別供應煙葉、 煙紙和火柴，并將它們放在桌上。如果桌上放的是煙紙和火柴， 則有煙葉的抽煙者會拾起煙紙和火柴，制作香煙，然后抽煙；其他類推。試用信號量同步煙草代理商和三個抽煙者。

方案1：用信號量機制解決問題的算法見表4。設想一下，若某時刻代理商提供煙葉和煙紙，因攜帶火柴的煙客1等待煙葉, 它可能被喚醒而執行語句1；而煙客2也在等待煙紙，所以它也很有可能被喚醒而執行語句1，此時兩線程均在語句2阻塞，造成死鎖。

表4 有死鎖風險的方案

方案2：一個網絡上比較常見的死鎖解決方案，見表5。盡管該算法無死鎖風險，但不是一個好的解決方案，因為方案違背了SuhasPati最初設計這個典型問題的初衷[2]。這里的代理商進程相當于操作系統，它的作用是僅僅向多個用戶進程提供資源，不可能也不需要知道他們中間誰在等待什么資源以及如何使用這些資源，因此在這一點上SuhasPati的要求是合理的。用戶進程對這些資源的使用對操作系統來講是透明的，所以方案2中的代理商進程顯然違反了這一分層設計原則?；诜桨?代理商進程比較忠實地反映SuhasPati的初衷，在保留此算法的基礎上，Parnas提出了下面的解決方案[2,6]。

表5 無死鎖風險的方案之一

方案3：引入3個名為“推送進程”(pusher)的輔助進程，負責處理agent進程放置的制煙原料信息，之后再轉發給相應的煙客進程。主要工作是推送進程完成，agent進程同方案一，smoker1,smoker2,smoker3同方案2，算法不再贅述。這里只給出3個推送進程的偽代碼，見表6。

表6 無死鎖風險的方案之二

算法分析：agent進程隨機產生兩種原料，例如煙葉和煙紙，此時信號量tabacoo和paper增至1，系統分別喚醒pusherTobacoo和pusherPaper兩進程：若先調度進程pusherTobacoo，由于isPaper和isMatch均為假，執行語句10，將isTobacoo設置為真；再調度進程pusherPaper時，執行語句3，將信號量matchSem曾至1，系統喚醒攜帶火柴的煙客進程smoker1。同樣，若先調度進程pusherPaper運行結果與前面一致。

3 結束語

哲學家就餐問題和吸煙者問題是兩類經典進程的同步問題，它可為多個進程互斥地訪問有限資源這一類問題的解決提供思路，對問題的深度剖析有助于學生深刻地理解操作系統原理中的資源共享、進程同步及死鎖等問題。筆者根據多年的教學經驗，分析了不合理地使用PV操作導致死鎖產生的原因，總結并提出了阻止死鎖產生的方案。方案以實現進程或線程最大限度地并發以及系統資源透明使用為優化目標，它們的提出對讀者以后解決此類問題具有很大的啟發性。

[1]GregoryR.Andrews.ConcurrentProgramming:PrinciplesandPractice[M].NewJersey:Addison-Wesley,1991:1-3

[2]AllenB.Downey.TheLittleBookofSemaphores[EB/OL].[2014-10-18]．http://greenteapress.com/semaphores

[3]湯小丹,梁紅兵,哲鳳屏,等.計算機操作系統[M].3版.西安：西安電子科技大學出版社,2007:103-104

[4]竇金鳳,曹家寶,郭忠文,等.計算機操作系統哲學家進餐問題的教學探討[J].計算機教育,2009,14(3):86-88

[5]AndrewS.ModernOperatingSystems[M].2nded.UpperSaddleRiver:prenticehall,2009:55-56

[6]DavidL.Parnas.Onasolutiontothecigarettesmokers'problemwithoutconditionalstatements[J].CommunicationsoftheACM,1975,18:181-183

(責任編輯：汪材印)

10.3969/j.issn.1673-2006.2015.04.027

2014-12-10

安徽省高校質量工程項目“計算機科學與技術專業綜合改革試點”(NO.2012zy075)。

謝士春(1970-),安徽濉溪人,碩士,講師,主要研究方向：計算機操作系統、程序設計、圖像識別方面的教學和研究。

TP311.12

A

1673-2006(2015)04-0094-05