虚拟化内存

#计算机/四大件/操作系统/虚拟化

什么是虚拟化内存？

将物理内存的使用方式抽象化，使每个运行的程序都感觉自己拥有独立的连续内存空间

不同进程之间的地址空间互不影响

早期系统怎么分配地址？

早期的机器没有提供什么抽象给用户，而且一个物理内存中一次只能放入一个进程

![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=RtI0hcqP|780]]

[!question] 那我们怎么解决保护问题呢？我们不希望物理内存之间的进程可以相互读取数据 所以我们给出了物理内存的抽象，地址空间

地址转换

硬件对每次内存访问进行处理，将指令中的虚拟地址转换为数据实际存储的物理地址

[!hint] 地址空间 一个进程的地址空间包含这个程序的所有内存状态

![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=jzxFcBcn|510]]

作为用户级程序的程序员，可以看到的任何地址都是虚拟地址【如果你在程序中打印出一个地址，那就是一个虚拟的地址】； 只有操作系统，通过精妙的虚拟化内存技术，知道这些指令和数据所在的物理内存的位置；

假设：

• 用户的地址空间必须连续地放在物理内存中
• 假设地址空间不是很大【小于物理内存】
• 每个地址空间的大小都一样

动态重定位————地址转换的第一次革命

在程序运行时，可以改变程序在内存中的位置，所以叫动态重定位

动态重定位的过程

在编写和编译程序时假设地址空间从 0 开始 当程序执行时，操作系统会决定其在物理内存中的实际加载地址的初始位置，并将其记录在基址寄存器中。【能修改寄存器必须是在内核模式下】 在程序运行时，会通过 物理地址 = 虚拟地址 + 基址寄存器地址 来找到实际的物理地址。 界限寄存器会有两种方法来“保护”：

• 在求和前，检测被访问的虚拟地址是否超过虚拟空间总大小
• 在求和后，检测被访问的虚拟地址是否超过虚拟空间总大小 + 基址寄存器地址大小

一旦越界访问，CPU 就会触发异常，进程就可能终止

[!question] 为什么通过硬件，而不是软件？

• 不提供访问保护
• 一旦完成，很难进行二次定位【将内存空间重定位到其他位置】

[!bookinfo]

进程自己世界里的内存模样【以为整个物理内存都是它的】	进程实际在物理内存中的模样

程序计数器首先被设置为 128。当硬件需要获取这条指令时，它先将这个值加上基址寄存器中的 32KB【32768】，得到实际的物理地址 32896，然后硬件从这个物理地址获取指令。接下来，执行该指令时，进程发起从虚拟地址 15KB 的加载，处理器同样将虚拟地址加上基址寄存器中的地址，得到最终的物理地址 47KB，从而获得需要的数据。

整体过程

操作系统	硬件	CPU
启动内核模式，初始化陷阱表
	操作系统要求硬件记住：系统调用处理程序；时钟处理程序；非法内存处理程序；非常指令处理程序
开启时钟
	时钟开启，每 x 就中断一次
初始化进程表，初始化空闲列表
操作系统初始化结束，运行内核模式
启动进程 A 的准备工作：在进程表中分配条目；为进程分配内存；设置基址，界限寄存器；从陷阱返回【进入进程 A】
切换到用户模式	恢复进程 A 的寄存器；跳到 A 的程序计数器
		进程 A 运行，获取指令
	检查是否越界，转换虚拟地址
		执行指令
	是否需要显示加载/保存【可以重定义】
		……，A 继续执行指令
	发生时钟中断【切换到进程 B】
操作系统转回内核模式，执行中断处理程序
	跳到中断处理程序所在位置
调用 switch() 例程：将寄存器（A）保存到进程结构（A）；从进程结构（B）恢复寄存器（B）
从陷阱返回【进入进程 B】
	切换到用户模式，跳到 B 的程序计数器
		进程 B 运行
		进程 B 执行了错误的加载
转向内核模式
	跳到陷阱处理程序
决定终止进程 B；回收 B 的内存；移除 B 在进程表中的条目

动态重定位如何解决三大问题的？

	解释	解决方法
怎么欺骗进程？	不要让程序知道内存被虚拟化了，让它认为它拥有自己的私有物理内存	通过地址转换
怎么让效率更高？	不能让程序运行的更慢；也不能需要太多额外的内存来支持虚拟化	利用硬件
怎么保护进程？	让一个进程在运行时，只能访问它机子的地址空间里的内容	界限寄存器
### 优缺点

• 优点

解决了三大问题

• 缺点

效率低下【由于进程的栈区和堆区并不大，导致这块内存区域中大量的空间被浪费。这种浪费通常称为内部碎片（已经分配的内存单元内部有未使用的空间，造成了浪费）。所以，我们需要更复杂的机制，以便更好地利用物理内存，避免内部碎片。】

分段————地址转换的第二次革命

在这个例子里，有 3 个逻辑不同的段：代码、栈、堆。我们给每一段分配一对寄存器【基址寄存器 + 界限寄存器】。

如何知道什么时候要用哪一对寄存器？

• [x] 显式方法：

引入 段寄存器 ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=6Y6PgUpXxcHrbCvAhQEFU|600]] 段寄存器中的偏移量与基址寄存器相加，硬件就得到了最终的物理内存地址

• [x] 隐式方法：

硬件通过地址产生的方式来确定段【如果地址由程序计数器产生，那么地址在代码段；如果基于栈或基址指针，那么在栈段；其他地址则在堆段】

段错误：在支持分段的机器上发生了非法的内存访问

优缺点

• [x] 优点
• [ ] 可以代码共享，有利于节省内存：

在段寄存器中增加几个位，用于表示这段程序 只读，可执行，可读可写。之后不仅要检查虚拟地址是否越界，还要检查特定访问是否允许

• [ ] 地址转换的开销极小
• [x] 缺点
• [ ] 会产生 外部碎片

解决方案：

重新安排原有的段【操作系统先终止运行的进程，将它们的数据复制到连续的内存区域中去，改变它们的段寄存器中的值，指向新的物理地址，从而得到了足够大的连续空闲空间】 但是，内存紧凑成本很高，一般会占用大量的处理器时间

[[#空闲空间管理]]【最优匹配，最坏匹配，首次匹配，伙伴算法】 无论算法多么精妙，都无法完全消除外部碎片

永远不要分配不同大小的内存块

分页————地址转换的第三次革命

将进程的地址空间划分为固定大小的单元，每个单元称为一页

如何通过分页来实现虚拟化内存？

![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=YlbBv12U|700]] 我们首先要维护 页表【操作系统为每一个进程保存的一个数据结构（倒排页表不是）】，它的作用是记录每个虚拟页在物理内存中对应的位置【例如此处的页表有以下 4 个条目：(虚拟页 0→物理帧 3)、(VP 1→PF 7)、(VP 2→PF 5)、(VP 3→PF 2)】

虚拟地址=虚拟页面号+偏移量 ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=NyhdJGp4|700]]

页表的位置

![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=Q6jjbvYN|290]]

![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=5pvr5y2J|1000]]

优缺点

• [x] 优点
• [ ] 可以更高效地管理内存【页的大小是固定的】
• [ ] 减少空间碎片化的问题【因为每个页的大小是一致的，不会出现碎片化的情况】
• [ ] 为虚拟内存系统提供了更灵活的管理机制【我们不会假定堆/栈的增长方向，以及它们如何使用】
• [x] 缺点
• [ ] 维护页表需要较大的内存空间
• [ ] 利用页表进行地址转换开销很大【可能使进程减慢 2 倍甚至更多】

TLB 分页————地址转换的第四次革命

空闲空间管理

对于外部碎片问题的空闲空间管理。【例如，用户级的内存分配库【如 malloc() 和 free()】/操作系统用分段的方式实现虚拟化内存】

底层机制

分割与合并

![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=0liEF2j1KrpJoFFcZaXH8|791]]

如何追踪已分配的空间？

[!question] 我们在 free() 时只是给定了一个指针，并没有给定空间的大小，程序是如何知道要 free 多大空间呢？ 通过在内存中加入头块 ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=5gcdSplk|500]] 调用 free(ptr) 时，库会通过简单的指针运算得到头块的位置，获得头块指针，检查幻数是否符合预期，并计算要释放的空间大小【头块大小 + 分配给用户的空间大小】

如何维护一个简单的空闲列表？

![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=kp595uwB|900]]

堆的空间不足怎么办？

大多数传统的分配程序会先分配一个很小的堆，当空间耗尽时，再向操作系统申请更大的堆

基本策略

最优匹配

遍历整个空闲列表，找到所有符合条件的空闲块【大于等于请求的内存空间】，然后返回最小的一块

![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=jtoVfliw]]

• 优点
  • 能够最大程度地减少内部碎片的产生
• 缺点
  • 需要进行大量的比较操作，这可能导致较高的时间复杂度和性能开销
  • 会产生外部碎片

最差匹配

遍历整个空闲列表，找到所有符合条件的空闲块，然后返回最大的一块给用户，分割并满足用户需求后，剩下的再加入空闲列表

![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=24Oe6S2i]]

• 优点
  • 可以减少外部碎片【因为它保持了大块内存的连续性】
• 缺点
  • 容易产生内部碎片
  • 表现很差，开销很高

首次匹配

按顺序查找并将第一个满足大小的空闲块分配给用户，剩下的再加入空闲列表

![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=24Oe6S2i]]

• 优点
  • 简单快速【不需要遍历所有空闲块】
• 缺点
  • 会产生内部碎片【因为第一个满足大小的空闲块可能很大】
  • 会产生外部碎片【随着时间推移，经常发生分配和释放的内存块会留下许多零散的未分配内存空间】

下次匹配

第一个请求时，从起始位置开始查找第一个满足请求大小的空闲内存块； 对于后续的内存请求，算法会从上一次分配的位置继续向后搜索，找到满足需求的第一个空闲内存块，将其分配给用户； 如果在当前位置及其后续位置都没有足够大的空闲内存块，算法会循环回到起始位置重新开始搜索；

• 优点
  • 降低了外部碎片【因为他从上一次分配的位置开始搜索，尽量使用连续的内存块】
  • 快速分配【不用遍历所有空闲块】
• 缺点
  • 会产生内部碎片【可能就算从上一次的结束位置开始分配，空闲块也会很大】

改进内存分配的技术

分离空闲列表 + 厚块分配程序

如果某个应用程序经常申请一种（或几种）大小的内存空间，那就用一个独立的列表，只管理这样大小的对象，其他大小的内存请求都交给更通用的内存分配程序。

• 优点
  • 碎片将不再是问题
  • 这种特定大小的内存分配和释放会很快【没有复杂的查找过程】
  • 能够提高内存管理的效率【因为避免了初始化和销毁数据结构的开销（厚块分配程序尝试保持空闲对象在一个预初始化的状态。这意味着当这些对象被再次需要时，它们就已经处于可用状态，不需要经过初始化过程。可以减少初始化和销毁对象所需的时间和计算资源）】

二分伙伴分配程序

当有一个内存分配请求时，空闲空间被递归地一分为二，知道刚好可以满足请求的大小，再将请求的块返回给用户。 *** 当块被释放时，分配程序会检查“伙伴”块是否空闲。如果空闲，则合二为一，接着继续检查，直到合并整个内存区域 ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=Lyoa2p8V|320]]

• 优点
  • 让合并变得简单
• 缺点
  • 会有内部碎片【如上图】

内存操作 API

栈内存：申请和释放操作由编译器来隐式管理的 ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=Dm3sIqfT|450]] 堆内存：申请和释放操作都由程序员显式地完成【这也导致了很多缺陷】 ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=WQQCmjec]]

malloc()

传入要申请的堆内存的大小，失败就返回 NULL，成功就返回一个新申请空间的指针

double* d = (double*)malloc(sizeof(double));   //给双精度浮点数分配空间

free()

接收一个参数，释放堆内存

int* x = malloc(10*sizeof(int));
free(x);

calloc()

realloc()

brk()

sbrk()

mmap()

即使一个程序正确地运行过一次，也并不意味着它是正确的

进程退出时，是否要进行 free()？

系统存在两级内存管理。 第一级：操作系统在程序运行时将内存交给程序，并在进程结束时将其收回； 第二级：进程在堆或栈进行管理【在 malloc() 和 free() 调用时】

• [ ] 对于短时间运行的程序，即使泄露了内存【在第二级上没有 free()】，操作系统也会在程序结束时收回进程的所有内存
• [ ] 对于长期运行的程序【web 服务器，数据库管理系统】，泄露了内存，由于这些服务不会被关停，所以操作系统也不会回收，这时的内存泄露非常危险