第二章 进程管理

2.1 进程的基本概念

在传统的操作系统中，程序并不能独立运行，作为资源分配和独立运行的基本单位都是进程。

2.1.1 程序的顺序执行及其特征

1、程序的顺序执行

把一个应用程序分成若干个程序段，在各程序段之间，必须按照某种先后次序顺序执行，仅当前一操作（程序段）执行完后，才能执行后及操作。

2、程序顺序执行时的特征

1）顺序性

处理机的操作严格按照程序所规定的顺序执行，即每一操作必须在上一个操作结束之后开始

2）封闭性

程序是在封闭环境下执行的，即程序运行时独占全机资源，资源的状态（除初始状态外）只有本程序才能改变它。程序一旦执行，其执行结果不受外界因素影响。

3）可再现性

只要程序执行是的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿的执行，还是断续执行，都将获得相同的结果

2.1.2 前趋图

前趋图（Precedence Graph）是一个有向无循环图，记为DAG（Directed Acyclic Graph），用于描述进程之间之行的前后关系。如图：

图中的每个节点可用于描述一个程序段或进程，乃至一条语句；节点间的有向边表示两个节点之间存在的偏序关系（Partial Order）或者前趋关系（Precedence Relation）“→”。

→={(Pi，Pj)|Pi must complete before Pj may start}，如果(Pi，Pj)∈→，可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。此外，每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。在图2-1(a)和2-1(b)中分别存在着这样的前趋关系:

Ii→Ci→Pi  和  S1→S2→S3

对于图2-2（a） 所示的前趋图，存在下述前趋关系：

�    P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P4→P6，P4→P7，P5→P8，P6→P8，P7→P9，P8→P9

或表示为：

P={P1，P2，P3，P4，P5，P6，P7，P8，P9}→={(P1，P2)，(P1，P3)，(P1，P4)，(P2，P5)，(P3，P5)，(P4，P6)，(P4，P7)，(P5，P8)，(P6，P8)，(P7，P9)，(P8，P9)}

应当注意，前趋图中必须不存在循环，但在图2-2（b）中却有这下述的前趋关系：

S2→S3，S3→S2

显然，这种前趋关系是不可能满足的。

2.1.3 程序的并发执行及其特征

1、程序的并发执行

输入程序在输入第一个程序后，在计算程序对该程序进行计算的同时，可由输入程序再输入第二个程序，从而使第一个程序的计算操作可与第二个程序的输入操作并发执行。一般来说，输入程序在输入第 i+1个程序时，计算程序可能正在对第 i 个程序进行计算，而答应程序正在打印第 i-1个程序的计算结果。

2、程序并发执行时的特征

1）间断性

程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系。相互制约将导致并发程序具有“执行——暂停——执行”这种间断性的活动规律。

2）失去封闭性

程序在并发执行时，是多个程序共享系统中的各种资源。因而这些资源的状态将有多个程序来改变，致使程序的运行失去了封闭性。这样，某程序在执行时，必然会受到其他程序的影响。

3）不可再现性

程序在并发执行时，失去了封闭性，计算结果已与并发程序的执行速度有关，从而使程序的执行失去了可再现性，亦即，程序经过多次执行后，虽然它们执行时的环境和初始条件相同，但得到的结果却各不相同。

2.1.4 进程的特征与状态

1、进程的特征和定义

1）结构特征

通常的程序是不能并发执行的。为使程序（含数据）能独立运行，应为之配置一进程控制块，即 PCB（Process Control Block）：而由程序段、相关的数据段和 PCB 三部分便构成了进程实体。在早期的 UNIX 版本中，把这三部分总称为“进程映像”。在许多情况下所说的进程，实际上是指进程实体，如，所谓创建进程，实质上是创建进程实体中的 PCB；而撤销进程，实质上是撤销进程的 PCB。

2）动态性

进程的实质是进程实体的一次执行过程，因此，动态性是进程的最基本特征。进程实体有一定的生命期，而程序则只是一组有序指令的集合，并存放区某种介质上，其本身并不具有运动的含义，因而是静态的。

3）并发性

并发性是指多个进程实体同存于内存中，且能在一段时间内同时运行。并发性是进程的重要特征，同时也成为 OS 的重要特征。引入进程的目的也正是为了使其进程实体能和其它进程实体并发执行；而程序（没有建立 PCB）是不能进行并发执行的。

4）独立性

在传统的 OS 中，独立性是指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。凡未建立 PCB 的程序都不能作为一个独立的单位参与运行

5）异步性

这是指进程按各自独立、不可预知的速度向前推进，或说进程实体按异步方式运行。

①进程是程序的一次执行

②进程是一个程序及其数据在处理机上顺序执行时所发生的活动

③进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

在引入了进程实体的概念后，我们可以把传统的 OS 中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。

2、进程的三种基本状态

1）就绪状态

当进程已分配到除 CPU 以外的所有必要资源后，只要再获得 CPU，便可立即执行，进程这时的状态称为就绪状态。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。

2）执行状态

进程已获得 CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态；在多处理机系统中，则有多个进程处于执行状态。

3）阻塞状态

正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行收到阻塞，把这种暂停状态成为阻塞状态，有时也称为等待状态或封锁状态。

致使进程阻塞的典型事件有：请求 I/O，申请缓冲空间等。

3、挂起状态

1）引入挂起状态的原因

①终端用户的请求

②父进程请求

③负荷调节的需要

④操作系统的需要

2）进程状态的转换

①活动就绪→静止就绪

②活动阻塞→静止阻塞

③静止就绪→活动就绪

④静止阻塞→活动阻塞

4、创建状态和终止状态

1）创建状态

创建一个进程一般要通过两个步骤：首先，为一个新进程创建 PCB，并填写必要的管理信息；其次，把该进程转入就绪状态并插入就绪队列中，当一个新进程被创建时，系统已为其分配了 PCB，填写了进程标识等信息，但由于该进程所必须的资源或其他信息，如主存资源尚未分配时等，一般而言，此时的进程已拥有了自己的 PCB，但进程自身还未进入主存，即创建工作尚未完成，进程还不能被调度运行，其所处的状态就是创建状态。

引入创建状态，是为了保证进程的调度必须在创建工作完成后进行，以确保对进程控制块操作的完整性。同时，创建状态的引入，也增加了管理的灵活性，操作系统可以根据系统性能或主存容量的限制，推迟创建状态进程的提交。对于处于创建状态的进程，获得了其所必须的资源，以及对其 PCB 初始化工作完成后，进程状态便可由创建状态转入就绪状态。

2）终止状态

进程的终止也要通过两个步骤：首先等待操作系统进行善后处理，然后将其 PCB 清零，并将 PCB 空间返还系统。当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。进入终止状态的进程以后不能再执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统计数据，供其他进程收集。一旦其他进程完成了对终止状态进程的信息提取之后，操作系统将删除该进程。

如图2-8所示，引进创建和终止状态后，在进程状态转换时，相比较2-7所示的进程五状态而言，需要增加考虑下面的几种情况。

①NULL→创建：一个新进程产生时，该进程处于创建状态。

②创建→活动就绪：在当前系统的性能和内存的容量均允许的情况下，完成对进程创建的必要操作后，相应的系统进程将进程的状态转换为活动就绪状态。

③创建→静止就绪：考虑到系统当前资源状况和性能要求，并不分配给新建进程所需资源，主要是主存资源，相应的系统进程将进程状态转换为静止就绪状态，对换到外存，不再参与调度，此时进程创建工作尚未完成。

④执行→终止：当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，进程即进入终止状态。

2.1.5 进程控制块

1、进程控制块的作用

为了描述和控制进程的运行，系统为每个进程定义了一个数据结构——进程控制块 PCB（Process Control Block），它是进程实体的一部分，是操作系统中最重要的记录数据结构。PCB 中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。

进程控制块的作用是使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。或者说，OS 是根据 PCB 来对并发执行的进程进行控制和管理的。

在进程的整个生命期中，系统总是通过 PCB 对进程进行控制的，亦即，系统时根据进程的 PCB 而不是任何别的什么而感知到该进程的存在的，所以说，PCB 是进程存在的唯一标志。

2、进程控制块中的信息

1）进程标识符

①内部标识符：在所有的操作系统中，都为了每一个进程赋予了一个唯一的数字标识符，它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。

②外部标识符：它由创建者提供，通常是由字母、数字组成，往往是由用户（进程）在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，还可以设置用户标识，以指示拥有该进程的用户。

2）处理及状态

处理机状态信息主要是由处理机的各种寄存器中的内容组成的。处理机在运行时，许多信息都放在寄存器中，当处理机被中断时，所有这些信息都必须保存在 PCB 中，以便在该进程重新执行时，能从断点继续执行。这些寄存器包括：①通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有8~32个通用寄存器，在 RISC 结构的计算机中可超过100个；②指令计数器，其中存放了要访问的下一条指令的地址；③程序状态字 PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；④用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址，栈指针指向该栈的栈顶。

3）进程调度信息

在 PCB 中还存放一些与进程调度和进程对换有关的信息，包括：①进程状态，指明进程的当前状态，作为进程调度和对换时的依据；②进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高德进程优先获得处理机；③进程调度所需的其他信息，它们与所采用的进程调度算法有关，比如，进程已等待 CPU 的时间总和、进程已执行的时间总和等；④事件，指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。

4）进程控制信息

进程控制信息包括：①程序和数据的地址，指进程的程序和数据所在的内存或外存地址，以便再调度到该进程执行时，能从 PCB 中找到其程序和数据；②进程同步和通信机制，指实现进程同步和进程通信时必须的机制，如消息队列指针，信号量等，它们可能全部或部分地放在 PCB 中；③资源清单，即一张列出了出 CPU 以外的、进程所需的全部资源及已经分配到该进程的资源的清单；④链接指针，它给出了本进程（PCB）所在队列中的下一个进程的 PCB 的首地址。

3、进程控制块的组织方式

1）链接方式

把具有同一状态的 PCB，用其中的链接字链接成一个队列。可以形成就绪队列、若干个阻塞队列和空白队列等。对其中的就绪队列常按进程优先级的高低排列，把优先级高的进程的 PCB 排在队列前面。此外，也可根据阻塞原因的不同把处于阻塞状态的进程的 PCB 排成等待 I/O 操作完成的队列和等待分配内存的队列等。如图：

2）索引方式

系统根据所有进程的状态建立几张索引表。例如，就绪索引表、阻塞索引表等，并把各索引表在内的首地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个 PCB 在 PCB 表中的地址。如图：示出了索引方式的 PCB 组织。