计算机操作系统考研辅导--第二章

1、计算机操作系统计算机操作系统第二章第二章 进程同步与互斥进程同步与互斥2009年年1个选择、个选择、1个综合应用题个综合应用题2010年年3个选择题个选择题2011年年2个选择，个选择，1个综合应用题个综合应用题 进程管理是考试的热门。这一章出题的灵活进程管理是考试的热门。这一章出题的灵活性比较大，这部分考查的是操作系统性比较大，这部分考查的是操作系统5大管理功大管理功能之一：处理机管理，包括能之一：处理机管理，包括进程管理进程管理和和处理机调处理机调度度两大块的内容，是考试的重点内容，同时也是两大块的内容，是考试的重点内容，同时也是难点，因此对这部分除了要掌握基本的概念和基难点，因此对这部分

2、除了要掌握基本的概念和基本的原理外，还要求考生能运用这些基本原理去本的原理外，还要求考生能运用这些基本原理去分析和解决问题，其中分析和解决问题，其中P、V原语操作、同步问题原语操作、同步问题及死锁问题都有可能出综合应用题。及死锁问题都有可能出综合应用题。 进程同步与互斥是进程管理的重点，进程同步与互斥是进程管理的重点，也是操作系统学科的一个难点。这个考点的也是操作系统学科的一个难点。这个考点的知识，一般都会出现在考试试题中。具体包知识，一般都会出现在考试试题中。具体包括进程同步的基本概念、实现临界区互斥的括进程同步的基本概念、实现临界区互斥的基本方法基本方法(包括软件实现方法、硬件实现方包括软

3、件实现方法、硬件实现方法法)、信号量、信号量(P、V操作操作)、管程、经典同步、管程、经典同步问题问题(包括生产者包括生产者-消费者问题、读者消费者问题、读者-写者问写者问题、哲学家进餐问题等题、哲学家进餐问题等)。我们一定要掌握。我们一定要掌握P、V操作的概念、流程，以及操作的概念、流程，以及P、V操作在同步操作在同步问题、互斥问题中的应用。问题、互斥问题中的应用。 进程管理是操作系统的重要任务之一是使用进程管理是操作系统的重要任务之一是使用户充分、有效地利用系统资源，这部分：户充分、有效地利用系统资源，这部分： 首先要求掌握进程的概念，其中进程和程序首先要求掌握进程的概念，其中进程和程序这

4、两个概念的区别和联系一定要搞清楚；这两个概念的区别和联系一定要搞清楚； 第二要记住进程的三个基本状态以及它们之第二要记住进程的三个基本状态以及它们之间相互转换条件，一定要记住不可能从就绪间相互转换条件，一定要记住不可能从就绪状态直接转换到等待状态；状态直接转换到等待状态； 第三需要理解进程控制和原语这两个概念，第三需要理解进程控制和原语这两个概念，掌握进程的创建、撤销、阻塞、唤醒的条件，掌握进程的创建、撤销、阻塞、唤醒的条件，理解四种原语的执行过程；理解四种原语的执行过程； 第四理解什么是并发进程间的直接制约以及由直第四理解什么是并发进程间的直接制约以及由直接制约所引发的进程同步，分清什么是私

5、用信号接制约所引发的进程同步，分清什么是私用信号和公用信息，重点要掌握如何用和公用信息，重点要掌握如何用P、V原语操作实原语操作实现同步问题，要会利用现同步问题，要会利用P、V原语操作来解决经典原语操作来解决经典的同步问题；的同步问题； 第五是知道进程的通信方式及它们各自的特点；第五是知道进程的通信方式及它们各自的特点； 第六要理解进程和线程的异同以及多线程模型；第六要理解进程和线程的异同以及多线程模型； 最后一定要弄清楚什么是死锁产生的必要条件以最后一定要弄清楚什么是死锁产生的必要条件以及如何预防和避免死锁。及如何预防和避免死锁。第二章第二章 进程管理进程管理2.1 进程的基本概念进程的基本

6、概念2.2 进程控制进程控制2.3 进程同步进程同步2.4 经典进程的同步问题经典进程的同步问题2.5 进程通信进程通信2.6 线程线程基础知识总结基础知识总结实战练习实战练习综合应用题综合应用题 操作系统在管理进程与线程的过程中需要完成以操作系统在管理进程与线程的过程中需要完成以下工作：用户和系统进程的创建和删除；进程的下工作：用户和系统进程的创建和删除；进程的调度；为进程的同步、通信、死锁处理提供机制。调度；为进程的同步、通信、死锁处理提供机制。 多道程序设计的提出多道程序设计的提出 其基本思想是在主存中同时存放多个用户的作其基本思想是在主存中同时存放多个用户的作业，使之同时处于运行状态而

7、共享系统资源。之业，使之同时处于运行状态而共享系统资源。之所以采用多道程序设计技术，是由于中断和通道所以采用多道程序设计技术，是由于中断和通道技术的出现，技术的出现，CPU可以把直接控制输入可以把直接控制输入/输出的工输出的工作转给通道作转给通道 多道程序的目标、方法和主要问题多道程序的目标、方法和主要问题目标：是充分使用系统所有资源并尽可能地使它们目标：是充分使用系统所有资源并尽可能地使它们并行工作，这种技术可把硬件的代价交叉分布在并行工作，这种技术可把硬件的代价交叉分布在大量并行用户之间，而使计算机系统的代价极小大量并行用户之间，而使计算机系统的代价极小化。化。方法：是一个正在运行的程序不

8、使用某设备时，让方法：是一个正在运行的程序不使用某设备时，让另一程序去使用该设备。为了发挥多道程序设计另一程序去使用该设备。为了发挥多道程序设计的有效性，应选择各种不同类型的作业同时执行，的有效性，应选择各种不同类型的作业同时执行，让资源处于忙碌状态。让资源处于忙碌状态。多道程序设计实现的多道程序设计实现的3个问题：存储保护、程序浮个问题：存储保护、程序浮动、处理机和系统资源的管理和调度。动、处理机和系统资源的管理和调度。 多道程序系统所必须解决的问题多道程序系统所必须解决的问题（1）提出解决各种冲突的策略）提出解决各种冲突的策略（2）协调并发活动的关系）协调并发活动的关系（3）保证数据的一致

9、性）保证数据的一致性（4）实现数据的存取控制）实现数据的存取控制2.1 进程的基本概念进程的基本概念2.1.1 程序的顺序执行及其特征：顺序性、封闭程序的顺序执行及其特征：顺序性、封闭性、可再现性。性、可再现性。2.1.2 前趋图：描述进程之间执行的前后关系。前趋图：描述进程之间执行的前后关系。2.1.3 程序的并发执行及其特征：间断性程序的并发执行及其特征：间断性(制约制约性性)、失去封闭性、不可再现性。、失去封闭性、不可再现性。2.1.4 进程的特征与状态进程的特征与状态 引入进程的目的：引入进程的目的：是使多个程序能并发是使多个程序能并发执行，提高资源利用率和系统吞吐量执行，提高资源利用

10、率和系统吞吐量。进程的定义：进程包括程序代进程的定义：进程包括程序代码（程序段或文本段）、堆码（程序段或文本段）、堆栈段（临时数据，如函数参栈段（临时数据，如函数参数、返回地址和局部变量）、数、返回地址和局部变量）、数据段（包括全局变量）、数据段（包括全局变量）、堆（进行运行期间动态分配堆（进行运行期间动态分配的内存）的内存） 内存中的进程如右图示：内存中的进程如右图示：栈栈堆堆数据数据文本文本(1)特征：特征： 结构特征：程序段、相关的数据段和结构特征：程序段、相关的数据段和PCB构成的进程实体。构成的进程实体。 动态性：最基本。动态性：最基本。 并发性：并发性： 独立性：独立性： 异步性：

11、进程以各自独立的，不可预先的速度向前推进。异步性：进程以各自独立的，不可预先的速度向前推进。可能会造成不正确的情况出现，原因与进程占用处理器的可能会造成不正确的情况出现，原因与进程占用处理器的时间、执行的速度以及外界的影响有关，都与时间有关。时间、执行的速度以及外界的影响有关，都与时间有关。称为与时间有关的错误。称为与时间有关的错误。 进程的定义：进程是进程实体的运行过程，是系统进行进程的定义：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。资源分配和调度的一个独立单位。简述进程和程序的区别和联系简述进程和程序的区别和联系 (1)每个进程实体中包含了程序段和数据段，还包含了一

12、个数每个进程实体中包含了程序段和数据段，还包含了一个数据结构据结构PCB(2)进程是程序的一次执行过程，是动态的，是有生命周期的。进程是程序的一次执行过程，是动态的，是有生命周期的。程序是静态的，是可以长期保存的。程序是静态的，是可以长期保存的。(3)多个进程实体可同时存放在内存中并发执行。多个进程实体可同时存放在内存中并发执行。(4)进程是一个能够独立运行、独立分配资和独立接受调度的进程是一个能够独立运行、独立分配资和独立接受调度的基本单位。基本单位。(5)进程和程序不是一一对应的。进程和程序不是一一对应的。1对多或对多或1对对1,通过多次执行，通过多次执行，一个程序可对应多个进程，通过调用

13、关系，一个进程可包一个程序可对应多个进程，通过调用关系，一个进程可包括多个括多个 程序。程序。 系统内的进程能并发执行，允许并发执行的系统内的进程能并发执行，允许并发执行的理由：信息共享，加快计算，模块化和方便性。理由：信息共享，加快计算，模块化和方便性。(2)进程的三种基本状态：进程的三种基本状态： 就绪状态：三种情况的进程就绪状态：三种情况的进程 执行状态：当前进程执行状态：当前进程 阻塞状态：等待状态、封锁状态、睡眠状态。阻塞状态：等待状态、封锁状态、睡眠状态。三种基本状态之间的转换：三种基本状态之间的转换：两个基本队列：就绪队列和等待队列。入队和出队。两个基本队列：就绪队列和等待队列。

14、入队和出队。(3)挂起状态：终端用户的请求，父进程请求，负荷挂起状态：终端用户的请求，父进程请求，负荷调节的需要，操作系统的需要。调节的需要，操作系统的需要。进程状态的转换：进程状态的转换：(4)创建状态和终止状态：创建状态和终止状态： 例例1：简述三种基本状态之间的转换方向及原因：简述三种基本状态之间的转换方向及原因：绝对不会出现的是从阻塞到执行状态的转换。绝对不会出现的是从阻塞到执行状态的转换。进程队列：就绪队列和等待队列。入队和出队。进程队列：就绪队列和等待队列。入队和出队。例例2：处于就绪队列中的进程是由哪三种类型的进：处于就绪队列中的进程是由哪三种类型的进程组成的程组成的解：解：（1

15、）新进程）新进程（2）因时间片用完而中断运行的进程）因时间片用完而中断运行的进程（3）因等待的条件发生而被唤醒的进程）因等待的条件发生而被唤醒的进程例例3：在一个只有单处理机的操作系统中，进程有运行、就绪、：在一个只有单处理机的操作系统中，进程有运行、就绪、等待三个基本状态。假如某时刻操作系统中有等待三个基本状态。假如某时刻操作系统中有10个进程并个进程并发执行，且发执行，且CPU以非核心态情况下，试问：以非核心态情况下，试问：（1）这时刻系统中处于运行状态的进程数最多有几个？最少）这时刻系统中处于运行状态的进程数最多有几个？最少有几个？有几个？（2）这时刻系统中处于就绪状态的进程数最多有几个

16、？最少）这时刻系统中处于就绪状态的进程数最多有几个？最少有几个？有几个？（3）这时刻系统中处于等待状态的进程数最多有几个？最少）这时刻系统中处于等待状态的进程数最多有几个？最少有几个？有几个？解：解：（1）因为系统中只有一个处理机，所以某时刻处于运行状态）因为系统中只有一个处理机，所以某时刻处于运行状态的进程数最多有的进程数最多有1个。而最少可能为个。而最少可能为0，此时其他，此时其他10个进程个进程一定全部排在各等待队列中，在就绪队列中没有进程，在一定全部排在各等待队列中，在就绪队列中没有进程，在实际的操作系统中，此时实际的操作系统中，此时CPU是在运行操作系统的空闲进是在运行操作系统的空闲

17、进程（程（System Idle Process）或线程。）或线程。（2）处于就绪状态的进程数最多只有）处于就绪状态的进程数最多只有9个，不可能个，不可能出现出现10个，因为一旦个，因为一旦CPU有空，调度程序马上调有空，调度程序马上调度；处于就绪状态的进程数最少是度；处于就绪状态的进程数最少是0个，个，1个进程个进程运行，运行，9个进程等待，或者个进程等待，或者10个进程全部等待。个进程全部等待。（3）处于等待状态的进程数最多有）处于等待状态的进程数最多有10个，等待状个，等待状态的进程最少是个。态的进程最少是个。例例3：某系统在：某系统在t0时刻，打印机刚刚打印完毕或者刚时刻，打印机刚刚打

18、印完毕或者刚刚开始打印，试问该时刻系统内部发生了进程状刚开始打印，试问该时刻系统内部发生了进程状态变化的情况如何？态变化的情况如何？2.1.5 进程控制块：任务控制块进程控制块：任务控制块1、PCB的作用：进程存在的惟一标志。的作用：进程存在的惟一标志。是使一个在多道是使一个在多道程序环境下不能独立运行的程序，成为一个能独程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，一个能与其他进程并发执行立运行的基本单位，一个能与其他进程并发执行的进程。是进程存在的惟一标志。操作系统是根的进程。是进程存在的惟一标志。操作系统是根据据PCB来对并发执行的进程进行控制和管理的。来对并发执行的进程进

19、行控制和管理的。 2、PCB中的信息中的信息 (1)进程标识符：内部和外部标识进程标识符：内部和外部标识 (2)处理机状态：通用寄存器、处理机状态：通用寄存器、PC、PSW和用户栈指针。和用户栈指针。 (3)进程调度信息：进程状态、进程优先级、调度的其他信进程调度信息：进程状态、进程优先级、调度的其他信息、阻塞事件。息、阻塞事件。 (4)进程控制信息：程序和数据的地址、同步和通信机制、进程控制信息：程序和数据的地址、同步和通信机制、资源清单和链接指针。资源清单和链接指针。3、PCB的组织方式：链接和索引。的组织方式：链接和索引。进程上下文（进程上下文（Context）实际上是进程执行活动全过程

20、的静）实际上是进程执行活动全过程的静态描述。又称进程映像。包括三个组成部分：态描述。又称进程映像。包括三个组成部分：（1）用户级上下文。由用户程序代码、用户数据段（含共）用户级上下文。由用户程序代码、用户数据段（含共享数据块）和用户堆栈组成的进程地址空间。享数据块）和用户堆栈组成的进程地址空间。（2）系统级上下文。包括进程的标识信息、现场信息、控）系统级上下文。包括进程的标识信息、现场信息、控制信息、进程环境块，以及系统堆栈等组成的进程地址空制信息、进程环境块，以及系统堆栈等组成的进程地址空间。间。（3）寄存器上下文。由程序状态字寄存器和各类控制寄存）寄存器上下文。由程序状态字寄存器和各类控制

21、寄存器、地址寄存器、通用寄存器组成。器、地址寄存器、通用寄存器组成。Context switch发生在寄存器和内存之间，依赖于内存速度，发生在寄存器和内存之间，依赖于内存速度，复制的寄存器的数量，是否有特殊指令等。复制的寄存器的数量，是否有特殊指令等。 可再入程序是指一个能被多个用户同时调用的程可再入程序是指一个能被多个用户同时调用的程序：必须是纯代码，要求调用者提供工作区。序：必须是纯代码，要求调用者提供工作区。 中断及中断响应中断及中断响应 中断是指中断是指CPU对系统中发生的异步事件的响应或对系统中发生的异步事件的响应或处理，异步事件是指无一定时序关系而随机发生处理，异步事件是指无一定时

22、序关系而随机发生的事件。的事件。 中断的作用：充分发挥处理机的使用效率；提高中断的作用：充分发挥处理机的使用效率；提高系统的实时处理的能力。系统的实时处理的能力。 中断的功能：发现中断源，提出中断请求；保护中断的功能：发现中断源，提出中断请求；保护现场；启动并运行处理中断事件的体育场。现场；启动并运行处理中断事件的体育场。 中断优先级是按中断事件的重要性和紧迫中断优先级是按中断事件的重要性和紧迫程序来确定的，是由硬件设计时固定下来程序来确定的，是由硬件设计时固定下来的。依次：的。依次：硬件故障中断、自愿中断、程硬件故障中断、自愿中断、程序性中断、外部中断和输入序性中断、外部中断和输入/输出中断

23、输出中断。 中断屏蔽：中断处理程序只能屏蔽比自己中断屏蔽：中断处理程序只能屏蔽比自己优先级低的事件，并且不能屏蔽自愿中断。优先级低的事件，并且不能屏蔽自愿中断。2.2 进程控制进程控制原语操作的定义：原语操作的定义：2.2.1 进程的创建进程的创建(1)进程图：描述一个进程的家庭关系的有向图。进程图：描述一个进程的家庭关系的有向图。(2)引起创建进程的事件：用户登录，作业调度，提引起创建进程的事件：用户登录，作业调度，提供服务和应用请求。供服务和应用请求。(3)进程的创建：申请空白进程的创建：申请空白PCB，为新进程分配资源，为新进程分配资源，初始化初始化PCB，将新进程插入就绪队列。，将新进

24、程插入就绪队列。(4)进程的创建请求系统为一个程序分配一个工作区进程的创建请求系统为一个程序分配一个工作区和建立一个进程控制块和建立一个进程控制块 当进程创建新进程时，有两种执行可能：当进程创建新进程时，有两种执行可能：（1）父进程与子进程并发执行）父进程与子进程并发执行（2）父进程等待，直到某个或全部子进程执）父进程等待，直到某个或全部子进程执行完。行完。 新进程的地址空间也有两种可能新进程的地址空间也有两种可能（1）子进程是父进程的复制品（具有与父进）子进程是父进程的复制品（具有与父进程相同的程序和数据）程相同的程序和数据）（2）子进程装入另一个新程序）子进程装入另一个新程序2.2.2 进

25、程的终止进程的终止(1)引起进程终止的事件：正常结束，异常结引起进程终止的事件：正常结束，异常结束和外界干预。束和外界干预。(2)进程的终止过程：检索进程的终止过程：检索PCB，判断状态，判断状态，撤销子进程，归还资源，清空撤销子进程，归还资源，清空PCB。(3)进程的撤消，系统收回该进程所用的工作进程的撤消，系统收回该进程所用的工作区，取消进程控制块。区，取消进程控制块。Exit()、TerminatePorcess() 父进程终止其子进程的原因父进程终止其子进程的原因（1）子进程使用了超过它所分配到的一些资）子进程使用了超过它所分配到的一些资源源（2）分配给子进程的任务已不再需要）分配给子

26、进程的任务已不再需要（3）父进程退出，如果父进程终止，操作系）父进程退出，如果父进程终止，操作系统不允许子进程继续。级联终止统不允许子进程继续。级联终止Cascading termination。VMS。2.2.3 进程的阻塞与唤醒进程的阻塞与唤醒(1)引起进程阻塞和唤醒的事件：请求系统服务，启引起进程阻塞和唤醒的事件：请求系统服务，启动某种操作，新数据尚未到达和无新工作可做。动某种操作，新数据尚未到达和无新工作可做。(2)进程阻塞过程：进程阻塞过程：(3)进程唤醒过程：进程唤醒过程：2.2.4 进程的挂起与激活进程的挂起与激活(1)进程的挂起进程的挂起(2)进程的激活过程进程的激活过程2.3

27、 进程同步与互斥进程同步与互斥2.3.1 进程同步的基本概念进程同步的基本概念并发进程间的关系可以是无关的，也可以是有交往的并发进程间的关系可以是无关的，也可以是有交往的。独立进程或协作进程。独立进程或协作进程。 1、两种制约关系：、两种制约关系： 间接制约关系：互斥间接制约关系：互斥 进程互斥是指当有若干个进程使用某一共享资源时，进程互斥是指当有若干个进程使用某一共享资源时，任何时刻最多只允许一个进程使用，而其他要使用任何时刻最多只允许一个进程使用，而其他要使用该资源的进程必须等待，直到占用资源者释放该资该资源的进程必须等待，直到占用资源者释放该资源。是进程间竞争共享资源的使用权，没有固定的

28、源。是进程间竞争共享资源的使用权，没有固定的必然关系。利用公用信号量必然关系。利用公用信号量 直接制约关系：同步直接制约关系：同步 进程同步是指并发进程之间存在一种制约进程同步是指并发进程之间存在一种制约关系，一个进程的执行依赖另一个进程的关系，一个进程的执行依赖另一个进程的消息，当一个进程没有得到另一个进程的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息到达才被唤醒。消息时应等待，直到消息到达才被唤醒。涉及共享资源的并发进程之间有一种必然涉及共享资源的并发进程之间有一种必然的依赖关系。利用私用信号量。的依赖关系。利用私用信号量。 同步与互斥的混合问题：进程的互斥是进程同步与互斥的

29、混合问题：进程的互斥是进程间竞争共享资源的使用权，这种竞争没有固定的间竞争共享资源的使用权，这种竞争没有固定的必然关系；进程同步，涉及共享资源的并发进程必然关系；进程同步，涉及共享资源的并发进程之间有一种必然的依赖关系。之间有一种必然的依赖关系。 race condition竞争条件：多个内核进程同时竞争条件：多个内核进程同时活动，会发生竞争条件。如打开文件的内核数据活动，会发生竞争条件。如打开文件的内核数据结构，内存分配的数据结构，维护进程列表及处结构，内存分配的数据结构，维护进程列表及处理中断处理程序的数据结构。理中断处理程序的数据结构。 非抢占内核式的系统中不会导致竞争非抢占内核式的系统

30、中不会导致竞争条件，抢占内核的系统可能会导致竞争条条件，抢占内核的系统可能会导致竞争条件。抢占内核比非抢占内核更受欢迎。件。抢占内核比非抢占内核更受欢迎。Windows XP和和Windows 2000为非抢占式为非抢占式内核，传统的内核，传统的Unix和和Linux 2.6以前的内核以前的内核也是非抢占式的。也是非抢占式的。Linux 2.6以后，商用以后，商用Unix、Solaris是抢占内核是抢占内核2、临界资源：一次只允许一个进程使用的资源。打、临界资源：一次只允许一个进程使用的资源。打印机、磁带机、消息缓冲队列、变量、数组、缓冲印机、磁带机、消息缓冲队列、变量、数组、缓冲区等。又称独

31、享资源。区等。又称独享资源。 3、临界区：实现互斥的方法：软件和硬件方法、临界区：实现互斥的方法：软件和硬件方法4、同步机制的规则：空闲让进，忙则等待，有限等、同步机制的规则：空闲让进，忙则等待，有限等待和让权等待。（在单处理机系统中是必须的，在待和让权等待。（在单处理机系统中是必须的，在多处理机系统中不是必须的）多处理机系统中不是必须的） 实现同步的几种方法实现同步的几种方法1、禁止中断：只适合单处理器环境，会出现饿死。、禁止中断：只适合单处理器环境，会出现饿死。2、TestAndSet指令：不可分的原子操作指令：不可分的原子操作,可适用于可适用于多处理器环境。多处理器环境。Boolean

32、TestAndSet(boolean locked) if(locked) return true; else locked=true; return false; 3、Swap指令指令 boolean void Swap(boolean a,boolean b) boolean temp; temp=b; b=a; a=temp; 4、Dekker算法和算法和Peterson算法：基于软件算法：基于软件的两个进程间的通信。的两个进程间的通信。 Bakery算法，用于算法，用于N个进程间的通信个进程间的通信2.3.2 信号量机制信号量机制 1、整型信号量：、整型信号量：P、V操作操作 wait

33、(s):while s=0 do nothing; s=s-1;信号量的值不可能取负值。信号量的值不可能取负值。 signal(s):s=s+1; 又称简单信号量，二元信号量，二进制信号量，互又称简单信号量，二元信号量，二进制信号量，互斥锁。斥锁。缺点：忙等待方式缺点：忙等待方式busy waiting,自旋锁（优点：不自旋锁（优点：不进行上下文切换，常用于多处理系统）进行上下文切换，常用于多处理系统）2、记录型信号量：、记录型信号量： struct semaphore int:value; struct process *L; s; wait(s): s.value=s.value-1; i

34、f s.value0 then block(s.L); 信号量的递减和测试次序的互换，其值可取负值。信号量的递减和测试次序的互换，其值可取负值。 signal(s):s.value=s.value+1; if s.value=0 then wakeup(s.L);又称计数信号量，资源信号量，用来控制又称计数信号量，资源信号量，用来控制m个进程访问某一个进程访问某一类类n个临界资源。个临界资源。例例1记录型信号量的物理含义：记录型信号量的物理含义：例例2：设有：设有n个进程共享一个程序段，对于如个进程共享一个程序段，对于如下两种情况：下两种情况：（1）如果每次只允许一个进程进入该程序段。）如果每

35、次只允许一个进程进入该程序段。（2）如果每次最多允许）如果每次最多允许m个进程（个进程（m0)个单元的缓冲区。个单元的缓冲区。P1每次用每次用produce()生成一个正整数并用生成一个正整数并用put()送入缓送入缓冲区某一空单元中；冲区某一空单元中；P2每次用每次用getodd()从从该缓冲区中取出一个奇数并用该缓冲区中取出一个奇数并用countodd()统计奇数个数；统计奇数个数；P3每次用每次用geteven()从该缓从该缓冲区中取出一个偶数并冲区中取出一个偶数并counteven()统计偶统计偶数个数。请用信号量机制实现这三个进程数个数。请用信号量机制实现这三个进程的同步与互斥活动，

36、并说明所定义信号量的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。的含义。要求用伪代码描述。 答案：定义信号量答案：定义信号量S1控制控制P1与与P2之间的同步；之间的同步；S2控制控制P1与与P3之间的同步；之间的同步；empty控制生产者与消费者之间的同步；控制生产者与消费者之间的同步；mutex控制进程间互斥使用缓冲区。控制进程间互斥使用缓冲区。程序如下：程序如下： Var s1=0,s2=0,empty=N,mutex=1; Parbegin P1:begin X=produce(); /*生成一个数生成一个数*/ P(empty);/*判断缓冲区是否有空单元判断缓冲区是

37、否有空单元*/ P(mutex); /*缓冲区是否被占用缓冲区是否被占用*/ put(x); If x%2=0 V(s2); /*如果是偶数，向如果是偶数，向P3发出信号发出信号*/ else V(s1); /*如果是奇数，向如果是奇数，向P2发出信号发出信号*/ V(mutex); /*使用完缓冲区，释放使用完缓冲区，释放*/ P2：begin P(s1); /*收到收到P1发来的信号，已产生一个奇数发来的信号，已产生一个奇数*/ P(mutex); /*缓冲区是否被占用缓冲区是否被占用*/ Getodd(); Countodd():=coutodd()+1; V(mutex); /*释放缓

38、冲区释放缓冲区*/ V(empty); /*向向P1发信号，多出一个空单元发信号，多出一个空单元*/ End. P3:begin P(s2); /*收到收到P1发来的信号，已产生一个偶数发来的信号，已产生一个偶数*/ P(mutex); /*缓冲区是否被占用缓冲区是否被占用*/ Geteven(); Counteven():=counteven()+1; V(mutex); /* 释放缓冲区释放缓冲区*/ V(empty); /*向向P1发信号，多出一个空单元发信号，多出一个空单元*/End.Parend.2.4.2 读者和写者问题：一直用来测试几乎所有新读者和写者问题：一直用来测试几乎所有新

39、的同步原语。多个用户共享数据库系统的建模问的同步原语。多个用户共享数据库系统的建模问题。有多种不同的策略，都与优先级有关。题。有多种不同的策略，都与优先级有关。 1、读者优先：第一读者、读者优先：第一读者-写者问题，写者可能饥饿。写者问题，写者可能饥饿。 2、排队策略或先来先服务、排队策略或先来先服务 3、写者优先：第二读者、写者优先：第二读者-写者问题，读者可能饥饿。写者问题，读者可能饥饿。 4、某个进程即是写者又是读者的问题、某个进程即是写者又是读者的问题例：设有例：设有P1,P2,P3三个进程共享某一资源三个进程共享某一资源F，P1对对F只读不写，只读不写，P2对对F只写不读，只写不读，

40、P3对对F先读后写。当一个进程写先读后写。当一个进程写F时，其他进程对时，其他进程对F不能进行读写，但多个进程同时读不能进行读写，但多个进程同时读F是允是允许的。试用许的。试用P、V操作正确实现操作正确实现P1,P2,P3的的同步互斥。要求：同步互斥。要求：（1）正常运行时不产生死锁）正常运行时不产生死锁（2）使用）使用F的并发度要高。（北京大学的并发度要高。（北京大学1996年研究生试题）年研究生试题） 解：本题实际上是一个读者和写者问题，解：本题实际上是一个读者和写者问题，P1是一个读者，是一个读者，P2是一个写者，为了使是一个写者，为了使F的并的并发度较高，将发度较高，将P3先看成读者，

41、当其完成读先看成读者，当其完成读操作后，再将其看成写者。操作后，再将其看成写者。 定义如下变量：定义如下变量： int readcount=0; semaphore rmutex=1,mutex=1; P1( ) While(1) P(rmutex); If(readcount=0)P(mutex); Readcount+; V(rmutex); 读读F； P（rmutex）; Readcount-; If(readcount=0)V(mutex); V(rmutex);P2() While(1) P(mutex); 写写F； V（mutex）;P3() While(1) P(rmtex);

42、If(readcount=0)P(mutex); Readcount+; V(rmutex); 读读F； P（rmutex）; Readcount-; If(readcount=0)V（mutex）; V(rmutex); P(mutex); 写写F； V（mutex）; 2.4.3 哲学家进餐问题：是一个并发控制问题，在多哲学家进餐问题：是一个并发控制问题，在多个进程之间分配多个资源且不会出现死锁和饥饿的个进程之间分配多个资源且不会出现死锁和饥饿的问题。问题。方法：方法： 1、同时允许四个哲学家提出进餐要求、同时允许四个哲学家提出进餐要求 2、同时去拿起两边的筷子、同时去拿起两边的筷子 3、

43、使用非对称解决方法，奇数号哲学家先拿左边、使用非对称解决方法，奇数号哲学家先拿左边的筷子，偶数号哲学家先拿右边的筷子的筷子，偶数号哲学家先拿右边的筷子注意：没有死锁的解决方案并不能消除饿死的可能性。注意：没有死锁的解决方案并不能消除饿死的可能性。2.4.4 理发师嗜睡问题理发师嗜睡问题 一个理发店由一个有一个理发店由一个有N张椅子的等候室和一张椅子的等候室和一个放有一张理发椅的理发室组成。若没有要理发个放有一张理发椅的理发室组成。若没有要理发的顾客，则理发师就去睡觉，若一个顾客走进理的顾客，则理发师就去睡觉，若一个顾客走进理发店且所有的椅子都被占用了，则该顾客就离开发店且所有的椅子都被占用了，

44、则该顾客就离开理发店，若理发师正在为人理发，则该顾客就找理发店，若理发师正在为人理发，则该顾客就找一张空椅子坐下等待，若理发师在睡觉，则顾客一张空椅子坐下等待，若理发师在睡觉，则顾客就唤醒他。就唤醒他。 试用信号量设计一个协调理发师和顾客的程序。试用信号量设计一个协调理发师和顾客的程序。（西安电子科技大学（西安电子科技大学2000年研究生试题）年研究生试题） 解：本题中，顾客进程和理发师进程之间存在着多解：本题中，顾客进程和理发师进程之间存在着多种同步关系：种同步关系：（1）只有在理发椅空闲时，顾客才能坐到理发椅）只有在理发椅空闲时，顾客才能坐到理发椅上等待理发师理发，否则顾客便必须等待；只有

45、上等待理发师理发，否则顾客便必须等待；只有当理发椅上有顾客时，理发师才可以开始理发，当理发椅上有顾客时，理发师才可以开始理发，否则他也必须等待。这种同步关系类似于单缓冲否则他也必须等待。这种同步关系类似于单缓冲（理发椅）的生产者和消费者问题中的同步关系，（理发椅）的生产者和消费者问题中的同步关系，故可以通过信号量故可以通过信号量empty(初值为初值为1)和和full(初值为初值为0)来控制。来控制。（2）理发师为顾客理发时，顾客必须等待理发的）理发师为顾客理发时，顾客必须等待理发的完成，并在理发完成后由理发师唤醒他，这可单完成，并在理发完成后由理发师唤醒他，这可单独使用一个信号量独使用一个信

46、号量cut来控制，初值为来控制，初值为0。 （3）顾客理完发后必须向理发师付费，并等理发师收费后）顾客理完发后必须向理发师付费，并等理发师收费后顾客才能离开；而理发师则需等待顾客付费，并在收费后顾客才能离开；而理发师则需等待顾客付费，并在收费后唤醒顾客以允许他离开，这可分别通过两个信号量唤醒顾客以允许他离开，这可分别通过两个信号量payment和和receipt来控制，初值都为来控制，初值都为0。（4）等候室中的）等候室中的N张沙发是顾客进程竞争的资源，故还需为张沙发是顾客进程竞争的资源，故还需为它们设置了一个资源信号量它们设置了一个资源信号量sofa，初值为，初值为n（5）为了控制顾客的人数

47、，使顾客能在所有的沙发都被占）为了控制顾客的人数，使顾客能在所有的沙发都被占用时离开理发店，还必须设置一个整型变量用时离开理发店，还必须设置一个整型变量count来对理来对理发店中的顾客进行计数，该变量将被多个顾客进程互斥地发店中的顾客进行计数，该变量将被多个顾客进程互斥地访问并修改，这可通过一个互斥信号量访问并修改，这可通过一个互斥信号量mutex来实现，初来实现，初值为值为1Guestbegin wait(mutex); if(countN)then begin signal(muetx); 离开理发店; end else begin count=count+1; if(count1) t

48、hen begin wait(sofa); 在沙发中就座在沙发中就座; wait(empty); 从沙发上起来从沙发上起来; signal(sofa); end else /*count=1*/ wait(empty); 在理发椅上就座在理发椅上就座; signal(full); wait(cut); 理发；理发； 付费；付费； signal(payment); wait(receipt); 从理发椅上起来从理发椅上起来; signal(empty); wait(mutex); count=count-1; signal(mutex); 离开理发店离开理发店; end endbarber:be

49、gin repeat wait(full); 替顾客理发替顾客理发; signal(cut); wait(payment); 收费收费; signal(receipt); until false; endparendend 2.4.5 “吸烟者吸烟者”问题。假设一个系统有问题。假设一个系统有3个吸烟者个吸烟者（smoker）进程和一个供货商（）进程和一个供货商（Agent）进程。）进程。每个吸烟者连续不断地制造香烟并吸掉它。每个吸烟者连续不断地制造香烟并吸掉它。 但是，制造一支香烟需要但是，制造一支香烟需要3种材料种材料烟、纸、烟、纸、火柴。一个吸烟者进程有纸，另一个有烟，第三个火柴。一个吸烟

50、者进程有纸，另一个有烟，第三个有火柴。供货商进程可以无限地提供这有火柴。供货商进程可以无限地提供这3种材料。种材料。供货商将这这两种材料一起放在桌上，持有另一种供货商将这这两种材料一起放在桌上，持有另一种材料的吸烟者即可制造一支香烟并吸掉它。当此吸材料的吸烟者即可制造一支香烟并吸掉它。当此吸烟者抽香烟时，它发出一个信号通知供货商进程，烟者抽香烟时，它发出一个信号通知供货商进程，供货商马上给出另外两种材料，如此循环往复。试供货商马上给出另外两种材料，如此循环往复。试编写一个程序使供货商和吸烟者同步执行。编写一个程序使供货商和吸烟者同步执行。解法：解法：semaphore smoker30; 三个

51、吸烟者三个吸烟者semaphore material30; 三种原料三种原料semaphore agent1; 供应商供应商int turn=0;轮到谁轮到谁Main()CobeginAgent While(1) P(agent); 放原料；放原料； V(smokerturn); V(material(turn+1)%3); V(material(turn+2)%3); turn=(turn+1)%3Smoker_i While(1) P(smokeri); P(material(i+1)%3); P(material(i+2)%3); 制作香烟；制作香烟； 吸烟；吸烟； V(agent);

52、coend;参考算法参考算法供应者供应者seller随即产生两样东西，提供它们，这里用普通变量随即产生两样东西，提供它们，这里用普通变量来表示来表示（1） 吸烟者进程吸烟者进程smoker根据其排号不同，拥有不同的一件东根据其排号不同，拥有不同的一件东西。假设西。假设1号吸烟者拥有烟草号吸烟者拥有烟草tobacco，2号吸烟者拥有纸号吸烟者拥有纸paper，3号吸烟者拥有火柴号吸烟者拥有火柴match。其他号码错误返回。其他号码错误返回。（2） 吸烟者的序号代表他们拥有的东西，用他们的序号和供吸烟者的序号代表他们拥有的东西，用他们的序号和供应者产生的两样东西比较，如果都不相等，则说明他拥有的应

53、者产生的两样东西比较，如果都不相等，则说明他拥有的东西和供应者产生的东西匹配，它可以吸烟。如果其中一个东西和供应者产生的东西匹配，它可以吸烟。如果其中一个相等，则推出，继续排队。相等，则推出，继续排队。（3） mutex信号量代表一个只能进入的门，每次只有一个吸信号量代表一个只能进入的门，每次只有一个吸烟者可以进入进行比较和吸烟。烟者可以进入进行比较和吸烟。（4） 每个吸烟者在吸烟完毕之后出门之前要叫醒供应者，调每个吸烟者在吸烟完毕之后出门之前要叫醒供应者，调用用seller进程。进程。vars , S1 ,S2 , S3 ; semaphore ;S:=1 ; S1:=S2:=S3:=0 ;

54、fiag1 , flag2 , fiag3 : Boolean ;fiag1:=flag2:=flag3:=true;cobeginprocess 供应者供应者beginrepeatP(S) ;取两样香烟原料放桌上，由取两样香烟原料放桌上，由flagi标记；标记；/nago1 、nage2 、nage3 代表烟草、纸、火柴代表烟草、纸、火柴if flag2 & flag3 then V(S1) ; /供纸和火柴供纸和火柴else if flag1 & fiag3 then V(S2); /供烟草和火柴供烟草和火柴else V(S3) ; /供烟草和纸供烟草和纸untile false ;end

55、process 吸烟者吸烟者1beginrepeatP(S1) ;取原料；取原料；做香烟；做香烟；V(S) ;吸香烟；吸香烟；untile false ;endprocess 吸烟者吸烟者2beginrepeatp(S2);取原料；取原料；做香烟；做香烟；V(S) ;吸香烟；吸香烟；untile false ;endprocess 吸烟者吸烟者3beginrepeatP(S3);取原料；取原料；做香烟；做香烟；V(S);吸香烟；吸香烟；untile false ;endcoend变型变型1抽烟问题：有一个烟草代理和三个抽烟者。抽烟问题：有一个烟草代理和三个抽烟者。抽烟者若要抽烟，必须具有烟叶、

56、烟纸和抽烟者若要抽烟，必须具有烟叶、烟纸和火柴。三个抽烟者中，一人缺烟叶、一人火柴。三个抽烟者中，一人缺烟叶、一人缺烟纸、一人缺火柴。烟草代理会源源不缺烟纸、一人缺火柴。烟草代理会源源不断地分别供应烟叶、烟纸和火柴，并将它断地分别供应烟叶、烟纸和火柴，并将它们放在桌上。如果放的是烟叶，则缺烟叶们放在桌上。如果放的是烟叶，则缺烟叶的抽烟者拾起烟叶，制作香烟，然后抽烟；的抽烟者拾起烟叶，制作香烟，然后抽烟；其他类推。试用信号量同步烟草代理和三其他类推。试用信号量同步烟草代理和三个抽烟者。个抽烟者。解法：解法：semaphore smoker30; 三个吸烟者三个吸烟者semaphore mater

57、ial30; 三种原料三种原料semaphore agent1; 供应商供应商int turn=0;轮到谁轮到谁Agent While(1) P(agent); 放原料；放原料； V(smokerturn); V(material(turn+1)%3); 制作香烟；制作香烟； 吸烟；吸烟； turn=(turn+1)%3Smoker_i While(1) P(smokeri); P(material(i+1)%3); 制作香烟；制作香烟； 吸烟；吸烟； V(agent); 变型变型2有一间酒吧里有有一间酒吧里有3个音乐爱好者队列，第个音乐爱好者队列，第1队的音乐队的音乐爱好者只有随身听，第爱好

58、者只有随身听，第2队只有音乐磁带，第队只有音乐磁带，第3队队只有电池。而要听音乐就必须随身听、音乐磁带只有电池。而要听音乐就必须随身听、音乐磁带和电池这和电池这3种物品俱全。酒吧老板一次出售这种物品俱全。酒吧老板一次出售这3种种物品中的任意两种。当一名音乐爱好者得到这物品中的任意两种。当一名音乐爱好者得到这3种物品并听完一首乐曲后，酒吧老板才能再一次种物品并听完一首乐曲后，酒吧老板才能再一次出售这出售这3种物品中的任意两种，于是第种物品中的任意两种，于是第2名音乐爱名音乐爱好者得到这好者得到这3种物品，并开始听乐曲。全部买卖种物品，并开始听乐曲。全部买卖就这样进行下去。就这样进行下去。试用试用

59、P、V操作正确解决这一买卖。（北京大学操作正确解决这一买卖。（北京大学1999年研究生试题）年研究生试题）变型变型3（桔子汁生产线问题）现有三个生产者（桔子汁生产线问题）现有三个生产者P1 、P2 、P3 ，他们都要生产水，每个生产者都已分别购得，他们都要生产水，每个生产者都已分别购得两种不同原料，待购得第三种原料后就可配制成两种不同原料，待购得第三种原料后就可配制成桔子水，装瓶出售。有一供应商能源源不断地供桔子水，装瓶出售。有一供应商能源源不断地供应糖、水、桔子精，但每次只拿出一种原料放入应糖、水、桔子精，但每次只拿出一种原料放入容器中供给生产者。当容器中有原料时需要该原容器中供给生产者。当

60、容器中有原料时需要该原料的生产者可取走，当容器空时供应商又可放入料的生产者可取走，当容器空时供应商又可放入一种原料。假定：生产者一种原料。假定：生产者P1已购得糖和水；生产已购得糖和水；生产者者P2 已购得水和桔子精；生产者已购得水和桔子精；生产者P3 已购得糖和已购得糖和桔子精；试用：信号量与桔子精；试用：信号量与P 、v 操作，写出供应操作，写出供应商和三个生产者之间能正确同步的程序商和三个生产者之间能正确同步的程序 2.4.6 银行排队问题银行排队问题(北京大学北京大学2000）银行有）银行有n个柜个柜员员,每个顾客进入银行后先取一个号每个顾客进入银行后先取一个号,并且等着叫并且等着叫号