919
1. 前言
一致性协议(coherency protocol)挂死(hang)通常有三种情况：死锁(deadlock)、活锁(livelock)和饿死(starvation)。
2. 死锁
死锁是指两个或多个参与者互相等待对方执行某些操作，导致系统永远无法向前运行。通常情况下，死锁是由资源循环依赖引起的。
举个简单例子，如下图1所示，有两个参与者节点A和B，以及两个资源X和Y。假设A持有资源Y，B持有资源X。如果A请求X，B请求Y，那么除非一个节点放弃它已经持有的资源，否则这两个节点将发生死锁。
图1 资源循环依赖导致死锁的示例。圆圈表示节点，正方形表示资源。以资源结尾的连线表示对该资源的请求，从资源开始的连线表示该资源的持有者
一般来说，如果事件A(例如，接收消息)可能导致事件B(例如，发送消息)，并且这两个事件都需要分配资源(例如，网络连接(network links)和缓冲区(buffer))，如果出现循环资源依赖，那么必须小心避免死锁发生。下图2为一个死锁发生的另一个场景，有两个一致性控制器C1和C2，它们正在响应彼此的请求，但是输入FIFO队列缓冲器已经被其它一致性请求填满了，会导致各自的响应无法绕过请求，因此无法被处理。在这时候，每个一致性控制器会暂停发送响应，而且控制器也不能去处理后续请求或者获得响应，系统就发生死锁了。
图2 死锁例子
在一致性协议中避免死锁的常用解决方案是为每一类消息使用单独的路由网络，网络可以是物理上分离的，也可以是逻辑上分离的(称为虚拟网络，virtual networks)，其实本质就是避免消息类之间的依赖关系。
下图3系统中，请求和响应消息使用不同的物理网络通道进行传输，由于响应消息不会被其它请求消息阻塞，因此它最终可以被其它目标节点收到，从而打破了资源循环依赖关系。
图3 使用分离网络路由通道来避免死锁
在一致性协议中，死锁可能出现在协议级(Protocol Deadlock)、缓存资源分配(Cache Resource Deadlock)和网络(Protocol-Dependent Network Deadlock)中。
2.1 协议死锁
当一致性控制器等待一个永远不会发送的消息时，就会出现协议死锁。这种死锁大多数情况下是由未经测试的竞争条件引起的。
2.2 缓存资源死锁
当缓存控制器在执行某些操作之前必须分配资源时，就会出现缓存资源死锁。这种死锁通常在处理另一个Core的请求或自己回写时出现。比如有一个缓存控制器，它有一组共享缓冲区，这些缓冲区可以分配给自己发起的一致性请求或其它Core的请求。如果Core发出足够多的一致性请求来占用所有缓冲区，那么它不能处理其它Core的请求。这样的话，当所有Core都达到这种状态，系统就会出现死锁。
2.3 协议相关的网络死锁
网络死锁有两种原因：一种是由错误的路由算法引起的死锁，这种算法与消息的类型和一致性协议无关；另一种是由于在一致性协议操作期间，交换特定的消息而引起的网络死锁。本文主要讲述后一类依赖于协议的网络死锁。比如定义了一个目录协议，其中一个请求消息可能导致一个转发的请求，而一个转发的请求可能导致一个响应。该协议必须确保三个原则，才能避免循环依赖的死锁。
每一类的消息必须在自己的网络通道上传播，网络可以时物理的，也可以是虚拟的，但关键是避免在FIFO缓冲区中出现某一类的消息被卡在另一类消息后面的情况。在本例中，请求、转发的请求和响应都需要再不同的网络上传输。因此，一致性控制器必须有三个输入FIFO，每个网络通道都需要一个。
每一类消息必须具有依赖顺序。例如A类消息可以引起一致性控制器发出B类消息，那么如果某个一致性控制器在等待A类消息时，不能停止处理收到的B类消息。比如在本例中，一致性控制器不能在等自己请求过程中停止对收到的转发请求进行处理，也不能在等待转发请求过程中停止对响应的处理。
如果一致性控制器接收到响应消息，那么没有任何消息类可以阻止它被一致性控制器处理。
这三个原则消除了协议网络循环的可能性。尽管请求在等待响应或转发请求时会被停止住，但每个请求最终都会得到处理，因为响应和转发请求的数量收到未完成请求事务数量的限制。
3. 饿死
饿死是指一个或多个Core未能取得进展，而其它Core仍然可以取得进展，没有进展的Core被认为是饿死的。饿死有几个根本原因，但它们往往分为两类：不公平的仲裁和不正确地使用否定确认响应。
如果某个资源总是由其它Core获得或持有，当至少一个Core无法获得该关键资源，就会出现饿死现象。典型例子是监听协议中的不公平总线仲裁机制，如果总线对不同Core的访问按固定优先级顺序进行的，Core C1发出的请求可以马上被响应，Core C2发出的请求必须在没有C1请求的情况下才会被响应，C3必须等C1和C2的请求处理后才会被响应，以此推理等等。在这样的系统中，具有低优先级的Core可能永远无法获得请求的响应，因此就会饿死。这个问题的常用解决办法就是：公平仲裁。
另一类导致饿死的主要原因是否定确定响应的不正确使用。在某些协议中，接收到一致性请求的一致性控制器可以向请求者发送NACK，通知请求者请求未被满足，必须重新发出。协议通常使用NACK来简化请求块正在被其它事务进行处理的情况。例如，在一些目录协议中，如果请求块正在被其它事务处理，那么新的请求访问请求块会得到NACK的响应。用NACK解决协议的竞争条件似乎比设计协议来处理这些罕见和复杂的情况更容易，但是挑战在于NACK请求一定要最终成功。如果有很多Core同时访问请求块，那么保证不会被饿死具有一定的挑战性。
4. 活锁
活锁是指两个或多个参与者执行操作并改变状态，但最终从未取得进展的情况。活锁是饿死的一个特例。多个Core使用exclusive操作进行抢锁比较容易出现活锁。
如下表1所示，在一个监听协议中，Core C1发出一个GetS请求操作来获取B块内容，并将B块的状态更改为ISAD(B块为I，目标是转到S状态，等待Own-GetS和数据(Data))。稍后，C1在总线上观察到Own-GetS，并将B块的状态更改为ISD。在B块进入ISD和C1接收到数据响应之间，C1很容易收到来自总线上其它Core对B块的GetM请求，这时候C1会将B块的状态变为ISDI。在这种瞬态状态下，就算C1稍后接收到数据响应时，C1会把B块的状态改成I，因此C1暂时无法获取数据给load操作，所以它必须重新发出另一个GetS操作去获得B块。但是下一个GetS也同样容易收到其它Core的影响，因此，C1可能永远也无法取得进展。这样就出现了活锁，Core仍然是活跃的，但是系统永远不会向前执行。活锁容易出现在高度竞争的场景中，这意味着大多数或所有Cores可能都同时被卡住了，系统陷入活锁。可以通过要求C1在接收到数据响应时至少把数据转发一次给load操作，这样也不会违法一致性。
表1 在监听协议中load B块的活锁示例
同样的问题也可能出现在store操作对块的操作状态为IMDS，IMDSI或IMDI。在这些情况下，块的结束状态是I或S，store对块的操作永远不会执行。幸运的是，我们为ISDI中的load操作提供的解决方案同样适用于这些状态中的store操作。Core发出GetM操作在收到数据时必须至少执行一次store操作，并且Core必须将新写入的数据转发给处于S或M请求块的其它Core。
5. 知识拓展
虚拟网络(virtual network)
除了使用物理上的不同网络，我们还可以使用不同的虚拟网络。虚拟网络防止不同类型的消息相互堵塞，从而避免消息级死锁。
下图4(a)为使用单个点对点链路连接的两个Cores，在每条链路的末端都有一个FIFO队列，用于在预接收传入的消息，最后Core会一一顺序处理其中消息。4(b)添加了另一个物理网络，它复制了一份链路和FIFO队列，请求消息在一个物理网络上传输，而响应消息在另一个物理网络上传输。
为了避免复制一份链路和交换机的面积成本，我们可以添加一个虚拟网络，如图4(c)所示。虚拟网络的唯一代价是在网络中的每个交互机和端点上增加一个FIFO队列，在本例中添加第二个虚拟网络，使得请求消息不会和响应消息互相影响。
图4 虚拟网络
除了虚拟网络，还有虚拟通道(virtual channel)，它们两者有所不同。在网络级别上，虚拟通道用于避免由于路由而导致的死锁，不看消息类型如何。为了避免路由死锁，消息可以在多个虚拟通道上传输。虚拟通道像虚拟网络，是通过在每个交换机和端点上增加额外的FIFO队列来实现的。但是每个虚拟网络可能有一定数量的虚拟通道，以避免路由死锁。
