Cache学习（4）：Cache分配策略Cache更新策略Cache逐出策略

Cache的数据流

常用名词

• Allocation 分配
• Eviction 驱逐
• 分配策略和更新策略分别为当产生Cache miss和Cache hit的时候数据流的具体行为

1 Cache分配策略（Cache Allocation Policy）

Cache的分配策略是指不同情况下为数据分配Cache Line的不同行为。Cache分配策略分为读和写两种情况。（分配一般都是发生在miss 情况下，因为hit的时候，直接进行读写即可）

1.1 读分配（Read Allocation）

发生条件： CPU读数据，所需读取数据Cache缺失

数据流操作： 从主存读取数据，分配对应Cache Line空间进行缓存

备注： 默认情况下，Cache都支持读分配

1.2 写分配（Write Allocation）

发生条件： CPU写数据，所写数据对应地址Cache缺失

数据流操作：

• 当不支持写分配时，写指令直接写入主存，只会更新主存数据
• 当支持写分配时，首先从主存中加载数据到Cache Line中（相当于先做个读分配动作），然后会更新Cache Line中的数据

2 Cache更新策略（Cache Update Policy）

Cache更新策略是指当发生Cache命中时，写操作应该如何更新数据。Cache更新策略分成两种：写直通和回写。

2.1 写直通（Write Through）

发生条件： 当CPU执行store指令并在Cache命中时

数据流操作： 更新Cache中的数据并且更新主存中的数据

备注： Cache和主存的数据始终保持一致

2.2 写回（Write Back）

发生条件： 当CPU执行store指令并在Cache命中时

数据流操作：

• 只更新Cache中的数据
• 将dirty bit置位：每个Cache Line中会有一个bit位记录数据是否被修改过，称之为dirty bit（前文的图片中，Cache Line旁边有一个D就是dirty bit）。
• 在Cache Line被替换或者显示的clean操作时，主存中的数据才会进行更新。因此，主存中的数据可能是未修改的数据，而修改的数据躺在Cache中。

备注： Cache和主存的数据可能不一致

为什么Cache Line大小是Cache控制器和主存之间数据传输的最小单位呢？

因为每个Cache Line只有一个dirty bit。这一个dirty bit代表着整个Cache Line是否被修改的状态。

实例

假设有如下Cache

• Cache Size 128 Byte
• Cache Line Size 8 Byte
• Way=1 直接映射缓存
• 策略：写分配和写回机制
• Tag Array中Tag旁边Valid位：是否合法：1代表合法，0代表非法。
• Data Array中dataCache Line旁边的Dirty位：是否脏，可以理解为是否与主存不一样，1代表dirty（Cache中更新过数据），0代表没有写过数据，即非dirty（与主存一致）

行为1：当CPU从地址0x0654读取1个字节，Cache表现如下：

• 根据Index找到对应的Cache Line（图中用绿色表示选中的Cache Line）
• 对应的Tag部分valid bit是合法的（Tag 为 1，如果为不合法的话可以直接刷掉）
• 合法且Tag的值不相等，因此判断发生缺失
• 此时需要从地址0x0650地址（请注意Cache Line大小对齐）加载16 Byte数据到该Cache Line中
• 但是，发现当前Cache Line的dirty bit置位。因此，Cache Line里面的数据不能被简单的丢弃，由于采用写回机制，所以需要将Cache Line中的数据0xFF…FF写回他应该在的主存地址
• 以Cache Line中的Tag为000001111，Index为101，offset为0（因为需要Cache Line大小对齐），所以地址为0000,0111,1101,0000，即为0x07D0

• 当写回操作完成，将主存中0x0650地址开始的16个字节0x00…00加载到该Cache Line中，并清除dirty bit。然后根据offset找到0x0654返回给CPU

2 Cache 逐出策略 （Cache Cache Eviction Policy）

缓存逐出策略

2.1 LRU（Least Recently Used）最久没有使用的优先剔除

假设条件： 最近最少使用的那些信息，将来被使用的概率也不大，所以在容量有限的情况下，就可以把这些不常用的信息踢出去，腾地方。认为最近用到的信息以后用到的概率会更大

逐出条件： 把很久没有用过的信息踢出去，也就是 Least Recently Used 的信息被踢出去

备注： 这个是最常用的逐出策略

2.2 FIFO（First In First Out）先进先出

假设条件： 最先进入Cache的最先被用完，之后被使用的概率低

逐出条件： 把最先进入Cache的数据优先剔除，认为他们被优先用完了

2.3 LFU（Least Frequently Used)）最低频被使用的优先剔除

假设条件： 越是不常用的用的数据之后使用到的概率越大

逐出条件： 计算每个信息的访问次数，踢走访问次数最少的那个；如果访问次数一样，就踢走好久没用过的那个

备注： 这个算法其实很高效，但是耗资源，所以一般不用

Note

Tag Array 存储在硬件 Cache 里，占用真实 Cache 内存。但是我们提到 Cache Size 的时候，并没有考虑 Tag 的占用。所以计算时，请忽略 Tag 占用。

参考文献

Cache的基本原理 - 知乎
LRU Cache_cache age lru-CSDN博客