CSAPP Cache 详细解析

前言

又要来推荐CSAPP这本书啦。很多同学可能写了这么久代码，计算机的基本工作方式都不太懂，看这本书会给你一种融会贯通的感觉，小到二进制位级操作，大到手撸web服务器。

今天主要整理下Cache的运行机制。

什么是Cache

编程说到底其实就是对数据的操作。CPU通过各种总线从读取数据，放入ALU(运算器)进行运算，然后再把数据放回主存中。下面是一个简单的示意图。

很明显。数据运输过程的时间，就是性能的提现。没有数据CPU只能在那里等待.所以为了加快主存到CPU的速度，系统设计者采取了存储设备分层的结构.

Cache又称为高速缓存存储器，是一种非常小非常快的存储器，同时也非常贵，放在CPU和主存之间，相当于中介的存在，每当CPU取数据的时候总是先从Cache中找，如果Cache没有，再到主存找。

CPU和主存直接会放置多个Cache，越靠近CPU则越小越快越贵。

局部性

程序一般使用数据，都倾向于使用地址靠近的数据，或者是最近刚刚使用过的数据。回想下你之前写的程序是不是这样。比如说数组，一整块连续的地址循环访问。不断访问同一个数据去做求和之类的操作。所以分为如下:

时间局部性

空间局部性

Cache工作原理

查找Cache中数据时，找到了称为Hit,没找到则称为Miss。

Cache Miss Type

Miss的情况分为三种：

Cold Miss.也就是第一次找的时候，Cache不含数据，当然是Miss。

Conflict Miss.比较有意思的一种的情况。比如说第一次查找数据0，第一次时不含数据属于Cold Miss，然后就去主存中找，放到Cache中，第二次查找需要数据8，又没有，继续去主存那里找，注意！，8把放到Cache中时覆盖了0，第三次你又需要0了，然后就悲剧了，不断0,8,0,8,0,8,0,8 Miss,当然这里涉及到一个写策略。

Capacity Miss.这种也比较容易理解，就是你需要的数据超过Cache的大小了，当然Miss了。

Cache Replacement Policies(Cache替换策略)

Random 随机替换

LRU Least Recently Used，替换最近最少使用的数据

FIFO 这个应该很熟悉先进先出法。先保存的数据先出去

Cache 查找原理

了解查找之前先要知道Cache的组成结构，总共分为两块。

set

line

一块Cache，有多个set，一个set有多行line.

set个数取决于你是几位的机器，因为查找数据的时候是根据地址来区分是哪个set的。

line中又分成三块。

valid bit 标志位，标志这块数据是否有效。

tag 相当于身份证，只有部分地址和这个tag对上以后，才能继续访问block。

block 数据真正存放的地方。

那么地址又是如何划分的呢？也是分成三块

tag 对应前面line的tag。

set index 用来查找属于哪个set。

block offset 块偏移量确定数据的位置。

我这么讲可能比较抽象，直接看下图，再对照着看上面的文字，应该比较容易理解。

所以Cache的查找过程是怎么样的呢？

1.根据set index找到属于哪个set

2.查找set中的每一行line

3.先看valid bit是否有效

4.接着比对tag

5.根据block offset获取数据

回写策略

回写指的是，保持数据一致性，需要写回到主存中，这也很好理解，不回写的话数据就不同步了。

Write-through 直接把数据写回到主存中

Write-back 等知道数据在Cache中要被覆盖了再写回到主存中

Reference

CSAPP
CMU 15213
维基百科

原文地址：http://threezj.com/2016/05/04/CSAPP Cache 详细解析/