謝士春

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

?

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

謝士春

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

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

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

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

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

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

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

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

表1 有死鎖風(fēng)險(xiǎn)的方案

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

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

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

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

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

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

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

表2 無死鎖風(fēng)險(xiǎn)的方案之一

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

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

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

2.2 吸煙者問題(CigaretteSmokersProblem)

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

表3 無死鎖風(fēng)險(xiǎn)的方案之二

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

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

表4 有死鎖風(fēng)險(xiǎn)的方案

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

表5 無死鎖風(fēng)險(xiǎn)的方案之一

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

表6 無死鎖風(fēng)險(xiǎn)的方案之二

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

3 結(jié)束語

哲學(xué)家就餐問題和吸煙者問題是兩類經(jīng)典進(jìn)程的同步問題，它可為多個(gè)進(jìn)程互斥地訪問有限資源這一類問題的解決提供思路，對(duì)問題的深度剖析有助于學(xué)生深刻地理解操作系統(tǒng)原理中的資源共享、進(jìn)程同步及死鎖等問題。筆者根據(jù)多年的教學(xué)經(jīng)驗(yàn)，分析了不合理地使用PV操作導(dǎo)致死鎖產(chǎn)生的原因，總結(jié)并提出了阻止死鎖產(chǎn)生的方案。方案以實(shí)現(xiàn)進(jìn)程或線程最大限度地并發(fā)以及系統(tǒng)資源透明使用為優(yōu)化目標(biāo)，它們的提出對(duì)讀者以后解決此類問題具有很大的啟發(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]湯小丹,梁紅兵,哲鳳屏,等.計(jì)算機(jī)操作系統(tǒng)[M].3版.西安：西安電子科技大學(xué)出版社,2007:103-104

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

(責(zé)任編輯：汪材印)

10.3969/j.issn.1673-2006.2015.04.027

2014-12-10

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

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

TP311.12

A

1673-2006(2015)04-0094-05