【操作系统导论】第一章-进程（楚门）的世界
引言
OS Three Easy Pieces（操作系统导论）将操作系统的核心概括为三个特性：虚拟化、并行、持久化。
本篇将从书中的虚拟化部分（除高级板块）中小结一下何为“虚拟化”，同时这个功能又给计算机带来了什么便利，姑且作为这段学习的反刍。
本书作为操作系统的教材相当优秀啊，不仅清晰地讲述知识（就是翻译比较……），还给你模拟器玩辅助理解。甚至还有实例拆析，要是能更悠闲地学就好力~
DD 比单推更“高级”？—— 进程是怎么运行的
如果你不太了解虚拟主播，请忽略标题（和下面一些意义不明的比喻）。总之本章将从进程的角度试着看看操作系统的工作。
众所周知，单推人往往能且只能打开一个虚拟主播的直播间开始发电，这样的行为与早期计算机的行动一致，即在相当的一段时间内只做一件事（包括等待这件事）。
现在引入一些术语，进程，一个创建出来为了完成一件事（这一件事的定义很宽泛）的结构。内含这件事的状态（1. 就绪，也就是未开始；2. 运行；3. 阻塞，等待其它事情的完成才会解除），这件事怎么做（代码和静态数据）等。
计算机运行过程中，肯定要处理很多进程。但毕竟就一个 CPU，怎么能够多开呢？要解决这个问题，就要说到CPU的虚拟化（后面还有其它部分的）。
“只要让每个进程都觉得它们各有一个专属 CPU 不就好了吗？”某个计算机学家说道。于是进程只管自己执行就好了，而操作系统要考虑的可就多了。
总之，为了保证进程不会对系统造成比较严重的损害，让进程的运行会有两个状态，用户态和系统态，其中区别是系统态能执行一些比较“危险”的行为，比如读写文件。当进程在用户态执行到调用系统行为的部分，或是出现错误，就切换上下文，即把当前进程的各种寄存器信息保存到某处（比如内核栈），然后让操作系统接管运行，直到完成任务后再恢复上下文。
上面的用户态与系统态的互相切换，涉及到了中断。对于进程在用户态来说，写入文件的部分可能就一小段代码，但就这部分会引起中断，也就是不继续执行剩下的程序，而是转去执行其它程序。当这个其它程序运行完，也会发生中断，这次中断则是断回上一次中断的后面继续执行（如果没有多次中断的话）。
想起了《计算机组成原理》 唐** 版在某个期末考试有可能会因为中断，让你默写长达十几条的中断顺序……
现在，我们了解了一个进程是怎么完成自己的事，那么操作系统面对这么多个进程，是怎么调度这些进程的呢？
时间管理大师 —— 操作系统是怎么“同时”应付多个进程的
对于一个海王而言，如何一个晚上约完七次也是一个相当有挑战性的任务，更何况操作系统。
不过，在介绍具体的方法之前，需要先引入两个衡量调度方法的指标。
- 周转时间，即一个进程从到达进程队列，到完成的时间；
- 响应时间，即一个进程从到达进程队列，到首次开始运行的时间；
- 很好理解，理想状况是每个对象都您尽早被翻到牌子以及完事（从安全的角度来考虑）
那么接下来迅速且简单的过一下普通的方法：FIFO，早进早出，非抢占式，两个指标都一般；SJF，短的优先，非抢占式，但长时任务可能饿死，而且如果短的晚到那么就和 FIFO 没啥差别；STCF，短剩余时间优先，抢占式，和 SJF 区别就是这个会运行一小会再选，所以不担心短任务晚到，但长的还是可能饿死；RR，就是轮转，公平地给予每个进程相同时间，响应时间短，但周转时间长。
要尽可能多处理任务，且时间长的任务也能处理到，这就需要多级反馈队列。顾名思义，按优先级设立多个进程队列，优先处理高优先级任务。但是，针对两个特殊情况会有特殊机制（下面仅为举例做法，核心是解决特殊情况的问题）。1. 对于很占用 CPU 的进程，这类进程既然占了这么多计算资源却还没做完，说明它还很可能会占很多时间，后面还有这么多任务，所以会降级；2. 对于没那么占用 CPU 的低优先级进程（排除因为太短直接完成的），既然会因为 IO 啥的空出时间，而且还会经常调用，那么就升级。
不过进程也有一些方法能糊弄操作系统，比如加入无意义的 IO，让 OS 误以为该程序其实占 CPU 没那么多来提升优先级，对于这种可以设置配额，一旦进程用完在这个队列的配额，无论是否有 IO，都会降级。
上面的多级反馈队列（MLFQ）简单的说就是让占 CPU 时间长的连续任务后做，同时让占 CPU 比较少的任务早完成。这种设计不需要考虑进程的具体设计，算得上是通用调度程序。
还有一种有趣的调度方式，叫做彩票调度，就是给不同进程划分不同数量的彩票，然后随机抽签，抽到谁执行谁。显然，彩票数越多的进程越容易被执行。但抽签终究有随机性，所以又有人想到，把彩票换成步长，让 CPU 优先执行总步数最少的程序，规定彩票越多，步长越短。这样即使小部分情况顺序偶有随机，总体上规定时间内的执行次数是确定的。但对于未知程序难以分配合适的彩票次数，所以这样的调度方式只能在相对容易的领域实现。
CPU 虚拟化小结
- 再简单一点地说，CPU 的虚拟化，就是解决了进程自身如何运行，以及系统如何调度多个进程。
进程（楚门）的世界 —— 内存虚拟化
首先，要知道，计算机的 IO 的效率并不高，所以要尽可能规避进程对硬盘的直接读写。
知道了上面这一点，就不难理解为什么不能让每个进程都独立访问硬盘了（而且早些时候，一台计算机很可能得同时应付多个用户）。那么该如何在减少 IO 的情况下，让进程对硬盘的操作都能正常运行呢？
宗旨就一条，让进程觉着自己拥有独立硬盘，从而避免多个进程对硬盘的混乱操作。要实现这一点，先后出现了分段和分页两种流派。
在具体讲述流派区别前，先简单说一下地址的映射，学过计组的都知道，有个间接寻址，*A + B，说人话就是访问 A 寄存器的内容，与 B 寄存器内容相加得出的地址。对于一个进程来说，它对硬盘的存储，都经过了这样的映射，比如存到 0 地址的数据，实际上映射去了 100（随便的例子，不必较真）。
映射间亦有高下，如何有条理的映射地址来方便管理呢？分段应运而生。所谓的段，就是一块能够连续增长的空间。经典分段将一个进程的地址空间分为代码，栈和堆。由于栈和堆的增长方向相反，这种方式能够比较有效地利用空间，而且对于同一段代码，可以有不同的堆栈代表不同的进程。
但是分段容易把内存变得碎片化，比如一块 4KB 的内存，若是从中间取走 2KB 又放回来，不做合并的情况下就变成了 1KB 2KB 1KB 的尴尬情形，而合并又是一件比较复杂的处理方式。有没有什么方法能够在避免内存难以利用的情况下，高效利用内存呢？这就是分页诞生的意义。
分页直接将内存碎片化为页，即一段固定长度的地址（只要自杀了就不会被人杀了的既视感）然后在每个进程设立一个叫做页表的数据结构，能够记录所有页的使用情况（是否被占用），页内又记载了虚拟地址到物理地址的映射，所以进程根据页表调用就好。（先不要疑惑为什么每个进程都要设立页表，毕竟最终设计就那样）
但是上面这种方式的效率其实很低，原因有二：1. 页表的设立还是没有解决进程的直接读写多的问题，而且更是严重了；2. 页比较小，所以页表往往很大，如果每个进程都要保存一份，光是创建进程所耗的内存就很大了。
对于问题一，通过快速地址转换（TLB），在内存设立一个部分，专门保存进程很有可能访问的页，如果进程需要访问硬盘，可以优先访问 TLB，命中的情况下就可以避免对硬盘的直接访问在硬盘数据需要更新时，TLB 还能一次性把更改的部分都写入，这样的方式比分开写入会高效不少。
那么 TLB 未命中的情况下则要考虑把硬盘的对应页替换进来，具体算法有 FIFO，LRU 等。主要讲下近似 LRU，会定期把所有的页的使用位置 0，使用则置 1，要替换页时就让某个指针线性去找第一个使用位为 0 的页换出来。还有不少方法，比如考虑脏页（修改过的页）的情况下，会优先替换走未修改的干净页，这样就不用把脏页覆写硬盘了（写时复制）。
问题二则可以通过多级页表解决，以两级为例，第一级页表记录的是小页表的情况，假设该进程被分配了两个小页表的内存，则进程除了第一级页表，还有对应的两个小页表，总共三个。
其实还有反向页表，这个页表是全局的，记录页与对应的使用进程，能节省空间，但是效率会降低。
从上面的脏页处理，可以知道计算机为了效率，有不少的“懒惰”操作，尽可能减少操作。这样的原理其实也应用在无限内存上，硬盘中设立了一个交换空间，里面放了进程正在占用但还没有使用的页，只有当进程确实需要才会把这些页放进内存。
