CPU虚拟化
概述
在操作系统中，常常同时运行着许多个进程，对于现代操作系统来说可能会有上百个进程同时运行（Windows可查看任务管理器，Linux系统为top或ps命令）。但是实际上只有少量的物理CPU可用，操作系统通过虚拟化CPU提供了几乎有无数个CPU可用的假象。
CPU虚拟化是通过时分共享的方式实现的：运行一个进程一段时间，然后运行另一个进程，如此轮换。这样可以允许用户运行多个进程，但是相应地也会使得每个进程的运行慢一些。相较于计算机中的其他设备（内存、总线上的其它设备等），CPU的运行速度要快得多。因此多个任务轮换执行可以充分利用CPU的计算资源。
在构建虚拟化机制时，需要考虑两个重要的问题：一是如何在不增加系统开销的情况下实现虚拟化，二是如何有效控制进程并同时保留对CPU的控制权。
受限直接执行
受限的直接执行（Limited direct execution）包括两部分：直接执行指的是直接在CPU上运行程序；而受限指的是进程在运行时存在一些限制，用于确保OS对CPU的控制。
直接执行
当OS希望启动程序运行时，它会在进程列表里面为其创建一个进程条目，为其分配一些内存，将程序代码从磁盘加载到内存，找到程序的入口点并跳转到那里开始执行。这样，程序便直接在CPU上运行，从而取得快速的执行速度。
受限操作
在操作系统中，通过引入用户模式和内核模式，使得一个进程能够执行I/O和其他一些受限制的操作，同时又确保进程不能完全控制系统。在用户模式下，运行的代码会受到限制，比如进程不能发出I/O请求；而在内核模式下，运行的代码可以执行任何事情，操作系统就以这种模式运行。
为了让进程执行某些特权操作，几乎所有的现代硬件都提供了用户程序执行系统调用的能力；同时内核也会提供一些系统调用（大多数操作系统提供几百个调用），小心地向用户程序暴露一些关键功能。
要执行系统调用，程序需要执行特殊的陷阱指令。执行该指令将会跳到内核，并将特权级别提升为内核模式，此时程序可以执行被允许的特权操作。完成后，操作系统将会调用一个从陷阱返回的指令，返回到发起系统调用的用户程序中，并回到用户模式继续执行该程序。在执行陷阱时，硬件需要确保调用者寄存器中的值被保存下来，以便在操作系统发出从陷阱返回指令时能够正确返回。在X86上，处理器会将程序计数器、标志和一些其他寄存器推入每个进程的内核栈上，从陷阱返回时将这些值从内核栈中弹出。
备注—内核栈与用户栈：
每个进程都有两个堆栈，用户栈和内核栈。用户栈位于用户地址空间，而内核栈位于内核地址空间，用于保存进程在内核态运行时所产生的相关信息。当CPU在用户态运行时，CPU栈指针寄存器（%rsp/%esp）保存的是用户栈的栈顶指针，此时使用用户栈；而CPU在内核态运行时，栈指针寄存器则使用内核栈的栈顶指针，相当于使用内核栈。在切换用户态与内核态时，通过保存与设置栈指针的值，便可完成栈的切换。
当操作系统启动时，会设置一个陷阱表，告诉硬件在发生某些异常事件时应该运行哪些代码。操作系统会通过一些特殊的指令向硬件发送信息，使硬件知道这些陷阱处理程序的位置，以及发生系统调用和其他异常事件时应该跳转到哪一条代码。硬件会保存这些信息，直到重新启动机器。
进程之间的切换
重获CPU的控制权
当一个进程在CPU上运行时，操作系统无法采取任何行动，需要采取一些策略来重新获得对CPU的控制权。常用的方式有：
- 协作方式：操作系统相信系统的进程会合理运行，OS通过等待系统调用或者某种非法操作发生，从而重新获得对CPU的控制权。当某个进程进入无限循环，这种方式便会出现问题。
- 非协作方式：通过使用时钟设备编程，每隔一段时间产生一次中断。在产生中断时，停止当前正在运行的进程，运行操作系统中预先配置好的中断处理程序。此时操作系统重新获得对CPU的控制权。
保存和恢复上下文
当操作系统重新获得控制权之后，便可以决定是否切换进程（由操作系统的进程调度算法来决定）。如果要进行切换，OS会执行一些底层代码，即上下文切换。上下文切换指的是操作系统为当前正在执行的进程保存一些寄存器的值，并为即将执行的进程恢复一些寄存器的值。
具体来说，在上下文切换的过程中，操作系统会执行一些底层的汇编代码，保存通用寄存器、程序计数器、当前进程的内核栈指针，然后恢复寄存器、程序计数器并切换内核栈指针，供即将运行的进程使用。通过切换栈，内核便完成了进程的切换。（注意：在切换进程的时候，操作系统是在内核态下进行操作的，因此切换的栈指针是内核栈，而用户栈的指针则保存在内核栈中）
进程调度
度量指标
周转时间：\(T_{周转时间}=T_{完成时间}-T_{到达时间}\)
响应时间：\(T_{响应时间}=T_{首次运行}-T_{到达时间}\)
调度方案及其分析
简单的调度算法
先进先出
最基本的调度算法为先进先出（First In First Out, FIFO），或称为先到先服务（First Come First Served, FCFS）。这种方法简单易实现，但是会出现护航效应（Convoy effect），即一些耗时较少的资源消费者被排在耗时较多的资源消费者之后，造成周转时间的表现较差。
最短任务优先
最短任务优先（Shortest Job First, SJF）调度算法先执行最短的任务，再执行次短的任务，以此类推。如果假设所有任务同时到达，那么这种方法是最优的调度算法。但是这种假设是不切实际的，事实中，如果耗时较多的任务先到达，耗时较少的任务后到达，则会遇到同样的护航问题。
最短完成时间优先
如果我们允许抢占，向SJF调度算法中添加抢占则变成了最短完成时间优先（Shortest Time-to-Completion First, STCF）调度算法。每当一个新工作进入系统中时，它会确定剩余工作和新工作中谁的剩余时间最少，然后调度这一工作。这种方法的周转时间较少，但是却具有糟糕的响应时间和交互性。
轮转
轮转（Round-Robin, RR）调度算法在一个时间片（时间片的长度是计算机时钟中断周期的倍数）内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到完成。反复这样执行，直到所有任务完成。考虑响应时间的话，RR算法的表现很好；但如果考虑周转时间的话，RR算法是最糟糕的策略之一。
时间片的长短对于RR算法来说十分重要，时间片越短则在响应时间上表现越好，但是也会造成上下文切换的次数增加，从而影响整体性能。
结合I/O的调度
由于进程在执行I/O操作期间不会使用CPU，此时调度算法可以在CPU上安排另外一项工作。通过这样可以实现重叠，一个进程在等待另一个进程的I/O完成时使用CPU，从而使得系统得到更好的利用。
多级反馈队列
在多级反馈队列（Multi-level Feedback Queue, MLFQ）算法中，同时维护了多个独立的队列。每个队列都有不同的优先级，同时每个队列也可以拥有不同长度的时间片，在任何时刻一个工作只能存在于一个队列中。MLFQ总是优先执行较高级队列中的工作；如果一个队列中有多个工作，就对这些工作采用轮转调度。
MLFQ调度策略的关键在于如何设置优先级，这种算法中对于优先级的设置有如下规则：
- 工作进入系统时，放在最高优先级，即最上层队列。这一规则假设每个进入系统的工作都为短工作，如果确实是短工作则很快会执行完毕，否则它的优先级会降低，也就相当于被认为是长工作。
- 调度程序记录每个进程在某一层中消耗的总时间，一旦工作用完了在某一层中的时间配额（无论中间放弃过多少次CPU），就降低它的优先级，移动这个工作到下一级队列中去。这一做法主要是为了防止过多的交互型工作造成饥饿问题，使得长工作无法被执行；同时也防止一些进程通过添加I/O操作来愚弄调度程序。
- 经过一段时间\(S\)，就将系统中的所有工作重新加入到最高级队列。这样可以防止出现饥饿问题，同时也能够使得进程的工作类型从CPU密集型变成交互型时，调度系统能够正确处理。对于\(S\)的值应当合理设置，太大会造成饥饿问题，太小则会影响交互型工作的执行。
比例份额算法
比例份额（Proportional-share）调度算法的核心思想是确保每个工作获得一定比例的CPU时间，而不是优化周转时间和响应时间。
彩票调度算法
彩票调度（lottery scheduling）算法利用了随机性，这种方法运行速度快、占用空间少、同时也可以避免一些奇怪的边界情况。在彩票调度算法中，一个进程拥有的彩票数占总彩票数的百分比就是它占用资源的份额。拥有的彩票越多，则优先执行的可能性越大。
为了增加调度的灵活性，调度算法还提供了一些机制，以不同且有效的方式来调度彩票：
- 彩票货币：用户可以按照不同的比例将自己持有的彩票分给不同的任务。调度系统会按照每个用户所拥有的彩票份额，自动计算出这些任务所对应的全局彩票份额。
- 彩票转让：一个进程可以临时将自己的彩票转移给另一个进程。
- 彩票通胀：一个进程可以临时提升或降低自己拥有的彩票数量。这种机制适用于进程之间相互信任的环境，如果在竞争环境中则可能会使得恶意进程占用全部资源。
彩票调度算法的实现很简单，只需要一个随机数生成器来选择中奖彩票，一个链表记录系统中所有的进程，并记录所有彩票的总数。在任务调度时，首先选择出一个随机数（小于彩票总数），并将变量counter置为0。之后会从前向后遍历进程链表，并将每个进程所拥有的彩票数累加给counter，直到counter的值大于选出的随机数。
彩票算法也存在一些问题：首先是当工作执行时间很短时，可能无法做到公平调度，只有当执行很多时间片时才能够期望取得比较公平的调度结果；另一个问题是系统的运行严重依赖于彩票的分配。
步长调度算法
步长调度（stride scheduling）算法是一种确定性的公平分配算法。系统中的每个工作都有自己的步长，与彩票调度算法相对应的是，步长与票数值成反比，即步长越小的进程占用资源的份额越高。系统为每一个进程维护了一个行程值，用于记录它的总体进展。
调度的基本思路很简单：当需要调度时，选择目前拥有最小行程值的进程，并且在运行之后将该进程的形成值增加一个步长。如果最小行程值的进程有多个，则可以任意选择。
与彩票调度算法相比，步长算法可以在每个调度周期内做到完全正确，但是需要为每个进程维护一个全局状态。同时，对于中间加入的进程，步长调度算法需要合理地设置它的行程值，而彩票调度算法只需要使用它的票数去更新全局的总票数即可。
多处理器调度
多处理器架构的影响
对于多个CPU的计算机架构，每个CPU有自己的独立缓存，同时也可能有一块多个CPU共享的缓存，并且它们共享内存（参考计算机组成原理相关部分）。这就导致了一些不同于单CPU调度系统的地方：
- 需要考虑读写数据时的缓存一致性问题，通常这一问题由硬件解决。
- 在跨CPU访问共享数据时，需要使用互斥原语才能保证其正确性。
- 需要考虑缓存亲和性，尽可能将同一个进程保持在同一个CPU上
单队列调度
单队列多处理器调度（Single Queue Multiprocessor Scheduling, SQMS）算法将所有需要调度的工作放入一个单独的队列中。
优点：可以将单CPU中的一些调度方式直接用于多CPU系统，实现简单
缺点：
- 缺乏可扩展性：需要在代码中加锁来保证原子性，这会带来性能损失，尤其是当CPU数目增加时。
- 缓存亲和性差：每个工作可能会不断地在不同的CPU中间执行，所以缓存亲和性较差。为了解决这一问题，可以引入一些亲和度机制。
多队列调度
多队列多处理器调度（Multi-Queue Multiprocessor Scheduling, MQMS）算法包含了多个调度队列，每个队列可以使用不同的调度规则。当一个工作进入系统时，会按照一定的启发式规则将其放入某个调度队列。这样使得每个CPU的调度相互独立。
优点：具有可扩展性与良好的缓存亲和度。
缺点：可能会形成负载不均，通过工作的跨CPU迁移可以缓解这一现象。
参考
- Operating Systems: Three Easy Pieces