前趋图和程序执行

1.前趋图（Precedence Graph），是指一个有向无循环图，可记为 DAG（Directed Acyclic Graph），它用于描述进程之间执行的先后顺序。

图中的每个结点可用来表示一个进程或程序段，乃至一条语句，结点间的有向边则表 示两个结点之间存在的偏序（Partial Order）或前趋关系（Precedence Relation）。（前趋图中是不允许有循环的，否则必然会产生不可能实现的前趋关系。）

若 (Pi，Pj) ∈→，可以写成Pi→Pj，则称Pi是Pj的直接前驱，Pj是Pi的直接后继。若存在一个序列Pi→Pj…→Pk，则称Pi是Pk的前驱(即前驱具有传递性)。在前趋图中，没有前驱的结点称为初始结点，没有后继的结点称为终止结点。

具有七个结点的前趋图

2.程序顺序执行

一个应用程序由若干个程序段组成，每一个程序段完成特定的功能，它们在执行时，都需要按照某种先后次序顺序执行，仅当前一程序段执行完后，才运行后一程序段。 在进行计算时，应先运行输入程序，用于输入用户的程序和数据；然后运行计算程序， 对所输入的数据进行计算；最后是运行打印程序，打印计算结果。

3.程序的顺序执行时的特征：

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

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

③可再现性：指只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都可获得相同的结果。

4.程序的并发执行

程序的并发执行是指若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的，即一个程序（或程序段）的执行尚未结束，另一个程序（或程序段）的执行已经开始。

5.程序并发执行时的特征：

①间断性：程序在并发执行时，由于它们共享资源，或为完成同一项任务而相互合作，致使并发程序之间形成了相互制约关系。

②失去封闭性：当系统中存在着多个可以并发执行的程序时，系统中的各种资源将为它们所共享，而这些资源的状态也由这些程序来改变，致使其中任一程序在运行时，其环境都必然会受到其它程序的影响。

③不可再现性：程序并发执行时，由于失去了封闭性，也将导致失去其运行结果的可再现性。

进程的概念

1.进程的定义

在多道程序环境下，允许多个程序并发执行，此时它们将失去封闭性，并具有间断性及不可再现性的特征。为了能使程序并发执行，并且可以对并发执行的程序加以描述和控制，人们引入了“进程”的概念。

为了使参与并发执行的程序（含数据）能独立地运行，必须为之配置一个专门的数据结构，称为进程控制块（Process Control Block，PGB）。系统利用PCB来描述进程的基本情况和运行状态，进而控制和管理进程。相应地，由程序段、相关数据段和PCB三部分便构成了进程实体（又称进程映像）。所谓创建进程，实质上是创建进程实体中的PCB；而撤销进程，实...

无