經(jīng)典同步問題的死鎖解決方案

謝士春

宿州學(xué)院信息工程學(xué)院,安徽宿州,234000

?

經(jīng)典同步問題的死鎖解決方案

謝士春

宿州學(xué)院信息工程學(xué)院,安徽宿州,234000

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

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

1 預(yù)備知識

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

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

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

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

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

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

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

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

2 經(jīng)典同步問題的死鎖解決方案

2.1 哲學(xué)家就餐問題

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

表1 有死鎖風險的方案

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

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

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

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

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

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

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

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

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

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

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

2.2 吸煙者問題(CigaretteSmokersProblem)

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

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

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

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

表4 有死鎖風險的方案

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

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

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

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

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

3 結(jié)束語

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

[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]湯小丹,梁紅兵,哲鳳屏,等.計算機操作系統(tǒng)[M].3版.西安：西安電子科技大學(xué)出版社,2007:103-104

[4]竇金鳳,曹家寶,郭忠文,等.計算機操作系統(tǒng)哲學(xué)家進餐問題的教學(xué)探討[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

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

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

TP311.12

A

1673-2006(2015)04-0094-05