|
|
|
|
|
|
|
前趋图是一个有向无循环图，由结点和有向边组成，结点代表各程序段的操作，而结点间的有向边表示两个程序段操作之间存在的前趋关系（→）。程序段Pi和Pj的前趋关系表示成Pi→Pj，其中，Pi是Pj的前趋，Pj是Pi的后继，其含义是Pi执行结束后Pj才能执行。例如，下图为3个程序段，其中输入是计算的前驱（计算是输入的后继），输入结束才能进行计算；计算是输出的前驱，计算结束才能进行输出。
|
|
|
|
|
|
|
|
程序顺序执行时的主要特征包括顺序性、封闭性和可再现性。
|
|
|
|
|
|
若在计算机系统中采用多道程序设计技术，则主存中的多道程序可处于并发执行状态。对于上述有3个程序段的作业类，虽然每个作业有前趋关系的各程序段不能在CPU和输入／输出各部件并行执行，但是同一个作业内没有前趋关系的程序段或不同作业的程序段可以分别在CPU和各输入／输出部件上并行执行。例如，某系统中有一个CPU、一台输入设备和一台输出设备，每个作业具有3个程序段，输入I、计算Ci和输出Pi（i=l，2，3）。下图为3个作业的各程序段并发执行的前驱图，图中的前驱关系可记为：
|
|
|
|
→=｛I1→C1，I1→I2，I2→C2，I2→I3，I3→C3，C1→P1，C1→C2，C2→P2，C2→C3，C3→P3，P1→P2，P2→P3｝
|
|
|
|
|
|
|
|
从上图中可以看出，I2与C1并行执行；I3、C2与P1并行执行；C3与P2并行执行。其中，I2、I3受到I1的间接制约，C2、C3受到C1的间接制约，P2、P3受到P1的间接制约，而C1、P1受到I1的直接制约，等等。
|
|
|
|
|
|
|
|
|
|
|
|
例如，两个并发执行的程序段完成交通流量的统计，其中，“观察者”P1识别通过的车辆数，“报告者”P2定时将观察者的计数值清0。程序实现如下：
|
|
|
|
|
|
对于上例，由于程序可并发执行，所以可能有以下3种执行序列：
|
|
|
|
①COUNT:=COUNT+1；PRINT COUNT；COUNT:=0
|
|
|
|
②PRINT COUNT；COUNT:=0；COUNT:=COUNT+1
|
|
|
|
③PRINT COUNT；COUNT:=COUNT+1；COUNT:=0
|
|
|
|
假定COUNT的某个循环的初值为n，那么这3种执行序列得到的COUNT结果不同，如下表所示。
|
|
|
|
|
|
|
|
这种不正确结果的发生是因为两个程序P1和P2共享变量COUNT引起的，即程序并发执行破坏了程序的封闭性和可再现性，使得程序和执行程序的活动不再一一对应。为了解决这一问题，需要研究进程间的同步与互斥问题。
|
|
|
|
|
|
进程是程序的一次执行，该程序可以和其他程序并发执行。进程通常是由程序、数据和进程控制块（Process Control Block，PCB）组成的。
|
|
|
|
（1）PCB。PCB是进程存在的唯一标志，其主要内容如下表所示。
|
|
|
|
|
|
|
|
（2）程序。程序部分描述了进程需要完成的功能。假如一个程序能被多个进程同时共享执行，那么这一部分就应该以可再入（纯）码的形式编制，它是程序执行时不可修改的部分。
|
|
|
|
（3）数据。数据部分包括程序执行时所需的数据及工作区。该部分只能为一个进程所专用，是进程的可修改部分。
|
|
|
|
|
|
|
|
在多道程序系统中，进程在处理器上交替运行，状态也不断地发生变化，因此进程一般有3种基本状态：运行、就绪和阻塞。下图显示了进程基本状态及其转换，也称三态模型。
|
|
|
|
|
|
|
|
（1）运行。当一个进程在处理机上运行时，则称该进程处于运行状态。显然，对于单处理机系统，处于运行状态的进程只有一个。
|
|
|
|
（2）就绪。一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态。
|
|
|
|
（3）阻塞。阻塞也称等待或睡眠状态，一个进程正在等待某一事件发生（例如请求I/O，等待I/O完成等）而暂时停止运行，这时即使把处理机分配给进程也无法运行，故称该进程处于阻塞状态。
|
|
|
|
|
|
事实上，对于一个实际的系统，进程的状态及其转换更复杂。例如，引入新建态和终止态构成了进程的五态模型，如下图所示。
|
|
|
|
|
|
|
|
其中，新建态对应于进程刚刚被创建时没有被提交的状态，并等待系统完成创建进程的所有必要信息。因为创建进程时分为两个阶段，第一个阶段为一个新进程创建必要的管理信息，第二个阶段让该进程进入就绪状态。由于有了新建态操作系统，往往可以根据系统的性能和主存容量的限制推迟新建态进程的提交。类似地，进程的终止也可分为两个阶段，第一个阶段等待操作系统进行善后处理，第二个阶段释放主存。
|
|
|
|
|
|
由于进程的不断创建，系统资源特别是主存资源已不能满足进程运行的要求。这时，就必须将某些进程挂起，放到磁盘对换区，暂时不参加调度，以平衡系统负载。或者是系统出现故障，或者是用户调试程序，也可能需要将进程挂起检查问题。下图是具有挂起状态的进程状态及其转换。
|
|
|
|
|
|
|
|
（1）活跃就绪。活跃就绪是指进程在主存并且可被调度的状态。
|
|
|
|
（2）静止就绪。静止就绪是指就绪进程被对换到辅存时的状态，它是不能被直接调度的状态，只有当主存中没有活跃就绪态进程，或者是挂起态进程具有更高的优先级时，系统将把挂起就绪态进程调回主存并转换为活跃就绪。
|
|
|
|
（3）活跃阻塞。活跃阻塞是指进程在主存，一旦等待的事件产生便进入活跃就绪状态。
|
|
|
|
（4）静止阻塞。静止阻塞是指阻塞进程对换到辅存时的状态，一旦等待的事件产生便进入静止就绪状态。
|
|
|
