先说明一下MPU，MPU有很多含义，我们常见的有：

MPU：Memory Protection Unit，内存保护单元（本文描述的内容）；

MPU：Microprocessor Unit，微处理器；

MPU-6050 陀螺仪 跟这个就更是差了十万八千里了

所以请不要搞混

STM32–MPU内存保护单元(二）

MPU

MPU，即内存保护单元，可以设置不同存储区域的存储器访问特性（如只支持特权访问或全访问）和存储器属性（如可缓存、可缓冲、可共享），对存储器（主要是内存和外设）提供保护，从而提高系统可靠性

通过这些规则可以实现如下功能

• 防止不受信任的应用程序访问受保护的内存区域。
• 防止用户应用程序破坏操作系统使用的数据。
• 通过阻止任务访问其它任务的数据区。
• 允许将内存区域定义为只读，以便保护重要数据。
• 检测意外的内存访问。

也就是内存保护、外设保护和代码访问保护 设置一段内存是只读，还是只允许高权限访问，还是禁止访问等

MPU可以保护的区域为内存映射区 memory map

内存映射区就是 32 位的 CM7 内核整体可以寻址的 0 到 2^32 -1 共计 4GB 的寻址空间。通过这些地址可以访 问 RAM、Flash、外设等。下面是内存映射的轮廓图，IC 厂家使用时，再做细分，添加相应的硬件功能

也就是说 MPU可以保护我们的保护内存区域（SRAM 区）不受非法干扰，也可以保护我们的外设区（比如 FMC）

MPU 区域（region）

STM32H7 的 MPU 提供多达 16 个可编程保护区域（region）每个区域最小要求 256 字节，序号范围是 0 到 15， 每个区域（region）还可以被进一步划分为更小的子区域（sub region），每个区域（region）都有自己的可编程起始地址、大小及设置。

这些内存区可以嵌套和重叠，所以这些区域在嵌套或者重叠的时候有个优先级的问题。MPU 可以配置的 16 个内存区的序号范围是 0 到 15，序号15 的优先级最高，以此递减，还有默认区 default region，也叫作背景区，序号-1，即背景区的优先级最低。这些优先级是固定的

MPU 功能必须开启才会有效，默认条件下，MPU 是关闭的

MPU在执行其功能时，是以“region区域”为单位的。一个region其实就是一段连续的地址，只是它们的位置和范围都要满足一些限制（对齐方式，最小容量等）

MPU 区域（region）优先级

MPU 定义的区域（region）还可以相互交迭。如果某块内存落在多个区域（region）中，则访问属性和权限将由编号最大的 region 来决定。比如，若 3 号 region 与 5 号 region 交迭，则交迭的部分受 5 号 region 控制

比方说5号区域（region）内存是只读模式， 3 号 region内存是读写模式 那么重叠的部分就变成了只读模式，如果对其写入数据则会报错

MPU背景区

MPU在Region区域之外，还允许启用一个背景区域（即没有MPU 设置的其他所有地址空间），上面图片的空白存储区域。背景区域只允许特权访问。在启用 MPU 后，就不得再访问定义之外的地址区间，也不得访问未经授权的区域（region），否则，将以“访问违例”处理，触发 MemManage 异常

具体的我们在寄存器中讲解，你就会有一个清晰的了解。

---

MPU 设置是由 CTRL、RNR、RBAR 和 RASR 等寄存器控制的，其中最主要的就是RASR寄存器，下面我们来一一介绍

1.MPU 控制寄存器（CTRL），该寄存器只有最低三位有效

• PRIVDEFENA 位用于设置是否开启背景区域（region），通过设置该位为 1 即可打开背景区
• HFNMIENA 位用于控制是否在 NMI 和硬件 fault
• ENABLE 位，则用于控制是否使能 MPU

如果PRIVDEFENA 设置为0 那么就只能访问MPU的设置的内存区域，如果访问其他地址就会报错

2.MPU 区域编号寄存器（RNR）
该寄存器只有低 8 位有效 可以读写

在配置一个区域（region）之前，必须先在 MPU 内选中这个区域，我们可以通过将区域编号写入 MPU_RNR 寄存器来完成这个操作。该寄存器只有低 8 位有效，不过由于 STM32H7最多只支持 16 个区域，所以，实际上只有最低 4 位有效（0~15）。在配置完区域编号以后，我们就可以对区域属性进行设置了。

也就是设置要配置那个一内存区域（region）

3. MPU 区域属性和容量寄存器（RASR）

该寄存器是一个32位的寄存器 其中31:29位 27位 23:22位保存，没有作用

• XN(28位)：用于控制是否允许从此区域提取指令，如果 XN=1，说明禁止从区域提取指令，即这块内存区禁止执行程序代码，如果设置XN=0，则允许提取指令 即这块内存区可以执行程序代码
• AP 位（bit[26:24]），用于控制Region区域内数据的访问权限（访问许可）三位就对应8中情况

具体设置如下：

注意： 下面的TEX，C，B 和 S 都是设置Cache高速缓存的，正常使用MPU是做内存保护，用上面的AP位即可，如果没有用到Cache，下面的配置有个了解即可，在HAL库配置的时候直接禁止，不会有任何影响

如果对Cache不了解，具体可看：STM32H7—高速缓存Cache(一)

TEX，C，B 和 S 的定义如下，这仅关注 TEX = 000 和 001，其它的 TEX 配置基本用不到。

• C位：用于使能或者禁止Cache
• B位：用于配合C位实现Cache下是否使用缓冲
• S位：用于位用于控制存储器的共享特性，S=1,则二级存储器不可以缓存（Cache），如果设
  置 S=0，则可以缓存（Cache），一般我们设置该位为 0 即可。

按照配置的不同，总共可以分成以下四种：

read/write-through/back/allocate的区别：
一、CPU读Cache

1. Read through：直接从内存区读取数据
2. Read allocate：先把数据读取到Cache中，再从Cache中读取数据

二、CPU写Cache
若hit命中，有两种处理方式：

1. Write-through：在数据更新时，把数据同时写入Cache和存储区
   操作简单，但是写入速度慢
2. Write-back：只有在数据被替换出缓存时，被修改的缓存数据才会被写到后端存储。
   写入速度快，但是一旦更新后的数据未被写入时出现断电，则数据无法找回

若miss，有两种处理方式：

1. Write allocate：先把要写的数据载入到Cache中，写Cache，然后再通过flush的方式写入到内存>中。
2. No-write allocate：并不将写入位置读入缓存，直接把要写的数据写入到内存中。

什么叫hit/miss：

一、读操作
如果CPU要读取的SRAM区数据在Cache中已经加载好，这就叫读命 中（Cache hit），如果Cache里面没有怎么办，这就是所谓的读Cache Miss。
二、写操作
如果CPU要写的SRAM区数据在Cache中已经开辟了对应的区域（专业词汇叫Cache Line，以32字节为单位），这就叫写命中（Cache hit），如果Cache里面没有开辟对应的区域怎么办，这就是所谓的写Cache Miss。

• SRD位： 用于控制内存区的子区域，一共有8bit，一个bit控制一个子区域，一般都开启
• RegionSIZE位：配置Region内存区域的大小，最小为32位 可以为32kb 64kb 128kb等等

4. MPU 基地址寄存器（RBAR）

• ADDR： Region内存区的首地址

注意一定要保证首地址跟内存区的大小(RegionSIZE位)对齐，例如，我们定义某个 region 的容量(RegionSIZE位)是 64KB，那么它的基址（ADDR）就必须能被 64KB 整除,也就是这个地址对 64KB，即 0x00010000 求余数等于 0,比如0X0001 0000、0X0002 0000、0X0003 0000 等都可以被整除

• VALID 区域编号是否覆盖，如果为1的话将会重新修改ADDR Region内存区的编号
• REGION 段（bit[3:0]） ： 新编号，四位地址对应（0~15）

Region内存区的编号在初始化的时候就设置完成，所以一般VALID位设置为0

关于MPU一些基本原理和寄存器就先探讨到这里，下一篇我们来看下HAL库里MPU的配置以及如何使用。

STM32H7内存默认映射和属性

STM32H7 FMC地址

MMU 诞生之前:

在传统的批处理系统如 DOS 系统,应用程序与操作系统在内存中的布局大致如下图：

• 应用程序直接访问物理内存，操作系统占用一部分内存区。

• 操作系统的职责是“加载”应用程序，“运行”或“卸载”应用程序。

如果我们一直是单任务处理，则不会有任何问题，也或者应用程序所需的内存总是非常小，则这种架构是不会有任何问题的。然而随着计算机科学技术的发展，所需解决的问题越来越复杂，单任务批处理已不能满足需求了。而且应用程序需要的内存量也越来越大。而且伴随着多任务同时处理的需求，这种技术架构已然不能满足需求了，早先的多任务处理系统是怎么运作的呢？

程序员将应用程序分段加载执行，但是分段是一个苦力活。而且死板枯燥。此时聪明的计算机科学家想到了好办法，提出来虚拟内存的思想。程序所需的内存可以远超物理内存的大小，将当前需要执行的留在内存中，而不需要执行的部分留在磁盘中，这样同时就可以满足多应用程序同时驻留内存能并发执行了。

从总体上而言，需要实现哪些大的策略呢？

• 所有的应用程序能同时驻留内存，并由操作系统调度并发执行。需要提供机制管理 I/O 重叠，CPU 资源竞争访问。

• 虚实内存映射及交换管理，可以将真实的物理内存，有可变或固定的分区，分页或者分段与虚拟内存建立交换映射关系，并且有效的管理这种映射，实现交换管理。

这样，衍生而来的一些实现上的更具体的需求：

• 竞争访问保护管理需求：需要严格的访问保护，动态管理哪些内存页/段或区，为哪些应用程序所用。这属于资源的竞争访问管理需求。

• 高效的翻译转换管理需求：需要实现快速高效的映射翻译转换，否则系统的运行效率将会低下。

• 高效的虚实内存交换需求：需要在实际的虚拟内存与物理内存进行内存页/段交换过程中快速高效。

总之，在这样的背景下，MMU 应运而生，也由此可见，任何一项技术的发展壮大，都必然是需求驱动的。这是技术本身发展的客观规律。

 

内存管理的好处

• 为编程提供方便统一的内存空间抽象，在应用开发而言，好似都完全拥有各自独立的用户内存空间的访问权限，这样隐藏了底层实现细节，提供了统一可移植用户抽象。

• 以最小的开销换取性能最大化，利用 MMU 管理内存肯定不如直接对内存进行访问效率高，为什么需要用这样的机制进行内存管理，是因为并发进程每个进程都拥有完整且相互独立的内存空间。那么实际上内存是昂贵的，即使内存成本远比从前便宜，但是应用进程对内存的寻求仍然无法在实际硬件中，设计足够大的内存实现直接访问，即使能满足，CPU 利用地址总线直接寻址空间也是有限的。

内存管理实现总体策略

从操作系统角度来看，虚拟内存的基本抽象由操作系统实现完成：

• 处理器内存空间不必与真实的所连接的物理内存空间一致。

• 当应用程序请求访问内存时，操作系统将虚拟内存地址翻译成物理内存地址，然后完成访问。

从应用程序角度来看，应用程序（往往是进程）所使用的地址是虚拟内存地址，从概念上就如下示意图所示，MMU 在操作系统的控制下负责将虚拟内存实际翻译成物理内存。

从而这样的机制，虚拟内存使得应用程序不用将其全部内容都一次性驻留在内存中执行：

• 节省内存：很多应用程序都不必让其全部内容一次性加载驻留在内存中，那么这样的好处是显而易见，即使硬件系统配置多大的内存，内存在系统中仍然是最为珍贵的资源。所以这种技术节省内存的好处是显而易见的。

• 使得应用程序以及操作系统更具灵活性。

  • 操作系统根据应用程序的动态运行时行为灵活的分配内存给应用程序。

  • 使得应用程序可以使用比实际物理内存多或少的内存空间。

MMU 以及 TLB

MMU(Memory Management Unit)内存管理单元：

• 一种硬件电路单元负责将虚拟内存地址转换为物理内存地址

• 所有的内存访问都将通过 MMU 进行转换，除非没有使能 MMU。

TLB(Translation Lookaside Buffer)转译后备缓冲器: 本质上是 MMU 用于虚拟地址到物理地址转换表的缓存

这样一种架构，其最终运行时目的，是为主要满足下面这样运行需求：

多进程并发同时并发运行在实际物理内存空间中，而 MMU 充当了一个至关重要的虚拟内存到物理内存的桥梁作用。

那么，这种框架具体从高层级的概念上是怎么做到的呢？事实上，是将物理内存采用分片管理的策略来实现的，那么，从实现的角度将有两种可选的策略：

• 固定大小分区机制

• 可变大小分区机制

固定大小区片机制

通过这样一种概念上的策略，将物理内存分成固定等大小的片：

• 每一个片提供一个基地址

• 实际寻址，物理地址=某片基址+虚拟地址

• 片基址由操作系统在进程动态运行时动态加载

这种策略实现，其优势在于简易，切换快速。但是该策略也带来明显的劣势：

• 内部碎片:一个进程不使用的分区中的内存对其他进程而言无法使用

• 一种分区大小并不能满足所有应用进程所需。

可变大小分区机制

内存被划分为可变大小的区块进行映射交换管理：

• 需要提供基址以及可变大小边界，可变大小边界用于越界保护。

• 实际寻址，物理地址=某片基址+虚拟地址

那么这种策略其优势在于没有内部内存碎片，分配刚好够进程所需的大小。但是劣势在于，在加载和卸载的动态过程中会产生碎片。

分页机制

分页机制采用在虚拟内存空间以及物理内存空间都使用固定大小的分区进行映射管理。

• 从应用程序(进程)角度看内存是连续的 0-N 的分页的虚拟地址空间。

• 物理内存角度看，内存页是分散在整个物理存储中

• 这种映射关系对应用程序不可见，隐藏了实现细节。

分页机制是如何寻址的呢？这里介绍的设计理念，具体的处理器实现各有细微差异：

• 虚拟地址包含了两个部分：虚拟页序号 VPN（virtual paging number)以及偏移量

• 虚拟页序号 VPN是页表（Page Table）的索引

• 页表（Page Table）维护了页框号(Page frame number PFN)

• 物理地址由PFN::Offset进行解析。

举个栗子，如下图所示：

还没有查到具体的物理地址，憋急，再看一下完整解析示例：

 

如何管理页表

对于 32 位地址空间而言，假定 4K 为分页大小，则页表的大小为 100MB，这对于页表的查询而言是一个很大的开销。那么如何减小这种开销呢？实际运行过程中发现，事实上只需要映射实际使用的很小一部分地址空间。那么在一级页机制基础上，延伸出多级页表机制。

以二级分页机制为例：

单级页表已然有不小的开销，查询页表以及取数，而二级分页机制，因为需要查询两次页表，则将这种开销再加一倍。那么如何提高效率呢？其实前面提到一个概念一直还没有深入描述 TLB,将翻译工作由硬件缓存 cache,这就是 TLB 存在的意义。

• TLB 将虚拟页翻译成 PTE，这个工作可在单周期指令完成。

• TLB 由硬件实现

  • 完全关联缓存(并行查找所有条目)

  • 缓存索引是虚拟页码

  • 缓存内容是 PTE

  • 则由 PTE+offset，可直接计算出物理地址

TLB 加载

谁负责加载 TLB 呢？这里可供选择的有两种策略：

• 由操作系统加载，操作系统找到对应的 PTE，而后加载到 TLB。格式比较灵活。

• MMU 硬件负责，由操作系统维护页表，MMU 直接访问页表，页表格式严格依赖硬件设计格式。

总结一下

从计算机大致发展历程来了解内存管理的大致发展策略，如何衍生出 MMU，以及固定分片管理、可变分片管理等不同机制的差异，最后衍生出单级分页管理机制、多级分页管理机制、TLB 的作用。从概念上相对比较易懂的角度描述了 MMU 的诞生、机制，而忽略了处理器的具体实现细节。作为从概念上更深入的理解 MMU 的工作机理的角度，还是不失为一篇浅显易懂的文章。

内存作为计算机中一项比较重要的资源，它的主要作用就是解决CPU和磁盘之间速度的鸿沟，但是由于内存条是需要插入到主板上的，因此对于一台计算机来说，由于物理限制，它的内存不可能无限大的。我们知道我们写的代码最终是要从磁盘被加载到内存中的，然后再被CPU执行，不知道你有没有想过，为什么一些大型游戏大到10几G，却可以在只有8G内存的电脑上运行？甚至在玩游戏期间，我们还可以聊微信、听音乐...，这么多进程看着同时在运行，它们在内存中是如何被管理的？带着这些疑问我们来看看计算系统内存管理那些事。

内存的交换技术

如果我们的内存可以无限大，那么我们担忧的问题就不会存在，但是实际情况是往往我们的机器上会同时运行多个进程，这些进程小到需要几十兆内存，大到可能需要上百兆内存，当许许多多这些进程想要同时加载到内存的时候是不可能的，但是从我们用户的角度来看，似乎这些进程确实都在运行呀，这是怎么回事？

这就引入要说的交换技术了，从字面的意思来看，我想你应该猜到了，它会把某个内存中的进程交换出去。当我们的进程空闲的时候，其他的进程又需要被运行，然而很不幸，此时没有足够的内存空间了，这时候怎么办呢？似乎刚刚那个空闲的进程有种占着茅坑不拉屎的感觉，于是可以把这个空闲的进程从内存中交换到磁盘上去，这时候就会空出多余的空间来让这个新的进程运行，当这个换出去的空闲进程又需要被运行的时候，那么它就会被再次交换进内存中。通过这种技术，可以让有限的内存空间运行更多的进程，进程之间不停来回交换，看着好像都可以运行。 

 如图所示，一开始进程A被换入内存中，所幸还剩余的内存空间比较多，然后进程B也被换入内存中，但是剩余的空间比较少了，这时候进程C想要被换入到内存中，但是发现空间不够了，这时候会把已经运行一段时间的进程A换到磁盘中去，然后调入进程C。 

内存碎片

通过这种交换技术，交替的换入和换出进程可以达到小内存可以运行更多的进程，但是这似乎也产生了一些问题，不知道你发现了没有，在进程C换入进来之后，在进程B和进程C之间有段较小的内存空间，并且进程B之上也有段较小的内存空间，说实话，这些小空间可能永远没法装载对应大小的程序，那么它们就浪费了，在某些情况下，可能会产生更多这种内存碎片。

 如果想要节约内存，那么就得用到内存紧凑的技术了，即把所有的进程都向下移动，这样所有的碎片就会连接在一起变成一段更大的连续内存空间了。 

 但是这个移动的开销基本和当前内存中的活跃进程成正比，据统计，一台16G内存的计算机可以每8ns复制8个字节，它紧凑全部的内存大概需要16s，所以通常不会进行紧凑这个操作，因为它耗费的CPU时间还是比较大的。

动态增长

其实上面说的进程装载算是比较理想的了，正常来说，一个进程被创建或者被换入的时候，它占用多大的空间就分配多大的内存，但是如果我们的进程需要的空间是动态增长的，那就麻烦了，比如我们的程序在运行期间的for循环可能会利用到某个临时变量来存放目标数据（例如以下变量a，随着程序的运行是会越来越大的）：

var a []int64
for i:= 0;i <= 1000000;i++{
  if i%2 == 0{
   a = append(a,i) //a是不断增大的
  }
}

当需要增长的时候：

1. 如果进程的邻居是空闲区那还好，可以把该空闲区分配给进程
2. 如果进程的邻居是另一个进程，那么解决的办法只能把增长的进程移动到一个更大的空闲内存中，但是万一没有更大的内存空间，那么就要触发换出，把一个或者多个进程换出去来提供更多的内存空间，很明显这个开销不小。

为了解决进程空间动态增长的问题，我们可以提前多给一些空间，比如进程本身需要10M，我们多给2M，这样如果进程发生增长的时候，可以利用这2M空间，当然前提是这2M空间够用，如果不够用还是得触发同样的移动、换出逻辑。

空闲的内存如何管理

前面我们说到内存的交换技术，交换技术的目的是腾出空闲内存来，那么我们是如何知道一块内存是被使用了，还是空闲的？因此需要一套机制来区分出空闲内存和已使用内存，一般操作系统对内存管理的方式有两种：位图法和链表法。

位图法

先说位图法，没错，位图法采用比特位的方式来管理我们的内存，每块内存都有位置，我们用一个比特位来表示：

1. 如果某块内存被使用了，那么比特位为1
2. 如果某块内存是空闲的，那么比特位为0

这里的某块内存具体是多大得看操作系统是如何管理的，它可能是一个字节、几个字节甚至几千个字节，但是这些不是重点，重点是我们要知道内存被这样分割了。

 位图法的优点就是清晰明确，某个内存块的状态可以通过位图快速的知道，因为它的时间复杂度是O(1)，当然它的缺点也很明显，就是需要占用太多的空间，尤其是管理的内存块越小的时候。更糟糕的是，进程分配的空间不一定是内存块的整数倍，那么最后一个内存块中一定是有浪费的。

如图，进程A和进程B都占用的最后一个内存块的一部分，那么对于最后一个内存块，它的另一部分一定是浪费的。

链表法

相比位图法，链表法对空间的利用更加合理，我相信你应该已经猜到了，链表法简单理解就是把使用的和空闲的内存用链表的方式连接起来，那么对于每个链表的元素节点来说，他应该具备以下特点：

1. 应该知道每个节点是空闲的还是被使用的
2. 每个节点都应该知道当前节点的内存的开始地址和结束地址

针对这些特点，最终内存对应的链表节点大概是这样的：

 p代表这个节点对应的内存空间是被使用的，H代表这个节点对应的内存空间是空闲的，start代表这块内存空间的开始地址，length代表的是这块内存的长度，最后还有指向邻居节点的pre和next指针。

因此对于一个进程来说，它与邻居的组合有四种：

1. 它的前后节点都不是空闲的
2. 它的前一个节点是空闲的，它的后一个节点也不是空闲的
3. 它的前一个节点不是空闲的，它的后一个节点是空闲的
4. 它的前后节点都是空闲的

当一个内存节点被换出或者说进程结束后，那么它对应的内存就是空闲的，此时如果它的邻居也是空闲的，就会发生合并，即两块空闲的内存块合并成一个大的空闲内存块。

ok，通过链表的方式把我们的内存给管理起来了，接下来就是当创建一个进程或者从磁盘换入一个进程的时候，如何从链表中找到一块合适的内存空间？

首次适应算法

其实想要找到空闲内存空间最简单的办法就是顺着链表找到第一个满足需要内存大小的节点，如果找到的第一个空闲内存块和我们需要的内存空间是一样大小的，那么就直接利用，但是这太理想了，现实情况大部分可能是找到的第一个目标内存块要比我们的需要的内存空间要大一些，这时候呢，会把这个空闲内存空间分成两块，一块正好使用，一块继续充当空闲内存块。

 一个需要3M内存的进程，会把4M的空间拆分成3M和1M。

下次适配算法

和首次适应算法很相似，在找到目标内存块后，会记录下位置，这样下次需要再次查找内存块的时候，会从这个位置开始找，而不用从链表的头节点开始寻找，这个算法存在的问题就是，如果标记的位置之前有合适的内存块，那么就会被跳过。

 一个需要2M内存的进程，在5这个位置找到了合适的空间，下次如果需要这1M的内存会从5这个位置开始，然后会在7这个位置找到合适的空间，但是会跳过1这个位置。

最佳适配算法

相比首次适应算法，最佳适配算法的区别就是：不是找到第一个合适的内存块就停止，而是会继续向后找，并且每次都可能要检索到链表的尾部，因为它要找到最合适那个内存块，什么是最合适的内存块呢？如果刚好大小一致，则一定是最合适的，如果没有大小一致的，那么能容得下进程的那个最小的内存块就是最合适的，可以看出最佳适配算法的平均检索时间相对是要慢的，同时可能会造成很多小的碎片。

 假设现在进程需要2M的内存，那么最佳适配算法会在检索到3号位置（3M）后，继续向后检索，最终会选择5号位置的空闲内存块。

最差适配算法

我们知道最佳适配算法中最佳的意思是找到一个最贴近真实大小的空闲内存块，但是这会造成很多细小的碎片，这些细小的碎片一般情况下，如果没有进行内存紧凑，那么大概率是浪费的，为了避免这种情况，就出现了这个最差适配算法，这个算法它和最佳适配算法是反着来的，它每次尝试分配最大的可用空闲区，因为这样的话，理论上剩余的空闲区也是比较大的，内存碎片不会那么小，还能得到重复利用。

 一个需要1.5M的进程，在最差适配算法情况下，不会选择3号（2M）内存空闲块，而是会选择更大的5号（3M）内存空闲块。

快速适配算法

上面的几种算法都有一个共同的特点：空闲内存块和已使用内存块是共用的一个链表，这会有什么问题呢？正常来说，我要查找一个空闲块，我并不需要检索已经被使用的内存块，所以如果能把已使用的和未使用的分开，然后用两个链表分别维护，那么上面的算法无论哪种，速度都将得到提升，并且节点也不需要P和M来标记状态了。但是分开也有缺点，如果进程终止或者被换出，那么对应的内存块需要从已使用的链表中删掉然后加入到未使用的链表中，这个开销是要稍微大点的。当然对于未使用的链表如果是排序的，那么首次适应算法和最佳适应算法是一样快的。

快速适配算法就是利用了这个特点，这个算法会为那些常用大小的空闲块维护单独的链表，比如有4K的空闲链表、8K的空闲链表...，如果要分配一个7K的内存空间，那么既可以选择两个4K的，也可以选择一个8K的。

 它的优点很明显，在查找一个指定大小的空闲区会很快速，但是一个进程终止或被换出时，会寻找它的相邻块查看是否可以合并，这个过程相对较慢，如果不合并的话，那么同样也会产生很多的小空闲区，它们可能无法被利用，造成浪费。

虚拟内存：小内存运行大程序

可能你看到小内存运行大程序比较诧异，因为上面不是说到了吗？只要把空闲的进程换出去，把需要运行的进程再换进来不就行了吗？内存交换技术似乎解决了，这里需要注意的是，首先内存交换技术在空间不够的情况下需要把进程换出到磁盘上，然后从磁盘上换入新进程，看到磁盘你可能明白了，很慢。其次，你发现没，换入换出的是整个进程，我们知道进程也是由一块一块代码组成的，也就是许许多多的机器指令，对于内存交换技术来说，一个进程下的所有指令要么全部进内存，要么全部不进内存。看到这里你可能觉得这不是正常吗？好的，别急，我们接着往下看。

后来出现了更牛逼的技术：虚拟内存。它的基本思想就是，每个程序拥有自己的地址空间，尤其注意后面的自己的地址空间，然后这个空间可以被分割成多个块，每一个块我们称之为页（page）或者叫页面，对于这些页来说，它们的地址是连续的，同时它们的地址是虚拟的，并不是真正的物理内存地址，那怎么办？程序运行需要读到真正的物理内存地址，别跟我玩虚的，这就需要一套映射机制，然后MMU出现了，MMU全称叫做：Memory Managment Unit，即内存管理单元，正常来说，CPU读某个内存地址数据的时候，会把对应的地址发到内存总线上，但是在虚拟内存的情况下，直接发到内存总线上肯定是找不到对应的内存地址的，这时候CPU会把虚拟地址告诉MMU，让MMU帮我们找到对应的内存地址，没错，MMU就是一个地址转换的中转站。

程序地址分页的好处是：

1. 对于程序来说，不需要像内存交换那样把所有的指令都加载到内存中才能运行，可以单独运行某一页的指令
2. 当进程的某一页不在内存中的时候，CPU会在这个页加载到内存的过程中去执行其他的进程。

当然虚拟内存会分页，那么对应的物理内存其实也会分页，只不过物理内存对应的单元我们叫页框。页面和页框通常是一样大的。我们来看个例子，假设此时页面和页框的大小都是4K，那么对于64K的虚拟地址空间可以得到64/4=16个虚拟页面，而对于32K的物理地址空间可以得到32/4=8个页框，很明显此时的页框是不够的，总有些虚拟页面找不到对应的页框。

我们先来看看虚拟地址为20500对应物理地址如何被找到的：

1. 首先虚拟地址20500对应5号页面（20480-24575）
2. 5号页面的起始地址20480向后查找20个字节，就是虚拟地址的位置
3. 5号页面对应3号物理页框
4. 3号物理页框的起始地址是12288，12288+20=12308，即12308就是我们实际的目标物理地址。

但是对于虚拟地址而言，图中还有红色的区域，上面我们也说到了，总有些虚拟地址没有对应的页框，也就是这部分虚拟地址是没有对应的物理地址，当程序访问到一个未被映射的虚拟地址（红色区域）的时候，那么就会发生缺页中断，然后操作系统会找到一个最近很少使用的页框把它的内容换到磁盘上去，再把刚刚发生缺页中断的页面从磁盘读到刚刚回收的页框中去，最后修改虚拟地址到页框的映射，然后重启引起中断的指令。

最后可以发现分页机制使我们的程序更加细腻了，运行的粒度是页而不是整个进程，大大提高了效率。

页表

上面说到虚拟内存到物理内存有个映射，这个映射我们知道是MMU做的，但是它是如何实现的？最简单的办法就是需要有一张类似hash表的结构来查看，比如页面1对应的页框是10，那么就记录成hash[1]=10，但是这仅仅是定位到了页框，具体的位置还没定位到，也就是类似偏移量的数据没有。不猜了，我们直接来看看MMU是如何做到的，以一个16位的虚拟地址，并且页面和页框都是4K的情况来说，MMU会把前4位当作是索引，也就是定位到页框的序号，后12位作为偏移量，这里为什么是12位，很巧妙，因为2^12=4K，正好给每个页框里的数据上了个标号。因此我们只需要根据前4位找到对应的页框即可，然后偏移量就是后12位。找页框就是去我们即将要说的页表里去找，页表除了有页面对应的页框后，还有个标志位来表示对应的页面是否有映射到对应的页框，缺页中断就是根据这个标志位来的。

可以看出页表非常关键，不仅仅要知道页框、以及是否缺页，其实页表还有保护位、修改位、访问位和高速缓存禁止位。

• 保护位：指的是一个页允许什么类型的访问，常见的是用三个比特位分别表示读、写、执行。
• 修改位：有时候也称为脏位，由硬件自动设置，当一个页被修改后，也就是和磁盘的数据不一致了，那么这个位就会被标记为1，下次在页框置换的时候，需要把脏页刷回磁盘，如果这个页的标记为0，说明没有被修改，那么不需要刷回磁盘，直接把数据丢弃就行了。
• 访问位：当一个页面不论是发生读还是发生写，该页面的访问位都会设置成1，表示正在被访问，它的作用就是在发生缺页中断时，根据这个标志位优先在那些没有被访问的页面中选择淘汰其中的一个或者多个页框。
• 高速缓存禁止位：对于那些映射到设备寄存器而不是常规内存的页面而言，这个特性很重要，加入操作系统正在紧张的循环等待某个IO设备对它刚发出的指令做出响应，保证这个设备读的不是被高速缓存的副本非常重要。

TLB快表加速访问

通过页表我们可以很好的实现虚拟地址到物理地址的转换，然而现代计算机至少是32位的虚拟地址，以4K为一页来说，那么对于32位的虚拟地址，它的页表项就有2^20=1048576个，无论是页表本身的大小还是检索速度，这个数字其实算是有点大了。如果是64位虚拟的地址，按照这种方式的话，页表项将大到超乎想象，更何况最重要的是每个进程都会有一个这样的页表。

我们知道如果每次都要在庞大的页表里面检索页框的话，效率一定不是很高。而且计算机的设计者们观察到这样一种现象：大多数程序总是对少量的页进行多次访问，如果能为这些经常被访问的页单独建立一个查询页表，那么速度就会大大提升，这就是快表，快表只会包含少量的页表项，通常不会超过256个，当我们要查找一个虚拟地址的时候。首先会在快表中查找，如果能找到那么就可以直接返回对应的页框，如果找不到才会去页表中查找，然后从快表中淘汰一个表项，用新找到的页替代它。

总体来说，TLB类似一个体积更小的页表缓存，它存放的都是最近被访问的页，而不是所有的页。

多级页表

TLB虽然一定程度上可以解决转换速度的问题，但是没有解决页表本身占用太大空间的问题。其实我们可以想想，大部分程序会使用到所有的页面吗？其实不会。一个进程在内存中的地址空间一般分为程序段、数据段和堆栈段，堆栈段在内存的结构上是从高地址向低地址增长的，其他两个是从低地址向高地址增长的。

可以发现中间部分是空的，也就是这部分地址是用不到的，那我们完全不需要把中间没有被使用的内存地址也引入页表呀，这就是多级页表的思想。以32位地址为例，后12位是偏移量，前20位可以拆成两个10位，我们暂且叫做顶级页表和二级页表，每10位可以表示2^10=1024个表项，因此它的结构大致如下：

 对于顶级页表来说，中间灰色的部分就是没有被使用的内存空间。顶级页表就像我们身份证号前面几个数字，可以定位到我们是哪个城市或者县的，二级页表就像身份证中间的数字，可以定位到我们是哪个街道或者哪个村的，最后的偏移量就像我们的门牌号和姓名，通过这样的分段可以大大减少空间，我们来看个简单的例子：

如果我们不拆出顶级页表和二级页表，那么所需要的页表项就是2^20个，如果我们拆分，那么就是1个顶级页表+2^10个二级页表，两者的存储差距明显可以看出拆分后更加节省空间，这就是多级页表的好处。

当然我们的二级也可以拆成三级、四级甚至更多级，级数越多灵活性越大，但是级数越多，检索越慢，这一点是需要注意的。

---

最后

为了便于大家理解，本文画了20张图，肝了将近7000多字，创作不易，各位的三连就是对作者最大的支持，也是作者最大的创作动力。

微信搜一搜【假装懂编程】，加入我们，与作者共同学习，共同进步。

 

往期精彩：

• 简单！代码原来是这样被CPU跑起来的
• 20张图！常见分布式理论与解决方案
• 小心陷入MySQL索引的坑