探索OS的内存管理原理
前言
内存作为计算机系统的组成部分，跟开发人员的日常开发活动有着密切的联系，我们平时遇到的segment fault、outofmemory、memory leak、gc等都与它有关。本文所说的内存，指的是计算机系统中的主存（main memory），它位于存储金字塔中cpu缓存和磁盘之间，是程序运行不可或缺的一部分。
图1
在计算机系统中，主存通常都是由操作系统（os）来管理，而内存管理的细则对开发者来说是无感的。对于一个普通的开发者，他只需懂得如何调用编程语言的接口来进行内存申请和释放，即可写出一个可用的应用程序。如果你使用的是带有垃圾回收机制的语言，如java和go，甚至都不用主动释放内存。但如果你想写出高效应用程序，熟悉os的内存管理原理就变得很有必要了。
下面，我们将从最简单的内存管理原理说起，带大家一起窥探os的内存管理机制，由此熟悉底层的内存管理机制，写出高效的应用程序。
独占式内存管理
早期的单任务系统中，同一时刻只能有一个应用程序独享所有的内存（除开os占用的内存），因此，内存管理可以很简单，只需在内存上划分两个区域：
图2
在多任务系统中，计算机系统已经可以做到多个任务并发运行。如果还是按照独占式的管理方式，那么每次任务切换时，都会涉及多次内存和磁盘之间的数据拷贝，效率极其低下：
图3
最直观的解决方法就是让所有程序的数据都常驻在内存中（假设内存足够大），这样就能避免数据拷贝了：
图4
但这样又会带来另一个问题，程序之间的内存地址空间是没有隔离的，也就是程序a可以修改程序b的内存数据。这样的一个重大的安全问题是用户所无法接受的，要解决该问题，就要借助虚拟化的力量了。
虚拟地址空间
为了实现程序间内存的隔离，os对物理内存做了一层虚拟化。os为每个程序都虚拟化出一段内存空间，这段虚拟内存空间会映射到一段物理内存上。但对程序自身而言，它只能看到自己的虚拟地址空间，也就有独占整个内存的错觉了。
图5
上图中，虚拟内存空间分成了三个区域，其中code区域存储的是程序代码的机器指令；heap区域存储程序运行过程中动态申请的内存；stack区域则是存储函数入参、局部变量、返回值等。heap和stack会在程序运行过程中不断增长，分别放置在虚拟内存空间的上方和下方，并往相反方向增长。
从虚拟地址空间到物理地址空间的映射，需要一个转换的过程，完成这个转换运算的部件就是mmu（memory management unit），也即内存管理单元，它位于cpu芯片之内。
要完成从虚拟地址到物理地址到转换，mmu需要base和bound两个寄存器。其中base寄存器用来存储程序在物理内存上的基地址，比如在图5中，程序a的基地址就是192kb；bound寄存器（有时候也叫limit寄存器）则保存虚拟地址空间的size，主要用来避免越界访问，比如图5中程序a的size值为64k。那么，基于这种方式的地址转换公式是这样的：
物理地址 = 虚拟地址 + 基地址
以图5中程序a的地址转换为例，当程序a尝试访问超过其bound范围的地址时，物理地址会转换失败：
图6
现在，我们再次仔细看下程序a的物理内存分布，如下图7所示，中间有很大的一段空闲内存是“已申请，未使用”的空闲状态。这也意味着即使这部分是空闲的，也无法再次分配给其他程序使用，这是一种巨大的空间浪费！为了解决这个内存利用率低下的问题，我们熟悉的段式内存管理出现了。
图7
段式内存管理
在上一节中，我们发现如果以程序为单位去做内存管理，会存在内存利用率不足的问题。为了解决该问题，段式内存管理被引入。段（segment）是逻辑上的概念，本质上是一块连续的、有一定大小限制的内存区域，前文中，我们一共提到过3个段：code、heap和stack。
段式内存管理以段为单位进行管理，它允许os将每个段灵活地放置在物理内存的空闲位置上，因此也避免了“已申请，未使用”的内存区域出现：
图8
地址转换
从上图8可知，段式内存管理中程序的物理内存空间可能不再连续了，因此为了实现从虚拟地址到物理地址到转换，mmu需要为每个段都提供一对base-bound寄存器，比如：
图9
给一个虚拟地址，mmu是如何知道该地址属于哪个段，从而根据对应的base-bound寄存器转换为对应的物理地址呢？
假设虚拟地址有16位，因为只有3个段，因此，我们可以使用虚拟地址的高2位来作为段标识，比如00表示code段，01表示heap段，11表示stack段。这样mmu就能根据虚拟地址来找到对应段的base-bound寄存器了：
图10
但这样还不是能够顺利的将虚拟地址转换为物理地址，我们忽略了重要的一点：heap段和stack段的增长方向是相反的，这也意味着两者的地址转换方式是不一样的。因此，我们还必须在虚拟地址中多使用一位来标识段的增长方向，比如0表示向上（低地址方向）增长，1表示向下（高地址方向）增长：
图11
下面，看一组段式内存管理地址转换的例子：
图12
那么，总结段式内存管理的地址转换算法如下：
// 获取当前虚拟地址属于哪个段segment = (virtualaddress & seg_mask) >> seg_shift// 得到段内偏移量offset = virtualaddress & offset_mask// 获得内存增长的方向growsdirection = virtualaddress & grows_direction_mask// 有效性校验if (offset >= bounds[segment]) raiseexception(protection_fault)else if (growsdirection == 0) { physaddr = base[segment] + offset } else { physaddr = base[segment] - offset }
内存共享和保护
段式内存管理还可以很方便地支持内存共享，从而达到节省内存的目的。比如，如果存在多个程序都是同一个可执行文件运行起来的，那么这些程序是可以共享code段的。为了实现这个功能，我们可以在虚拟地址上设置保护位，当保护位为只读时，表示该段可以共享。另外，如果程序修改了只读的段，则转换地址失败，因此也可以达到内存保护的目的。
图13
内存碎片
段式内存管理的最明显的缺点就是容易产生内存碎片，这是因为在系统上运行的程序的各个段的大小往往都不是固定的，而且段的分布也不是连续的。当系统的内存碎片很多时，内存的利用率也会急剧下降，对外表现就是虽然系统看起来还有很多内存，却无法再运行起一个程序。
解决内存碎片的方法之一是定时进行碎片整理：
图14
但是碎片整理的代价极大，一方面需要进行多次内存拷贝；另一方面，在拷贝过程中，正在运行的程序必须停止，这对于一些以人机交互任务为主的应用程序，将会极大影响用户体验。
另一个解决方法就是接下来要介绍的页式内存管理。
页式内存管理
页式内存管理的思路，是将虚拟内存和物理内存都划分为多个固定大小的区域，这些区域我们称之为页（page）。页是内存的最小分配单位，一个应用程序的虚拟页可以存放在任意一个空闲的物理页中。
物理内存中的页，我们通常称之为页帧（page frame）
图15
因为页的大小是固定的，而且作为最小的分配单位，这样就可以解决段式内存管理中内存碎片的问题了。
但页内仍然有可能存在内存碎片。
地址转换
页式内存管理使用页表（page table）来进行虚拟地址到物理地址到转换，地址转换的关键步骤如下：
1）根据虚拟页找到对应的物理页帧
每个虚拟页都有一个编号，叫做vpn（virtual page number）；相应的，每个物理页帧也有一个编号，叫做pfn（physical frame number）。页表存储的就是vpn到pfn的映射关系。
2）找到地址在物理页帧内的偏移（offset）
地址在物理页帧内的偏移与在虚拟页内的偏移保持一致。
我们可以将虚拟地址划分成两部分，分别存储vpn和offset，这样就能通过vpn找到pfn，从而得到pfn+offset的实际物理地址了。
比如，假设虚拟内存空间大小为64byte（6位地址），页的大小为16byte，那么整个虚拟内存空间一共有4个页。因此我们可以使用高2位来存储vpn，低4位存储offset：
图16
下面看一个转换例子，vpn（01）通过页表找到对应的pfn（111），虚拟地址和物理地址的页内偏移都是0100，那么虚拟地址010100对应的物理地址就是1110100了。
图17
页表和页表项
os为每个程序都分配了一个页表，存储在内存当中，页表里由多个页表项（pte，page table entry）组成。我们可以把页表看成是一个数组，数组的元素为pte：
图18
以x86系统下的pte组成为例，pte一共占32位，除了pfn之外，还有一些比较重要的信息，比如p（present）标识当前页是否位于内存上（或是磁盘上）；r/w（read/write）标识当前页是否允许读写（或是只读）；u/s（user/supervisor）标识当前页是否允许用户态访问；a（access）标识当前页是否被访问过，在判断当前页是否为热点数据、页换出时特别有用；d（dirty）标识当前页是否被修改过。
页式内存管理的缺点
地址转换效率低
根据前文介绍，我们可以总结页式内存管理机制下地址转换的算法如下：
// 从虚拟地址上得到vpnvpn = (virtualaddress & vpn_mask) >> shift// 找到vpn对应的pte的内存地址pteaddr = ptbr + (vpn * sizeof(pte))// 访问主存，获取ptepte = accessmemory(pteaddr)// 有效性校验if (pte.valid == false) raiseexception(invalid_access)else // 获取页内偏移量 offset = virtualaddress & offset_mask // 计算得出物理地址 physaddr = (pte.pfn <> shift(success, tlbentry) = tlb_lookup(vpn)if (success == true) // tlb hit if (canaccess(tlbentry.protectbits) == true) offset = virtualaddress & offset_mask physaddr = (tlbentry.pfn << shift) | offset else raiseexception(protection_fault)else // tlb miss pteaddr = ptbr + (vpn * sizeof(pte)) pte = accessmemory(pteaddr) if (pte.valid == false) raiseexception(segmentation_fault) else if (canaccess(pte.protectbits) == false) raiseexception(protection_fault) else tlb_insert(vpn, pte.pfn, pte.protectbits) retryinstruction()
从上述算法可以发现，在tlb缓存命中（tlb hit）时，能够避免直接访问主存，从而提升了地址转换的效率；但是在tlb缓存不命中（tlb miss）时，仍然需要访问一次主存，而且还要往tlb中插入从主存中查询到的pfn，效率变得更低了。因此，我们必须尽量避免tlb miss的出现。
更好地利用tlb
下面，我们通过一个数组遍历的例子来介绍如何更好地利用tlb。
假设我们要进行如下的一次数组遍历：
int sum = 0;for (i = 0; i < 10; i++) { sum += a[i]; }
数组的内存的分布如下：
图20
a[0]~a[2]位于page 5上，a[3]~a[6]位于page 6上，a[7]~a[8]位于page 7上。当我们首先访问a[0]时，由于page 5并未在tlb缓存里，所以会先出现一次tlb miss，接下来的a[1]和a[2]都是tlb hit；同理，访问a[3]和a[7]时都是tlb miss，a[4]~a[6]和a[8]~a[9]都是tlb hit。所以，整个数组遍历下来，tlb的缓存命中情况为：miss，hit，hit，miss，hit，hit，hit，miss，hit，hit，tlb缓存命中率为70%。我们发现，访问同一页上的数据tlb的缓存更易命中，这就是空间局部性的原理。
接下来，我们再次重新遍历一次数组，由于经过上一次之后page 5 ～ page 7的转换信息已经在tlb缓存里里，所以第二次遍历的tlb命中情况为：hit，hit，hit，hit，hit，hit，hit，hit，hit，hit，tlb缓存命中率为100%！这就是时间局部性的原理，短时间内访问同一内存数据也能够提升tlb缓存命中率。
tlb的上下文切换
因为tlb缓存的是当前正在运行程序的上下文信息，当出现程序切换时，tlb里面的上下文信息也必须更新，否则地址转换就会异常。解决方法主要有2种：
方法1：每次程序切换都清空tlb缓存（flush tlb），让程序在运行过程中重新建立缓存。
方法2：允许tlb缓存多个程序的上下文信息，并通过asid（address space identifier，地址空间标识符，可以理解为程序的pid）做区分。
方法1实现简单，但是每次程序切换都需要重新预热一遍缓存，效率较低，主流的做法是采用方法2。
需要注意的是tlb是嵌入到cpu芯片之内的，对于多核系统而言，如果程序在cpu之间来回切换，也是需要重新建立tlb缓存！因此，把一个程序绑定在一个固定的核上有助于提升性能。
让页表更小
大页内存
降低页表大小最简单的方法就是让页更大。前文的例子中，地址空间为32-bit，页的大小为4kb，pte的大小为4-byte，那么每个页表需要4mb的内存空间。现在，我们把页的大小增加到16kb，其他保持不变，那么每个页表只需要个pte，也即1mb内存，内存占用降低了4倍。
大页内存对tlb的使用也有优化效果，因tlb能够缓存的上下文数量是固定的，当页的数量更少时，上下文换出的频率会降低，tlb的缓存命中率也就增加了，从而让地址转换的效率更高。
段页式内存管理
根据前文所述，程序的地址空间中，堆与栈之间的空间很多时候都是处于未使用状态。对应到页表里，就是有很大一部分的pte是invalid状态。但因为页表要涵盖整个地址空间的范围，这部分invalid的pte只能留在页表中，从而造成了很大的空间浪费。
图21
前文中，我们通过段式内存管理解决了堆与栈之间内存空间的浪费问题。对应到页表中，我们也可以为页式内存管理引入段式管理的方式，也即段页式内存管理，解决页表空间浪费的问题。
具体的方法是，为程序的地址空间划分出多个段，比如code、heap、stack等。然后，在每个段内单独进行页式管理，也即为每个段引入一个页表：
图22
从上图可知，将页表分段之后，页表不再需要记录那些处于空闲状态的页的pte，从而节省了内存空间的消耗。
多级页表
降低页表大小另一个常见的方法就是多级页表（multi-level page table），多级页表的思路也是减少处于空闲状态的页的pte数量，但方法与段页式内存管理不同。如果说段页式内存管理可以看成是将页表分段，那么多级页表则可以看成是将页表分页。
具体的做法是将页表按照一定大小分成多个部分（页目录，page directory，pd），如果某个页目录下所有的页都是处于空闲状态，则无须为该页目录下的页申请pte。
以二级页表为例，下图对比了普通页表和多级页表的构成差异：
图23
下面，我们再对比一下普通页表和多级页表的空间消耗。还是假设地址空间为32-bit，页的大小为4kb，pte的大小为4-byte，一共有个页，那么普通页表需要4mb的内存空间。现在，我们将个页切分为份，也即有个页目录，每个页目录下管理个页，也即有个pde（page directory entry）。假设pde也占4-byte内存，且根据20/80定律假设有80%的页处于空闲状态，那么二级页表只需要0.804mb！()
由此可见，多级页表能够有效降低页表的内存消耗。多级页表在实际运用中还是较为常见的，比如linux系统采用的就是4级页表的结构。
swap sapce: 磁盘交换区
到目前为止，我们都是假设物理内存足够大，可以容纳所有程序的虚拟内存空间。然而，这往往是不切实际的，以32-bit地址空间为例，一个程序的虚拟内存为4g，假设有100个程序，那么一共需要400g的物理内存（忽略共享部分）！另外，程序运行过程中，并不是一直都需要所有的页，很多时候只需要其中的一小部分。
因此，如果我们可以先把那些暂时用不到的页先存在磁盘上，等需要用到时再加载到内存上，那么就可以节省很多物理内存。磁盘中用来存放这些页的区域，被称作swap sapce，也即交换区。
图24
在这种机制之下，当程序访问某一个地址，而这个地址所在的页又不在内存上时，就会触发缺页（page fault）中断。就像tlb缓存不命中时会带来额外的开销一样，缺页也会导致内存的访问效率降低。因为在处理缺页中断时，os必须从磁盘交换区上把数据加载到内存上；而且当空闲内存不足时，os还必须将内存上的某些页换出到交换区中。这一进一出的磁盘io访问也直接导致缺页发生时，内存访问的效率下降许多。
因此，在空闲内存不足时，页的换出策略显得极为重要。如果把一个即将要被访问的页换出到交换区上，就会带来本可避免的无谓消耗。页的换出策略很多，常见的有fifo（先进先出）、random（随机）、lru（最近最少使用）、lfu（最近最不经常使用）等。在常见的工作负载下，fifo和random算法的效果较差，实际用的不多；lru和lfu算法都是建立在历史内存访问统计的基础上，因此表现较前两者好些，实际应用也多一些。目前很多主流的操作系统的页换出算法都是在lru或lfu的基础上进行优化改进的结果。
最后
本文主要介绍了os内存管理的一些基本原理，从独占式内存管理，到页式内存管理，这过程中经历了许多次优化。这其中的每一种优化手段，都朝着如下3个目标前进：
1、透明化（transparency）。内存管理的细节对程序不可见，换句话说，程序可以自认为独占整个内存空间。
2、效率（efficiency ）。地址转换和内存访问的效率要高，不能让程序运行太慢；空间利用效率也要高，不能占用太多空闲内存。
3、保护（protection）。保证os自身不受应用程序的影响；应用程序之间也不能相互影响。
当然，目前主流的操作系统（如linux、macos等）的内存管理机制要比本文介绍的原理复杂许多，但本质原理依然离不开本文所描述的几种基础的内存管理原理。
光通信市场迎来了一个令行业震惊的并购事件
鸿蒙2.0操作系统采用JavaScript作为开发语言 可看出JS生态圈未来形势很好
中控智慧科技射频卡考勤机M880介绍
关于华虹宏力对功率技术的投入分析
RolfPfeifer：机器人走向生活
探索OS的内存管理原理
携号转网将带给国内带来三大影响
树莓派5将于10月底推出，树莓派5功能介绍
未来已来，AI 如何颠覆传统营销服，这场大会为你揭秘！
线性霍尔传感器在磁悬浮产品上的应用
邓力荣获学术界的盛高荣誉：入选加拿大国家工程院院士
中芯国际Q3营收大涨，关键在于8nm甚至14nm等先进工艺
PLC梯形图怎么画 有哪些操作步骤
氧气传感器存储和使用寿命的经验总结
正弦波发电机工作原理及操作规范
格力拿出价格“杀手锏” 消费升级激发潜在空调需求
GSMA将取消举办原定于上海举行的2020 MWC
WINCC 时间同步按钮,脚本分析
为何1.6mm是PCB设计的黄金标准？
模板函数以及模板类的基本概念以及原理
内存作为计算机系统的组成部分，跟开发人员的日常开发活动有着密切的联系，我们平时遇到的segment fault、outofmemory、memory leak、gc等都与它有关。本文所说的内存，指的是计算机系统中的主存（main memory），它位于存储金字塔中cpu缓存和磁盘之间，是程序运行不可或缺的一部分。
图1
在计算机系统中，主存通常都是由操作系统（os）来管理，而内存管理的细则对开发者来说是无感的。对于一个普通的开发者，他只需懂得如何调用编程语言的接口来进行内存申请和释放，即可写出一个可用的应用程序。如果你使用的是带有垃圾回收机制的语言，如java和go，甚至都不用主动释放内存。但如果你想写出高效应用程序，熟悉os的内存管理原理就变得很有必要了。
下面，我们将从最简单的内存管理原理说起，带大家一起窥探os的内存管理机制，由此熟悉底层的内存管理机制，写出高效的应用程序。
独占式内存管理
早期的单任务系统中，同一时刻只能有一个应用程序独享所有的内存（除开os占用的内存），因此，内存管理可以很简单，只需在内存上划分两个区域：
图2
在多任务系统中，计算机系统已经可以做到多个任务并发运行。如果还是按照独占式的管理方式，那么每次任务切换时，都会涉及多次内存和磁盘之间的数据拷贝，效率极其低下：
图3
最直观的解决方法就是让所有程序的数据都常驻在内存中（假设内存足够大），这样就能避免数据拷贝了：
图4
但这样又会带来另一个问题，程序之间的内存地址空间是没有隔离的，也就是程序a可以修改程序b的内存数据。这样的一个重大的安全问题是用户所无法接受的，要解决该问题，就要借助虚拟化的力量了。
虚拟地址空间
为了实现程序间内存的隔离，os对物理内存做了一层虚拟化。os为每个程序都虚拟化出一段内存空间，这段虚拟内存空间会映射到一段物理内存上。但对程序自身而言，它只能看到自己的虚拟地址空间，也就有独占整个内存的错觉了。
图5
上图中，虚拟内存空间分成了三个区域，其中code区域存储的是程序代码的机器指令；heap区域存储程序运行过程中动态申请的内存；stack区域则是存储函数入参、局部变量、返回值等。heap和stack会在程序运行过程中不断增长，分别放置在虚拟内存空间的上方和下方，并往相反方向增长。
从虚拟地址空间到物理地址空间的映射，需要一个转换的过程，完成这个转换运算的部件就是mmu（memory management unit），也即内存管理单元，它位于cpu芯片之内。
要完成从虚拟地址到物理地址到转换，mmu需要base和bound两个寄存器。其中base寄存器用来存储程序在物理内存上的基地址，比如在图5中，程序a的基地址就是192kb；bound寄存器（有时候也叫limit寄存器）则保存虚拟地址空间的size，主要用来避免越界访问，比如图5中程序a的size值为64k。那么，基于这种方式的地址转换公式是这样的：
物理地址 = 虚拟地址 + 基地址
以图5中程序a的地址转换为例，当程序a尝试访问超过其bound范围的地址时，物理地址会转换失败：
图6
现在，我们再次仔细看下程序a的物理内存分布，如下图7所示，中间有很大的一段空闲内存是“已申请，未使用”的空闲状态。这也意味着即使这部分是空闲的，也无法再次分配给其他程序使用，这是一种巨大的空间浪费！为了解决这个内存利用率低下的问题，我们熟悉的段式内存管理出现了。
图7
段式内存管理
在上一节中，我们发现如果以程序为单位去做内存管理，会存在内存利用率不足的问题。为了解决该问题，段式内存管理被引入。段（segment）是逻辑上的概念，本质上是一块连续的、有一定大小限制的内存区域，前文中，我们一共提到过3个段：code、heap和stack。
段式内存管理以段为单位进行管理，它允许os将每个段灵活地放置在物理内存的空闲位置上，因此也避免了“已申请，未使用”的内存区域出现：
图8
地址转换
从上图8可知，段式内存管理中程序的物理内存空间可能不再连续了，因此为了实现从虚拟地址到物理地址到转换，mmu需要为每个段都提供一对base-bound寄存器，比如：
图9
给一个虚拟地址，mmu是如何知道该地址属于哪个段，从而根据对应的base-bound寄存器转换为对应的物理地址呢？
假设虚拟地址有16位，因为只有3个段，因此，我们可以使用虚拟地址的高2位来作为段标识，比如00表示code段，01表示heap段，11表示stack段。这样mmu就能根据虚拟地址来找到对应段的base-bound寄存器了：
图10
但这样还不是能够顺利的将虚拟地址转换为物理地址，我们忽略了重要的一点：heap段和stack段的增长方向是相反的，这也意味着两者的地址转换方式是不一样的。因此，我们还必须在虚拟地址中多使用一位来标识段的增长方向，比如0表示向上（低地址方向）增长，1表示向下（高地址方向）增长：
图11
下面，看一组段式内存管理地址转换的例子：
图12
那么，总结段式内存管理的地址转换算法如下：
// 获取当前虚拟地址属于哪个段segment = (virtualaddress & seg_mask) >> seg_shift// 得到段内偏移量offset = virtualaddress & offset_mask// 获得内存增长的方向growsdirection = virtualaddress & grows_direction_mask// 有效性校验if (offset >= bounds[segment]) raiseexception(protection_fault)else if (growsdirection == 0) { physaddr = base[segment] + offset } else { physaddr = base[segment] - offset }
内存共享和保护
段式内存管理还可以很方便地支持内存共享，从而达到节省内存的目的。比如，如果存在多个程序都是同一个可执行文件运行起来的，那么这些程序是可以共享code段的。为了实现这个功能，我们可以在虚拟地址上设置保护位，当保护位为只读时，表示该段可以共享。另外，如果程序修改了只读的段，则转换地址失败，因此也可以达到内存保护的目的。
图13
内存碎片
段式内存管理的最明显的缺点就是容易产生内存碎片，这是因为在系统上运行的程序的各个段的大小往往都不是固定的，而且段的分布也不是连续的。当系统的内存碎片很多时，内存的利用率也会急剧下降，对外表现就是虽然系统看起来还有很多内存，却无法再运行起一个程序。
解决内存碎片的方法之一是定时进行碎片整理：
图14
但是碎片整理的代价极大，一方面需要进行多次内存拷贝；另一方面，在拷贝过程中，正在运行的程序必须停止，这对于一些以人机交互任务为主的应用程序，将会极大影响用户体验。
另一个解决方法就是接下来要介绍的页式内存管理。
页式内存管理
页式内存管理的思路，是将虚拟内存和物理内存都划分为多个固定大小的区域，这些区域我们称之为页（page）。页是内存的最小分配单位，一个应用程序的虚拟页可以存放在任意一个空闲的物理页中。
物理内存中的页，我们通常称之为页帧（page frame）
图15
因为页的大小是固定的，而且作为最小的分配单位，这样就可以解决段式内存管理中内存碎片的问题了。
但页内仍然有可能存在内存碎片。
地址转换
页式内存管理使用页表（page table）来进行虚拟地址到物理地址到转换，地址转换的关键步骤如下：
1）根据虚拟页找到对应的物理页帧
每个虚拟页都有一个编号，叫做vpn（virtual page number）；相应的，每个物理页帧也有一个编号，叫做pfn（physical frame number）。页表存储的就是vpn到pfn的映射关系。
2）找到地址在物理页帧内的偏移（offset）
地址在物理页帧内的偏移与在虚拟页内的偏移保持一致。
我们可以将虚拟地址划分成两部分，分别存储vpn和offset，这样就能通过vpn找到pfn，从而得到pfn+offset的实际物理地址了。
比如，假设虚拟内存空间大小为64byte（6位地址），页的大小为16byte，那么整个虚拟内存空间一共有4个页。因此我们可以使用高2位来存储vpn，低4位存储offset：
图16
下面看一个转换例子，vpn（01）通过页表找到对应的pfn（111），虚拟地址和物理地址的页内偏移都是0100，那么虚拟地址010100对应的物理地址就是1110100了。
图17
页表和页表项
os为每个程序都分配了一个页表，存储在内存当中，页表里由多个页表项（pte，page table entry）组成。我们可以把页表看成是一个数组，数组的元素为pte：
图18
以x86系统下的pte组成为例，pte一共占32位，除了pfn之外，还有一些比较重要的信息，比如p（present）标识当前页是否位于内存上（或是磁盘上）；r/w（read/write）标识当前页是否允许读写（或是只读）；u/s（user/supervisor）标识当前页是否允许用户态访问；a（access）标识当前页是否被访问过，在判断当前页是否为热点数据、页换出时特别有用；d（dirty）标识当前页是否被修改过。
页式内存管理的缺点
地址转换效率低
根据前文介绍，我们可以总结页式内存管理机制下地址转换的算法如下：
// 从虚拟地址上得到vpnvpn = (virtualaddress & vpn_mask) >> shift// 找到vpn对应的pte的内存地址pteaddr = ptbr + (vpn * sizeof(pte))// 访问主存，获取ptepte = accessmemory(pteaddr)// 有效性校验if (pte.valid == false) raiseexception(invalid_access)else // 获取页内偏移量 offset = virtualaddress & offset_mask // 计算得出物理地址 physaddr = (pte.pfn <> shift(success, tlbentry) = tlb_lookup(vpn)if (success == true) // tlb hit if (canaccess(tlbentry.protectbits) == true) offset = virtualaddress & offset_mask physaddr = (tlbentry.pfn << shift) | offset else raiseexception(protection_fault)else // tlb miss pteaddr = ptbr + (vpn * sizeof(pte)) pte = accessmemory(pteaddr) if (pte.valid == false) raiseexception(segmentation_fault) else if (canaccess(pte.protectbits) == false) raiseexception(protection_fault) else tlb_insert(vpn, pte.pfn, pte.protectbits) retryinstruction()
从上述算法可以发现，在tlb缓存命中（tlb hit）时，能够避免直接访问主存，从而提升了地址转换的效率；但是在tlb缓存不命中（tlb miss）时，仍然需要访问一次主存，而且还要往tlb中插入从主存中查询到的pfn，效率变得更低了。因此，我们必须尽量避免tlb miss的出现。
更好地利用tlb
下面，我们通过一个数组遍历的例子来介绍如何更好地利用tlb。
假设我们要进行如下的一次数组遍历：
int sum = 0;for (i = 0; i < 10; i++) { sum += a[i]; }
数组的内存的分布如下：
图20
a[0]~a[2]位于page 5上，a[3]~a[6]位于page 6上，a[7]~a[8]位于page 7上。当我们首先访问a[0]时，由于page 5并未在tlb缓存里，所以会先出现一次tlb miss，接下来的a[1]和a[2]都是tlb hit；同理，访问a[3]和a[7]时都是tlb miss，a[4]~a[6]和a[8]~a[9]都是tlb hit。所以，整个数组遍历下来，tlb的缓存命中情况为：miss，hit，hit，miss，hit，hit，hit，miss，hit，hit，tlb缓存命中率为70%。我们发现，访问同一页上的数据tlb的缓存更易命中，这就是空间局部性的原理。
接下来，我们再次重新遍历一次数组，由于经过上一次之后page 5 ～ page 7的转换信息已经在tlb缓存里里，所以第二次遍历的tlb命中情况为：hit，hit，hit，hit，hit，hit，hit，hit，hit，hit，tlb缓存命中率为100%！这就是时间局部性的原理，短时间内访问同一内存数据也能够提升tlb缓存命中率。
tlb的上下文切换
因为tlb缓存的是当前正在运行程序的上下文信息，当出现程序切换时，tlb里面的上下文信息也必须更新，否则地址转换就会异常。解决方法主要有2种：
方法1：每次程序切换都清空tlb缓存（flush tlb），让程序在运行过程中重新建立缓存。
方法2：允许tlb缓存多个程序的上下文信息，并通过asid（address space identifier，地址空间标识符，可以理解为程序的pid）做区分。
方法1实现简单，但是每次程序切换都需要重新预热一遍缓存，效率较低，主流的做法是采用方法2。
需要注意的是tlb是嵌入到cpu芯片之内的，对于多核系统而言，如果程序在cpu之间来回切换，也是需要重新建立tlb缓存！因此，把一个程序绑定在一个固定的核上有助于提升性能。
让页表更小
大页内存
降低页表大小最简单的方法就是让页更大。前文的例子中，地址空间为32-bit，页的大小为4kb，pte的大小为4-byte，那么每个页表需要4mb的内存空间。现在，我们把页的大小增加到16kb，其他保持不变，那么每个页表只需要个pte，也即1mb内存，内存占用降低了4倍。
大页内存对tlb的使用也有优化效果，因tlb能够缓存的上下文数量是固定的，当页的数量更少时，上下文换出的频率会降低，tlb的缓存命中率也就增加了，从而让地址转换的效率更高。
段页式内存管理
根据前文所述，程序的地址空间中，堆与栈之间的空间很多时候都是处于未使用状态。对应到页表里，就是有很大一部分的pte是invalid状态。但因为页表要涵盖整个地址空间的范围，这部分invalid的pte只能留在页表中，从而造成了很大的空间浪费。
图21
前文中，我们通过段式内存管理解决了堆与栈之间内存空间的浪费问题。对应到页表中，我们也可以为页式内存管理引入段式管理的方式，也即段页式内存管理，解决页表空间浪费的问题。
具体的方法是，为程序的地址空间划分出多个段，比如code、heap、stack等。然后，在每个段内单独进行页式管理，也即为每个段引入一个页表：
图22
从上图可知，将页表分段之后，页表不再需要记录那些处于空闲状态的页的pte，从而节省了内存空间的消耗。
多级页表
降低页表大小另一个常见的方法就是多级页表（multi-level page table），多级页表的思路也是减少处于空闲状态的页的pte数量，但方法与段页式内存管理不同。如果说段页式内存管理可以看成是将页表分段，那么多级页表则可以看成是将页表分页。
具体的做法是将页表按照一定大小分成多个部分（页目录，page directory，pd），如果某个页目录下所有的页都是处于空闲状态，则无须为该页目录下的页申请pte。
以二级页表为例，下图对比了普通页表和多级页表的构成差异：
图23
下面，我们再对比一下普通页表和多级页表的空间消耗。还是假设地址空间为32-bit，页的大小为4kb，pte的大小为4-byte，一共有个页，那么普通页表需要4mb的内存空间。现在，我们将个页切分为份，也即有个页目录，每个页目录下管理个页，也即有个pde（page directory entry）。假设pde也占4-byte内存，且根据20/80定律假设有80%的页处于空闲状态，那么二级页表只需要0.804mb！()
由此可见，多级页表能够有效降低页表的内存消耗。多级页表在实际运用中还是较为常见的，比如linux系统采用的就是4级页表的结构。
swap sapce: 磁盘交换区
到目前为止，我们都是假设物理内存足够大，可以容纳所有程序的虚拟内存空间。然而，这往往是不切实际的，以32-bit地址空间为例，一个程序的虚拟内存为4g，假设有100个程序，那么一共需要400g的物理内存（忽略共享部分）！另外，程序运行过程中，并不是一直都需要所有的页，很多时候只需要其中的一小部分。
因此，如果我们可以先把那些暂时用不到的页先存在磁盘上，等需要用到时再加载到内存上，那么就可以节省很多物理内存。磁盘中用来存放这些页的区域，被称作swap sapce，也即交换区。
图24
在这种机制之下，当程序访问某一个地址，而这个地址所在的页又不在内存上时，就会触发缺页（page fault）中断。就像tlb缓存不命中时会带来额外的开销一样，缺页也会导致内存的访问效率降低。因为在处理缺页中断时，os必须从磁盘交换区上把数据加载到内存上；而且当空闲内存不足时，os还必须将内存上的某些页换出到交换区中。这一进一出的磁盘io访问也直接导致缺页发生时，内存访问的效率下降许多。
因此，在空闲内存不足时，页的换出策略显得极为重要。如果把一个即将要被访问的页换出到交换区上，就会带来本可避免的无谓消耗。页的换出策略很多，常见的有fifo（先进先出）、random（随机）、lru（最近最少使用）、lfu（最近最不经常使用）等。在常见的工作负载下，fifo和random算法的效果较差，实际用的不多；lru和lfu算法都是建立在历史内存访问统计的基础上，因此表现较前两者好些，实际应用也多一些。目前很多主流的操作系统的页换出算法都是在lru或lfu的基础上进行优化改进的结果。
最后
本文主要介绍了os内存管理的一些基本原理，从独占式内存管理，到页式内存管理，这过程中经历了许多次优化。这其中的每一种优化手段，都朝着如下3个目标前进：
1、透明化（transparency）。内存管理的细节对程序不可见，换句话说，程序可以自认为独占整个内存空间。
2、效率（efficiency ）。地址转换和内存访问的效率要高，不能让程序运行太慢；空间利用效率也要高，不能占用太多空闲内存。
3、保护（protection）。保证os自身不受应用程序的影响；应用程序之间也不能相互影响。
当然，目前主流的操作系统（如linux、macos等）的内存管理机制要比本文介绍的原理复杂许多，但本质原理依然离不开本文所描述的几种基础的内存管理原理。
光通信市场迎来了一个令行业震惊的并购事件
鸿蒙2.0操作系统采用JavaScript作为开发语言 可看出JS生态圈未来形势很好
中控智慧科技射频卡考勤机M880介绍
关于华虹宏力对功率技术的投入分析
RolfPfeifer：机器人走向生活
探索OS的内存管理原理
携号转网将带给国内带来三大影响
树莓派5将于10月底推出，树莓派5功能介绍
未来已来，AI 如何颠覆传统营销服，这场大会为你揭秘！
线性霍尔传感器在磁悬浮产品上的应用
邓力荣获学术界的盛高荣誉：入选加拿大国家工程院院士
中芯国际Q3营收大涨，关键在于8nm甚至14nm等先进工艺
PLC梯形图怎么画 有哪些操作步骤
氧气传感器存储和使用寿命的经验总结
正弦波发电机工作原理及操作规范
格力拿出价格“杀手锏” 消费升级激发潜在空调需求
GSMA将取消举办原定于上海举行的2020 MWC
WINCC 时间同步按钮,脚本分析
为何1.6mm是PCB设计的黄金标准？
模板函数以及模板类的基本概念以及原理