1、高速缓存与硬件基础

一、高速缓存

1、高速缓存概念

• 由来：当代处理器的速度远远大于主内存的访问速度，为了弥补处理器与主内存之间的鸿沟，硬件设计者们在处理器和主内存之间引入了高速缓存。
• 概念：高速缓存是一种存取速度远比主内存大而容量远比主内存小的存储部件。

2、高速缓存数据结构与缓存行概念

有了高速缓存后，处理器执行内存的读写操作的时候并不是直接与主内存打交道，而是通过高速缓存来执行

变量名相当于内存地址，变量值相当于相应内存空间存储的数据。也就是说高速缓存相当于为程序访问的每一个变量保留了一份，相应内存空间所存储数据（变量值）的副本。

• （1）高速缓存存储结构：

高速缓存相当于一个由硬件实现的容量很小的散列表，其键是一个内存地址，其值是一个内存数据的副本或者准备写入内存的数据。并通过“链地址法”解决hash冲突。

高速缓存存储结构

• （2） 缓存行：

缓存条目可被进一步的划分为Tag、Data Block和Flag部分。

• Data Block被称之为缓存行，是高速缓存和主内存之间进行数据交换的最小单元，用于存储从内存中读取或者准备写入内存的数据。
• Tag包含了缓存行中数据相应的内存地址的部分信息
• Flag用于表示相应缓存行的状态信息

缓存行结构

缓存行的大小通常是2的倍数，大小在16-256（2^4-28）字节之间，从代码角度看，一个缓存行可以容纳多个变量的值，而多个变量的值可以存储在同一个缓存行中。

• （3）缓存命中

处理器在执行内存访问操作的时候会将相应的内存地址进行解码，解码为包含（index，tag，offset）的数据结构。（1）index相当于桶编号，用来定位内存地址对应的桶（2）tag相当于缓存条目的相对编号，（一个桶可能包含多个缓存条目）用于确定一个具体的缓存条目（3）offset是缓存行的位置偏移，（一个缓存行可以有多个变量的值），用于确定一个变量在缓存行中的存储起始位置。

根据内存地址的解码结果，如果高速缓存能够找到相应的缓存行并且缓存行所在缓存条目的flag表示相应的缓存条目是有效的，就称相应的内存操作产生了缓存命中，否则就产生了缓存未命中。

• 从性能上来说，应该尽量的减少缓存未命中，因为当缓存未命中时候，处理器直接从内存中加载数据并存入高速缓存中，会导致处理器停顿不能处理其他指令；但是高速缓存的容量远远小于主内存，同一个缓存行在不同时刻可能存储的是不一样的数据，因此缓存未命中又是不可以避免的。因此采用多级缓存来尽量较少缓存未命中。
• （4）多级缓存架构

现代处理器一般有多个层次的高速缓存，距离处理器越近的高速缓存，其存取速度越快，制造成本越高，容量越小。

处理器多级缓存架构

二、缓存一致性协议

• 缓存一致性问题：多个线程并发访问同一个共享变量的时候，这些线程的执行处理器上的高速缓存各自保留了一份该共享变量的副本，这就带来了一个问题，一个处理器对其副本进行修改后，其他的处理器如何察觉到并作出相应的反应，以保证处理器后续读取到这个变量的时候能读取到这个更新。也就是说如何防止读取脏数据和更新丢失问题。
• 缓存一致性协议：为了处理这个问题，处理器之间规定一个一种通信机制-“缓存一致性协议”。
• MESI：是一种广泛使用的缓存一致性协议，x86处理器所使用的缓存一致性协议就是基于MESI协议的。

通过MESI，在多线程共享变量的情况下面，已经能保证一个线程对共享变量的更新对其他处理器上的运行的线程来说是可见的了。

三、硬件缓存区：写缓冲器和无效化队列

• MESI虽然解决了一致性问题，但是有一个弱点-处理器在执行写操作的时候，必须等待其他所有处理器将其高速缓存中的相应副本进行删除并接受这个更新处理器所回复的消息后才可以将数据写入高速缓存中，也就是说会影响性能。为了规避和减少等待造成的写操作的延时，硬件设计者们引入了写缓冲器和无效化队列概念。
• 写缓冲器：是处理器内部的一个容量比高速缓存还小的私有高速存储部件。每一个处理器都有其写缓冲器，写缓冲器可能包含多个条目。
• 无效化队列：

引入写缓冲器和无效化队列后，能减少处理器写操作的延迟，提高处理器的执行指令效率。但是同时引入了新的问题--内存重排序和可见性问题，缓冲器和无效化队列都有可能导致内存重排序，同时由于写缓冲器是处理器私有的，它的变更并不会对其他处理器可见，因此存在着可见性问题（可以说写缓冲器是可见性问题的根源）

四、内存屏障

• 为了使一个处理器上运行的线程对共享变量所做的更改可以被其他处理器上运行的线程所读取，我们必须将写缓冲区的内容写入其所在处理器的高速缓存中，从而使该更新在缓存一致性协议的作用下可以被其他处理器读取到。就需要在一定条件下面，会将写缓存区中的冲刷到对应高速缓存中。但是从程序对一个或者一组变量更新的角度看，处理器本身并不能保证冲刷对于程序来说是即时的。而为了保证一个处理器对共享变量所做的更新可以被其他处理器同步，编译器等底层系统需要借助一类被称为内存屏障的特殊指令，内存屏障中的存储屏障可以使执行该指令的处理器冲刷其写缓冲区。

• 为了保证一个处理器对共享变量所做的更改可以被其他处理器同步，编译器等底层系统需要借助一类称为内存屏障的特殊指令，内存屏障中的存储屏障可以使执行该指令的处理器冲刷其写缓冲器。而内存屏障的加载屏障解决了无效化队列造成的可见性问题。

• 同时内存屏障也有禁止指令重排序的作用