《现代操作系统》——内存管理

前言

内存管理是操作系统中经典的话题。小型嵌入式系统一次只需要执行一个任务，对内存管理没有要求。现代的操作系统通常要同时执行多个进程，多个进程所占用的内存之和通常超出物理内存的容量大小。即便内存容量也在不断的增长，但始终跟不上软件体积膨胀的速度。甚至有些庞大的程序所需要的内存就足以塞满整个物理内存空间。所以，现代操作系统的设计者就要想办法来调和系统的多任务同时运行、软件体积膨胀和有限的物理内存容量之间的冲突，想尽办法做到鱼和熊掌兼得。这就是本文所介绍的操作系统的内存管理。本文所介绍的主要是：

• 操作系统为何实现物理内存的抽象？
• 操作系统如何给进程分配内存空间？
• 操作系统为何要引入虚拟内存这个概念？
• 操作系统的虚拟内存为什么以及如何进行分页？
• 操作系统的虚拟内存中常见的页面置换技术有哪些？
• 操作系统如何在内存紧张的时候通过交换（置换）合理的协调多个进程所占用的虚拟内存？

回答这些问题，期间会涉及到以下这些概念，读完本文会对这些概念有一定了解：

• 地址空间
• 动态重定位
• 基址寄存器
• 界限寄存器
• 交换技术
• 虚拟内存
• 内存紧缩
• 分页与页
• 页框
• 虚拟地址
• 虚拟地址空间
• MMU（内存管理单元）
• TLB（转换检测缓冲区）
• 缺页中断/缺页错误
• 页表
• 页面置换算法
• 内存分段

地址空间

背景

把物理地址暴露给进程会带来2个严重问题：

1. 用户程序可以寻址内存中的每个字节，操作系统容易被有意或无意的影响正常运行。
2. 现代操作系统通常要同时运行多个程序，使用物理地址同时运行多个程序是困难的。

总之，在系统中没有对物理内存的抽象，很难实现上述场景。解决办法是使用地址空间。

地址空间是一个进程可用于寻址内存的一套地址集合。为程序创建了一种抽象的内存。每个进程都有自己的地址空间。地址空间是对物理内存的抽象，就像进程抽象了CPU。 有了地址空间的概念，每个程序都有一个独立的地址空间，使得A程序的地址28和B程序的地址28所对应的物理地址不同。所以，操作系统需要保证2个进程的地址空间上相同的地址对应不同的物理地址，曾经实现这一能力的办法是动态重定位。

动态重定位

• 动态重定位是一种很古老的技术，现代计算机中已经不再使用，这里仅作为介绍。
• 在虚拟内存出现以前，基址寄存器和界限寄存器为每个进程提供了一个独立的地址空间。
• 动态重定位是把每个进程的地址空间映射到物理内存的不同部分。
• 经典的动态重定位方法是采用基址寄存器和界限寄存器。
  • 比如世界上最早的超级计算机——CDC 6600 到 Intel 8088(原IBM PC的心脏)就采用了动态重定位。他们采用的经典办法是给CPU配置2个特殊的硬件寄存器——基址寄存器和界限寄存器。使用这种方法，程序装载到内存中连续的空闲位置。程序运行时，基址寄存器中装载程序的起始物理地址，界限寄存器中装载程序的长度。
  • 每次一个进程访问内存（取一条指令、读/写一个数据字），CPU硬件会先把基址值（基址寄存器上的值）加到进程发出的地址值（进程地址空间上的地址偏移量）上，然后再把结果值发送到内存总线
• 使用基址寄存器和界限寄存器的缺点：每次访问内存都需要加法和比较运算。
  • 加法运算是为了把基址值和地址值进行相加
  • 比较运算是为了比较计算后的地址是否越界、是否合法
  • 加法运算由于进位传递时间的问题，在不使用特殊电路时会很慢

交换技术

现代计算中，计算机通常会同时运行多个程序，即多个进程同时存在于内存中。所有进程所需要的RAM（random access memory）总和通常会超出存储器（内存）所能支持的范围（比如8G的内存）。甚至有时候一个大型的程序自己所需要的RAM就会超过内存的最大容量。有两种应对内存超载的方法（本节只介绍交换技术）：

1. 交换技术
2. 虚拟内存

• 交换技术是把一个进程完整的调入内存，使该进程运行一段时间后再把他存回磁盘。（如下图）
  • 在内存已满时，如果需要运行其他进程，交换技术会把空闲进程存储在磁盘，把需要运行的进程从磁盘读入内存。
  • 因为被交换出去的空闲进程保存在磁盘，所以不会占用内存。这种技术本质是在内存和磁盘之间交换进程。
• 交换技术会使再次载入内存的进程的位置(物理地址)发生变化。所以需要通过软件或硬件的方式对其地址进行重定位。（如下图）
  • 基址寄存器和界限寄存器就适用这种场景
• 内存紧缩：交换在内存中产生了多个空闲区，通过把所有进程向下移动，进而将小的空闲区合并为一大块
  • 通常不这样操作，因为非常耗时。比如，1ns复制1个字节，16G内存需要消耗CPU 16s时间

因为很多程序设计语言都允许从堆中动态的分配内存，所以，进程的数据段可以增长。那么问题来了？进程被创建或通过交换技术被换入时，应该给它分配多大的内存呢？

解决办法是可以为进程额外分配一些内存。但当进程换出到磁盘时，只需交换进程实际上使用的内存中的内容。无需交换额外的未使用的内存，如下图3-5a。

如下图3-5b，代码段（程序）的长度是固定的。进程有2个可增长的段：数据段、堆栈段。数据段可以动态分配和释放堆变量。堆栈段可以存放普通的局部变量和返回值。堆栈段和数据段相向增长，如果在两者之间的内存用完了，进程必须移动到足够大的空闲区。

空闲内存管理

上面介绍了应该给进程分配多大的内存。在动态分配内存时，操作系统必须对其进行管理，操作系统需要知道哪些内存在使用，哪些内存未使用（可以再次被分配）。一般而言，有2种方法跟踪内存使用情况：

1. 位图——使用位图进行存储管理
2. 链表——使用链表进行存储管理

如下图3-6a、3-6b和3-6c分别描述了位图和链表进行存储管理的原理。

使用位图的存储管理

• 使用位图进行管理内存，0表示空闲，1表示占用
• 如上图3-6a所示，5个进程和3个空闲区。阴影区标识空闲
• 分配单元的大小是一个重要的设计因素。分配越小，位图越大。反之同理
• 内存的大小和分配单元的大小决定了位图的大小
• 进程调入内存之前，需要先在位图上查找足够长的空闲区——连续的0串。查找操作是非常耗时的。这是位图的缺点

使用链表的存储管理

• 如上图3-6c所示，内存被分为很多段，这些段共同组成段链表
• 这些内存段有些被进程占用，用P表示进程；有些是空闲区，用H表示空闲区
• P段和H段后面的2个数字分别表示起始位置（程序或空闲区的起始位置）和长度（程序或空闲区的长度）
• 按照地址顺序在段链表中存放进程和空闲区时，有几种算法可以为创建的进程分配内存：
  • 首次适配算法（first fit）
  • 下次适配算法（next fit）
  • 最佳适配算法（best fit）
  • 最差适配算法（worst fit）
  • 快速适配算法（quick fit）

内存管理之虚拟内存

背景

虚拟内存出现的出现的背景主要包括以下3点：

• 软件大小的膨胀
  • 需要运行的程序往往大到内存无法容纳
  • 存储器容量大小的增长无法跟上软件大小的增长
• 对系统支持多个程序同时运行的诉求
  • 多个程序同时运行对内存容量的大小提出了挑战
• 基址寄存器和界限寄存器只能创建地址空间的抽象，无法解决这一问题

虚拟内存的基本思想

每个程序拥有自己的地址空间（上面已经介绍过了地址空间的概念）。地址空间被分割成多个块，每一块称作一页（page）或一个页面。进行划分这些页的技术叫做分页（paging）。

• 每一页地址范围都是连续的
• 这些页都会被映射到物理内存，但并非所有页必须在内存中才能运行程序（下面介绍）
• 当程序引用到在物理内存中的地址空间时，由硬件执行映射
• 当程序引用到不再物理内存中的地址空间时，由操作系统负责将确实的部分装入物理内存并重新执行失败的指令

从某个角度讲，虚拟内存是对基址寄存器和界限寄存器的一种综合。虚拟内存使得整个地址空间可以用相对较小的单元（页）映射到物理内存，而不是为正文段和数据段分别进行重定位（基址寄存器和界限寄存器的动态重定位）。

虚拟内存很适合在多道程序设计系统中使用。 许多程序的片段同时保存在内存中，当一个程序等待IO时，可以把CPU交给另一个进程运行。

分页

• 由程序产生的地址称为虚拟地址
• 多个连续的虚拟地址构成了虚拟地址空间
• 在没有虚拟内存的计算机上，系统直接将虚拟地址送到内存总线上，读写操作使用具有同样地址的物理内存字
• 在有虚拟内存的计算机上，虚拟地址被送到MMU（Memory Management Unit，内存管理单元），MMU是一个单独的芯片，MMU的作用是把虚拟地址映射为物理内存地址
• 虚拟地址空间按照固定大小划分成固定大小的块，这种技术被称为分页（paging），这些相同大小的块被称为页 或 页面（page）
• 页面再物理内存中对应的单元称为页框（page frame），页框的作用是承载这些页面，所以页面和页框的大小是一样的
• 将虚拟地址送到MMU会得到映射的物理内存地址，如果页面没有被映射则会使CPU陷入到操作系统，这个陷阱称为缺页中断（page fault缺页错误）。当个缺页错误发生后，操作系统找到一个很少使用的页框并把他的内容写入磁盘（如果内容被修改过），随后把需要访问的页面读到刚才回收的页框，并修改映射关系，最后重新启动引入陷阱的指令，就像缺页错误从未发生过一样。

MMU内部原理

我们已经知道MMU通常是作为一个单独的芯片，其作用是把虚拟地址映射为物理内存地址。这里简单介绍下MMU把虚拟地址映射为物理地址的内部原理。假设在16个4KB页面下，MMU内部操作可见下图：

• 假设要映射的虚拟地址是8196，其对应的二进制是十六位的 0010 0000 0000 0100
• 十六位的二进制虚拟地址被分为4位的页号和12位的偏移量，高4位为页号，低12位为偏移量
• 4位的页号可以最多表示16（2^424）个页面；12位的偏移量可以为一页（4KB）内的全部4096个字节编址
• 用4位的页号作为页表的索引（index），然后查找页表中的表项，可得出对应的虚拟页面的页框号110（如下图）
• 如果表项的在/不在位为0，说明对应页面不再内存中，将会引起一个操作系统陷阱，即缺页中断
• 如果表项的在/不在位为1，则把在页表中查到的页框号110复制到输出寄存器的高3位，第四位用0补齐，再加上输入地址中的低12位偏移量，如此就构成了16位的物理内存地址，输出寄存器的内容作为物理地址送到内存总线

页表

页表的目的是把虚拟页面映射为页框。从数学角度，页表是一个函数，参数是虚拟页号（高位部分，假设是高4位），结果是物理页框号。通过这个函数可以把虚拟地址中的虚拟页面域（高位部分，假设是高4位）替换为页框域，从而形成物理地址。这也是MMU的作用。

通过上述MMU内部原理，页表的一种最简单的实现，虚拟地址到物理地址的映射可以概括为：虚拟地址被分成虚拟页号（高位部分）和偏移量（低位部分）两部分。例如，对于16位地址和4KB的页面大小，高4位可以指定最多16个虚拟页面中的一页，而低12位确定了所选页面中的字节偏移量（0~4095）。但使用3或5或其他位数才分虚拟地址也开始可行的，不同的划分方案对应不同大小的页面。

页表项

构成页表的每一项被称为页表项。页表项主要由以下几个域组成：

• 页框号。这当然是最终要的部分，因为查表的目的就是为了确定页框号。
• 在/不在位。这个域只占1个bit为，因为只能取0、1两个值。0代表该表项对应的虚拟页面不再内存中，访问该页面会引起一个缺页中断。1代表该表项是有效的，可以直接将虚拟地址映射为物理地址。
• 保护位。通常可以使用3个bit位来表示一个页允许什么类型的访问。这个域的3个位分别代表是否允许读、写、执行该页面。通常程序的代码段是可读、可执行不可修改的。而其他数据段是可读、可写不可执行的。
• 修改位。为了记录页面是否被修改，引入了修改位（Modify M位）。这个位为1代表页面被修改过，为0代表没有被修改过。如果一个页面被修改过，那么它就是脏（dirty）的，所以这个修改位有时又被称为“脏位”。被修改过的页框在发生页面置换的时候，需要先把修改的页面写回磁盘。而未修改过的页框发生页面置换时可以直接覆盖，因为磁盘中有一个对应的副本。通常程序的代码段的这个位始终是0，即不允许被修改。所以，程序的代码段发生置换时可以直接覆盖而不需协会磁盘。
• 访问位。为了记录页面是否被访问过，引入了访问位（Referenced R位）。它的值被用来帮助操作系统在发生缺页中断时选择要淘汰的页面。如果访问位为1，代表页面被访问过，可能不适合立即淘汰。如果访问位为0，代表页面没有被访问过，则可以把该页面置换出去。不论是读页操作还是写操作，系统都会在该页面被访问时设置访问位为1。

TLB

我们已经了解了虚拟内存和分页。任何分页系统的实现都要老驴2个问题：

• 虚拟地址到物理地址的映射必须非常快
• 虚拟地址空间很大，那么页表也会很大

综上两条，对大而快速的页映射的需求成为构建计算机的重要约束。多年以来，计算机的设计者已经意识到这个问题并找到了一个解决方案。这种方案基于这样一种观察：大多数程序总是对少量的页面进行多次的访问，而不是相反。因此，只有少量的页面会被反复读取，其他的页表项很少被访问。

基于上面的的观察结论，可以为计算机设置一个小型的硬件设备，不需访问页表就可将虚拟地址直接映射为物理地址。这种设备称为TLB（Translation Lookside Buffer，转换检测缓冲区）又称为相联存储器或快表。TLB通常在MMU中，包含少量的表项。下图中的表项为8个，实际中很少超过256个。每个表项记录了一个页面的相关信息，包括：

• 页面虚拟页号
• 页面的修改位
• 页面的保护位
• 页面对应的物理页框

TLB的工作流程是：将一个虚拟地址放入MMU中进行转换时，硬件首先通过将该虚拟页号与TLB中所有表项同时进行（并行）匹配，判断虚拟页面是否存在TLB中。如果发现一个有效的匹配并且要进行的访问操作并不违反保护位，则将页框号直接从TLB中取出而不必再访问页表。如果虚拟页号不再TLB中，就会进行正常的页表查询，然后从TLB中淘汰一个表项，并用页表中找到的表项代替TLB中淘汰的表项。这样，如果这个页面很快被再次访问，第二次访问TLB时就会命中，而不必再访问内存中的页表。当一个表项被清除出TLB时，将被清除表项的修改位（M位）复制到内存中对应的页表项中。

以上介绍的是硬件的方式实现TLB，即对TLB的管理和TLB的失效都是由MMU硬件来实现。但现代的机器中几乎所有的页面管理都是在软件中实现的。TLB表项被操作系统显示的装载。当发生TLB访问失效时，不再由MMU到内存页表中查找并取出需要的页表项，而是生成一个TLB失效并抛给操作系统。系统会先从内存页表中找到该页面，然后从TLB中删除一项，并把找到的页面的表项装载到TLB中。以上这一切都要在有限的几条指令中完成，因为TLB失效比缺页中断发生的更频繁，毕竟TLB的容量并没有那么大。

当使用软件TLB管理时，一个进本的要求是要理解两种不同的TLB失效（软失效、硬失效）的区别：

• 软失效。当一个页面访问不在TLB中而在内存中，将产生一个软失效（soft miss）。此时要做的就是更新一下TLB，不需要产生磁盘I/O。典型的处理需要10~20个指令花费几纳秒时间即可完成操作。
• 硬失效。当一个页面访问不在TLB中也不在内存中，将产生一个硬失效（hard miss）。此时需要一次磁盘I/O来装入该页面，这个过程大概需要几毫秒。所以硬失效的处理时间往往是软失效的百万倍。不难看出，处理一次硬失效的代价是昂贵的。

大内存页表

• 多级页表
• 倒排页表

内存管理之页面置换算法

1. 最优页面置换算法
   • 最优算法是不可实现的，但可以作为衡量其他算法的基准。
2. 最近未使用页面置换算法
   • 最近未使用页面置换算法叫做NRU（Not Recently Used）算法
   • NRU算法根据R位和M位的算法把页面分为4类（编号分别为0、1、2、3）。在最近的一个时钟滴答中（典型的大约是20ms）从编号最小的一类页面中随机清除一个页面。该算法优点是易于理解、容易实现，缺点是性能不是最好的。
3. 先进先出页面置换算法
   • 先进先出页面置换算法叫做FIFO（First-In First-Out）算法
   • FIFO算法通过维护一个由页（page）组成的链表来记录它们装入内存的顺序，优先淘汰的始终是最老的页面，但这有一个问题——淘汰的这个最老的页面可能仍在使用，因此FIFO算法不是一个好的选择。
4. 第二次机会页面置换算法
   • 第二次机会页面置换算法叫做 Second Chance算法
   • 第二次机会算法是对FIFO算法的改进，他在移除页面前会检查该页面是否正在使用。如果该页面正在被使用，就保留该页面。
5. 时钟页面置换算法
   • 时钟算法又是对第二次机会算法的改进，它具有相同的性能特征，但因为是只修改指针，而不需要操作链表，所以性能比第二次机会算法好。
6. 最近最少使用页面置换算法
   • 最近最少使用页面算法叫做 LRU（Least Recently Used）算法
   • LRU算法是一种非常优秀的算法，但只能通过特定的硬件来实现
   • LRU算法基于一种观察结论：在前面几条指令中频繁使用的页面在后面的指令中很可能被使用；反之，已经很久没使用的页面很可能在未来的一段时间也不会被使用
   • 基于上面的观察结论，LRU算法的本质是置换未使用时间最长的页面
7. 用软件模拟LRU-NFU算法
   • NFU（Not Frequently Used）算法叫做 最不常用算法

   = 该算法将每个页面和一个软件计数器相关联，计数器初始值为0。每次时钟中断时，由操作系统扫描所有的页面，然后把页面的R位（0或1）加到它的计数器上。每个计数器反应了对应页面的访问频次。发生缺页中断时，淘汰计数最小的页面。即访问频次最低的页面。

   • NFU算法近似于LRU算法，他的性能不是非常好
8. 老化算法
   • 对NFU算法稍加修改就是老化算法
   • 老化算法能很好的模拟LRU
9. 工作集页面置换算法
   • 工作集页面置换算法基于进程的局部性访问行为。即在进程运行的任何阶段，它都只访问较少的一部分页面
   • 工作集是指一个进程当前正在使用的页面的集合
   • 工作集模型是指分页系统设法跟踪进程的工作集，以确保在进程运行以前，所需的工作集就已经在内存中了。其目的是为了降低程序启动时的缺页中断率，提升程序启动速度。
   • 预先调页是指在进程运行前预先把推测出的工作集装入内存
   • 当前实际运行时间是指一个进程从它开始执行到当前所实际使用的CPU时间总数，不包括被被挂起的时间
   • 该算法的基本思路是找到一个不在工作集中的页面并淘汰它。假设每个时钟滴答中，有一个定期的时钟中断会用软件方法来清除R位。当缺页中断发生时，扫描页表的每个表项：
     • 如果表项的R位是1，就把当前实际时间写进页表项的“上次使用时间”域，目的是更新最近使用时间。以表示缺页中断发生时，该页正在被使用。既然最近使用时间被更新（该页面在当前时钟滴答中被访问过），说明该页面肯定会出现在工作集中，则不应该删除该页面（假设工作集横跨的时间t横跨多个时钟滴答）。
     • 如果表项的R位是0，那么表示当前时钟滴答中，该页面没有被访问过，则把它作为被置换的候选者。至于要不要被置换，则要看它的生存时间（当前实际运行时间-上次使用时间）是不是大于工作集的时间t。如果它的生存时间大于t，说明这个页面不再工作集中，可以用新的页面覆盖或置换它。如果页面生存时间小于或等于t，说明它在工作集中，需要把该页面临时保留下来，并记录生存时间最长（“上次使用时间”的最小值）的页面，如果扫描完真个页表发现素有的页面都在工作集中，则找到一个R位=0的页面，淘汰生存时间最长的即可。
   • 该算法有合理的性能，但开销较大。
10. 工作集时钟页面置换算法
    • 工作集时钟页面置换算法叫做 WSClock算法
    • 该算法基于时钟算法，并且使用了工作集信息
    • 与时钟算法一样，缺页中断发生时，首先检查指针指向的页面。如果指针指向的页面R位被置为1，则在当前时钟滴答中页面被使用过，该页面不适合淘汰。然后把R位置为0，指针继续向后移动

最好的两种算法是老化算法和工作集时钟算法，他们分别基于LRU和工作集，二者都具有良好的页面调度性能，可以有效的实现。在实际应用中，这两种算法可能是最重要的。 很多程序为了提升其启动速度，会对其可执行文件的二进制代码进行重新排布，称为二进制重排。其原理就是将启动时的指令符号尽量的排布在相邻的几个页面中，尽量减少程序启动时的缺页中断率。

内存管理之分段

分段的好处：

• 在一维地址空间中（无分段），当有多个动态增加的表时，一个表的增加可能会与另一个表发生碰撞
• 简化对长度经常变化的数据结构的管理
• 有助于在几个进程之间共享过程和数据，比如共享库
• 有助于为不同的段设置不同类型的保护（r、w、x）
• （假如）每个过程都位于一个独立的段，对一个过程的修改以及这个过程的变大或缩小，都不会影响其他段的过程，因为其他段中的过程的起始地址都没变。假如不分段，一个过程的变大或缩小会导致其他过程的起始地址发生变化，进而影响所有过程的地址，在程序过程较多的时候，这种开销是非常之大的。

易于编程、模块化、保护、共享

分段的实现分为两类：

• 纯分段
• 对段进行分页

纯分段

棋盘形碎片（外部碎片）：在进程运行一段时间后，因为段的转入转出，进程的地址空间内存被划分成许多快，一些块包含段，一些则称为空闲区，空闲区的碎片导致了大量的内存浪费。当然这种问题可以通过内存紧缩来解决。

对段进行分页

我们已经了解了分段的优点，也知道了分页的优点：

• 统一的页面大小
• 只使用程序或者段的一部分时，不需要把整个程序或段调入内存

纯分段的缺点也不难想象：

• 纯分段容易产生棋盘形碎片
• 如果一个段比较大，把它整个保存在内存中是不方便甚至是不可能的

所以有必要对段进行分页，这样段也可以实现“按需加载”，只有那些真正需要的页面才会调入内存，不必把段的全部内容装入内存。

总结

• 最简单的系统没有任何交换和分页技术。一旦程序装入，它们将持续在内存中，直到运行结束。这种模型适合一次只运行一个程序的模型，在小型或嵌入式实时系统中有用武之地。
• 交换技术使得系统可以一次运行总内存超过系统物理内存大小的多个进程。如果一个进程没有内存空间可用，那么他可以交换到磁盘上。内存和磁盘上的空闲空间可以是使用位图和空闲区链表来表示。
• 现代计算机都有某种形式的虚拟内存。虚拟内存很好的解决了 ①进程占用内存大于实际内存的问题 ②现代操作系统多道程序同时在内存中运行的问题。在虚拟内存中，每个进程都有自己所属的独立的地址空间，进程的地址空间被划分为多个同等大小的页（页面 page）。页面可以被放在内存中任何空闲的页框中。如果页框已满，也可以选择置换页框中的页面，被置换的页面如果被修改过，则需要写入磁盘，否则可直接丢弃（因为磁盘中的副本就是最新的）。页面置换算法有多种，比较好2个的是老化算法和工作集时钟算法。
• 看完本文，我们可以知道，现代操作系统中，无论是PC端桌面系统，还是移动端手机系统，开发者所谈论的内存通常是指“虚拟内存”。
• 我们知道了缺页中断，以及了解了操作系统在处理缺页中断中要浪费较长的时间，所以开发者可以对程序的可执行文件的二进制进行排版——二进制重排，使得程序启动时所需要的指令尽量紧凑的排列在相邻的几个页面中，这样既可以使用较少的页面来包含较多的程序启动时所需的指令，以降低程序启动时的缺页中断率。
• 分段技术可以较好的处理在执行过程中大小变化的数据结构，他还能简化链接、利于共享、利于分段保护。总之易于编程、模块化、保护、共享。纯粹的分段容易产生棋盘形碎片，将分段和分页结合，对段进行分页，提供二位的虚拟内存，不比将整段加载进内存，可以提供更细粒度的加载机制。