第八章 内存管理策略
1. 一些基本概念
- 进程隔离
每个进程都有一个单独的内存空间，保证不越界是通过两个寄存器：基地址寄存器和界限地址寄存器来保证的。这两个寄存器的值只有 OS 能通过特权指令在内核模式下修改。 - 地址绑定
进程逻辑地址空间到内存物理地址的映射称为地址绑定。这一过程可以发生在：
- 编译时。生成绝对代码，如果起始地址发生变化需要重新编译
- 加载时。生成可重定位代码。静态重定位
- 执行时。动态重定位。大多数的通用计算机系统采用这种方法。
- 逻辑地址和物理地址
CPU 生成的地址称为逻辑地址或虚拟地址，而内存单元看到的地址为物理地址。编译时和加载时生成的逻辑地址和物理地址相同，而执行时生成的逻辑地址与物理地址不同。两者之间的映射通过内存管理单元（Memory Management Unit, MMU）来完成。通俗点讲，就是对某个地址的访问都要加上一个 offset。 - 动态加载
程序片段只有在运行时才加载到内存，从而节约内存使用 - 动态链接
主要是用于系统库或语言库。用户程序通过一个存根来引用外部库，当执行到存根的时候，会用外部程序地址替换存根，完成控制流的跳转。这样做的目的主要是为了共享公共代码。 - 交换
进程可以从内存中换到辅助存储，也可以换回来。用于提高多道程序度。
2. 内存分配
2.1 碎片
碎片是任何动态存储分配都会遇到的一个问题，
外部碎片：当总的空闲内存可以容纳一个进程但并不连续的时候，这些空闲内存就称为外部碎片。
内部碎片：分配的最小单位比进程还大，那么就会造成一部分空间浪费。原因是精确分配带来的开销可能比浪费掉这个空间更大。
对于外部碎片，紧缩（compaction）是常见的策略。但是前提是重定位是动态的，因为程序的位置会变动。另一个解决方案是，允许进程的逻辑地址空间不连续，通过链表串起来，也就是下面提到的分段、分页。这个问题和策略贯穿整个计算机系统，如 Java 垃圾回收。Linux 磁盘空间的使用也是通过 superblock 来做的。*。
2.2 连续内存分配
最简单的办法。可以分为固定大小分区和可变分区两种方案。对于可变分区，有首次适应、最优适应、最差适应等算法。
2.2 非连续内存分配
非连续内存分配本身就是一种动态的重定位。
2.2.1 分段
逻辑地址由 <段号, 偏移> 组成，存储在段表内，段表的每个条目都有段基地址和段界限，一般由硬件来做。编译时，编译器自动构造段，如代码段、全局变量段、栈等。
2.2.2 分页
分段虽然允许非连续物理地址，但是还是存在外部碎片，根本原因是段大小不同又不连续，就在连续的物理内存上产生了空洞。而分页可以避免这个问题。分页同时也降低了不同大小的内存块的管理麻烦。但是分页不能解决内部碎片的问题。
分页的核心思想是：将物理内存分为固定大小的块，称为帧/页帧；而将逻辑内存也分为同样大小的块，称为页/页面。逻辑地址由 <页码, 页偏移> 组成，存储在页表内。页表包含页的基地址，不需要单独存界限地址，因为所有页都是一样的，这点与分段不同。页的大小一般为 2 的幂，主要是为了方便切分逻辑地址为页码和页偏移。
引入页表的坏处就是：每次内存访问，都需要两次内存访问：一次访问页表，一次访问内存。引入专用的硬件转换表缓冲区（Translation Look-aside Buffer, TLB）可以类似 cache 一样部分解决这个问题。
分页带来的另外一个好处就是支持共享和交换。
2.2.2.1 页表结构
- 多级页表。主要是为了减少页表大小。类似于 ext superblock 和 Bigtable 的多级索引。<一级页码，二级页码，页偏移>
- 哈希页表。常用于大于 32 位地址空间，主要是为了减少搜索时间。虚拟页码通过 hash 函数映射到哈希表里，hash 表内的 entry 是 <虚拟页码, 物理页码, 链表指针>。
- 倒置页表。主要是为了减少页表大小。多级页表存在一个问题，页可能并不存在或并没有使用，但是页表里也要有那么大的空间。这会导致页表很大。倒置页表的结构是 <进程 id, 页码, 偏移>。缺点：搜索时间可能较长；实现共享比较困难。
共享内存的通常实现为：将多个逻辑地址映射到一个物理地址。倒置页表因为一个物理页只对应一个虚拟页，所以不能实现共享
2.2.2.2 64 位系统究竟能用多大空间
这个完全取决于底层体系结构。常见的 x86-64 架构，采用四级分页，因为有 16 位未使用，支持 48 位的虚拟地址。如果配合 PAE，能支持 52 位的物理地址。
第九章 虚拟内存管理
1. 什么是虚拟内存
虚拟内存主要是为了将逻辑内存和物理内存分开，逻辑内存是一个无限大、连续的地址空间，程序员可以不考虑底层细节；同时，程序所需内存并不需要同时驻留内存，提高了多道程序度；同时，允许底层的共享，进一步节省内存。
2. 虚拟内存的工作机制
虚拟内存通常基于分页，如果程序需要某页，且该页尚未加载到内存，会触发一个缺页错误，陷入 OS，OS 调页到内存。通常由于局部访问性，一次会调入多页。如果内存不够了或页不需要驻留内存，那么会被换出到外存，接收区域称为交换空间。通常，交换空间的磁盘 I/O 比文件系统更快，因为它是按更大的块来分配的。可以在一开始就把程序先放到交换空间进行预热，或者只在一开始从原始磁盘位置读页，后续都走交换空间。
3. 写时复制
为进一步节省空间和提高进程创建效率，回想一下 fork() 操作，实际上很多 fork() 操作之后会马上接一个 exec()，复制父进程的地址空间可能完全没有必要。写时复制（Copy On Write) 是常见的一种优化策略，在进程创建的过程中，也使用了这个技术。
vfork() 函数会挂起父进程，子进程使用父进程的地址空间，而不是 COW。修改过后的进程地址空间对父进程完全可见。主要用于创建新进程，进一步省去了 COW 的管理开销。
4. 页面置换
页面置换的基本思路：找到一个空闲帧，如果有，就使用它；如果没有，就使用某种页面置换算法来换出一个牺牲帧，再使用它。修改页表和帧表。
4.1 FIFO 页面置换
最简单的页面置换算法。这个算法性能不好，并可能引发 Belady 异常：随着分配帧数量的增加，缺页错误率可能会增加。
4.2 LRU 页面置换
最优置换算法必然是：置换最长时间不会使用的页面。这种算法确保，对于给定数量的帧会产生最低的可能的缺页错误率。但是这个算法需要未来的知识，不太可能实现，只是作为 OPT 的情况与其它置换算法比较。
FIFO 和 OPT 算法的关键区别在于两者在时间上一个向前看，一个向后看：FIFO 使用的是页面调入内存的时间，OPT 算法使用的是将来使用的时间。如果使用最近的过去作为不远将来的近似，置换最长时间未被使用的页，就引出了 LRU 置换算法。
LRU 是个近似算法并可以数学证明它较优的，广泛使用于计算机各种 cache 问题。
难点是如何实现，一般基于堆栈和双向链表。每次访问一个节点时，就把它从栈中移除并重新入栈，这样最近访问的节点更靠近栈顶，而最近最少使用的节点更靠近栈底。引入 hash 可以更快 (Java 的 LinkedHashMap）。
FIFO 为什么可能导致 Belady 异常？为什么 LRU 等不会？
FIFO 不是说必定会导致 Belady 异常，而只是可能；当帧容量从 n 增到到 n + 1，改变的是队列的出队顺序，这个顺序可能会变动的很大，所以只有在特殊的输入顺序下出现异常。整体上，提高帧容量，还是会使得缺页率降低。LRU 是必定不会出现 Belady 异常的。原因在于，如果能在最近访问的 n 帧里找到一个相同帧，那么必定能在最近访问的 n + 1 帧里找到一个相同帧。
4.3 其它置换算法
Least Frequently Used, LFU 和 Most Frequently Used, MFU 都可以用，但是都实现很困难，而且不能很好地近似 OPT。
4.4 全局置换与局部置换
全局置换允许一个进程从所有帧的集合中选择一个置换帧，局部置换只允许从自己的帧集合中选择一个置换帧。全局置换的一个问题是，进程不能控制它自己的缺页错误率，但通常有着更好的系统吞吐量。
4.5 抖动
如果进程频繁地进行换入/换出，就称为抖动。产生的原因：CPU 根据 CPU 利用率来调整多道程序度。假设 CPU 觉得现在利用率不够高引入新的进程，如果一个进程缺页并从其它进程“抢”了几个页，但是其它进程又需要这个页，那么他们又会缺页，从而陷入 OS 阻塞在 I/O 上。CPU 利用率降低，CPU 觉得自己可以继续增加多道程序度，继续调入更多进程，从而加剧缺页程度，恶性循环。
可见，系统抖动的原因是采用全局置换策略且多道程序过高。通过局部置换算法或优先级置换算法可以限制抖动。工作集模型也可以防止抖动，但是很难跟踪进程的工作集大小。最好的办法还是充钱买内存。
4.6 内核内存分配
内核内存分配通常不走前面提到的种种策略，因为内核可能对内部碎片都非常敏感，或者有的硬件需要直接与连续物理内存交互。
4.6.1 伙伴系统
伙伴系统就是连续内存一分为 2，再分为 2，每次使用一半；这个方案的优点是快速合并，可以将相邻伙伴快速组成更大的段以供使用；但是，很可能造成碎片。
4.6.2 slab 分配
不想看了，略
