令牌傳遞

令牌傳遞又稱“標記傳送”，局部網數據送取的一種控制方法，多用於環形網。

令牌由專用的信息塊組成，典型的令牌由連續的8位“1”組成。當網絡所有節點都空閒時，令牌就從一個節點傳送到下一個節點。當某一節點要求發送信息時，它必須獲得令牌並在發送之前把它從網絡上取走。一旦傳送完數據，就把令牌轉送給下一個節點，每個節點都具備有發送/接收令牌的裝置。使用這種傳送方法決不會發生碰撞，這是因為在某一瞬間只有一個節點有可能傳送數據。最大的問題是令牌在傳送過程中丟失或受到破壞，從而使節點找不到令牌從而無法傳送信息。 ^[1] 

令牌傳送算法是一種通信量更小的分佈式同步算法，該算法由以下規則組成。

（1）該算法使用兩個數據結構。一個是被傳遞的令牌（token），另一個是請求（request）數組。令牌也是一個數組。請求數組是每個進程一個，記錄各進程申請資源狀況信息的一個表格。當它發申請信時，或者接到其他進程發來的申請信時，就記錄下該進程已處於申請資源狀態，並將信中所附的時間戳記錄下來。當接到該進程發來的第二封申請信時，第一封信的時間戳就不再保留。令牌數組從其結構上來説與請求數組相同。

（2）只有令牌持有者才能獲得資源。在任何時候系統中有且只有一個進程持有令牌。

（3）申請資源時，如果該進程不持有令牌，則它向其他進程廣播申請信件，信中需附上當時的時間戳。

（4）如果令牌持有者不是申請者，並且它不冉使用資源，則當申請數組中記錄有申請者時，就按算法選擇一個具有最小時間戳的申請者（或其他方便的算法），將令牌傳送給它．並附上自己的申請數組中保存的所有進程使用資源的狀況信息（是否申請資源．以及最大的時間戳）於令牌中。

（5）收到令牌的進程根據令牌中附有的各進程的申請狀況信息。對自己的申請數組中各個進程的狀況進行修改，從而成為令牌持有者，並進入它的臨界段使用臨界資源。

（6）每次使用互斥資源後，將自己的狀態改為非申請資源狀態，然後做規則（4）。

在分佈式系統中無論是在資源分配還是在進程通信中均均容易發生死鎖。在單機系統中使用的預防死鎖的方法在分佈式中同樣可以使用。在分佈式系統中的死鎖檢測比較困難，因為一個死鎖可能涉及各個分佈的資源，因此需要系統中所行進程合作實現死鎖的檢測，系統開銷很大。 ^[2] 

在令牌傳送系統中，令牌在網絡中沿各站依次傳遞。令牌是一個有特殊目的信息段，它的作用是允許站點進行數據發送。一個站點只有在持有令牌時才能發送數據。

令牌傳送常用於環形拓撲中，如IBM的Token RingARCnet等。其優點在於網絡中的站點依次收到令牌，並依次發送數據。這樣的系統就稱為固定的，從而可以計算出最壞情況下的訪問時間、吞吐量等。在工業生產控制中經常使用類似的固定系統。令牌傳送還允許建立優先級控制，從而保證較重要的信息能夠首先被髮送。

採用令牌傳送方式的網絡常用於負載較重、通信量較大的網絡中。在一般情況下，這一類網絡不會出現衝突問題。

採用令牌傳送方式的網絡可能帶來一些問題，例如，令牌可能損壞或丟失，以致所有的站點都在等待並不存在的令牌。相反地，網絡中也有可能出現兩個或多個令牌，導致站點在錯誤的時間發送數據。而上述問題往往是源自硬件的錯誤，尤其是網卡。

為了防止上述錯誤的出現，每個網絡必須具有錯誤檢測能力、恢復機制等。而且，網絡中的某個站被設計為專用的監視器，檢查重複或丟失的令牌。為了防止監視器本身的故障，可以設置一個或幾個備用監視器。

令牌傳送結構包括ARCnet、IEEE 802.4、IEEE 802.5等。

概括地講，競爭方式和令牌傳送方式在局域網的訪問方法中都佔有一定的地位。在較輕的負載下，競爭方式提供較好的性能，並使用簡單、便宜的網卡，而且不必為等待令牌而耗費時間。令牌傳動系統則在負載較重時性能較好，而且每個站對網絡的訪問具有一個最大的時間間隔。 ^[3]