摘 要：raymond算法是分布式系統(tǒng)中一種基于令牌的樹(shù)形互斥資源訪問(wèn)算法。由于算法基于樹(shù)形結(jié)構(gòu)，就從根本上杜絕了循環(huán)等待鏈這樣一種死鎖的必然條件，申請(qǐng)隊(duì)列的先到先服務(wù)特性也保證了算法一定程度的公平性。但恰是這種FCFS特性，使得該算法不能保證絕對(duì)公平。對(duì)raymond算法提出改進(jìn)，加入跳數(shù)限制，保證了樹(shù)形結(jié)構(gòu)的各分支之間的平衡，從而保證了算法的公平性。

關(guān)鍵詞：令牌；raymond算法；公平性；響應(yīng)延遲

1 Raymond算法

1.1 數(shù)據(jù)結(jié)構(gòu)

針對(duì)每個(gè)進(jìn)程，都基于如下數(shù)據(jù)結(jié)構(gòu)：

令牌指引元：指向通往根進(jìn)程路徑上的第一個(gè)鄰居進(jìn)程（父進(jìn)程），而不是直接指向令牌的持有者。根節(jié)點(diǎn)是特例，沒(méi)有父進(jìn)程，其令牌指引元指向自己。

申請(qǐng)隊(duì)列：每個(gè)進(jìn)程還要管理一個(gè)先來(lái)先服務(wù)的申請(qǐng)隊(duì)列，這個(gè)隊(duì)列記載著所有尚未得到滿足的臨界區(qū)申請(qǐng)。

這棵邏輯樹(shù)不是一個(gè)靜態(tài)樹(shù)，而是會(huì)根據(jù)運(yùn)行動(dòng)態(tài)地改變樹(shù)的邏輯結(jié)構(gòu)。樹(shù)中的根節(jié)點(diǎn)是令牌的持有者，即無(wú)論哪個(gè)進(jìn)程得到令牌，該進(jìn)程即成為樹(shù)的根節(jié)點(diǎn)。

1.2 申請(qǐng)臨界區(qū)

當(dāng)Pi希望進(jìn)入臨界區(qū)時(shí)，首先把REQi附加到自己的申請(qǐng)服務(wù)隊(duì)列；如果Pi不是令牌持有者并且申請(qǐng)隊(duì)列里只有自己的申請(qǐng)，則向令牌指引元發(fā)出一封REQi；

當(dāng)Pj接收到來(lái)自Pi的REQi信件，首先將申請(qǐng)附加到自己的申請(qǐng)隊(duì)列；如果Pj不是令牌持有者并且申請(qǐng)隊(duì)列里只有一份申請(qǐng)，則向令牌指引元發(fā)出一封REQj；

當(dāng)根進(jìn)程接收到一份REQ信件并且根進(jìn)程沒(méi)有使用臨界區(qū)，則向發(fā)送者發(fā)出令牌，同時(shí)把自己的令牌指引元改置為令牌接收進(jìn)程；隊(duì)列里面若還有進(jìn)程，則向令牌指引元發(fā)送REQi；

當(dāng)Pj接收到令牌，如果申請(qǐng)隊(duì)列的首位申請(qǐng)者不是自己，則摘取首位申請(qǐng)者，向它發(fā)送令牌，把自己的令牌指引元改置為令牌接收者；如果此時(shí)申請(qǐng)隊(duì)列非空，則立即向新的令牌指引元發(fā)送一封REQj信件。

1.3 進(jìn)入和退出臨界區(qū)

當(dāng)Pi接收到令牌并且自己是申請(qǐng)隊(duì)列的首位申請(qǐng)者，就刪除首位申請(qǐng)并進(jìn)入臨界區(qū)；

當(dāng)Pi退出臨界區(qū)時(shí)，如果Pi的申請(qǐng)隊(duì)列非空，則摘取首位申請(qǐng)者，向它發(fā)送令牌，把自己的令牌指引元改置為令牌接收者；如果此刻申請(qǐng)隊(duì)列非空，則立即向新的令牌指引元發(fā)送一封REQj信件。

2 Raymond 算法局限性

由于算法基于樹(shù)形結(jié)構(gòu)，從根本上杜絕了循環(huán)等待這樣一種死鎖的必然條件。申請(qǐng)隊(duì)列的FCFS特性也保證了算法在一定程度上的公平性，但恰是這種FCFS特性，使得該算法具有一定程度的不公平性。下面以圖1為例來(lái)說(shuō)明。

（a）為某網(wǎng)絡(luò)在某一時(shí)刻的資源訪問(wèn)狀態(tài)，其中根進(jìn)程6正在訪問(wèn)臨界資源。在（b）中，進(jìn)程1發(fā)出資源訪問(wèn)的請(qǐng)求，該請(qǐng)求沿進(jìn)程3、5被發(fā)送到根進(jìn)程6。當(dāng)進(jìn)程6退出臨界區(qū)，則將令牌沿原路發(fā)送到進(jìn)程1。此時(shí)，進(jìn)程1變成根進(jìn)程，如圖（c）所示。此時(shí)，若進(jìn)程2和進(jìn)程10同時(shí)發(fā)送訪問(wèn)資源的請(qǐng)求，則按照FCFS原則，進(jìn)程2先訪問(wèn)臨界資源。同理，由于進(jìn)程10離根進(jìn)程跳數(shù)太多，造成其對(duì)臨界資源的訪問(wèn)必然滯后。

3 改進(jìn)算法

3.1 數(shù)據(jù)結(jié)構(gòu)

對(duì)算法的令牌指引元不作改變。申請(qǐng)隊(duì)列該做可以執(zhí)行插入操作的動(dòng)態(tài)隊(duì)列。對(duì)REQ信件作部分改動(dòng)，加入跳數(shù)字段，即REQ（i，h），其中，i代表發(fā)送節(jié)點(diǎn)，h是i到源申請(qǐng)節(jié)點(diǎn)的跳數(shù)。

3.2 申請(qǐng)臨界區(qū)

當(dāng)Pi希望進(jìn)入臨界區(qū)時(shí)，首先設(shè)置h為0，把REQ（i，h）附加到自己的申請(qǐng)服務(wù)隊(duì)列；如果Pi不是令牌持有者并且申請(qǐng)隊(duì)列里只有自己的申請(qǐng)，則向令牌指引元發(fā)出一封REQ（i，h）；

當(dāng)Pj接收到來(lái)自Pi的REQ（i，h）信件，首先將申請(qǐng)按h的大小插入到自己的申請(qǐng)隊(duì)列，使h=h+1；如果Pj不是令牌持有者并且申請(qǐng)隊(duì)列里只有一份申請(qǐng)，則向令牌指引元發(fā)出一封REQ（j，h）；

當(dāng)根進(jìn)程接收到一份REQ信件并且根進(jìn)程沒(méi)有使用臨界區(qū)，則向發(fā)送者發(fā)出令牌，同時(shí)把自己的令牌指引元改置為令牌接收進(jìn)程；隊(duì)列里面若還有進(jìn)程，則使其h=h+1，并向令牌指引元發(fā)送REQ（i，h）；

當(dāng)Pj接收到令牌，如果申請(qǐng)隊(duì)列的首位申請(qǐng)者不是自己，則摘取首位申請(qǐng)者，向它發(fā)送令牌，把自己的令牌指引元改置為令牌接收者；如果此時(shí)申請(qǐng)隊(duì)列非空，則使其h=h+1，并立即向新的令牌指引元發(fā)送一封REQ（j，h）信件。

3.3 進(jìn)入和退出臨界區(qū)

當(dāng)Pi接收到令牌并且自己是申請(qǐng)隊(duì)列的首位申請(qǐng)者，就刪除首位申請(qǐng)并進(jìn)入臨界區(qū)；

當(dāng)Pi退出臨界區(qū)時(shí)，如果Pi的申請(qǐng)隊(duì)列非空，則摘取首位申請(qǐng)者，向它發(fā)送令牌，把自己的令牌指引元改置為令牌接收者；如果此刻申請(qǐng)隊(duì)列非空，則使其h=h+1，并立即向新的令牌指引元發(fā)送一封REQ（j，h）信件。

4 算法分析

首先進(jìn)行直觀的分析，以圖2為例進(jìn)行說(shuō)明。1為當(dāng)前根進(jìn)程，若2與10的資源訪問(wèn)申請(qǐng)?jiān)?訪問(wèn)資源過(guò)程中到達(dá)，則進(jìn)程10具有絕對(duì)的優(yōu)先訪問(wèn)權(quán)。如圖（b），10成為根進(jìn)程后，將會(huì)把令牌交于2。既不會(huì)增加通信開(kāi)銷，又避免了不公平的資源訪問(wèn)。另外，與Raymond算法相似，本算法是互斥的，且不會(huì)造成死鎖。

假設(shè)有n個(gè)進(jìn)程需共用臨界區(qū)。

消息復(fù)雜度是衡量分布式互斥算法的重要指標(biāo)。根據(jù)其樹(shù)形的拓?fù)浣Y(jié)構(gòu)，且由于算法改進(jìn)前后都不難得出，Raymond算法的消息復(fù)雜度為O（logn），而改進(jìn)后的算法沒(méi)有增加或減少其消息復(fù)雜度。

為了簡(jiǎn)化問(wèn)題，本文首先假設(shè)相鄰節(jié)點(diǎn)間進(jìn)行通過(guò)一跳發(fā)送單個(gè)消息的所需時(shí)間為T，使用一次臨界區(qū)需時(shí)間為E。改進(jìn)后的算法和Raymond算法相同，請(qǐng)求并訪問(wèn)一次臨界區(qū)所需要的平均延遲為O（logn）*T+E。

最長(zhǎng)延遲和最短延遲之間的差可以反映算法的公平性。Raymond 算法的最大延遲為（n-1）*T+E。而由于有跳數(shù)限制，使得其各分支長(zhǎng)度保持平衡，因此改進(jìn)后算法的最長(zhǎng)延遲為logn*T+E。最短延遲兩者相同，即T+E。因此，改進(jìn)后的算法提高了公平性。

5 結(jié)論

Raymond算法是一種基于令牌的分布式互斥控制算法。其FCFS特性造成該算法一定程度的不公平性，本文對(duì)此提出改進(jìn)。在其信令報(bào)文中加入跳數(shù)，通過(guò)跳數(shù)限制，使得樹(shù)形結(jié)構(gòu)的各分支維持在平衡狀態(tài)，保證了算法的公平性。

參考文獻(xiàn)

[1]K Raymond. A tree based algorithm for distributed mutual exclusion[J]. ACM Trans. on Computer Systems ， 1989 ，7（1） ：61277.

[2]P.K.Dash and R.C.Hansdah， \"An Efficient Token Based Algorithm for Distributed Mutual Exclusion.\"1997