Linux 内核101:cache组织策略

1,525 阅读2分钟

本文参考了:

简述

上篇文章 讲了 cache 的一些基本知识,提到了一种最基本的 cache 组织策略:Direct Mapped Cache。这种策略优点是实现简单,速度快(这里指的速度快是说定位 cache 位置的速度,因为一个 main memory address对应在 cache 中的位置是固定的),但是有一个严重的缺陷,就是 cache miss 率高。为什么呢?还是看下面这个图,假如 CPU 恰好依次需要0、4、8、12这四个 main memory address 的速度,之后的 block 都会把前面 block 的挤占掉!(尽管现在 cache 中还有很多空余空间)

本文将介绍另外两种 cache 组织策略:Fully Associative CacheSet Associative Cache

Fully Associative Cache

Fully Associative Cache是解决了Direct Mapped Cache cache miss 高的缺陷。它是怎么实现的呢?

对比一下Direct Mapped Cache的示意图,Fully Associative Cache中就没有 index 这个位了,main memory 中的一个block 可以被 map 到 cache 中的任意位置。这种方法,定位main memory block 在 cache 中位置是通过 tag 位来判断的。因为没有 index,所以在 cache 中定位的时候,就需要对比 cache 中每一条记录的 tag,That’s a lot of comparators!

所以,Fully Associative Cache只适用于小的 cache,比如某些 Intel CPU 中的 TLB cache就是Full Associative的。这里说的非常小,顶多也就几十个 entry。虽然这种方法应用也不是很广泛,但是给了我们一种很好的思路:Direct Mapped Cache 定位快,但是 cache miss 几率高;Fully Associative Cache 定位慢,但是 cache miss 率低。那么,可以取一个中间值,使得定位 速度足够快,同时cache miss几率足够低。

Set Associative Cache

Set Associative Cache是Direct mapped cache 和 Fully associative cache的一种取舍。cache 被分成了多个 set,每个 set 里面有多个 cache line。一个 memory block 会先被 map 到其中一个 set,然后置于此 set 中的任一cache line。

Direct mapped cache 可以看做 n * 1的矩阵(n 个set,每个 set 含有一个 entry),Fully associative cache可以看做1 * m 的矩阵,而Set Associative Cache就是 n * m 的矩阵。Direct mapped cache实质上可以看作是 1-way Associative Cache,而Fully associative cache是 m-way Associative Cache。

那么现实生活中,该采用 ?-way Associative Cache呢?一般选择8-way 就足够了,下图的数据可以得到一个直观地感觉。

总结一下

Direct Mapped Cache实现最简单,但是 cache miss 率太高,实际生产几乎不会使用。Fully Associative Cache cache miss 几率最低(理论上可以达到0),但是如何快速定位cache line 所在位置成了个大问题,所以只适用于很小的cache,比如TLB cache。Set Associative Cache是二者的权衡,普遍采用的是8-way Associative Cache。