前面讨论了为什么CPU需要缓存？
有了缓存，如何使用缓存？cache的结构是怎样的？缓存和内存的对应关系是什么？本篇继续讨论这些问题。
根据局部性原理，CPU Cache 在读取内存数据时，每次不会只读一个字或一个字节，而是一块块地读取（Block Transfer），这每一小块数据也叫CPU 缓存行（CPU Cache Line）。
Cache的结构原理图如下：
cache的替换策略已介绍过(常见的缓存数据淘汰算法)，本篇主要讨论cache与内存的地址映射问题。所谓地址映射是指利用某种方法或者规则将主存块定位到cache。
根据缓存和内存的映射关系，Cache映射分为三种类型，分别为直接映射缓存，多路组相连缓存，全相连缓存。下图是三种类型的示例。
一、直接映射缓存
对于直接映射缓存而言，其内存和缓存的映射关系如下所示：
从图中我们可以看出，直接映射缓存会将一个内存地址固定映射到某一行的cache line，但不同cacheline会对应多个内存地址，如0x00，0x40，0x80这三个内存地址对映射到同一cache line。
一个内存地址可划分为三部分，分别是Tag（也叫区号）, Index（也叫块号），Offset。
其中，Tag表示内存中每个block所在的分区号，Index表示内存中每个block块对应的cache行号。offset是指虚拟内存的偏移量。
具体工作机制如下：
-
根据地址中index（块号）位找到cache line；
-
在获取cache-line的数据后，获取其中的Tag值，将其与地址中的Tag值进行对比，如果相同，则代表该内存地址位于该cache line中，即cache命中了；如果不命中（miss），则寻找下一级cache或者内存；
-
最后根据Offset的值去data数组中获取对应的数据。
整个流程大概如下图所示：
试想一下如果我们依次访问了0x00，0x40，0x00会发生什么？
当我们访问0x00时，cache miss，于是从内存中加载到第0行cache line中。当访问0x40时，第0行cache line中的tag与地址中的tag成分不一致，因此又需要再次从内存中加载数据到第0行cache line中。最后再次访问0x00时，由于cache line中存放的是0x40地址的数据，因此cache再次miss。可以看出在这个过程中，cache并没有起什么作用，访问了相同的内存地址时，cache line并没有对应的内容，而都是从内存中进行加载。
这种现象叫做cache颠簸（cache thrashing）。针对这个问题，引入多路组相连缓存。下面一节将讲解多路组相连缓存的工作原理。
二、多路组相连缓存
多路组相连缓存的原理相比于直接映射缓存复杂一些，这里将以两路组相连这种场景来进行讲解，其内存和缓存的映射关系如下所示：
下面还是以8个cache line的两路缓存为例，假设现在有一个虚拟地址是0000001100101100，其tag值为0x19（十六进制19转换为二进制为11001），其index为1，offset为4。那么根据index为1可以找到两个cache line，由于第一个cache line的tag为0x10，因此没有命中，而第二个cache line的tag为0x19，值相等，于是cache命中。
由于多路组相连的缓存需要进行多次tag的比较，对比直接映射缓存，其硬件成本更高，因为为了提高效率，可能会需要进行并行比较，这就需要更复杂的硬件设计。
另外，如果cache没有命中，那么该如何处理呢？
以两路为例，通过index可以找到两个cache line，如果此时这两个cache line都是处于空闲状态，那么cache miss时可以选择其中一个cache line加载数据。如果两个cache line有一个处于空闲状态，可以选择空闲状态的cache line 加载数据。如果两个cache line都是有效的，那么则需要一定的淘汰算法，例如PLRU/NRU/fifo/round-robin等等。
在Intel Core i7中，不同cache的way个数不同。
在多路组相连缓存的情况下，如果我们依次访问了0x00，0x40，0x00会发生什么？
当我们访问0x00时，cache miss，于是从内存中加载到第0路的第0行cache line中。当访问0x40时，第0路第0行cache line中的tag与地址中的tag成分不一致，于是从内存中加载数据到第1路第0行cache line中。最后再次访问0x00时，此时会访问到第0路第0行的cache line中，因此cache就生效了。由此可以看出，多路组相连的缓存可以改善cache颠簸的问题。
三、全相连缓存
从多路组相连，我们了解到其可以降低cache颠簸的问题，并且路数量越多，降低cache颠簸的效果就越好。那么是不是可以这样设想，如果路数无限大，大到所有的cache line都在一个组内，是不是效果就最好？基于这样的思想，全相连缓存相应而生。
下面还是以8个cache line的全相连缓存为例，假设现在有一个虚拟地址是0000001100101100,其tag值为0x19，offset为4。依次遍历，直到遍历到第4行cache line时，tag匹配上。
全连接缓存中所有的cache line都位于一个组(set)内，因此地址中将不会划出一部分作为index。在判断cache line是否命中时，需要遍历所有的cache line，将其与虚拟地址中的tag成分进行对比，如果相等，则意味着匹配上了。因此对于全连接缓存而言，任意地址的数据可以缓存在任意的cache line中，这可以避免缓存的颠簸，但是与此同时，硬件上的成本也是最高。
参考：图文并茂，带你认识CPU缓存那些事儿 – 知乎 (zhihu.com)