学习目标：

虚拟存储器的功能和角色
地址翻译的工作机制
了解动态内存分配的原理
理解垃圾回收机制

虚拟存储器（VM）的三大功能：

高效使用主存：通过将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保留活动区域，并根据需要在磁盘和主存之间来回传送数据。
为每个进程提供了一致的地址空间，简化了存储管理，进而简化了链接、进程间共享数据、进程的存储器分配以及程序加载。
通过在每条页表条目中加入保护位，从而保护了每个进程的地址空间不被其他进程破坏。

使用虚拟寻址时，CPU通过生成一个虚拟地址(Virtual Address,VA)来访问主存，这个虚拟地址在被送到存储器之前先转换成适当的物理地址。

CPU 芯片上有个叫存储器管理单元(Memory Managemnet Unit,MMU)，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容是由操作系统管理的。

虚拟存储器的基本思想:
地址空间清楚地区分了数据对象（字节）和它们的属性（地址）。其允许每个数据对象有多个独立的地址，其中每个地址都选自一个不同的地址空间。主存中每个字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。

虚拟内存的三个角色

作为缓存的工具

虚拟存储器就是一个由存放在磁盘上的 N 个连续的字节大小的单元组成的数组。这个数组的部分内容，会缓存在DRAM中，在DRAM中的内个缓存块(cache block)就称为页(page)，如下图所示：

大致的思路和以前 cache memory 是类似的，就是利用 DRAM 比较快的特性，把最常用的数据缓存起来。如果要访问磁盘的话，大约会比访问 DRAM 慢一万倍，所以我们的目标是尽可能从 DRAM 中拿数据，所以需要：

更大的虚拟页（4KB~2MB）
全相连：任何虚拟页都可以放在任何物理页中
操作系统对DRAM缓存使用了更复杂精密的替换算法
- DRAM总使用写回而不是直写

具体怎么做呢？通过页表(page table)
页表将虚拟页映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时都会读取页表。操作系统负责维护页表的内容，以及在磁盘和DRAM之间来回传送页。

页表其实就是一个页表条目（Page Table Entry,PTE）的数组。虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个PTE。

因为有一个表可以查询，就会遇到两种情况，一种是命中(Page Hit)，另一种是未命中(Page fault)

命中的时候，即访问到页表中蓝色条目的地址时，因为在DRAM中有对应的数据，可以直接访问。
不命中的时候，即访问到page table中灰色条目的时候，因为在DRAM中并没有对应的数据，所以需要执行一系列操作（从磁盘复制到DRAM中），具体为：

触发Page fault，也就是一个异常
Page fault handler 会选择 DRAM 中需要被替换的 page，并把数据从磁盘复制到 DRAM 中
重新执行访问指令，这时候就会是 page hit

复制过程中等待的时间成为 demand paging。

留意上面的页表，会发现有一个条目是null，也就是没有分配。具体的分配过程，就是让该条目指向虚拟内存的某个页，但不复制到 DRAM，只有当出现 page fault 的时候才需要拷贝数据。

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

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

内存分配没有太多的限制，每个虚拟页都可以被映射到任何的物理页上。这样也带来一个好处，如果两个进程间有共享的数据，那么直接指向同一个物理页即可。

虚拟内存带来的另一个好处就是可以简化链接和载入的结构

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

现代计算机系统必须为操作系统提供手段来控制对存储器系统的访问。
提供独立的地址空间使得分离不同进程的私有存储器变得容易。但是，地址翻译机制可以以一种自然的方式扩展到提供更好的访问控制。
页表中每个高位部分是表示权限的位，MMU可以通过检查这些位来进行权限控制(读、写、执行)，运行在用户模式下的进程只能访问那些SUP为0的页面。

进程1运行在用户模式下，它有读 VP0 和读写 VP1 的权限。

地址翻译

下面通过一个例子来说明如何进行地址翻译

具体的过程为：

通过虚拟地址找到页表(page table)中对应的条目
检查有效位(valid bit)，是否需要触发页错误(page fault)
然后根据页表中的物理页编号(physical page number)找到内存中的对应地址
最后把虚拟内存页偏移(virtual page offset)和前面的地址拼起来，就是最终的物理地址了。

这里又分为两种情况：Page Hit 和 Page Fault，我们先来看 Page Hit 的情况：

主要步骤：

第一步：CPU 首先把虚拟地址发送给 MMU
第二步：MMU 生成 PTE 地址，并从高速缓存/主存请求得到它
第三步：MMU 高速缓存/主存向 MMU 返回 PTE
第四步：MMU 构造物理地址，并把它传送给高速缓存/主存
第五步：高速缓存/主存返回所请求的数据字给处理器

Page Fault：

第一步到第三步，和上面相同
第四步：PTE 中的有效位是零，所以 MMU 触发了一次异常，传递 CPU 中的控制到操作系统内核中的缺页异常处理程序。
第五步：缺页处理程序确定出物理存储器中的牺牲页，如果这个页面已经修改了，则把它换出磁盘。
第六步：缺页处理程序页面调入新的页面，并更新存储器中的 PTE
第七步：缺页处理程序返回到原来的进程，再次执行导致缺页程序的指令。CPU 将引起缺页的虚拟地址重新发送给 MMU。因为虚拟页面现在缓存在物理存储器中，所以会命中，在 MMU 执行了page hit的步骤后，主存就会将所有请求字返回给处理器。

翻译后备缓冲器(TLB)

虽然缓存已经很快了，但还是有进步的空间，那就是在MMU中集成一个小的、虚拟寻址的缓存(Translation Lookaside Buffer,TLB)。

这里VPN + VPO就是虚拟地址，同样分为三部分，分别用于匹配标签、确定集合，如果TLB中有对应的记录，那么直接返回对应页表项(PTE)即可，如果没有的话，就要从缓存/内存中获取，并更新TLB的对应集合。

动态内存分配

程序员通过动态内存分配（例如malloc）来让程序在运行时得到虚拟内存。动态存储器分配器维护着一个进程的虚拟存储器区域，称为堆(heap)
分配器有两种风格：

显示分配器(explict allocator)，要求应用显式地释放任何已分配的块。C程序通过调用 malloc 函数来分配一个块，并通过 free 函数来释放一个块。
隐式分配器(implict allocator)，也叫垃圾收集器(garbage collection)，而自动释放未使用的已分配的块的过程叫做垃圾收集。

#include <stdio.h>
#include <stdlib.h>
void foo(int n){
	int i,*p;
	/*Allocate a block of n ints*/
	p = (int *)malloc(n * sizeof(int));
	if (p == NULL)
	{
		perror("malloc");
		exit(0);
	}
	/*Initialize allocted block*/
	for(i=0; i<n; i++)
		p[i] = i;
	/*Return allocated block to the heap*/
	free(p);
}

分配器的要求和目标：

处理任意请求序列
立即响应请求
只使用堆
对齐块
不修改已分配的块

实现细节

如何能够实现一个高效的内存分配算法？首先要考虑下列问题：

给定一个指针，我们如何知道需要释放多少内存？
如何记录未分配的块？
实际需要的空间比未分配的空间要小的时候，剩下的空间怎么办？
如果有对个区域满足条件，如何选择？
释放空间之后如何进行记录？

书中给出四种方法：

隐式空闲列表Implicit List
显式空闲列表Explicit List
分离的空闲列表 Segregated Free List
按照大小对块进行排序 Blocks Sorted by Size

如何确定哪部分空间合适，有三种方法：

First Fit:每次都从头进行搜索，找到第一个合适的块，线性查找
Next Fit:每次从上次搜索结束的位置继续搜索，速度较快，但可能会有更多碎片
Best Fit:每次遍历列表，找到最合适的块，碎片较少，但是速度最慢

垃圾回收

垃圾回收器(garbage collector)是一种动态存储分配器，它自动释放程序不再需要的已分配块。

无论何时需要堆空间，应用都会用通常的方式调用 malloc。
如果 malloc 找不到一个合适的空闲块，那么它就调用垃圾收集器，希望能够回收一些垃圾到空闲链表。
收集器识别出垃圾块，并调用 free 函数将它们返回堆。关键的思想是收集器代替应用程序去调用 free。
当对收集器的调用返回时，malloc 重试，试图发现一个合适的空闲块。如果还是失败，就会向操作系统要求额外的存储器。
最后，malloc 返回一个指向请求块的指针（成功）或者返回一个空指（失败）

内存陷阱

关于内存的使用要注意避免以下问题：

间接引用坏指针
读取未初始化的内存
覆盖内存
引用不存在的变量
多次释放同一个块
释放块失败

具体的见书本P582

第9章虚拟存储器