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
维基百科