第九章 虚拟存储器

---

第一节 物理和虚拟寻址

1.物理地址——【物理寻址】

2.虚拟地址——【虚拟寻址】

第二节 地址空间
1.地址空间
地址空间是一个非负整数地址的有序集合：

{0,1,2,……}

2.线性地址空间

3.虚拟地址空间
CPU从一个有 N=2^n 个地址的地址空间中生成虚拟地址，这个地址空间成为称为虚拟地址空间。

4.地址空间大小表示：
由最大地址所需要的位数来描述。

N=2^n：n位地址空间

第三节 虚拟存储器作为缓存的工具

1.DRAM缓存的组织结构
2.页表
页表是一个数据结构，存放在物理存储器中，将虚拟页映射到物理页。

页表就是一个页表条目PTE的数组，组成为：有效位+n位地址字段
1.如果设置了有效位：
地址字段表示DRAM中相应的物理页的起始位置，这个物理页中缓存了该虚拟页

2.如果没有设置有效位：
(1)空地址：表示该虚拟页未被分配

(2)不是空地址：这个地址指向该虚拟页在磁盘上的起始位置。

3.缺页
DRAM缓存不命中。

4.虚拟存储器中的局部性
局部性原则保证了在任意时刻，程序将往往在一个较小的活动页面集合上工作，这个集合叫做工作集/常驻集。

颠簸：工作集大小超出了物理存储器的大小。

第四节 虚拟存储器作为存储器管理的工具

操作系统为每个进程提供了一个独立的页表，多个虚拟页面可以映射到同一个共享物理页面上。

第五节 虚拟存储器作为存储器保护的工具

PTE的三个许可位：

• SUP：表示进程是否必须运行在内核模式下才能访问该页

• READ：读权限

• WRITE：写权限

第六节 地址翻译

一、结合高速缓存和虚拟存储器
在既使用SRAM高速缓存又使用虚拟存储器的系统中，
大多数系统选择物理寻址
主要思路是地址翻译发生在高速缓存之前
页表目录可以缓存，就像其他的数据字一样
二、利用TLB加速地址翻译
TLB：翻译后备缓冲器，是一个小的、虚拟存储的缓存，其中每一行都保存着一个由单个PTE组成的块

三、多级页表

第七节 案例研究

一、Core i7地址翻译

二、Linux虚拟存储器系统

一、Linux虚拟存储器区域
区域：就是已分配的虚拟存储器的连续片。

一个具体区域的区域结构包括：

• vm_start：指向起始处

• vm_end：指向结束处

• vm_prot：描述这个区域包含的所有页的读写许可权限

• vm_flags：是共享的还是私有的

• vm_next：指向下一个区域

第八节 存储器映射

一、共享对象和私有对象

1. 共享对象

2. 私有对象
   于execve函数：
   

二、使用mmap函数的用户级存储器映射

1. 创建新的虚拟存储器区域

2.  #include <unistd.h>
    #include <sys/mman.h>
   
    void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);
   

参数含义：

• start：这个区域从start开始

• fd：文件描述符

• length：连续的对象片大小

• offset：距文件开始处的偏移量

• prot：访问权限位，具体如下：

  • PROT_EXEC:由可以被CPU执行的指令组成

  • PROT_READ:可读

  • PROT_WRITE:可写

  • PROT_NONE:不能被访问

• flag：由描述被映射对象类型的位组成，具体如下：

  • MAP_ANON:匿名对象，虚拟页面是二进制0

  • MAP_PRIVATE:私有的、写时拷贝的对象

  • MAP_SHARED：共享对象

2.删除虚拟存储器：

include
include <sys/mman.h>
int munmap(void *start, size_t length);

成功返回0，失败返回-1

从start开始删除，由接下来length字节组成的区域。

第九节 动态存储器分配

一、malloc和free函数：

malloc函数：从堆中分配块：

#include <stdlib.h>

void *malloc(size_t size);

free函数：释放已分配的堆块：

#include <stdlib.h>

void free(void *ptr);

二、分配器的要求和目标：

1.要求
处理任意请求序列、立即响应请求、只使用堆、对齐块、不修改已分配的块
2.目标：
最大化吞吐率、最大化存储器利用率

三、碎片

1. 内部碎片

2. 外部碎片

四、隐式空闲链表

堆块的格式：

五、放置策略

1. 首次适配

2. 下一次适配

3. 最佳适配

六、申请额外的堆存储器

sbrk函数：

#include <unistd.h>

vid *sbrk(intptr_t incr);

成功则返回旧的brk指针，出错为-1
通过将内核的brk指针增加incr来扩展和收缩堆。

七、合并空闲块

策略：

立即合并
推迟合并

八、带边界的合并

九、实现简单的分配器

序言块和结尾块

十、显式空闲链表

1.区别
（1）分配时间
隐式：分配时间是块总数的线性时间

显式：分配时间是空闲块数量的线性时间。

（2）链表形式
隐式——隐式空闲链表

显式——双向链表，有前驱和后继，比头部脚部好使。

2.排序策略：
后进先出
按照地址顺序维护

十一、分离的空闲链表

分离存储，是一种流行的减少分配时间的方法。一般思路是将所有可能的块大小分成一些等价类/大小类。

分配器维护着一个空闲链表数组，每个大小类一个空闲链表，按照大小的升序排列。

有两种基本方法：

1. 简单分离存储
   每个大小类的空闲链表包含大小相等的块，每个块的大小就是这个大小类中最大元素的大小。

2. 分离适配

3. 伙伴系统——分离适配的特例

第十节 垃圾收集

1. 基本知识
   垃圾收集器

2. Mark&Sweep垃圾收集器
   两个阶段：标记、清除
   相关函数：

    ptr定义为typedef void *ptr
    ptr isPtr(ptr p)：如果p指向一个已分配块中的某个字，那么就返回一个指向这个块的起始位置的指针b，否则返回NULL
    int blockMarked(ptr b)：如果已经标记了块b，那么就返回true
    int blockAllocated(ptr b)：如果块b是已分配的，那么久返回ture
    void markBlock(ptr b)：标记块b
    int length(ptr b)：返回块b的以字为单位的长度，不包括头部
    void unmarkBlock(ptr b)：将块b的状态由已标记的改为未标记的
    ptr nextBlock(ptr b)：返回堆中块b的后继
   

3. C保守的Mark&Sweep——平衡二叉树
   根本原因是C语言不会用类型标记来标记存储器位置。

第十一节 C程序中常见的与存储器有关的错误

1. 间接引用坏指针
   常见错误——scanf错误

2. 读未初始化的存储器
   常见错误——假设堆存储器被初始化为0

3. 允许栈缓冲区溢出
   常见错误——缓冲区溢出错误

4. 假设指针和它们指向的对象是相同大小的

5. 造成错位错误

6. 引用指针，而不是它所指向的对象

7. 误解指针运算

8. 引用不存在的变量

9. 引用空堆块中的数据

10. 引起存储器泄露

参考：

1. 《深入理解计算机系统》

2. 有道云笔记
   http://note.youdao.com/share/web/file.html?id=0b10aca28173bc7c8306ff7aa608e79e&type=note