征服OS的第一座大山-虚拟化

type

status

date

slug

summary

概览

所谓虚拟化, 就是将硬件资源虚拟化为通用(泛用)且易于使用的虚拟形式.

完成虚拟化之后, 在用户视角机器由裸机(bare machine)变为虚拟机(virtual machine/abstract machine?), 通过虚拟机提供的API来调用虚拟机的功能.

在此视角下, 操作系统≈硬件资源管理器, 可感知形式接近于标准库.

虚拟化CPU——进程

概述

进程就是运行中的程序.

一个系统中可能有多个进程在”同时”运行, 而这实际上是由操作系统通过虚拟化CPU提供的假象.

“操作系统通过让一个进程只运行一个时间片, 然后切换到其他进程, 来提供存在多个虚拟CPU的假象, 是为时分共享CPU技术, 看起来就像多个进程在并行运行. ”

进程的组成/机器状态: 进程的内存(虚存), 寄存器, 持久存储设备(I/O设备)

进程创建

将程序的所有代码和静态数据(从持久化存储设备)(惰性)加载到进程的地址空间(内存中的某个页框)

惰性: 分页机制, 用时加载

在内存上分配堆和运行时栈(并初始化)以备用

其他初始化任务(如与I/O相关的文件描述符fd的初始化)

跳转到程序的main()例程, 启动程序

进程状态

运行态: 正在处理器上运行(在调度列表中并获得了调度)

就绪态: 可以运行, 准备运行(在调度列表中但未获得调度)

阻塞态/等待态: 不具备运行条件, 等待条件被满足(不在调度列表中)

运行态和就绪态之间可以相互切换(调度列表内轮流获得调度), 而等待态不能直接获得调度, 需要先进入列表(达到就绪态)

💡

“suspended” vs “stopped”

在操作系统中, suspended(挂起)状态和 stopped(停止)状态是两种不同的进程状态, 主要区别在于它们的原因和恢复方式.

1. Suspended(挂起)状态

描述:

进程被挂起, 通常是由于系统资源限制或人为操作, 使其暂停执行, 但仍然保留在内存中.

常见原因:

资源不足: 系统内存不足, 操作系统将某些进程挂起, 以腾出资源给更重要的进程.

用户操作: 用户主动挂起进程(如 Ctrl+Z 发送 SIGTSTP 信号).

作业调度: 某些任务调度策略可能会让进程进入挂起状态, 等待更合适的运行时机.

恢复方式:

操作系统恢复资源后, 可自动恢复进程.

用户可使用 fg 或 bg 命令恢复挂起的进程.

示例命令:

2. Stopped(停止)状态

描述:

进程被完全停止运行, 不会执行任何代码, 通常由特定信号(如 SIGSTOP)触发, 但进程的状态仍然被操作系统保留.

常见原因:

用户操作: 用户使用 Ctrl+Z 或 kill -STOP <pid> 停止进程.

调试: 调试器(如 gdb)可能会让进程进入 stopped 状态.

系统信号: 系统管理员或某些安全策略可能会暂停进程执行.

恢复方式:

需要显式恢复, 如 kill -CONT <pid>.

示例命令:

区别总结

状态	触发方式	进程是否仍在内存	是否可被自动恢复	主要用途
Suspended	资源不足、用户操作、作业调度	是	可能自动恢复	释放资源、等待运行
Stopped	信号(如 SIGSTOP)、调试工具	是	需手动恢复	暂停进程执行

简单来说:

Suspended 更偏向资源管理, 可能自动恢复.

Stopped 是完全暂停, 必须手动恢复.

进程存储形式(i.e.数据结构)

💡

在 struct proc 中的字段:

chan 是 “channel”(通道)的缩写. 它是一个指针, 用于标识进程正在等待的资源或事件. 常用于 sleep/wakeup 机制, 例如:

进程因为某个条件(如 I/O 完成、锁释放)尚未满足而进入 SLEEPING 状态；

此时, 操作系统会将 proc->chan 设置为一个用于识别该等待条件的地址(可以是任意唯一的指针值, 如锁对象的地址)；

其他进程或中断处理程序可以通过 wakeup(chan) 唤醒所有 proc->chan == chan 的进程.

例如:

假设有个锁 lock1, 进程 A 在获取失败后调用:

稍后某个释放该锁的线程会调用:

保存所有进程状态的数据结构 → 进程控制块PCB(Process Control Block)

进程API

fork(): 复制当前进程作为子进程, 从调用fork()的行开始执行. fork()在父进程中返回子进程的进程号, 在子进程中返回0, 可以在代码逻辑中用于区分父子进程.

exec() / execve(): 移交进程控制权到指定的程序, 覆盖当前进程控制流. 成功的exec()调用永远不会返回.

wait(): 阻塞父进程, 等待子进程返回, 用于同步父子进程的执行.

kill(): 发送信号要求杀死/睡眠进程.

ps/pstree: 查看当前系统进程

top: 查看占用资源最多的进程(自身开销很大)

底层机制: 受限直接执行

目标: 高性能地虚拟化CPU, 同时保留OS对CPU/关键行为/访问权限的控制权

方案: 受限(控制权)直接(高性能)执行

直接执行

这样没有多余步骤, 性能较好, 但是在程序执行期间OS失去对机器的控制, 且无法让程序停下来进行进程的上下文切换

受限

两个模式(权限等级): 用户模式/内核模式(特权模式)

用户模式下不能发出I/O请求, 不能执行受限指令; 内核模式下可以.

用户程序通过执行trap指令跳转(陷入)到内核并提升特权等级, 从而调用特权功能(系统调用). 完成后通过RET等指令返回到用户程序, 同时将特权等级降回用户模式.

trap期间用户程序(进程)的信息被压入内核栈保存, 返回时再出栈还原.

💡

系统调用的代码遵守系统调用的ABI, 将数据放入约定的位置之后执行trap指令跳转到系统调用例程. 返回时trap例程也需要将返回值放到周知的约定处.

C库中进行系统调用的部分是用汇编手工编码的!

用户程序不能拥有跳转到指定例程的权限(进程隔离), 跳转到正确的trap例程需要参考陷阱表(trap table). 陷阱表在机器启动时、特权模式下设置(systemd?).

进程间切换(上下文切换)

💡

问题: 单个CPU同时只能执行一个进程, 如何在运行其他进程的同时保持操作系统的运行以保证OS的控制?

策略:

信任策略(不安全): 用户程序主动进行系统调用(如yield), 定期放弃CPU, 将控制权交还到OS;

非协作方式(安全): 操作系统利用时钟中断定期中断用户程序, 抢占CPU控制权以进行控制.

💡

补充: 中断控制流程

机制(需要特权):

进入上下文切换的系统调用例程

通过系统调用, 保存当前执行的进程信息(如特定寄存器的值), 压入内核栈;

通过系统调用, 为即将执行的进程恢复/准备信息(如特定寄存器的值), 切换内核栈.

从系统调用(中断例程)返回, 则返回到切换后的进程开始执行, 上下文切换完毕,

上层策略: 进程调度

💡

调度的层次:

高级调度决定进程能否被创建

中级调度决定进程能否加入调度队列(不能则为挂起/阻塞)

低级调度决定接下来运行哪个进程

调度指标

周转时间(高效性) = 任务完成时刻 - 任务到达时刻

响应时间(交互性) = 任务开始运行时刻 - 任务到达时刻

调度的公平性 → 各进程受调度的机会均等

调度的优先级 → 根据重要性分配不同的调度机会

FIFO(First In, First Out)

先来先服务(First In, First Out), 按进程到达顺序依次调度, 简单但有护航效应(convoy effect), 短时任务排在长时任务之后等待很久.

SJF/SPN(Shortest Job First)

最短作业优先(Shortest Job First), 优先调度运行时间最短的进程, 可最小化平均等待时间, 但需准确预测运行时间(做不到), 且SJF为非抢占式调度, 在短时进程在长时进程之后到达的情况下护航效应依然存在(但不会饿死, 因为是非抢占式调度).

STCF/SRTF(Shortest Time to Completion First/Shortest Remaining Time First)

最短剩余时间优先(Shortest Time to Completion First), SJF 的抢占式版本, 当前执行的进程如果剩余时间更长会被新进程抢占. 问题在于长时进程会饿死(不断被短时进程插队).

轮转(Round-Robin, RR)

又称时间片轮转, 每个进程按固定时间片周期性轮流执行, 公平简单, 为简单的时分共享系统, 但会频繁产生切换开销, 损失性能. 所以需要权衡时间片的长度, 平衡切换开销与响应速度.

💡

考虑到Cache, TLB, 分支预测和其他片上硬件的状态, 切换开销是很高昂的.

时间片越长, 切换开销平摊下来越小;

时间片越短, 响应速度越快.

💡

考虑I/O: 当进程因等待I/O而阻塞时应该调入其他进程, 以免空转浪费CPU资源.

多级反馈队列(SJF和轮转的混合)

💡

问题: 无法预知每个进程的运行时长, 在保证一定周转时间的情况下降低响应时间

使用多个优先级队列, 根据进程行为动态评估/调整其优先级, 兼顾响应性和吞吐量, 能防止进程饿死.

规则:

若A的优先级>B的优先级, 则运行A不运行B(高级优先);

如果A的优先级=B的优先级, 则轮转运行A和B(同级轮转);

工作进入系统时放在最高优先级队列(接受评估);

一旦工作用完了在某一层的时间配额(时间片)就降低其优先级, 移入低一级队列(对其需要运行的市场的评估值增加, 根据SJF的思想应该靠边站)

💡

高优先级被评估为短工作, 低优先级被评估为长工作

经过一段时间S, 就将系统中所有工作重新加入最高优先级队列(防止长时进程饿死)

💡

S的值需要考量(性能与公平的平衡)

优化: 优先级/队列的个数, 每一层时间片的长度(分时优先级层次: 高优先级短, 低优先级长), 使用数学公式调整优先级, 将最高优先级留给操作系统, 让用户建议高优先级的任务, etc.

比例份额调度(彩票调度)

为进程分配“彩票”数量作为调度权重, 调度时随机抽奖, 概率性公平, 易实现优先级和资源控制.

💡

问题在于权重的合理分配.

“彩票转让” “彩票通胀”

💡

随机性: 没有边角情况, 不需要维护状态, 决策迅速.

当工作长度足够长, 时间片足够多时才能体现出公平性

步长调度(Stride Scheduling)

步长调度是一种确定性的比例份额调度算法, 用于实现类似“彩票调度”的公平资源分配, 但不依赖随机性.

每个进程分配一个步长(stride), 步长值与其份额(tickets, 即彩票张数)成反比.

步长 = 大常数 / tickets

每个进程还维护一个通行值(pass value) 初始为0.

每次调度选择通行值最小的进程运行, 并将该进程的通行值增加其步长.

示例:

进程	tickets	stride	pass
P1	100	100	0
P2	200	50	0

调度顺序将趋近于:

P2 → P1 → P2 → P2 → P1 → P2 → ...

P2 以较小步长获得更多执行机会, 实现了近似2:1的调度比例.

特点:

比随机的彩票调度更可控、更可预测;

适用于实时或对调度公平性有严格要求的场景;

实现简单, 仅需维护整数值.

💡

彩票调度需要再多个周期累积后在概率上实现分配的比例, 而步长调度算法可以做到每一个调度周期内严格符合该比例.

彩票调度的优势在于不需要维护全局状态pass, 当新进程加入时可以立即与其他进程同等调度, 而步长调度则不便设置新进程的pass(若设为0则该进程独占CPU, 不妥)

HRRF(Highest Response Ratio First, 最高响应比优先)

是一种非抢占式的作业调度算法, 用于提高系统对短作业的响应速度, 同时避免长期等待的作业饥饿现象.

基本思想: 每次选择“响应比最高”的作业进入运行状态.

💡

响应比(Response Ratio, R)计算公式:

R = (等待时间 + 服务时间) / 服务时间 = 1 + 等待时间 / 服务时间

每次调度时从就绪队列中选取响应比最大的作业运行, 响应比越高, 作业越优先被调度.

等待时间长的作业响应比会逐渐变高, 能够防止饥饿.

算法特点

特点	说明
非抢占式	一旦作业开始执行, 直到结束不被打断
动态优先级	响应比随时间变化, 优先级自动调整
平衡公平性和效率	兼顾短作业优先和防止长作业饥饿
实现复杂度中等	需要实时计算等待时间和响应比

举例

假设有三个作业到达时间均为 0, 它们的服务时间如下:

作业	服务时间	等待时间	响应比计算	响应比
A	3	0	(0+3)/3	1.00
B	6	0	(0+6)/6	1.00
C	1	0	(0+1)/1	1.00

初始时三个作业响应比一样, 任选一个. 假设先执行 C:

执行后, A 和 B 的等待时间分别为 1.

再次计算响应比:

作业	服务时间	等待时间	响应比
A	3	1	(1+3)/3 = 1.33
B	6	1	(1+6)/6 = 1.17

选择 A(响应比高), 以此类推.

适用场景: 批处理系统, 作业调度器, 希望兼顾响应速度和公平性的场合.

多处理器调度

在多个CPU间调度进程, 包括全局队列调度(简单但易冲突)和每核独立调度(减少开销但需负载均衡).

虚拟化内存——虚存

需求

💡

操作系统为每个进程提供一个假象: 它拥有大量的连续私有内存, 用户程序的每个地址都是虚拟的.

早期系统: 单道程序, 操作系统以一个库的形式存在, 没有复杂功能.

↓

多道程序系统: 多个进程共享机器, 由操作系统负责切换进程.

↓

时分共享系统: 注重交互性, 以各用户时间片轮转的形式保证系统对多个用户任务的及时响应.

💡

在进程切换时若将原进程的信息写入磁盘保存则效率太低, 只能让原进程信息留在内存中.

但是这样做引入了新的问题: 我们不希望一个进程能够修改另一个进程的数据, 故需要进程间的内存隔离机制. 所以我们引入了地址空间.

地址空间

物理内存的抽象, 是运行中的程序(进程)看到的内存. 一个进程的地址空间中的内容大致包括代码, 堆, 栈等.

虚拟内存的特性: 透明(进程不可察觉), 保护(进程隔离), 效率(保证性能).

内存管理API

库调用:

malloc(size_t size)

calloc(size_t size) → 分配并置零

realloc()

free(void *ptr)

底层系统调用:

brk(): 改变程序分断的位置, 即堆结束的位置. 需要一个参数即新分断的地址来判断是增大还是减小堆的大小.

sbrk(): 与brk大致相同, 参数是堆大小的增量.

mmap(): 在程序中创建一个匿名区域, 与swap空间相关联/

底层机制: (基于硬件的)地址转换

使用硬件对每次内存访问进行处理, 将指令中的虚拟地址转换为物理地址再执行. 硬件需要被操作系统正确设置.

基址+界限/动态重定位(原始思想)

💡

动态: 在运行时计算物理地址, 而不是在代码中静态写死物理地址.

每个CPU需要两个寄存器: 基址寄存器和界限寄存器, 指示进程地址空间在物理内存中的起始位置和大小. 这连个寄存器由操作系统设置.

虚拟地址和基址相加得到物理地址, 与界限比较检查是否越界访问非法内存区域.

该方案对硬件的要求:

问题: 空闲内存列表管理, 进程创建时分配内存, 进程终止时回收内存, 上下文切换时保存/恢复机制寄存器和界限寄存器(将其加入进程控制块PCB), 进程物理地址迁移(停止-复制-恢复), 异常处理机制(处理越界等情况)

运行实例:

分段式(进步)

💡

问题: 堆和栈之间有大片未分配空白内存, 浪费了内存空间(内部碎片). 剩余的物理内存可能无法提供大段连续的区域.

分段: 泛化的基址/界限. 为一个地址空间不止分配一对基址/界限寄存器, 而是给地址空间内的每个逻辑段一对基址/界限寄存器, 这样只占用了已使用的内存区域, 解放了堆栈之间的空白空间.

💡

段不等长, 会产生外部碎片.

访问超出段界限的非法地址则触发段错误(Segmentation Fault). 这个术语在当下不支持分段的机器上仍然保留, 表示访问了非法内存.

具体实现: 可以用虚拟地址的高位代表段号, 剩下的位表示段内偏移.

另外, 栈所在段由高地址向低地址反向增长, 需要专门记录.

进程之间可以共享内存段(需要有一定权限制约 → 段寄存器/段表中加入权限位/保护位)

对操作系统的要求: 上下文切换时保存/恢复段寄存器, 管理空闲空间(紧凑物理内存/空闲列表管理算法如伙伴算法)

空闲空间管理算法(缝缝补补)

头块(Header): 维护空闲列表(形式类似链表, 维护一个next指针)

基本策略:

最优匹配: 遍历整个空闲列表, 找到最小的能满足请求大小的块并分配(遍历开销大);

首次匹配: 遍历, 分配首个找到的满足要求大小的块(优点速度快, 缺点碎片多);

下次匹配: 多维护一个指针, 从上次遍历结束的位置开始遍历找到并分配首个满足要求的块, 遍历到末尾则回到开头, 将对空闲空间的查找操作扩散到整个列表中去, 避免频繁分割开头;

分离空闲列表: 使用专门的列表来管理常用大小的内存块(这种内存的分配和释放都很快), 其他照旧管理;

(二分)伙伴系统: 分配2的整数次幂大小的空间, 形成一个伙伴树. 若节点大小大于待分配内存的两倍则递归对半分割为两个兄弟节点, 若兄弟节点均空闲则向上递归合并为更大的内存块.

分页式(最终解)

不等长分段必然导致外部碎片 → 将内存划分为等长的单元(page, 页), 将物理内存看成是定长槽块的序列(page frame, 页框). 每一个页框恰好容纳一个页大小的数据.

💡

这样只会有内部碎片, 不会有外部碎片. 只要页大小合适则内部碎片就可以得到合理控制.

如此, 虚拟内存的高位即为虚拟页号, 剩下地位为页内偏移.

地址转换中, 使用(每个进程专有的)页表来存储(进程的)虚拟页号到物理页号的映射, 再将页内偏移与物理页号拼起来, 就得到物理地址.

页表实例:

虚拟页号 (VPN)	页框号 (PFN)	有效位 (Valid)	修改位 (Dirty)	访问位 (Accessed)	权限 (Permissions)
0	5	1	0	1	R/W
1	3	1	1	1	R
2	—	0	—	—	—
3	8	1	0	0	R/W

页表字段说明:

VPN: 虚拟页号(由虚拟地址计算得出)

PFN: 页框号(物理内存中对应的页帧)

有效位: 标记该页是否有效(即是否已映射)

修改位: 标记该页是否被写过

访问位: 标记该页是否被访问过(用于页面置换)

权限: 读写权限控制

💡

问题1: 地址转换机制使得每次内存引用都至少需要两次访存, 速度太慢;

问题2: 页表用于管理单个进程的地址转换, 若为每个进程都存储一个完整的页表则存储开销过大.

快表(TLB) → 解决问题1(速度太慢)

地址转换缓存, 大大提高效率, 使得虚拟内存成为可能.

快表TLB: 存储在快速的小存储器中, 存储部分页表项的信息. 若常用的页表项的内容绝大多数时候能在TLB中获取则能大大提升速度. 地址转换时先查TLB, 若TLB命中(hit)则直接返回, 若TLB缺失(miss)则再查页表并将缺失项载入TLB再重试.

💡

性能提升大小取决于TLB命中率/缺失率.

命中 → 大大缩短(1次TLB访问)

缺失 → 雪上加霜(1次TLB访问+1次页表访问+1次TLB访问)

TLB实例:

虚拟页号 (VPN)	页框号 (PFN)	有效位 (Valid)	权限 (Permissions)	最近使用时间 (LRU)
1	3	1	R	5
3	8	1	R/W	3
0	5	1	R/W	1

📌 TLB 字段说明:

通常是页表的缓存, 只缓存部分映射

LRU 表示最近使用时间或顺序, 用于替换策略

TLB缺失用硬件或软件处理均可, CISC倾向于设计一个指令来处理, RISC倾向于中断并调用trap例程来处理.

考虑到进程间切换, 需要清空TLB或加上地址空间标识符(ASID)来避免混淆不同进程的地址映射.

💡

若频繁切换进程则简单清空TLB会引起大量TLB缺失.

多级页表 → 解决问题2(页表太大)

引入页表的表 → (n级)页目录(Page Directory)

以页为单位来存储页表, 从而用树的形式组织页的存储. 优势在于紧凑且支持稀疏的地址空间.

若整页的页表/页目录都没有有效项, 则干脆不分配子表/子目录以节省空间.

💡

时间-空间折中: 多级页表带来了更小的内存开销, 但是TLB缺失时需要跨多级页目录查询, 时间开销更大.

控制流(考虑TLB):

涉及多级页表时的虚拟地址字段分割:

反向页表: 极端的空间节省, 将物理页框号映射到虚拟页号, 这样就只用维护一个页表(表项索引为物理页框号, 反向页表项与物理页框一一对应, 页表大小与物理地址空间而非虚拟地址空间成正比)

Swap机制

💡

将内存视为磁盘的缓存, 从而能够运行内存要求比内存更大的任务, 超越物理内存限制.

页踢出/调入物理内存的过程和机制对进程透明, 不可察觉.

swap空间: 是磁盘上的一块空间, 用于在内存不足时临时保存被换出的页面, 相当于虚拟内存的后备存储. 页面从物理内存换出时会被写入swap区域.

页表中, 每个页表项中设置一个装入位, 用于指示该页是否当前存在于物理内存中. 如果存在位为 0, 说明该页在swap空间中或根本尚未装入(还在磁盘中).

缺页异常(Page Fault): 当程序访问的页不在物理内存中(即装入位为0), 就会触发缺页异常. 操作系统会从swap空间(或其他来源如磁盘)将该页读入内存, 并更新页表, 然后重试.

页替换策略(见下方): 当在物理内存已满的情况下发生缺页异常时, 必须选择一个已加载的页将其从物理内存中踢出, 即触发“页替换策略”.

💡

不一定要等完全满了再踢出, 比如可以设置高低水位线: 页数达到高水位线就开始踢出, 直到降至低水位线.

可能的几种流程:

查TLB命中 → 返回

查TLB未命中 → 查页表装入 → 更新TLB → 重试 → 查TLB命中

查TLB未命中 → 查页表未装入 → 访问磁盘取回页 → 更新页表和TLB → 重试 → 查TLB命中

上层策略: 页替换策略

最优替换策略(OPT, 理想情况)

替换将来最久不会被访问的页面;

理论上页面置换最少, 但需要预知未来访问序列;

实际中不可实现, 用于评估其他算法性能.

先进先出(FIFO)

替换最早进入内存的页面;

简单但容易产生“Belady 异常”——增加内存反而页错误更多;

用队列实现, 每次插入新页时, 从队首换出.

💡

随机替换(避免边界)

随机选择一个页面替换;

简单易实现, 避免特定访问模式导致最坏情况;

平均性能不稳定, 完全看运气, 但在某些场景下表现良好.

最近最少用(LRU)

💡

指标: 频率, 近期性(时间局部性原则)

替换最长时间未被访问的页面;

近似模拟最优策略;

精确实现需要硬件支持(如访问时间戳), 开销较大.

实现: 维护一个队列, 将最近使用的条目提到首位, 需要踢出时淘汰末位条目.

💡

缺陷: 每次访问TLB都需要更新时间戳和列表, 且在页数较多时要找到绝对最旧的页开销较大.

近似LRU(找差不多最旧的页, 提高效率)

💡

只在处理缺页异常时才转动指针, 其余时间(页命中时)指针在原地不动, 只维护访问位的值.

常用Clock算法模拟LRU;

每个页加一个访问位(Reference Bit), 页被访问时将访问位设为1(说明最近被使用过);

要替换页时类似时钟指针循环扫描, 路过访问位为1的页时将其清零, 找到访问位为0的页(最近未用)就进行替换, 替换后指针指向下一页但是不清零;

每次指针扫描都从当前指向的页开始检查访问位.

💡

任何周期性清除使用位, 然后根据使用位判断是否替换的方法都可以实现近似LRU.

脏页+写回/写直达

脏页(Dirty Page): 在装入期间被修改过的页.

写回策略: 写时设置脏位, 脏页被换出前写回磁盘以维持数据一致. 提高效率但增加一致性管理复杂度;

写直达: 每次写都直接写入主存或磁盘, 不设置脏位, 开销较大, 适用于不频繁修改的数据.

💡

最简单有效的做法: 买更大的内存!