Raymond算法分析與改進

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

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

1 Raymond算法

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

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

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

申請隊列：每個進程還要管理一個先來先服務(wù)的申請隊列，這個隊列記載著所有尚未得到滿足的臨界區(qū)申請。

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

1.2 申請臨界區(qū)

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

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

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

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

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

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

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

2 Raymond 算法局限性

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

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

3 改進算法

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

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

3.2 申請臨界區(qū)

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

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

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

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

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

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

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

4 算法分析

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

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

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

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

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

5 結(jié)論

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

參考文獻

[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