Raymond算法分析與改進

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

關鍵詞：令牌；raymond算法；公平性；響應延遲

1 Raymond算法

1.1 數據結構

針對每個進程，都基于如下數據結構：

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

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

這棵邏輯樹不是一個靜態樹，而是會根據運行動態地改變樹的邏輯結構。樹中的根節點是令牌的持有者，即無論哪個進程得到令牌，該進程即成為樹的根節點。

1.2 申請臨界區

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

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

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

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

1.3 進入和退出臨界區

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

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

2 Raymond 算法局限性

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

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

3 改進算法

3.1 數據結構

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

3.2 申請臨界區

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

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

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

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

3.3 進入和退出臨界區

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

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

4 算法分析

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

假設有n個進程需共用臨界區。

消息復雜度是衡量分布式互斥算法的重要指標。根據其樹形的拓撲結構，且由于算法改進前后都不難得出，Raymond算法的消息復雜度為O（logn），而改進后的算法沒有增加或減少其消息復雜度。

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

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

5 結論

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

參考文獻

[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