最近开始看Operating Systems: Three Easy Pieces这本书，感觉光看书还是不够，还是需要将学习到的东西整理和归纳，以加深自己对于操作系统的理解。
CPU的虚拟化
基本概念
进程
进程(Process)是操作系统对于一个正在运行的程序的抽象
进程API
大体上可以分为创建(Create)，销毁(Destroy)，等待(Wait)，杂项控制(Miscellaneous Control)包括挂起等以及状态查询(Status)。
Unix下的进程API
fork() wait() 以及 exec()
进程状态
进程的状态大体上可以分为运行(Running)，就绪(Ready)以及阻塞(Blocked)。
- 运行(Running)，进程正在被处理器运行，这意味着，处理器正在执行指令。
- 就绪(Ready)，进程已经准备好去运行，但是出于某种原因，操作系统决定不在当前的时刻运行该进程。
- 阻塞(Blocked)，在阻塞状态，进程已经执行了某种其他的操作以至于在该操作完成前该进程不能就绪，如：进程对于磁盘的IO请求。
进程表
操作系统通常会使用进程表管理所有的进程，包括追踪每一个进程的寄存器，起始内存，内存大小，PID，父进程，已打开的文件，进程状态等。
机制:Limited Direct Execution(LDE)
直接执行即系统直接将进程运行在CPU上以最大化效率，限制即不能直接让进程取得对硬件以及系统所有的控制。
限制操作
当进程需要执行IO请求等限制操作时，不应该使得进程获得整个操作系统的控制权限。因此引入了Protected Control Transfer的概念。
Protected Control Transfer
引入两种处理器模式：User Mode和Kernal Mode
- User Mode - 在User Mode下，运行在该模式下的代码受到了严格的限制。比如，在该模式下，进程无法发起IO请求，并且也无法执行所有的限制指令。
- Kernal Mode - 在Kernal Mode下，由操作系统执行指令，执行的指令没有任何限制，包括IO请求以及所有的限制指令都可以被执行。
System Call - 用户程序通过执行System Call去执行限制指令如访问文件系统，与其他进程通信或是分配内存。
为了执行System Call，用户程序需要执行一个特殊的Trap指令，Trap指令同时地跳转至内核并且提升至Kernal Mode，一旦进入了内核，系统就可以执行任何限制指令，并且完成调用进程需要完成的任务。完成后，系统调用一个特殊的Return-From-Trap指令，跳转回用户程序并且降低至User Mode。
在执行Trap指令时，系统需要额外的开销以保证执行Return-From-Trap指令时跳转正确，例如，在x86下，系统会将PC及其他几个寄存器存入每个进程的内核栈。
此外，内核需要在引导时建立Trap Table以保证用户程序程序执行Trap指令后能跳转至对应的指令。操作系统通知硬件Trap Handlers的位置，通知之后，直到下次引导之前，硬件都会知道对应handlers的位置，这样，当System Call或是其他异常被抛出时，硬件能对应作出正确的反应。
显然，建立Trap Table的指令也是限制指令。
进程间切换
进程的切换需要操作系统的介入，但是当用户程序在CPU上执行时，操作系统并不在运行，那么，操作系统要如何重新获得对CPU的控制呢？
合作方法：等待System Calls
在这种方法下，操作系统相信系统进程能正确的执行，长时间运行的进程理应周期性的放弃CPU，从而操作系统能决定运行其他的任务。
大多数进程通过发起System Calls的方法转移CPU的控制权 - 在发起System Call，执行了Trap指令后，操作系统就获得了CPU的控制权。
那么，当程序错误的执行死循环之后，操作系统还能拿到CPU的控制权吗？
非合作方法：系统直接控制CPU
Timer Interrupt - 通过对定时器装置编程使得其每隔特定的时间（通常是毫秒级）发起中断。在这种情况下，当前执行的进程会被停止，并且操作系统中一个预先配置的Interrupt Handler会被执行，这样，操作系统就重新取得了对CPU的控制。
保存和恢复上下文
通常，当系统决定切换进程时，操作系统会执行一段底层代码(Context Switch)。从概念上来说，Context Switch会保存当前进程的若干寄存器的值，并且恢复待执行的进程的寄存器的值（例如，从内核栈中），这样，当Return-From-Trap指令执行时，系统得以恢复另一个进程的运行。
在Timer Interrupt的LDE Protocal中（例如），存在着两种类型的寄存器保存／恢复，在中断产生时，由硬件隐式的将寄存器的值存入当前进程的内核栈中，而在操作系统决定从当前进程切换至待执行进程时，由软件（操作系统）显式的将当前进程的寄存器的值（如PC，栈指针）存入当前进程的进程结构中（例如，进程控制块），并且从带切换进程的进程结构中恢复对应寄存器的值，这样，当执行Return-From-Trap指令后，由硬件隐式的从切换进程的内核栈中恢复寄存器的值，就好像刚才的Trap是由切换后进程执行的一样。
并发性
如果当一个System Call被发起时，发生了一个Timer Interrupt怎么办？
简单的做法是，在处理中断时，禁止其他中断的传入。更加复杂的机制留至并发行部分讨论。
调度器
负载假设
将正在运行在系统上的进程称为负载。为了简化调度过程，首先做出如下的假设：
- 每一个任务(Job)运行同样的时间
- 所有的任务都在同样的时间到达
- 所有的任务都仅使用CPU(不执行I/O)
- 每一个任务的运行时间都已知
我们会在稍后的讨论中放宽这些限制
调度指标
我们用调度指标衡量调度器的好坏，我们将使用以下两个指标：
- 周转时间(Turnaround Time) 周转时间是指完成时间与到达时间的差，周转时间是衡量性能性能的指标。
- 响应时间(Response Time) 响应时间是指任务第一次运行的时间与到达时间的差，响应时间是衡量公平性的指标。
先进先出(First In First Out)
该调度方法有时又被称作先到先得(First Come First Served)，即先到达的方法先被CPU运行。
假设有3个任务，每个任务都运行10s，那么它们的平均周转时间为(10+20+30)/3=20s
下面我们放宽假设1，即现在每一个任务运行的时间不必相同。
同样地，假设有3个任务，A运行100s而B和C运行10s，如果A先运行，然后运行B，最后运行C，那么现在的平均周转时间为(100+110+120)/3=110s，这就是护送效应(Convoy Effect)，即由于A的运行时间过长，而导致运行时间较短的B和C需要等待较长的时间。
提出如下的新规则——
最短任务优先(Shortest Job First)
为此，我们提出一种新的规则称为最短任务优先，该规则同样易于理解，即首先执行最短的任务，然后次短的任务，以此类推。
同样地假设A、B、C三个任务，其中A运行100s，而B和C运行10s，在SJF下，系统会先运行B和C，再运行A，平均周转时间为(10+20+120)/3=50s，远好于FIFO下相同假设的结果。
下面我们放宽假设2，即每一个任务有可能在任意时间到达。
假设A、B、C三个任务，其中A运行100s，在0s时到达，B和C运行10s，在10s时到达，在SJF下，平均周转时间为(100+(110-10)+(120-10))/3=103.33s，这是我们不愿意看到的结果，我们仍然需要改进调度算法——
最短完成时间优先(Shortest Time-to-Completion First)
SJF是一种非抢占(Non-preemptive)的调度器，而STCF是一种允许抢占的调度器，在上述的例子中，当B或者C到达时，调度器允许B或者C抢占A——即操作系统从任务A切换至任务B或者任务C（通过上下文切换），从而达到提升性能的目的。
在上例中，若采用STCF，平均周转时间为((120-0)+(20-10)+(30-10))/3=50s，远好于103.33s这一结果。
事实上，如果任务长度已知，任务仅使用CPU资源，且周转时间是唯一指标的话，STCF是最佳的调度算法，下面我们来讨论另一个指标——响应时间。
考虑到响应时间，上述的算法表现都不尽如人意，在上例中，用户要至少要等待10s才能得到任务C的响应，而这显然是对于交互不友好的，我们需要引入新的调度算法来解决这个问题——
轮循(Round Robin)
轮循的基本思想按照时间分片(Time Slice)或者说调度量子(Scheduling Quantum)来循环执行任务而不是运行任务直到完成。
假设有A、B、C三个任务，它们同时到达系统而且均运行5s，假设时间分片为1s，在这种情况下，操作系统首先运行A，1s后切换到B，B运行1s后再切换到C，然后再循环回A。这样，平均响应时间为(0+1+2)/3=1s；而在SJF下，平均响应时间为(0+5+10)/3=5s。
需要权衡时间分片的大小，如果时间分片过小，那么操作系统执行上下文切换的开销会显著增加。
在RR下，平均周转时间会变得非常糟糕。事实上，公平性和性能在调度中是矛盾的，任何注重公平性的调度算法（即拥有良好的响应时间）在性能上（即周转时间）都会表现的很差。这是固有的权衡，鱼和熊掌不可兼得。
合并I/O
接下来我们放宽假设3，即任务除了使用CPU外，还可能执行I/O请求，在发起了I/O请求后，任务将不会使用CPU，并且将处于阻塞的状态以等待I/O完成。
调度器需要决定I/O请求启动时是否切换至另一个任务，以及I/O完成时是执行当前任务还是切换回之前阻塞的任务。
假设我们正试图建立一个STCF调度器，假设A和B两个任务均运行50ms，并且A每10ms会发起一个花费10ms的I/O请求。在这种情况下，通常的解决方法是将A划分为5个独立的子任务，这样，当A发起I/O请求并且阻塞之后，B就可以被执行，而当I/O完成后，新的A的子任务会抢占B而继续执行。
上述的做法允许了重叠(Overlap)的发生，系统得以更好的利用处理器资源。
多级反馈队列(Multi-Level Feedback Queue)
最后，我们将放宽限制4，即系统不知道每个任务的运行时间。在这种情况下，我们将引入最有名的调度器之一——多级反馈队列来解决该问题。多级反馈队列试图在提升性能（即缩短平均周转时间）的同时最小化任务的响应时间。首先，我们将介绍有关多级反馈队列的最基本的概念。
MLFQ:基本规则
多级反馈队列(MLFQ)具有一系列相互独立的队列(Queue)，每一个队列都对应着不同的优先级(Priority Level)，在同一时间，一个任务只会处在一个队列中。
MLFQ根据优先级决定运行哪一个任务：即具有更高优先级的任务会被运行。
同时，考虑到可能会有多个任务处于同一个队列，即有可能出现相同优先级的情况，在这种情况下，MLFQ以轮循的方式运行这些任务。
因此我们得到了如下的基本规则：
- 如果A的优先级大于B的优先级，运行A(B不运行)
- 如果A和B的优先级相同，以轮循的方式运行A和B
假设两个任务A和B，A和B位于最高的优先级，而C和D位于次高的优先级，那么我们会发现，A和B会一直被运行，而C和D将永远无法被运行。
尝试1:如何改变优先级
MLFQ依据已经观察到的结果确定一个任务的优先级：如果一个任务在一个相当长的周期内一直在使用CPU，那么MLFQ会降低它的优先级，如果一个任务周期性的放弃CPU而等待用户的输入，那么MLFQ会维持它的优先级，因为这样的任务是一个活跃的任务。
因此我们得到了如下的规则：
- 当一个任务进入系统时，它将会被放置在优先级最高的队列
- a如果一个任务在运行中占用了一个完整的时间分片，那么它的优先级会被降低
- b如果一个任务在时间分片用完前放弃了CPU，那么它的优先级维持不变
在上述的规则中，我们考虑如下的两个问题：
- 如果有太多的活跃任务，那么他们会占用所有的CPU时间，那么，长时间运行的任务将永远不会得到任何的CPU时间。
- 程序可以以在时间分片用完前“故意”地放弃CPU以欺骗操作系统而使得其保持高优先级
尝试2:优先级提高
我们引入如下的规则来解决上面提到的问题1：
- 在某个时间周期S之后，将系统中所有的任务提升至优先级最高的队列
通过该规则，过多的活跃进程并不会完全占用CPU的时间，此外，当一个程序从不活跃转变为活跃时也能够及时得得到响应的CPU时间。
尝试3:更好的计量
我们引入如下的规则来解决上面提到的问题2:
- 一旦某个任务用完了在给定优先级下的分配时间，无论它已经放弃了多少次CPU，降低它的优先级。
这么做避免了一个任务欺骗操作系统，避免了其通过不公正的手段分享CPU的时间。