计算机操作系统教程_第三版_(张尧学_张高_史美林_著)_清华大学出版社_第3章G

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