深入理解计算机系统（第三版）/ CSAPP 杂谈，第9章：虚拟内存

• 所有程序共享内存资源，这容易造成很多问题。虚拟内存用于管理内存，协调各程序之间的内存占用和释放，但对程序来说无感知。
• 物理寻址流程：CPU 执行加载指令时，生成一个物理地址，通过内存总线传递给主存。主存取出物理地址对应的内存，并返回给 CPU，CPU 将其存放在寄存器中
• 虚拟寻址流程：CPU 执行加载指令时，生成一个虚拟地址，通过内存总线传递给主存，主存将其转换成物理地址。主存取出物理地址对应的内存，并返回给 CPU，CPU 将其存放在寄存器中。转换过程叫做地址翻译 address translation。
• address translation 需要硬件和操作系统一起合作完成。CPU 中有专用硬件 MMU（Memory Managerment Unit），会利用存放在主存中的查询表（页表）来动态翻译虚拟地址。
• 虚拟内存的基本思想：同一个数据可以有一个或多个地址，其中每个地址都选自不同的线性地址空间。线性地址空间是一个连续的非负整数集合，可以根据需要自由定义其大小和范围（线性空间）
• 虚拟内存会被分割成固定大小的虚拟页，物理内存对应分割为物理页，大小与虚拟内存一致
• 虚拟页存在三种状态：未分配，缓存（到物理页），未缓存（到物理页）。
• 页表 page table 存放在内存（DRAM）中，记录虚拟页到物理页的映射关系。地址翻译硬件转换地址时都会读取页表，而操作系统负责维护这个页表，以及在磁盘和内存中来回传送页。

—- 20190113 —-

• SRAM 缓存指的是 CPU 和 L1，L2，L3 和主存之间的缓存，DRAM 缓存指的是虚拟内存系统的缓存，他在主存中缓存虚拟页。
• 虚拟内存优点： 1. 简化链接：每个进程都可以使用相同的基本格式（包括 segment 组成，内存地址）； 2. 简化加载：向内存中加载可执行文件和共享对象文件变得简单。加载磁盘文件时是通过虚拟内存地址加载的； 3. 简化共享：每个进程资源是隔离的，但只要将虚拟页面映射到同一个物理页面，就可以了安排多个进程共享这部分代码的一个副本，而不是每个进程都包含单独一个副本； 4. 简化内存分配：进程申请额外的堆空间时（如 malloc），操作系统分配连续数字的虚拟内存页，并映射到不一定连续的物理页面中。
• 虚拟内存的特性可以作为内存保护的工具。进程之间无法随意的访问对方的内存空间。虚拟内存还可以通过设置 flag 来控制内存的读写权限
• 地址翻译过程：（命中） 1. 处理器生成虚拟地址 VA，传给 MMU； 2. MMU 生成 PTE 地址，通过高速缓存或主存请求得到它； 3. 高速缓存或主存返回PTE； 4. MMU 构造物理地址，并传送给高速缓存或主存； 5. 高速缓存或主存返回请求的数据字给处理器。
• 地址翻译过程：（不命中） 1. 处理器生成虚拟地址 VA，传给 MMU； 2. MMU 生成 PTE 地址，通过高速缓存或主存请求得到它； 3. 高速缓存或主存返回PTE； 4. PTE 有效位为 0，传递 CPU 的控制，让操作系统内核执行缺页异常处理程序 5. 确定物理内存的牺牲页，如果该牺牲页已被修改则换出磁盘； 6. 缺页处理程序页面调入新的页面，并更新内存中的 PTE。 7. 返回到原来的进程，再次执行缺页指令，此时会命中，MMU 将返回请求的数据字给处理器。
• 在 SRAM 缓存和虚拟内存共存的系统中，大部分系统使用的是物理寻址来访问 SRAM。这样设计可以让 SRAM 缓存保持简单。
• PTE 也可以有缓存，来避免每次使用虚拟地址 MMU 都要查阅一个 PTE。PTE 缓存就在 MMU 中，叫 TLB
• 内存映射是 Linux 把磁盘上的一个对象，关联起来并初始化一个虚拟内存区域的内容。
• fork 原理是虚拟内存全部页面改为只读，新页面私有写时复制。
• 内存分配实现：1. 隐式空闲链表。把大小和是否使用写在区块头，通过遍历链表（一般用数组实现），找出空闲区块。匹配策略有三种：首次适配，从头找到第一个适合的空闲块；下次适配，从上一次位置开始找；最佳适配，找到符合要求的最小空闲块。匹配后分割也有策略。合并（碎片整理）也有策略，可以是立即合并（释放时合并）和推迟合并（无空间时合并，通常会使用这个）。
• 2. 显式空闲链表。把空闲块信息写在空闲块主体内（因为它是空闲的，所以可以用来存数据），信息数据结构是一个双向链表，记录上一个和下一个空闲块。管理方法可以是 LIFO，刚释放的块放入链表头部，这样释放块时间复杂度是 O(1)，如果用了边界标记（末尾标记），合并的时间复杂度也是 O(1)；也可以是地址顺序，这样首次匹配复杂度是 O(n)，但内存利用率接近最佳匹配。显示链表有最小区块限制，一定程度上提高了内部碎片的程度。
• 3. 分离空闲列链表。维护多个空闲链表，同一个链表的空闲块大小大致相等。
• 4. 垃圾收集器根据内存的可达图，来判断孤立的内存块，进而回收