令牌是沿著環傳送的專門的訊息。當某站有包傳送時，等待令牌到達，得到令牌後先傳送包，再傳送令牌。
基本介紹
- 中文名：令牌傳遞
- 外文名：Token Passing
- 別稱：標記傳送
- 定義：局部網數據送取的一種控制方法
- 用於：環形網
- 學科：通信技術
概述,算法,令牌傳送方式,
概述
令牌傳遞又稱“標記傳送”，局部網數據送取的一種控制方法，多用於環形網。
令牌由專用的信息塊組成，典型的令牌由連續的8位“1”組成。當網路所有節點都空閒時，令牌就從一個節點傳送到下一個節點。當某一節點要求傳送信息時，它必須獲得令牌並在傳送之前把它從網路上取走。一旦傳送完數據，就把令牌轉送給下一個節點，每個節點都具備有傳送/接收令牌的裝置。使用這種傳送方法決不會發生碰撞，這是因為在某一瞬間只有一個節點有可能傳送數據。最大的問題是令牌在傳送過程中丟失或受到破壞，從而使節點找不到令牌從而無法傳送信息。
算法
令牌傳送算法是一種通信量更小的分散式同步算法，該算法由以下規則組成。
（1）該算法使用兩個數據結構。一個是被傳遞的令牌（token），另一個是請求（request）數組。令牌也是一個數組。請求數組是每個進程一個，記錄各進程申請資源狀況信息的一個表格。當它發申請信時，或者接到其他進程發來的申請信時，就記錄下該進程已處於申請資源狀態，並將信中所附的時間戳記錄下來。當接到該進程發來的第二封申請信時，第一封信的時間戳就不再保留。令牌數組從其結構上來說與請求數組相同。
（2）只有令牌持有者才能獲得資源。在任何時候系統中有且只有一個進程持有令牌。
（3）申請資源時，如果該進程不持有令牌，則它向其他進程廣播申請信件，信中需附上當時的時間戳。
（4）如果令牌持有者不是申請者，並且它不冉使用資源，則當申請數組中記錄有申請者時，就按算法選擇一個具有最小時間戳的申請者（或其他方便的算法），將令牌傳送給它．並附上自己的申請數組中保存的所有進程使用資源的狀況信息（是否申請資源．以及最大的時間戳）於令牌中。
（5）收到令牌的進程根據令牌中附有的各進程的申請狀況信息。對自己的申請數組中各個進程的狀況進行修改，從而成為令牌持有者，並進入它的臨界段使用臨界資源。
（6）每次使用互斥資源後，將自己的狀態改為非申請資源狀態，然後做規則（4）。
在分散式系統中無論是在資源分配還是在進程通信中均均容易發生死鎖。在單機系統中使用的預防死鎖的方法在分散式中同樣可以使用。在分散式系統中的死鎖檢測比較困難，因為一個死鎖可能涉及各個分布的資源，因此需要系統中所行進程合作實現死鎖的檢測，系統開銷很大。
令牌傳送方式
在令牌傳送系統中，令牌在網路中沿各站依次傳遞。令牌是一個有特殊目的信息段，它的作用是允許站點進行數據傳送。一個站點只有在持有令牌時才能傳送數據。
令牌傳送常用於環形拓撲中，如IBM的Token RingARCnet等。其優點在於網路中的站點依次收到令牌，並依次傳送數據。這樣的系統就稱為固定的，從而可以計算出最壞情況下的訪問時間、吞吐量等。在工業生產控制中經常使用類似的固定系統。令牌傳送還允許建立優先權控制，從而保證較重要的信息能夠首先被傳送。
採用令牌傳送方式的網路常用於負載較重、通信量較大的網路中。在一般情況下，這一類網路不會出現衝突問題。
採用令牌傳送方式的網路可能帶來一些問題，例如，令牌可能損壞或丟失，以致所有的站點都在等待並不存在的令牌。相反地，網路中也有可能出現兩個或多個令牌，導致站點在錯誤的時間傳送數據。而上述問題往往是源自硬體的錯誤，尤其是網卡。
為了防止上述錯誤的出現，每個網路必須具有錯誤檢測能力、恢復機制等。而且，網路中的某個站被設計為專用的監視器，檢查重複或丟失的令牌。為了防止監視器本身的故障，可以設定一個或幾個備用監視器。
令牌傳送結構包括ARCnet、IEEE 802.4、IEEE 802.5等。
概括地講，競爭方式和令牌傳送方式在區域網路的訪問方法中都占有一定的地位。在較輕的負載下，競爭方式提供較好的性能，並使用簡單、便宜的網卡，而且不必為等待令牌而耗費時間。令牌傳動系統則在負載較重時性能較好，而且每個站對網路的訪問具有一個最大的時間間隔。
