第3章_操作系统_进程管理-new

1、第三章第三章 进程管理进程管理 3.1 进程的概念进程的概念3.2 进程的描述进程的描述 3.3进程状态及其转换进程状态及其转换 3.5 进程互斥进程互斥3.4 进程控制进程控制第三章第三章 进程管理进程管理 3.6 进程同步进程同步3.7 进程通信进程通信 3.8 死锁问题死锁问题 3.10 线程分类与执行线程分类与执行3.9 线程的概念线程的概念3.1 3.1 进程的概念进程的概念 3.1.1 程序的并发执行程序的并发执行 3.1.2 进程的定义进程的定义 显然，程序的显然，程序的顺序执行顺序执行具有如下具有如下三特点三特点：（1 1）顺序性）顺序性程序所规定的动作在机器上严格地按顺序执行

2、。每个动作的执行程序所规定的动作在机器上严格地按顺序执行。每个动作的执行都以前一个动作的结束为前提条件，即：都以前一个动作的结束为前提条件，即：程序和机器执行它的活程序和机器执行它的活动严格一一对应动严格一一对应。（2 2）封闭性）封闭性程序执行得到的最终结果由给定的初始条件决定，不受外界因素程序执行得到的最终结果由给定的初始条件决定，不受外界因素的影响。即：的影响。即：只有程序本身的动作才能改变程序的运行环境只有程序本身的动作才能改变程序的运行环境。（3 3）可再现性）可再现性顺序执行的最终结果与程序运行的速度无关顺序执行的最终结果与程序运行的速度无关，只要输入，只要输入的初始条件相同，的初

3、始条件相同，则：无论何时重复执行该程序，都会得到相同的结果，则：无论何时重复执行该程序，都会得到相同的结果，且：且：CPUCPU在执行程序时，任意两个动作之间的停顿对程在执行程序时，任意两个动作之间的停顿对程序的计算结果都不会产生影响。序的计算结果都不会产生影响。 在许多情况下，要求计算机能够在许多情况下，要求计算机能够同时处理同时处理多个具多个具有独立功能的程序，以增强系统的处理能力和提高有独立功能的程序，以增强系统的处理能力和提高机器的利用率。机器的利用率。 通常采用通常采用并行操作并行操作技术，使系统的各种硬件资源技术，使系统的各种硬件资源尽量做到并行工作，这就形成了尽量做到并行工作，这

4、就形成了多道程序系统多道程序系统，此，此时，允许时，允许多个多个程序同时进入程序同时进入内存内存并运行。并运行。 这样，程序执行环境具有下述这样，程序执行环境具有下述3 3个特点个特点：3） 多道程序系统中程序执行环境的变化多道程序系统中程序执行环境的变化（1 1）独立性）独立性在多道程序环境下，执行的每道程序都是在多道程序环境下，执行的每道程序都是逻辑上逻辑上独立的，且执行独立的，且执行速度与其它程序无关，执行的速度与其它程序无关，执行的起止时间起止时间也是独立的。也是独立的。（2 2）随机性）随机性在多道程序环境下，程序和数据的在多道程序环境下，程序和数据的输入输入与执行与执行开始时间开始

5、时间都是随机都是随机的。的。（3 3）资源共享性）资源共享性一般来说，多道程序环境下，执行程序的一般来说，多道程序环境下，执行程序的道数道数总是总是多于多于计算机系计算机系统中的统中的CPUCPU的的个数个数，单，单CPUCPU系统更是如此。系统更是如此。显然，同时执行的各个程序只能共享系统中已有的显然，同时执行的各个程序只能共享系统中已有的CPUCPU。同样，同样，输入输出设备输入输出设备、内存内存、信息信息等资源都将被各个程序所共享。等资源都将被各个程序所共享。资源共享将导致对进程执行速度的资源共享将导致对进程执行速度的制约制约。 所谓程序所谓程序并发执行并发执行，是指：，是指：一组一组在

6、逻辑上在逻辑上相互独立的程序或程序段相互独立的程序或程序段在在执行过程中，其执行过程中，其执行时间执行时间在客观上在客观上互相重叠互相重叠，即在计算机系统中，即在计算机系统中同同处于已处于已开始执行开始执行且且尚未结束尚未结束的状态。的状态。 假设有假设有3 3个个作业，每个作业，每个作业作业I I都由都由3 3个个程序段组成：程序段组成：（1 1）IIII（从输入机上读入第（从输入机上读入第I I个作业的信息）；个作业的信息）；（2 2）PIPI（处理第（处理第I I个作业）；个作业）；（3 3）OIOI（输出第（输出第I I个作业的结果到输出机上）。个作业的结果到输出机上）。 则在多道程序

7、环境下，它们可以如则在多道程序环境下，它们可以如图图3.23.2所示方式执行。所示方式执行。4）程序的并发执行）程序的并发执行4）程序的并发执行）程序的并发执行 对于对于任何一个作业任何一个作业I I，其输入，其输入IIII、处理、处理PIPI、输出、输出OIOI这这三个三个操作必须顺序操作必须顺序执行；执行； 但对于这但对于这三个作业三个作业而言，则有而言，则有可能并发可能并发执行。例如，输入执行。例如，输入程序在输入完第程序在输入完第I I个作业程序后，处理程序在对第个作业程序后，处理程序在对第I I个作业进行个作业进行处理的同时，再启动输入程序，输入第处理的同时，再启动输入程序，输入第I

8、+1I+1个作业程序，这就个作业程序，这就使得使得第第I I个作业的输入个作业的输入和和第第I+1I+1个作业的处理个作业的处理能能并发并发执行。执行。并发执行不同于并行执行。程序的并发执行不同于并行执行。程序的并行执行并行执行是指一组程序按是指一组程序按独立的、异步的独立的、异步的速度执行。速度执行。4）程序的并发执行）程序的并发执行 在图在图3.23.2中中：I I1 1先于先于P P1 1和和I I2 2；P P1 1先于先于O O1 1和和P P2 2；O O1 1先于先于O O2 2； 说明了有些程序段必须在其它程序段说明了有些程序段必须在其它程序段之前之前完成；完成； 此外此外可以

9、看出可以看出：P P1 1和和I I2 2；O O1 1和和P P2 2、I I3 3；O O2 2和和P P3 3 ； 是时间上是时间上同时同时发生的，即它们可发生的，即它们可并行并行执行。执行。 因此，三个作业的有些部分必须因此，三个作业的有些部分必须顺序顺序执行，有些则能执行，有些则能并行并行执行，执行，称称：它们是：它们是并发并发执行的作业。执行的作业。 对于相邻的语句对于相邻的语句S1和和S2，如果有下面的条件同时成立，如果有下面的条件同时成立，则则S1和和S2可以并发执行：可以并发执行：R（S1）W（S2）=W（S1）R（S2）=W（S1）W（S2）=其中其中R是语句的读变量集合，

10、是语句的读变量集合，W是语句是写变量集合。是语句是写变量集合。4）程序的并发执行）程序的并发执行并发的条件：并发的条件：顺序执行顺序执行并发执行并发执行执行过程执行过程顺序顺序并发并发程序和执行的对应关程序和执行的对应关系系一一对应一一对应一对多一对多封闭性封闭性独占资源独占资源共享资源共享资源确定性确定性具有具有无无可再现性可再现性具有具有无无程序间关系程序间关系无无有间接或直接制约关系有间接或直接制约关系顺序和并发执行比较顺序和并发执行比较4）程序的并发执行）程序的并发执行 引入程序并发执行，是为了充分利用系统引入程序并发执行，是为了充分利用系统资源，提高计算机的处理能力。资源，提高计算机

11、的处理能力。 但是，程序并发执行也会带来一些问题但是，程序并发执行也会带来一些问题4）程序的并发执行）程序的并发执行程序并发执行可能产生的问题程序并发执行可能产生的问题 两个程序段两个程序段getaddr（top）：从指定的栈取地址；）：从指定的栈取地址；reladdr（blk）：将地址）：将地址blk放入栈中。放入栈中。 分别独立地运行。可能出现下面的问题：分别独立地运行。可能出现下面的问题： 产生问题的原因是由于两段程序共享资源产生问题的原因是由于两段程序共享资源S栈。由此可栈。由此可见，多个程序并发执行，如果对资源、执行速度不进见，多个程序并发执行，如果对资源、执行速度不进行控制有可能产

12、生错误的结果。行控制有可能产生错误的结果。 控制占用资源和运行的单位以程序不合适，应该用更控制占用资源和运行的单位以程序不合适，应该用更小的、动态的概念为单位。小的、动态的概念为单位。4）程序的并发执行）程序的并发执行3.1 3.1 进程的概念进程的概念 3.1.1 程序的并发执行程序的并发执行 3.1.2 进程的定义进程的定义 为什么要引入为什么要引入“进程进程”的概念的概念 并发程序和顺序程序有并发程序和顺序程序有本质上的差异本质上的差异。为了能更好。为了能更好地描述程序的并发执行，实现操作系统的并发性和地描述程序的并发执行，实现操作系统的并发性和共享性，引入共享性，引入“进程进程”的概念

13、。的概念。 关键是关键是“共享资源共享资源”引起的，从资源观点看，有效引起的，从资源观点看，有效管理共享资源（同步操作、异步操作、通信）是操管理共享资源（同步操作、异步操作、通信）是操作系统的重要内容。作系统的重要内容。 3.1.2 3.1.2 进程的定义进程的定义 进程（进程（process）：是一个具有独立功能的程序对某）：是一个具有独立功能的程序对某个数据集在处理机上的个数据集在处理机上的执行过程执行过程和分配资源的和分配资源的基本基本单位单位。进程与程序的联系进程与程序的联系 程序是构成进程的组成部分之一。程序是构成进程的组成部分之一。 一个进程的运行目标是执行它所对应的程序，如果一个

14、进程的运行目标是执行它所对应的程序，如果没有程序，进程就失去了其实际存在的意义。没有程序，进程就失去了其实际存在的意义。 从静态的角度看，进程是由程序、数据和进程控制从静态的角度看，进程是由程序、数据和进程控制块（块（PCB）三部分组成。）三部分组成。程序和进程的区别程序和进程的区别程序程序 进程进程 静态的指令序列静态的指令序列进程是一个动态的概念。进程是一个动态的概念。程序没有并行特征程序没有并行特征进程具有并行特征进程具有并行特征, ,是竞争系是竞争系统资源的基本单位。统资源的基本单位。一个程序可对应多个进程一个程序可对应多个进程一个进程至少对应一个程序一个进程至少对应一个程序在工作（父

15、子进程有可能两在工作（父子进程有可能两个进程对应一个程序）个进程对应一个程序）程序是永久性的软件资源程序是永久性的软件资源暂存资源暂存资源, , 动态过程动态过程进程的五个基本特征进程的五个基本特征 动态性动态性：进程是程序在并发系统内的一次执行，一个进程：进程是程序在并发系统内的一次执行，一个进程有一个从产生到消失的生命期；有一个从产生到消失的生命期； 并发性并发性：正是为了描述程序在并发系统内执行的动态特性：正是为了描述程序在并发系统内执行的动态特性才引入了进程，没有并发就没有进程；才引入了进程，没有并发就没有进程； 独立性独立性：每个进程的程序代码都是相对独立的顺序程序，：每个进程的程序

16、代码都是相对独立的顺序程序，可以按照自己的方向和速度独立地向前推进；可以按照自己的方向和速度独立地向前推进； 制约性：制约性：进程之间的相互制约，主要表现在互斥地使用资进程之间的相互制约，主要表现在互斥地使用资源和相关进程之间必要的同步和通讯；源和相关进程之间必要的同步和通讯； 结构性：结构性：进程静态结构进程静态结构=PCB+=PCB+程序程序+ +数据集合。数据集合。3.2 3.2 进程的描述进程的描述 3.2.1 进程控制块进程控制块PCB 3.2.2 进程上下文进程上下文 3.2.3 进程上下文切换进程上下文切换 3.2.4 进程空间与大小进程空间与大小 3.2.1 3.2.1 进程控

17、制块进程控制块PCBPCB 进程控制块是系统感知进程的进程控制块是系统感知进程的唯一实体唯一实体。其主要内容包括。其主要内容包括(几百几百-上千字节上千字节)： 描述信息描述信息:进程号进程号,用户标识用户标识,家族关系家族关系 控制信息控制信息:进程当前状态进程当前状态,进程预先级进程预先级,程序开始地址程序开始地址,各种各种计时统计计时统计,通信信息通信信息 资源管理信息资源管理信息:占用内存大小占用内存大小,内存管理用的数据结构指内存管理用的数据结构指针针,共享程序段大小和起始地址共享程序段大小和起始地址,输入输出设备号输入输出设备号,传送数传送数据的长度据的长度/缓冲区地址缓冲区地址/

18、与设备管理相关的数据结构指针与设备管理相关的数据结构指针,指向文件系统的指针及有关标识指向文件系统的指针及有关标识 CPU现场保护结构现场保护结构3.2.1 3.2.1 进程控制块进程控制块PCBPCB进程控制块是进程存在的进程控制块是进程存在的标志标志，当系统创建一个进，当系统创建一个进程时，实际上就是为其建立一个进程控制块。程时，实际上就是为其建立一个进程控制块。 注意：进程控制块由于比较大，所以，内存中只存注意：进程控制块由于比较大，所以，内存中只存放放常用的部分常用的部分（例如（例如CPU现场保护、进程描述信息、现场保护、进程描述信息、控制信息等），而大部分信息存放在控制信息等），而大

19、部分信息存放在外存外存，待进程，待进程运运行时行时与其他数据一起与其他数据一起装入内存装入内存。3.2.2 3.2.2 进程上下文进程上下文 进程上下文：进程上下文：是进程是进程执行过程执行过程中中顺序关联顺序关联的的静态静态描述描述，包括：与进程相关的各种寄存器的值、正，包括：与进程相关的各种寄存器的值、正文段、数据集、各种堆栈值和文段、数据集、各种堆栈值和PCB结构。结构。3.2.2 3.2.2 进程上下文进程上下文 进程上下文有：用户级上下文、系统级上下文、寄存器上下文等。进程上下文有：用户级上下文、系统级上下文、寄存器上下文等。 系统级上下文有动态和静态部分组成。动态部分是各种寄存器的

20、值、记录系统级上下文有动态和静态部分组成。动态部分是各种寄存器的值、记录进入和退出各层时，系统记录的各层上下文中相关联的寄存器的值。进入和退出各层时，系统记录的各层上下文中相关联的寄存器的值。 进程上下文切换发生在不同的进程之间进程上下文切换发生在不同的进程之间图图3.3UNIX System 进程上下文组成进程上下文组成 当发生过当发生过程调用或程调用或者中断时者中断时必须保存必须保存和恢复的和恢复的信息。信息。用户执行用户执行程序和数程序和数据据处理器的处理器的状态信息状态信息包含着每包含着每个进程的个进程的控制信息。控制信息。3.2.2 3.2.2 进程上下文进程上下文3.2.3 3.2

21、.3 进程上下文切换进程上下文切换 进程上下文切换步骤进程上下文切换步骤：1）保存被）保存被切换进程的正文部分至有关存储区。切换进程的正文部分至有关存储区。2）把原来的进程移至合适的队列把原来的进程移至合适的队列-就绪、阻塞，选择另一个要执行的就绪、阻塞，选择另一个要执行的进程进程。3）将被选中进程的原来被）将被选中进程的原来被包保存的正文部分从相关存储区中包保存的正文部分从相关存储区中取出，并送至有关寄存器和堆栈，取出，并送至有关寄存器和堆栈，激活被选中进程执行激活被选中进程执行。 3.2.43.2.4进程空间与大小进程空间与大小进程空间进程空间：任一进程均有一个自己的地址空间，把该：任一进

22、程均有一个自己的地址空间，把该 空间称为进程控间或虚空间。空间称为进程控间或虚空间。进程空间大小进程空间大小只与处理机位数有关。只与处理机位数有关。例如例如32位长的处理位长的处理机进程空间大小为机进程空间大小为232=4GB.3.2.43.2.4进程空间与大小进程空间与大小为了防止用户程序访问系统空间为了防止用户程序访问系统空间,造成错误造成错误,计算机系统通过计算机系统通过程序状态寄存器等设置不同的执行模式程序状态寄存器等设置不同的执行模式,即用户模式即用户模式(用户态用户态)和系统模式和系统模式(系统态系统态)来进程保护来进程保护.只能由操只能由操作系统来作系统来访问空间访问空间3.3

23、3.3 进程状态及其转换进程状态及其转换 3.3.1 进程状态进程状态 3.3.2 进程状态的转换进程状态的转换 3.3.1 3.3.1 进程状态进程状态 初始态：初始态：一个进程在刚创建时处于一个进程在刚创建时处于“初始初始”状态。状态。 终止态：终止态：一个进程在运行终止后处于一个进程在运行终止后处于“终止终止”状态。状态。 运行状态运行状态：进程已：进程已获得获得处理机，并且在处理机，并且在CPU上上执行执行的的状态。单状态。单CPU系统中，任一时刻处于执行状态的进程系统中，任一时刻处于执行状态的进程只能有一个。只能有一个。 就绪状态就绪状态：一个进程已经：一个进程已经具备具备运行条件，

24、但由于运行条件，但由于没没有有获得获得处理机处理机而不能运行时所处的状态。一旦把而不能运行时所处的状态。一旦把CPU分配给它，该进程就可运行。处于就绪状态的进程分配给它，该进程就可运行。处于就绪状态的进程可以是可以是多个多个。 等待状态等待状态也称也称阻塞阻塞状态或状态或封锁封锁状态，是指：进程状态，是指：进程因因等待等待某种事件发生而暂时某种事件发生而暂时不能不能运行的状态。系统运行的状态。系统中处于等待状态的进程可以有中处于等待状态的进程可以有多个多个。 引起等待的原因一旦消失，进程便转为就绪状态，引起等待的原因一旦消失，进程便转为就绪状态，以便在适当的时候投入运行。以便在适当的时候投入运

25、行。3.3.1 进程状态进程状态一个进程在执行期间不断在一个进程在执行期间不断在“就绪就绪”、“执行执行”和和“等待等待”三种基本状态之间转换，以三种基本状态之间转换，以“走走停停走走停停”方方式向前推进。式向前推进。等待等待（不能占用（不能占用CPUCPU）就绪就绪（尚未占（尚未占用用CPUCPU）执行执行（正在占用（正在占用CPUCPU）等待事件等待事件事件发生事件发生时间片到时间片到调度选中进入调度选中进入初始初始终止终止 3.3.2 进程状态转换进程状态转换3.4 3.4 进程控制进程控制 3.4.1 进程创建与撤销进程创建与撤销 3.4.2 进程阻塞与唤醒进程阻塞与唤醒 3.4 3.

26、4 进程控制进程控制 进程控制进程控制：系统使用一些具有特定功能的程序段（原语）来：系统使用一些具有特定功能的程序段（原语）来创建、撤销进程以及完成进程个状态间的转换，从而达到多进创建、撤销进程以及完成进程个状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。程高效率并发执行和协调、实现资源共享的目的。 原语原语：在：在系统态系统态下执行的具有特定功能的下执行的具有特定功能的程序段程序段，原语分为，原语分为指令级原语和功能级原语。指令级原语和功能级原语。 （1）指令级原语指令级原语：执行期间不允许中断，是不可分割的单位。：执行期间不允许中断，是不可分割的单位。 （2）功能级原

27、语功能级原语：执行期间不允许并发的程序段。：执行期间不允许并发的程序段。 原语的特点：原语的特点： a、具有独立的系统功能；、具有独立的系统功能； b、在系统态运行；、在系统态运行； c、不允许中断或不允许并发。、不允许中断或不允许并发。 3.4 进程控制进程控制1、进程创建、进程创建 （1）创建方式：）创建方式： a、由系统程序模块统一创建，各进程关系平等；、由系统程序模块统一创建，各进程关系平等； b、由父进程创建、由父进程创建 进程之间存在隶属关系，形成家族关系；进程之间存在隶属关系，形成家族关系； 属于某家族的一个进程可以继承父进程的资源。属于某家族的一个进程可以继承父进程的资源。 3

28、.4.1 进程创建与撤销进程创建与撤销入口入口查查PCB链表链表有 空有 空PCB创建失败创建失败取空取空PCB（i）将有关参数填入将有关参数填入PCB(i)相应项相应项PCB(i)入就绪队列入就绪队列PCB(i)入进程家族或进程链入进程家族或进程链返回返回 创建一个进程的创建一个进程的主要任务主要任务是是建立建立进程控制块进程控制块PCBPCB。 其其具体操作过程具体操作过程是：是： 先先申请申请一一空闲空闲PCBPCB区域，区域， 将有关信息将有关信息填入填入PCBPCB， 置该进程为置该进程为就绪就绪状态，状态， 最后把它最后把它插入插入就绪队列中。就绪队列中。（2）进程的创建过程）进程

29、的创建过程 2、进程撤销：、进程撤销： （1）引起进程撤销的原因：）引起进程撤销的原因： a、该进程已完成所要求的功能而正常终止；、该进程已完成所要求的功能而正常终止； b、由于某种错误而导致非正常终止；、由于某种错误而导致非正常终止； c、祖先进程要求撤销某个子进程。、祖先进程要求撤销某个子进程。 （2）撤销的任务：）撤销的任务： a、释放所占有的所有资源；、释放所占有的所有资源； b、释放相应的、释放相应的PCB或子进程相应的或子进程相应的PCB。 3.4.1 进程创建与撤销进程创建与撤销（3 3）撤销的过程）撤销的过程 ： 找到要被撤消进程的找到要被撤消进程的PCBPCB， 将它从所在队

30、列中消去，将它从所在队列中消去， 撤消属于该进程的一切撤消属于该进程的一切“子孙进程子孙进程”， 释放被撤消进程所占用的全部资源，释放被撤消进程所占用的全部资源， 并消去被撤消进程的并消去被撤消进程的PCBPCB。3.4.1 进程创建与撤销进程创建与撤销 2、进程撤销（、进程撤销（p50页流程图）：页流程图）：3.4.1 进程的阻塞与唤醒进程的阻塞与唤醒 1、进程的阻塞、进程的阻塞（执行态到等待态）（执行态到等待态）处于执行状态的进程由于需等待外部事件的发生而处于执行状态的进程由于需等待外部事件的发生而调用调用block原语将自己从执行态变为等待态。原语将自己从执行态变为等待态。其具体操作过程

31、是：其具体操作过程是： 由于进程正处于运行状态，因此首先应中断由于进程正处于运行状态，因此首先应中断CPUCPU执行；执行； 把把CPUCPU的当前状态保存在的当前状态保存在PCBPCB的现场信息中；的现场信息中； 把进程的当前状态置为等待状态；把进程的当前状态置为等待状态； 并把它插入到该事件的等待队列中去。并把它插入到该事件的等待队列中去。3.4.1 进程的阻塞与唤醒进程的阻塞与唤醒 1、进程的唤醒、进程的唤醒（等待态到就绪态）（等待态到就绪态）当等待队列中的进程所等待的事件发生时，待事件当等待队列中的进程所等待的事件发生时，待事件的所有进程都将被唤醒，即从等待态变为就绪态。的所有进程都将

32、被唤醒，即从等待态变为就绪态。唤醒的方法唤醒的方法有：有： a、由系统进程唤醒由系统进程唤醒 系统进程统一控制事件的发生系统进程统一控制事件的发生 并将并将“事件发生事件发生”这一消息通知等待进程，从而这一消息通知等待进程，从而使使 进程从等待态变为就绪态；进程从等待态变为就绪态； b、由事件发生进程唤醒由事件发生进程唤醒 这种情况下，事件发生进这种情况下，事件发生进 程和被唤醒进程之间是合作关系。程和被唤醒进程之间是合作关系。 其其具体操作过程具体操作过程是：是： 在在等待队列等待队列中找到该进程，中找到该进程， 置进程的当前状态为置进程的当前状态为就绪状态就绪状态， 然后将它从等待队列中撤

33、出并插入到然后将它从等待队列中撤出并插入到就绪队列就绪队列中排队，等待处理机调度执行。中排队，等待处理机调度执行。 3.4.1 进程的阻塞与唤醒进程的阻塞与唤醒 1、进程的唤醒、进程的唤醒（等待态到就绪态）（等待态到就绪态）PCB表组织方式表组织方式3.5 3.5 进程互斥进程互斥 3.5.1 共享资源所引起的制约共享资源所引起的制约 3.5.2 互斥的加锁实现互斥的加锁实现 3.5.3 用用P、V原语实现进程互斥原语实现进程互斥3.5.1 3.5.1 共享资源所引起的制约共享资源所引起的制约1 1）相关进程和无关进程）相关进程和无关进程 多道程序系统中，同时运行的并发进程通常有多道程序系统中

34、，同时运行的并发进程通常有多个。多个。 在在逻辑逻辑上上具有具有某种某种联系联系的进程称为的进程称为相关相关进程，进程， 在在逻辑逻辑上上没有没有任何任何联系联系的进程称为的进程称为无关无关进程。进程。3.5.1 3.5.1 共享资源所引起的制约共享资源所引起的制约 2 2）进程间的相互作用）进程间的相互作用 多道程序系统中，由于资源共享、进程合作，而产生进程之间的相互制约这种相互制约的多道程序系统中，由于资源共享、进程合作，而产生进程之间的相互制约这种相互制约的关系称做关系称做进程间的相互作用进程间的相互作用；因因共享资源的方式不同共享资源的方式不同，而导致进程间两种不同的制约关系，而导致进

35、程间两种不同的制约关系（1 1）间接制约（进程互斥，）间接制约（进程互斥，可发生在可发生在相关进程相关进程之间，也可发生在之间，也可发生在无关进程无关进程之间之间）由于共享资源而引起的由于共享资源而引起的临界区临界区内不允许并发进程内不允许并发进程交叉执行交叉执行的现象，称为由的现象，称为由共享公有资源共享公有资源而造成而造成的对并发进程执行速度的的对并发进程执行速度的间接制约间接制约（2 2） 直接制约（进程同步，直接制约（进程同步，只发生在只发生在相关进程相关进程之间之间）由于并发进程由于并发进程互相共享对方的私有资源互相共享对方的私有资源所引起的直接制约。所引起的直接制约。 3.5.1

36、3.5.1 共享资源所引起的制约共享资源所引起的制约 预售票系统，两个终端，运行预售票系统，两个终端，运行T1、T2进程进程T1 : T2:. .Read(x); Read(x);if x=1 then if x=1 then x:=x-1; x:=x-1;write(x); write(x);. .（1）（2）（3）（4）（5）（6） 3.5.1 共享资源所引起的制约共享资源所引起的制约 临界资源：临界资源：系统中一些资源系统中一些资源一次一次只允许只允许一个一个进程使用，进程使用，这类资源称为临界资源这类资源称为临界资源(critical resources) 。例如：公共变量例如：公共变

37、量X X临界区：临界区：进程中进程中访问临界资源访问临界资源的那一段的那一段程序程序，称为临，称为临界区界区(critical region) 。例如：程序例如：程序T1 T2T1 T2 互斥：不允许两个以上互斥：不允许两个以上的共享该资源的的共享该资源的并发进程同时并发进程同时进入进入临界区称为互斥临界区称为互斥。例如：进程例如：进程T1T1和和T2T2之间的关系，多个进程在竞争使用之间的关系，多个进程在竞争使用一台打印机。一台打印机。 3.5.1 3.5.1 共享资源所引起的制约共享资源所引起的制约 空闲让进：空闲让进：当无进程在临界区时，任何有权使用临界区的进程可当无进程在临界区时，任何

38、有权使用临界区的进程可进入；进入； 多中择一多中择一：当没有进程在临界区，如果有：当没有进程在临界区，如果有若干若干进程申请进入临界进程申请进入临界区时，只允许一个进程区时，只允许一个进程进入进入临界区临界区，其他进程必须等待；，其他进程必须等待； 平等竞争：平等竞争：任何进程任何进程无权停止其它进程的运行无权停止其它进程的运行，进程之间相对运行，进程之间相对运行速度无硬性规定；速度无硬性规定；让权等待：让权等待：处于等待状态的进程应处于等待状态的进程应放弃占用放弃占用CPU；有限等待：有限等待：任何进入临界区的要求应在任何进入临界区的要求应在有限的时间有限的时间内得到满足内得到满足使用临界区

39、应遵循的使用临界区应遵循的准则准则：3.5 3.5 进程互斥进程互斥 3.5.1 共享资源所引起的制约共享资源所引起的制约 3.5.2 互斥的加锁实现互斥的加锁实现 3.5.3 用用P、V原语实现进程互斥原语实现进程互斥3.5.2 3.5.2 互斥的加锁实现互斥的加锁实现 思路：思路： 1 1）并发进程申请进入临界区时，）并发进程申请进入临界区时，首先测试首先测试该临界该临界区是否是上锁的。如果该临界区已被锁住，则该进区是否是上锁的。如果该临界区已被锁住，则该进程要等到该临界区程要等到该临界区开锁之后开锁之后才有可能才有可能获得临界区获得临界区。 2 2）当某个进程）当某个进程进入临界区进入临

40、界区之后，它将之后，它将锁上锁上临界区，临界区，直到直到它它退出退出临界区时为止。临界区时为止。 3.5.2 3.5.2 互斥的加锁实现互斥的加锁实现 实现：实现： 设置一锁位：设设置一锁位：设keyS = 1表示临界资源表示临界资源S相关的临界区可相关的临界区可用用, 且仅允许一个进程使用；且仅允许一个进程使用；keyS= 0临界资源临界资源S相关的相关的临界区不可用。临界区不可用。 加锁后的临界区程序描述如下：加锁后的临界区程序描述如下： lock(keyS) Read(x); if x=1 then x:=x-1; write(x); unlock(keyS) 临界区临界区3.5.2 3

41、.5.2 互斥的加锁实现互斥的加锁实现 实现：实现： unlock(keyS) lock(keyS) 满足满足keyS=0时不允许任何进程进入临界时不允许任何进程进入临界区，区， keyS=1时仅允许一个进程进入临界区。时仅允许一个进程进入临界区。keyS=1lock(x) begin local v repeat vx until vl x0 end 有问题吗？有问题吗？增加增加“测试与设置测试与设置”指令指令3.5.2 3.5.2 互斥的加锁实现互斥的加锁实现 分析：分析： 一个进程能否进入临界区是依靠自己的测试，容易造成一个进程能否进入临界区是依靠自己的测试，容易造成忙忙等等和和不公平不

42、公平。PA A：lock(keyS) unlock(keyS) Goto A PB B：lock(keyS) S unlock(keyS) Goto B 3.5 3.5 进程互斥进程互斥 3.5.1 共享资源所引起的制约共享资源所引起的制约 3.5.2 互斥的加锁实现互斥的加锁实现 3.5.3 用用P、V原语实现进程互斥原语实现进程互斥 3.5.3 3.5.3 用用P P、V V原语实现进程互斥原语实现进程互斥信号量（信号量（semaphore）：）：一种一种特殊特殊的的变量变量，只能，只能被被特殊的操作特殊的操作（即（即P操作和操作和V操作）使用。它的操作）使用。它的表表面形式面形式是：是：

43、一个整型变量一个整型变量附加附加一个队列一个队列(等待该信等待该信号量的进程队列号量的进程队列)。 3.5.3 3.5.3 用用P P、V V原语实现进程互斥原语实现进程互斥 P原语操作原语操作的主要动作：的主要动作： (1) sem减减1； (2) 若若sem减减1后仍后仍大于或等于大于或等于 零零，则进程，则进程继续执行继续执行； (3) 若若sem减减l后后小于零小于零， 则该进程被则该进程被阻塞在阻塞在与该信与该信 号相对应的号相对应的队列中队列中，然后，然后 转进程调度转进程调度。 semSem0时，表示尚时，表示尚有资源有资源可分配；可分配；3) 当当Sem=0时，表示该资源刚时，

44、表示该资源刚分配完分配完；4) 当当Sem0时，表示已时，表示已无资源无资源可分配，可分配， 此时此时Sem的的绝对值绝对值表示表示Sem信号量信号量等待等待队列中进程的队列中进程的数目数目。5) 每执行一次每执行一次P操作操作，意味着要求，意味着要求分配分配一个一个资源资源；6) 每执行一次每执行一次V操作操作，意味着，意味着释放释放一个一个资源资源。 3.5.3 3.5.3 用用P P、V V原语实现进程互斥原语实现进程互斥用用P、V原语实现进程互斥原语实现进程互斥： (1) (2) P(sem) V(sem)P1P2P3临界区临界区 P(sem) P(sem) V(sem) V(sem)

45、 3.5.3 3.5.3 用用P P、V V原语实现进程互斥原语实现进程互斥用用P、V原语实现进程互斥原语实现进程互斥：（1）互斥）互斥信号量信号量sem=1 （2）将临界区置于将临界区置于P/V操作之间操作之间。当一个进程要进入临界区。当一个进程要进入临界区时，必须时，必须先执行先执行P操作操作将信号量将信号量sem减减1，进程完成对临界区，进程完成对临界区的操作之后，必须的操作之后，必须执行执行V操作操作，释放它所占用的临界区。，释放它所占用的临界区。（3）当一个进程已经进入了临界区之后，另一个进程想进入）当一个进程已经进入了临界区之后，另一个进程想进入临界区时，也应先执行临界区时，也应先

46、执行P操作，使操作，使sem值变为负值，将自己阻值变为负值，将自己阻塞，直到前一个进程执行了塞，直到前一个进程执行了V操作之后，唤醒阻塞队列中的一操作之后，唤醒阻塞队列中的一个进程，使其变为就绪状态，经调度程序选中，占用个进程，使其变为就绪状态，经调度程序选中，占用CPU，进入临界区进入临界区 模拟执行模拟执行序号序号P1P2P3S说明说明01资源未占用资源未占用1P(s)P1进入占资源进入占资源2P(s)P2进入无资源进入无资源3P(s)P3进入无资源进入无资源4V(s)P1释放资源释放资源P2解封解封5V(s)P2释放资源释放资源P3解封解封6V(s)P3释放资源释放资源7可反复执行可反复

47、执行0-1-2-1011 3.5.3 3.5.3 用用P P、V V原语实现进程互斥原语实现进程互斥使用使用P、V操作应操作应注意注意的事项的事项 ： (1) (2) 为什么？为什么？3.6 3.6 进程同步进程同步 3.6.1 同步的概念同步的概念 3.6.2 私用信号量私用信号量 3.6.3 用用P、V原语实现进程同步原语实现进程同步 3.6.4 生产者生产者消费者问题消费者问题 3.6.1 3.6.1 同步的概念同步的概念 例子例子： 计算进程和打印进程计算进程和打印进程共同使用共同使用同一缓冲区同一缓冲区Buf。 计算进程反复地把每次计算结果计算进程反复地把每次计算结果放入放入Buf中

48、，中， 而打印进程则把计算进程每次放入而打印进程则把计算进程每次放入Buf中的数据通过打印机中的数据通过打印机打打印输出印输出。 如果不采取任何制约措施，这两个进程的执行起始时间和执行如果不采取任何制约措施，这两个进程的执行起始时间和执行速度都是彼此独立的，其相应的控制段可以描述为：速度都是彼此独立的，其相应的控制段可以描述为： Pc： A： local tempBuf Repeat Buf tempBuf Until Buf 空空 计算计算 得到计算结果得到计算结果 tempBuf计算结果计算结果 Goto A PP： B： local Pri Repeat PriBuf Until Pri

49、 空空 打印打印Buf中的数据中的数据 清除清除Buf中的数据中的数据 Goto B 3.6.1 同步的概念同步的概念 3.6.1 3.6.1 同步的概念同步的概念 把异步环境下的一组并发进程，因把异步环境下的一组并发进程，因直接制约直接制约而互相而互相合作、互相等待，使得各进程按一定的速度执行的过程合作、互相等待，使得各进程按一定的速度执行的过程称为称为进程间的同步进程间的同步。具有同步关系的一组并发进程称为具有同步关系的一组并发进程称为合作进程合作进程合作进程间互相发送的信号称为合作进程间互相发送的信号称为消息或事件消息或事件。 3.6.1 3.6.1 同步的概念同步的概念 理解同步和互斥

50、理解同步和互斥： 进程互斥是进程间进程互斥是进程间共享资源共享资源的使用权，这种竞争的使用权，这种竞争没有固定的必然联系没有固定的必然联系，哪个进程竞，哪个进程竞争到使用权就归那个进程使用，直到不需要使用时再归还；争到使用权就归那个进程使用，直到不需要使用时再归还； 而而进程同步进程同步则涉及共享资源的并发进程间有一种则涉及共享资源的并发进程间有一种必然的联系必然的联系，当进程必须同步时，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资源。源。 如果对一个消息或事件赋以唯一的消息名

51、，则可用过程如果对一个消息或事件赋以唯一的消息名，则可用过程: wait (消息名消息名) 表示进程等待合作进程发来的消息表示进程等待合作进程发来的消息 signal (消息名消息名) 表示向合作进程发送消息。表示向合作进程发送消息。同步的消息实现机制同步的消息实现机制 3.6.1 同步的概念同步的概念 利用过程利用过程wait和和signal，可以简单地描述上面例子中，可以简单地描述上面例子中的计算进程的计算进程Pc和打印进程和打印进程Pp的同步关系如下：的同步关系如下：Pc： A：wait(Bufempty) 计算计算 Buf计算结果计算结果 Bufemptyfalse signal(Bu

52、ffull) Goto A PP： B：wait(Buffull) 打印打印Buf中的数据中的数据 清除清除Buf中的数据中的数据 Buffullfalse signal(Bufempty) Goto B 过程过程wait的功能是等待到消息名为的功能是等待到消息名为true的进程后继续执行，的进程后继续执行，而而signal的功能则是向合作进程发送合作进程所需要的消息的功能则是向合作进程发送合作进程所需要的消息名，并将其值置为名，并将其值置为true。 3.6 3.6 进程同步进程同步 3.6.1 同步的概念同步的概念 3.6.2 私用信号量私用信号量 3.6.3 用用P、V原语实现进程同步原

53、语实现进程同步 3.6.4 生产者生产者消费者问题消费者问题 各进程之间发送的各进程之间发送的消息消息作为作为信号量信号量看待。看待。与进程互斥时不同的是，这里的信号量只与与进程互斥时不同的是，这里的信号量只与制约进程及制约进程及被制约进程有关被制约进程有关而不是与整组并发进程有关。因此，称而不是与整组并发进程有关。因此，称该信号量为该信号量为私用信号量私用信号量(Private Semaphore)。一个进程一个进程Pi的私用信号量的私用信号量Semi是是从制约进程发送从制约进程发送来来的进程的进程Pi的执行条件所需要的消息的执行条件所需要的消息。与私用信号量相对应，称互斥时使用的信号量为公

54、用与私用信号量相对应，称互斥时使用的信号量为公用信号量。信号量。 3.6.2 私用信号量私用信号量 3.6 3.6 进程同步进程同步 3.6.1 同步的概念同步的概念 3.6.2 私用信号量私用信号量 3.6.3 用用P、V原语实现进程同步原语实现进程同步 3.6.4 生产者生产者消费者问题消费者问题 利用利用P，V原语实现进程同步的方法与利用原语实现进程同步的方法与利用wait和和signal过程时相同，分为三步。过程时相同，分为三步。 1) 为各并发进程为各并发进程设置私用信号量设置私用信号量 2) 为私用信号量为私用信号量赋初值赋初值 3) 利用利用P，V原语和私用信号量原语和私用信号量

55、规定规定各进程的各进程的执行顺序执行顺序 3.6.3 用用P、V原语实现进程同步原语实现进程同步例例：设进程设进程P PA A和和P PB B通过缓冲区队列传递数据通过缓冲区队列传递数据PA为发送进程为发送进程，PA发送数据时调用发送过程发送数据时调用发送过程deposit(data)，PB为接收进程为接收进程, PB接收数据时调用过程接收数据时调用过程remove(data)且且数据的发送和接收过程满足如下条件数据的发送和接收过程满足如下条件：(1)在在PA至少送一块数据入一个缓冲区之前，至少送一块数据入一个缓冲区之前，PB不可能从缓冲区中不可能从缓冲区中取出数据取出数据 (假定数据块长等于

56、缓冲区长度假定数据块长等于缓冲区长度)；(2) PA往缓冲队列发送数据时，至少有一个缓冲区是空的；往缓冲队列发送数据时，至少有一个缓冲区是空的；(3) 由由PA发送的数据块在缓冲队列中按先进先出发送的数据块在缓冲队列中按先进先出(FIFO)方式排列。方式排列。 3.6.3 用用P、V原语实现进程同步原语实现进程同步 3.6.3 用用P、V原语实现进程同步原语实现进程同步分步描述过程分步描述过程deposit(data)和和remove(data)：(1) 设设Bufempty为进程为进程PA的私用信号量的私用信号量， Buffull为进程为进程PB的私用信号量的私用信号量；(2) 令令Bufe

57、mpty的初始值为的初始值为n (n为队列中的缓冲区个数为队列中的缓冲区个数) Buffull的初始值为的初始值为0； (3) 描述：描述： PA：deposit(data)： begin local x P(Bufempty)； 按按FIFO方式选择一个空缓冲区方式选择一个空缓冲区Buf(x)； Buf(x)data Buf(x)置满标记置满标记 V(Buffull) end PB ：remove(data)： Begin local x P(Buffull)； 按按FIFO方式选择一个装满方式选择一个装满数据的缓冲区数据的缓冲区Buf(x) dataBuf(x) Buf(x)置空标记置空标

58、记 V(Bufempty) end 3.6.3 用用P、V原语实现进程同步原语实现进程同步3.6 3.6 进程同步进程同步 3.6.1 同步的概念同步的概念 3.6.2 私用信号量私用信号量 3.6.3 用用P、V原语实现进程同步原语实现进程同步 3.6.4 生产者生产者消费者问题消费者问题 3.6.4 生产者生产者消费者问题消费者问题 把并发进程的把并发进程的同步和互斥问题一般化同步和互斥问题一般化，可以得到一个，可以得到一个抽象的一般模型，即抽象的一般模型，即生产者生产者消费者问题消费者问题(producer-consumer problems) 。计算机系统中，每个进程都申请使用和释放各

59、种不同计算机系统中，每个进程都申请使用和释放各种不同类型的资源。类型的资源。把系统中把系统中使用使用某一类资源的进程称为该资源的某一类资源的进程称为该资源的消费者消费者而把而把释放释放同类资源的进程称为该资源的同类资源的进程称为该资源的生产者。生产者。把一个长度为把一个长度为n的有界缓冲区的有界缓冲区(n0)与一群生产者进程与一群生产者进程P1，P2，Pm和一群消费者进程和一群消费者进程C1，C2，Ck联联系起来系起来 3.6.4 生产者生产者消费者问题消费者问题 设生产者进程和消费者进程是设生产者进程和消费者进程是互相等效互相等效的，其中，各生产者进程的，其中，各生产者进程使用的过程使用的过

60、程deposit(data)和各消费者使用的过程和各消费者使用的过程remove(data)可可描述如下：描述如下：1. 首先首先生产者生产者消费者问题是一个消费者问题是一个同步问题同步问题。即生产者和消费者。即生产者和消费者之间满足如下条件：之间满足如下条件： 1)消费者想消费者想接收数据接收数据时，有界缓冲区中至少有时，有界缓冲区中至少有一个一个单元是单元是满的满的 2)生产者想生产者想发送数据发送数据时，有界缓冲区中至少有时，有界缓冲区中至少有一个一个单元是单元是空的空的2. 由于有界缓冲区是临界资源，因此，各生产者进程和各消费者由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程