缓存一致性
介绍
现代计算机体系结构中往往使用多级缓存加快访存速度，往往使用多级缓存，其中1,2级缓存为每个核独享，而3级缓存往往是所有核共享。如果不同核同时对同一地址进行写，那么针对同一地址便有了不同的值，这种问题称为缓存一致性问题。
监听协议
监听协议的特点为：
- 实现了一种广播机制来通知更改，通常使用总线
- 当CPU涉及全局操作时，需要在获取总线控制权之后，才可以进行更改。例如写入内存
- 所有处理器一直监听总线，并检测总线上的地址是否在本地中存在，如果有，则进行操作
- 写操作的串行化： 写操作必须在获得总线后才可进行
一个简单的监听协议中每个数据块有三种状态：
- 无效： 总线中的缓存在本地中不存在
- 共享： 当前缓存可能在其他处理器中有副本。只要发出读请求，就会进入共享状态，无论其他处理器中是否存在
- 独占： 当前缓存只在该处理器中存在
当接收到来自处理器的请求时，会发生如下转换：
当读写命中时:
当读写未命中时:
当总线中的请求命中时:
总的来说，当写入一块缓存时，这片缓存将会切换到独占状态，并且清除其他处理器中的缓存。当读取一块缓存时，将从其他处理器和内存中取得，并且将状态修改为共享
| 请求 | 源 | 状态 | 类型 | 解释 |
|---|---|---|---|---|
| 读命中 | 处理器 | M/S | 命中 | 读本地缓存的数据 |
| 读缺失 | 处理器 | I | 缺失 | 将读缺失放到总线上 |
| 读缺失 | 处理器 | M | 替换 | 写回块，并且将读缺失放到总线上 |
| 写命中 | 处理器 | M | 命中 | 本地缓存写入数据 |
| 写命中 | 处理器 | S | 一致性 | 将Invalidate请求放到总线上，写入缓存并切换成独占状态 |
| 写缺失 | 处理器 | I | 缺失 | 将写缺失放到总线上 |
| 写缺失 | 处理器 | S | 替换 | 将写缺失放到总线上 |
| 写缺失 | 处理器 | M | 替换 | 写回块，将写缺失放到总线上 |
| RdMiss | 总线 | S | 无操作 | 不需要任何操作 |
| RdMiss | 总线 | M | 一致性 | 将状态切换为S，并且写回块 |
| Invalidate | 总线 | S | 一致性 | 使该块无效 |
| WtMiss | 总线 | S | 一致性 | 使该块无效 |
| WtMiss | 总线 | M | 一致性 | 写回该块，并且使该块无效 |
该协议有MSI三种状态，因此称为MSI协议。下面是这个协议的一些扩展
- MESI协议： 添加了独占(exclusive)状态，它表示当前块只在一个缓存中并且没有被修改，它是从S状态划分出去的。这样当写入这个块时就可以不用向总线发出Invalidate请求
- MOESI协议： 添加了拥有(owned)状态，表示其他处理器有该块并且在存储器中已过时。在MSI协议中，M状态遇到RdMiss将切换成S状态，并且写回块。而现在只需要将状态切换成O，而不需要写回块，当他真正被替换出去时才需要写回。
目录协议
目录是一种集中式的数据结构，它包含所有块在所有处理器中的信息，因此现在只需要查目录就可以获得这些缓存的位置信息。
在目录协议中，同样存在MSI三种状态。但是现在它的操作对象只有三种：
- 本地节点： 发出请求的节点
- 宿主节点（目录）： 包含所访问的存储单元及其目录项的结点
- 远程节点： 包含所需存储块，可能和宿主节点是一个节点，也可能不是
本地节点发送给宿主节点的信息：
- RdMiss: 向宿主节点请求块，并要求把本节点加入共享集
- WtMiss： 请求宿主节点提供数据，并且使本节点称为独占者
- Invalidate： 本节点写命中，作废远程副本
- MdSharer: 要求宿主节点删除被替换块的信息，如果删除后变成空集，将状态切换为I
- WtBack2: 将修改过的被替换块写回，然后再进行MdSharer操作
宿主节点发给远程节点的信息：
- Invalidate： 作废远程节点中的副本
- Fetch： 从远程节点中获得副本，并且将数据送到宿主节点，把远程节点状态改成共享
- Fetch&Inv: 获得数据并作废远程副本
宿主发给本地：
- DReply： 将数据发送给本地
远程发给宿宿主
- WtBack： 把远程的数据给宿主，该消息时远程节点对于Fetch的响应
ACE协议
ace协议是axi4协议的扩展，给硬件一致性提供了方案。
状态
如图为ACE协议定义的cache行状态，
- UniqueDirty: M
- SharedClean: S
- Invalid: I
- UniqueClean: E
- SharedDirty: O
Shared表示可能有多个缓存共享该缓存行，Dirty表示当前远程节点是脏的。当然这些状态不都是必须的，可以根据自己的需要自由组合。
事务
首先本地节点读写会发送一些消息给目录，目录根据节点状态将消息转发给对应节点，这些消息在ACE协议中称为事务。
本地节点发出的事务：
| 事务 | 状态转换 | 通道 | 说明 |
|---|---|---|---|
| ReadShared | I->E, E->S, M->O | R | 读一个cache行，不影响其他节点的数据 通常是Load Miss时使用 |
| ReadUnique | 状态转换图 | R | 读cache行并独占它。写回式cache写miss时使用， |
| CleanUnique | S->E,O->M | W | 清除其他节点中的缓存行，写命中时使用 |
| WriteBack | O->I,M->I | W | 写回并清除所有节点中的副本，cache写回时使用 |
| WriteClean | M->E,O->S | W | 只写回副本， |
| WriteEvict | E->I | W | 驱逐当前节点 |
| MakeUnique | I->M,S->M,O->M | R | 直接驱逐所有副本，状态转为M。整个缓存行都需要写回时执行。和ReadUnique的区别是不需要发送读请求 |
RRESP是上级cache返回的信号，例如L1Cache发送读请求，L2Cache会发送该节点的状态。当然如果上级节点是memroy，那么shared和dirty都为0.
写操作的过程可以表示为：
驱逐操作可以表示为：
当本地节点发送请求之后，部分请求需要转发给远程节点进行下一步操作。
| 本地事务 | 远程事务 |
|---|---|
| ReadShared | ReadShared |
| ReadUnique | ReadUnique |
| CleanUnique | CleanInvalid |
| WirteBack | 无需转发 |
| WriteClean | 无需转发 |
| WriteEvict | 无需转发 |
| MakeUnique | MakeInvalid |
WriteBack无需转发的原因是只有脏块才需要写回，也就是说此时状态为M或O，写回后状态变为I，这表明没有节点拥有该块的控制权。此时其他拥有该缓存行的节点还是可以正常读写(内容相同)，如果有节点重新写入该块会将状态转换为M。
信号定义
snoop通道信号（用于master之间交流）
ack信号：
| 信号 | 源 | 说明 |
|---|---|---|
| RACK | Master | 读事务完成通知 |
| WACK | Master | 写事务完成通知 |
DOMAIN
- Non-shareable: 只包含一个Master
- Inner Shareable: 包含多个Master
- Outer Shareable: 包含Inner Shareable和其他Master
- System： 包含所有节点
domain用来指示当前位于哪个域。域这个概念视为了屏障设立的，屏障只确保同一个域内节点的内存序。
BAR
为了内存屏障而设立
SNOOP
事务的类型标识符，具体如下表
RESP
- RRESP[2]: dirty位。它表示读过来的数据是否是脏的，例如L2Cache当前缓存行是脏的，并且L1Cache不存在该数据，那么L1Cache读取时就需要更改状态为UD
RRESP[3]: shared位
CRRESP[0]: 数据传输位，例如ReadShared等读操作便可能导致数据传输
- CRRESP[1]: 错误位，例如ECC错误
- CRRESP[2]: dirty位，它表示事务之前，当前节点的缓存行是脏的，并且写回缓存的责任正移交给interconnect或发出的节点。也就是说如果是ReadShared事务那么dirty可能转移给发出事务的节点。
- CRRESP[3]: shared位。它表明在事务结束后还拥有这份副本。
- CRRESP[4]: unique位。它表明事务发生前是否拥有这份副本。
线程同步
线程同步是基于锁来实现的，而实现锁的关键功能是硬件需要提供一种机制，使得每次只有一个核执行成功，也就是硬件原语。一般情况下，这些原语通常不是给用户使用的，而是给精心设计的底层库使用。
一种典型的操作是原子交换。它将寄存器中的一个值和内存中的一个值进行交换。我们可以假定要实现一个简单的锁，0表示这个锁可以占用，1表示已经被占用。处理器设置锁的方式是将寄存器中的1和存储器中的值进行交换，如果获得的值是1，表示其他处理器已经占用，反之则可以将1写入内存中占用锁。
实现上述方式会增加一致性实现的复杂性，因为硬件不允许在该操作之间插入任何操作，并且不能死锁。
替代方法是使用一对指令，第二条指令返回一个值，这个值表示这对指令是否如原子指令一样执行。MIPS和RISC-V都采用了这种方式。
MIPS实现了ll和sc两条指令。其中ll读取内存中的一个值并且将llbit置1，并且硬件还会记录这一次读的地址，如果中间对该地址进行操作那么llbit将会置0。sc将某个值写入内存，但是它在写入前会进行检查，如果llbit为1才会写入。
在拥有原子操作之后，可以利用这些操作实现自旋锁 - 处理器不断尝试获得锁，直到成功为止。
具体操作为：
- 处理器不断的读取和检测，直到这个锁已经解锁为止
- 所有处理器都是用交换指令，直到看到1为止，而胜利者将会看到0.