重学操作系统：CPU 虚拟化与进程

操作系统是每名程序员必须掌握的内容。回想大学时学习操作系统时，总是陷于一些算法方面的细节，习题则多为计算不同算法的性能指标，而忽略了从更高层面来看待和理解操作系统。因此，最近开始阅读备受好评的操作系统书籍：《操作系统导论》（英文版名称为：Operating Systems: Three Easy Pieces，OSTEP）。

OSTEP 从虚拟化、并发、持久化三大方面展开对操作系统的介绍，通过提出问题、介绍简单的解决方案、逐渐放宽假设从而引出现代操作系统中真正使用的复杂算法，循序渐进地展开对操作系统的介绍。同时，我认为本书最好的一点就是：对操作系统要解决的关键问题用单独的排版特别标出。抓住这些问题，就抓住了学习操作系统的主线任务和主要矛盾，而不会再局限于算法细节，真正从更高的角度理解操作系统。

本文内容基于《操作系统导论》CPU 虚拟化部分的内容，并按照自己的理解重新组织了内容。需要注意的是：本文的基本假设是单核 CPU 以及多进程，不考虑现代多核 CPU 所带来的进程调度等问题。

1. 什么是操作系统

在正式开始之前，我们首先要搞清楚一个问题：什么是操作系统？

首先，我们要对操作系统有一个直观的概念。这里用之前在知乎冲浪时看到的内容概括：操作系统就是躺在内存里面，等着中断到来进行处理的代码。（原文参见：Linux 内核的操作系统是不是得一直运行着？ - 高鹏的回答 - 知乎）

现在我们知道了操作系统不是魔法，它也是程序，只不过它的功能比较特殊，同时它的权限也比普通程序更高，也就是要区分 CPU 的内核模式和用户模式。

对操作系统有了直观的概念后，还需要知道操作系统究竟是用来干什么的，它有什么样的功能？同样一句话概括：操作系统是系统资源（CPU 时间、内存、IO 设备等）的管理者。资源往往是稀少的，而需求（即不同进程都有对资源的需求）又是很多的。因此，操作系统作为资源管理者，有以下主要设计目标：

• 共享：当资源有限时，如何满足众多需求，实现资源的共享；
• 高效：操作系统作为资源的管理者，其本身占用的 CPU、内存等资源要尽可能少，且尽量不让资源空闲，以实现高效的资源共享；
• 公平：在分配资源时，尽可能公平，不能让某个进程一直独占系统资源；
• 安全：操作系统要保证资源的安全性，防止资源遭到破坏以及不同进程之间互相影响。

实现这些目标的一个重要方法是：虚拟化，即：制造一个假象，让用户程序以为自己在独占资源。

对于 CPU 时间资源而言，进程便是为了解决 CPU 的共享问题而引出的概念，下一小节详细介绍。

2. 如何共享 CPU：进程

为了共享 CPU 实现运行多道程序，首先要知道 CPU 是用来干什么的？程序又是什么？

这里我们只需要知道 CPU 就是一个不断执行指令的器件，每个时钟周期其都在不断地进行：取指令、分析指令、执行指令的操作。而程序就是一个指令序列，正在执行中的程序称为进程。在某一时刻进程运行到的指令（PC，程序计数器）及进程的所有数据（包括寄存器和内存）共同构成了一个状态。在 CPU 的下一个时钟周期，CPU 将根据 PC 指针地址取指令，并分析执行，从而得到进程的下一个状态。

为了让 CPU 资源能够被共享，一个简单的想法就是：将时间划分为时间片，例如 1 秒钟。第 1 秒执行第 1 个进程；第 2 秒执行第 2 个进程；以此类推……这种方式称为：时分共享。同时，在切换执行的进程时，需要保存必要的进程状态（保存在内核栈中），包括：PC（程序计数器）、SP（栈指针） 等寄存器，以能够在后面恢复程序的运行状态并继续执行（上下文切换）。操作系统要用数据结构维护系统内所有的进程信息，称为：进程列表。为了保证安全性，操作系统运行于 CPU 内核模式下，而进程运行于用户模式下。同时，采用时间中断方式让操作系统能够周期性地获取执行权限。

3. 如何高效公平地共享 CPU：进程调度

当有多个进程在系统内运行时，我们要考虑让 CPU 执行哪个进程，这就是进程调度问题。同时，操作系统也要尽可能地保证高效地调度，及不浪费 CPU 资源；同时也要保证公平，不能出现饥饿现象（即有进程一直得不到执行）。

3.1 先进先出（First In First Out，FIFO）

FIFO 算法也被称为先到先服务（First Come First Served，FCFS）。

这是最简单的进程调度算法，根据名字就可以知道含义：先到达的进程先占用 CPU，直到运行结束（假设进程不存在 IO 操作）。

3.2 最短任务优化（Shortest Job First，SJF）

该调度策略含义为：先运行耗时最短的任务，然后次短任务，以此类推。

不过，由于现实世界往往不知道进程的执行耗时，因此该算法并不现实。

3.3 最短完成时间优化（Shortest Time-to-Completion First，STCF）

该调度策略也称为：抢占式最短作业优先（Preemptive Shortest Job First，PSJF）。

该调度算法运行进行抢占式调度（SJF 是非抢占式的），每当有新任务加入系统时，选择剩余工作和新工作中剩余时间最少的，执行该任务。

前三种调度算法都是为了优化周转时间（完成时间减去到达时间）。

3.4 轮转（Round-Robin，RR）

对于交互式程序，响应时间（即：首次运行时刻减去到达时刻）非常重要，于是提出了 RR 调度策略。

RR 基本思想是：在一个时间片内运行一个任务，然后切换到运行队列的下一个任务，而不是运行一个任务直到结束。反复执行，直到所有任务都运行结束。时间片长度必须是时钟中断周期的倍数。

3.5 多级反馈队列（Multi-level Feedback Queue，MLFQ）

前面 3.1 到 3.4 小节中的调度算法只能优化周转时间或响应时间中的一个。本小节介绍现代操作系统中真正使用的进程调度算法：多级反馈队列，其能够同时优化周转时间和响应时间。

MLFQ 调度算法有多个独立的队列，每个队列有不同的优先级。任何时刻一个任务只能存放在一个队列中。MLFQ 总是优先执行较高优先级的工作。同一优先级队列内的任务采用轮转调度。为了兼顾周转时间和响应时间，MLFQ 遵循以下规则：

• 如果 A 优先级大于 B 优先级，运行 A；
• 如果 A 优先级等于 B 优先级，轮转运行 A 和 B；
• 工作进入系统时，放在最高优先级队列；（优化响应时间）
• 一旦工作用完了其在某一层的时间配额（无论中间主动放弃了多少次 CPU），就降低其优先级；（公平性，优先级越高的队列时间配额越短）
• 每经过一段时间 \(S\) ，就将系统内所有工作重新加入最高优先级队列。（防止 CPU 密集型任务饥饿）

4. 总结

本文主要参考了 《操作系统导论》 1 到 11 章的内容，介绍了 CPU 虚拟化部分的主要内容，包括：进程概念、上下文切换、进程调度等。原书部分章节本文并未涉及，如：比例配额调度和多核处理器调度等，推荐阅读原书。