目录
一.概要
二. Cache的工作原理
1、Cache命中率
che-主存储系统效率
2、Cache的基本结构
3、缓存读写操作
写入缓存
改进的缓存
三. cache主存的地址映射
1、直接映射
2、全联系测绘
3、小组合作测绘
四.常见置换算法
http://www.Sina.com/http://www.Sina.com /
要使用高速缓冲存储器，必须遵循程序访问的局部原理。 这意味着要求CPU使用的指令大部分都在缓存中。
一、概述
如果“时间局部性”(Temporal Locality )信息项目已被访问，则很可能会在近期内再次访问。 程序的循环、堆栈等是产生时间局部性的原因。
空间局部性：用于最近的将来的信息很可能在空间地址上接近当前使用的信息。
顺序局部性(Order Locality )典型的程序中，除了分支指令外，几乎所有的指令都是依次执行的。 依次执行和非依次执行的比例大致为5:1。 此外，对大型数组的访问也是顺序的。 命令的顺序执行、数组的连续存储等是产生顺序局部性的原因。
二、Cache的工作原理主存和缓存按块存储，块的大小相同，块内的地址相同。
cache的结构其实和内存的结构很相似，也包含地址和内容。 但是，cache的内容中除了保存的数据(data )以外，还包含要保存的数据的物理存储器的地址信息(tag )。 由于CPU发布的所有地址信息都发布到物理内存中，因此cache除了保存数据信息外，还保存与数据对应的地址。 然后在cache中(当然，为了加快搜索速度，cache通常还包含一个有效位(valid )，用于标记此cacheline是否包含有效数据)。 由一个tag和相应的数据构成的一行称为cacheline。 如下图所示，下表中的一行是cacheline。
图2知道cache的结构
后，如何在cache中去寻找对应的数据呢？简单起见，我们先选择直接映射的cache组成方式（参见下文）进行下文的分析。首先对于一段物理内存（block），该物理内存上的每个字节的地址划分为以下几段：
图三这样的话物理内存中的数据到cache的映射关系如下图所示：
图四上图四的映射原则就是：根据物理地址的中间三位（index字段）来定位当前数据应该在cache的哪一行，把物理地址的tag字段和该地址对应的内容放入对应的cache line的tag字段和data字段，并把相应的valid位置置为1。那么在之后进行cache寻找的时候就可以根据cache line的tag字段来辨认当前line中的数据是数据哪个block的。
上图四中的地址00 000 00~11 111 11按照图三的原则进行地址划分：地址的最高两位为Tag字段；中间三位为index字段；最低两位为Block Offset 字段。
由于Block Offset是两位，也就是一个block的大小是2²=4个字节的数据，也就是一个cache line的data字段包含4个字节的数据；index为3位，说明cache共包含2³=8个组（对于直接映射的cache，也称为8个行）；很明显，cache的一个行中只能存储1 块(Block )=4字节的数据，但是按照图四的映射方式，会有2^(tag位数) = 2^2 = 4块的数映射到同一个行，此时通过Tag字段的比较来辨别是不是我们要取数据的地址，如果不是的话，也就是发生了cache的缺失。
如图四的Block 0和Block 1的index字段都是000，按照上面的理论它们都应该映射到第 000=0行（这儿的行也就是组，因为图四是直接映射的cache），但是现在第0行的内容是K、L、M、N，也就是Block 1的内容，为什么呢？仔细看该cache line的tag=01，映射到第0行的块只有Block 1的tag字段=01，所以可以得知此时该cache line中存储的数据是Block 1的数据，此时如果CPU发出的访存请求是访问Block 0 的话，也就是发生了缺失。此时进一步定量分析的话，共有4个数据块竞争使用cache 第0行的位置，也就是说cache的命中率为25%。
上面的过程总结起来就是：
物理内存的索引字段(Index)选择cache 的行，通过对比物理内存和cache line的Tag来判断是否命中。块偏移字段(Block Offset)可以从cache line的数据块中选择期望数据。注意在这个过程中cache的index是不占空间的，它就类似于物理内存的地址，对于物理内存来说是通过地址去寻找数据，对于cache来说，是通过index来找到对应的cache line，或者更通俗的讲就是：cache line的地址对应的就是物理内存的index字段。
此时该cache的容量计算如下：每一个cache line的数据字段占4个字节，共2³=8行，所以数据占据4×8=32个字节，一个cache line中tag字段和valid位占2+1=3bit，整个cache的tag+valid=3bit×8行=24bit=3Byte，通常情况下我们都是以cache中数据部分占的空间表示cache的容量，也就是32字节，但是实际上，它还额外多占用了3字节的存储空间。
1、Cache命中率 主存和缓存 按块存储， 块的大小相同；缓存共有 C 块，主存共有 M 块 ，主存 M 块的数量>>(远远大于) 缓存 C块的数量 命中： 主存块 调入 缓存，主存块与缓存块 建立 了对应关系，用 标记记录 与某缓存块建立了对应关系的 主存块号 未命中： 主存块与缓存块 未建立 对应关系，主存块 未调入 缓存 Cache 的命中率 ：CPU 欲访问的信息在 Cache 中的 比率 ，命中率 与 Cache 的 容量 与 块长 有关 ，一般每块可取 4 ~ 8 个字 ， 块长取一个存取周期内从主存调出的信息长度 Cache –主存系统的效率 效率 e 与 命中率 有关 设 Cache 命中率 为 h ， 访问 Cache 的时间为 t c ， 访问 主存 的时间为 t m 2、Cache 的基本结构将主存地址映射到缓存中称为地址映射，将主存地址变换成缓存地址称为地址变换，当新的主存块需要调入缓存中，而它的可用位置又被占用时，需根据替换算法解决调入问题。
3、Cache 的读写操作如果命中缓存，直接从缓存中获取信息，如果没命中，从主存中查找信息。如果缓存Cache满，根据替换算法，把从主存中读取的信息放入缓存。
Cache的读操作流程图
Cache 的写操作 写直达法（Write – through） 写操作时数据既写入 Cache又写入主存， 写操作时间就是访问主存的时间 ， Cache块退出时，不需要对主存执行写操作，更新策略比较容易实现。 优点：主存和缓存数据始终保持一致缺点：同一时间内可能对同一主存进行反复的写 写回法（Write – back） 写操作时只把数据写入 Cache 而不写入主存，当 Cache 数据被替换出去时才写回主存， 写操作时间就是访问 Cache 的时间， Cache块退出时，被替换的块需写回主存，增加了 Cache 的复杂性。 优点：写操作时间就是访问 Cache 的时间缺点：主存和缓存数据不一致，多系统情况下会出现数据一致性问题 Cache 的改进（1）对Cache进行分级，增加Cache的级数
（2）分立缓存，把指令 Cache和数据 Cache分开，避免在流水的过程中造成资源冲突。
三、Cache –主存的地址映射 1、直接映射主存中的任意块映射到缓存中的唯一块，每个主存块只与一个缓存块相对应，但是实现简单。
特点：不灵活，每个主存块只能与固定对应某个缓存块，即使还空着许多位置也不能使用。这使得直接映射的块冲突概率最高，空间利用率最低。
2、全相联映射直接映射的另一个极端，可以把主存数据块装入 Cache 中的任何位置。全相联映射方式的优点是比较灵活，Cache 块的冲突概率低，空间利用率高，命中率也高，缺点是地址变换速度慢，实现成本高。
3、组相联映射组相联映射是直接映射和全相联映射相结合的方式，将主存和cache都分成若干段，并且使他们每组所包含的块数都相等，组之间采用全相联映射，组内块之间采用直接映射。
直接映射和全相连映射的折中。
四、常见替换算法（1）FIFO(First In First Out)：遵循先入先出原则，若当前Cache被填满，则替换最早进入Cache的那个。
（2）LRU(Least Recently Used)：最近最少被使用的被替换，也就是替换最后一次访问时间最久远的那个。
（3）LFU(Least Frequently Used)：最不常使用的被替换，也就是过去某个时间窗口里引用次数最少的那个。