高速缓存，写缓冲器和无效队列

高速缓存

由于处理器的运行速度远远大于内存的读写速度，为了提高性能，所以硬件设计者引入了高速缓存的概念。
高速缓存是一种速度比内存快，但大小远远比内存小的存储部件。有了它之后，处理器不再与内存发生直接的操作，而是读写高速缓存里的数据，高速缓存在与内存发生读写操作。

缓存的结构

缓存的结构类似HashMap，是链表散列结构的。有若干个通，每个桶里面都是一个链表。
每个链表节点就是一个缓存条目（Cache Line），缓存条目由三部分组成：Tag，Data Block，Flag

• Tag：包含缓存行中数据的位置信息
• Data Block（缓存行）：存储从主内存中读取的数据以及准备写入主内存的数据，一个缓存行可存储多个变量
• Flag：缓存行的状态信息

CPU访问内存时，会通过内存地址解码的三个数据：index（桶编号）、tag（缓存条目的相对编号）、offset（变量在缓存条目中的位置偏移）来获取高速缓存中对应的数据。

缓存一致性协议（MESI）

由于每个处理器都有自己的缓存，当多线程并发访问同一共享变量时，就会出现这些线程所在的处理器都会有一份该变量的副本。
当一个线程对副本进行修改后，副本间的数据如何同步呢？这时就要靠缓存一致性协议

MESI定义

• Modified

该缓存条目的数据是被修改过的，且与主存的数据不一致（还未写回主存）。在任一时刻，多个处理器的高速缓存，相同tag的缓存条目只有一个能处于
该状态。

如果其它处理器要读取同一tag的缓存条目数据之前，要先等数据写回主存。在数据写回主存之后，该缓存条目的状态变为独享的。

• Exclusive

已独占的方法保存着副本数据，其它高速缓存的变量副本都是无效的。该缓存条目的数据与主存数据一致。

当有其它处理器读取该数据时，该缓存条目的状态变为共享的。如果有处理器修改了该缓存条目的数据，状态则变为修改的。

• Shared

该缓存条目被多个高速缓存同时缓存。且它们的数据都与主存中的一致。

当有缓存对该缓存行的数据进行修改时，改缓存行的状态变为无效的。

• Invalid

该缓存行是无效的，不包含任何内存地址对应的有效副本数据。该状态是缓存条目的初始状态。

MESI消息

请求消息	描述	返回消息	描述
Read	通知其他处理器，主内存正准备读取某个数据。该消息包含待读取数据的内存地址	Read Response	返回请求读取的数据，该消息可能是主内存返回的，也可能是其他高速缓存返回。
Invalidate	通知其他处理器将高速缓存中指定内存地址对应的缓存条目状态置为I（无效），即通知这些处理器删除指定内存地址的副本数据	Invalidate Acknowledge	接收Invalidate消息必须回复该消息，表示已经删除其高速缓存上面的数据
Read Invalidate	由Read和Invalidate组合而成的复合消息。作用在于通知其他处理器，当前处理器准备更新（Read-Modify-Write）一个数据，请求其他处理器删除自己高速缓存中的副本数据。	Read Response与Invalidate Acknowledge	接收到请求的处理器必须返回这两个消息
Writeback	该消息包含需要写入主内存的数据及其对应的内存地址

处理器在执行内存读写操作时，在有必要的情况下会往总线发送特定的请求消息，同时每个处理器还会嗅探（也称拦截）总线中由其他处理器发出的请求消息并在一定条件下往总线回复相应的响应消息。

MESI总结

从上面可以看出，MESI协议对内存数据的访问控制类似于读写锁。多个高速缓存同时对同一变量副本进行读的操作是并发的，而写的操作是独占的。

并发读

当处理器Processor 0要读取缓存中的数据A时，如果发现A所在的缓存条目状态为M、E或S，那么处理器可直接读取数据。

如果A所在的缓存条目状态状态为 I，说明Processor 0的缓存中不包含A的有效数据。这时，Processor 0会往总线发送一条Read消息来读取A的有效数据，而缓存状态不为 I 的其他处理器（如Process 1）或主内存（其他处理器缓存条目状都为 I 时从主内存读）收到消息后需要回复Read Response，来将有效的A数据返回给发送者。

需要注意的是，返回有效数据的其他处理器（如Process 1），如果状态为M，则会先将数据写入主内存，此时状态为E，然后在返回Read Response后，再将状态更新为S。
这样，Processor 0读取的永远是最新的数据，即使其他处理器对这个数据做了更改，也会获取到其他处理器最新的修改信息。

互斥写

处理器Processor 0要对缓存中的数据A时进行写操作时，如果发现A所在的缓存条目状态为M、E，那么处理器可直接对数据进行写的操作。完成后再把缓存条目的状态改为M

如果缓存条目状态为 S 则会先向总线发送Invalidate消息，来通知其他高速缓存该缓存条目无效，获得该缓存条目的独占权。当收到拥有该数据副本的处理器返回的Invalidate Acknowledge，
才确认已获得该缓存条目的独占权，再将数据A写入，并把缓存条目的状态改成M。

如果缓存条目状态为 I 则会先发送Read Invalidate消息，先获取最新的数据，再通过 Invalidate来获取独占权。

需要注意的是，如果接收到Invalidate消息的其他其他处理器，缓存条目状态为M，则该处理器会先将数据写入主内存（以方便发送Read Invalidate指令的处理器读到最新值），然后再将状态改为I

写缓冲器和无效化队列

根据缓存一致性协议，实现了对数据的共享读和互斥写，按理说已经解决了数据的一致性问题，那么又为什么还会出现”可见性”这样的问题呢？

原因在于写缓冲器和无效化队列的引入。MESI协议虽然解决了缓存一致性问题，但其本身有一个性能缺陷：处理器每次写数据时，都得等待其他所有处理器将其高速缓存中对应的数据删除，
并接收到它们返回的Read Response与Invalidate Acknowledge消息后才执行写操作。这个过程无疑是很消耗时间的。

写缓冲器

写缓冲器是处理器内部一个容量比高速缓存还小的高速存储部件，每个处理器都有自身的写缓冲器，且一个处理器无法读取另一个处理器上的写缓冲器内容。
写缓冲器的引入主要是为了解决上面提到的MESI的写性能问题。

写操作

如果相应的缓存条目状态为 E、M，则直接写入

如果相应的缓存条目状态为 S， 处理器会将写操作相关信息存入写缓冲器，并发送Invalidate消息。（不再等待响应消息）

如果相应的缓存条目状态为 I，将写操作相关信息存入写缓冲器，并发送Read Invalidate消息。（不再等待响应消息）

当处理器将写操作写入写缓冲器后，则认为写操作已经完成。而实际上，当处理器收到其他所有处理器回应的Read Response、Invalidate Acknowledge消息后，处理器才会将写缓冲器中对应的写操作写入相应的缓存行，这个时候，写操作才算真正完成。

写缓冲器让处理器在执行写操作时不需要再额外的等待，减少了写操作的等待，提高了处理器的指令执行效率。

读操作

引入写缓存器后，处理器读取数据时，由于该数据的更新结果可能仍然停留在写缓冲器中，所以处理器会先从写缓冲器中找寻数据，没有找到时，才从高速缓存中找。

这种处理器直接从写缓冲器中读取数据的技术被称为：存储转发

无效化队列

处理器在接收到Invalidate消息后，并不马上删除消息中指定地址对应的副本数据，而是将消息存入无效化队列之后就回复Invalidate Acknowledge消息，从而减少了执行写操作的处理器的等待时间。

需要注意的是，有些处理器（如X86）可能并没有使用无效化队列

新问题

写缓冲器和无效化队列的引入带来了性能的提高，同时又带来了新的两个问题：内存重排序与可见性

内存重排序

如下表，变量data初始值为0，变量ready初始值为false。两个处理器Processor 1和Processor 2在各自的线程上执行上述代码。执行的绝对时间顺序为 S1——>S2——>L3——>L4

Processor 1	Processor 2
data = 1; // S1
ready = true; // S2
	while(!ready) continue; //L3
	system.out.println(data); //L4

• 以StoreStore（写又写）操作为例，看写缓冲造成的重排序。如果S1步data值的写操作被写入写缓冲器、还没真正的写到高速缓存中，而S2步的ready值的写操作已经写入到了高速缓存。那在L3步读取ready值时，根据MESI协议，会读到正确的ready值：true；但在L4步读取data时，会读到data的初始值0，而不是在另外一个处理器写缓冲器中的值：修改值1。在处理器Processor 2看来，S1和S2的执行顺序就好像反了一样，即发生了重排序。
• 以LoadLoad（读又读）为例，看无效化队列造成的重排序。同上面的步骤，S2已被同步到高速缓存，S1写入写缓冲器，并发送了Invalidate消息。当执行L3时，读取到正确的值：true，当执行到L4时，由于无效化队列，Processor 2虽然发送了Invalidate Acknowledge消息，但并没有删除自己高速缓存中的data数据，所以会读取到其高速缓存中的data：0

可见性

因为写缓冲器中的内容是无法被其他处理器读取的，这个也就造成了一个处理器更新一个共享变量后，对其他处理器而言，看不到这个更新的值，即可见性。

看似内存重排序和可见性是一样的问题，都是因为数据被写到了写缓冲器，没有及时写到高速缓存中，从而产生了这么个“时间差”