CPU缓存一致性与C++ Memory Order (第一部分-MESI协议)

在对称多处理系统（Symmetric Multiprocessing, SMP）中，一个变量（或内存位置）可以同时存在于多个CPU的缓存行中。为了提供完美的用户级抽象，任何对一个或多个变量的修改都应该被强制同步，以确保其它CPU的缓存得到更新。 然而，在实现上，由于CPU之间通常通过总线互联，它们不能同时对多个缓存进行写操作。

缓存一致性

缓存一致性是指在一个多处理器系统中，确保当某个处理器修改了存储在共享资源（如主内存或缓存中的数据）时，其他处理器能够访问到最新的数据版本，从而保证数据的一致性。

为了达到这一目标，缓存一致性机制必须处理两个主要问题：写传播（Write Propagation）和事务串行化（Transaction Serialization）。

写传播确保一个处理器核心的写操作能被传播并被其他处理器核心所见。而事务串行化则确保所有处理器核心的写操作按照一定的顺序执行，对所有处理器核心而言这个顺序是一致的。这两个机制共同工作，确保了即使多个CPU可能并发地修改同一份数据，它们也能看到一致的数据视图。

MESI协议

为了实现缓存一致性，多种协议和机制被设计出来，其中MESI协议是最广泛使用的一种机制。

实际上，AMD处理器使用的是MOESI协议，Intel处理器使用的是MESIF协议。这两种协议都是MESI协议的变种。这里不展开讨论。

MESI 协议通过定义缓存行的四种状态——修改（Modified）、独占（Exclusive）、共享（Shared）和无效（Invalid），管理多个处理器缓存之间的一致性。状态之间的转换受到缓存协议控制，以确保数据的一致性和同步。

  • 独占（Exclusive, E）：缓存行仅存在于当前缓存中，并且是干净的（即缓存数据与主存数据一致）。当其他缓存尝试读取该数据时，状态转变为共享；当前缓存写入数据时，转变为已修改状态
  • 共享（Shared, S）：缓存行同时存在于其他缓存中，并且是干净的。该缓存行可以在任意时刻被抛弃
  • 已修改（Modified, M）：缓存行的数据是“脏”的（即与主存的值不同）。如果其他 CPU 核心需要读取这块数据，该缓存行必须先回写到主存，然后状态转变为共享
  • 无效（Invalid, I）：表示该缓存行无效，即为空。上文提到的缓存策略会优先填充无效行

简单来说，MESI的设计目标在于：

  1. 防止多个处理器核心同时对共享数据进行修改。任何需要修改共享数据的核心都会先发出RFO（Read For Ownership）请求来获取该缓存块的所有权，并使其他处理器核心中的相应缓存块变为无效。
  2. 通过推迟写回操作来减少对内存的频繁修改，确保只有在必要时才将缓存中的更改写回内存。

MESI 的状态转移

MESI 协议的状态转移如下：

  • 从无效（I）到独占（E）：当 CPU 需要写入一个缓存行而该行当前状态为无效时，如果其他 CPU 缓存中没有该缓存行的副本，该行状态变为独占。这表明当前 CPU 缓存中的数据是最新的，且没有其他副本存在
  • 从无效（I）到共享（S）：当 CPU 需要读取一个缓存行而该行当前状态为无效时，如果其他 CPU 缓存中存在该缓存行的副本，则该行状态变为共享
  • 从共享（S）到独占（E）：当一个 CPU 想要写入一个处于共享状态的缓存行时，必须首先获取其他所有 CPU 上该缓存行的独占访问权，如果成功，该缓存行状态变为独占
  • 从独占（E）到修改（M）：当 CPU 对处于独占状态的缓存行进行写操作时，该缓存行状态变为修改。这表示数据已被当前 CPU 修改，且与主存不同步
  • 从修改（M）到共享（S）：当其他 CPU 请求读取处于修改状态的缓存行时，当前 CPU 必须将该缓存行的数据写回主存，并将缓存行状态改为共享，以便其他 CPU 可以读取最新数。
  • 从任何状态到无效（I）：当 CPU 接收到其他 CPU 发出的无效化请求时，如果当前 CPU 缓存中有该缓存行的副本，不论它处于何种状态，都必须将其标记为无效。这通常发生在其他 CPU 想要写入同一缓存行的情况下

可以使用这个简单的模拟器来模拟MESI协议的工作状态

MESI的优化

随着多核处理器的普及和系统复杂度的增加，MESI协议面临着性能瓶颈和效率问题。因此，为了提高系统性能和缩短响应时间，对MESI协议的优化变得非常必要。

写缓冲区（Store Buffer）机制

在进行写入操作时，一个CPU核心（例如核心1）首先需要广播一个读取为了写入（Read For Ownership，RFO）请求，以获得对应数据的独占访问权。在等待其他核心响应此请求并发送回确认信号（ACK）期间，核心1原本需要空闲等待，这无疑是对CPU资源的一种浪费。

为了提高效率，现代CPU设计了“写缓冲区”机制。通过这种机制，当核心1发出RFO请求并将写入操作放入写缓冲区后，它可以立即继续执行其他任务，而不需要等待ACK的到来。一旦收到ACK，CPU再从写缓冲区中取出写入操作，实际写入到缓存中。这样不仅优化了CPU的工作流程，还提升了处理器的整体效能。

失效队列（Invalidation Queue）

为了解决核心在忙碌时无法及时响应RFO请求的问题，现代CPU引入了“失效队列”机制。收到的RFO请求被放入失效队列，并立即发送回ACK，待核心完成手头上的任务后，再处理失效队列中的请求。这种设计有效地缩短了等待时间，加速了数据同步过程。

MESI的潜在问题

False Sharing

由于CPU以64B的Cache Line为最小单位从内存中加载数据，可能会出现这样的问题：

假设变量a和b位于同一个Cache Line中，当前CPU0和CPU1都将这个Cache Line加载到Cache，CPU0只修改变量a，CPU1只读取变量b。当CPU0修改a时，CPU1的Cache Line会变为Invalid状态，即使CPU1并没有修改b，这会导致CPU1从内存或其它核心重新加载Cache Line中的所有变量，影响性能。这就是False Sharing。

解决False Sharing的常用方法是进行字节填充，在a和b之间填充无意义的变量，使一个变量单独占用一个Cache Line。

RMW操作

在并发编程中，读-改-写（RMW）操作，如比较并交换（CAS）和原子加（ADD），需作为单一的原子操作执行以避免数据竞争。

尽管MESI缓存一致性协议确保了处理器核心间缓存行状态的一致性，它并不解决操作的原子性问题。在RMW操作中，由于从读取到写回的时间窗口内可能发生其他处理器的干预修改，可能导致数据竞争和状态不一致。

在为此，LOCK指令被用来确保RMW操作的原子性，通过锁定操作涉及的缓存行，防止在操作完成前被其他处理器访问，从而有效地解决了数据竞争问题，保障了操作的安全性和数据的一致性。

写缓冲区（Store Buffer）优化带来的潜在问题

写缓冲区带来的最主要的问题是与其他核心的数据一致性问题。由于写操作被延迟执行，其他核心可能在这段时间内读取到了旧的数据值，从而导致数据不一致的问题。此外，写缓冲区可能导致内存顺序的问题，即编写的程序逻辑与实际执行逻辑不符。

失效队列（Invalidation Queue）带来的潜在问题

失效队列提高了响应速度，但它也可能引入新的问题。失效队列允许CPU核心在确认接收到失效请求后，延迟处理这些请求。这种延迟可能导致数据在不同核心间的一致性问题，即一个核心可能会在短时间内继续使用已经失效的数据，而这段时间内其他核心已经修改了这部分数据。

参考链接

Comments

comments powered by Disqus