[科普中国]-令牌传递

令牌是沿着环发送的专门的消息。当某站有包发送时，等待令牌到达，得到令牌后先发送包，再发送令牌。

概述令牌传递又称“标记传送”，局部网数据送取的一种控制方法，多用于环形网。

令牌由专用的信息块组成，典型的令牌由连续的8位“1”组成。当网络所有节点都空闲时，令牌就从一个节点传送到下一个节点。当某一节点要求发送信息时，它必须获得令牌并在发送之前把它从网络上取走。一旦传送完数据，就把令牌转送给下一个节点，每个节点都具备有发送/接收令牌的装置。使用这种传送方法决不会发生碰撞，这是因为在某一瞬间只有一个节点有可能传送数据。最大的问题是令牌在传送过程中丢失或受到破坏，从而使节点找不到令牌从而无法传送信息。1

算法令牌传送算法是一种通信量更小的分布式同步算法，该算法由以下规则组成。

（1）该算法使用两个数据结构。一个是被传递的令牌（token），另一个是请求（request）数组。令牌也是一个数组。请求数组是每个进程一个，记录各进程申请资源状况信息的一个表格。当它发申请信时，或者接到其他进程发来的申请信时，就记录下该进程已处于申请资源状态，并将信中所附的时间戳记录下来。当接到该进程发来的第二封申请信时，第一封信的时间戳就不再保留。令牌数组从其结构上来说与请求数组相同。

（2）只有令牌持有者才能获得资源。在任何时候系统中有且只有一个进程持有令牌。

（3）申请资源时，如果该进程不持有令牌，则它向其他进程广播申请信件，信中需附上当时的时间戳。

（4）如果令牌持有者不是申请者，并且它不冉使用资源，则当申请数组中记录有申请者时，就按算法选择一个具有最小时间戳的申请者（或其他方便的算法），将令牌传送给它．并附上自己的申请数组中保存的所有进程使用资源的状况信息（是否申请资源．以及最大的时间戳）于令牌中。

（5）收到令牌的进程根据令牌中附有的各进程的申请状况信息。对自己的申请数组中各个进程的状况进行修改，从而成为令牌持有者，并进入它的临界段使用临界资源。

（6）每次使用互斥资源后，将自己的状态改为非申请资源状态，然后做规则（4）。

在分布式系统中无论是在资源分配还是在进程通信中均均容易发生死锁。在单机系统中使用的预防死锁的方法在分布式中同样可以使用。在分布式系统中的死锁检测比较困难，因为一个死锁可能涉及各个分布的资源，因此需要系统中所行进程合作实现死锁的检测，系统开销很大。2

令牌传送方式在令牌传送系统中，令牌在网络中沿各站依次传递。令牌是一个有特殊目的信息段，它的作用是允许站点进行数据发送。一个站点只有在持有令牌时才能发送数据。

令牌传送常用于环形拓扑中，如IBM的Token RingARCnet等。其优点在于网络中的站点依次收到令牌，并依次发送数据。这样的系统就称为固定的，从而可以计算出最坏情况下的访问时间、吞吐量等。在工业生产控制中经常使用类似的固定系统。令牌传送还允许建立优先级控制，从而保证较重要的信息能够首先被发送。

采用令牌传送方式的网络常用于负载较重、通信量较大的网络中。在一般情况下，这一类网络不会出现冲突问题。

采用令牌传送方式的网络可能带来一些问题，例如，令牌可能损坏或丢失，以致所有的站点都在等待并不存在的令牌。相反地，网络中也有可能出现两个或多个令牌，导致站点在错误的时间发送数据。而上述问题往往是源自硬件的错误，尤其是网卡。

为了防止上述错误的出现，每个网络必须具有错误检测能力、恢复机制等。而且，网络中的某个站被设计为专用的监视器，检查重复或丢失的令牌。为了防止监视器本身的故障，可以设置一个或几个备用监视器。

令牌传送结构包括ARCnet、IEEE 802.4、IEEE 802.5等。

概括地讲，竞争方式和令牌传送方式在局域网的访问方法中都占有一定的地位。在较轻的负载下，竞争方式提供较好的性能，并使用简单、便宜的网卡，而且不必为等待令牌而耗费时间。令牌传动系统则在负载较重时性能较好，而且每个站对网络的访问具有一个最大的时间间隔。3

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学