计算机操作系统(第4版)汤小丹-第2章详解.ppt

　　　　?2.1 前趋图和程序执行　　在早期未配置OS的系统和单道批处理系统中，程序的执行方式是顺序执行，即在内存中仅装入一道用户程序，由它独占系统中的所有资源，只有在一个用户程序执行完成后，才允许装入另一个程序并执行。可见，这种方式浪费资源、系统运行效率低等缺点。 2.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)，用于表示该结点所含有的程序量或程序的执行时间。 　　在图2-1(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-1(b)所示的前趋关系中就存在着循环。它一方面要求在S3开始执行之前，S2必须完成，另一方面又要求在S2开始执行之前，S3必须完成。显然，这种关系是不可能实现的。　　　　　　　　　S2→S3，S3→S2 图2-1 前趋图 2.1.2 程序顺序执行　　1. 程序的顺序执行　　通常，一个应用程序由若干个程序段组成，每一个程序段完成特定的功能，它们在执行时，都需要按照某种先后次序顺序执行，仅当前一程序段执行完后，才运行后一程序段。例如，在进行计算时，应先运行输入程序，用于输入用户的程序和数据；然后运行计算程序，对所输入的数据进行计算；最后才是运行打印程序，打印计算结果。我们用结点(Node)代表各程序段的操作(在图2-1中用圆圈表示)，其中I代表输入操作，C代表计算操作，P为打印操作，用箭头指示操作的先后次序。 　　这样，上述的三个程序段间就存在着这样的前趋关系：Ii→Ci→Pi，其执行的顺序可用前趋图2-2(a)描述。　　即使是一个程序段，也可能存在着执行顺序问题，下面示出了一个包含了三条语句的程序段：　　S1: a :=x+y；　　S2: b :=a-5；　　S3: c :=b+1；其中，语句S2必须在语句S1后(即a被赋值)才能执行，语句S3也只能在b被赋值后才能执行，因此，三条语句存在着这样的前趋关系：S1→S2→S3，应按前趋图2-2(b)所示的顺序执行。 图2-2　程序顺序执行的前趋图 　　2. 程序顺序执行时的特征　　由上所述可以得知，在程序顺序执行时，具有这样三个特征：① 顺序性：指处理机严格地按照程序所规定的顺序执行，即每一操作必须在下一个操作开始之前结束；② 封闭性：指程序在封闭的环境下运行，即程序运行时独占全机资源，资源的状态(除初始状态外)只有本程序才能改变它，程序一旦开始执行，其执行结果不受外界因素影响；③ 可再现性：指只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都可获得相同的结果。程序顺序执行时的这种特性，为程序员检测和校正程序的错误带来了很大的方便。 2.1.3　程序并发执行　　1. 程序的并发执行　　我们通过一个常见的例子来说明程序的顺序执行和并发执行。在图2-2中的输入程序、计算程序和打印程序三者之间，存在着Ii→Ci→Pi这样的前趋关系，以至对一个作业的输入、计算和打印三个程序段必须顺序执行。但若是对一批作业进行处理时，每道作业的输入、计算和打印程序段的执行情况如图2-3所示。 图2-3 程序并发执行时的前趋图 　　由图2-3可以看出，存在前趋关系Ii→