Operating Systems: Three Easy Pieces

[gaocegege]

来源：大学教辅书

[gaocegege]

这本书是 OS 绝佳的入门读物，尤其是前面两个 piece，CPU 和内存相关的章节。这本书的特色是会从每个特性最早的实现开始，循循善诱地逐步一点点的提出新的思路。这样的好处是读者会对现代的 OS 的各种特性有着更深入的认识，不只是知道特性是什么，还会知道为什么需要它，以及实现原理是怎样的。

[gaocegege]

CPU Virtualization

Process（进程）这一概念，最早是为了多任务提出的。不同的任务可以维护自己的 PC，堆，栈，代码段等。多任务的支持，可以通过切换线程来实现。但是，如果对每一个进程的运行不加限制，那么会遇到各种问题。

比如，进程如果需要申请更多的系统资源（如 CPU 时间，内存等），申请是否应该得到满足？

这一疑问很自然地让人想到，进程不能直接跑在硬件上，可以跑在操作系统里，通过引入 user mode，与 kernel mode 进行区分。进程跑在用户态，系统调用时进入内核态，在内核态才能执行特权操作。这也是内核态的由来。

还有问题，内核应该在什么时候切换进程？

协作式的方式可以通过等待系统调用实现。系统调用或者其他会陷入内核态的操作发生时，CPU 会交给内核，这时候可以切换。但是，如果一个进程不自觉，不会定期让出 CPU 给到内核，那进程就可以一直占用 CPU，一直执行。

于是，非协作的方式出现了，这就是大家熟悉的时钟中断。通过时钟中断和处理时钟中断的 handler，内核可以定期获得控制权。通过硬件的辅助，这一问题就解决了。在时钟中断发生时，被换出的进程 A 会由硬件把它的 user registers 保存在进程 A 的内核栈上。然后在内核态中，把保存的 regs 再保存在 A 的进程控制块（PCB）中，同时从 B 的 PCB 中恢复上下文，再切到 B 的内核栈，硬件恢复 B 的 regs，然后 jump 到 B 的 PC。

这里的设计跟最近 Go 1.14 的非协作异步抢占的 goroutine 调度也有关系，go 的 runtime scheduler 是在用户态的，没有硬件的辅助，没有时钟，因此只能采取信号这样的折衷办法解决问题。

接下来介绍的是调度算法的问题。这里就是 FIFO，SJF，STCF，RR，MLFQ，CFS 等算法的介绍了。总而言之就是在各种不同的 metrics（任务完成时间，turnaround time（不知道怎么翻译，任务完成时间减去任务到达时间），响应时间（等待被执行的时间））等等的 trade-off 了。

最后，在多 CPU 调度中，介绍了缓存一致性带来的问题。因为每个 CPU 都有自己的缓存，如果一个程序在 CPU 1 上读了内存地址 A 的值 d，然后更新了 CPU 1 中的缓存，从 d 改为了 d'，随后因为调度的关系，被重新分配到了 CPU 2 上执行，这时 CPU 1 的缓存还没有写回内存，就会导致程序读到了过期的值。

这一问题的解决办法还是硬件辅助，bus snooping（Bus 嗅探）。每个 cache 都 watch bus 上的内存更新，如果发现了就失效旧的缓存或者更新为新值。

为了解决缓存亲和性的问题（Cache affinity），又介绍了 SQMS，MQMS 等算法。最后比了一下 O(1)，CFS，BFS 等调度器的异同。同时强调没有银弹。

[gaocegege]

Memory Virtualization

在最早的分时复用的系统中，正在运行的进程是具有对内存的全部控制的。在进行进程切换时，OS 会把所有的 state 保存到硬盘中（包括所有的物理内存里的状态），然后切换别的进程的所有 state 进到寄存器和内存。这一方式在进程切换时成本太高。

这一成本主要在切换内存上，切换寄存器的值是非常快的，因此演化出了第二代实现。第二代实现中，多个进程可以共享内存，这样就避免了内存切换带来的开销，但是引入了新的问题：进程间内存的保护问题。

于是，地址空间的概念就出现了。就是我们常说的进程的堆栈结构。

OS 提供一层软件上的抽象，地址空间。进程看到的内存是抽象后的，连续的地址空间。这就引入了地址翻译的问题。

在最简单的实现中，地址翻译依赖两个寄存器，base 和 bounds 寄存器。物理地址 = 虚拟地址 + base。而 bounds 寄存器是用来做内存保护的，保证内存访问不会越界。而因为 base 和 bounds 两个寄存器在 CPU 上是专门做内存管理用的，因此也被称作 memory management unit（广为人知的 MMU）。

这种方式，存在一个问题，就是内存的浪费。一个进程内的堆栈可能用的特别少，堆栈之间的内存，其实也是在进程申请的 bounds 内的，这部分就被浪费了。为了解决这个问题，引入了 Segmentation 机制（段机制）。这是对之前说的 base bounds 机制的扩展：

我们为 code，heap，stack 分配了不同的内存段，每个段都有自己的 base 和 bounds（也就是图中的 size）。同时为了支持 heap stack 往不同方向扩展的特性，引入了一些额外的标志，来标志内存的伸展方向。通过更加细粒度的管理，缓解了内存浪费问题。