截图来自原书，贴出书的官方主页： 《Operating Systems: Three Easy Pieces》
(作者Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau)。感谢原作者这么好的书。
本篇笔记是书的第一部分(Virtualization)的上半部分，讲述了操作系统是怎么通过进程的抽象，将CPU计算资源进行虚拟化的。
第一节 进程的抽象
1.1. 策略和机制
Policy在mechanism（策略和机制）在操作系统中通常是分开设计的。比如如何切换上下文是一个low-level的mechanism，指底层的方法或者协议。当前时刻应该让哪个进程运行更好是一个high-level的policy的问题，指一些“智能”的调度。
1.2. 虚拟化和OS
OS本身就可以看做是“虚拟机”(virtual machine)。系统通过在可以被接受的合理开销（时间、空间）范围内，将计算机CPU、内存、存储等资源进行虚拟化（抽象），目的是为了用户的方便使用。
CPU虚拟化 主要体现在将任务抽象为 进程(process) ，将资源按进程隔离，然后多个进程轮转使用计算资源； 内存虚拟化 主要体现在 虚拟地址空间(virtual address space 或 adress space) ；而对于持久化的 存储 ，OS让文件共享，没有那么多私有隔离，OS假定用户会用文件来共享数据。 (？？？？)
第二节 进程API
2.1. fork和exec
exec()函数组和fork()的区别是：fork()复制当前进程为一个子进程执行，exec()会执行一个新的程序；exec()执行以后就再也不会返回。
2.2. shell和stdout redirect
例如shell就是一个普通的用户程序，利用了fork和exec的组合。给出一个提示符，你输入可执行程序时，会先fork()，然后在fork出的子进程中exec()这个命令，然后调用wait()来结束。这种fork和exec的组合使用，可以在让shell在fork后运行一些其他代码：fork后的子进程可以redirect操作再exec；fork后的父进程可以执行wait操作在exec结束后再显示提示符prompt。
stdout redirect的原理很简单，stdout一般的fd都是0，在fork后的子进程中close掉stdout，然后打开要redirect到的文件，这个文件就会获得为0的fd，这时执行新命令的exec，则会把这个为0的文件看做stdout进行输出，程序清单如下图：
2.3. 其他
kill()可以向进程发送信号，让程序sleep, die。
第三节 机制：有限的直接执行(Limited Direct Excution)
为了实现多个程序在同一个机器上执行，即CPU时间被多个进程共享，需要一种称为Limited Direct Excution(LDE)的机制。若单说Direct excution，指的是程序直接在CPU上执行（类似单片机？），OS对各程序加以限制，让进程间交替执行，即LDE。
3.1 用户空间和内核空间的切换
用户程序操作受限
OS的执行模式可以分为 kernel mode 和 user mode ，kernel mode下内核程序代码可以为所欲为，而user mode下的应用程序是受限的：比如，user mode程序无法直接进行IO请求，这种限制是必要的，因为OS不希望用户随便更改磁盘，而且OS的FS也希望用户访问文件前检查用户的访问权限。
系统调用并陷入内核
系统调用(system call) 可以说是连接用户空间和内核空间的桥梁。用户程序想执行受限的操作，需要通过OS的系统调用来 陷入(trap) OS内核。（这就类似于OS是个代理，特殊的操作都要由内核程序经手办理。最开始OS的系统调用可能有二十种左右，现在一般OS都有几百种系统调用。）
系统调用并陷(trap)入内核的流程可以看成是LDE执行协议，如下图，分为两段，第一段是系统启动时的向硬件的注册，第二段是正常运行：进行系统调用时，控制权将从用户程序转交内核，这需要用户程序执行trap指令，硬件首先会把当前程序的寄存器信息备份（x86下会将PC、各种标志位等寄存器push到对应进程的kernel stack中），然后根据（系统启动时注册到硬件的）系统调用trap表jump到指定的内核代码，OS内核为所欲为地执行完后，会最后执行return-from-trap指令，恢复用户程序寄存器(pop from kernel stack)，用户程序会继续运行。
比如，open()等函数就属于系统调用，在open的C库中，会有进行trap的汇编指令，所以我们可以直接调用系统调用函数，而不用写汇编，因为已经有人封装好了。
3.2 用户空间多个程序的切换(交替执行)
要使多个程序一起执行，需要OS进行整体的控制和调度，但是当用户程序在CPU运行时，意味着OS没有在运行，所以要在程序间复用CPU，OS需要频繁地拿回控制权并向多个进程进行分配。
早期的苹果系统和Xerox系统等采用了一种和谐 “合作”方式 处理这个问题，OS相信用户会调用一个成为yield的系统调用，主动交出控制权给内核。但是这样并无法保证程序不存在恶意，OS只能期望程序交出控制权或者程序执行出错（illegal operation）。
最常用的方法是用 timer中断方式 保证OS可以拿回控制权。系统启动时会设定一个定时器，若一个进程在一定时间没有放弃控制权，timer中断也会把控制权“夺回”给OS，OS决定是继续执行当前进程还是将时间片分给其他程序。需要注意的是，在这个过程中，存在两中保存和恢复(saves/restores)寄存器的过程：首先，在timer中断时， 硬件 会保存当前程序A的寄存器以便恢复执行；其次，如果OS决定从A切换到B，需要 软件 (OS)将A的寄存器保存到memory中。
中断还存在很多并发的问题，比如OS会在中断代码执行时禁止中断，并会引入很多锁保证内部数据结构的并发访问，书的第二部分将详细讨论。
第四节 进程调度
workload的信息
讨论调度首先要了解workload（当前系统运行的进程集），有时条件比较宽松，比如知道任务同时来，任务长短已知等，这时SJF(short job first)这种简单调度就是最优的；但一般情况下，workload的很多信息并无法预知，所以需要更复杂的调度方法。
调度的metrics：完成时间和响应时间
有两个衡量调度优劣的评判标准，Turnaround time和response time，一般两者不可兼得。
4.1 调度思想
两种简单的 非抢占(non-preemptive)调度 ，任务是一个接一个执行的：
- FIFO 或者称为FCFS，最简单，但是可能引起convoy effect（护送效应？），即第一个任务时间很长，后边的任务需要等很长时间。
-
SJF 改进了这种情况，让最短的任务最先执行。
但是，实际中的任务一般不是同时到达的，如果短的任务来晚了一会，长的任务已经执行了，又要等很长时间。于是有了 抢占式(preemptive)调度：
- STCF 即shortes time-to-completion first，或者叫 PSJF (Preempttive Shorted Job First)，改进了SJF 可以在预知完成时间的情况下，让可以先执行完的任务抢占执行。
但是，实际中很少知道任务什么时候将执行完一般很难知道，为了保证响应时间，有了 时间片(time slice或scheduling quantum) 的概念：
- Round Robin ,简称 RR ，是一种轮询调度，保证了响应时间，但是完成时间确是最差的。另外时间片的长短选择时，有一个 trade-off ：即进程的上下文切换需要时间，如果时间片太短，则会导致用在切换的时间太长，时间片太长，又会导致响应时间变差，这也是一个时间 分摊(amortize) 的问题。作者之后讨论的调度多是基于时间片的调度。
4.2 进行磁盘I/O的进程的调度
一个进程进行IO请求后，很可能会阻塞，但是这个阻塞并不占用CPU，因此这是应该利用这个时间去执行其他的进程，这样可以提升CPU利用率。当IO完成时，一般会有中断发生，这时OS才把进行IO的进程改回“ready”状态。
4.3 多级反馈队列调度(MLFQ)
Multi-level feedback queue主要通过”learn from history”的方法，解决完成时间(turnaround time)和响应时间(response time)的优化问题。
MLFQ有多个queue，每个queue有不同的优先级，并且可以根据任务执行的情况调整优先级：若任务在时间片结束前就放弃控制权，说明是 交互型任务 (类似latency-sensitive任务)，放在高优先级；如果每次都用完了时间片，说明是 CPU-bound 的任务(类似best-effort任务)，对响应要求不高，放在低优先级。比如对于鼠标键盘等IO，时间片结束前就会放弃CPU控制权，从而保持高优先级，保证了响应时间。
但是这种优先级调整会遇到几个问题：
饥饿问题(starvation) 如果高优先级的任务太多，低优先级队列的任务永远饿着，解决这个问题的办法是定期的 优先级boost ，即定期(如1s)将任务全调到最高优先级，这样可以防止饥饿。但是这个周期S参数怎么选又是个 trade-off ：太长的话，低优先级队列的任务就要饿很久；太短的话，对响应要求高的任务就不能更好地工作。
欺骗问题(game the scheduler) 既然执行完时间片会被降级，那么执行99%的时间片再放弃CPU，会同时获得高优先级和大量的CPU时间，这种欺骗是恶意的，会导致系统性能问题。解决的方法是将各个优先级间调整的依据（时间片）改为更精确的计时，高优先级的队列要求的时间更短，向下的优先级逐级递增（优先级越低，时间配额越大）。这里当然还会有很多参数设定的问题。
任务特征变化的问题 任务不都是一成不变的，可能由CPU-bound型转为interactive型。这个问题也可以通过定期 优先级boost 解决。
参数设定的问题 队列数目、队列长度、boost周期、优先级调整时间配额等都是可变的参数，但是这个参数很难调。我们大家都知道，多数用户从不改默认参数，改的话也可能越改越差，这个问题很难解决。有些系统给出了方便调优的工具，有些利用了应用或用户的建议(advise)或提示( hint )，比如进程优先级 nice 和内存管理 madvise 等。
MLFQ达到了一定的fairness，BSD UNIX的衍生版本、Solaris、Windows NT及后续版本都在用它作为基本调度器。
4.4 按比例(Proportion-Share)调度
比例调度(proportional-share scheduler, fair-share scheduler)保证了fairness，保证某个进程得到一定比例的CPU时间。
主要介绍了两种方法： lottery scheduling 和 stride scheduling ，前者为不同人物分配不同数量的ticket，然后随机选一个数，根据概率决定下一次哪个进程执行；后者根据步长，将每个任务的“计步器”初始化为0，CPU配额大的任务步长小，每次步数最少的程序执行。
stride scheduling更精确，因为没有随机数的应用；lottery scheduling更灵活，因为中途可以很方便地加入新的任务而不用新的初始化。
而且，lottery scheduling有很多有趣的玩法，ticket可以看成一种通货( ticket currency )，这种ticket通货在进程间进行转增( ticket transfer )、可能发生“通胀( ticket inflation )”的ticket增发等。ticket转赠即一个进程可以将自己的ticket划给其他进程，这样CPU比例就发生了变化；如果进程间 相互信任 ，还可以允许某个进程暂时凭空增加（借贷）和减少（放贷）ticket数目，这可能引起问题，但的确很灵活。这种讨论还可以参见[1]。
ticket assignment problem是指应该怎么指定给每个进程发多少tickets的问题，这个问题是开放性的。
[1] Lottery Scheduling, https://cs.nyu.edu/rgrimm/teaching/sp07-os/lottery.pdf