摘要:在分布式操作系統(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