《计算机操作系统 第三章》由会员分享，可在线阅读，更多相关《计算机操作系统 第三章（176页珍藏版）》请在金锄头文库上搜索。
1、第3章 进程管理,3.1 进程的概念 3.2 进程的描述 3.3 进程状态及其转换 3.4 进程控制 3.5 进程互斥 3.6 进程同步 3.7 进程通信 3.8 死锁问题 3.9 线程 本章小结 习题,3.1 进程的概念 现代操作系统的重要特点是程序的并发执行，及系统所拥有的资源被共享和系统的用户随机地使用。这三个特点是互相联系和互相依赖的，它们是互相独立的用户如何使用有限的计算机系统资源的反映。通常，操作系统的重要任务之一是使用户充分、有效地利用系统资源。采用一个什么样的概念，来描述计算机程序的执行过程和作为资源分配的基本单位才能充分反映操作系统的执行并发、资源共享及用户随机的特点呢？这个
2、概念就是进程。为了讲清进程的概念，以及引入进程概念的必要性等，下面将从操作系统的特点讲起。,3.1.1 程序的并发执行 1. 程序的顺序执行 程序是一个在时间上按严格次序前后相继的操作序列，是一个静态的概念。程序体现了编程人员要求计算机完成所要求功能时所应该采取的顺序步骤。显然，一个程序只有经过执行才能得到最终结果，且一般用户在编写程序时不考虑在自己的程序执行过程中还有其他用户程序存在这一事实。另外，计算机 CPU是通过时序脉冲来控制顺序执行指令的。其执行过程可以描述为： Repeat IR M pc pc pc+1 Execute (instruction in IR) Until CPU
3、halt,这里IR为指令寄存器，pc为程序计数器，M为存储器。显然，程序的顺序性与计算机硬件的顺序性是一致的。我们把一个具有独立功能的程序独占处理机直至最终结束的过程称为程序的顺序执行。程序的顺序执行具有如下特点： (1) 顺序性 程序顺序执行时，其执行过程可看作一系列严格按程序规定的状态转移过程。 (2) 封闭性 程序执行得到的最终结果由给定的初始条件决定，不受外界因素的影响。 (3) 可再现性 只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果。,2. 多道程序系统中程序执行环境的变化 在许多情况下，需要计算机能够同时处理多个具有独立功能的程序。批处理系统、分时系统、实时系
4、统以及网络与分布式系统等都是这样的系统。这样的执行环境具有下述三个特点： (1) 独立性 每道程序都是逻辑上独立的，它们之间不存在逻辑上的制约关系。 (2) 随机性 在多道程序环境下，特别是在多用户环境下，程序和数据的输入与执行开始时间都是随机的。 (3) 资源共享 资源共享将导致对进程执行速度的制约。,3. 程序的并发执行 (1) 什么是程序的并发执行 所谓并发执行，是为了增强计算机系统的处理能力和提高资源利用率所采取的一种同时操作技术。程序的并发执行可进一步分为两种：第一种是多道程序系统的程序执行环境变化所引起的多道程序的并发执行。由于资源的有限性，多道程序的并发执行总是伴随着资源的共享与
5、竞争。从而制约各道程序的执行速度。而无法作到在微观上，也就是在指令级上的同时执行。因此，尽管多道程序的并发执行在宏观上是同时进行的，但在微观上仍是顺序执行的；第二种并发执行是在某道程序的几个程序段中（例如几个程序），包含着一部分可以同时执行或顺序颠倒执行的代码。例如语句：,read (a) ； read (b) ； 它们既可以同时执行，也可颠倒次序执行。对于这样的语句，同时执行不会改变顺序程序所具有的逻辑性质。因此，可以采用并发执行来充分利用系统资源以提高计算机的处理能力。 程序的并发执行可总结为：一组在逻辑上互相独立的程序或程序段在执行过程中，其执行时间在客观上互相重叠，即一个程序段的执行尚
6、未结束，另一个程序段的执行已经开始的这种执行方式。 程序的并发执行不同于程序的并行执行。程序的并行执行是指一组程序按独立的、异步的速度执行。并行执行不等于时间上的重叠。可以将并发执行过程描述为：,S0 Cobegin P1；P2；. Pn Coend Sn 这里，S0，Sn分别表示并发程序段P1，P2，Pn开始执行前和并发执行结束后的语句。P1，P2，Pn也可以由同一程序段中的不同语句组成。1966年Bernstein 提出了两相邻语句S1，S2可以并发执行的条件： 将程序中任一语句Si划分为两个变量的集合R(Si)和W(Si)。其中 R(Si)=a1 a2 am，aj(j=1，m) 是语句S
7、i在执行期间必须对其进行读写的变量；,W(Si)=b1 b2 bn，bj(j=1，n) 是语句Si在执行期间必须对其进行修改、访问的变量； 如果对于语句S1和S2，有 R(S1) W(S2)=， W(S1) R(S2)=， W(S1) W(S2)= 同时成立，则语句S1和S2是可以并发执行的。,(2) 程序的并发执行所带来的影响 程序的并发执行充分地利用了系统资源，从而提高了系统的处理能力，这是并发执行好的一方面。但是，正如前面所提到的那样，由于系统资源有限，程序的并发执行必然导致资源共享和资源竞争，从而改变程序的执行速度。如果并发执行的各程序段中语句或指令满足上述Bernstein 的三个条
8、件，则认为并发执行不会对执行结果的封闭性和可再现性产生影响（证明略）。但在一般情况下，系统要判定并发执行的各程序段是否满足Bernstein 条件是相当困难的。从而，如果并发执行的程序段不按照特定的规则和方法进行资源共享和竞争，则其执行结果将不可避免地失去封闭性和可再现性。下面的例子说明了这一点。,图3.1 堆栈的取数和存数过程,例：设有堆栈S，栈指针top，栈中存放内存中相应数据块地址（如图3.1(a)）设有两个程序段getaddr(top)和reladdr(blk)，其中getaddr(top)从给定的top所指栈中取出相应的内存数据块地址，而reladdr(blk)则将内存数据块地址bl
9、k放入堆栈S中。getaddr(top)和reladdr(blk)可分别描述为： procedure getaddr(top) begin local r r (top) top top-1 return(r) end procedure reladdr(blk),begin top top+1 (top) blk end 显然，如果上例中的getaddr 和 reladdr程序段进行顺序执行，其执行结果具有封闭性和可再现性。但如果对这两个程序段采用并发执行，则在单CPU系统中，将有可能出现下述情况：,首先，程序段 reladdr开始执行，准备释放内存数据块地址入栈。然而，当reladdr 执
10、行到top top+1语句时（如图3.1(b)），程序段getaddr 也开始执行且抢占了处理机，从而程序段reladdr 停在top top+1处等待处理机。getaddr 程序段的执行目的是要从对应的堆栈指针top 所指的栈格中取出一个内存数据块地址，显然，由于reladdr 程序段的执行将指针top 升高了一格且未放进适当的数据，getaddr 的执行结果是失败的（如图3.1(c)）。另外，如果改变程序段getaddr和 reladdr的执行顺序或执行速度，又可得到不同的执行结果。这说明了如下问题：在某些情况下，程序的并发执行使得其执行结果不再具有封闭性和可再现性，且可能造成程序出现错误
11、。,上例中的程序段并发执行出现错误结果是由于两程序段共享资源堆栈S，从而使得执行结果受执行速度影响。一般情况下，并发执行的各程序段如果共享软、硬件资源，都会造成其执行结果受执行速度影响的局面。显然，这是程序设计人员不希望看到的。为了使得在并发执行时不出现错误结果，必须采取某些措施来制约、控制各并发程序段的执行速度。这在操作系统程序设计中尤其重要，因为操作系统用户随机性与各道程序逻辑独立的特点将使得每个用户程序所使用的软、硬件资源都受到其他并发程序的共享和竞争，从而得到非预料的或不正确的结果。为了控制和协调各程序段执行过程中的软、硬件资源的共享和竞争，显然，必须应该有一个描述各程序段执行过程和共
12、享资源的基本单位。,从上述讨论可以看出，由于程序的顺序性、静态性以及孤立性，用程序段作为描述其执行过程和共享资源的基本单位既增加操作系统设计和实现的复杂性，也无法反映操作系统所应该具有的程序段执行的并发性、用户随机性，以及资源共享等特征。也就是说，用程序作为描述其执行过程以及共享资源的基本单位是不合适的。需要有一个能描述程序的执行过程且能用来共享资源的基本单位。这个基本单位被称为进程（或任务）。,3.1.2 进程的定义 进程的概念是60年代初期，首先在MIT 的 Multics系统和IBM 的 TSS/360系统中引用的。从那以来，人们对进程下过许多各式各样的定义。 (1) 进程是可以并行执行
13、的计算部分（S.E.Madnick，J.T.Donovan）； (2) 进程是一个独立的可以调度的活动（E.Cohen，D.Jofferson）； (3) 进程是一抽象实体，当它执行某个任务时，将要分配和释放各种资源（P.Denning）； (4) 行为的规则叫程序，程序在处理机上执行时的活动称为进程（E.W.Dijkstra）；,(5) 一个进程是一系列逐一执行的操作，而操作的确切含义则有赖于以何种详尽程度来描述进程（Brinch Hansen），等等。 以上进程的定义，尽管各有侧重，但在本质上是相同的。即主要注重进程是一个动态的执行过程这一概念。也可以这样定义进程：一个具有独立功能的程序对
14、某个数据集在处理机上的执行过程和分配资源的基本单位。这里，程序指一组操作序列，而数据集则是接受程序规定操作的一组存储单元的内容。 进程和程序是两个既有联系又有区别的概念，它们的区别和关系可简述如下：,(1) 进程是一个动态概念，而程序则是一个静态概念。程序是指令的有序集合，没有任何执行的含义。而进程则强调执行过程，它动态地被创建，并被调度执行后消亡。 (2) 进程具有并行特征，而程序没有。由进程的定义可知，进程具有并行特征的两个方面，即独立性和异步性。也就是说，在不考虑资源共享的情况下，各进程的执行是独立的，执行速度是异步的。显然，由于程序不反映执行过程，所以不具有并行特征。 (3) 进程是竞
15、争计算机系统资源的基本单位，从而其并行性受到系统自己的制约。这里，制约就是对进程独立性和异步性的限制。 (4) 不同的进程可以包含同一程序，只要该程序所对应的数据集不同。,3.1.3 作业和进程的关系 作业是用户需要计算机完成某项任务时要求计算机所作工作的集合。进程是已提交完毕程序的执行过程的描述，是资源分配的基本单位。区别与关系： (1) 作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行。而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于内存中。 (2) 一个作业可由多个进
16、程组成。且必须至少由一个进程组成，但反过来不成立。 (3) 作业的概念主要用在批处理系统中。而进程的概念则用在几乎所有的多道系统中。,3.2 进程的描述 从处理机的活动角度来看，又如何识别描述程序执行活动的进程呢？显然，系统中需要有描述进程存在和能够反映其变化的物理实体，即进程的静态描述。进程的静态描述由三部分组成：进程控制块PCB，有关程序段和该程序段对其进行操作的数据结构集。进程控制块包含了有关进程的描述信息、控制信息以及资源信息，是进程动态特征的集中反映。系统根据PCB感知进程的存在和通过PCB中所包含的各项变量的变化，掌握进程所处的状态以达到控制进程活动的目的。由于进程的PCB 是系统感知进程的唯一实体，因此，在几乎所有的多道操作系统中，一个进程的PCB结构都是全部或部分常驻内存的。,进程的程序部分描述进程所要完成的功能。而数据结构集是程序在执行时必不可少的工作区和操作对象。这两部分是进程完成所需功能的物质基础。由于进程的这两部分内容与控制进程的执行及完成进程功能直接有
