操作系统中的页式内存管理
- 2020 年 4 月 7 日
- 筆記
编者注：操作系统中两个重要的概念是CPU和内存，CPU管理相对来说比较"直男"一点，只顾着执行指令，最多忙到100%或者超频执行；但对于内存来说，它是资源有限的，如果进程占用内存较大甚至大于物理内存，并且要同时执行多个进程，这就涉及到内存管理。
1. 内存管理
理想情况下用户对内存的期待是大容量、高速度和持久性，但是现实中却是一个由缓存、主存、磁盘组成的内存架构，该架构中，缓存低容量、速度快但是成本高，主存中速度、中容量和中成本，磁盘就是大容量、持久性但是速度慢。
内存管理就是要对"用户"提供一个统一的抽象，屏蔽缓存、主存和磁盘之间的差异，甚至感知不到它们的存在。用户无需担心程序是存储在缓存、主存或者磁盘上，反正运行、输出的结果都是一样的，这种抽象就是通过虚拟内存来实现的。
操作系统中要同时执行多个进程程序，要保证它们之间互不干扰，也就是说一个进程不能访问另一个进程的内存空间。程序中读写特定内存数据时，不能直接映射到物理内存，也就是说程序发出的内存地址和物理内存要是独立的。综上所述，内存管理的目标就是：
- 地址保护：一个程序不能访问另一个程序地址空间。
- 地址独立：程序发出的地址应与物理主存地址无关。
1.1. 虚拟内存
虚拟内存是操作系统发展史上一个重要的里程碑，虚拟内存的使用，避免程序直接和主存（物理内存）打交道，并且对缓存、主存和磁盘做了统一抽象，这样程序就可以突破物理内存的大小限制，当然程序还是要受制于虚拟内存的大小限制的。
应用程序、虚拟内存和物理内存的关系如下：
程序中看到的内存地址是虚拟内存地址，程序读写内存时会被映射到实际的物理内存中，这个映射称为翻译，这个翻译工作是由MMU（内存管理单元）来完成，MMU接收CPU发出的虚拟地址，将其翻译为物理地址后发送给内存，内存按照该物理地址进行相应访问后读出或写入相关数据。
2. 分页内存
分页系统的核心是将虚拟内存空间和物理内存空间皆划分为大小相同的页面，如4KB、8KB或16KB等，并以页面作为内存空间的最小分配单位，一个程序的一个页面可以存放在任意一个物理页面里。
只是简单说说可能体现不出来分页管理的优势，让我们思考下，除了分页管理之外，简单的内存管理该如何做呢？很容易想到的是分配和程序所需内存同样大小的虚拟/物理内存，也就是基址极限管理，限定内存开始结束位置，随着应用的执行，如果程序还需要更多空间，可以先swap到磁盘，再找一个大的连续空间然后再swap回内存，如果找不到就尴尬了，程序就stop the world了。这样看起来也是一个方案，但是存在一个问题是，这样分配内存的粒度太大，容易造成内存碎片，并且多个内存碎片加在一起可以满足程序使用时也不能直接使用。
可能有的小伙伴会想，那就进行内存碎片整理，通过移动进程在内存里面的位置将空闲空间连成一片。但是这种操作需要将进程swap到磁盘上，再重新加载，效率十分低下。在进行碎片整理的过程中，系统的响应延迟将显著增加，这种方案不太可取。
2.1. 分页管理
在分页系统下，一个程序发出的虚拟地址由两部分组成：页面号和页内偏移值。为了解决程序比内存大的问题，我们可以允许一个进程的部分虚拟页面存放在物理页面之外，也就是磁盘上。在需要访问这些外部虚拟页面时，再将其调入物理内存，需要腾出空间时，将暂时不同的内存swap到磁盘。
分页管理对于任一虚拟页面，系统知道该页面是否在物理内存中，如果在的话，其对应的物理页面是哪个；如果不在的话，则产生一个系统中断（缺页中断），并将该虚页从磁盘转到内存，然后将分配给它的物理页面号返回，这个过程也就是前面说到的地址翻译：
注意：地址翻译只是针对页面号的翻译，即虚拟地址页和物理地址页的映射关系翻译，因为二者一一对应，页内偏移量无需翻译。
内存页的翻译是通过查表进行的，系统对于每个进程都为其保存一个页表，该页表中存放的是虚拟页面到物理页面的映射。每当为一个虚拟页面寻找到一个物理页面后，就在页表里面增加一个记录来保留该虚拟页面到物理页面的映射关系，随着虚拟页面进出物理内存，页表的内容页不断发生变化。
进程发出一个虚拟地址给内存管理单元后，内存管理单元首先将地址里面页号部分的字位分离出来，然后判断该虚拟页面是否有效，是否存放在内存，是否受到保护。如果页面无效，即该虚拟页面不存在或没有在内存，也就是说该虚拟页面在物理内存里面没有对应。如果该页面受到保护，即对该页面的访问被禁止，则产生一个系统中断来处理这些特殊情况。对于无效页面访问，需要终止发出该无效访问的进程。对于合法但不在物理内存中的页面，我们通过缺页中断将该虚拟页面放进物理内存。对于受保护的页面，同样终止该进程。判断页是否合法的信息也是存在页面中的，如果页面合法，则通过页表找对对应物理页号。
2.2. 页表
页表的根本功能是提供从虚拟页面到物理页面的映射，因此其地位十分关键，内存管理单元依赖页表来进行一切与页面有关的管理活动。这些活动包括判断某一页面号是否在内存里，页面是否受到保护，页面是否非法空间等。由于页表的特殊地位（使用非常频繁），因此只能由硬件来实现，也即是说它是一个硬件数据结构。
对于32位寻址的虚拟地址，如果页面大小为4KB，则虚拟页面数最多可以达到2的20次方，即1048576个虚拟页面，那么页表的记录条数就为1048576条。这样就占用较多空间，如何减少页表空间呢？这时可以使用多级页，表页表根据存放的内容可分为：顶级页表、一级页表、二级页表、三级页表等。顶级页表里面存放的是一级页表的信息，一级页表里面存放的是二级页表的信息，以此类推，到最后一级页表存放的才是虚拟页面到物理页面的映射，就和MySQL中非聚集索引和聚集索引的关系类似。二级页面结构如下：
2.3. 页表快速翻译
地址翻译因增加了内存访问次数而降低了系统效率。如果只使用单级页表，则每次内存访问变为两次内存访问，速度的下降还尚可以忍受。但如果使用多级页表或反转页表，则每次内存访问将变为多于两次的内存访问，这样效率的下降将非常明显。我们都知道，程序的执行有时空局限性，即在一段时间内，程序所要访问的地址空间有一定的空间局域性。如果一个页面被访问，则该页面的其他地址可能也将被随后访问。这样，我们可以将该页面的翻译结果存放在缓存里，而无须在访问该页面的每个地址时再翻译一次。这样就可以大大提高系统的执行效率。
这种存放翻译结果的缓存称为翻译快表（Translation Look-Aside Buffer,TLB）。TLB里面存放的是从虚拟页面到物理页面的映射，其记录的格式与内容和正常页表的记录格式与内容一样：
TLB是线性表结构，那么它的时间复杂度是多少呢？O(1)，是不是不可思议？解决方案就是使用硬件，TLB的比较不是顺序执行的，而是一次性比较其中所有数据，因此只需要一次查找就能确定一个虚拟页面号是否在TLB里。这种设计需要同时配备多套比较电路，比较电路的套数需与TLB的大小一样。这也就是为什么TLB非常昂贵。
显然，采用多级页表的分页系统的效率将取决于TLB的命中率。如果命中率很高，则系统效率高；如果命中率低，则系统效率低。例如，Linux使用的是三级页表，按照常理来说，这将使得系统的执行效率大大降低，但许多人并没有感觉到Linux特别慢，这就是因为Linux的TLB命中率高，据称其命中率达98%。
