背景

虚拟内存将用户逻辑内存与物理内存分离。在物理内存有限的情况下,为程序提供了巨大的虚拟内存。

随着动态内存分配,栈向下生长,堆向上生长。但实际上中间空余的虚拟空间并不真实占用物理内存。另外,一个进程可以有多个线程,每个线程有自己的栈,但它们共享一个堆。

虚存的实现方式:

  • 按需分页
  • 按需分段

按需换页(Demand Paging)

延迟交换器(Lazy swapper):仅当需要页时把页换入内存。

页表项的有效位:指出页是否在内存。

若无效页被引用,则触发页故障(page fault)。

**EAT(有效访问时间)**计算:

页故障率 $p$

EAT = (1 – p) x memory access
+ p (page fault overhead
+ swap page out
+ swap page in
+ restart overhead
)

写时复制

Copy-on-Write (COW) 使得父子进程开始可以共享页,直到其中一方修改内存。

页面置换算法

页置换算法的思想在各种缓存系统中普遍应用。

我们可以将高速容器(如内存相对于磁盘)看作有限个槽。此数量即可用帧数

基本页置换

假设需要换入一个新帧

  • 有空闲帧,则使用它
  • 否则,选择一个牺牲帧(victim frame)
  • 将牺牲帧写入到低速容器,用新帧取代其原来位置

FIFO 页置换

用一个 FIFO 队列管理页。需要置换时,队头页被换出,新帧加入队尾。

缺点:Belady 异常

Belady 异常:使用 FIFO 算法时,会出现增加可用帧数,缺页率反而提高的现象。

image_up_163991123688e97212.jpg

个人认为,这种现象出现的本质原因是,死板 FIFO 导致将高频页面换出,从而命中率下降。使用栈可避免 Belady 异常。

最优页置换(OPT or MIN)

最优页置换置换距离最远的页。距离:下次执行所间隔的指令数。

缺点:无法预测未来。

最近最少使用页置换(LRU)

最近最少使用(Least Recently Used)。有多种实现方式。

基于计数器的实现:

  • 建立一个时钟机制 clock
  • 每个页表项关联一个时间域 refTime
  • 每次引用 clock++, refTime [i] = clock

于是我们相当于记录了各页的上次访问时间。从而可以换出最老的页。

基于栈的实现:

严格来说是一个双端队列。容量固定,每次引用,若已存在,则对应页上浮。栈底是 LRU 页。

近似 LRU

附加引用位算法

内存的每个页有一个 8 位字节,记录了 8 个周期内的使用情况。

1100 0100 表示之前 1,2,6 个周期使用过,之前 3,4,5,7,8 个周期没有使用过。

第 2~7 位叫做历史位。

二次机会算法

当历史位降低到 0 时,即 1 个引用位,相当于二次机会(second chance)算法。

当要选择一个页时,检查其引用位。如果其值为 0, 那么就直接置换该页。如果引用位为 1, 那么就给该页第二次机会,并选择下一个 FIFO 页。当一个页获得第二次机会时,其引用位清零,且其到达时间设为当前时间。

简言之,增加一次访问位清零的机会。即检查表头(最老)页面的 R 位,是 0 则置换,不是 0 则清零然后放到表尾。

SC 优化了 FIFO 的错误淘汰常用页的频率。

增强型二次机会算法(NRU 页置换)

最近未使用算法使用了 引用位修改位,根据这两个值分为 4 类,随机地从类编号最小队列中挑选一个页面淘汰之。

编号规则:访问 > 未访问,修改 > 未修改

第 0 类: 没有被访问, 没有被修改。

第 1 类: 没有被访问, 已被修改。

第 2 类: 已被访问, 没有被修改。

第 3 类: 已被访问, 已被修改。

CLOCK 页置换

优化了二次机会法经常操作链表的缺点。

所有的页面都保存在一个类似钟面的环形链表中, 一个表针指向最老的页面。

当发生缺页中断时, 算法首先检查表针指向的页面, 如果它的 R 位是 0 就淘汰该页面, 并把新的页面插入这个位置, 然后把表针前移一个位置; 如果 R 位是 1 就清除 R 位并把表针前移一个位置, 重复这个过程直到找到了一个 R 位为 0 的页面为止。

基于计数的页置换

最小使用频率页置换(LFU)

每次引用计数自增。

定期右移指数衰减。

最大使用频率页置换(MFU)

最差内存分配方案的泛化,认为如果页面的频率计数器很大,那么该页面已经拥有公平的内存份额,是时候轮到其他人了。

不幸的是,它不起作用。

内核内存分配

内核的内存来自于空闲内存池而非用户态进程的内存链表。原因:

  1. 内核需要为不同大小的数据结构分配内存。链表分配很容易产生碎片。
  2. 有的内核程序必须使用连续物理页。

伙伴分配器(Buddy 系统)

Buddy 系统分配物理上连续的段。使用 2^n 分配器。并且可以快速合并小段为大段(32 + 32 = 64)。 image_up_163991589435f1c3d6.jpg

当请求 11KB,则分配 16KB。也正因此,容易产生内存碎片。

SLAB 分配器

image_up_163991624281a94c7b.jpg

课本讲得不好。建议看 SLAB 分配器和 kmalloc - 魅族内核团队 (meizu.com)

slab 分配器 | FreeFlyingSheep 的小站

参考

进程结构和内存布局 - Kjing - 博客园 (cnblogs.com)

使用堆内存为什么比栈内存慢很多很多?申请堆内存需要经过操作系统吗? - V2EX