CSAPP虚拟存储器

发表于 2019-08-24

什么是虚拟存储器

一种对主存的抽象概念，为每个进程提供一个更大的，一致的和私有的地址空间。

物理内存 + 磁盘 = 虚拟内存

一些概念

什么是物理地址，虚拟地址

物理地址单指主存中的地址，系统将主存看作是一个非常大由M个连续字节大小的单元组成的数组，每个字节都有一个唯一的物理地址，第一个字节的地址为0，下面一个是1，以此类推
同理在虚拟存储器中的数组元素的地址就是虚拟地址

什么是物理寻址，虚拟寻址

CPU使用物理地址访问主存的方式就叫做物理寻址
同理使用虚拟地址访问主存的方式叫做虚拟寻址，CPU通过生成一个虚拟地址来访问主存，这个虚拟地址在被送到存储器前先转换为适当的物理地址

什么是地址空间

是一个非负整数地址的有序集合，如果整数是连续的，就是一个线性地址空间

虚拟地址空间：
- 有2的n次方个地址的地址空间，n是电脑位数决定的，比如32位，64位
- 位数是数据总线的宽度，是指一次能传输的数据的位数，通常就是CPU一次能处理的数据的位数，所以字长就是取决于数据总线
- 所以虚拟存储器的大小是不一定的，同时有上限的，我们可以设置的非常大，但是访问不到也就没有用了
物理地址空间：与系统中物理存储器的M个字节相对应

VM实现的原理

装载程序时：只将当前指令执行需要的部分页面放入内存中
执行需要的指令或数据不在内存中时：处理器通知操作系统将相应的页面调入内存
OS用页面调度算法将内存中暂时不用的页面保存到外存中

实现的依据是局部性

VM的作用

作为缓存的工具

DRAM用于磁盘和SRAM间的缓存，而VM可以用于磁盘和DRAM间的缓存。

这个缓存是通过虚拟地址空间来实现的，这个空间不是真实存在的，它是假的，将这个空间划分为大小固定的块，称为虚拟页，再用一张表来记录这些块的使用情况叫做页表，这个表存放在内存中，每次需要使用某个虚拟页时先查找这个表中的条目（页表条目PTE）：
- 命中：当存在于内存中时，就通过表中地址直接查到在内存中的物理地址，需要使用地址翻译，同时可以利用TLB加速这个翻译过程，下文会介绍
- 不命中：不存在于内存中时，触发缺页异常，通过表中地址查找该页面在磁盘中的地址，再换入到内存中
作为存储器管理的工具

管理DRAM，实际上每个进程有独立的页表，也就是单独的虚拟地址空间，再通过各自独立的虚拟地址空间映射到共同的物理地址空间（在DRAM中）和磁盘地址中，简化了链接，加载，共享和存储器分配这些过程。
作为储存器保护的工具

在PTE添加一些许可位来控制对虚拟页面的访问，比如SUP，READ，WRITE位。

地址翻译

翻译的过程

是建立一个虚拟地址空间到物理地址空间的映射关系

需要使用一个叫做存储器管理单元MMU的专用硬件

CPU中有一个专门的页表基址寄存器（PTBR）指向当前页表，当CPU生成一个虚拟地址并传递给MMU开始翻译的时候，MMU利用虚拟地址的VPN来选择相应的PTE，同时将该页表中对应的物理页号（PPN）+ 虚拟地址的VPO就生成了相应的物理地址。

当页面没命中时：

缺页步骤：①CPU生成虚拟地址；②MMU生成PTE地址从内存的页表中请求内容；③ 内存中的页表返回相应的PTE值；④ PTE的有效位是0，转到异常处理程序；⑤ 异常处理程序确定内存中的牺牲页，并将其写会到磁盘上（pagefile.sys）；⑥从pagefile.sys中调入新的文件并更新PTE。⑦ 由于PTE已经被更新好了，从新发送虚拟地址到MMU（后面就和命中的过程一样了）

和cache结合

大多数系统使用物理寻址来访问SRAM高速缓存，理由是cache无需处理保护问题，同时多进程同时在cache有存储块和共享来自相同虚拟页面的块很简单？？？

地址翻译发生在高速缓存查找之前，不是很懂

利用TLB加速地址翻译

产生的原因：本来页表是放在内存中的，我们知道DRAM是比SRAM慢将近10倍的，每次需要先在内存中查到物理地址，再到内存中这个位置找到想要的数据就需要访问内存两次，就让追求极限速度的人们感到不爽。

TLB是什么：

（翻译后备缓冲器）一个小的，虚拟寻址的缓存，每行都保存由单个PTE组成的块
是一个在L1上的片上高速缓存，大多数页表条目位于其中，称为快表
这样翻译时只需访问一次SRAM和一次DRAM，就快了很多
快表只是页表的一个子集

多级页表

为什么需要：如果只用一张页表来进行地址翻译的话，想要能翻译所以的物理地址空间会需要较大的页表驻留在内存中，想要表示4GB的内存地址空间需要4MB的表。假设固定页表大小为4KB，那么二级页表就可以表示4MB的内存空间了，三级页表可以表示4GB的内存空间，而在内存中我们只用常驻一个4KB的表即可。

怎样做：采用层次结构的页表，一级页表中每个PTE映射虚拟地址空间中的一个二级表，二级表在映射三级表，以此类推。从两个方面减少了对存储器的要求：

如果一级页表中某个PTE为空，那么其对应的二级表就根本不会存在
只有一级表需要常驻于内存中，VM系统可以在需要时创建，页面调入/调出二级页表

存储器映射

什么是存储器映射

是虚拟存储器区域与一个磁盘上对象的关联过程

虚拟存储区域映射到两种类型的对象：

Unix文件系统中的普通文件
匿名文件

一个虚拟页面一旦被初始化了，就在内核维护专门的交换文件中换来换去。交换文件也叫做交换空间，交换区域。

存储器映射对共享对象非常有帮助。一个对象可以被映射到虚拟存储器的一个区域，要么作为共享对象，要么作为私有对象。映射到共享对象的区域叫做共享区域，同理有私有区域：

一个进程对共享区域的写操作对于也把该共享对象映射到它们虚拟存储器的其他进程而言也是可见的，同时变化会反映在磁盘的原始对象中
但是对一个映射到私有对象的区域进行改变时，对其他进程是不可见的，并且进程对该区域的任何写操作都不会反映在磁盘的对象中。私有对象使用写时拷贝（COW），当一个进程试图写私有区域的某个页面时，会触发一个保护故障。在物理存储器中创建该页面的拷贝，更新页面条目指向该拷贝，同时再使该拷贝页面可写，最后再在这个新页面进行写操作。

动态存储器分配

是什么

更方便的创建和删除虚拟存储区域
在程序运行的时候分配额外的存储空间
维护着一个进程的虚拟存储区域，称为堆
分配器将堆视为一组不同大小的块的集合

分配器的类型

显示分配器：显示的创建和释放块。C标准库提供了一个称为malloc程序包的显示分配器

隐式分配器：也叫垃圾收集器，显示的创建，但是会自动检测不再使用的块并自动释放

malloc和free函数

malloc遇到问题会返回NULL

如果想要初始化存储器为0，可以使用calloc函数，它是基于malloc的瘦包装函数。

想要改变已分配的大小可以使用realloc函数

碎片

内部碎片：当已分配块比有效载荷大时，比如堆中头部和脚部所占的空间，还有因为对齐造成的浪费

外部碎片：当空闲存储器合计起来满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求。就是空闲块不连续造成的

实现

隐式空闲链表

是什么：

是一种组织堆的结构，块的结构是：头部，有效载荷，填充（可选）；同时通过块头部的最低位来指明该块是已分配还是空闲的
空闲块通过头部的大小字段隐含地链接
有一个特殊标记的结束块

分配器通过遍历堆中所有块便利空闲块的集合。

放置策略：

首次适配
下一次适配：指每次从上一次查询结束的地方继续查询
最佳适配

操作：

分割空闲块
合并空闲块：在每个块的结尾处添加一个脚部，是头部的副本
申请额外的堆存储器

显式空闲链表

来由：在隐式空闲链表中，块分配与堆块的总数是线性关系，所以一般不适用

是什么：

堆组织成一个双向空闲链表，每个空闲块都含一个前驱和后继指针
首次适配时间从块总数线性时间减到了空闲块数量的线性时间
释放块可选择后进先出（新释放的块放在链表的开始处）或者按地址顺序（表中每个块地址都小于它后继的地址）两种方法

分离的空闲链表

来由：单向表的分配时间呈线性，为了减少分配的时间

是什么：

一个分离存储的系统
维护多个空闲链表，每个链表中块的大小大致相同
将所有块按大小分成一些大小不同的类（根据2的幂来划分），每个大小类一个空闲链表，按升序排列
每次查找空闲块时，从前往后依次寻找

分离存储方法有许多种，其中有两种：

简单分离存储：每个空闲链中都是大小相等的块，不分割，不合并。所有分配和释放都很快，但是容易造成内部和外部碎片。
分离适配：每个空闲链表被组织成某种类型的显式或隐式链表，每个链表包含潜在的大小不同的块。像单向链表一样可以分割，合并。但是搜索被限制在堆的某个部分而不是整个堆，所以搜索更快了。
伙伴系统：是分离适配的一个特例。将每次请求块大小向上舍入到2的幂，使用起来更加快速，缺点是会导致显著的内部碎片，适合于特定应用的工作负载（块大小预先知道是2的幂）。