操作系统导论笔记——虚拟化

本文是笔者在阅读操作系统导论 时做的笔记。虽然这本书笔者曾反复阅读过多次，但每次阅读都有不少收获（主要是读后就忘）。笔者最近决定重读本书，并做一份笔记。本文的笔记不是对原书的摘抄或总结，而是笔者自身的理解和感悟，本文中部分疑惑都是从AI那里解答的，但整篇笔记依然是笔者用自己的写的，杜绝使用任何AI直接生成的东西。

操作系统导论 共分三个部分：虚拟化、并发和持久性，本篇笔记是第一部分：虚拟化

1. CPU虚拟化

操作系统实现cpu虚拟化主要依赖两个机制：

1. 对需要访问硬件的操作做限制，要求只能在内核态执行对硬件的访问，如读写文件，读写网卡等。这种受限访问就是我们说的系统调用，一般通过软中断实现。
2. 时分共享。每个进程仅能持续占用cpu一小段时间，不同的进程交替获得cpu执行，就好像每个进程都拥有cpu一样。时分共享实现的核心是时钟中断，硬件设备时钟会每隔一定时间给cpu发送硬中断，检测到硬中断的cpu会跳转到操作系统预置的中断处理程序中，此时操作系统重新获得cpu控制权，然后决定要继续运行当前进程，还是切换一个新的进程来运行。

系统调用保证了进程对硬件访问的保护以及提供了统一的抽象，而时分共享则保证了操作系统可以频繁的拿到cpu的控制权，并决定进程的调度，避免一些用户进程长时间占用cpu问题。

1.1 上下文切换

当前CPU运行进程A，此时发生硬中断，cpu会自动将进程A的关键寄存器，如PC、SP、Flag等信息压入进程A的内核栈上，cpu根据中断向量号找到中断向量表中对应的ISR程序入口，同时切换到内核模式。
内核会将当前进程A的所有通用寄存器的信息（如EAX，EBX等）继续保存到内核栈，这样就相当于内核栈当前栈顶保存了进程A用户态下的所有寄存器信息，记录了进程A在用户态执行的完整快照，这段将用户态进程A的上下文保存到内核栈栈顶的结构叫trapframe。

然后内核开始执行ISR代码，如果ISR代码判断无需进行上下文切换，则将之前保存在trapframe中的通用寄存器(EAX, EBX 等)从A的内核栈中弹出并恢复到CPU寄存器。然后执行iret，cpu识别到iret返回后，自动从当前sp指向的栈（此时是A的内核栈）的栈顶pop出User PC, User SP, Flags等（也即进程A在用户态的关键上下文）并加载到自己的寄存器中，此时切换到用户态，cpu开始继续执行进程A的代码。

如果判断需要进行上下文切换则执行swicth()程序，switch程序做两件事：

1. 当前正处在进程A的内核态下，cpu寄存器信息是进程A内核态执行的上下文，因此我们需要先将这些关键信息，如PC、SP等保存起来，使用context保存，context位于PCB或TCB等内存中。
2. 将要执行的进程B的context加载进CPU的寄存器，可以很显然的知道，进程B的context其实就是进程B在内核态执行的上下文，此时CPU的SP寄存器就是进程B的内核栈，而PC指向的也是上一次进程B在内核态执行中止的下一条指令地址。

此时CPU再取指执行，其实就是恢复之前进程B的内核态执行代码。因此switch函数返回后，其实整个执行已经被换为了进程B的内核态，进程B可能会在内核态再做一些收尾工作，将自己内核栈的trapframe中的通用寄存器(EAX, EBX 等)恢复到cpu，然后执行iret准备将控制权转移到用户态，也即进程B的用户态，CPU判断到iret指令后，就从SP指向的内核栈pop出栈顶的User PC, User SP, Flags等，因为当前sp指向的是进程B的内核栈，因此此时的trapFrame自然是用户态进程B的完整上下文。

上述过程便完成了一次完整的进程上下文切换。我们可以将整个流程梳理为：用户态进程A => 内核态进程A => 内核态进程B => 用户态进程B。其中用户态进程A的完整上下文保存在进程A的内核栈叫trapFrame，而内核态进程A的上下文保存在TCB或PCB中叫context。
如果以后某个时刻进程A被恢复运行，那恢复的点其实就是内核态进程A switch()函数切换完成的点，此时内核态进程A恢复运行，cpu的寄存器已经换为了内核态进程A的上下文（也即A的context），然后内核态进程A执行iret，cpu捕捉到从A的内核栈pop出trapFrame，正是我们之前保存的用户态进程A的上下文，此时用户态进程A就得以恢复运行。

上述流程也可以理解为：一旦进程由用户态切为内核态，操作系统都需要完整备份整个用户态的上下文信息，只不过这个上下文信息是通过两阶段实现的，首先是cpu先将用户态的关键寄存器如PC、SP、Flag等保存进内核栈，然后切换到内核态，内核程序将再用户态的剩余完整寄存器保存到内核态。同样的道理，上下文的恢复也是两阶段恢复，内核态先将其他寄存器信息恢复，再执行iret由cpu恢复PC、SP等关键寄存器。两阶段执行的思想有些像linux的ksoftirqd，CPU执行最紧要的部分，然后交由内核分步执行剩余的部分。在上下文保存的基础上，ISR如果判断需要进行上下文切换，则会备份当前内核态的上下文，然后切到别的内核进程恢复执行（将cpu寄存器恢复为别的进程的内核态上下文），这是因为我们当前要暂停的进程是在内核态暂停的，虽然我们之前备份了用户态的上下文，但还需要再备份下内核态的上下文，这样如果后续恢复运行，可以从内核态暂停的地方继续运行。

或者我们再精简些，将上述CPU与内核的两阶段上下文保存视为一体，那就是先进行用户态上下文的保存，如果需要进行上下文切换，那就再保存当前内核态的上下文，并加载要切换的进程的内核态上下文，随后已经切换的内核态进程再执行iret加载切换后的用户态上下文切到用户态执行切换后的用户进程，这也就是原书中的

运行进程的用户寄存器由硬件隐式保存，使用该进程的内核栈。当操作系统决定从 A 切换到 B。在这种情况下，内核寄存器被软件（即 OS）明确地保存， 但这次被存储在该进程的进程结构的内存中。后一个操作让系统从好像刚刚由 A 陷入内核， 变成好像刚刚由 B 陷入内核

2. 内存虚拟化

内存虚拟化主要解决了两个问题：

1. 隔离和保护，避免进程可以读到甚至篡改另外一些进程内存的情况
2. 抽象，让程序和编写程序的人觉得自己是在享有整个内存，使用的是一整个连续的地址空间，无需考虑不同物理内存碎片下放不同大小的数据问题。而操作系统为进程提供的内存抽象就叫地址空间。

地址空间的结构大致如下图：代码放在一开始的位置，大小可以提前确定，随后是堆的位置，堆从上往下增长（从低地址往高地址增长），而栈的起始地址在最后，从下往上增长（从高地址往低地址增长），堆和栈之间的是空闲的还未使用，可以被申请的地址。比如你的物理内存是4GB，那地址空间就可以看作是一个4GB大小的连续数组，程序会认为自己可以完整的利用这4GB内存，其中假设代码占用1KB，堆栈100MB，栈占100MB，那就是地址空间的地址[0,1kB)存储的是代码，[1KB,1kB+100MB)的地方存储的是堆，(4GB,4GB-100MB]存储的是栈。而[100MB+1KB,4GB-100MB)之间这段地址是还未被使用的地址，堆可以使用，栈也可以使用。

由于每个进程都有自己的地址空间，而地址空间的大小往往与物理内存的大小相等，因此每个进程都会认为自己享有整个物理内存。但实际我们知道物理内存只有一个，所有进程的数据都存在同一个物理内存中，因此我们就需要一套地址空间与实际物理内存地址的转换机制。

下面我们来讨论下现代CPU的内存管理单元（MMU）如何高效的将地址空间的虚拟地址转为物理地址的。

2.1 基址+界限

最初始的转换机制是假设地址空间占用没物理内存那么大，整个地址空间必须连续的放入物理内存中，且每个地址空间的大小完全一样。

如上图所示，一个16KB的地址空间被映射到一个64KB的物理内存中。这时候其实我们只需要两个信息：一个是基址，一个是界限。其中基址代表的是地址空间在物理空间存储的起始偏移量，在上图中是32KB，而界面用于限制程序对地址的访问不超过自己的地址空间，在上图中是16KB。因此物理地址 = 基址 + 地址空间的虚拟地址。比如访问地址空间地址128的代码段，实际读取的是32KB+128（32896） 物理地址位置的数据。也因此每个CPU都有两个硬件寄存器：基址寄存器和界限寄存器

由于上述假设足够的简单，因此操作系统对内存的管理也足够简单，身为操作系统必须清楚物理空间的哪块地址被占用哪块是空闲的，我们假设操作系统维护了一个空闲列表，而由于上例我们假设进程地址空间相同，因此物理空间就可以想象为组槽，槽的大小就是地址空间的大小，空闲列表里记录的也是槽的位置。当一个新的进程被创建就从空闲列表中找一个新槽，将该槽变为占用，并记录其基址和界面，同样进程终止也需要回收槽，将可用槽放回到空闲列表。

我们需要明确的是，CPU只有一组基址寄存器，其基址寄存器和界限都是针对当前CPU正在运行的进程的，每个进程的基址寄存器不同，因此在上下文切换的时候我们需要保存当前进程的基址寄存器和界面寄存器（一般放入进程结构或进程控制块中），然后再加载要切换的进程的基址界面到相应的寄存器中。

2.2 分段

上述地址空间映射存在一个比较明显的问题：由于大部分进程无法用满整个地址空间，存在大量的空闲区域，如果直接整体映射，会导致物理内存中也占用了大量未使用的内存。

如上图所示，地址空间4KB-14KB是未使用的空间，但其直接映射到物理空间的36KB-46KB导致物理内存中消耗了这段物理内存地址。解决这种问题的方案是采取分段。也即在 MMU 中引入不止 一个基址和界限寄存器对，而是给地址空间内的每个逻辑段（segment）一对。一个段只是 地址空间里的一个连续定长的区域，在典型的地址空间里有 3 个逻辑不同的段：代码、栈 和堆。分段的机制使得操作系统能够将不同的段放到不同的物理内存区域，从而避免了虚 拟地址空间中的未使用部分占用物理内存

比如按上图中我们分别为代码段、栈和堆分别单独记录他们的基址和界限，如下图所示：

这样每一个段属于连续的地址空间，可以独立映射到物理内存，而无需将整个地址空间整体映射。

按上图，比如要引用在代码段中的虚拟地址 100，MMU 将基址值加上偏移量（100）得到实际的物理地址：100 + 32KB = 32868。然后它会检查该地址是否在界限内（100 小于 2KB），发现是的，于是发起对物理地 址 32868 的引用。

再比如堆中的地址，虚拟地址 4200，因为堆从虚拟地址 4K（4096）开始，4200 的 偏移量实际上是 4200 减去 4096，即 104，然后用这个偏移量（104）加上基址寄存器中的 物理地址（34KB），得到真正的物理地址 34920。

因此对于分段的物理地址转换规则是：先判该虚拟地址在哪个段，然后得到当前虚拟地址在段中的偏移量，最后再加上该段的基址。

判断虚拟地址在哪个段可以用虚拟地址的头标识，比如我们有代码段、堆和栈三个段，那两位头标识就足以表示（00代码、10堆、11段）。假设对于一个14位的虚拟地址，我们采用头两位表示段标识，后12位表示段内偏移量。

2.3 分页

分段虽然解决了未使用地址空间占用物理内存问题，但带来了内存空间碎片化。因为每个段都是一个独立的连续地址，直接映射到物理空间，段的大小很可能不统一，各种各样的大小都有，物理内存会很快充满许多空闲空间的小洞，从而很难再分配给新的段，或扩大已有的段。

针对这个问题，解决方案是分页，所谓页可以理解为系统进行虚拟内存管理和分配物理内存的基本单位，也是虚拟地址空间和物理地址空间之间映射的基本单位

我们将一个进程的地址空间分割成固定大小的单元，每个单元称为一页，相应地，把物理内存看成是定长槽块的阵列，每个槽块的大小与页的大小一致，叫作页帧。因此每一个进程的地址空间被使用的页都会被映射到物理内存的页帧上，对于虚拟内存到物理内存的映射也就变为了地址空间页号到物理页帧的映射。而其中原本连续的虚拟地址空间就可以拆分为页，映射到不连续的物理页帧。

如上图，地址空间的第0页被映射到了物理空间的页帧3、地址空间第1页映射到了物理页帧7、地址空间第2页映射到了物理页帧5、地址空间第3页映射到了物理页帧2。

可以看到分页后，操作系统无需关心进程是如何使用地址空间，也无需关心堆和栈的增长方向的。由于最小单元是页，因此也避免了物理空间外部碎片化问题。

为了将一个进程虚拟的页号映射物理页帧，操作系统通常为每个进程保 存一个数据结构，称为页表（page table）。页表的主要作用是为地址空间的每个虚拟页面保 存地址转换（address translation），从而让我们知道每个页在物理内存中的位置。需要记住的是每个进程都有一个页表。

以一个64字节的虚拟地址空间为例，它的虚拟地址需要6位（2^6=64），我们假设页大小是16字节，那就可以用高2位表示页号，低4位表示页内偏移量，如下图，其中VPN代表虚拟页号。

因此假设我们访问地址空间21的地址，转为2进制如下：

虚拟页号就是1，页内偏移量是5。这时候我们只需要查找当前进程的页表，找到虚拟页1对应的物理页帧（PFN），假设是111，将虚拟页替换为物理页帧再加上页内偏移量就是实际的物理地址。

一个x86架构的页表条目大概如下：

它包含一个存在位（P），确定是否允 许写入该页面的读/写位（R/W） 确定用户模式进程是否可以访问该页面的用户/超级用户位 （U/S），有几位（PWT、PCD、PAT 和 G）确定硬件缓存如何为这些页面工作，一个访问位 （A）和一个脏位（D），最后是页帧号（PFN）本身。可以看到上述一个页表条目占用4字节。

对页表信息的存储我们可以采取简单线性表，也即数组，数组下标为虚拟页号，数组元素为页表条目，这样我们就能立即通过虚拟页号找到页表条目，也就能确定物理页帧了。

分页存在两个比较明显的问题：

1. 我们其实是对整个地址空间进行了统一分页，而我们知道每一页都需要一个页表条目来映射，假设对于32位操作系统下4GB的地址空间，页大小为4KB，那就代表一个地址空间有2^20^ 个页，也就是有2^20^ 个页表条目，4字节 * 2^20^ = 400MB，也即一个4GB地址空间的进程光维护地址转化的页表就需要400MB的空间，更别提现在64位操作系统了。
2. 由于页表条目那么大，它也没法装入cache或寄存器中，这就导致这种情况下的页表只能存入内存，而假设我们需要访问一段数据，则需要先将这段数据的虚拟地址转为物理地址，而转换需要页表，页表在内存中，这就需要一次内存访问，拿到物理地址后再去内存中取实际值，这又是一次内存访问，因此整个过程还是比较慢的。

针对第二种情况，解决方案是引入TLB，而TLB其实就是一个硬件，干的是缓存的是，缓存当前VPN对应的PFN是什么。我们知道所有缓存其实核心都是利用的是空间局部性和时间局部性。TLB为了速度因此做的比较小，一般TLB可能只有32条或64条，如果有未命中的TLB查询，则还是需要去内存的页表中查询，查询后将查询结果记录进TLB，如果TLB满了则需要替换策略，如LRU。另外，我们知道现代操作系统有大页缓存的功能，大页缓存其实就是把一页的大小由常见的4KB改为2MB、1GB等，大页缓存虽然可以减少页表条目，但其核心目的还是提供TLB的命中率。比如在一些数据库场景，数据存储的是一块比较大的连续区域，如果采用原来的页大小，那会存在较多的页表条目，这样也会造成TLB中条目不够，存在未命中的情况。但通过将每页变大，减少页表的条目，使得TLB所能表示的内存范围更大，则更容易命中，从而避免TLB未命名导致的低性能问题。

针对第一个问题，采取的可以是分段+分页，类似于之前的分段，每个段都单独有一个自己的页表，这样地址空间中间未使用的空洞部分就可以不被记录。

还可以是多级页表，多级页表的思路比较简单，就是对页表加索引，可以往上加多层索引，类似于跳表或B树。对于一整页的页表记录都是无效的，则直接不申请这一页。多级页表有一个核心思想是页表或页表的索引（目录）也是存储在页帧里。举例如下：

对于上述14位地址空间，页大小是64字节，一个页表条目占4字节。那页表条目就是2^8^个，那么一页可以装入64/4 = 16个页条目。因此按之前的分页，页条目就需要占2^8^/16 = 16页。但多级页表的好处是，对于一整页的页表记录都是无效的，则直接不分配这一页。我们知道地址空间中间有大量未使用的空洞部分，而这些就可以不分配页记录。

但我们其实又需要知道，这些页表所在的页哪些是没分配的，哪些是已分配的，因此这时候就需要在原页表上建索引，索引指向的是分配页表时所在的页。比如上例的页表如下：

上述2^8^页表条目，中间大部分是空缺的，我们就可以省略，由于一页可以装入16个页表条目，则页表条目在实际分配的如下：VPN 0-16页表条目分配在物理页100中，中间这些没分配，VPN 110-127分配在物理页101中。

那其实上述信息就是建立了一个页表的目录，我们叫做页目录：

其中页目录的条目数是页表理论可分配的页数量，上述为16条，页目录正好占1页。这样对于上述地址空间，我们就可以由1页页目录，2页页表来完成，不再是原来的16页页表。

我们以虚拟地址11 1111 1000 0000为了来说下多级页表如何转换为物理地址：

当我们寻址的时候，寄存器内会存储页目录地址，找到页目录。然后根据VPN高4位代表的是页目录内的偏移量找到对应的页表的页，高4位是1111，对应第15项，找到其页表在物理的101页。因此访问物理的101页，根据中间4位代表其在页表内的偏移量找到对应的页表条目，1110，对应倒数第二项，也即

因此实际PFN是55，再加上低6位页内偏移量000000，因此最终物理地址就是0011 0111 000000

上面我们只是两级页表，但很显然，可以构造更高，多级页表：

如上就是三级页表。

2.4 小知识补充

以前我一直以为32位操作系统的物理内存最大是4GB，但后来了解到是可以突破4GB的，如向下图的一个TLB条目：

VPN19位，页内偏移量12位，用户可用的总地址空间是2GB（还一半给了内核），但VPN转为PFN的时候，PFN是24位，那PFN+页内偏移地址 = 36位，可表示的物理地址空间就是64GB。

也就是说即使是32位操作系统，也可能超过4GB的物理内存。

首先32位操作系统提供的地址空间还是4GB，这是因为32位操作系统运行在32位cpu上，而32位cpu寄存器地址是32位的。寄存器的主要目的是存储地址，比如PC寄存器存的是当前进程下一条要执行指定的地址，这个地址是当前进程地址空间的地址，由于寄存器最大存32位，所能表示的地址范围最大就是4GB，因此32位操作系统下地址空间也是4GB，另外32位操作系统提供的指针大小也是32位，指针指向的也是地址空间的地址。

而对于物理地址线也是32条的cpu，其物理寻址能力也只能是4GB，因为cpu的物理地址线就像是cpu与外界通信的渠道，cpu想取值，需要将地址传给内存控制器，一个物理地址线能传递1bit的信息，因此32位物理地址线导致cpu访问物理内存的限制只能是4GB。

但后续部分32位cpu引入PAE（Physical Address Extension）支持更多的物理地址线，如36位物理地址线，那能访问的物理内存范围就变为了64GB。

但寄存器的大小还是32位，如果寄存器存的地址是地址空间地址，那32位是够用的，但如果存的是物理地址，如页表寄存器或页目录寄存器，那物理地址现在是64GB，32位寄存器不够用，操作系统的做法是对于一些需要直接存入寄存器的物理地址，他所在的位置不能超过前4GB地址，这样32位就够用了。

比如按上例，当前某个进程它的PC寄存器是0X12345678，那先取为VPN0X12345，根据寄存器存的页表地址（或页目录地址），查询VPN0X12345对应的PFN，而PFN是24位，假设是0X654321，则PFN+页内偏移量 = 0X654321678就是物理地址，这个物理地址就是36位的，CPU通过自己36位的物理地址线向内存控制器发送该地址，就可以读取64GB物理内存空间下的某一处的数据。

注：这里只是一个示例，实际引入PAE后页表条目可能也变为了8字节64位，不再是32位。