存储系统

背景

问题提出

Cache的出现，可以一定程度上解决以下三个方面的问题：

• 解决DRAM主存与CPU速度之间的不匹配
• 解决CPU与I/O的访存冲突
• 避免CPU“空等”现象

理论基础

局部性原理（程序访问的局部性原理）

Cache思想

Cache体现的是一种思想：“缓存”思想，即将经常被用到的东西，放到更加容易方便获取的地方。

Cache的使用

• CPU内部集成了两级Cache，即L1CACHE，L2CACHE
• 主板上有Cache
• 硬盘、打印机、CD-ROM（只读光盘）等外围设备都加上了Cache；
• 访问网站时都会在本地保存网站的cookie；

“块”

数据块————把若干存储单元称为一个数据块；
此外，内存与Cache之间是以数据块为单位进行交换的。

Cache工作原理

主存和缓存的编址

主存储器和缓存地址都分成了两段，

• 主存：高m位表示主存块地址，低b位表示块内地址
• 缓存：高c位表示缓存的块号，低b位表示块内地址

命中与未命中

缓存的高c位表示存放的是哪一个主存块，相当于主存块的块号，CPU在访问Cache时，用主存地址的m位与标记位比较，确定是否命中。

• 命中，则主存块已经调入缓存，主存块与缓存块已经建立了对应关系。
• 未命中，则主存块未调入缓存，主存块与缓存块未建立对应关系。

命中率

命中率是衡量Cache效率的主要指标。

可见，主存、缓存都用b位表示块内字数，即 $ 2^b $ 用以表示块的大小，称为块长。

主存-Cache地址映像

即将CPU送来的主存地址变换成Cache地址。依赖于主存Cache地址映像变换机构。
映射方式包括：

• 直接映射
• 全相联映射
• 组相联映射
• 段相联映射

直接映射方式

记Cache块号为i，主存块号为j，Cache总块数量为C，则映射为：

可以看出，每一个Cache块i可以对应多个主存块；
而每一个主存块j只能和一个Cache缓存块i对应。

但是，由于每一个Cache缓存块可以和 $ 2^{m-c}个主存块对应 $，故主存地址高位有t=m-c位为主存字块标记，Cache也有t位记录当前对应的是哪一个主存（块号）。

全相联映射方式

即主存中的每一个字块映射到Cache中的任何一块位置上。
由于每一个Cache块对应全部的主存块，因此主存字块标记位有m=t+c位，Cache也有m位。

组相联映射方式

即Cache分为Q组，每组R块，则主存块j与Cache组号i之间的映射为：

可以看出，主存块与Cache之间是直接映射，主存块同Cache特定组内的块是全相联映射。

替换策略

何为替换

当一个新的主存块需要拷贝到Cache中，而允许存放该新块的位置被其他的主存块占用时，就需要替换。
由硬件完成。

替换算法

1. 先进先出算法
   即将最先调入Cache的字块替换出去。
2. 近期最少使用算法
   即将近期内最少使用的字块替换出去。
3. 随机法

写操作策略

Cache应该与主存内容保持一致，而CPU对Cache的写入会改变Cache中的内容，因此如何保持Cache与内存内容的一致性，就需要采取策略。

1. 写回法
   • 当CPU与Cache命中时，只修改Cache中的内容，而不立即写入主存，只有当该块被替换出时，才写回主存。
   • 优点：减少了CPU访问主存的次数。
   • 缺点：写内存与写Cache是异步进行的，故存在内存与Cache不一致的隐患。
   • 注意：为了区别Cache中的块是否经过了修改，另设标志位，“清”表示未修改过，“浊”表示已修改过。
2. 全写法
   写Cache命中时，数据既写入Cache，也写入主存。
   未命中时，数据只直接写入内存。
3. 只写主存法
   • 当写Cache命中时，信息只写入主存，同时将相应的Cache块置为失效，也就是说，下一次需要时，再重新调入。
   • 这种写法效率低下。

虚拟存储器

• 当前计算机系统中，三级结构的存储器系统：
  • 高速缓冲存储器
  • 主存储器
  • 虚拟存储器

三级不同的存储器存放的信息必须满足如下两个原则：

• 一致性原则：同一个信息在几个级别的存储器中必须保持相同的值。
• 包含性原则：处在内层的存储器中的信息一定被包含在外层的各个存储器中。

存储器的校验

奇偶校验码

被传输N位，加入一位校验位，使得整个N+1位信息中“1”的个数为偶数（或者奇数），称为偶校验（奇校验）。

汉明码

汉明码是一种可以纠正一位差错的编码。

纠错理论：L - 1 = D + C,
其中，L是编码的最小距离，D是检测错误位数，C是纠正错误的位数
也就是说，要想编制具有更多位纠错能力的编码，则要求L更大。

汉明码的组成

• 海明码的位数：海明码需增添k位检测位
• 海明码的位置
  每一个增添的检测位，负责检测一个小组，通常一个小组包含位数较多。
  组：1，3，5，7
  组：2，3，6，7
  组：4，5，6，7
• 海明码的取值

汉明码的纠错

实际上，是对传送后的汉明码形成新的检测位P，根据P的状态，可以直接指出错误的位置。

循环冗余校验码

模2运算

二进制数的运算

CRC码的编码方法

k位校验码，位于原信息位的后面；
拿到题目给出的多项式G(x)，用多项式去除，拿到结果的余数，即为校验位。

CRC码的检错与纠错

CRC码某一位出错，除以G(x)的结果必不为零。不同的出错位，其余数也不尽相同。
将不为零的余数补0继续模2除，得到下一信息位的出错余数；出错信息位对应的余数构成一个循环————“循环码”。

字符的表示

• 字符
• EBCDIC码
• ASCII码
• 汉字编码
• Unicode码