Cache的工作原理
要讲清楚 Cache 的工作原理，需要回答 4 个问题：
- 数据如何放置
- 数据如何查询
- 数据如何被替换
- 如果发生了写操作，Cache如何处理
2.1 数据如何放置
这个问题也好解决。我们举个简单的栗子来说明问题。
假设我们主存中有 32 个块，而我们的 Cache 一共有 8 个 Cache 行( 一个 Cache 行放一行数据）。
假设我们要把主存中的块 12 放到 Cache 里。
那么应该放到 Cache 里什么位置呢？
三种方法：
- 全相连（Fully associative）。可以放在Cache的任何位置。
- 直接映射（Direct mapped）。只允许放在Cache的某一行。比如12 mod 8
- 组相连（set associative）。可以放在Cache的某几行。例如2路组相连，一共有4组，所以可以放在0,1位置中的一个。
可以看到，全相连和直接映射是Cache组相连的两种极端情况。
不同的放置方式主要影响有两点：
1、组相连组数越大，比较电路就越大，但Cache利用率更高，Cache miss发生的概率小。
2、组相连数目变小，Cache经常发生替换，但是比较电路比较小。
这也好理解，内存中的块在Cache中可放置的位置多，自然找起来就麻烦。
2.2 如何在Cache中找数据
其实找数据就是一个比对过程，如下图所示。
我们地址都以 Byte 为单位的。
但主存于Cache之间的数据交换单位都是块（block，现代Cache一般一个block大约64Byte)。所以地址对最后几位是block offset。
由于我们采用了组相连，则还有几个比特代表的是存储到了哪个组。
组内放着若干数据，我们需要比较Tag, 如果组内有Tag出现，则说明我们访问的数据在缓存中，可以开心的使用了。
比如举个 2 路组相连的例子，如下图所示。
T表示Tag。直接比较Tag，就能得知是不是命中了。如果命中了，则根据index(组号）将对应的块取出来即可。
如上图所示。用index选出位于组相连的哪个组。然后并行的比较Tag, 判断最后是不是在Cache中。上图是2路组相连，也就是说两组并行比较。
那如果不在缓存中呢？这就涉及到另一个问题。
不在缓存中如何替换 Cache ？
2.3 如何替换Cache中的数据
Cache中的数据如何被替换的？这个就比较简单直接。
- 随机替换。如果发生Cache miss里随机替换掉一块。
- Least recently used. LRU。最近使用的块最后替换。
- First in, first out (FIFO), 先进先出。
实际上第一个不怎么使用，LRU 和 FIFO 根据实际情况选择即可。
Cache 在什么时候数据会被替换内？也有几种策略。
- 不在本 Cache 替换。如果Cache miss了，直接转发访问地址到主存，取到的数据不会写到Cache.
- 在读MISS时替换。如果读的时候Cache里没有该数据，则从主存读取该数据后写入Cache。
- 在写MISS时替换。如果写的时候Cache里没有该数据，则将本数据调入Cache再写。
2.4 如果发生了写操作怎么办
Cache毕竟是个临时缓存。
如果发生了写操作，会造成Cache和主存中的数据不一致。如何保证写数据操作正确呢？
也有三种策略。
- 通写：直接把数据写回Cache的同时写回主存。极其影响写速度。
- 回写：先把数据写回Cache, 然后当Cache的数据被替换时再写回主存。
- 通写队列：通写与回写的结合。先写回一个队列，然后慢慢往主存储写。如果多次写同一个数据，直接写这个队列。避免频繁写主存。
