写点什么

探索 OS 的内存管理原理

作者:元闰子
  • 2022 年 1 月 09 日
  • 本文字数:7350 字

    阅读完需:约 24 分钟

前言

内存作为计算机系统的组成部分,跟开发人员的日常开发活动有着密切的联系,我们平时遇到的 Segment FaultOutOfMemoryMemory LeakGC 等都与它有关。本文所说的内存,指的是计算机系统中的主存(Main Memory),它位于存储金字塔中 CPU 缓存和磁盘之间,是程序运行不可或缺的一部分。



在计算机系统中,主存通常都是由操作系统(OS)来管理,而内存管理的细则对开发者来说是无感的。对于一个普通的开发者,他只需懂得如何调用编程语言的接口来进行内存申请和释放,即可写出一个可用的应用程序。如果你使用的是带有垃圾回收机制的语言,如 Java 和 Go,甚至都不用主动释放内存。但如果你想写出高效应用程序,熟悉 OS 的内存管理原理就变得很有必要了。


下面,我们将从最简单的内存管理原理说起,带大家一起窥探 OS 的内存管理机制,由此熟悉底层的内存管理机制,写出高效的应用程序。

独占式内存管理

早期的单任务系统中,同一时刻只能有一个应用程序独享所有的内存(除开 OS 占用的内存),因此,内存管理可以很简单,只需在内存上划分两个区域:



在多任务系统中,计算机系统已经可以做到多个任务并发运行。如果还是按照独占式的管理方式,那么每次任务切换时,都会涉及多次内存和磁盘之间的数据拷贝,效率极其低下:



最直观的解决方法就是让所有程序的数据都常驻在内存中(假设内存足够大),这样就能避免数据拷贝了:



但这样又会带来另一个问题,程序之间的内存地址空间是没有隔离的,也就是程序 A 可以修改程序 B 的内存数据。这样的一个重大的安全问题是用户所无法接受的,要解决该问题,就要借助虚拟化的力量了。

虚拟地址空间

为了实现程序间内存的隔离,OS 对物理内存做了一层虚拟化。OS 为每个程序都虚拟化出一段内存空间,这段虚拟内存空间会映射到一段物理内存上。但对程序自身而言,它只能看到自己的虚拟地址空间,也就有独占整个内存的错觉了。



上图中,虚拟内存空间分成了三个区域,其中 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 范围的地址时,物理地址会转换失败:



现在,我们再次仔细看下程序 A 的物理内存分布,如下图 7 所示,中间有很大的一段空闲内存是“已申请,未使用”的空闲状态。这也意味着即使这部分是空闲的,也无法再次分配给其他程序使用,这是一种巨大的空间浪费!为了解决这个内存利用率低下的问题,我们熟悉的段式内存管理出现了。


段式内存管理

在上一节中,我们发现如果以程序为单位去做内存管理,会存在内存利用率不足的问题。为了解决该问题,段式内存管理被引入。段(Segment)是逻辑上的概念,本质上是一块连续的、有一定大小限制的内存区域,前文中,我们一共提到过 3 个段:Code、Heap 和 Stack。


段式内存管理以段为单位进行管理,它允许 OS 将每个段灵活地放置在物理内存的空闲位置上,因此也避免了“已申请,未使用”的内存区域出现:


地址转换

从上图 8 可知,段式内存管理中程序的物理内存空间可能不再连续了,因此为了实现从虚拟地址到物理地址到转换,MMU 需要为每个段都提供一对 base-bound 寄存器,比如:



给一个虚拟地址,MMU 是如何知道该地址属于哪个段,从而根据对应的 base-bound 寄存器转换为对应的物理地址呢?


假设虚拟地址有 16 位,因为只有 3 个段,因此,我们可以使用虚拟地址的高 2 位来作为段标识,比如00表示 Code 段,01表示 Heap 段,11表示 Stack 段。这样 MMU 就能根据虚拟地址来找到对应段的 base-bound 寄存器了:



但这样还不是能够顺利的将虚拟地址转换为物理地址,我们忽略了重要的一点:Heap 段和 Stack 段的增长方向是相反的,这也意味着两者的地址转换方式是不一样的。因此,我们还必须在虚拟地址中多使用一位来标识段的增长方向,比如0表示向上(低地址方向)增长,1表示向下(高地址方向)增长:



下面,看一组段式内存管理地址转换的例子:



那么,总结段式内存管理的地址转换算法如下:


// 获取当前虚拟地址属于哪个段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 段的。为了实现这个功能,我们可以在虚拟地址上设置保护位,当保护位为只读时,表示该段可以共享。另外,如果程序修改了只读的段,则转换地址失败,因此也可以达到内存保护的目的。


内存碎片

段式内存管理的最明显的缺点就是容易产生内存碎片,这是因为在系统上运行的程序的各个段的大小往往都不是固定的,而且段的分布也不是连续的。当系统的内存碎片很多时,内存的利用率也会急剧下降,对外表现就是虽然系统看起来还有很多内存,却无法再运行起一个程序


解决内存碎片的方法之一是定时进行碎片整理



但是碎片整理的代价极大,一方面需要进行多次内存拷贝;另一方面,在拷贝过程中,正在运行的程序必须停止,这对于一些以人机交互任务为主的应用程序,将会极大影响用户体验。


另一个解决方法就是接下来要介绍的页式内存管理

页式内存管理

页式内存管理的思路,是将虚拟内存和物理内存都划分为多个固定大小的区域,这些区域我们称之为Page)。页是内存的最小分配单位,一个应用程序的虚拟页可以存放在任意一个空闲的物理页中。


物理内存中的页,我们通常称之为页帧(Page Frame)



因为页的大小是固定的,而且作为最小的分配单位,这样就可以解决段式内存管理中内存碎片的问题了


但页内仍然有可能存在内存碎片。

地址转换

页式内存管理使用页表Page Table)来进行虚拟地址到物理地址到转换,地址转换的关键步骤如下:


1)根据虚拟页找到对应的物理页帧


每个虚拟页都有一个编号,叫做 VPNVirtual Page Number);相应的,每个物理页帧也有一个编号,叫做 PFNPhysical Frame Number)。页表存储的就是 VPN 到 PFN 的映射关系。


2)找到地址在物理页帧内的偏移(Offset)


地址在物理页帧内的偏移与在虚拟页内的偏移保持一致。


我们可以将虚拟地址划分成两部分,分别存储 VPN 和 Offset,这样就能通过 VPN 找到 PFN,从而得到 PFN+Offset 的实际物理地址了。


比如,假设虚拟内存空间大小为 64Byte(6 位地址),页的大小为 16Byte,那么整个虚拟内存空间一共有 4 个页。因此我们可以使用高 2 位来存储 VPN,低 4 位存储 Offset:



下面看一个转换例子,VPN(01)通过页表找到对应的 PFN(111),虚拟地址和物理地址的页内偏移都是0100,那么虚拟地址010100对应的物理地址就是1110100了。


页表和页表项

OS 为每个程序都分配了一个页表,存储在内存当中,页表里由多个页表项PTE,Page Table Entry)组成。我们可以把页表看成是一个数组,数组的元素为 PTE:



以 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 << PFN_SHIFT) | offset
复制代码


我们发现,每次地址转换都会访问一次主存来获取页表,比段式内存管理(无主存访问)低效很多。

占用空间大

假设地址空间为 32-bit,页的大小固定为 4KB,那么整个地址空间一共有个页表,也即页表一共有个 PTE。现假设每个 PTE 大小为 4-byte,那么每个页表占用 4MB 的内存。如果整个系统中有 100 个程序在运行,那么光是页表就占用了 400MB 的内存,这同样是用户无法接受的。


接下来,我们将介绍如何去优化页式内存管理的这两个显著缺点。

让页式管理的地址转换更快

TLB:Translation-Lookaside Buffer

根据前文所述,页式内存管理地址转换因为多了一次主存访问,导致效率很低。如果能够避免或者减少对主存的访问,那么就能让地址转换更快了。


很多人应该都可以想到通过增加缓存的方式提升效率,比如为避免频繁查询磁盘,我们一般在内存中增加一层缓存来提升数据访问效率。那么为了提升访问主存中数据的效率,自然应该在离 CPU 更近的地方增加一层缓存。这个离 CPU 更近的地方,就是前文提到的位于 CPU 芯片之内的 MMU。而这个高速缓存,就是 TLBTranslation-Lookaside Buffer),它缓存了 VPN 到 PFN 到映射关系,类似于这样:



增加 TLB 之后,地址转换的算法如下:


VPN = (VirtualAddress & VPN_MASK) >> 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]; }
复制代码


数组的内存的分布如下:



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 缓存多个程序的上下文信息,并通过 ASIDaddress 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 只能留在页表中,从而造成了很大的空间浪费。



前文中,我们通过段式内存管理解决了堆与栈之间内存空间的浪费问题。对应到页表中,我们也可以为页式内存管理引入段式管理的方式,也即段页式内存管理,解决页表空间浪费的问题。


具体的方法是,为程序的地址空间划分出多个段,比如 Code、Heap、Stack 等。然后,在每个段内单独进行页式管理,也即为每个段引入一个页表:



从上图可知,将页表分段之后,页表不再需要记录那些处于空闲状态的页的 PTE,从而节省了内存空间的消耗。

多级页表

降低页表大小另一个常见的方法就是多级页表(Multi-level Page Table),多级页表的思路也是减少处于空闲状态的页的 PTE 数量,但方法与段页式内存管理不同。如果说段页式内存管理可以看成是将页表分段,那么多级页表则可以看成是将页表分页


具体的做法是将页表按照一定大小分成多个部分(页目录,Page Directory,PD),如果某个页目录下所有的页都是处于空闲状态,则无须为该页目录下的页申请 PTE。


以二级页表为例,下图对比了普通页表和多级页表的构成差异:



下面,我们再对比一下普通页表和多级页表的空间消耗。还是假设地址空间为 32-bit,页的大小为 4KB,PTE 的大小为 4-byte,一共有个页,那么普通页表需要 4MB 的内存空间。现在,我们将个页切分为份,也即有个页目录,每个页目录下管理个页,也即有PDE(Page Directory Entry)。假设 PDE 也占 4-byte 内存,且根据 20/80 定律假设有 80%的页处于空闲状态,那么二级页表只需要 0.804MB!(${+2^{20}4(1-80%)}$)


由此可见,多级页表能够有效降低页表的内存消耗。多级页表在实际运用中还是较为常见的,比如 Linux 系统采用的就是 4 级页表的结构。

Swap Sapce: 磁盘交换区

到目前为止,我们都是假设物理内存足够大,可以容纳所有程序的虚拟内存空间。然而,这往往是不切实际的,以 32-bit 地址空间为例,一个程序的虚拟内存为 4G,假设有 100 个程序,那么一共需要 400G 的物理内存(忽略共享部分)!另外,程序运行过程中,并不是一直都需要所有的页,很多时候只需要其中的一小部分。


因此,如果我们可以先把那些暂时用不到的页先存在磁盘上,等需要用到时再加载到内存上,那么就可以节省很多物理内存。磁盘中用来存放这些页的区域,被称作 Swap Sapce,也即交换区。



在这种机制之下,当程序访问某一个地址,而这个地址所在的页又不在内存上时,就会触发缺页(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 等)的内存管理机制要比本文介绍的原理复杂许多,但本质原理依然离不开本文所描述的几种基础的内存管理原理。


参考

1、Operating Systems: Three Easy Pieces, Remzi H Arpaci-Dusseau / Andrea C Arpaci-Dusseau

2、为什么 HugePages 可以提升数据库性能 , 面向信仰编程

3、探索CPU的调度原理, 元闰子的邀请

更多文章请关注微信公众号:元闰子的邀请

发布于: 刚刚阅读数: 2
用户头像

元闰子

关注

正心、修身 2021.05.03 加入

阅读、写作、生活 个人博客:https://yrunz.com 公众号【元闰子的邀请】:yuanrunzi

评论

发布
暂无评论
探索OS的内存管理原理