2、内存管理

点击阅读更多查看文章内容

虚拟内存

单片机的 CPU 是直接操作内存的「物理地址」。在这种情况下,要想在内存中同时运行两个程序是不可能的。如果第一个程序在 2000 的位置写入一个新的值,将会擦掉第二个程序存放在相同位置上的所有内容,所以同时运行两个程序是根本行不通的,这两个程序会立刻崩溃。

我们可以把进程所使用的地址「隔离」开来,即让操作系统为每个进程分配独立的一套「虚拟地址」,互不干涉。但是有个前提每个进程都不能访问物理地址,至于虚拟地址最终怎么落到物理内存里,对进程来说是透明的。

我们程序所使用的内存地址叫做虚拟内存地址(Virtual Memory Address)

实际存在硬件里面的空间地址叫物理内存地址(Physical Memory Address)

进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元(MMU)的映射关系,来转换变成物理地址,然后再通过物理地址访问内存,如下图所示:

img

操作系统是如何管理虚拟地址与物理地址之间的关系?主要有两种方式,分别是内存分段和内存分页

内存分段

程序是由若干个逻辑分段组成的,如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的,所以就用分段(Segmentation)的形式把这些段分离出来。

好处:

  • 内存布局更直观。
  • 方便数据共享
  • 段大小可按需扩展

分段机制下的虚拟地址由两部分组成,段选择因子段内偏移量

img
  • 段选择因子就保存在段寄存器里面。段选择因子里面最重要的是段号,用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级等。
  • 虚拟地址中的段内偏移量应该位于 0 和段界限之间,如果段内偏移量是合法的,就将段基地址加上段内偏移量得到物理内存地址。

段表:分段机制会把程序的虚拟地址分成 4 个段,每个段在段表中有一个项,在这一项找到段的基地址,再加上偏移量,于是就能找到物理内存中的地址,如下图:如果要访问段 3 中偏移量 500 的虚拟地址,我们可以计算出物理地址为,段 3 基地址 7000 + 偏移量 500 = 7500。

img

分段存在两个问题:

  • 第一个就是内存碎片的问题。
  • 第二个就是内存交换的效率低的问题。

我们来看看这样一个例子。假设有 1G 的物理内存,用户执行了多个程序,其中: 游戏占用了 512MB 内存 浏览器占用了 128MB 内存 音乐占用了 256 MB 内存。 这个时候,如果我们关闭了浏览器,则空闲内存还有 1024 - 512 - 256 = 256MB。 如果这个 256MB 不是连续的,被分成了两段 128 MB 内存,这就会导致没有空间再打开一个 200MB 的程序。

img

内存分段管理可以做到段根据实际需求分配内存,所以有多少需求就分配多大的段,所以不会出现内部内存碎片。 但是由于每个段的长度不固定,所以多个段未必能恰好使用所有的内存空间,会产生了多个不连续的小物理内存,导致新的程序无法被装载,所以会出现外部内存碎片的问题。

解决「外部内存碎片」的问题就是内存交换。 可以把音乐程序占用的那 256MB 内存写到硬盘上,然后再从硬盘上读回来到内存里。不过再读回的时候,我们不能装载回原来的位置,而是紧紧跟着那已经被占用了的 512MB 内存后面。这样就能空缺出连续的 256MB 空间,于是新的 200MB 程序就可以装载进来。 这个内存交换空间,在 Linux 系统里,也就是我们常看到的 Swap 空间,这块空间是从硬盘划分出来的,用于内存与硬盘的空间交换。

为什么效率低?

对于多进程的系统来说,用分段的方式,外部内存碎片是很容易产生的,产生了外部内存碎片,那不得不重新 Swap 内存区域,这个过程会产生性能瓶颈。 因为硬盘的访问速度要比内存慢太多了,每一次内存交换,我们都需要把一大段连续的内存数据写到硬盘上。 所以,如果内存交换的时候,交换的是一个占内存空间很大的程序,这样整个机器都会显得卡顿。 为了解决内存分段的「外部内存碎片和内存交换效率低」的问题,就出现了内存分页。


内存分页

分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间,我们叫页(Page)。在 Linux 下,每一页的大小为 4KB。

虚拟地址与物理地址之间通过页表来映射,如下图:

img

采用了分页,页与页之间是紧密排列的,所以不会有外部碎片。 但是,因为内存分页机制分配内存的最小单位是一页,即使程序不足一页大小,我们最少只能分配一个页,所以页内会出现内存浪费,所以针对内存分页机制会有内部内存碎片的现象。

如果内存空间不够,操作系统会把其他正在运行的进程中的「最近没被使用」的内存页面给释放掉,也就是暂时写在硬盘上,称为换出(Swap Out)。一旦需要的时候,再加载进来,称为换入(Swap In)。所以,一次性写入磁盘的也只有少数的一个页或者几个页,不会花太多时间,内存交换的效率就相对比较高。

更进一步地,分页的方式使得我们在加载程序的时候,不再需要一次性都把程序加载到物理内存中。我们完全可以在进行虚拟内存和物理内存的页之间的映射之后,并不真的把页加载到物理内存里,而是只有在程序运行中,需要用到对应虚拟内存页里面的指令和数据时,再加载到物理内存里面去。

在分页机制下,虚拟地址分为两部分,页号和页内偏移。页号作为页表的索引,页表包含物理页每页所在物理内存的基地址,这个基地址与页内偏移的组合就形成了物理内存地址,见下图。

img

多级页表

在 32 位的环境下,虚拟地址空间共有 4GB,假设一个页的大小是 4KB(2^12),那么就需要大约 100 万 (2^20) 个页,每个「页表项」需要 4 个字节大小来存储,那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。 这 4MB 大小的页表,看起来也不是很大。但是要知道每个进程都是有自己的虚拟地址空间的,也就说都有自己的页表。 那么,100 个进程的话,就需要 400MB 的内存来存储页表,这是非常大的内存了,更别说 64 位的环境了

要解决上面的问题,就需要采用一种叫作多级页表(Multi-Level Page Table)的解决方案。 在前面我们知道了,对于单页表的实现方式,在 32 位和页大小 4KB 的环境下,一个进程的页表需要装下 100 多万个「页表项」,并且每个页表项是占用 4 字节大小的,于是相当于每个页表需占用 4MB 大小的空间。 我们把这个 100 多万个「页表项」的单级页表再分页,将页表(一级页表)分为 1024 个页表(二级页表),每个表(二级页表)中包含 1024 个「页表项」,形成二级分页。如下图所示:

img

你可能会问,分了二级表,映射 4GB 地址空间就需要 4KB(一级页表)+ 4MB(二级页表)的内存,这样占用空间不是更大了吗?

每个进程都有 4GB 的虚拟地址空间,而显然对于大多数程序来说,其使用到的空间远未达到 4GB,因为会存在部分对应的页表项都是空的,根本没有分配,对于已分配的页表项,如果存在最近一定时间未访问的页表,在物理内存紧张的情况下,操作系统会将页面换出到硬盘,也就是说不会占用物理内存

如果使用了二级分页,一级页表就可以覆盖整个 4GB 虚拟地址空间,但如果某个一级页表的页表项没有被用到,也就不需要创建这个页表项对应的二级页表了,即可以在需要时才创建二级页表。做个简单的计算,假设只有 20% 的一级页表项被用到了,那么页表占用的内存空间就只有 4KB(一级页表) + 20% * 4MB(二级页表)= 0.804MB,这对比单级页表的 4MB 是不是一个巨大的节约?

我们把二级分页再推广到多级页表,就会发现页表占用的内存空间更少了,这一切都要归功于对局部性原理的充分应用。 对于 64 位的系统,两级分页肯定不够了,就变成了四级目录,分别是: 全局页目录项 PGD(Page Global Directory); 上层页目录项 PUD(Page Upper Directory); 中间页目录项 PMD(Page Middle Directory); 页表项 PTE(Page Table Entry);


TLB

基于程序访问的局部性,把最常访问的几个页表项存储到访问速度更快的硬件,于是计算机科学家们,就在 CPU 芯片中,加入了一个专门存放程序最常访问的页表项的 Cache,这个 Cache 就是 TLB(Translation Lookaside Buffer) ,通常称为页表缓存、转址旁路缓存、快表等。

img

在 CPU 芯片里面,封装了内存管理单元(Memory Management Unit)芯片,它用来完成地址转换和 TLB 的访问与交互。 有了 TLB 后,那么 CPU 在寻址时,会先查 TLB,如果没找到,才会继续查常规的页表。 TLB 的命中率其实是很高的,因为程序最常访问的页就那么几个


段页式内存管理

先将程序划分为多个有逻辑意义的段,但每个段不再直接分配连续物理内存; 接着进一步把每个段划分为多个页,物理内存根据页进行分配,物理页框无需连续,可以分散在内存的任何位置

  • 分段负责逻辑管理:保持模块化、共享和保护特性。
  • 分页负责物理分配:将每段划分为固定大小的页,消除外部碎片,提高内存利用率。

这样,地址结构就由段号、段内页号和页内位移三部分组成。 用于段页式地址变换的数据结构是每一个程序一张段表,每个段又建立一张页表,段表中的地址是页表的起始地址,而页表中的地址则为某页的物理页号,如图所示:

img

段页式地址变换中要得到物理地址须经过三次内存访问: 第一次访问段表,得到页表起始地址; 第二次访问页表,得到物理页号; 第三次将物理页号与页内位移组合,得到物理地址

方式 优点 缺点
纯分段 逻辑模块化,易于共享 外部碎片多,内存利用率低
纯分页 无外部碎片,内存利用率高 逻辑意义不直观,共享困难
段页式 结合两者优势 实现复杂,硬件开销大

传统LRU是如何管理数据的

当访问的页在内存里,就直接把该页对应的 LRU 链表节点移动到链表的头部。

当访问的页不在内存里,除了要把该页放入到 LRU 链表的头部,还要淘汰 LRU 链表末尾的页。

比如下图,假设 LRU 链表长度为 5,LRU 链表从左到右有编号为 1,2,3,4,5 的页。

img

如果访问了 3 号页,因为 3 号页已经在内存了,所以把 3 号页移动到链表头部即可,表示最近被访问了。

img

而如果接下来,访问了 8 号页,因为 8 号页不在内存里,且 LRU 链表长度为 5,所以必须要淘汰数据,以腾出内存空间来缓存 8 号页,于是就会淘汰末尾的 5 号页,然后再将 8 号页加入到头部。

img

传统的 LRU 算法并没有被 Linux 和 MySQL 使用,因为传统的 LRU 算法无法避免下面这两个问题: 预读失效导致缓存命中率下降; 缓存污染导致缓存命中率下降


预读失效

Linux 操作系统为基于 Page Cache 的读缓存机制提供预读机制

一个例子是: 应用程序只想读取磁盘上文件 A 的 offset 为 0-3KB 范围内的数据,由于磁盘的基本读写单位为 block(4KB),于是操作系统至少会读 0-4KB 的内容,这恰好可以在一个 page 中装下。

但是操作系统出于空间局部性原理(靠近当前被访问数据的数据,在未来很大概率会被访问到),会选择将磁盘块 offset [4KB,8KB)、[8KB,12KB) 以及 [12KB,16KB) 都加载到内存,于是额外在内存中申请了 3 个 page; 下图代表了操作系统的预读机制:

img

预读机制带来的好处就是减少了 磁盘 I/O 次数,提高系统磁盘 I/O 吞吐量。 MySQL Innodb 存储引擎的 Buffer Pool 也有类似的预读机制,MySQL 从磁盘加载页时,会提前把它相邻的页一并加载进来,目的是为了减少磁盘 IO。

如果这些被提前加载进来的页,并没有被访问,相当于这个预读工作是白做了,这个就是预读失效。 如果使用传统的 LRU 算法,就会把「预读页」放到 LRU 链表头部,而当内存空间不够的时候,还需要把末尾的页淘汰掉。 如果这些「预读页」如果一直不会被访问到,就会出现一个很奇怪的问题,不会被访问的预读页却占用了 LRU 链表前排的位置,而末尾淘汰的页,可能是热点数据,这样就大大降低了缓存命中率

预读失效解决方案

Linux 操作系统和 MySQL Innodb 通过改进传统 LRU 链表来避免预读失效带来的影响,具体的改进分别如下:

  • Linux 操作系统实现两个了 LRU 链表:活跃 LRU 链表(active_list)和非活跃 LRU 链表(inactive_list);
  • MySQL 的 Innodb 存储引擎是在一个 LRU 链表上划分来 2 个区域:young 区域 和 old 区域。

这两个改进方式,设计思想都是类似的,都是将数据分为了冷数据和热数据,然后分别进行 LRU 算法。不再像传统的 LRU 算法那样,所有数据都只用一个 LRU 算法管理。

inux 操作系统实现两个了 LRU 链表:活跃 LRU 链表(active_list)和非活跃 LRU 链表(inactive_list)。 active list 活跃内存页链表,这里存放的是最近被访问过(活跃)的内存页; inactive list 不活跃内存页链表,这里存放的是很少被访问(非活跃)的内存页; 有了这两个 LRU 链表后,预读页就只需要加入到 inactive list 区域的头部,当页被真正访问的时候,才将页插入 active list 的头部。如果预读的页一直没有被访问,就会从 inactive list 移除,这样就不会影响 active list 中的热点数据。(active中淘汰数据会加入inactive的head,再淘汰inactive的tail)

img

MySQL 的 Innodb 存储引擎是在一个 LRU 链表上划分来 2 个区域,young 区域 和 old 区域。 young 区域在 LRU 链表的前半部分,old 区域则是在后半部分,这两个区域都有各自的头和尾节点,如下图,young 区域与 old 区域在 LRU 链表中的占比关系并不是一比一的关系,而是 63:37(默认比例)的关系。 划分这两个区域后,预读的页就只需要加入到 old 区域的头部,当页被真正访问的时候,才将页插入 young 区域的头部。如果预读的页一直没有被访问,就会从 old 区域移除,这样就不会影响 young 区域中的热点数据。

img


缓存污染

当我们在批量读取数据的时候,由于数据被访问了一次,这些大量数据都会被加入到「活跃 LRU 链表」里,然后之前缓存在活跃 LRU 链表(或者 young 区域)里的热点数据全部都被淘汰了,如果这些大量的数据在很长一段时间都不会被访问的话,那么整个活跃 LRU 链表(或者 young 区域)就被污染了。

缓存污染带来的影响就是很致命的,等这些热数据又被再次访问的时候,由于缓存未命中,就会产生大量的磁盘 I/O,系统性能就会急剧下降。

缓存污染解决方案

前面的 LRU 算法只要数据被访问一次,就将数据加入活跃 LRU 链表(或者 young 区域),这种 LRU 算法进入活跃 LRU 链表的门槛太低了!正式因为门槛太低,才导致在发生缓存污染的时候,很容就将原本在活跃 LRU 链表里的热点数据淘汰了。 所以,只要我们提高进入到活跃 LRU 链表(或者 young 区域)的门槛,就能有效地保证活跃 LRU 链表(或者 young 区域)里的热点数据不会被轻易替换掉。

Linux 操作系统和 MySQL Innodb 存储引擎分别是这样提高门槛的:

  • Linux 操作系统:在内存页被访问第二次的时候,才将页从 inactive list 升级到 active list 里。
  • MySQL Innodb:在内存页被访问第二次的时候,并不会马上将该页从 old 区域升级到 young 区域,因为还要进行停留在 old 区域的时间判断:
    • 如果第二次的访问时间与第一次访问的时间在 1 秒内(默认值),那么该页就不会被从 old 区域升级到 young 区域;
    • 如果第二次的访问时间与第一次访问的时间超过 1 秒,那么该页就会从 old 区域升级到 young 区域;

提高了进入活跃 LRU 链表(或者 young 区域)的门槛后,就很好了避免缓存污染带来的影响。 在批量读取数据时候,如果这些大量数据只会被访问一次,那么它们就不会进入到活跃 LRU 链表(或者 young 区域),也就不会把热点数据淘汰,只会待在非活跃 LRU 链表(或者 old 区域)中,后续很快也会被淘汰。

作者

ShiHaonan

发布于

2025-03-03

更新于

2025-04-10

许可协议

评论