1 第二章 进程的描述与控制 第二章 进程的描述与控制 2.1 前趋图和程序执行 2.2 进程的描述 2.3 进程控制 2.4 进程同步 2.5 经典进程的同步问题 2.6 进程通信 2.7 线程(Threads)的基本概念 2.8 线程的实现 习题 2 第二章 进程的描述与控制 2.1 前趋图和程序执行 在早期未配置OS的系统和单道批处理系统中，程序的执 行方式是顺序执行，即在内存中仅装入一道用户程序，由它 独占系统中的所有资源，只有在一个用户程序执行完成后， 才允许装入另一个程序并执行可见，这种方式浪费资源、 系统运行效率低等缺点 3 第二章 进程的描述与控制 2.1.1 前趋图 为了能更好地描述程序的顺序和并发执行情况，我们先 介绍用于描述程序执行先后顺序的前趋图所谓前趋图 (Precedence Graph)，是指一个有向无循环图，可记为 DAG(Directed Acyclic Graph)，它用于描述进程之间执行的 先后顺序图中的每个结点可用来表示一个进程或程序段， 乃至一条语句，结点间的有向边则表示两个结点之间存在的 偏序(Partial Order)或前趋关系(Precedence Relation)。
4 第二章 进程的描述与控制 进程(或程序)之间的前趋关系可用“→”来表示，如果进 程Pi和Pj存在着前趋关系，可表示为(Pi，Pj)∈→，也可写成 Pi→Pj，表示在Pj开始执行之前Pi 必须完成此时称Pi是Pj的 直接前趋，而称Pj是Pi的直接后继在前趋图中，把没有前 趋的结点称为初始结点(Initial Node)，把没有后继的结点称 为终止结点(Final Node)此外，每个结点还具有一个重量 (Weight)，用于表示该结点所含有的程序量或程序的执行 时间 5 第二章 进程的描述与控制 在图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)} 6 第二章 进程的描述与控制 应当注意，前趋图中是不允许有循环的，否则必然会产 生不可能实现的前趋关系。
如图2-1(b)所示的前趋关系中就 存在着循环它一方面要求在S3开始执行之前，S2必须完成 ，另一方面又要求在S2开始执行之前，S3必须完成显然， 这种关系是不可能实现的 S2→S3，S3→S2 7 第二章 进程的描述与控制 图2-1 前趋图 8 第二章 进程的描述与控制 2.1.2 程序顺序执行 1. 程序的顺序执行 通常，一个应用程序由若干个程序段组成，每一个程序 段完成特定的功能，它们在执行时，都需要按照某种先后次 序顺序执行，仅当前一程序段执行完后，才运行后一程序段 例如，在进行计算时，应先运行输入程序，用于输入用户 的程序和数据；然后运行计算程序，对所输入的数据进行计 算；最后才是运行打印程序，打印计算结果我们用结点 (Node)代表各程序段的操作(在图2-1中用圆圈表示)，其中I代 表输入操作，C代表计算操作，P为打印操作，用箭头指示操 作的先后次序 9 第二章 进程的描述与控制 这样，上述的三个程序段间就存在着这样的前趋关系： 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)所示的顺序执行 。
10 第二章 进程的描述与控制 图2-2 程序顺序执行的前趋图 11 第二章 进程的描述与控制 2. 2. 程序顺序执行时的特征程序顺序执行时的特征 由上所述可以得知，在程序顺序执行时，具有这样三个 特征：① 顺序性：指处理机严格地按照程序所规定的顺序执 行，即每一操作必须在下一个操作开始之前结束；② 封闭性 ：指程序在封闭的环境下运行，即程序运行时独占全机资源 ，资源的状态(除初始状态外)只有本程序才能改变它，程序 一旦开始执行，其执行结果不受外界因素影响；③ 可再现性 ：指只要程序执行时的环境和初始条件相同，当程序重复执 行时，不论它是从头到尾不停顿地执行，还是“停停走走”地 执行，都可获得相同的结果程序顺序执行时的这种特性， 为程序员检测和校正程序的错误带来了很大的方便 12 第二章 进程的描述与控制 2.1.3 程序并发执行 1. 程序的并发执行 我们通过一个常见的例子来说明程序的顺序执行和并发 执行在图2-2中的输入程序、计算程序和打印程序三者之 间，存在着Ii→Ci→Pi这样的前趋关系，以至对一个作业的输 入、计算和打印三个程序段必须顺序执行但若是对一批作 业进行处理时，每道作业的输入、计算和打印程序段的执行 情况如图2-3所示。
13 第二章 进程的描述与控制 图2-3 程序并发执行时的前趋图 14 第二章 进程的描述与控制 由图2-3可以看出，存在前趋关系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 可画出图2-4所示的前趋关系可以看出：S3必须在a和b 被赋值后方能执行；S4必须在S3之后执行；但S1和S2则可以 并发执行，因为它们彼此互不依赖 15 第二章 进程的描述与控制 图2-4 四条语句的前趋关系 16 第二章 进程的描述与控制 2. 程序并发执行时的特征 在引入了程序间的并发执行功能后，虽然提高了系统的 吞吐量和资源利用率，但由于它们共享系统资源，以及它们 为完成同一项任务而相互合作，致使在这些并发执行的程序 之间必将形成相互制约的关系，由此会给程序并发执行带来 新的特征 (1) 间断性 (2) 失去封闭性 (3) 不可再现性 17 第二章 进程的描述与控制 2.2 进 程 的 描 述 2.2.1 进程的定义和特征 1. 进程的定义 在多道程序环境下，程序的执行属于并发执行，此时它 们将失去其封闭性，并具有间断性，以及其运行结果不可再 现性的特征。
由此，决定了通常的程序是不能参与并发执行 的，否则，程序的运行也就失去了意义为了能使程序并发 执行，并且可以对并发执行的程序加以描述和控制，人们引 入了“进程”的概念 18 第二章 进程的描述与控制 对于进程的定义，从不同的角度可以有不同的定义，其 中较典型的定义有： (1) 进程是程序的一次执行 (2) 进程是一个程序及其数据在处理机上顺序执行时所 发生的活动 (3) 进程是具有独立功能的程序在一个数据集合上运行 的过程，它是系统进行资源分配和调度的一个独立单位 19 第二章 进程的描述与控制 2. 进程的特征 进程和程序是两个截然不同的概念，除了进程具有程序 所没有的PCB结构外，还具有下面一些特征： (1) 动态性 (2) 并发性 (3) 独立性 (4) 异步性 20 第二章 进程的描述与控制 2.2.2 进程的基本状态及转换 1. 进程的三种基本状态 由于多个进程在并发执行时共享系统资源，致使它们在 运行过程中呈现间断性的运行规律，所以进程在其生命周期 内可能具有多种状态一般而言，每一个进程至少应处于以 下三种基本状态之一： (1) 就绪(Ready)状态 (2) 执行(Running)状态。
(3) 阻塞(Block)状态 21 第二章 进程的描述与控制 2. 三种基本状态的转换 进程在运行过程中会经常发生状态的转换例如，处于 就绪状态的进程，在调度程序为之分配了处理机之后便可执 行，相应地，其状态就由就绪态转变为执行态；正在执行的 进程(当前进程)如果因分配给它的时间片已完而被剥夺处理 机暂停执行时，其状态便由执行转为就绪；如果因发生某事 件，致使当前进程的执行受阻(例如进程访问某临界资源， 而该资源正被其它进程访问时)，使之无法继续执行，则该 进程状态将由执行转变为阻塞图2-5示出了进程的三种基 本状态，以及各状态之间的转换关系 22 第二章 进程的描述与控制 图2-5 进程的三种基本状态及其转换 23 第二章 进程的描述与控制 3. 创建状态和终止状态 1) 创建状态 如前所述，进程是由创建而产生创建一个进程是个很 复杂的过程，一般要通过多个步骤才能完成：如首先由进程 申请一个空白PCB，并向PCB中填写用于控制和管理进程的 信息；然后为该进程分配运行时所必须的资源；最后，把该 进程转入就绪状态并插入就绪队列之中但如果进程所需的 资源尚不能得到满足，比如系统尚无足够的内存使进程无法 装入其中，此时创建工作尚未完成，进程不能被调度运行， 于是把此时进程所处的状态称为创建状态。
24 第二章 进程的描述与控制 2) 终止状态 进程的终止也要通过两个步骤：首先，是等待操作系统 进行善后处理，最后将其PCB清零，并将PCB空间返还系统 当一个进程到达了自然结束点，或是出现了无法克服的错 误，或是被操作系统所终结，或是被其他有终止权的进程所 终结，它将进入终止状态进入终止态的进程以后不能再执 行，但在操作系统中依然保留一个记录，其中保存状态码和 一些计时统计数据，供其他进程收集一旦其他进程完成了 对其信息的提取之后，操作系统将删除该进程，即将其PCB 清零，并将该空白PCB返还系统图2-6示出了增加了创建状 态和终止状态后进程的五种状态及转换关系图 25 第二章 进程的描述与控制 图2-6 进程的五种基本状态及转换 26 第二章 进程的描述与控制 2.2.3 挂起操作和进程状态的转换 1. 挂起操作的引入 引入挂起操作的原因，是基于系统和用户的如下需要： (1) 终端用户的需要 (2) 父进程请求 (3) 负荷调节的需要 (4) 操作系统的需要 27 第二章 进程的描述与控制 2. 引入挂起原语操作后三个进程状态的转换 在引入挂起原语Suspend和激活原语Active后，在它们的 作用下，进程将可能发生以下几种状态的转换： (1) 活动就绪→静止就绪。
(2) 活动阻塞→静止阻塞 (3) 静止就绪→活动就绪 (4) 静止阻塞→活动阻塞 28 第二章 进程的描述与控制 3. 引入挂起操作后五个进程状态的转换 如图2-8示出了增加了创建状态和终止状态后具有挂起 状态的进程状态及转换图 如图2-8所示，引进创建和终止状态后，在进程状态转 换时，与图2-7所示的进程五状态转换相比较，要增加考虑 下面的几种情况： (1) NULL→创建： (2) 创建→活动就绪： (3) 创建→静止就绪： (4) 执行→终止： 29 第二章 进程的描述与控制 图2-7 具有挂起状态的进程状态图 30 第二章 进程的描述与控制 图2-8 具有创建、终止和挂起状态的进程状态图 31 第二章 进程的描述与控制 2.2.4 进程管理中的数据结构 1. 操作系统中用于管理控制的数据结构 在计算机系统中，对于每个资源和每个进程都设置了一 个数据结构，用于表征其实体，我们称之为资源信息表或进 程信息表，其中包含了资源或进程的标识、描述、状态等信 息以及一批指针通过这些指针，可以将同类资源或进。