一種基于消息槽的Ｋ資源互斥算法

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

關鍵詞：K資源互斥；進程；消息槽；算法

引言

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

1 K資源互斥算法

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

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

1．1 前提與假設

(1)系統中的所有節點組織成一個環形結構，消息槽，就像一個令牌，沿著這個邏輯環在系統中循環往復地傳送。

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

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

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

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

(1)請求資源

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

如果f

若f

(2)釋放資源

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

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

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

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

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

3 分析與總結

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

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

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

4 結束語

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