虚拟内存

1. 存储器层次结构
   1. 高速缓存存储器
   2. 高速缓存的分类
      1. 直接映射高速缓存
      2. 组相连高速缓存
      3. 全相连高速缓存
   3. 关于高速缓存写的问题
   4. 高速缓存参数的性能影响
   5. 编写高速缓存友好的代码
2. 虚拟内存
   1. 物理和虚拟寻址的概念
   2. 地址空间
   3. 虚拟内存

下学期看完了OSTEP这本书, 但是感觉对于虚拟内存以及其相关的程序加载机制一直有些模糊, 然后开始做CSAPP的malloc lab, 发现这本书对于虚拟内存相关的知识讲的比较全面, 于是参考CSAPP的思路来整理一下相关的知识.

存储器层次结构

由于不同层次单位容量造价不同以及他们之间访问速度的差异, 以及良好软件的局部性的存在, 这两种软件和硬件的性质完美互补使得存储器层次结构产生.

存储器层次结构的核心思想是: 对于k, 位于k层的更快更小的存储设备作为k + 1层的更大更慢设备的缓存(caching), k + 1层的存储器被分为连续的数据对象组块(chunk), 称之为块(block). 类似的, 第k层的存储器被划分成同样大小的块的集合. 在任何时刻, 第k层的缓存包括第k + 1层的一个子集的副本.

高速缓存存储器

通用的高速缓存存储器结构可以用元组(S,E,B,m)表示. 含义是

• 存储器地址 m 位, 形成 M = 2 ^ m 个地址
• S = 2 ^ s 个高速缓存组
• 每个组有 E = 2 ^ e 个缓存行
• 每一行有 B = 2 ^ b 字节数据
• 缓存的容量 C = S * E * B

其中 S 和 E 将存储器地址分为三部分: s 位组索引, 剩下 b 位块偏移, 还有 t = m - s - b 位标记位.

高速缓存的分类

直接映射高速缓存

当 E = 1 时, 称为直接映射高速缓存

查找方式:

• 组选择: 从地址中取出s位索引位解释成一个对应于一个组号的无符号整数
• 行匹配: 检查有效位是否设置 若设置再对比标记是否相同, 相同则得到缓存命中, 否则便缓存不命中
• 字选择: 根据偏移位确定字的初始位置
• 缓存不命中的行替换: 去下一层层次结构中取出被请求的块, 将新的块存储在组索引指示的组中的一个高速缓存行中,如果组中都是有效高速缓存行,就需要换出一个现存的行, 对于直接映射高速缓存, 直接替换现有的行.

组相连高速缓存

当 1 < E < C/B 的高速缓存, 称为E路组相连的高速缓存

查找方式:

• 组选择: 跟直接映射高速缓存一致
• 行匹配和字选择: 组中的任何一行都可以包含映射到这个组的内存块, 所以高速缓存搜索组中的每一行, 寻找设置有效位的行, 检查标记是否匹配, 如果缓存命中, 根据块偏移找到这个字的初始地址.
• 不命中时行替换: 替换策略(LFU, LRU等)

全相连高速缓存

E = C / B, 只有一个包含所有高速缓存行的组.

• 组选择: 因为只有一个组, 所以地址中没有组索引位, 只有标记位和块偏移
• 行匹配和字选择: 与组相连高速缓存一致

关于高速缓存写的问题

处理写命中方法:

• 直写: 立即将修改的缓存块写回内存, 缺点是每次写都会引起总线流量
• 回写: 当被修改的块被换出时再写回内存, 缺点是增加复杂性, 需要维护一个修改位

处理写不命中:

• 写分配: 从下一层存储器结构中获取要写的块更新到高速缓存的某个组中
• 非写分配: 直接修改下一层的对应的块

直写高速缓存通常是非写分配, 写回高速缓存通常是写分配.

高速缓存参数的性能影响

指标:

• 不命中率: 不命中数/访问次数
• 命中率: 1-不命中率
• 命中时间: 高速缓存传送一个字到CPU时间(组选择, 行确认, 字选择)
• 不命中处罚: 不命中所需的额外时间

具体实践见: Cache lab part A

编写高速缓存友好的代码

实践见: Cache lab part B

虚拟内存

上面总结了缓存的概念, 因为虚拟内存技术用到了缓存的思想, 结合缓存技术来实现.

物理和虚拟寻址的概念

计算机的主存可以看成是一个连续字节大小的单元组成的数组, 每字节都有一个唯一的物理地址(Physical Address, PA)

虚拟寻址是CPU生成一个虚拟地址(Virtual Address, VA)来访问主存, 通过内存管理单元(Memory Management Unit, MMU)硬件通过查询主存中的页表将VA翻译成PA, 页表的内容由操作系统管理, 下文会详细描述.

地址空间

虚拟内存的基本思想就是允许一个数据对象有多个独立的地址, 其中每个地址都选自不同的地址空间. 主存中每个字节都有一个来自虚拟地址空间的虚拟地址和物理地址空间的物理地址

虚拟内存

对于程序员来说, 所接触到的地址一般都是虚拟地址, 这里的虚拟地址对应的来自虚拟地址空间,虚拟内存可以看成是将主存和磁盘一起抽象成一个存储器, 由主存作为磁盘的 Cache , 通过将文件划分为固定大小的块来最为主存和磁盘间的传输单元.

跟 Cache 一样, 虚拟内存需要某种方法来判断一个虚拟页是否已经被载入主存中, 于是就有了一个软硬件结合完成的一个由页表项(记录了虚拟页物理页号(有效)或磁盘地址(无效)等信息)组成的数组叫做页表,