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

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

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

引言

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

1 K資源互斥算法

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

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

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

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

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

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

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

1．2 算法的運(yùn)作過程描述

(1)請求資源

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

如果f

若f

(2)釋放資源

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

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

消息槽到達(dá)后，節(jié)點(diǎn)不作申請，并釋放操作，槽往下一個(gè)邏輯節(jié)點(diǎn)傳送。2算法運(yùn)作實(shí)例

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

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

3 分析與總結(jié)

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

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

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

4 結(jié)束語

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