在本章中，我们将讨论操作系统为用户提供的最基本的抽象之一:进程。一个进程的定义在理论上是相当简单的:它是一个正在运行的程序[V+65,BH70]。程序本身就是一个没有生命的东西:它只是位于磁盘上，一堆指令(可能还有一些静态数据)，等待着开始行动。是操作系统获取这些字节并使它们运行，将程序转换成有用的东西。
事实证明，人们经常希望同时运行多个程序;例如，考虑你的台式机或笔记本电脑，你可能想运行一个网页浏览器，邮件程序，游戏，音乐播放器，等等。事实上，一个典型的系统看起来可能同时运行数十个甚至数百个进程。这样做使系统易于使用，因为人们永远不需要关心CPU是否可用;人们只是运行程序。因此我们面临的挑战：

问题的关键是: 如何提供有许多cpu的假象 尽管可用的物理cpu很少，但是操作系统如何提供几乎无穷无尽的cpu供应的假象呢？

操作系统通过虚拟化 CPU 来创造这种错觉。通过运行一个进程，然后停止它并运行另一个进程，依此类推，操作系统可以产生存在许多虚拟 CPU 的错觉，而实际上只有一个（或几个）物理 CPU。这种被称为 CPU 时间共享的基本技术允许用户运行任意数量的并发进程；潜在的成本是性能，因为如果必须共享 CPU，每个都会运行得更慢。
为了实现CPU的虚拟化，并且很好地实现它，操作系统将需要一些低级机器和一些高级智能。我们称之为低级机械机制;机制是实现所需功能的底层方法或协议。例如，我们稍后将学习如何实现上下文切换，这使操作系统能够在给定的CPU上停止运行一个程序并开始运行另一个程序;所有现代操作系统都采用这种分时机制。

Tip: 使用时间共享(和空间共享) USE TIME SHARING (AND SPACE SHARING) 时间共享（Time sharing）是操作系统共享资源的基本技术。通过允许资源被一个实体使用一段时间，然后被另一个实体使用一段时间，以此类推，所讨论的资源(例如CPU或网络链接)可以被许多实体共享。与时间共享相对应的是空间共享（space sharing），即将资源(在空间上)分配给希望使用它的人。例如，磁盘空间自然是一种空间共享资源;一旦一个块被分配给一个文件，它通常不会分配给另一个文件，直到用户删除原始文件。

在这些机制之上，一些智能以策略的形式存在于操作系统中。策略是用于在操作系统内做出某种决定的算法。例如，给定许多可能在 CPU 上运行的程序，操作系统应该运行哪个程序？操作系统中的调度策略将做出这个决定，可能使用历史信息（例如，哪个程序在最后一分钟运行得更多？）、工作负载知识（例如，运行的是什么类型的程序）和性能指标（例如，系统优化交互性能或吞吐量？）来做出决定。

4.1 抽象：进程 The Abstraction: A Process

操作系统对正在运行的程序所提供的抽象，我们称之为进程。正如我们上面所说的，进程只是一个正在运行的程序;在任何时刻，我们都可以通过记录进程在执行过程中访问或影响的系统的不同部分来概括进程。
为了理解什么构成了进程，我们必须了解它的机器状态:程序在运行时可以读取或更新什么。在任何给定的时间，机器的哪些部分对程序的执行是重要的。
组成进程的机器状态的一个明显组件是它的内存。指令存在内存中;正在运行的程序读取和写入的数据也存在内存中。因此，进程可以寻址的内存(称为地址空间)是进程的一部分。
进程的机器状态的一部分是寄存器;许多指令显式地读取或更新寄存器，因此显然它们对进程的执行很重要。
请注意，有一些特殊的寄存器构成此机器状态的一部分。例如，程序计数器(PC)(有时称为指令指针或IP)告诉我们下一步将执行程序的哪条指令;类似地，堆栈指针和相关的帧指针用于管理函数参数、局部变量和返回地址的堆栈。
最后，程序也经常访问持久存储设备。这样的I/O信息可能包括进程当前打开的文件列表。

Tip: 分离策略和机制 在许多操作系统中，一个常见的设计范例是将高级策略从低级机制中分离出来[L+75]。您可以将这种机制看作是对关于系统的“如何”问题提供答案;例如，操作系统如何执行上下文切换?政策提供了哪个问题的答案;例如，操作系统现在应该运行哪个进程?将两者分开，可以轻松地更改策略，而无需重新考虑机制，因此这是模块化的一种形式，模块化是通用的软件设计原则。

4.2 进程API Process API

虽然我们将真正的进程API的讨论推迟到后面的章节，但在这里，我们首先给出一些操作系统的任何接口中都必须包含哪些内容的概念。这些APIs以某种形式在任何现代操作系统上都可用。

• 创建:操作系统必须包含创建新进程的方法。当您在shell中输入命令或双击应用程序图标时，将调用操作系统创建一个新进程来运行您所指示的程序。
• 销毁：由于有进程创建的接口，系统也提供了一个接口来强制销毁进程。当然，许多进程会运行并在完成时自行退出；然而，当它们不这样做时，用户可能希望杀死它们，因此停止失控进程的接口非常有用。
• 等待:有时等待进程停止运行是有用的;因此，通常会提供某种等待接口。
• 杂项控制:除了终止或等待进程之外，有时还可能有其他控制。例如，大多数操作系统都提供某种方法来暂停进程(暂停运行一段时间)，然后恢复进程(继续运行)。

• 状态:通常也有一些接口来获取进程的一些状态信息，比如它运行了多长时间，或者它处于什么状态。

  4.3 进程创建：更多细节 Process Creation: A Little More Detail

  我们应该揭开的一个谜团是程序是如何转化为进程的。具体来说，操作系统如何启动和运行程序?进程创建实际上是如何工作的？
  操作系统运行一个程序必须做的第一件事是加载它的代码和任何静态数据(例如，初始化的变量)到内存，到进程的地址空间。程序最初以某种可执行格式驻留在磁盘(或者，在一些现代系统中，基于闪存的ssd)上;因此，加载程序和静态数据到内存的过程需要操作系统从磁盘读取这些字节，并将它们放在内存中的某个地方(如图4.1所示)。
  
  在早期的(或简单的)操作系统中，加载过程是急切地完成的，也就是说，在运行程序之前一下子完成;现代的操作系统执行这个过程是惰性的，例如，只在程序执行过程中需要的时候才加载代码或数据。要真正理解代码和数据段的延迟加载是如何工作的，您必须更多地了解分页 paging 和交换机制 swapping，这些主题将在将来讨论内存虚拟化时讨论。现在，只要记住，在运行任何东西之前，操作系统显然必须做一些工作，将重要的程序位从磁盘放到内存中。
  一旦代码和静态数据被加载到内存中，在运行进程之前，操作系统还需要做一些其他的事情。一些内存必须分配给程序的运行时堆栈 run-time stack (或仅仅堆栈 stack)。你可能已经知道，C程序使用栈来存放局部变量、函数形参和返回地址;操作系统分配这些内存并将其交给进程。操作系统也可能会用参数初始化堆栈;具体来说，它将填充main()函数的形参，即argc和argv数组。
  操作系统也可能为程序的堆分配一些内存。在C程序中，堆用于显式请求动态分配的数据;程序通过调用malloc()请求这样的空间，并通过调用free()显式释放它。堆用于数据结构，如链表、散列表、树和其他有趣的数据结构。堆一开始会很小;当程序运行时，并通过malloc()库API请求更多内存时，操作系统可能会参与进来，并分配更多内存给进程，以帮助满足此类调用。
  操作系统还将执行一些其他的初始化任务，特别是与输入/输出(I/O)相关的任务。例如，在UNIX系统中，每个进程默认有三个打开的文件描述符，分别用于标准输入、输出和错误;这些描述符让程序可以轻松地从终端读取输入并将输出打印到屏幕上。在这本关于持久性的书的第三部分中，我们将学习更多关于I/O、文件描述符等方面的知识。
  通过将代码和静态数据加载到内存中，通过创建和初始化堆栈，以及执行与I/O设置相关的其他工作，操作系统现在(终于)为程序执行设置了舞台。因此，它还有最后一个任务:在入口点(即main())启动程序。通过跳转到main()例程(通过一种特殊的机制，我们将在下一章讨论)，操作系统将CPU的控制转移到新创建的进程，从而程序开始执行。

  4.4 进程状态 Process States

  现在我们对什么是流程有了一些了解（尽管我们将继续完善这个概念）以及（大致）它是如何创建的，让我们来谈谈流程在给定时间可能处于的不同状态。进程可以处于这些状态之一的概念出现在早期的计算机系统中 [DV66,V+65]。在简化的视图中，进程可以处于三种状态之一：

• 运行Running:表示进程在处理器上运行。这意味着它正在执行指令。

• 就绪Ready:在就绪状态下，进程已经准备好运行，但由于某种原因，操作系统在这个给定时刻选择不运行它。
• 阻塞Blocked:在阻塞状态下，进程执行了某种操作，使得它在发生其他事件之前不能运行。一个常见的例子是:当一个进程向磁盘发起I/O请求时，它会被阻塞，因此其他进程可以使用该处理器。

如果我们将这些状态映射到图上，我们将得到图 4.2 中的图。正如您在图中看到的，进程可以根据操作系统的判断在就绪和运行状态之间移动。从就绪状态变为运行状态意味着进程已被调度；从运行状态移动到就绪状态意味着进程已被取消调度。一旦进程被阻塞（例如，通过启动 I/O 操作），操作系统将保持这种状态，直到发生某些事件（例如，I/O 完成）；此时，进程再次进入就绪状态（并且可能立即再次运行，如果操作系统如此决定）。

让我们看一个例子，看看两个进程如何通过这些状态进行转换。首先，假设运行两个进程，每个进程只使用CPU(它们不进行I/O)。在本例中，每个流程的状态跟踪可能如图4.3所示。

在下一个示例中，第一个进程在运行一段时间后发出I/O。此时，进程被阻塞，给其他进程一个运行的机会。图4.4显示了这个场景的一个轨迹。

更具体地说，Process0启动一个I/O，并在等待它完成时变得阻塞;进程会阻塞，例如，当从磁盘读取数据或等待来自网络的数据包时。操作系统发现Process0没有占用CPU，开始运行Process1。当Process1运行时，I/O完成，将Process0移动回就绪状态。最后，Process1结束，Process0运行，然后完成。
注意，即使在这个简单的示例中，操作系统也必须做出许多决定。首先，当Process0发出I/O时，系统必须决定运行Process1;这样做可以保持CPU繁忙，从而提高资源利用率。第二，当I/O完成时，系统决定不切换回Process0;目前还不清楚这是否是一个好决定。你觉得呢?这些类型的决策是由操作系统调度器做出的，这个话题我们将在未来的几章中讨论。

4.5 数据结构 Data Structures

操作系统是一个程序，和任何程序一样，它有一些关键的数据结构，用于跟踪各种相关信息。例如，为了跟踪每个进程的状态，操作系统可能会保存所有就绪进程的某种进程列表和一些附加信息，以跟踪哪个进程当前正在运行。操作系统还必须以某种方式跟踪被阻塞的进程;当I/O事件完成时，操作系统应该确保唤醒正确的进程并使其准备好再次运行。
图4.5显示了操作系统需要什么类型的信息来跟踪xv6内核中的每个进程[CK+08]。类似的进程结构存在于真实的操作系统中，如Linux、Mac OS X或Windows;看看它们有多复杂。

从图中，您可以看到操作系统跟踪的关于进程的一些重要信息。对于已停止的进程，寄存器上下文将保存其寄存器的内容。
当一个进程停止时，它的寄存器将被保存到这个内存位置;通过恢复这些寄存器(即，将它们的值放回实际的物理寄存器中)，操作系统可以继续运行进程。在以后的章节中，我们将更多地了解这种称为上下文切换的技术。
您还可以从图中看到，除了运行、就绪和阻塞之外，进程还可能处于其他一些状态。有时候，系统在创建进程时，会有一个初始状态。此外，还可以将进程置于已退出但尚未被清除的最终状态(在基于unix的系统中，这称为僵尸状态zombie state)。
这个最终状态很有用，因为它允许其他进程（通常是创建进程的父进程）检查进程的返回码，看看刚刚完成的进程是否成功执行（通常，在基于 UNIX 的系统中，程序在成功完成任务后返回零，否则非零）。完成后，父进程将进行最后一次调用（例如，wait()）以等待子进程的完成，并向操作系统表明它可以清理任何涉及现已灭绝进程的相关数据结构。

4.6 总结 Summary

我们已经介绍了操作系统最基本的抽象:进程。它很简单地被看作是一个运行程序。有了这个概念性的观点，我们现在将转移到本质上:实现进程所需的低级机制，以及以智能方式调度进程所需的高级策略。通过结合机制和策略，我们将加深对操作系统如何虚拟化CPU的理解。

ASIDE:关键进程术语

• 进程是运行程序的主要操作系统抽象。在任何时候，进程都可以用它的状态来描述:地址空间address space中的内存内容，CPU寄存器的内容(包括程序计数器program counter和堆栈指针stack pointer等)，以及关于I/O的信息(如可读或可写的打开文件)。
• 进程API process API 由程序可以进行的与进程相关的调用组成。通常，这包括创建、销毁和其他有用的调用。
• 进程处于许多不同进程状态process states中的一种，包括正在运行、准备运行和阻塞。不同的事件(例如，调度或调度，或等待I/O完成)将进程从这些状态中的一种转移到另一种。
• 进程列表包含系统中所有进程的信息。每个条目都可以在有时被称为进程控制块(PCB)的地方找到，PCB实际上只是一个包含关于特定进程的信息的结构。

Homework (Simulation)

这个程序，process-run.py，允许你查看程序运行时进程状态是如何变化的，或者是使用CPU(例如，执行一个添加指令)或者是I/O(例如，发送一个请求到磁盘并等待它完成)。有关详细信息，请参阅README。

Questions

1. 使用以下标志运行 process-run.py：-l 5:100,5:100。CPU 利用率应该是多少（例如，CPU 正在使用的时间百分比？）您为什么知道这一点？使用 -c 和 -p 标志来查看您是否正确。
2. 现在使用这些标志运行:./process-run.py -l 4:100,1:0。这些标志指定了一个有4条指令的进程(都使用CPU)，以及一个简单地发出I/O并等待它完成的进程。完成这两个过程需要多长时间?使用-c和-p来确定是否正确。
3. 切换进程顺序:-l 1:0,4:100。现在发生了什么?转换顺序重要吗?为什么?(和往常一样，使用-c和-p来判断是否正确)。
4. 现在我们将研究其他一些标志。一个重要的标志是-S，它决定了当进程发出I/O时系统如何反应。如果将标志设置为SWITCH_ON_END，当一个进程正在进行I/O时，系统将不会切换到另一个进程，而是等待该进程完全完成。当你运行以下两个进程(-l 1:0,4:100 -c -S SWITCH_ON_END)，一个做I/O，另一个做CPU工作时，会发生什么?
5. 现在，运行相同的进程，但是将切换行为设置为在某个进程等待I/O时切换到另一个进程(-l 1:0,4:100 -c -S SWITCH_ON_IO)。现在发生了什么?使用-c和-p来确认您是正确的。
6. 另一个重要的行为是当I/O完成时该做什么。使用-I IO_RUN_LATER，当一个I/O完成时，发出它的进程不一定马上运行;相反，无论当时在运行什么，它都会继续运行。当您运行这个进程组合时会发生什么?(执行 ./process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_LATER -c -p)系统资源是否得到有效利用?
7. 现在运行相同的进程，但是使用-I IO_RUN_IMMEDIATE集，它会立即运行发出I/O的进程。这种行为有何不同?为什么运行一个刚刚完成I/O的进程是一个好主意呢?
8. 现在运行一些随机生成的进程:-s 1 -l 3:50,3:50或-s 2 -l 3:50,3:50或-s 3 -l 3:50,3:50。看看你能不能预测追踪结果。当你使用标志-I IO_RUN_IMMEDIATE和-I IO_RUN_LATER时会发生什么?当你使用-S SWITCH_ON_IO和-S SWITCH_ON_END时会发生什么?

   homework笔记

   进程还有一些其他状态
   
   一个进程由指令组成，每条指令只能做两件事之一：

• 使用CPU
• 发出 IO（并等待它完成）

当一个进程使用 CPU（并且根本不执行 IO）时，它应该简单地在 CPU 上运行RUNNING或准备运行READY之间交替。例如，这里是一个简单的运行，它只运行一个程序，并且该程序只使用 CPU（它没有 IO）。

这里我们指定的进程是“5:100”，意思是它应该由5条指令组成，每条指令是CPU指令的概率是100%。
您可以使用 -c 标志查看进程发生了什么，该标志会为您计算答案：

这个结果并不太有趣：进程在 RUN 状态下很简单，然后完成，整个时间都在使用 CPU，从而使 CPU 在整个运行过程中保持忙碌，并且不做任何 I/O。
让我们通过运行两个进程让它稍微复杂一点：

在这种情况下，运行了两个不同的进程，每个进程都只使用 CPU。当操作系统运行它们时会发生什么？让我们来了解一下：

正如您在上面看到的，首先运行“进程 ID”（或“PID”）为 0 的进程，而进程 1 准备运行但只是等待 0 完成。当 0 完成时，它移动到 DONE 状态，而 1 运行。当 1 完成时，跟踪完成。
在回答一些问题之前，让我们再看一个例子。在这个例子中，进程只发出 I/O 请求。我们在此处使用标志 -L 指定 I/O 需要 5 个时间单位来完成。

您认为执行跟踪会是什么样子？让我们来了解一下：

如您所见，该程序仅发出三个 I/O。当每个 I/O 发出时，进程进入 WAITING 状态，当设备忙于为 I/O 服务时，CPU 处于空闲状态。
为了处理 I/O 的完成，还会发生一个 CPU 操作。请注意，处理 I/O 启动和完成的单个指令并不是特别现实，只是为了简单起见在这里使用。
让我们打印一些统计信息（运行与上面相同的命令，但带有 -p 标志）以查看一些整体行为：

如您所见，跟踪运行了 21 个时钟滴答，但 CPU 忙的时间不到 30%。另一方面，I/O 设备非常繁忙。通常，我们希望让所有设备都处于忙碌状态，因为这样可以更好地利用资源。还有一些其他重要的标志：

现在请回答本章后面的问题以了解更多信息。