内存管理

分层存储器体系

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

无存储器抽象

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

只有一个进程下的内存组织方案

存储器抽象:地址空间

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

地址空间分为

概念

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

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

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

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

交换技术

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

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

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

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

空闲内存管理

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

使用位图的存储管理

202242523157

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

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

使用链表

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

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

虚拟内存

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

分页

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

MMU将虚拟地址转为物理地址

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

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

页表

一个页表项对应着一个页

页表项的结构:

加速分页过程

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

TLB

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

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

和 TLB 的访问和交互,由 MMU 控制

软件TLB管理

地址转换

CPU 要通过虚拟地址找到物理地址的几个步骤

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

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

当页面命中时

当缺页时

针对大内存的页表

多级页表

进行两次查找

多级页表

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

倒排页表

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

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

倒排页表

多进程虚拟内存

内存保护

页面置换算法

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

算法注释
最优算法不可实现,但可用作基准
NRU (最近未使用)算法LRU的很粗糙的近似
FIFO (先进先出)算法可能抛弃重要页面
第二次机会算法比FIFO有较大的改善
时钟算法现实的
LRU (最近最少使用)算法很优秀,但很难实现
NFU (最不经常使用)算法LRU的相对粗略的近似
老化算法非常近似LRU的有效算法
工作集算法实现起来开销很大
工作集时钟算法好的有效算法

最优页面置换算法(OPT, Optimal replacement algorithm)

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

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

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

先进先出页面置换算法(FIFO, First In First Out)

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

第二次机会页面置换算法

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

时钟页面置换算法

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

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

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

始终页面置换算法

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

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

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

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

用软件模拟LRU

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

工作集页面置换算法

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

工作集时钟页面置换算法

屏幕截图 2022-04-26 220905

分页系统中的设计问题

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

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

负载控制

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

页面大小

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

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

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

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

2022426231612

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

共享页面

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

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

共享库

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

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

内存映射文件

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

清除策略

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

虚拟内存接口

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

有关实现的问题

与分页有关的工作

指令备份

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

锁定内存中的页面

后备存储

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

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

整体架构设计

屏幕截图 2022-04-27 214029

分段

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

分段存储管理

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

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

纯分段的实现

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

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

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

段页式

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

分段和分页结合:MULTICS

段(段号,段内地址(页号,偏移地址))

屏幕截图 2022-04-27 215044

分段和分页结合:Intel x86

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

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

屏幕截图 2022-04-27 215221

分页与分段

对比分页分段
透明性对程序员透明需要程序员显示划分每个段
地址空间维度一维地址二维地址
大小可否改变页大小不可改变段大小可以动态改变
出现原因分页用来实现虚拟内存,以获得更大的地址空间分段是为了独立程序和数据并且有助于共享与保护

内存布局

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

IA-32 机器上的 Linux 进程内存布局

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);

动态内存分配器的要求:

和目标:

内存分配器实现

内存组织

空闲链表节点

空闲链表

放置已分配的块

分割空闲块

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

获取额外的堆内存

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

合并空闲块

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

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

块组织

带边界标记的合并

显式空闲链表

空闲块管理

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

多线程下的分配

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

页中断

异常来源中断服务程序要做的动作
页面未映射分配物理页面,并且在页表中设置好从虚拟地址到物理地址的映射
页面内容在磁盘中如果物理页面被交换出去,或者文件映射页表尚未加载,服务程序就会从磁盘中将数据按页读入内存
写只读页面如果是写时复制页,就复制一页,标记为可写分配给进程;如果是写异常,就触发SIGSEGV
没有访问权限给进程发送SIGSEGV信号

写保护中断

在 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,来完成真正的内存页映射

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