内存管理总览
先笼统地总结下内存管理到底是干啥的，下面这段话摘自《现代操作系统 - 第 3 版》：
内存管理的任务就是有效地管理内存，即记录哪些内存是正确使用的，哪些内存是空闲的，在进程需要时为其分配内存，在进程使用完后释放内存。
众所周知，当前计算机都是基于冯·偌依曼存储程序式的计算机，程序和数据在运行和使用时都需要存放在内存中。
设计操作系统的重要目标之一就是提高计算机资源的利用率，而随着多核 CPU 的盛行，多道程序设计技术大行其道。因此，必须合理地管理内存空间，使尽量多的进程/作业能够同时存放于内存中以提高 CPU 的利用率。
通俗来说，内存管理所研究的内容无外乎以下这三个方面：
- 取 Fetch
- 放 Placement
- 替换 Replacement
所谓 “取” 研究的就是，应该将哪个进程（或进程的某些部分）从外存（磁盘）调入内存。
“放” 研究的则是，将从外存（磁盘）中 “取” 来的进程（或进程的某部分）按照何种方式放在内存的什么地方。
很显然，“放” 是内存管理的基础，目前 “放” 的技术可归结成两类：
1）一类是连续分配，即运行的程序和数据必须放在内存的一片连续空间中。
连续分配管理方式包括单一连续分配、固定分区分配和动态分区分配。
2）另一类是不连续分配，即运行的程序和数据可以放在内存的多个不相邻的块中。
不连续分配管理方式包括基本分页管理、基本分段管理和基本段页式管理。
看到这里，各位不妨想一想，如果只有 “取” 操作和 “放” 操作，那么会导致什么问题？
随着用户程序功能的增加，进程所需要的内存空间越来越大，进程空间很容易就突破了物理内存的实际大小，导致进程无法运行。
因此，为了解决内存不足的情况，缓和大程序与小内存之间的矛盾，扩充内存容量势在必行。
可以从物理和逻辑两方面来考虑扩充内存容量，物理扩容没啥技术含量，需要我们研究的自然是如何从逻辑上扩充内存容量。
所谓逻辑扩充，就是说实际上物理内存的容量没有发生改变，但是它能装的东西却变多了。
对内存的逻辑扩充技术主要有三种：覆盖技术、交换技术、以及虚拟内存。事实上，这些逻辑扩充技术的核心理念都是一致的，我觉得用一个词来总结就是 “替换”：
所谓 “替换” 和 “取” 操作正好相反，它研究的是将哪个进程（或进程的某部分）暂时从内存移到外存（磁盘），以腾出内存空间供其他进程（或进程的某部分）占用。
前两种逻辑扩充技术已经成为历史，虚拟内存技术是目前的主流。所以也有很多人把内存管理这块的内容直接区分为物理内存管理和虚拟内存管理，一目了然。
对于虚拟内存的管理是建立在不连续分配管理方式之上的，包括请求分页管理、请求分段管理和请求段页式管理。这几个概念和上文所说的基本分页管理、基本分段管理和基本段页式管理非常容易混淆。
其实很容易区分，记住这句话就 OK，摘自百度百科：
如果不具备页面置换的功能，则称为基本分页管理（或称为纯分页管理），它不具有支持实现虚拟内存的功能，它要求把每个作业（进程）全部装入内存后方能运行。
内存管理整部分总览如上，而本文，内存管理第一部曲，讲的仅是物理内存管理这块。
连续分配管理方式
其实在早期的操作系统中，采用的都是连续内存空间分配的策略。那时还没有引入进程概念，内存分配还是以作业（相当于进程）为单位，而所谓连续分配呢就是将作业分配到一段连续的内存空间。
连续分配管理并非本文的重点，面试中更是冷门，但事实上，这些方法对任何形式的内存空间分配都具有参考意义。因此，还是有必要做个简单的了解。
连续分配管理方式包括单一连续分配、固定分区分配和动态分区分配。
单一连续分配
在没有操作系统的时期，勿容置疑，整个内存空间由单个用户使用。而随着操作系统的出现，内存管理也随之出现了，用户再无法独占内存资源。
当时的内存管理十分简单，仅将内存空间分成两块：系统区（用于存放操作系统相关数据）和用户区（用于存放用户进程相关数据）。
操作系统可以在低地址部分，也可以在高地址部分，假设操作系统在低地址部分，如图所示：
单一连续分配的管理方式确实有点过于简单了，内存中只能有一道用户程序，用户程序独占整个用户区空间。
缺点自然是显而易见：只能用于单用户、单任务的操作系统中；有内部碎片（分配给某进程的内存区域 中，如果有些部分没有用上，就是“内部碎片”）；内存利用率极低。
固定分区分配
20 世纪 60 年代出现了支持多道程序的系统，为了能在内存中装入多道程序，且这些程序之间又不会相互干扰， 于是考虑将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。
至于这些分区大小是否需要相等，各有各的适用场景：
- 分区大小相等：缺乏灵活性。但是适合用于一台计算机控制多个相同对象的场合（比如钢铁厂有 n 个相同的炼钢炉，就可以把内存空间分为 n 个大小相等的区域存放 n 个炼钢控制程序）
- 分区大小不等：增加了灵活性，可以满足不同大小的进程需求
遗憾的是，虽然固定分区分配的方式支持了多道程序，但是仍然会产生内部碎片，内存利用率依然比较低。为此，人们又引入了动态分区分配，这种方法对用户区域实施动态分割，从而改善了内存空间的利用效果。
动态分区分配
动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时， 根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。
动态分区分配比较复杂，需要用特殊的数据结构记录内存的使用情况，具体的细节这里就不再详细介绍了。
非连续分配管理方式
可以看出来，连续的内存分配具有易理解、访问效率高等优点。但是，由于其要求把作业（进程）放在内存的一片连续区域中，很容易出现大段的连续内存空间因为不足够容纳作业或进程而不可用。因此，为了充分利用内存空间资源而引入了非连续分配策略。
所谓非连续分配就是说作业（进程）可以放在内存的多个不相邻的块中。
非连续分配管理方式包括页式管理、段式管理和段页式管理。
在阅读本段之前，需要先了解虚拟地址（逻辑地址）与物理地址的概念，可以参考这篇文章：你看到的所有地址都不是真的
基本分页管理
所谓页式管理，我们需要先解释一下什么是 “页”？
首先，将内存空间分为一个个大小相等的分区，每个分区就称为一个 “页框（page frame）”。每个页框有一个编号，即“页框号”（也成为物理页框号、内存块号），页框号从 0 开 始 。
将进程的虚拟地址空间也分为与页框大小相等的一个个分区， 每个分区就称为一个 “页（page）” 或 “页面” 。每个页面也有一个编号， 即“页号”（也称为虚拟页号），页号也是从 0 开始。
操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻（离散）的各个页框中。
举个例子，如下图，每个页面和页框的大小都是 4KB，我们拥有 64KB 的虚拟地址空间和 32KB 的物理内存，因此可以得到 16 个页面和 8 个页框：
图片来源《现代操作系统 - 第 3 版》
前文说过，指令真正执行的时候会将虚拟地址最终转换为物理地址。
那么，页式管理中是如何将虚拟地址（页面）和物理地址（页框）进行映射的呢？换句话说，如何根据虚拟地址计算得到物理地址？
为此，操作系统为每个进程建立了一张页表，这是一个十分重要的数据结构！页表通常存在进程控制块（PCB）中。
一个进程对应一张页表，进程的每个页面对应一个页表项，每个页表项由页号和块号（页框号）组成，记录着进程页面和实际存放的内存块之间的映射关系。
从数学角度来说，页表是一个函数，它的参数是虚拟页号，结果是物理页框号。
页式管理中的两个重要问题
在任何分页式系统中，都不可避免地要考虑下面这两个问题：
- 问题 1：如何保证虚拟地址到物理地址的转换足够快 — 使用快表解决
- 问题 2：如何解决虚拟地址空间大，页表也会很大的问题（页表项多了，页表自然也就大了）— 使用多级页表解决
先来看第一个问题，由于每次访问内存，都需要进行虚拟地址到物理地址的转换，因此，每条指令进行一两次或更多页表访问是必要的，而页表又是存在于内存中的。
那么，既然访问页表（内存）次数太多导致其成为了一个性能瓶颈，那我们想个方法使得这个地址映射不用访问内存，访问一个比内存快得多的东西不就行了？
计算机的设计者给出的解决方案大致如此，为计算机设置了一个小型的硬件设备，将虚拟地址直接映射成物理地址，而不必再访问页表。这个设备就是转换检测缓冲区（Translation Lookaside Buffer，TLB），也被称为快表。
为啥说他快呢？因为 TLB 通常内置在 CPU 的 MMU（内存管理单元） 中，这访问速度跟内存不是一个档次的。内存中的页表一般被称为慢表。
那么，拥有了 TLB 就可以一劳永逸直接放弃页表了吗？
当然不。
TLB 仅仅包含少量的表项，每个表项记录了一个页面的相关信息，其表结构大致如下：
图片来源《现代操作系统 - 第 3 版》
事实上，TLB 的出现是基于这样一种现象的：大多数程序总是对少量的页面进行多次的访问。因此，只有很少的页表项会被反复读取，而其他的页表项很少被访问。
TLB 中存放的就是那些会被反复读取的页表项。换句话说，TLB 中存放的只是页表中的一部分副本。
若 TLB 命中，就不需要再访问内存了；若 TLB 中没有目标页表项，则还需要去查询内存中的页表（慢表），从页表中得到物理页框地址，同时将页表中的该表项添加到 TLB 中。
那么问题又随之而来了，如果 TLB 填满了怎么办？
当 TLB 填满后又要登记新页时，就会按照一定的淘汰策略淘汰掉快表中的一个页。
再来看第二个问题，现代大多数计算机系统，一般都支持非常大的虚拟地址空间，从而使页表变得十分庞大且需要占用相对可观的内存空间（页表项多了，页表自然也就大了）。我们假设系统中只有一个页表，那即使我们使用的只是虚拟地址空间中的一小部分，也总是需要一整个页表全部驻留在内存中。
用来压缩页表的常用方法就是使用层次结构的页表。
以最常见的二级页表举例，我们来看多级页表的处理思路：
把页表再分页并离散存储，然后再建立一张页表记录页表各个部分的存放位置，称为 “页目录表”（或称外层页表、顶层页表）。
图片来源《操作系统 - 第 3 版》
若分为两级页表后，页表依然很长，则可以对外层页表再分页形成三级以上的多级页表。
多级页表技术不但突破了页表必须连续存放的限制，同时当有大片虚拟地址空间未使用时，可以不分配对应页表空间，因此可节省内存。另外，多级页表增加了访存次数，因此外层页表的页表项应该尽可能保持在 TLB 中，以减少访存开销。
基本分段管理
页式管理虽具有内存空间利用率高、管理方法简单等特点，但是将内存空间按页进行划分对用户来说不是很自然。用户看待程序是以自然段为单位的，比如主程序段、子程序段、数据段等。若用户要求对数据进行保护，那么受到保护的基本单位也是自然段。例如，某段只能读，另一段可执行等。
而分页完全可能把不属于同一段的两块分到同一页中。如下图，第 4 页中既包含程序段（可执行），又包含数据段（可读、可写）：
换句话说，虽然页式管理提高了内存利用率，但是页式管理划分出来的页并无任何实际意义。
为此，段式管理应运而生。
段式系统是按照用户作业（进程）中的自然段来划分逻辑空间的。比如说，用户作业（进程）由主程序、两个子程序、栈和一段数据组成，于是可将这个用户作业（进程）划分成 5 段，显然，页面是定长的而段不是：
从图中可以看出来，段与段之间可以不连续存储，但是段的内部仍然是连续的。
另外，和基本分页管理一样，基本分段管理也需要一个数据结构来记录虚拟地址和物理地址之间的映射，这个数据结构就是段表。
基本段页管理
如果一个段比较大，把它整个保存在内存中可能很不方便甚至不可能的，因此对它产生了分页的想法。
对段进行分页的支持，这就是段页式管理的基本思想。
简单来说，就是对虚拟地址空间先进行段的划分，然后在每一段内再进行页的划分。例如，若用户进程由主程序、子程序和数据段组成，则通过段、页划分后如图所示：
References
- 《操作系统 - 第 3 版 - 罗宇》
- 《现代操作系统 - 第 3 版》
- 《深入理解计算机系统 - 第 3 版》
