一、为什么需要内存管理 #
内存管理的演化过程：
最开始，直接把一个进程放在物理内存中运行，此时物理内存中一部分是内核，另一部分就是进程，运行完了就出来；后来有了多道程序设计，物理内存不再是只给一个进程使用，而是多个进程同时分配一个物理内存；再后来为了安全考虑（防止越界、越权），引入了虚拟内存，每个进程都有一个自己独立的地址空间。
在多道程序设计中，多个程序同时驻留内存，此时程序中的地址不直接等于物理地址，所以需要地址重定位（或者地址映射、地址翻译）；同时进程之间不能相互访问，需要地址保护，以及共享与隔离。
那么内存管理就是为了解决如上述的问题而存在的。除此之外，还有很多内存管理需要解决的问题，比如程序什么时候进入内存、进程空间如何映射到物理内存、内存不够怎么办、怎么保证效率和保护等等。
二、内存管理基本概念 #
1. 两个“空间” #
逻辑地址空间 vs 物理内存空间：这对矛盾，是驱动整个内存管理技术演进的源动力。
- 逻辑地址空间（程序看到的世界）要求：连续、从0开始、独立、无限大（理想情况下）。
- 物理内存空间（硬件提供的现实）是：有限的、可能碎片化的、所有进程共享的、需要竞争的资源。
内存管理的核心任务，就是用物理内存这个有限的现实，去满足多个进程对逻辑地址空间这个无限的理想。
内存管理的基本功能：
- 给进程分配内存——地址空间
- 往内存加载内容——映射进程地址空间到物理内存
- 存储保护——地址越界、权限
- 管理共享的内存
- 最小化存储访问时间
关于“逻辑地址空间”，和本系列第三章的“进程线程模型”中的“虚拟地址空间”有关系但不完全相同，可以认为前者是一种概念，后则是实现这个概念的一种技术。
下图是一个典型的逻辑地址空间的布局：
2. 两个空间地址的重定位（地址如何映射） #
- 逻辑地址（相对地址，虚拟地址）：用户程序经过编译、汇编后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址，不能用逻辑地址在内存中读取信息。
- 物理地址（绝对地址，实地址）：内存中存储单元的地址，可直接寻址。
地址重定位：将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址的过程。目的是保证CPU执行指令时可正确访问内存单元。
静态地址重定位 #
当程序加载到内存时一次性由装载器实现从逻辑地址到物理地址的转换，一般可以由软件完成。
动态地址重定位 #
在执行过程中进行地址转换，需要硬件支持。CPU将逻辑地址给硬件内存管理单元MMU，得到物理地址。
以下是在动态重定位中，硬件和软件分别需要的要求：
动态重定位的过程由MMU完成，是不需要OS干预的。下面是在操作系统初始化和运行时阶段的有关动态重定位的图示：
3. 地址绑定时机（地址映射的时机） #
那么程序里的“地址”是在哪个阶段，被最终确定成为物理内存中的“真实地址”的呢？在现代操作系统中一般而言都是运行时绑定，这是出于性能的考虑。
如果用编译时绑定，会直接生成绝对的物理地址，程序必须加载到固定的内存位置才能运行，这样显然是没有灵活性的，只适合早期单任务系统或极简单的嵌入式设备。
如果用链接时绑定，链接器将多个.o目标文件合并成可执行文件，并在此时确定各个符号的相对地址（相对于可执行文件起始位置的），程序仍然需要在加载时整体放入内存但不需要固定位置。
如果是加载时绑定，加载器知道应该放在哪个物理位置，然后将程序的所有地址一次性放在最终转换得到的物理地址；允许程序在加载时选择位置但一旦放入后就不能移动。
如果是运行时绑定，每次涉及到地址的指令时都通过硬件MMU配合页表来将逻辑地址转换为物理地址，这样性能是最优的。一是因为有CPU内部的TLB的帮助，二是因为虚拟内存技术允许进程的一部分放在内存其余放在磁盘，可以懒分配。这也是最常见的方式。
4. 地址保护 #
- 越界
基地址寄存器和界限寄存器：保证CPU访问的地址是在这两个范围内的。（在虚存提出后，每个进程都是一样的地址空间，就不会有越界的问题了，最多是越权）
- 越权
三、物理内存空闲管理 #
1. 数据结构 #
- 位图：每个分配单元对应于位图中的一位，0表示空闲，1表示占用（或者相反）
- 空闲区表、已分配区表：表中每一项记录了空闲区（或已分配区）的起始地址、长度、标志
- 空闲块链表：隐式空闲链表、显式空闲链表、分离空闲链表
2. 分配算法 #
考虑的衡量指标：1. 内存资源利用率（内碎片、外碎片）。2. 性能。
- 首次适配 first fit：在空闲区表中找到第一个满足进程要求的空闲区
- 下次适配 next fit：从上次找到的空闲区处接着查找
- 最佳适配 best fit：查找整个空闲区表，找到能够满足进程要求的最小空闲区
- 最差适配 worst fit：总是分配满足进程要求的最大空闲区
- 分离适配算法：核心思想是：将空闲块按照大小分成不同的类别（大小类），每个类别维护一个独立的空闲链表。
3. 回收与合并 #
内存回收算法：当某一块归还后，前后空闲空间合并，修改内存空闲区表。有四种情况：上相邻、下相邻、上下都相邻、上下都不相邻。
4. 分离适配算法的一些例子 #
⭐伙伴系统 #
一种经典的分离适配算法（或者说一种）：伙伴系统。主要思想是将内存按2的幂进行划分，组成若干空闲块链表；查找该链表找到能满足进程需求的最佳匹配块。算法的流程是，首先将整个可用空间看作一块：$ 2^U $ ，假设进程申请的空间大小为 $ s $ ，如果满足$ 2^{U-1} \lg s \le 2^{U} $，则分配整个块；否则，将块划分为两个大小相等的伙伴，大小为 $ 2^{U-1} $ 。一直划分下去直到产生大于或等于 $ s $ 的最小块。
当合并的时候，每个块只能与其伙伴进行合并（大小相同，位置相邻）。
SLAB分配器 #
伙伴系统分配的最小单位是 一页（通常 4KB），但操作系统内核经常需要分配很小的对象，比如进程描述符（task_struct）：约 1-2KB，文件描述符（file 结构体）：几十字节，锁、信号量、缓冲区头等。直接使用伙伴系统会导致内碎片严重且效率低，缓存不友好。伙伴系统管理用户空间的大块内存，对于系统内核的小对象，需要专门的“批发零售”机制，这就引出了SLAB分配：为每种常用大小的对象，预先申请一批内存，内部维护一个“空闲对象池”，分配时直接拿一个，释放时放回池子，避免频繁调用伙伴系统。
但会维护太多的队列，容易出现锁竞争，提出了改进，如SLUB（数据结构简单）、SLOB（简单紧凑的设计）
四、内存管理方案的演进 #
注意加载单位是进程，上述都是在把进程的内容都放进内存为前提的，而目前的虚拟内存则是不需要把进程的内容都放进内存的。
1. 单一连续区 #
一段时间内只有一个进程在内存，用完就出去。
2. 固定分区 #
先把内存空间分割成固定大小，每个分区只能装一个进程，容易产生内碎片。
3. ⭐可变分区 #
根据需要分割分区分配给进程，剩余的成为新的空闲区。这样在回收的时候容易形成外部碎片。
内部碎片(internal fragmentation)：分配给进程的内存块中，未被使用的部分。当分配的内存块大小 大于 进程实际请求的大小的时候会产生，往往是在固定大小分配的场景中会见到。
外部碎片(external fragmentation)：内存中分散的小空闲块，加起来够大但每个都不够用（内存中散布的太小而无法被利用的空闲块）。当进程被加载、换出、释放后，内存被切割成多个小空闲区时可能产生，往往是在可变大小分配的场景。
为了解决外碎片，一种方法是紧缩技术(memory compaction)，通过移动正在运行的进程，将分散的小空闲区合并成一个大空闲区，从而能够容纳更大的进程。
那什么时候做紧凑呢？当分配失败的时候进行按需紧凑，但是分配延迟高；或者定期执行；或者在释放内存时进行但是可能会频繁移动。一般而言现代会使用按需紧凑+定期检查的组合策略。同时，能移动的前提是动态重定位，否则移动后程序会失效。主要的开销是CPU拷贝数据、暂停进程执行的时间、更新紧凑的基址寄存器/页表等等。
那哪些进程适合移动呢？小进程移动成本低，优先移动；阻塞/睡眠进程容易移动；IO密集进程移动成本高（比如read()系统调用，可能DMA固定把读取的内容放在内存的某个位置，不能随便移动）。其中阻塞态是最佳的，因为不占用CPU可以安全移动。
下面的页式管理可以有效缓解外部碎片的问题。
4. 段式管理（分段） #
与分页类似，但是是按照程序自身的逻辑结构来划分内存，每个逻辑单元（如一个代码段、数据段、堆、栈）是一个段。每个进程会有一个段表，存放在内存中，与页表类似进行段的地址的转换。
5. ⭐页式管理（分页） #
逻辑地址空间划分为大小相等的区域：页 page；物理内存空间按页大小划分为大小相等的区域，称为内存块 page frame。
内存分配规则：以页为单位进行分配，并按进程需要的页数来分配；逻辑上相邻的页，物理上不一定相邻。典型的页面尺寸：4K或4M。
为了完成逻辑地址空间的页和物理地址空间的页，引入了页表来对二者的地址进行映射。每个进程一个页表，存放在内存中；页表项记录着逻辑页号与页框号的对应关系。页表的其实地址保存在PCB中。
CPU通过页表来完成地址转换：CPU取到逻辑地址，自动划分为页号和页内地址；用页号查页表（由硬件完成），得到页框号，再与页内地址（页内偏移）拼接为物理地址。
由于页式也是固定分区类型，仍然会有内碎片问题的存在；但是不会有在物理内存上的外碎片问题（因为连续的逻辑页可以映射到不连续的物理页框）。
6. 段页式 #
先分段，再分页。这样逻辑地址就是段号+页号+偏移。
- 段表：记录了每一段的页表始址和页表长度
- 页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多个页表）
- 空闲区管理、分配、回收：同页式管理
五、内存“扩充” #
目标：解决在较小的存储空间中运行较大程序时遇到的矛盾（内存不够了怎么办？）
- 覆盖技术：按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域，要求程序各模块之间有明确的调用结构。程序员声明覆盖结构，操作系统完成自动覆盖。
-
交换技术：内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域（进程在内存与外存之间的动态调度）
- 交换时机？当系统发现物理内存不足或有不够的危险，且需要为即将运行的程序腾出空间时。
- 如何选择被换出的进程？不应该换出处于等待IO的进程
- 换出后再换入的进程不一定回到原处，采用动态重定位，可以换到新的物理地址处，但是通过查页表可以得知虚拟地址位置是不会变的
-
紧缩技术：在本文第四节的第3部分有介绍到，目的是解决外部碎片，从而来达到产生大片空闲区域。
