在这一节中我们进一步深入讨论总线嗅探的缓存一致性协议，首先从MSI开始，然后进一步讨论更复杂的协议。总线嗅探基于这样一个想法，所有的一致性控制器都以相同的顺序观察到总线上的一致性请求来保持一致性，因此我们对一致性请求的顺序到达有一定要求。我们考虑下面图中的例子，如果一致性请求的顺序没有保证，可能会出现缓存不一致的情况。
总线嗅探一致性协议的简单例子
传统的嗅探协议在所有缓存块中都保持请求的全局顺序，因而可以很容易实现需要全局顺序的内存模型，如SC和TSO，但也可以看下面的例子，C1和C2观察到的GetM和GetS请求顺序是不同的，违反了SC和TSO内存模型。
每个缓存块都保持总线上的一致性请求顺序，但不保持全局顺序，违反了SC和TSO内存模型，注意方括号表示该内存地址中存放的值
最简单的总线嗅探一致性协议
我们讨论一个最简单的、没有优化的协议，并描述在两个不同的系统模型上的实现，前者说明了实现的基本方法，后者更复杂一些，表明即使是相对简单的性能改进的方法也会影响协议实现的复杂性。
协议规范
有三种稳定状态，即M、S和I，也叫MSI协议。下面两张图展示了缓存和内存控制器的稳定状态之间转换的状态机。
MSI协议状态机
简单的总线嗅探系统模型：原子请求与原子事务
简单的总线嗅探系统
这个系统实现了两个原子属性：原子请求和原子事务，前者表示一致性请求在发出的同一个周期内就被排序，后者表示一致性事务也是原子性的，对同一个块的后续的请求会在第一个事务完成之后才会出现在总线上。下表列出了该系统模型的协议细节，和之前的状态机不同的是，这里我们加入了两个过渡状态。
缓存控制器视角下的协议细节
内存控制器视角下的协议细节
测验问题6：在MSI总线嗅探协议中，一个缓存行只能处于三种一致性状态中的一种。
答：错误。即使对上面讨论的最简单的系统模型，也包含了过渡状态，不止三个状态。
这个系统的原子性属性以两种方式简化了缓存缺失的处理，首先原子请求属性确保了当控制器想提升一个区块的状态时，可以直接发出一个请求，而不需要考虑另一个控制器的请求会排在前面，因此可以直接进入过渡状态，同时原子事务属性保证了当前事务完成之前不会发生对同一个块的后续请求。同时也可以简化缓存块驱逐的处理方式，例如原子请求属性简化了缓存控制器的设计，例如我们不需要考虑PutM请求发出之后但是再被总线接收之前，其他内核发出GetM请求的情况，原子事务属性也简化了内存控制器的设计。
下图展示了一个例子来说明该系统模型。
简单总线嗅探系统模型的例子
复杂一些的总线嗅探系统模型：非原子请求与原子事务
在这种模型中，我们允许非原子请求，通常是由于我们在缓存控制器和总线之间插入了一个消息队列，但仍然保留了原子事务属性。下表介绍了详细的协议细节，包括过渡状态，注意这里过渡状态的数量更多。
缓存控制器视角下的协议细节
内存控制器视角下的协议细节
特别需要注意的是M到I的状态变化，我们额外加入了一种NoData消息，表示向内存控制器表明这个消息来自一个非所有者，意思就是该内核已经不是缓存块的所有者了，并使内存控制器退出其过渡状态，内存控制器也添加了一个额外的状态M_D，方便表示内存控制器收到NoData后应该回到哪个稳定状态。
下图展示了一个例子来说明该系统模型。
复杂一些的总线嗅探系统模型的例子
添加Exclusive状态
一个非常常用的优化是增加E状态，如果一个缓存有一个处于E状态的块，那么这个块是有效的、只读的、干净的、独占的、拥有的，缓存控制器可以自己把E状态变为M状态，不需要发出一致性请求。这种协议在首先读取一个块然后再写入的情况下有优势，在这种情况中，E状态可以减少一半的一致性事务。
进入E状态
我们必须首先理解GetS的发出者如何确定没有其他内核也share了该缓存块，保证进入状态E是安全的。一种方法是在总线上增加一个或门连接的sharer信号，如果GetS请求发现这个信号为1，那么就将缓存块状态改为S，否则进入E状态；另一种方法是在LLC中保持额外的状态，在LLC中区分I和S状态，但是准确维护S状态也是一个挑战，LLC必须检测最后一个sharer什么时候放弃所有权，要求缓存控制器在驱逐S状态区块时发出PutS消息，且内存控制器需要维护sharer的数量，一个更简单但不太完整的替代方案是允许LLC保守地跟踪sharer，放弃了一些使用E状态的机会，但不需要额外的PutS事务。
在接下来的讨论中我们选择了最容易实现的方案，在LLC上保持一个保守的S状态，避免出现在总线上实现或门信号相关的工程问题，并且不需要PutS事务。
协议规范与细节
下面两张图展示了缓存和内存控制器的稳定状态之间转换的状态机。
MESI协议状态机
下表说明了MESI协议的实现细节，包括了过渡状态。注意我们仍然假设了原子事务属性，但不要求原子请求属性。
缓存控制器视角下的协议细节
内存控制器视角下的协议细节
下面展示了一个例子来说明MESI协议。
MESI协议系统模型的例子
非原子总线
我们之前讨论的实现都是基于原子事务属性的，也就是说所有事务都由不可分割的请求与响应组成，这种原子性大大简化了协议实现的设计，但牺牲了性能。下图直观地展示了总线是否保证原子性会影响性能，注意到第三种情况中响应不一定是顺序的，这种情况响应的数据中需要带有请求或请求者的身份信息。
总线的原子性
乱序事务总线上的MSI协议
乱序事务总线的系统模型
我们现在在上图中的系统模型中实现MSI协议，下面两张表说明了协议的实现细节。注意事务的排序是基于请求被放入总线的时间，而非到达请求者的时间。我们需要实现一些原子总线上不可能出现的状态变化，例如一个缓存块可以在状态IS_D中收到Other-GetS请求，此时不需要做任何事情。但可能还有一些其他更复杂的状态转换，例如当缓存块处于状态IM_D且观察到一个Other-GetS请求时，该缓存块实际上处于M状态，是所有者但没有数据，必须对GetS请求做出响应，最简单的解决方案就是暂时不处理Other-GetS，直到该缓存从内存中得到数据。
缓存控制器视角下的协议细节
内存控制器视角下的协议细节
对于其他复杂的状态转换，我们也采用了停顿的策略，但可能会引起一些问题：首先是牺牲了性能；其次可能会引起死锁，我们需要避免出现链式的停顿，在这一节讨论的协议中不会出现；最后一个问题是请求者可能会在处理自己的请求之前就收到了请求的响应，可以参考下面的例子。
响应在请求之前到达的例子
该实现可以进一步优化，具体的细节可以参考原书。
总线互联网络的优化
我们进一步讨论另外两种可能的系统模型，进一步提升性能。
第一种模型中，我们可以使用独立的数据响应非总线网络，一致性请求的响应没有必要进行排序，也没有必要广播，可以使用独立的网络进行传递，更容易实现、吞吐量高、且延迟低。
第二种模型中，我们使用一个用于一致性请求的逻辑总线，有两种方法。首先是其他支持物理上的全局顺序的拓扑结构，如树形拓扑，一致性控制器位于叶节点，所有请求单播到树的根部，然后继续向下广播；其次也可以使用逻辑全局顺序，关键是在逻辑时间上对请求进行排序，需要确保每个请求都有一个不同的逻辑时间、一致性控制器按照逻辑时间顺序处理请求、且没有位于逻辑时间T的请求会在控制器已经过了逻辑时间T之后到达。
测验问题7：总线嗅探缓存一致性协议要求内核必须在总线上通信。
答：错误。总线嗅探需要一个可以保持全局顺序的广播网络，但是不需要物理总线也可以实现。