摘要：在分布式操作系統(tǒng)等一些有多個進程同時活躍的應用中，必須妥善解決不同進程對資源的需求，即同步與互斥問題。文章提出了一種基于消息槽的K資源互斥算法，介紹了該算法的原理，詳細描述了該算法的運作過程，并進行了深入的分析。分析結(jié)果表明，該算法能夠有效地滿足K資源分布式環(huán)境下同步與互斥的要求。

關(guān)鍵詞：K資源互斥；進程；消息槽；算法

引言

關(guān)于資源互斥以及K資源互斥的問題，有很多算法已經(jīng)被提出來了，其中有一些還是相當不錯的，比如基于令牌的K資源互斥算法和基于仲裁集的K資源互斥算法等。本文在分析吸取他人成果的基礎(chǔ)上，提出了基于消息槽的K資源互斥算法，下文將對該算法進行描述并進行討論。

1 K資源互斥算法

所謂消息槽，就像一個大卡車，卡車上分成了很多部分，每一部分可以容納—個貨物；當有人要把自己的貨物給別人時，他就等著這個大卡車的到來，然后在車上找到一個空閑的貨位，把貨物放上去；大卡車繼續(xù)往前，到了收貨人那里，收貨人把貨物卸下來，原來的這個貨位也就再次成為可用的了。

這里所說的消息槽，就像這個大卡車，槽中共分出K槽位，每個槽位代表對一個資源的操作情況，即該資源目前是否被使用。當一個節(jié)點要使用資源時，就等著消息槽的到來，然后在其中找出若干空閑的槽位，并聲明，這些資源已被占用。使用完之后，再將這些槽位釋放。

1．1 前提與假設(shè)

(1)系統(tǒng)中的所有節(jié)點組織成一個環(huán)形結(jié)構(gòu)，消息槽，就像一個令牌，沿著這個邏輯環(huán)在系統(tǒng)中循環(huán)往復地傳送。

(2)消息槽中共有K槽位，相應的，系統(tǒng)中有K資源，每個槽位代表對一個資源的使用情況。初始時，每個槽位的內(nèi)容都為空。

(3)在消息槽的末尾，另設(shè)一項數(shù)據(jù)，記錄當前別的某個節(jié)點所需要的資源數(shù)。平常該項數(shù)據(jù)固定為0，當某個節(jié)點發(fā)現(xiàn)消息槽中空閑的資源數(shù)不能滿足自己的要求時，就把這一位填上自己所需要的資源數(shù)，等到釋放資源時，再將這項數(shù)據(jù)重新清0。

(4)為防止某些節(jié)點長期占用資源，導致另一些節(jié)點被餓死，并為提高資源的利用率，采用時間片(比如消息槽轉(zhuǎn)了n圈)的方法，當一個節(jié)點使用資源持續(xù)一定時間后，必須將資源釋放，若還要使用，則需重新申請。

1．2 算法的運作過程描述

(1)請求資源

若節(jié)點i申請使用a個資源，當i等到消息槽到達時，如果消息槽中空閑的槽位數(shù)能滿足自己的要求，即空閑槽位數(shù)f>=a，并且消息槽的末尾數(shù)據(jù)項為0，或者消息槽末尾數(shù)據(jù)項為b，但f>=a+b，則節(jié)點i從這f個資源中任選a個，并在他們對應的消息槽槽位中填上自己的進程號，表明這些資源已經(jīng)被占用了。同時，如果節(jié)點i曾經(jīng)將消息槽的末尾項數(shù)據(jù)填上的話，那么，將這項數(shù)據(jù)清0；否則直接使用資源，不必考慮消息槽的末尾項數(shù)據(jù)。

如果f

若f

(2)釋放資源

如果節(jié)點i完成了對資源的使用，那么等到消息槽到達后，將自己所申請資源所對應的消息槽中的槽位清空，表明這些資源又成為可用的了。當一個節(jié)點連續(xù)使用某些資源達一定時間后，該節(jié)點必須進行資源釋放過程，若還需使用，需要再次進行資源申請過程。

(3)不中請，也不釋放資源

消息槽到達后，節(jié)點不作申請，并釋放操作，槽往下一個邏輯節(jié)點傳送。2算法運作實例

上面給出了該算法的形式化描述，為便于理解，下邊將結(jié)合一個例子具體說明。 在一個系統(tǒng)中，共有7個進程節(jié)點，6個共享資源。這7個進程通過上邊的算法，來對這3個資源進行互斥訪問。

以后，這個系統(tǒng)就按照上面的算法，不斷地運作下去，直到斷電或者人為的切斷。

3 分析與總結(jié)

該算法滿足了互斥的要求。因為只有拿到資源的節(jié)點才能進入臨界段，當系統(tǒng)剩余資源不能滿足新的請求時，節(jié)點將申請不到資源，即同時處于臨界段的節(jié)點所占用的資源總數(shù)不會大于K，所以算法可以滿足互斥的要求。 這個算法是不存在死鎖的情況的。因為節(jié)點要么一次拿到所需的所有的資源，要么一個資源也拿不到，不會出現(xiàn)占有了一些資源，卻還在等待另一些資源的情況，也就是說，不可能發(fā)生死鎖的條件。

另外，這個算法也不存在節(jié)點餓死的情況。因為如果一個進程需要的資源數(shù)較多而無法立即得到滿足的話，那么它可以在消息槽中加以聲明，這樣別的節(jié)點就會“讓路”，等保證了它的請求得到滿足后，別的節(jié)點才會去申請資源。所以，任何需要較多資源的進程，都會在一定的時間后得到所需要的資源，不會出現(xiàn)一個需要較多資源的進程一直處于等待別的進程釋放資源的狀態(tài)。

此外，該算法的資源利用率也還比較高，雖然存在一點資源浪費，但由于有時間片限制，不會出現(xiàn)長時間內(nèi)有大量空閑資源不能使用的情況。而且，與幾種較成功的K資源互斥算法相比，資源利用率相差不大。

4 結(jié)束語

綜上所述，該算法實現(xiàn)了K資源的互斥，不存在死鎖與餓死情況，并且資源利用率較高，是一個滿足了各方面要求的算法。