内存管理

分层存储器体系

存储管理器：操作系中管理分层存储器体系的部分，用来记录哪些内存正在使用，哪些内存空闲

无存储器抽象

IBM 360系统的不用交换运行多个程序，其通过对地址进行一个静态映射，来达到一个逻辑地址与物理地址的分离

存储器抽象：地址空间

将物理地址直接暴露给进程，除非硬件能给予特殊的保护，否则进程可以任意对整个内存进行读写操作，不论有意无意，这是很危险的。另外一个问题就是这种抽象很难实现多道程序设计。

地址空间分为

• 虚拟地址空间
• 物理地址空间

概念

所谓地址空间，就是一系列地址集合（内存地址0...内存地址n），而独立的地址空间则代表每个进程都有属于自己的地址空间，类似于编程语言中的命名空间，不同的命名空间下，可以有同名的标志符

运行多个程序互相不影响，需要解决两问题：

• 保护不属于该进程的内存
• 重定位

内存重定位可以通过两个寄存器来实现：

• **基址寄存器**
• **界限寄存器**

相当于划定一个物理内存范围，进程的内存就分配在此区域之内，并且操作系统对内存地址做一次重定位

交换技术

由于程序运行符合局部性原理，CPU 访问内存会有很明显的重复访问的倾向性。那对于那些没有被经常使用到的内存，可以把它换出到磁盘

把一个进程从磁盘完整调入内存，使该进程运行一段时间，再将其的内存写回磁盘

内存紧缩：将小空闲区合并成一大块

当频繁进行内存交换，内存就会之间就会出现空洞，就需要使用内存紧缩，确保能有较大的一片连续内存区域给后续内存分配

空闲内存管理

操作系统需要管理分配的动态内存

使用位图的存储管理

通过一个bitmap的槽为0还是为1，代表某一块内存是否为空闲

当每一块内存单元越小，所需要的位图就需要越大，分配一整块大小为n连续的内存时，就需要搜索到连续出现了n个0的内存块

使用链表

通过将不连续的内存块用链表连接起来

使用链表的内存分配算法：

• 首次适配算法：找到一个比所需内存大或者刚好等于的内存块，将其分配给进程，余下的内存加会到链表
• 下次适配算法：首次适配每次都从头找，而下次适配则从上次找到的地方开始找
• 最佳适配算法：找出最接近所需的内存的一个内存块，需要搜索整个链表
• 最差适配算法：每次都选择最大的一块空间
• 快速适配算法：维护常用大小的内存空间，4k 16k 之类的，这样就能快速分配

虚拟内存

地址空间被分为多块，每块称作页 页被映射到物理内存，如果程序引用不存在的物理内存 由操作系统负责将缺失的部分装入物理内存

分页

当虚拟地址空间是比物理地址空间大时，当程序请求一个不存在物理地址的虚拟地址时，MMU通过缺页中断：当访问的页没有映射到物理内存中时，操作系统会将其他的页写到磁盘，将空出来的内存映射给当前的页，内存管理单元（MMU） 则是执行这个映射的服务，频繁的缺页中断会影响程序的执行效率

局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。

假设程序对内存的使用有局部性，即实际使用的内存只是程序名义上使用内存的一小部分，使用虚拟内存就能远远获得高于真实物理内存的容量

页表

一个页表项对应着一个页

页表项的结构：

• 保护位：允许什么类型的访问（读、写、执行）
• 修改位：判断页面是否被写过
• 访问位：判断页面是否被访问过
• 高速缓存禁止位

加速分页过程

分页系统需要考虑的2个问题：

• 虚拟地址映射到物理地址必须非常快
• 如果虚拟地址空间很大，则页表也会很大

TLB

转换检测缓冲区（TLB）：小型硬件设备，本质就是个缓存，其可以通过并行的方式对虚拟地址进行查找，如果在缓冲区中命中，就直接返回，否则再去查找页表，是一种多级缓存架构

缓存存放了之前已经进行过地址转换的查询结果。这样，当同样的虚拟地址需要进行地址转换的时候，可以直接在 TLB 里面查询结果，而不需要多次访问内存来完成一次转换

软件TLB管理

• 软失效：页表不在TLB里，但在内存中，需要少量的代价更新TLB
• 硬失效：页表也不在内存里，需要读取磁盘

地址转换

1. 确定页目录基址：每个 CPU 都有一个页目录基址寄存器，最高级页表的基地址就存在这个寄存器里。在 X86 上，这个寄存器是 CR3
2. 定位页目录项（PDE）：一个 32 位的虚拟地址可以拆成 10 位，10 位和 12 位三段，上一步找到的页目录表基址加上高 10 位的值乘以 4，就是页目录项的位置
3. 定位页表项（PTE）：用页表基址加上中间 10 位乘以 4 就可以得到页表项的地址
4. 确定真实的物理地址：上一步 CPU 已经找到页表项了，这里存储着物理页的物理地址，只要对物理页的物理地址加上最后 12 位，就是真正所需要访问的

对于 64 位的机器，只使用了 48 位的虚拟地址，所以它需要使用 4 级页表

针对大内存的页表

多级页表

进行两次查找

多级页表由于二级三级项在没被使用的时候可以不创建，且二级三级项甚至可以不存在内存中，所以可以减少内存的使用

倒排页表

需要使用TLB作为前置缓存，当TLB搜索不到，需要查找整个页表来找到所需的页表

为了避免对整个页表的搜索，可以使用对虚拟地址进行散列，使用散列值使用常数时间复杂度找到需要的页表

多进程虚拟内存

• 简化链接
• 简化加载
• 简化共享
• 简化内存分配

内存保护

页面置换算法

主要目的：挑选出最不常使用的页面，本质就是缓存的淘汰

最优页面置换算法（OPT, Optimal replacement algorithm）

无法确定哪个页面未来最少被使用 ，该算法只是一种理论算法，无法实现

最近未使用(NRU)页面置换算法

随机淘汰最近一个时钟周期没有访问、没有修改的最老的页面

先进先出页面置换算法（FIFO, First In First Out）

选择换出的页面是最老的页面

第二次机会页面置换算法

淘汰掉一个进入时间最长，且最久未被使用的页面

时钟页面置换算法

使用一个指针指向最老的页面，当需要淘汰页面时，如果这个页面R标志位为0，则淘汰的就是这个页面

如果这个页面被修改过，则将R标志位设置为0，然后向前移动指针，直到找到一个R标志位0的页面，淘汰它

淘汰完页面，新的页面插入到被淘汰的这个位置

最近最少使用(LRU)页面置换算法

• 这种方式在[缓存系统](/软件工程/架构/系统设计/缓存.html#更新策略)中经常被使用

在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的

另外一种实现方式则是对于每个页表项维护一个计数器，这个计数器会随着系统的运行时间增加而增加，要淘汰的时候就遍历整个链表，找到计数器最小的页表项

两种方式都可以配合哈希表可以实现 O(1) 时间复杂度的查找及删除，只是二者维护访问状态的方式不同，一种对应实现的数据结构就是LinkedHashMap

用软件模拟LRU

最不常使用（NFU） 会记住最近一段时间内各个时钟周期的访问情况

工作集页面置换算法

工作集：进程当前正在使用的页面集合 淘汰掉工作集中最少使用的页面

工作集时钟页面置换算法

分页系统中的设计问题

局部分配策略与全局分配策略

缺页中断率（PFF）：用来指出何时增加或减少分配给进程的页面，中断率越高的进程需要更多的页面，以避免内存颠簸

负载控制

当所有进程所需的内存总量超出了物理内存总量时，则需要交换一部分进程到磁盘中，避免大量的缺页中断带来的系统颠簸

页面大小

大页面带来的问题就是如果需要大量的小内存，则大页面里面就会需要内存碎片。

选择小页面的好处在于可以有效利用内存，但同时更小的页面意味着需要更多的页表。

现在常见的页面大小事4K和8K

分离的指令空间和数据空间

使用独立的指令地址空间跟数据地址空间，不仅有了更大的寻址范围，并且也有助于页面共享

共享页面

如果地址空间分离实现共享页面就会非常简单 通过写时复制

这需要对页表项做改造，需要记录该页面是否被共享，因为一个页面可能被多个进程使用，一个进程关闭了，不能随意将其的所有页面回收掉

共享库

共享库很适合使用数据共享，系统中其他程序可以复用共享库，共享库的数据只需在内存中加载一份

但需要注意的是共享库必须使用位置无关代码：只使用相对偏移量的代码，这样不同的进程调用时才不会出现问题

内存映射文件

把文件当做成一个内存中的大字符数组

清除策略

使用分页守护进程定时淘汰页面

虚拟内存接口

通过开放接口，使得不同进程之间可以拥有同一份内存，甚至不同计算机之前分布式共享内存

有关实现的问题

与分页有关的工作

• 创建一个新进程时：确定程序和数据大小，创建一个页表
• 进程执行时：重置MMU,刷新TLB，清除之前进程的痕迹
• 缺页中断时：确定是哪个虚拟地址发生了中断，读入所需页面，重新执行指令
• 进程退出时：释放页表、页面

指令备份

• 重启引起缺页中断的那条指令，这不是一件容易的事

由于指令是有状态，而且在执行缺页中断处理也会执行一些指令，这意味着需要记住指令的执行状态，一些CPU通过一个隐藏的寄存器来实现

锁定内存中的页面

• 锁住正在做IO操作的内存中的页面保证它不会被移出内存

后备存储

• _linux中的swap_

当需要将页面交换到磁盘时，静态的方式就是事前在交换区一一建立磁盘与页表的映射

动态的方式则是需要写到磁盘时，动态申请一块磁盘，需要在页表中记录磁盘的地址

整体架构设计

• MMU
• 缺页中断处理程序
• 页面调度程序

分段

如果使用一个一维的地址空间，将这个空间分为不同的区域，随着程序运行数据增加，区域之间就会发生重叠，表碰撞：动态增长的表会导致覆盖的问题

段式管理会按功能把内存空间分割成不同段，有代码段、数据段、只读数据段、堆栈段，等等，为不同的段赋予了不同的读写权限和特权级

不同的应用程序中，代码段的长度各不相同。如果以段为单位进行内存的分配和回收的话，数据结构非常难于设计，而且难免会造成各种内存空间的浪费

纯分段的实现

在 8086 实模式的实现下，8086 的寄存器位宽是 16 位，但地址总线却有 20 位，地址的编码可以从 20 位 0 到 20 位 1，这意味着 8086 的寻址空间是 2^20 = 1M

所以 8086 引入了段寄存器，物理地址 = 段寄存器 << 4 + 段内偏移。这种包含了段基址和段内偏移值的地址形式有一个专门的名字，叫做逻辑地址

在进行编程时，使用逻辑地址直接操作物理内存

段页式

程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能

分段和分页结合：MULTICS

段（段号，段内地址（页号，偏移地址））

分段和分页结合：Intel x86

LDT与GDT 线性地址（目录，页面，偏移量），从 32 位的 i386 开始，就支持段页结合的保护模式

i386 中多了一个叫全局描述符表（Global Descriptor Table, GDT）的结构。它本质上是一个数组，其中的每一项都是一个全局描述符，段选择子本质上就是这个数组的下标

分页与分段

内存布局

• 代码段保存的是程序的机器指令，这一段区域的内存往往是可读可执行，但不可写
• 数据段保存的是程序的静态变量和全局变量
• bss 段用于无初值的变量区域
• 堆是进程可以自由申请的空间
• 栈是函数执行时的活跃记录

现代应用程序中还会包含其他的一些内存区域：

• 存放加载的共享库的内存空间：如果一个进程依赖共享库，那对应的，该共享库的代码段、数据段、BSS 段也需要被加载到这个进程的地址空间中
• 共享内存段：可以通过系统调用映射一块匿名区域作为共享内存，用来进行进程间通信
• 内存映射文件：可以将磁盘的文件映射到内存中，用来进行文件编辑或者是类似共享内存的方式进行进程通信

32 位 Linux 系统下，从 0 地址开始的内存区域并不是直接就是代码段区域，而是一段不可访问的保留区

每次在进程向内核申请新的堆地址时候，其地址的值是在增大的。而进程申请新的栈地址时，其地址值是在减少的，堆的指针叫做“Program break”，栈的指针叫做“Stack pointer”

可以通过系统调用 sbrk 来调整堆的大小

void* sbrk(intptr_t incr);

另外一个申请堆内存的系统调用是 mmap，其除了可以分配内存之外，还能被用来作为共享映射区域，进行进程之间的通信

mmap

私有匿名映射

在文件映射区域分配一块内存，当访问到这块虚拟内存时，由于这块虚拟内存都没有映射到物理内存上，就会发生缺页中断，发生缺页中断时，内核会为其分配一个物理内存，将整个物理页全部初始化为 0，然后在页表里建立起虚拟地址到物理地址的映射关系

私有文件映射

每个被进程打开的文件，都会在进程的内部信息中维护一个 struct file 结构，对于同一个文件，整个内核中只会有一个 inode 结构，struct file 会与 inode 关联。inode 中会维护页号与物理内存，如果要写文件的时候，因为这一段内存区域的属性是私有的，所以内核就会做一次写时复制，为写文件的进程单独地创建一份副本

共享文件映射

在私有文件映射的基础上，对于可写的页面，在写的时候不进行复制就可以了

共享匿名映射

由内核模拟出来的，但是它也有自己的 inode 结构。这样一来，内核就能在创建共享匿名映射区域时，创建一个虚拟文件，并将这个文件与映射区域的 vma 关联起来

栈

在调用一个函数的时候，CPU 会在栈空间里开辟一小块区域，这个函数的局部变量都在这一小块区域里存活。当函数调用结束的时候，这一小块区域里的局部变量就会被回收，这块区域被称为栈帧

指令的角度看栈

int fac(int n) {    return n == 1 ? 1 : n * fac(n-1);}

  40052d:       55                      push   %rbp  40052e:       48 89 e5                mov    %rsp,%rbp  400531:       48 83 ec 10             sub    $0x10,%rsp  400535:       89 7d fc                mov    %edi,-0x4(%rbp)  400538:       83 7d fc 01             cmpl   $0x1,-0x4(%rbp)  40053c:       74 13                   je     400551 <fac+0x24>  40053e:       8b 45 fc                mov    -0x4(%rbp),%eax  400541:       83 e8 01                sub    $0x1,%eax  400544:       89 c7                   mov    %eax,%edi  400546:       e8 e2 ff ff ff          callq  40052d <fac>  40054b:       0f af 45 fc             imul   -0x4(%rbp),%eax  40054f:       eb 05                   jmp    400556 <fac+0x29>  400551:       b8 01 00 00 00          mov    $0x1,%eax  400556:       c9                      leaveq  400557:       c3                      retq

push %rbp 是将当前栈基址指针存到栈顶，mov %rsp,%rbp 是栈指针保存到栈基址寄存器，这两句的作用是把当前函数的栈帧创建在调用者的栈帧之下。保存调用者的栈基址是为了在 return 时可以恢复这个寄存器

接下来 sub $0x10,%rsp 是把栈向下增长 0x10，这是为了给局部变量预留空间。mov %edi,-0x4(%rbp) 把变量 n 从 edi 寄存器存到栈上，接下来将变量 n 与常量 0x1 进行比较，相等的话就跳到 0x400551 处，否则就是继续入栈执行

执行 callq 指令时，CPU 会把 rip 寄存器中的内容，也就是 call 的下一条指令的地址放到栈上，然后跳转到目标函数处执行。当目标函数执行完成后，会执行 ret 指令，这个指令会从栈上找到刚才存的那条指令，然后继续恢复执行

所以缓冲区溢出攻击就是通过篡改 rip 寄存器的内容，执行恶意代码

内存分配

• 显式分配：程序员手动释放内存
• 隐式分配：垃圾收集器回收

动态内存分配

由于程序运行时的未执行，所以需要动态的内存分配，但由于动态的分配，也会造成内存碎片的产生

void *malloc(size_t size);void free(void *p);

动态内存分配器的要求：

• 处理任意请求序列
• 立即响应请求
• 只使用堆
• 对齐块
• 不修改已分配的块

和目标：

• 最大化吞吐率
• 最大化内存利用率

内存分配器实现

• 如何记录空闲块
• 如何选择一个合适的空闲块放置一个新分配的块
• 如何处理空闲块被分配后剩余的部分
• 如何处理一个被释放的块

内存组织

• 空闲链表管理

放置已分配的块

• 首次适配（First Fit）：首次适配策略会搜索可用内存块列表，并选择第一个满足请求大小的空闲块。这种方法简单直接，但可能会导致产生较多的碎片，因为被分配的空闲块可能比请求的大小稍大，导致剩余部分形成碎片
• 下次适配（Next Fit）：下次适配策略类似于首次适配，但是从上一次分配结束的地方开始搜索空闲块。这种策略可以减少搜索的时间，但也可能导致碎片的产生
• 最佳适配（Best Fit）：最佳适配策略会搜索可用内存块列表，并选择最接近请求大小的空闲块。这种方法尽可能地减少了碎片的产生，但可能会导致内存分配器需要更长的时间来搜索合适的空闲块

分割空闲块

允许将一个大的空闲块分割成两个或多个较小的块，以满足不同大小的内存请求

获取额外的堆内存

在处理内存分配请求时，有时可能需要获取额外的堆内存以满足大内存块的需求

合并空闲块

在管理内存时，会经常遇到内存碎片化的问题。为了尽量减少内存碎片，动态内存分配器通常会实现合并空闲块的功能

假碎片是指由于多个相邻的空闲块之间被已分配的内存块所分割，导致不能被利用的空闲内存空间，通过合并空闲块，可以消除假碎片，提高内存利用率

块组织

空闲块管理

通常会使用一种或多种空闲链表数据结构来管理可用的空闲内存块

• 简单分离存储：简单分离存储是一种基本的空闲链表管理方法，它将不同大小的空闲内存块分别存储在不同的链表中，当进行内存分配时，分配器会首先查找合适大小的链表，并从中选择一个空闲块进行分配
• 分离适配：根据内存分配的历史数据动态地调整各个链表的大小范围。例如，如果某个链表中的空闲块被频繁地分配和释放，那么分配器可能会增加该链表的大小范围，以提高内存分配的效率
• 伙伴系统：通过将可用内存划分为一系列大小相等的内存块，当有内存分配请求时，它会尝试找到与请求大小相匹配的内存块。如果找到了合适大小的内存块，则将其分配给请求者；如果找不到，则会尝试将较大的内存块划分为更小的内存块，直到找到与请求大小相匹配的内存块为止。释放内存时，伙伴系统会尝试合并相邻的空闲块，以形成更大的空闲块

多线程下的分配

Tcmalloc 引入了线程本地缓存 (Thread Local Cache)，每个线程在分配内存的时候都先在自己的本地缓存中寻找，如果找到就结束，只有找不到的情况才会继续向全局管理器申请一块大的空闲区域，然后按照伙伴系统的方式继续添加到本地缓存中去

页中断

写保护中断

在 Linux 中，通过 fork 出来的进程，子进程会复制父进程的结构信息以及页表等，而 Linux 对于每张物理页都会记录引用该页的进程数，当父进程或子进程对内存进行写操作时，就会触发写保护中断，中断程序判断到物理页的引用数大于1，就需要为发生中断的进程再分配一个物理页面，把老的页面内容拷贝进这个新的物理页，最后把发生中断的虚拟地址映射到新的物理页，完成一次写时复制

缺页中断

1. 陷入内核，保存当前指令的一些状态信息
2. 尝试发现所需要的虚拟页面
3. 如果虚拟页面的地址非法或者受到保护，则结束掉进程，否则就置换页框或者淘汰页面来置换
4. 如果选择的页框脏了，则将该页写回磁盘，挂起该进程，进行上下文切换，直至磁盘传输结束，再将该进程切换回来
5. 否则操作系统从磁盘读取该页到内存
6. 恢复当前指令的状态信息，继续执行进程

内存虚拟化

虚拟机 Guest 启动的时候，宿主机 Host 肯定是运行在保护模式的，也就是分页机制已经开启。但是 Guest 仍然运行在实模式下，所以 Guest 会采用虚拟 8086 模式运行。在这种情况下，因为 Guest 是直接操作 GPA（Guest 物理地址） 的，所以 VMM 只需要做好 GPA 到 HPA（Host 物理地址） 的转换就行了

当 Guest 进入保护模式后，Guest 也会维护自己的页表，我这个页表叫做虚拟机页表，也就是 gPT。gPT 是不能将 Guest 的虚拟地址转换成真正的物理地址的，这就需要 VMM 来做一次处理，将 gPT 替换为自己精心准备过的页表，也就是影子页表，sPT

影子页表的维护和切换的效率十分低下，为此硬件厂商提供了 EPT，它可以协助 MMU 进行第二次页表转换。也就是说，MMU 负责将 GVA 转换为 GPA，然后 EPT 再将 GPA 转换为 HPA，来完成真正的内存页映射

系统程序常见的与内存有关的错误

• 间接引用坏指针
• 读未初始化的内存
• 栈缓冲区溢出
• 假设指针与指针所指向的对象大小相同
• 错位错误
• 引用了指针，而不是指针所指的对象
• 误解指针运算
• 引用不存在的变量
• 引用空闲堆块中的数据
• 内存泄漏