计算机操作系统第3章课件

《计算机操作系统第3章课件》由会员分享，可在线阅读，更多相关《计算机操作系统第3章课件（153页珍藏版）》请在装配图网上搜索。

1、第第3 3章章 进程管理进程管理3.1 3.1 进程的概念进程的概念3.2 3.2 进程的描述进程的描述3.3 3.3 进程状态及其转换进程状态及其转换3.4 3.4 进程控制进程控制3.5 3.5 进程互斥进程互斥3.6 3.6 进程同步进程同步3.7 3.7 进程通信进程通信3.8 3.8 死锁问题死锁问题3.9 3.9 线程线程 3.1 进程的概念进程的概念 现代操作系统的重要特点：现代操作系统的重要特点：程序的并发执行、资源共享、用户随机地使用。程序的并发执行、资源共享、用户随机地使用。1.程序的顺序执行程序的顺序执行程序的顺序执行程序的顺序执行：程序独占处理机直至最终结束的过：程序独

2、占处理机直至最终结束的过程。程。程序的顺序执行具有如下特点：程序的顺序执行具有如下特点：(1)顺序性顺序性程序顺序执行时，其执行过程可看作一系列严格按程程序顺序执行时，其执行过程可看作一系列严格按程序规定的状态转移过程。序规定的状态转移过程。(2)封闭性封闭性程序执行得到的最终结果由给定的初始条件决定，不程序执行得到的最终结果由给定的初始条件决定，不受外界因素的影响。受外界因素的影响。(3)可再现性可再现性只要输入的初始条件相同，则无论何时重复执行该程只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果。序都会得到相同的结果。2.多道程序系统中程序执行环境的变化多道程序系统中程序

3、执行环境的变化多道程序执行的系统环境具有下述三个特点：多道程序执行的系统环境具有下述三个特点：(1)独立性独立性每道程序都是逻辑上独立的，它们之间不存在逻辑上每道程序都是逻辑上独立的，它们之间不存在逻辑上的制约关系。的制约关系。(2)随机性随机性在多道程序环境下，特别是在多用户环境下，程序和在多道程序环境下，特别是在多用户环境下，程序和数据的输入与执行开始时间都是随机的。数据的输入与执行开始时间都是随机的。(3)资源共享资源共享资源共享将导致对进程执行速度的制约。资源共享将导致对进程执行速度的制约。3.程序的并发执行程序的并发执行(1)什么是程序的并发执行什么是程序的并发执行 并发执行并发执行

4、：即一道程序的执行尚未结束；另一道程：即一道程序的执行尚未结束；另一道程序的执行已经开始的执行方式。是为了增强计算机序的执行已经开始的执行方式。是为了增强计算机系统的处理能力和提高资源利用率所采取的一种同系统的处理能力和提高资源利用率所采取的一种同时操作技术。程序的并发执行可进一步分为两种：时操作技术。程序的并发执行可进一步分为两种：第一种第一种第一种第一种是多道程序系统的程序执行环境变化所引起是多道程序系统的程序执行环境变化所引起的多道程序的并发执行。微观上仍是顺序执行，尽的多道程序的并发执行。微观上仍是顺序执行，尽管多道程序的并发执行在宏观上是同时进行的。管多道程序的并发执行在宏观上是同时

5、进行的。第第第第二种二种二种二种并发执行是在某道程序的几个程序段中（例如并发执行是在某道程序的几个程序段中（例如几个程序），包含着一部分可以同时执行或顺序颠几个程序），包含着一部分可以同时执行或顺序颠倒执行的代码。例如语句：倒执行的代码。例如语句：read(a)；read(b)；它们既可以同时执行，也可颠倒次序执行。对于这样它们既可以同时执行，也可颠倒次序执行。对于这样的语句，同时执行不会改变顺序程序所具有的逻辑的语句，同时执行不会改变顺序程序所具有的逻辑性质。因此，可以采用并发执行来充分利用系统资性质。因此，可以采用并发执行来充分利用系统资源以提高计算机的处理能力。源以提高计算机的处理能力。

6、程序的并发执行可总结为：一组在逻辑上互相独立的程序的并发执行可总结为：一组在逻辑上互相独立的程序或程序段在执行过程中，其执行时间在客观上程序或程序段在执行过程中，其执行时间在客观上互相重叠，即一个程序段的执行尚未结束，另一个互相重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始的这种执行方式。程序段的执行已经开始的这种执行方式。程序的并发执行不同于程序的并行执行。程序的并行程序的并发执行不同于程序的并行执行。程序的并行执行是指一组程序按独立的、异步的速度执行。并执行是指一组程序按独立的、异步的速度执行。并行执行不等于时间上的重叠。可以将并发执行过程行执行不等于时间上的重叠。可以将并发

7、执行过程描述为：描述为：S0CobeginP1；P2；.PnCoendSn这里，这里，S0，Sn分别表示并发程序段分别表示并发程序段P1，P2，Pn开始执行前和并发执行结束后的语句。开始执行前和并发执行结束后的语句。P1，2，Pn也可以由同一程序段中的不同语句组成。也可以由同一程序段中的不同语句组成。1966年年Bernstein 提出了提出了两相邻语句两相邻语句S1，S2可以并发执可以并发执行的条件：行的条件：将程序中任一语句将程序中任一语句Si划分为两个变量的集合划分为两个变量的集合R(Si)和和W(Si)。其中。其中R(Si)=a1 a2 am，aj(j=1，m)是语句是语句Si在执行期

8、间必须对其进行读操作的变量；在执行期间必须对其进行读操作的变量；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是可以并发执行的。是可以并发执行的。多道执行与单道执行有何优点:例：例：例：例：有三个程序有三个程序A、B、C；每个程序都由输入、计算、；每个程序都由输入、计算、输出三部分代码组成；记为输出三部分代码组成；记为Ai、Ac、Ao，

9、Bi、Bc、Bo，Ci、Cc、Co；假设各部分代码在相应的设备上；假设各部分代码在相应的设备上执行的时间都为执行的时间都为t；在单道环境下：总的运行时间；在单道环境下：总的运行时间9t，输入设备占用输入设备占用3t，输出设备占用，输出设备占用3t。C P U 利用率利用率3t9t3933.3 输入设备利用率输入设备利用率3t9t39 33.3 输出设备利用率输出设备利用率3t9t39 33.3 AiAiAoAoAcAcBiBiBoBoBcBcCiCiCcCcCoCoAiAiAoAoAcAcBiBiBoBoBcBcCiCiCcCcCoCott时时间间ttttttt多道环境下多道环境下多道环境下多

10、道环境下：总的运行时间：总的运行时间5t，输入设备占用，输入设备占用3t，输出设备占，输出设备占用用3t。C P U 利用率利用率3t5t3560 输入设备利用率输入设备利用率3t5t3560 输出设备利用率输出设备利用率3t5t3560CPUCPU时间片时间片时间片时间片进进进进 程程程程 A A进进进进 程程程程 B B进进进进 程程程程 C CtAiAiAcAcAoAoBiBiBcBcBoBoCiCiCcCcCoCotttt输入设备输入设备输入设备输入设备输出设备输出设备输出设备输出设备CPUCPU(2)程序的并发执行所带来的影响程序的并发执行所带来的影响程序的并发执行充分地利用了系统资

11、源，从而提高了程序的并发执行充分地利用了系统资源，从而提高了系统的处理能力，这是并发执行好的一方面。但是，系统的处理能力，这是并发执行好的一方面。但是，正如前面所提到的那样，由于系统资源有限，程序正如前面所提到的那样，由于系统资源有限，程序的并发执行必然导致资源共享和资源竞争，从而改的并发执行必然导致资源共享和资源竞争，从而改变程序的执行速度。如果并发执行的各程序段中语变程序的执行速度。如果并发执行的各程序段中语句或指令满足上述句或指令满足上述Bernstein 的三个条件，则认为的三个条件，则认为并发执行不会对执行结果的封闭性和可再现性产生并发执行不会对执行结果的封闭性和可再现性产生影响。但

12、在一般情况下，系统要判定并发执行的各影响。但在一般情况下，系统要判定并发执行的各程序段是否满足程序段是否满足Bernstein 条件是相当困难的。从条件是相当困难的。从而，如果并发执行的程序段不按照特定的规则和方而，如果并发执行的程序段不按照特定的规则和方法进行资源共享和竞争，则其执行结果将不可避免法进行资源共享和竞争，则其执行结果将不可避免地失去封闭性和可再现性。下面的例子说明了这一地失去封闭性和可再现性。下面的例子说明了这一点。点。堆栈的取数和存数过程图堆栈的取数和存数过程图例：设有堆栈例：设有堆栈S，栈指针，栈指针top，栈中存放内存中相应数，栈中存放内存中相应数据块地址（如图据块地址（

13、如图3.1(a)）设有两个程序段）设有两个程序段getaddr(top)和和reladdr(blk)，其中，其中getaddr(top)从给从给定的定的top所指栈中取出相应的内存数据块地址，而所指栈中取出相应的内存数据块地址，而reladdr(blk)则将内存数据块地址则将内存数据块地址blk放入堆栈放入堆栈S中。中。getaddr(top)和和reladdr(blk)可分别描述为：可分别描述为：procedure getaddr(top)beginlocal rr(top)top top-1return(r)endprocedure reladdr(blk)例：利用堆栈管理一块内存区中各数

14、据块的使用情况。用例：利用堆栈管理一块内存区中各数据块的使用情况。用getaddr(top)从栈顶取出相应的内存块的地址。用从栈顶取出相应的内存块的地址。用reladdr(blk)将数据块的地址（以将数据块的地址（以bkl为地址）放入堆栈中。为地址）放入堆栈中。proc getaddr(top)Begin local r;1.1 r stop;1.2 top top-1;1.3 return(r);end;Proc reladdr(blk)Begin 2.1 top top+1;2.2 stop blk;End;分析分析getaddr(top)与与reladdr(blk)的并发执行的并发执行0

15、12345t abtop2.1 top top+11.1 r stop1.2 top top-11.3 return(r)2.2 stop blktoptop blk上例中的程序段并发执行出现错误结果是由于两程序上例中的程序段并发执行出现错误结果是由于两程序段共享资源堆栈段共享资源堆栈S，从而使得执行结果受执行速度，从而使得执行结果受执行速度影响。一般情况下，并发执行的各程序段如果共享影响。一般情况下，并发执行的各程序段如果共享软、硬件资源，都会造成其执行结果受执行速度影软、硬件资源，都会造成其执行结果受执行速度影响的局面。显然，这是程序设计人员不希望看到的。响的局面。显然，这是程序设计人员不

16、希望看到的。为了使得在并发执行时不出现错误结果，必须采取为了使得在并发执行时不出现错误结果，必须采取某些措施来制约、控制各并发程序段的执行速度。某些措施来制约、控制各并发程序段的执行速度。这在操作系统程序设计中尤其重要，因为操作系统这在操作系统程序设计中尤其重要，因为操作系统用户随机性与各道程序逻辑独立的特点将使得每个用户随机性与各道程序逻辑独立的特点将使得每个用户程序所使用的软、硬件资源都受到其他并发程用户程序所使用的软、硬件资源都受到其他并发程序的共享和竞争，从而得到非预料的或不正确的结序的共享和竞争，从而得到非预料的或不正确的结果。为了控制和协调各程序段执行过程中的软、硬果。为了控制和协

17、调各程序段执行过程中的软、硬件资源的共享和竞争，显然，必须应该有一个描述件资源的共享和竞争，显然，必须应该有一个描述各程序段执行过程和共享资源的基本单位。各程序段执行过程和共享资源的基本单位。从上述讨论可以看出，由于程序的顺序性、静态性以从上述讨论可以看出，由于程序的顺序性、静态性以及孤立性，用程序段作为描述其执行过程和共享资及孤立性，用程序段作为描述其执行过程和共享资源的基本单位既增加操作系统设计和实现的复杂性，源的基本单位既增加操作系统设计和实现的复杂性，也无法反映操作系统所应该具有的程序段执行的并也无法反映操作系统所应该具有的程序段执行的并发性、用户随机性，以及资源共享等特征。也就是发性

18、、用户随机性，以及资源共享等特征。也就是说，用程序作为描述其执行过程以及共享资源的基说，用程序作为描述其执行过程以及共享资源的基本单位是不合适的。需要有一个能描述程序的执行本单位是不合适的。需要有一个能描述程序的执行过程且能用来共享资源的基本单位。这个基本单位过程且能用来共享资源的基本单位。这个基本单位被称为进程（或任务）。被称为进程（或任务）。3.1.2 进程的定义进程的定义进程的概念是进程的概念是60年代初期，首先在年代初期，首先在MIT 的的 Multics系系统和统和IBM 的的 TSS/360系统中引用的。系统中引用的。进程的定义进程的定义：一个具有独立功能的程序对某个数据集：一个具

19、有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位。在处理机上的执行过程和分配资源的基本单位。进程和程序是两个既有联系又有区别的概念，它们的进程和程序是两个既有联系又有区别的概念，它们的区别和关系可简述如下：区别和关系可简述如下：(1)进程是一个动态概念，而程序则是一个静态概念。进程是一个动态概念，而程序则是一个静态概念。程序是指令的有序集合，没有任何执行的含义。而程序是指令的有序集合，没有任何执行的含义。而进程则强调执行过程，它动态地被创建，并被调度进程则强调执行过程，它动态地被创建，并被调度执行后消亡。执行后消亡。(2)进程具有并行特征，而程序没有。由进程的定义进程具有并

20、行特征，而程序没有。由进程的定义可知，进程具有并行特征的两个方面，即独立性和可知，进程具有并行特征的两个方面，即独立性和异步性。也就是说，在不考虑资源共享的情况下，异步性。也就是说，在不考虑资源共享的情况下，各进程的执行是独立的，执行速度是异步的。显然，各进程的执行是独立的，执行速度是异步的。显然，由于程序不反映执行过程，所以不具有并行特征。由于程序不反映执行过程，所以不具有并行特征。(3)进程是竞争计算机系统资源的基本单位，从而其进程是竞争计算机系统资源的基本单位，从而其并行性受到系统自己的制约。这里，制约就是对进并行性受到系统自己的制约。这里，制约就是对进程独立性和异步性的限制。程独立性和

21、异步性的限制。(4)不同的进程可以包含同一程序，只要该程序所对不同的进程可以包含同一程序，只要该程序所对应的数据集不同。应的数据集不同。3.1.3 作业和进程的关系作业和进程的关系作业是用户需要计算机完成某项任务时要求计算机所作业是用户需要计算机完成某项任务时要求计算机所作工作的集合。进程是已提交完毕程序的执行过程作工作的集合。进程是已提交完毕程序的执行过程的描述，是资源分配的基本单位。区别与关系：的描述，是资源分配的基本单位。区别与关系：(1)作业是用户向计算机提交任务的任务实体。在用作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业之后，系统将它放入外存中的户向计算机提交作业之后

22、，系统将它放入外存中的作业等待队列中等待执行。而进程则是完成用户任作业等待队列中等待执行。而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于任一进程，只要它被创建，总有相应的部分存在于内存中。内存中。(2)一个作业可由多个进程组成。且必须至少由一个一个作业可由多个进程组成。且必须至少由一个进程组成，但反过来不成立。进程组成，但反过来不成立。(3)作业的概念主要用在批处理系统中。而进程的概作业的概念主要用在批处理系统中。而进程的概念则用在几乎所有的多道系统中。念则用在几乎所有的多道系统中。3

23、.2 进程的描述进程的描述从处理机的活动角度来看，又如何识别描述程序执行从处理机的活动角度来看，又如何识别描述程序执行活动的进程呢？显然，系统中需要有描述进程存在活动的进程呢？显然，系统中需要有描述进程存在和能够反映其变化的物理实体，即进程的静态描述。和能够反映其变化的物理实体，即进程的静态描述。进程的静态描述由三部分组成：进程控制块进程的静态描述由三部分组成：进程控制块PCB，有关程序段和该程序段对其进行操作的数据结构集。有关程序段和该程序段对其进行操作的数据结构集。进程控制块包含了有关进程的描述信息、控制信息进程控制块包含了有关进程的描述信息、控制信息以及资源信息，是进程动态特征的集中反映

24、。系统以及资源信息，是进程动态特征的集中反映。系统根据根据PCB感知进程的存在和通过感知进程的存在和通过PCB中所包含的各中所包含的各项变量的变化，掌握进程所处的状态以达到控制进项变量的变化，掌握进程所处的状态以达到控制进程活动的目的。由于进程的程活动的目的。由于进程的PCB 是系统感知进程的是系统感知进程的唯一实体，因此，在几乎所有的多道操作系统中，唯一实体，因此，在几乎所有的多道操作系统中，一个进程的一个进程的PCB结构都是全部或部分常驻内存的。结构都是全部或部分常驻内存的。进程的程序部分描述进程所要完成的功能。而数据结进程的程序部分描述进程所要完成的功能。而数据结构集是程序在执行时必不可

25、少的工作区和操作对象。构集是程序在执行时必不可少的工作区和操作对象。这两部分是进程完成所需功能的物质基础。由于进这两部分是进程完成所需功能的物质基础。由于进程的这两部分内容与控制进程的执行及完成进程功程的这两部分内容与控制进程的执行及完成进程功能直接有关，因而，在大部分多道操作系统中，这能直接有关，因而，在大部分多道操作系统中，这两部分内容放在外存中，直到该进程执行时再调入两部分内容放在外存中，直到该进程执行时再调入内存。下面分别介绍进程的内存。下面分别介绍进程的PCB结构、程序与数据结构、程序与数据结构集。结构集。3.2.1 进程控制块进程控制块PCB PCB包含一个进程的描述信息、控制信息

26、及资源信包含一个进程的描述信息、控制信息及资源信息，有些系统中还有进程调度等待所使用的现场保息，有些系统中还有进程调度等待所使用的现场保护区。护区。PCB 集中反映一个进程的动态特征。在创建集中反映一个进程的动态特征。在创建一个进程时，应首先创建其一个进程时，应首先创建其 PCB，然后才能根据，然后才能根据PCB 中信息对进程实施有效的管理和控制。当一个中信息对进程实施有效的管理和控制。当一个进程完成其功能之后，系统则释放进程完成其功能之后，系统则释放PCB，进程也随，进程也随之消亡。之消亡。根据操作系统的要求不同，根据操作系统的要求不同，PCB的内容会有所不同。的内容会有所不同。下面所示基本

27、内容是必需的：下面所示基本内容是必需的：(1)描述信息描述信息 进程名或进程标识号、进程名或进程标识号、用户名或用户标识号、用户名或用户标识号、家族家族关系。关系。(2)控制信息控制信息 进程当前状态进程当前状态进程在活动期间可分为就绪态、执行态和等待状态。进程在活动期间可分为就绪态、执行态和等待状态。进程优先级进程优先级进程优先级是选取进程占有处理机的重要依据。进程优先级是选取进程占有处理机的重要依据。程序开始地址程序开始地址 各种计时信息各种计时信息 通信信息通信信息(3)资源管理信息资源管理信息PCB 中包含最多的是资源管理信息，包括有关存储器中包含最多的是资源管理信息，包括有关存储器的

28、信息、使用输入输出设备的信息、有关文件系统的信息、使用输入输出设备的信息、有关文件系统的信息等。这些信息有：的信息等。这些信息有：占用内存大小及其管理用数据结构指针，例如后述占用内存大小及其管理用数据结构指针，例如后述内存管理中所用到的进程页表指针等。内存管理中所用到的进程页表指针等。对换或覆盖用的有关信息，如对换程序段长度，对换或覆盖用的有关信息，如对换程序段长度，对换外存地址等。这些信息在进程申请、释放内存对换外存地址等。这些信息在进程申请、释放内存中使用。中使用。共享程序段大小及起始地址。共享程序段大小及起始地址。输入输出设备的设备号，所要传送的数据长度、输入输出设备的设备号，所要传送的

29、数据长度、缓冲区地址、缓冲区长度及所用设备的有关数据结缓冲区地址、缓冲区长度及所用设备的有关数据结构指针等。这些信息在进程申请释放设备进行数据构指针等。这些信息在进程申请释放设备进行数据传输中使用。传输中使用。指向文件系统的指针及有关标识等。进程可使用指向文件系统的指针及有关标识等。进程可使用这些信息对文件系统进行操作。这些信息对文件系统进行操作。(4)CPU 现场保护结构现场保护结构当前进程因等待某个事件而进入等待状态或因某种事当前进程因等待某个事件而进入等待状态或因某种事件发生被中止在处理机上的执行时，为了以后该进件发生被中止在处理机上的执行时，为了以后该进程能在被打断处恢复执行，需要保护

30、当前进程的程能在被打断处恢复执行，需要保护当前进程的 CPU现场（或称进程上下文）。现场（或称进程上下文）。PCB 中设有专门中设有专门的的 CPU现场保护结构，以存储退出执行时的进程现场保护结构，以存储退出执行时的进程现场数据。现场数据。总之，进程控制块总之，进程控制块PCB 是系统感知进程存在的唯一是系统感知进程存在的唯一实体。通过对实体。通过对PCB 的操作，给进程分配资源、调度的操作，给进程分配资源、调度进程执行、释放进程所占有的各种资源；而完成进进程执行、释放进程所占有的各种资源；而完成进程所要求功能的程序段的有关地址，以及程序段在程所要求功能的程序段的有关地址，以及程序段在进程过程

31、中因某种原因被停止执行后的现场信息也进程过程中因某种原因被停止执行后的现场信息也都在都在PCB 中。中。由于由于PCB 中包含有较多的信息，因此，一个中包含有较多的信息，因此，一个PCB表表往往要占据较大的存储空间（一般占几百到几千个往往要占据较大的存储空间（一般占几百到几千个字节）。在有的系统中，为了减少字节）。在有的系统中，为了减少 PCB对内存的占对内存的占用量，只允许用量，只允许PCB中最常用的部分，如中最常用的部分，如CPU现场保现场保护、进程描述信息、控制信息等常驻内存。护、进程描述信息、控制信息等常驻内存。PCB 结结构中的其他部分则存放于外存之中，待该进程将要构中的其他部分则存

32、放于外存之中，待该进程将要执行时与其他数据一起装入内存。执行时与其他数据一起装入内存。近年来，面向对象技术已被用于操作系统设计。在面近年来，面向对象技术已被用于操作系统设计。在面向对象的操作系统中，进程的描述将采用其他方式。向对象的操作系统中，进程的描述将采用其他方式。3.2.2 进程上下文进程上下文本节介绍包括程序段和数据集在内的上下文的概念。本节介绍包括程序段和数据集在内的上下文的概念。进程上下文实际上是进程执行活动全过程的静态描述。进程上下文实际上是进程执行活动全过程的静态描述。具体地说，进程上下文包括计算机系统中与执行该具体地说，进程上下文包括计算机系统中与执行该进程有关的各种寄存器的

33、值、程序段在经过编译之进程有关的各种寄存器的值、程序段在经过编译之后形成的机器指令代码集（或称正文段）、数据集后形成的机器指令代码集（或称正文段）、数据集及各种堆栈值和及各种堆栈值和PCB结构结构(图图3.2)。这里，有关寄存。这里，有关寄存器和栈区的内容是重要的。例如，没有程序计数器器和栈区的内容是重要的。例如，没有程序计数器PC和程序状态寄存器和程序状态寄存器PS，CPU将无法知道下条待将无法知道下条待执行指令的地址和控制有关操作。从执行指令的地址和控制有关操作。从CPU是活动的是活动的观点来静态地看一个进程时，必须把有关寄存器和观点来静态地看一个进程时，必须把有关寄存器和栈区的内容也包括

34、在其中。无论在何种系统中，进栈区的内容也包括在其中。无论在何种系统中，进程上下文的各部分都必须按一定的规则有机地组合程上下文的各部分都必须按一定的规则有机地组合起来以便于执行。起来以便于执行。图图3.2 进程上下文结构进程上下文结构进程上下文可按一定的执行层次组合，例如用户级上进程上下文可按一定的执行层次组合，例如用户级上下文、系统级上下文等。显然，一个进程的执行是下文、系统级上下文等。显然，一个进程的执行是在该进程的上下文中执行，而当系统调度新进程占在该进程的上下文中执行，而当系统调度新进程占有处理机时，新老进程的上下文发生转换。有处理机时，新老进程的上下文发生转换。在在UNIX Syste

35、m 中，进程上下文由用户级上下文、中，进程上下文由用户级上下文、寄存器上下文以及系统级上下文组成。用户级上下寄存器上下文以及系统级上下文组成。用户级上下文由进程的用户程序段部分编译而成的用户正文段、文由进程的用户程序段部分编译而成的用户正文段、用户数据、用户栈等组成。而寄存器上下文则由程用户数据、用户栈等组成。而寄存器上下文则由程序寄存器序寄存器PC、处理机状态字寄存器、处理机状态字寄存器PS、栈指针和、栈指针和通用寄存器的值组成。其中通用寄存器的值组成。其中PC给出给出CPU 将要执行将要执行的下条指令的虚地址；的下条指令的虚地址；PS给出机器与该进程相关联给出机器与该进程相关联时的硬件状态

36、，例如当前执行模式、能否执行特权时的硬件状态，例如当前执行模式、能否执行特权指令等；栈指针指向下一项的当前地址，而通用寄指令等；栈指针指向下一项的当前地址，而通用寄存器则用于不同执行模式之间的参数传递等。存器则用于不同执行模式之间的参数传递等。进程的系统级上下文又分为静态部分与动态部分。这进程的系统级上下文又分为静态部分与动态部分。这里的动态部分不是指程序的执行，而是指在进入和里的动态部分不是指程序的执行，而是指在进入和退出不同的上下文层次时，系统为各层上下文中相退出不同的上下文层次时，系统为各层上下文中相关联的寄存器值所保存和恢复的记录。关联的寄存器值所保存和恢复的记录。系统级上下文的静态部

37、分包括系统级上下文的静态部分包括PCB 结构（结构（UNIX系统系统中的中的 PCB结构被分为结构被分为proc结构和结构和user结构两部分）、结构两部分）、将进程虚地址空间映射到物理空间用的有关表格和将进程虚地址空间映射到物理空间用的有关表格和核心栈。这里，核心栈主要用来装载进程中所使用核心栈。这里，核心栈主要用来装载进程中所使用系统调用的调用序列。系统调用的调用序列。系统级上下文的动态部分是与寄存器上下文相关联的。系统级上下文的动态部分是与寄存器上下文相关联的。进程上下文的层次概念也主要体现在动态部分中，进程上下文的层次概念也主要体现在动态部分中，即系统级上下文的动态部分可看成是一些数量

38、变化即系统级上下文的动态部分可看成是一些数量变化的层次组成。其变化规则满足先进后出的堆栈方式，的层次组成。其变化规则满足先进后出的堆栈方式，每个上下文层次在栈中各占一项。每个上下文层次在栈中各占一项。UNIX System 的进程上下文组成如图的进程上下文组成如图3.3。图图3.3 UNIX System 进程上下文组成进程上下文组成3.2.3 进程空间进程空间任一进程，都有一个自己的地址空间，把该空间称为任一进程，都有一个自己的地址空间，把该空间称为进程空间或虚空间。进程空间的大小只与处理机的进程空间或虚空间。进程空间的大小只与处理机的位数有关。在位数有关。在UNIX以及以及Linux等操作

39、系统中，进程等操作系统中，进程空间还被划分为用户空间和系统空间两大部分。空间还被划分为用户空间和系统空间两大部分。在进程空间被划分为两大部分后，用户程序在用户空在进程空间被划分为两大部分后，用户程序在用户空间内执行，而操作系统内核程序则在进程的系统空间内执行，而操作系统内核程序则在进程的系统空间内执行。间内执行。为防止用户程序访问系统空间，造成访问出错，系统为防止用户程序访问系统空间，造成访问出错，系统通过程序状态寄存器等设置不同的执行模式，即用通过程序状态寄存器等设置不同的执行模式，即用户模式和系统模式来进行保护。户模式和系统模式来进行保护。3.3 进程状态及其转换进程状态及其转换3.3.1

40、 进程状态进程状态一个进程的生命期可以划分为一组状态，这些状态刻一个进程的生命期可以划分为一组状态，这些状态刻划了整个进程。系统根据划了整个进程。系统根据PCB 结构中的状态值控制结构中的状态值控制进程。在进程的生命期内，一个进程至少具有三种进程。在进程的生命期内，一个进程至少具有三种基本状态，它们是：执行状态、等待状态和就绪状基本状态，它们是：执行状态、等待状态和就绪状态。态。处于就绪状态的进程已经得到除处于就绪状态的进程已经得到除 CPU之外的其他资之外的其他资源，只要由调度得到处理机，便可立即投入执行。源，只要由调度得到处理机，便可立即投入执行。在有些系统中，为了有效地利用内存，就绪状态

41、又可在有些系统中，为了有效地利用内存，就绪状态又可进一步分为内存就绪状态和外存就绪状态。在这样进一步分为内存就绪状态和外存就绪状态。在这样的系统中，只有处于内存就绪状态的进程在得到处的系统中，只有处于内存就绪状态的进程在得到处理机后才能立即投入执行。而处于外存就绪状态的理机后才能立即投入执行。而处于外存就绪状态的进程只有先成为内存就绪状态后，才可能被调度执进程只有先成为内存就绪状态后，才可能被调度执行。这种方式明显地提高了内存的利用效率，但反行。这种方式明显地提高了内存的利用效率，但反过来也增加了系统开销和系统复杂性。过来也增加了系统开销和系统复杂性。在单在单CPU系统中，任一时刻处于执行状态

42、的进程只能系统中，任一时刻处于执行状态的进程只能有一个。只有处于就绪状态的进程经调度选中之后有一个。只有处于就绪状态的进程经调度选中之后才可进入执行状态。才可进入执行状态。在某些操作系统中，一个进程在其生命期内的执行过在某些操作系统中，一个进程在其生命期内的执行过程中，总要涉及到用户程序和操作系统内核程序两程中，总要涉及到用户程序和操作系统内核程序两部分。因此，进程的执行状态又可进一步划分为用部分。因此，进程的执行状态又可进一步划分为用户执行状态和系统执行状态。划分用户态和系统态户执行状态和系统执行状态。划分用户态和系统态最主要的原因是要把用户程序和系统程序区分开来，最主要的原因是要把用户程序

43、和系统程序区分开来，以利于程序的共享和保护。显然，这也是以增加系以利于程序的共享和保护。显然，这也是以增加系统复杂度和系统开销为代价的。统复杂度和系统开销为代价的。进程因等待某个事件发生而放弃处理机进入等待状态。进程因等待某个事件发生而放弃处理机进入等待状态。显然，等待状态可根据等待事件的种类而进一步划显然，等待状态可根据等待事件的种类而进一步划分为不同的子状态，例如内存等待、设备等待、文分为不同的子状态，例如内存等待、设备等待、文件等待和数据等待等。这样做的好处是系统控制简件等待和数据等待等。这样做的好处是系统控制简单，发现和唤醒相应的进程较为容易。但系统中设单，发现和唤醒相应的进程较为容易

44、。但系统中设置过多的状态又会造成系统参数和状态转换过程的置过多的状态又会造成系统参数和状态转换过程的增加。增加。3.3.2 进程状态转换进程状态转换进程的状态反映进程执行过程的变化。这些状态随着进程的状态反映进程执行过程的变化。这些状态随着进程的执行和外界条件发生变化和转换。那么，是进程的执行和外界条件发生变化和转换。那么，是什么样的条件使得进程各状态发生转换呢？示图给什么样的条件使得进程各状态发生转换呢？示图给出了三个基本状态，即就绪状态、执行状态与等待出了三个基本状态，即就绪状态、执行状态与等待状态之间的转换关系。状态之间的转换关系。事实上，进程的状态转换是一个非常复杂的过程。从事实上，进

45、程的状态转换是一个非常复杂的过程。从一个状态到另一个状态的转换除了要使用不同的控一个状态到另一个状态的转换除了要使用不同的控制过程（将在下节中讲述），有时还要借助于硬件制过程（将在下节中讲述），有时还要借助于硬件触发器才能完成。例如，在触发器才能完成。例如，在 UNIX 系统中，从系统系统中，从系统态到用户态的转换要借助硬件触发器完成。态到用户态的转换要借助硬件触发器完成。进程状态转换图进程状态转换图3.4 进进 程程 控控 制制进程和处理机管理的一个重要任务是进程控制。所谓进程和处理机管理的一个重要任务是进程控制。所谓进程控制，就是系统使用一些具有特定功能的程序进程控制，就是系统使用一些具有

46、特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源从而达到多进程高效率并发执行和协调、实现资源共享的目的。一般地，把系统态下执行的某些具有共享的目的。一般地，把系统态下执行的某些具有特定功能的程序段称为原语。原语可分为两类：一特定功能的程序段称为原语。原语可分为两类：一类是机器指令级的，其特点是执行期间不允许中断。类是机器指令级的，其特点是执行期间不允许中断。另一类是功能级的，其特点是作为原语的程序段不另一类是功能级的，其特点是作为原语的程序段不允许并发执行。这两类原语都在系统态下执行，且允许并

47、发执行。这两类原语都在系统态下执行，且都是为了完成某个系统管理所需要的功能和被高层都是为了完成某个系统管理所需要的功能和被高层软件所调用。软件所调用。显然，系统在创建、撤消一个进程以及要改变进程的显然，系统在创建、撤消一个进程以及要改变进程的状态时，都要调用相应的程序段来完成这些功能。状态时，都要调用相应的程序段来完成这些功能。那么，这些程序段是不是原语呢？如果它们不是原那么，这些程序段是不是原语呢？如果它们不是原语，则由上述原语的定义可知，这些程序段是允许语，则由上述原语的定义可知，这些程序段是允许并发执行的。然而，如果不加控制和管理地让这些并发执行的。然而，如果不加控制和管理地让这些控制进

48、程状态转换及创建和撤消进程的程序段并发控制进程状态转换及创建和撤消进程的程序段并发执行，则会使得其执行结果失去封闭性和可再现性，执行，则会使得其执行结果失去封闭性和可再现性，从而达不到进程控制的目的。反过来，如果对这些从而达不到进程控制的目的。反过来，如果对这些程序段采用下面章节中所述的控制方法使其在并发程序段采用下面章节中所述的控制方法使其在并发执行过程中也能完成进程控制任务的话，将会大大执行过程中也能完成进程控制任务的话，将会大大增加系统的开销和复杂度。因此，在操作系统中，增加系统的开销和复杂度。因此，在操作系统中，通常把进程控制用程序段做成原语。用于进程控制通常把进程控制用程序段做成原语

49、。用于进程控制的原语有：创建原语、撤消原语、阻塞原语、唤醒的原语有：创建原语、撤消原语、阻塞原语、唤醒原语等。原语等。3.4.1 进程创建与撤消进程创建与撤消1.进程创建进程创建(1)由系统程序模块统一创建，例如在批处理系统中，由系统程序模块统一创建，例如在批处理系统中，由操作系统的作业调度程序为用户作业创建相应的由操作系统的作业调度程序为用户作业创建相应的进程以完成用户作业所要求的功能。进程以完成用户作业所要求的功能。(2)由父进程创建，例如在层次结构的系统中，父进由父进程创建，例如在层次结构的系统中，父进程创建子进程以完成并行工作。程创建子进程以完成并行工作。由系统统一创建的进程之间的关系

50、是平等的，它们之由系统统一创建的进程之间的关系是平等的，它们之间一般不存在资源继承关系。而在父进程创建的进间一般不存在资源继承关系。而在父进程创建的进程之间则存在隶属关系，且互相构成树型结构的家程之间则存在隶属关系，且互相构成树型结构的家族关系。属于某个家族的一个进程可以继承其父进族关系。属于某个家族的一个进程可以继承其父进程所拥有的资源。另外，无论是哪一种方式创建进程所拥有的资源。另外，无论是哪一种方式创建进程，在系统生成时，都必须由操作系统创建一部分程，在系统生成时，都必须由操作系统创建一部分承担系统资源分配和管理工作的系统进程。承担系统资源分配和管理工作的系统进程。无论是系统创建方式还是

51、父进程创建方式，都必须调无论是系统创建方式还是父进程创建方式，都必须调用创建原语来实现。用创建原语来实现。2.进程撤消进程撤消以下几种情况导致进程被撤消：以下几种情况导致进程被撤消：(1)该进程已完成所要求的功能而正常终止。该进程已完成所要求的功能而正常终止。(2)由于某种错误导致非正常终止。由于某种错误导致非正常终止。(3)祖先进程要求撤消某个子进程。祖先进程要求撤消某个子进程。无论哪一种情况导致进程被撤消，进程都必须释放它无论哪一种情况导致进程被撤消，进程都必须释放它所占用的各种资源和所占用的各种资源和PCB 结构本身，以利于资源的结构本身，以利于资源的有效利用。另外，当一个祖先进程撤消某

52、个子进程有效利用。另外，当一个祖先进程撤消某个子进程时，还需审查该子进程是否还有自己的子孙进程，时，还需审查该子进程是否还有自己的子孙进程，若有的话，还需撤消其子孙进程的若有的话，还需撤消其子孙进程的 PCB结构和释放结构和释放它们所占有的资源。它们所占有的资源。撤消原语首先检查撤消原语首先检查 PCB进程链或进程家族，寻找所进程链或进程家族，寻找所要撤消的进程是否存在。如果找到了所要撤消的进要撤消的进程是否存在。如果找到了所要撤消的进程的程的 PCB结构，则撤消原语释放该进程所占有的资结构，则撤消原语释放该进程所占有的资源之后，把对应的源之后，把对应的 PCB结构从进程链或进程家族中结构从进

53、程链或进程家族中摘下并返回给摘下并返回给 PCB空队列。如果被撤消的进程有自空队列。如果被撤消的进程有自己的子进程，则撤消原语先撤消其子进程的己的子进程，则撤消原语先撤消其子进程的 PCB结结构并释放子进程所占用的资源之后，再撤消当前进构并释放子进程所占用的资源之后，再撤消当前进程的程的 PCB结构和释放其资源。结构和释放其资源。3.4.2 进程的阻塞与唤醒进程的阻塞与唤醒进程的创建原语和撤消原语完成了进程从无到有，从进程的创建原语和撤消原语完成了进程从无到有，从存在到消亡的变化。被创建后的进程最初处于就绪存在到消亡的变化。被创建后的进程最初处于就绪状态，然后经调度程序选中后进入执行状态。这里

54、状态，然后经调度程序选中后进入执行状态。这里主要介绍实现进程的执行状态到等待状态，又由等主要介绍实现进程的执行状态到等待状态，又由等待状态到就绪状态转换的两种原语，即阻塞原语与待状态到就绪状态转换的两种原语，即阻塞原语与唤醒原语。唤醒原语。阻塞原语在一个进程期待某一事件发生，但发生条件阻塞原语在一个进程期待某一事件发生，但发生条件尚不具备时，被该进程自己调用来阻塞自己。阻塞尚不具备时，被该进程自己调用来阻塞自己。阻塞原语在阻塞一个进程时，由于该进程正处于执行状原语在阻塞一个进程时，由于该进程正处于执行状态，故应先中断处理机和保存该进程的态，故应先中断处理机和保存该进程的CPU现场。现场。然后将

55、被阻塞进程置然后将被阻塞进程置“阻塞阻塞”状态后插入等待队列状态后插入等待队列中，再转进程调度程序选择新的就绪进程投入运行。中，再转进程调度程序选择新的就绪进程投入运行。阻塞原语的实现过程如图。阻塞原语的实现过程如图。这里，转进程调度程序是很重要的，否则，处理机将这里，转进程调度程序是很重要的，否则，处理机将会出现空转而浪费资源。会出现空转而浪费资源。阻塞原语图阻塞原语图当等待队列中的进程所等待的事件发生时，等待该事当等待队列中的进程所等待的事件发生时，等待该事件的所有进程都将被唤醒。唤醒一个进程有两种方件的所有进程都将被唤醒。唤醒一个进程有两种方法：一种是由系统进程唤醒。另一种是由事件发生法

56、：一种是由系统进程唤醒。另一种是由事件发生进程唤醒。当由系统进程唤醒等待进程时，系统进进程唤醒。当由系统进程唤醒等待进程时，系统进程统一控制事件的发生并将程统一控制事件的发生并将“事件发生事件发生”这一消息这一消息通知等待进程。从而使得该进程因等待事件已发生通知等待进程。从而使得该进程因等待事件已发生而进入就绪队列。由事件发生进程唤醒时，事件发而进入就绪队列。由事件发生进程唤醒时，事件发生进程和被唤醒进程之间是合作关系。因此，唤醒生进程和被唤醒进程之间是合作关系。因此，唤醒原语既可被系统进程调用，也可被事件发生进程调原语既可被系统进程调用，也可被事件发生进程调用。称调用唤醒原语的进程为唤醒进程

57、。唤醒原语用。称调用唤醒原语的进程为唤醒进程。唤醒原语首先将被唤醒进程从相应的等待队列中摘下，将被首先将被唤醒进程从相应的等待队列中摘下，将被唤醒进程置为就绪状态之后，送入就绪队列。在把唤醒进程置为就绪状态之后，送入就绪队列。在把被唤醒进程送入就绪队列之后，唤醒原语既可以返被唤醒进程送入就绪队列之后，唤醒原语既可以返回原调用程序，也可以转向进程调度，以便让调度回原调用程序，也可以转向进程调度，以便让调度程序有机会选择一个合适的进程执行。如图：程序有机会选择一个合适的进程执行。如图：唤醒原语图唤醒原语图3.5 进进 程程 互互 斥斥3.5.1 资源共享所引起的制约资源共享所引起的制约进程的并发执

58、行不仅仅是用户程序的执行开始时间的进程的并发执行不仅仅是用户程序的执行开始时间的随机性和提高资源利用率的结果，也是资源有限性随机性和提高资源利用率的结果，也是资源有限性导致资源的竞争与共享对进程的执行过程进行制约导致资源的竞争与共享对进程的执行过程进行制约所造成的。所造成的。1.临界区临界区在描述一个程序或算法时，总是认为存在一个伪处理在描述一个程序或算法时，总是认为存在一个伪处理机，可以按程序或算法所规定的步骤来执行该程序机，可以按程序或算法所规定的步骤来执行该程序或算法的。但是，事实上，在实际的系统中则往往或算法的。但是，事实上，在实际的系统中则往往不是这样。一般说来，即使在程序中所描述的

59、一条不是这样。一般说来，即使在程序中所描述的一条语句，也是由多条执行指令构成的。例如，各种程语句，也是由多条执行指令构成的。例如，各种程序中经常出现的赋值语句：序中经常出现的赋值语句：X=X+1；在用汇编语言书写时，就变成：在用汇编语言书写时，就变成：LOADA，XADDIA，1STOREA，X等三条语句，这里等三条语句，这里 A代表累加器。根据系统的设计代表累加器。根据系统的设计和要求，在这三条语句的执行期间，也有可能发生和要求，在这三条语句的执行期间，也有可能发生中断或调度，从而使得与当前进程无关的程序得以中断或调度，从而使得与当前进程无关的程序得以执行。为了保证程序执行最终结果的正确性，

60、必须执行。为了保证程序执行最终结果的正确性，必须对并发执行的各进程进行制约，以控制它们的执行对并发执行的各进程进行制约，以控制它们的执行速度和对资源的竞争。在进程的概念一节中已经介速度和对资源的竞争。在进程的概念一节中已经介绍了进程中两相邻语句可并发执行的三个条件。是绍了进程中两相邻语句可并发执行的三个条件。是否有一种更为简单的办法来检查出需要对程序的哪否有一种更为简单的办法来检查出需要对程序的哪些部分进行制约才能保证其执行结果的正确性呢？些部分进行制约才能保证其执行结果的正确性呢？这里来看下面的例子。这里来看下面的例子。设有两个计算进程设有两个计算进程A，B共享内存共享内存S。其中。其中 S

61、分为三个领域，即系统区、进程工作区和数据区。分为三个领域，即系统区、进程工作区和数据区。这里数据区被划分大小相等的块，每个块中既可能这里数据区被划分大小相等的块，每个块中既可能放有数据，也有可能未放有数据。系统区主要是堆放有数据，也有可能未放有数据。系统区主要是堆栈，其中存放那些空数据块的地址。栈，其中存放那些空数据块的地址。多进程共享内存栈区示例图多进程共享内存栈区示例图当进程当进程A或或B要求空数据块时，从堆栈最顶部要求空数据块时，从堆栈最顶部（top指针所指的位置）取出所需数据块。当进程指针所指的位置）取出所需数据块。当进程A或或B释放数据块时，则把所释放数据块的地释放数据块时，则把所释

62、放数据块的地址放入堆栈顶部。令址放入堆栈顶部。令getspace 为取空数据块过程，为取空数据块过程，release(ad)为释放数据块过程。这里，为释放数据块过程。这里，ad为待释放为待释放数据块的地址。如果堆栈非空的话，进程数据块的地址。如果堆栈非空的话，进程A或或B是可以用任意的顺序释放和获取数据块的。执是可以用任意的顺序释放和获取数据块的。执行行getspace就是获取一个空数据块，而执行就是获取一个空数据块，而执行release(ad)就是释放一个地址为就是释放一个地址为ad的数据块。然而，的数据块。然而，由下面的描述可以看到，在进程并发执行时，由下面的描述可以看到，在进程并发执行时

63、，getspace或或 release(ad)将有可能完不成所要求的功将有可能完不成所要求的功能。能。getspace和和 release(ad)可进一步描述为：可进一步描述为：getspace:begin local ggstack top toptop-1endrelease(ad):begin top top+1stack top adend设时刻设时刻t0时，时，top=h0，则，则getspace和和 release(ad)可能可能按以下顺序执行：按以下顺序执行：首先首先 release(ad)的第一句执行，的第一句执行，t0：top top+1 top=h0+1；接着接着getsp

64、ace 执行，得：执行，得：t1：g stack top g=stack h0+1；t2：top top-1 top=h0；再是再是 release(ad)的第二句执行，得：的第二句执行，得：t3：stack top ad stack h0 ad；其结果是调用其结果是调用getspace的进程取到的是的进程取到的是h0+1中的一个中的一个未定义值，而调用未定义值，而调用release(ad)的进程把所释放的空的进程把所释放的空块地址块地址ad重复放入了重复放入了h0中。中。怎样保证上述执行结果的正确性呢？怎样保证上述执行结果的正确性呢？一个较为明显一个较为明显的答案是，如果把的答案是，如果把g

65、etspace和和release(ad)抽象为两个抽象为两个各以一个动作完成的顺序执行单位，那么执行结果各以一个动作完成的顺序执行单位，那么执行结果的正确性是可以保证的。的正确性是可以保证的。把不允许多个并发进程交叉执行的一段程序称为临界把不允许多个并发进程交叉执行的一段程序称为临界部分（部分（critical section）或临界区（）或临界区（critical region）。）。临界区是由属于不同并发进程的程序段共享公用数据临界区是由属于不同并发进程的程序段共享公用数据或公用数据变量而引起的，例如上例中就是因为过或公用数据变量而引起的，例如上例中就是因为过程程 getspace 和和

66、release(ad)共同访问栈中的数据而共同访问栈中的数据而引起的。临界区不可能用增加硬件的方法来解决。引起的。临界区不可能用增加硬件的方法来解决。因此，临界区也可以被称为访问公用数据的那段程因此，临界区也可以被称为访问公用数据的那段程序。序。2.间接制约间接制约一般来说，可以把那些不允许交叉执行的临界区按不一般来说，可以把那些不允许交叉执行的临界区按不同的公用数据划分为不同的集合。上例中，以公用同的公用数据划分为不同的集合。上例中，以公用数据栈划分的临界区集合是数据栈划分的临界区集合是getspace,release。把这些集合称为类（把这些集合称为类（class）。显然，对类给定一个）。显然，对类给定一个唯一的标识名，系统就会容易地区分它们。在程序唯一的标识名，系统就会容易地区分它们。在程序的描述中，可用下列标准形式来描述临界区：的描述中，可用下列标准形式来描述临界区：when类名类名do临界区临界区od设类设类 getspace，release 的类名为的类名为sp，则，则getspace和和release(ad)可重新描述为：可重新描述为：getspace:when sp d