进程描述与控制教程

1.进程的引入

在早期未配置OS的系统和单道批处理系统中，程序的执行方式是顺序执行，即在内存中仅装入一道用户程序，由它独占系统中的所有资源，只有在一个用户程序执行完成后，才允许装入另一个程序并执行。可见，这种方式浪费资源、系统运行效率低等缺点。由此出现了多道批处理系统。内存中可以同时装入多个程序，使其共享资源、并发执行。为了能使程序并发执行，并且可以对并发执行的程序加以描述和控制，于是引入了“进程” 。

1.1前趋图

为了能更好地描述程序的顺序和并发执行情况，我们先介绍用于描述程序执行先后顺序的前趋图。所谓前趋图(Precedence Graph)，是指一个有向无循环图，可记为DAG(Directed Acyclic Graph)，它用于描述进程之间执行的先后顺序。图中的每个结点可用来表示一个进程或程序段，乃至一条语句，结点间的有向边则表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)。

进程(或程序)之间的前趋关系可用“→”来表示，如果进程Pi和Pj存在着前趋关系，可表示为(Pi，Pj)∈→，也可写成Pi→Pj，表示在Pj开始执行之前Pi 必须完成。此时称Pi是Pj的直接前趋，Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。此外，每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或程序的执行时间。

在图(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)}

应当注意，前趋图中是不允许有循环的，否则必然会产生不可能实现的前趋关系。如图(b)所示的前趋关系中就存在着循环。它一方面要求在S3开始执行之前，S2必须完成，另一方面又要求在S2开始执行之前，S3必须完成。显然，这种关系是不可能实现的。

1.2程序顺序执行

通常一个应用程序由若干个程序段组成，每一个程序段完成特定的功能，它们在执行时，都需要按照某种先后次序顺序执行，仅当前一程序段执行完后，才运行后一程序段。例如，在进行计算时，应先运行输入程序，用于输入用户的程序和数据；然后运行计算程序，对所输入的数据进行计算；最后才是运行打印程序，打印计算结果。我们用结点(Node)代表各程序段的操作，其中I代表输入操作，C代表计算操作，P为打印操作，用箭头指示操作的先后次序。

这样，上述的三个程序段间就存在着这样的前趋关系：Ii→Ci→Pi，其执行的顺序可用前趋图(a)描述。即使是一个程序段，也可能存在着执行顺序问题，下面示出了一个包含了三条语句的程序段：

S1: a :=x+y；S2: b :=a-5；S3: c :=b+1；其中，语句S2必须在语句S1后(即a被赋值)才能执行，语句S3也只能在b被赋值后才能执行，因此，三条语句存在着这样的前趋关系：S1→S2→S3，应按前趋图(b)所示的顺序执行。

由上所述可以得知，在程序顺序执行时，具有这样三个特征：

① 顺序性：指处理机严格地按照程序所规定的顺序执行，即每一操作必须在下一个操作开始之前结束；

② 封闭性：指程序在封闭的环境下运行，即程 序运行时独占全机资源，资源的状态(除初始状态外)只有本程序才能改变它，程序一旦开始执行，其执行结果不受外界因素影响；

③ 可再现性：指只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都可获得相同的结果。程序顺序执行时的这种特性，为程序员检测和校正程序的错误带来了很大的方便。

1.3程序并发执行

如上图中的输入程序、计算程序和打印程序三者之间，存在着Ii→Ci→Pi这样的前趋关系，以至对一个作业的输入、计算和打印三个程序段必须顺序执行。但若是对一批作业进行处理时，每道作业的输入、计算和打印程序段的执行情况如下图所示。

可以看出，存在前趋关系Ii→Ci，Ii→Ii+1，Ci→Pi，Ci→Ci+1，Pi→Pi+1，而Ii+1和Ci及Pi-1是重叠的，即在Pi-1和Ci以及Ii+1之间，不存在前趋关系，可以并发执行。

对于具有下述四条语句的程序段：

S1: a :=x+2 S2: b :=y+4 S3: c :=a+b S4: d :=c+b

可画出如下图所示的前趋关系。可以看出：S3必须在a和b被赋值后方能执行；S4必须在S3之后执行；但S1和S2则可以并发执行，因为它们彼此互不依赖。

在引入了程序间的并发执行功能后，虽然提高了系统的吞吐量和资源利用率，但由于它们共享系统资源，以及它们为完成同一项任务而相互合作，致使在这些并发执行的程序之间必将形成相互制约的关系，由此会给程序并发执行带来新的特征：(1) 间断性(2) 失去封闭性(3) 不可再现性。

2. 进 程 的 描 述

2.1 进程的定义和特征

1. 进程的定义

在多道程序环境下，程序的执行属于并发执行，此时它们将失去其封闭性，并具有间断性，以及其运行结果不可再现性的特征。由此，决定了通常的程序是不能参与并发执行的，否则，程序的运行也就失去了意义。为了能使程序并发执行，并且可以对并发执行的程序加以描述和控制，人们引入了“进程”的概念。

对于进程的定义，从不同的角度可以有不同的定义，其中较典型的定义有：

(1) 进程是程序的一次执行。

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

(3) 进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

进程（也称进程实体）由三部分组成：PCB(进程控制块)、程序段和相关数据段。

2. 进程的特征

进程和程序是两个截然不同的概念，除了进程具有程序所没有的PCB结构外，还具有下面一些特征：

(1) 动态性。 (2) 并发性。 (3) 独立性。 (4) 异步性。

2.2 进程的基本状态及转换

1. 进程的三种基本状态

由于多个进程在并发执行时共享系统资源，致使它们在运行过程中呈现间断性的运行规律，所以进程在其生命周期内可能具有多种状态。一般而言，每一个进程至少应处于以下三种基本状态之一：

(1) 就绪(Ready)状态。 (2) 执行(Running)状态。 (3) 阻塞(Block)状态。

2. 三种基本状态的转换

进程在运行过程中会经常发生状态的转换。例如，处于就绪状态的进程，在调度程序为之分配了处理机之后便可执行，相应地，其状态就由就绪态转变为执行态；正在执行的进程(当前进程)如果因分配给它的时间片已完而被剥夺处理机暂停执行时，其状态便由执行转为就绪；如果因发生某事件，致使当前进程的执行受阻(例如进程访问某临界资源，而该资源正被其它进程访问时)，使之无法继续执行，则该进程状态将由执行转变为阻塞。下图为进程的三种基本状态，以及各状态之间的转换关系：

3. 创建状态和终止状态

1) 创建状态

如前所述，进程是创建而生。创建一个进程是个很复杂的过程，一般要通过多个步骤才能完成：如首先由进程申请一个空白PCB，并向PCB中填写用于控制和管理进程的信息；然后为该进程分配运行时所必须的资源；最后，把该进程转入就绪状态并插入就绪队列之中。但如果进程所需的资源尚不能得到满足，比如系统尚无足够的内存使进程无法装入其中，此时创建工作尚未完成，进程不能被调度运行，于是把此时进程所处的状态称为创建状态。

2) 终止状态

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

2.3 挂起操作和进程状态的转换

1. 挂起操作的引入

引入挂起操作的原因，是基于系统和用户的如下需要：

(1) 终端用户的需要。 (2) 父进程请求。 (3) 负荷调节的需要。 (4) 操作系统的需要。

2. 引入挂起原语操作后三个进程状态的转换

在引入挂起原语Suspend和激活原语Active后，在它们的作用下，进程将可能发生以下几种状态的转换：

(1) 活动就绪→静止就绪。

(2) 活动阻塞→静止阻塞。

(3) 静止就绪→活动就绪。

(4) 静止阻塞→活动阻塞。

3. 引入挂起操作后五个进程状态的转换

引进创建和终止状态后，在进程状态转化时，要增加考虑下面几种情况：

(1) NULL→创建：(2) 创建→活动就绪：(3) 创建→静止就绪： (4) 执行→终止：

下图是具有挂起状态的进程状态图：

下图是具有创建、终止和挂起状态的进程状态图

2.4 进程管理中的数据结构

1. 操作系统中用于管理控制的数据结构

在计算机系统中，对于每个资源和每个进程都设置了一个数据结构，用于表征其实体，我们称之为资源信息表或进程信息表，其中包含了资源或进程的标识、描述、状态等信息以及一批指针。通过这些指针，可以将同类资源或进程的信息表，或者同一进程所占用的资源信息表分类链接成不同的队列，便于操作系统进行查找。

如下图所示，OS管理的这些数据结构一般分为以下四类：内存表、设备表、文件表和用于进程管理的进程表，通常进程表又被称为进程控制块PCB。

1.进程控制块PCB

PCB作为进程实体的一部分，记录操作系统所需的用于描述进程的当前情况以及管理进程运行的全部信息，是操作系统中最重要的记录型数据结构。通常认为创建进程就是创建一个PCB，销毁进程也就是销毁进程的PCB。

进程控制块PCB的作用：

(1) 作为独立运行基本单位的标志。

(2) 能实现间断性运行方式。

(3) 提供进程管理所需要的信息。

(4) 提供进程调度所需要的信息。

(5) 实现与其它进程的同步与通信。

总的来说，PCB的作用就是使一个能在多道程序环境下不能独立运行的程序成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。

2.PCB中主要包含以下四方面的信息：
1）进程标识符：用于唯一的标识某一个进程。一个进程通常有两种标识符：(1) 外部标识符。(2) 内部标识符。

2）处理机状态(又称处理机上下文)：主要由处理机的各种寄存器中的内容组成，当进程被切换时，处理机状态信息被保存起来以便重新执行时可以继续执行。
寄存器主要包括：
通用寄存器：用于暂存信息(大多数处理机有8~32个)；
指令计数器：存放将要访问的下一条指令的地址；
程序状态字PSW：是运算器的一部分，分两类：一种是体现当前指令结果如是否有进位、是否为零，另一种是存放控制信息如允许中断、跟踪标志等；
用户栈指针：每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址，栈指针则是指向该栈的栈顶。
3）进程调度信息：存储当前进程的进程状态、进程优先级、进程调度所需的其他信息和事件：

① 进程状态，指明进程的当前状态，它是作为进程调度和对换时的依据；

② 进程优先级，是用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；

③ 进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；

④ 事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。

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

3.PCB的组织方式：在一个系统中常有数百乃至上千个PCB，为了对他们加以有效的管理，应使用适当方式将其组织起来，目前常用的有以下三种组织方式：

1）线性：所有的PCB都组织在一张线性表中，该表的首地址放在内存的一个专用区域，每次使用都遍历整张表，适合进程数目较少的操作系统；

2）链接：将具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列，这样可以形成就绪队列、阻塞队列和空白队列等；

3）索引：即系统根据进程状态不同，建立几张索引表。

3. 进 程 控 制

进程控制是进程管理中最基本的功能，主要包括创建新进程、终止已完成的进程、将因发生异常情况而无法继续运行的进程置于阻塞状态、负责进程运行中的状态转换等功能。如当一个正在执行的进程因等待某事件而暂时不能继续执行时，将其转变为阻塞状态，而在该进程所期待的事件出现后，又将该进程转换为就绪状态等。进程控制一般是由OS的内核中的原语来实现的。

3.1操作系统内核

OS分为若干层次，通常将一些与硬件紧密相关的模块（如中断处理程序等）、各种常用设备的驱动程序以及运行频率较高的模块（如时钟管理、进程调度和许多模块所公用的一些基本操作），这些都常驻于内存，被称为OS内核。

其目的在于：
1）便于对这些软件进行保护，防止遭受其他应用程序的破坏
2）提高OS的运行效率
相应的，系统为保护OS本身或关键数据（如PCB等）免遭破坏，也将处理机的执行方式分为两种状态：系统态和内核态
1）系统态：又称为管态或内核态。它具有较高的特权，能执行一切命令，访问所有的寄存器和存储区；
2）用户态：又称为目态。具有较低的执行权，只能执行一部分命令或访问一部分寄存器和存储区。一般情况下，应用程序都是用户态，防止破坏OS
不同的OS内核之间都有不同程度的差异，但都具有以下两大功能：
1）支撑功能：提供给OS其他众多模块所需要的一些基本操作以支撑其工作，三中最基本的支撑功能是：中断处理、时钟管理和原语操作。
2）资源管理功能：包括进程管理、存储器管理、设备管理。

3.2 进程的创建

1. 进程的层次结构（（UNIX中是树状层次，Windows下所有进程没有层次结构））

在OS中，允许一个进程创建另一个进程，通常把创建进程的进程称为父进程，而把被创建的进程称为子进程。子进程可继续创建更多的孙进程，由此便形成了一个进程的层次结构。如在UNIX中，进程与其子孙进程共同组成一个进程家族(组)。子进程在被创建后可以继承父进程所有的资源，例如父进程打开的文件、父继承所分配到的缓冲区等。当子进程被撤销时就将所有从父进程那获得的资源还回给父进程，然而当父进程被撤销时，所有子进程也同样被撤销，将资源归还给OS。为表示进程之间的家族关系，PCB中的进程标识符中设置有家族表项。

2. 进程图

为了形象地描述一个进程的家族关系而引入了进程图(Process Graph)。所谓进程图就是用于描述进程间关系的一棵有向树，根节点是这个进程家族的祖先如下图所示：

3. 引起创建进程的事件

为使程序之间能并发运行，应先为它们分别创建进程。导致一个进程去创建另一个进程的典型事件有四类：

(1) 用户登录。 (2) 作业调度。 (3) 提供服务。 (4) 应用请求。

4.进程创建

当系统中出现了创建新进程的请求后，OS便调用进程创建原语Creat按以下步骤创建一个新的进程：
①申请空白PCB，为新进程申请获得唯一的数字标识符，并从PCB集合中索取一个空白PCB。
②为新进程分配其所需的资源：包括各种物理和逻辑资源，如内存、文件、I/O设备和CPU时间等。
③初始化进程控制块（PCB）：初始化标识信息、处理机状态信息和处理机控制信息（进程状态和优先级等）。
④如果进程就绪队列可以接纳新的该进程，就将进程加入就绪队列。

3.3 进程的终止

1. 引起进程终止(Termination of Process)的事件

(1) 正常结束：任何系统中都有一个表示进程已经运行完成的指示，运行到该指令时，就产生一个中断通知OS该进程已运行完毕；

(2) 异常结束：指进程运行中出现了无法解决的错误导致程序无法继续执行。产生的原因有：越界错、保护错（权限问题或访问方式非法）、非法指令、特权指令错、运行超时、等待超时、算术运算错、I/O故障；

(3) 外界干预 ：操作员或操作系统干预、父进程请求、父进程终止。

2. 进程的终止过程

如果系统中发生了要求终止进程的某事件，OS便调用进程终止原语，按下述过程去终止指定的进程：

(1) 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态；

(2) 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度；

(3) 若该进程还有子孙进程，还应将其所有子孙进程也都予以终止，以防它们成为不可控的进程；

(4) 将被终止进程所拥有的全部资源或者归还给其父进程，或者归还给系统；

(5) 将被终止进程(PCB)从所在队列(或链表)中移出，等待其它程序来搜集信息。

3.4 进程的阻塞与唤醒

1. 引起进程阻塞和唤醒的事件

有下述几类事件会引起进程阻塞或被唤醒：

(1) 向系统请求共享资源失败。 (2) 等待某种操作的完成。 (3) 新数据尚未到达。 (4) 等待新任务的到达。

2. 进程阻塞过程

正在执行的进程，如果发生了上述某事件，进程便通过调用阻塞原语block将自己阻塞。可见，阻塞是进程自身的一种主动行为。进入block过程后，由于该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞队列。最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态，按新进程的PCB中的处理机状态设置CPU的环境。

3. 进程唤醒过程

当被阻塞进程所期待的事件发生时，比如它所启动的I/O操作已完成，或其所期待的数据已经到达，则由有关进程(比如提供数据的进程)调用唤醒原语wakeup，将等待该事件的进程唤醒。wakeup执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。

3.5.进程的挂起（suspend）与激活（active）

1.挂起操作的引入：

1）终端用户的需要：当终端用户在运行程序期间发现有可疑问题，希望暂停程序的运行以便研究其执行情况或做一定的修改
2）父进程请求
3）符合调节的需要
4）操作系统的需要：有时希望挂起某些进程以便检查运行中的资源使用情况或进行记账

2.进程的挂起
当出现引起进程挂起的事件时，系统将利用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起

suspend()原语的执行过程：首先检查被挂起进程的状态，若处于活动就绪状态,便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。（内存到外存）

3.进程的激活

当发生激活进程的事件时，系统将利用激活原语active( )将指定进程激活

active()原语执行过程激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞

下面这张图要好好消化