本文将介绍操作系统对 CPU 的虚拟化。

一、进程说明

1. 什么是进程？

简单来说，进程就是运行中的程序。

2. 进程如何创建？

• 加载：将代码和所有静态数据（例如初始化变量）加载到内存中

  在早期操作系统中，”加载” 操作会在程序运行前尽早完成；

  在现代操作系统中，会进行惰性 “加载”，只 “加载” 程序执行期间需要使用到的代码和数据

• 分配栈：分配内存，以便作为程序的栈

  使用栈存放局部变量、函数参数、返回地址

  若变量是对象，只存储引用

• 分配堆：分配内存，以便作为程序的堆

  使用堆存放对象本身

• I/O 初始化：操作系统还将执行一些 I/O 初始化任务

  在 UNIX 系统中，默认情况下，每个进程都有三个打开的文件描述符，用于标准输入、输出、错误

3. 进程状态

进程可以处于以下三种状态之一：

• 运行（running）：进程正在处理器上运行
• 就绪（ready）：进程已经准备好运行
• 阻塞（blocked）：进程执行了某种操作进入阻塞，知道某种时间发生时才会准备运行

二、进程权限

1. 主要问题

为了保证操作系统的安全性，不应该完全信任进程，因此应该对进程能做的事情做限制。

2. 用户模式与内核模式

• 用户模式：

  • 进程将以这种模式运行

  • 执行的操作将会受到限制

    例如用户模式下无法发起 I/O 请求

• 内核模式

  • 操作系统以这种模式运行
  • 此模式下拥有所有权限，可以执行任意操作

3. 系统调用

如果进程希望执行某些受限操作，操作系统会为它们提供渠道，即系统调用。

凡是与系统态级别的资源有关的操作（如文件管理、进程控制、内存管理等)，都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。

通常来说，程序会执行特殊的陷阱（trap）指令，该指令将控制转移到预先指定的陷阱处理程序（操作系统），并将权限级别提升为内核模式，自此，操作系统可以帮助进程完成其所需工作。完成后，操作系统调用一个从陷阱中返回（return-from-trap）指令，返回到用户程序中，同时将权限级别降低为用户模式。

三、进程协作方式

1. 主要问题

为了虚拟化 CPU，操作系统需要以某种方式让许多任务共享物理 CPU，让它们看起来像是在同时运行。其基本思想很简单：运行一个进程一段时间，然后运行另一个进程，如此循环往复。

如果要这么做，首先要解决的问题是控制权，操作系统要保留对 CPU 的控制权，以便将 CPU 运算能力分配给不同进程。

2. 协作方式

(1) 协作方式：被动等待

早期系统采用协作的方式，操作系统相信进程都是善意的，认为它们会定期放弃 CPU 控制权，以便操作系统重新获取。

“协作方式：被动等待” 过于被动，如果有 “恶意 / 缺陷” 进程（不放弃 CPU 控制权）持续运行，将导致操作系统永远无法接管 CPU。

(2) 非协作方式：操作系统主导

这种做法的实现核心是时钟中断：时钟设备可以编程为每隔几毫秒产生一次中断。产生中断时，正在运行的进程停止，操作系统中预先配置的中断处理程序会运行。操作系统可以因此重新获得 CPU 的控制权，从而把控进程的调度。

四、上下文切换

在进行进程切换时，操作系统应该做上下文切换。

• 在进行进程切换时，应该将上下文保存
• 在进程切换回来时，应该将上下文恢复

五、进程调度

1. 主要问题

操作系统需要考虑进程调度问题：假如同时有数个任务，应该如何分配 CPU 的使用权。

2. 常用概念

(1) 周转时间

周转时间：任务创建时间 -> 任务完成时间

(2) 响应时间

响应时间：任务创建时间 -> 任务首次执行时间

3. 调度方式 - 先进先出

一个最简单的做法是先进先出，将所有任务按照先来后到的顺序依次执行。

先进先出的做法在实际表现中不佳，一个执行所需时间较长的任务将会影响后续任务的 “完成时间”，因为后续任务都需要等待它执行完成。这种问题被称为 “护航效应”，一些耗时较少的资源消费者被排在重量级资源消费者之后，导致它们需要进行较长的等待。

4. 调度方式 - 最短完成时间优先

将任务按 “完成时间” 排序，从小到大依次完成。

5. 调度方式 - 最短剩余时间优先

将任务按照 “剩余时间” 排序，从小到大依次完成，如果新增了 “剩余时间” 更短的新任务，则执行新任务。

6. 调度方式 - 轮转

以时间片为单位，每个时间片轮流运行队列中的每一个任务。

这种做法的好处是响应时间较短。

7. 调度方式 - 结合 I/O

操作系统可以在某个进程等待 I/O 操作时，切换运行其它进程，以避免 CPU 闲置。

8. 调度方式 - 多级反馈队列

(1) 基本概念

• 多级反馈队列中有许多独立的队列
• 在任一时刻，一个工作只能存在于一个队列中
• 每个队列有不同的优先级，较高优先级的队列将会被优先执行
• 队列中的任务将会被轮转调度以执行

(2) 优先级计算

• 任务刚创建，首先作为最高优先级

• 一旦任务使用完时间配额后，降低优先级

  时间的计算通过累加的方式，即累加每次任务获取到 CPU 的时间

• 每经过一段时间，将所有任务都重新加入最高优先级队列

  主要考虑这样两个问题：

  • 低优先级的任务可能会长时间无法获取到 CPU
  • 同一个任务，可能在不同时间表现不同，一个 CPU 密集的进程可能在某个时间段表现为 I/O 密集，应该在它表现为 I/O 密集时给予更多的优先级

9. 调度方式 - 比例份额

(1) 基本概念

核心目标：以确保每个任务获得一定比例的 CPU 时间优先，而不以优化周转时间、响应时间优先。

(2) 实现 - 彩票调度

整个系统有若干张彩票，每个进程可以拥有一些彩票，进程的彩票数就代表着进程应该占有 CPU 的多少。

操作系统会在每个时间片随机抽取彩票号码，并让 CPU 运行拥有这个彩票的任务。

通过这种方式，可以让每个任务都 “近似” 拥有对应份额的 CPU。

(3) 实现 - 步长调度

略。

(4) 说明

比例份额并没有被广泛使用，原因是：

• 彩票调度和步长调度两种实现方式都不能很好地应对 I/O 密集型工作

• 比例的分配并没有一个较好的方案

  无法通过某种方式确定一个进程应该占据多少比例

参考

• 操作系统导论