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

1、计算机操作系统第二章 进程管理（进程同步与互斥）2009年1个选择、1个综合应用题2010年3个选择2011年2个选择，1个综合应用题2012年2个选择2013年2个选择,1个同步算法设计题 进程管理是本课程的重点章节，这部分介绍的是操作系统5大管理功能之一：处理机管理，包括进程管理和处理机调度两大块的内容。本章是学习和考试的重点内容，同时也是难点。这部分除了要掌握基本的概念和基本的原理外，还要求能运用这些基本原理去分析和解决问题。 进程同步与互斥是进程管理的重点，也是操作系统学科的一个难点。 具体包括:进程同步的基本概念、实现临界区互斥的基本方法(包括软件实现方法、硬件实现方法)、信号量(P

2、、V操作)、管程、经典同步问题(包括生产者-消费者问题、读者-写者问题、哲学家进餐问题等)。我们一定要掌握P、V操作的概念、流程，以及P、V操作在同步问题、互斥问题中的应用。 首先,要求掌握进程的概念，其中进程和程序这两个概念的区别和联系一定要搞清楚。第二,要记住进程的三个基本状态以及它们之间相互转换条件，一定要记住不可能从就绪状态直接转换到等待状态。第三,需要理解进程控制和原语这两个概念，掌握进程的创建、撤销、阻塞、唤醒的条件，理解四种原语的执行过程。第四,理解什么是并发进程间的直接制约以及由直接制约所引发的进程同步，重点要掌握如何用P、V原语操作实现同步问题，要会利用P、V原语操作来解决经

3、典的同步问题；第五,了解进程的通信方式及它们各自的特点；第六,要理解进程和线程的异同以及多线程模型；第二章 进程管理2.1 进程的基本概念2.2 进程控制2.3 进程同步2.4 经典进程的同步问题2.5 进程通信2.6 线程基础知识总结实战练习综合应用题操作系统在管理进程与线程的过程中需要完成以下工作：（1）用户和系统进程的创建和删除；（2）进程的调度；（3）为进程的同步、通信、死锁处理提供机制。多道程序设计的提出 其基本思想是在主存中同时存放多个用户的作业，使之同时处于运行状态而共享系统资源。宏观上是并行运行，微观上是依次轮流迸发运行的。操作系统的定义：操作系统是指控制和管理计算机的软、硬件

4、资源，合理地组织计算机的工作流程，为程序的运行提供一个良好环境，方便用户使用的程序集合。之所以采用多道程序设计技术，是由于中断和通道技术的出现，CPU可以把直接控制输入/输出的工作转给通道。多道程序的目标、方法和主要问题（1）目标：是充分使用系统所有资源并尽可能地使它们并行工作，这种技术可把硬件的代价交叉分布在大量并行用户之间，而使计算机系统的代价极小化。（2）方法：是一个正在运行的程序不使用某设备时，让另一程序去使用该设备。为了发挥多道程序设计的有效性，应选择各种不同类型的作业同时执行，让资源处于忙碌状态。（3）多道程序设计实现的3个问题：存储保护、程序浮动、处理机和系统资源的管理和调度。

5、多道程序系统所必须解决的问题（1）提出解决各种冲突的策略（2）协调并发活动的关系（3）保证数据的一致性（4）实现数据的存取控制2.1 进程的基本概念2.1.1 程序的顺序执行及其特征：顺序性、封闭性、可再现性。作业1：什么叫程序顺序执行的封闭性和可再现性？封闭性：程序执行得到的最终结果由给定的初始条件决定，不受外界因素的影响。可再现性：只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果。2.1.2 前趋图：有向无循环图，DAG（Directed Acyclic Graph），描述进程之间执行的前后关系。直接制约关系：同步间接制约关系：互斥2.1.3 程序的并发执行及其特征：间断

6、性(制约性)、失去封闭性、不可再现性（不可重复，例：变量的共享）。2.1.4 进程的特征与状态 引入进程的目的：是使多个程序能并发执行，提高资源利用率和系统吞吐量。进程的定义进程的组成：进程包括程序代码（程序段或文本段）、堆栈段（临时数据，如函数参数、返回地址和局部变量）、数据段（包括全局变量）、堆（进行运行期间动态分配的内存）PCB：Process Control Block进程表空间：PT进程图： 内存中的进程如右图示：栈堆数据文本(1)特征： 动态性：最基本。 并发性： 独立性：独立运行、独立分配资源和独立接受调度。 异步性：进程以各自独立的，不可预先的速度向前推进。 可能会造成不正确的

7、情况出现，原因与进程占用处理器的时间、执行的速度以及外界的影响有关，都与时间有关。称为与时间有关的错误。又称竞争条件， Race Condition结构特征：程序段、相关的数据段和PCB构成的进程实体。定义：一个程序段在一个数据段上的一次执行过程。作业2：简述进程和程序的区别和联系 进程和程序是既有联系又有区别的两个概念（1）程序是指令的集合，静态概念，进程是程序在处理机上的一次执行过程，动态概念。（2）程序是长期存在的，进程有生命周期，有创建、活动、消亡。（3）程序仅是指令的有序集合，而进程则由程序、数据和进程控制块组成。（4）进程与程序之间不是一一对应的，即同一程序同时运行于若干不同的数据

8、集合上，它将属于若干个不同的进程，而一个进程可以执行多个程序。 系统内的进程能并发执行，允许并发执行的理由：信息共享，加快计算，模块化和方便性。(2)进程的三种基本状态： 就绪状态：三种情况的进程构成了就绪队列 执行状态：当前进程，至少一个 阻塞状态：等待状态、封锁状态、睡眠状态、休眠状态。作业3：画出三种基本状态之间的转换方向并标明每一种转换的原因：这个时候，需要进行重新调度，会发生进程上下文内容的切换。两个基本队列：就绪队列和等待队列。队列管理模块：入队和出队。中断处理过程（1）唤醒被阻塞的驱动程序进程。（2）保护被中断进程的CPU环境。程序是指令在N位置时被中断的，程序计数器中的内容为N

9、+1，所有寄存器的内容都被保留在中断保留区（栈）中。（3）分析中断原因、转入相应的设备中断处理程序。（4）进行中断处理。不同的设备有不同的中断处理程序。（5）恢复被中断进程的现场。处理机再执行本程序时，从N+1开始。恢复的内容：包括第N+1条指令的地址（IR寄存器或PC计数器）、处理机状态字PSW(标志寄存器)、通用寄存器和段寄存器的内容注：此处与第四章中的缺页中断和缺段中断相区别(3)挂起状态：终端用户的请求，父进程请求，负荷调节的需要，操作系统的需要。进程状态的转换：(4)创建状态和终止状态： 例1：简述三种基本状态之间的转换方向及原因：绝对不会出现的是从阻塞到执行状态的转换。进程队列：就

10、绪队列和等待队列。入队和出队。例2：处于就绪队列中的进程是由哪三种类型的进程组成的解：（1）新进程（2）因时间片用完而中断运行的进程（3）因等待的条件发生而被唤醒的进程例3：在一个只有单处理机的操作系统中，进程有运行、就绪、等待三个基本状态。假如某时刻操作系统中有10个进程并发执行，且CPU以非核心态情况下，试问：（1）这时刻系统中处于运行状态的进程数最多有几个？最少有几个？（2）这时刻系统中处于就绪状态的进程数最多有几个？最少有几个？（3）这时刻系统中处于等待状态的进程数最多有几个？最少有几个？解：（1）因为系统中只有一个处理机，所以某时刻处于运行状态的进程数最多有1个。而最少可能为0，此时

11、其他10个进程一定全部排在各等待队列中，在就绪队列中没有进程，在实际的操作系统中，此时CPU是在运行操作系统的空闲进程（System Idle Process）或线程。（2）处于就绪状态的进程数最多只有9个，不可能出现10个，因为一旦CPU有空，调度程序马上调度；处于就绪状态的进程数最少是0个，1个进程运行，9个进程等待，或者10个进程全部等待。（3）处于等待状态的进程数最多有10个，等待状态的进程最少是个。例3：某系统在t0时刻，打印机刚刚打印完毕或者刚刚开始打印，试问该时刻系统内部发生了进程状态变化的情况如何？2.1.5 进程控制块：任务控制块1、PCB的作用：将程序变成可并发执行的进程，

12、是进程存在的惟一标志。操作系统是根据PCB来对并发执行的进程进行控制和管理的。常驻内存。系统会集中存储所有进程的PCB，构成进程表空间PT。 2、PCB中的信息 (1)进程标识符：内部和外部标识 (2)处理机状态：通用寄存器、PC、PSW（标志寄存器）和用户栈指针。 (3)进程调度信息：进程状态、进程优先级、调度的其他信息、阻塞事件。 (4)进程控制信息：程序和数据的地址、同步和通信机制、资源清单和链接指针。3、PCB的组织方式：链接和索引。作业4：试从进程管理、中断处理、文件管理、存储管理、设备管理的角度设计进程控制块应包含的项目。（北京大学1999年研究生试题）解：1、从进程管理的角度考虑

13、，PCB应包含进程标识符、进程状态、CPU状态信息（包括程序计数器、程序状态字、栈指针、通用寄存器等）、进程调度信息（进程的优先数）、链接指针（用于将PCB链入各种队列）等项信息。2、从进程通信的角度考虑，PCB中应包含消息队列指针、实现消息队列互斥访问的互斥信号量、描述消息队列中消息个数的资源信号量。3、从中断处理的角度考虑，PCB中应包含CPU状态信息。4、从文件管理的角度考虑，PCB中应包含用户文件描述符表，用来登记用户打开的各个文件，并可以通过它找到在内存的相应文件的FCB5、从存储管理的角度考虑，应保存进程的程序、数据、堆栈在内存和外存的地址和各部分长度等信息。6、从设备管理角度考虑

14、，应有该进程所需资源和已分配到的资源清单。进程上下文（Context）实际上是进程执行活动全过程的静态描述。又称进程映像。包括三个组成部分：（1）用户级上下文。由用户程序代码、用户数据段（含共享数据块）和用户堆栈组成的进程地址空间。（2）系统级上下文。包括进程的标识信息、现场信息、控制信息、进程环境块，以及系统堆栈等组成的进程地址空间。（3）寄存器上下文。由程序状态字寄存器和各类控制寄存器、地址寄存器、通用寄存器组成。Context Switch发生在寄存器和内存之间，依赖于内存速度，复制的寄存器的数量，是否有特殊指令等。 可再入程序是指一个能被多个用户同时调用的程序：必须是纯代码，要求调用者

15、提供工作区。2.2 进程控制作业5：原语操作的定义：是指由若干条指令组成、用来实现某个特定操作的一个过程，其执行具有原子性，即原语在执行过程中不允许被中断，常驻内存，在核心态下运行。2.2.1 进程的创建：fork()、CreateProcess()(1)进程图：描述一个进程的家族关系的有向图。(2)引起创建进程的事件：用户登录，作业调度，提供服务和应用请求。(3)进程的创建：申请空白PCB，为新进程分配资源，初始化PCB，将新进程插入就绪队列。(4)进程的创建请求系统为一个程序分配一个工作区和建立一个进程控制块。2013.3.22 计算机当进程创建新进程时，有两种执行可能：（1）父进程与子进

16、程并发执行（2）父进程等待，直到某个或全部子进程执行完。新进程的地址空间也有两种可能（1）子进程是父进程的复制品（具有与父进程相同的程序和数据）（2）子进程装入另一个新程序2.2.2 进程的终止(1)引起进程终止的事件：正常结束，异常结束和外界干预。(2)进程的终止过程：检索PCB，判断状态，撤销子进程，归还资源，清空PCB。(3)进程的撤消，系统收回该进程所用的工作区，取消进程控制块。Exit()、TerminatePorcess()父进程终止其子进程的原因（1）子进程使用了超过它所分配到的一些资源（2）分配给子进程的任务已不再需要（3）父进程退出，如果父进程终止，操作系统不允许子进程继续。

17、级联终止Cascading termination。VMS。2.2.3 进程的阻塞与唤醒sleep()和wakeup()(1)引起进程阻塞和唤醒的事件：请求系统服务，启动某种操作，新数据尚未到达和无新工作可做。(2)进程阻塞过程：是正在执行的进程的一种主动行为。(3)进程唤醒过程：2.2.4 进程的挂起与激活:交换进程(0号进程，sched)(1)进程的挂起；从内存置换到外存。(2)进程的激活过程：重新调入内存。2.3 进程同步与互斥2.3.1 进程同步的基本概念并发进程间的关系可以是无关的，也可以是有交往的。独立进程或协作进程。 1、两种制约关系： 间接制约关系：互斥进程互斥是指当有若干个进

18、程使用某一共享资源时，任何时刻最多只允许一个进程使用，而其他要使用该资源的进程必须等待，直到占用资源者释放该资源。是进程间竞争共享资源的使用权，没有固定的必然关系。利用公用信号量直接制约关系：同步进程同步是指并发进程之间存在一种制约关系，一个进程的执行依赖另一个进程的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息到达才被唤醒。涉及共享资源的并发进程之间有一种必然的依赖关系。利用私用信号量。作业6：进程间同步和互斥的含义各是什么？不允许两个以上共享临界资源的并发进程同时进入临界区的现象称为互斥。进程同步是指在异步环境下的一组并发进程因直接制约而相互发送消息导致的各个进程相互使用、相互

19、等待，使得各个进程按一定的速度执行的现象称为进程间的同步 同步与互斥的混合问题：进程的互斥是进程间竞争共享资源的使用权，这种竞争没有固定的必然关系；进程同步，涉及共享资源的并发进程之间有一种必然的依赖关系。 race condition竞争条件：多个内核进程同时活动，会发生竞争条件。如打开文件的内核数据结构，内存分配的数据结构，维护进程列表及处理中断处理程序的数据结构。 非抢占内核式的系统中不会导致竞争条件，抢占内核的系统可能会导致竞争条件。抢占内核比非抢占内核更受欢迎。Windows XP和Windows 2000为非抢占式内核，传统的Unix和Linux 2.6以前的内核也是非抢占式的。L

20、inux 2.6以后，商用Unix、Solaris是抢占内核2、临界资源：一次只允许一个进程使用的资源。打印机、磁带机、消息缓冲队列、变量、数组、缓冲区等。又称独享资源。 3、临界区：实现互斥的方法：软件和硬件方法1965年Dijkstra(狄克斯特拉)提出的临界段设计原则4、同步机制的规则：空闲让进，忙则等待，有限等待和让权等待。（在单处理机系统中是必须的，在多处理机系统中不是必须的） 实现同步的几种方法1、禁止中断：只适合单处理器环境，会出现饿死。2、TestAndSet Lock指令：不可分的原子操作,可适用于多处理器环境。Boolean TestAndSet(boolean locke

21、d) if(locked) return true; else locked=true; return false; TSL算法Enter_region: TSL REGISTER,LOCK复制乐到寄存器并将锁设为1 CMP REGISTER,#0 JNE enter_region若不是0,说明锁已被设置，所以循环 RET 返回调用者，进入了临界区Leave_region: MOVE LOCK,#0 在锁中存入0 RET 返回调用者3、Swap指令 boolean void Swap(boolean a,boolean b) boolean temp; temp=b; b=a; a=temp;

22、 Swap算法Do key=TRUE; swap(&lock,&key); critical section; lock=FALSE; remainder section; while(TRUE);4、Dekker算法和Peterson算法：基于软件的两个进程间的通信。 Bakery算法，用于N个进程间的通信Peterson解法#define FALSE 0#define TRUE 1#define N 2 ;进程数量Int turn;现在轮到谁Int interestedN;所有值初始化为0,即FALSE；Void enter_region(int process);进程是0或1 int o

23、ther;其他进程号 other=1-process;另一方进程 interestedprocess=TRUE;表明所感兴趣的 turn=process;设置标志 while(turn=process&interestedother=TRUE)； Void leave_region(int process)进程：谁离开？ interestedprocess=FALSE;表示离开临界区Peterson算法中Pi的结构Do flagi=TRUE; turn=j; while(flagj&turn=j); 临界区； flagi=FALSE; 剩余区； while(TRUE);2.3.2 信号量机制

24、1、整型信号量：P、V操作 wait(s):while s=0 do nothing; s=s-1;信号量的值不可能取负值。 signal(s):s=s+1;又称简单信号量，二元信号量，二进制信号量，互斥锁。缺点：忙等待方式busy waiting,自旋锁（优点：不进行上下文切换，常用于多处理系统）2013.3.24网络2、记录型信号量： struct semaphore int:value; struct process *L; s; wait(s): s.value=s.value-1; if s.value0 then block(s.L);信号量的递减和测试次序的互换，其值可取负值。

25、signal(s):s.value=s.value+1; if s.value=0 then wakeup(s.L);又称计数信号量，资源信号量，用来控制m个进程访问某一类n个临界资源。作业7:记录型信号量的物理含义：例：设有n个进程共享一个程序段，对于如下两种情况：（1）如果每次只允许一个进程进入该程序段。（2）如果每次最多允许m个进程（m0)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用geteven()从该缓冲区中取出一个偶数并countev

26、en()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。 答案：定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty控制生产者与消费者之间的同步；mutex控制进程间互斥使用缓冲区。程序如下： Var s1=0,s2=0,empty=N,mutex=1; Parbegin P1:begin X=produce(); /*生成一个数*/ P(empty);/*判断缓冲区是否有空单元*/ P(mutex); /*缓冲区是否被占用*/ put(x); If x%2=0 V(s2); /*如果是偶数，向P3发出信号*/

27、 else V(s1); /*如果是奇数，向P2发出信号*/ V(mutex); /*使用完缓冲区，释放*/ P2：begin P(s1); /*收到P1发来的信号，已产生一个奇数*/ P(mutex); /*缓冲区是否被占用*/ Getodd(); Countodd():=coutodd()+1; V(mutex); /*释放缓冲区*/ V(empty); /*向P1发信号，多出一个空单元*/ End. P3:begin P(s2); /*收到P1发来的信号，已产生一个偶数*/ P(mutex); /*缓冲区是否被占用*/ Geteven(); Counteven():=counteven(

28、)+1; V(mutex); /* 释放缓冲区*/ V(empty); /*向P1发信号，多出一个空单元*/End.Parend.2.4.2 读者和写者问题：一直用来测试几乎所有新的同步原语。多个用户共享数据库系统的建模问题。有多种不同的策略，都与优先级有关。 1、读者优先：第一读者-写者问题，写者可能饥饿。 2、排队策略或先来先服务 3、写者优先：第二读者-写者问题，读者可能饥饿。 4、某个进程即是写者又是读者的问题例：设有P1,P2,P3三个进程共享某一资源F，P1对F只读不写，P2对F只写不读，P3对F先读后写。当一个进程写F时，其他进程对F不能进行读写，但多个进程同时读F是允许的。试用

29、P、V操作正确实现P1,P2,P3的同步互斥。要求：（1）正常运行时不产生死锁（2）使用F的并发度要高。（北京大学1996年研究生试题） 解：本题实际上是一个读者和写者问题，P1是一个读者，P2是一个写者，为了使F的并发度较高，将P3先看成读者，当其完成读操作后，再将其看成写者。 定义如下变量： 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(re

30、adcount=0)V(mutex); V(rmutex);P2() While(1) P(mutex); 写F； V（mutex）;P3() While(1) P(rmutex); 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、同时允许四个哲学家提出进餐要求

31、2、同时去拿起两边的筷子 3、使用非对称解决方法，奇数号哲学家先拿左边的筷子，偶数号哲学家先拿右边的筷子注意：没有死锁的解决方案并不能消除饿死的可能性。2.4.4 理发师嗜睡问题 一个理发店由一个有N张椅子的等候室和一个放有一张理发椅的理发室组成。若没有要理发的顾客，则理发师就去睡觉，若一个顾客走进理发店且所有的椅子都被占用了，则该顾客就离开理发店，若理发师正在为人理发，则该顾客就找一张空椅子坐下等待，若理发师在睡觉，则顾客就唤醒他。 试用信号量设计一个协调理发师和顾客的程序。（西安电子科技大学2000年研究生试题） 解：本题中，顾客进程和理发师进程之间存在着多种同步关系：（1）只有在理发椅空

32、闲时，顾客才能坐到理发椅上等待理发师理发，否则顾客便必须等待；只有当理发椅上有顾客时，理发师才可以开始理发，否则他也必须等待。这种同步关系类似于单缓冲（理发椅）的生产者和消费者问题中的同步关系，故可以通过信号量empty(初值为1)和full(初值为0)来控制。（2）理发师为顾客理发时，顾客必须等待理发的完成，并在理发完成后由理发师唤醒他，这可单独使用一个信号量cut来控制，初值为0。 （3）顾客理完发后必须向理发师付费，并等理发师收费后顾客才能离开；而理发师则需等待顾客付费，并在收费后唤醒顾客以允许他离开，这可分别通过两个信号量payment和receipt来控制，初值都为0。（4）等候室中

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

34、 从沙发上起来; 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:begin repeat wait(full); 替顾客理发; signal(cut); wait(payment); 收费; signal(receipt);

35、until false; endparendend 2.4.5 “吸烟者”问题。假设一个系统有3个吸烟者（smoker）进程和一个供货商（Agent）进程。每个吸烟者连续不断地制造香烟并吸掉它。 但是，制造一支香烟需要3种材料烟、纸、火柴。一个吸烟者进程有纸，另一个有烟，第三个有火柴。供货商进程可以无限地提供这3种材料。供货商将这这两种材料一起放在桌上，持有另一种材料的吸烟者即可制造一支香烟并吸掉它。当此吸烟者抽香烟时，它发出一个信号通知供货商进程，供货商马上给出另外两种材料，如此循环往复。试编写一个程序使供货商和吸烟者同步执行。解法：semaphore smoker30; 三个吸烟者sema

36、phore 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); coend;变型1抽烟问题：有一个烟草代理和三个抽烟者。抽烟者若要抽

37、烟，必须具有烟叶、烟纸和火柴。三个抽烟者中，一人缺烟叶、一人缺烟纸、一人缺火柴。烟草代理会源源不断地分别供应烟叶、烟纸和火柴，并将它们放在桌上。如果放的是烟叶，则缺烟叶的抽烟者拾起烟叶，制作香烟，然后抽烟；其他类推。试用信号量同步烟草代理和三个抽烟者。解法：semaphore smoker30; 三个吸烟者semaphore material30; 三种原料semaphore agent1; 供应商int turn=0;轮到谁Agent While(1) P(agent); 放原料； V(smokerturn); V(material(turn+1)%3); 制作香烟； 吸烟； turn=(t

38、urn+1)%3Smoker_i While(1) P(smokeri); P(material(i+1)%3); 制作香烟； 吸烟； V(agent); 变型2有一间酒吧里有3个音乐爱好者队列，第1队的音乐爱好者只有随身听，第2队只有音乐磁带，第3队只有电池。而要听音乐就必须随身听、音乐磁带和电池这3种物品俱全。酒吧老板一次出售这3种物品中的任意两种。当一名音乐爱好者得到这3种物品并听完一首乐曲后，酒吧老板才能再一次出售这3种物品中的任意两种，于是第2名音乐爱好者得到这3种物品，并开始听乐曲。全部买卖就这样进行下去。试用P、V操作正确解决这一买卖。（北京大学1999年研究生试题）变型3（桔子

39、汁生产线问题）现有三个生产者P1 、P2 、P3 ，他们都要生产水，每个生产者都已分别购得两种不同原料，待购得第三种原料后就可配制成桔子水，装瓶出售。有一供应商能源源不断地供应糖、水、桔子精，但每次只拿出一种原料放入容器中供给生产者。当容器中有原料时需要该原料的生产者可取走，当容器空时供应商又可放入一种原料。假定：生产者P1已购得糖和水；生产者P2 已购得水和桔子精；生产者P3 已购得糖和桔子精；试用：信号量与P 、V 操作，写出供应商和三个生产者之间能正确同步的程序 2.4.6 银行排队问题(北京大学2000）银行有n个柜员,每个顾客进入银行后先取一个号,并且等着叫号,当一个柜员空闲后，就叫

40、下一个号。解：将顾客号码排成一个队列,顾客进入银行领取号码后,将号码由队尾插入;柜员空闲时,从队首取得顾客号码,并且为这个顾客服务,由于队列为若干进程共享, 所以需要互斥.柜员空闲时,若有顾客,就叫下一个顾客为之服务.因此,需要设置一个信号量来记录等待服务的顾客数.Cobegin var mutex=1,customer_count=0:semaphore; cobegin process customer begin repeat 取号码； p(mutex); 进入队列； v(mutex); v(customer_count); until false; endprocess servers

41、_i(i=1,.,n)begin repeat p(customer_count); p(mutex); 从队列中取下一个号码； v(mutex); 为该号码持有者服务； until falseendCoend变型-面包师问题面包店有很多面包，由n个销售人员推销。每个顾客进店后先取一个号，并且等待叫号。当一个销售人员空闲下来时，就叫下一个号。试设计一个使销售人员和顾客同步的算法。2.4.7 交通问题有桥如图示：（北京大学1992年研究生试题）桥北南车流如箭头所示。桥上不允许两车交会，但允许同方向车辆依次通行（即桥上可以有多个同方向的车）。用P、V操作实现交通管理以防止桥上堵塞。解：设置coun

42、tA和countB表示由南往北、由北 往南已在桥上行驶的汽车数目，初值为0,设置SA表示对countA的互斥，初值为1 ，设置SB表示对countB的互斥，初值为1,设置mutex表示对桥的互斥，初值为1P1：由南往北行驶到桥头； P（SA）;If(countA=0)P(mutex);countA+;V(SA);过桥；P(SA); countA-; if(countA=0)V(mutex);V(SA);P2：由北往南行驶到桥头； P（SB）;If(countB=0)P(mutex);countB+;V(SB);过桥；P(SB); countB-; if(countB=0)V(mutex);V(

43、SB);管程机制（略）1、管程的定义：是由一组局部的变量对局部变量进行操作的一组过程以及对局部变量进行初始化的语句序列构成的一个软件模块。可用来实现进程同步。Type monitor_name=monitor variable declarations; procedure entry P1(); begin end; procedure entry Pn(); begin end;Begin initialization code;end管程的特点1、管程内的局部变量只能被局限于管程内的过程所访问；反之亦然，即局部于管程内的过程只能访问管程内的变量。2、任何进程只能通过调用管程提供的过程入口

44、进入管程3、任一时刻，最多只能有一个进程在管程中执行。 保证进程互斥进入管程是由编译器负责，即管程是一种编程语言的构件，它的实现需要编译器的支持。管程解决生产者消费者问题先建立一个管程。Type P_C=monitor var in,out,count:integer; buffer:array0.n-1 of item; notfull,notempty:condition; procedure entry put(var product:item) begin if count=n then notfull.wait bufferin:=product; in:=(in+1) mod n;

45、 count:=count+1; notempty.signal end procedure entry get(var product:item) begin if count0，该进程继续执行；若S0，则阻塞该进程，并把它插入该信号量对应的阻塞队列中，重新进程调度。10、叙述进程和程序的主要区别。解：进程和程序是既有联系又有区别的两个概念，它们的主要区别如下：（1）程序是指令的有序集合，其本身没有任何运行的含义，它是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态概念。（2）程序的存在是永久的。而进程是有生命期的，它因创建而产生，因调度而执行，因得不到资源而暂停，因撤消而

46、消亡。（3）程序仅是指令的有序集合。而进程则由程序、数据和进程控制块组成。（4）进程与程序之间不是一一对应的，即同一程序同时运行若干个不同的数据集合上，它将属于若干个不同的进程；而一个进程可以执行多个程序。1、桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。 规定:当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。分析：本题中，爸爸、儿子、女儿共用一个盘子，且盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待，若放入果盘中的

47、是苹果，则允许女儿吃，儿子必须等待。本题实际是生产者消费者问题的一种变形。这里，生产者放入缓冲区产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。解：本题中，应设置三个信号量s,so,sa，信号量s表示盘子是否为空，其初值为1，信号量so表示盘中是否有桔子，其初值为0，信号量sa表示盘中是否有苹果，其初值为0。同步描述如下： var s,sa,so:integer=1,0,0; father:begin p(s); 将水果放入盘中； if(放入的是桔子)v(so); else v(sa); end; son:begin p(so); 从盘中取出桔子； v(s); 吃桔子； end

48、 daughter:begin p(sa); 从盘中取出苹果； v(s); 吃苹果； end2、(北京大学94年试题) 进程A1，A2，An1通过m个缓冲区向进程B1，B2，Bn2不断地发送消息。发送和接收工作遵循如下规则：(1)每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度；(2)对每一个消息，B1，B2，Bn2都必须各接收一次，读入各自的数据区内。(3)m个缓冲区都满时，发送进程等待，没有可读的消息时，接收进程等待。试用P、V操作组织正确的发送和接收工作。分析：本题是生产者消费者问题的一个变形，一组生产者和一组消费者共用m个缓冲区，每个缓冲区只要写一次，但需要读n2次

49、。所以，我们可以把这一组缓冲区看成n2组缓冲区，每个发送者需要同时写n2组缓冲区中相应的n2个缓冲区，而每一个接收者只需读它自己对应的那组缓冲区中的对应单元。解：本题中，应设置一个信号量mutex实现诸进程对缓冲区的互斥访问；两个信号量数组emptyn2和fulln2描述n2组缓冲区的使用情况。mutex的初值为1；数组empty中的元素初值为m;数组full中的元素初值为0。其同步描述如下： var mutex,emptyn2=m,fulln2=0:integer; mutex=1; for(i=0;i=n2-1;i+) emptyi=m; fulli=0; send:begin for(i

50、=0;i=n2-1;i+) p(emptyi); p(mutex); 将消息放入缓冲区； v(mutex); for(i=0;i=n2-1;i+) v(fulli); end; receive_i:begin p(fulli); p(mutex); 将消息从缓冲区取出； v(mutex); v(emptyi); end; Ai:begin repeat send(); until false; end Bi:begin repeat receive(i); until false; end3、(北京大学90年试题)(略) (1)写出P、V操作的定义 (2)有三个进程PA、PB和PC合作解决文件

51、打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次，复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P、V操作来保证文件的正确打印。解：(2)本题中：进程PA、PB和PC之间的关系为：PA与PB共用一个单缓冲区，而PB又与PC共用一个单缓冲区，其合作方式如图示： 从磁盘读入复制缓冲区1缓冲区2PAPCPB打印 当缓冲区1为空时，PA可将一个记录读入其中，若缓冲区1中有数据且缓冲区2为空，PB可将记录从缓冲区1复制到缓冲区2中；若缓冲区2中有数据，则进程PC可打印记录。其他条

52、件下，相应进程必须等待。实际上，这是一个生产者消费者问题。(PB既是生产者又是消费者) 为遵循这一同步规则。应设置四个信号量empty1、empty2、full1、full2，信号量empty1和empty2分别表示缓冲区1及缓冲区2是否为空，其初值为1；信号量full1和full2分别表示缓冲区1和缓冲区2是否有记录可供处理，其初值为0。其同步描述如下： 初始化； PA:begin repeat 从磁盘读一个记录； p(empty1); 将记录存入缓冲区1； v(full1); until false; end PB:begin repeat p(full1); 从缓冲区1取出记录； v(e

53、mpty1); p(empty2); 将记录存入缓冲区2； v(full2); until false; endPC:begin repeat p(full2); 从缓冲区2中取出记录； v(empty2); 打印记录； until false end中国矿大20044、P、V操作实现进程同步与互斥(40分)(1)P、V操作是原语，用类似C(或C+，或Pascal，或Java)写出信号量和V操作的定义(5分)(2)针对您写出的V操作，说明为什么V操作要求是原语？(10分)(3)使用P、V操作实现临界区的管理，S是信号量，说明S初始值为1，S值小于0，等于0的物理意义(5分)(4)有三个并发进程

54、：R负责从输入设备读入信息单元逐个放到缓冲区B1，B1由两个单元构成；M负责从B1缓冲区逐个读出信息单元，对信息加工处理后放入缓冲区B2，B2由两个单元构成；P负责从缓冲区B2逐个打印输出信息单元。使用P、V操作实现它们之间的同步。(20分)(设置您需要的信号量，指出它们的初始值，画出利用P、V操作实现它们的同步的流程)中国矿大20035、 有一个盆子可以放两个水果(两个苹果、或两个桃子、或一个苹果和一个桃子)。父亲不停地向盆子每次只放一个苹果，母亲不停地向盆子每次只放一个桃子；儿子从盆子只取一个苹果，消费完继续取一个苹果消费；女儿从盆子只取一个桃子，消费完继续取一个桃子消费。 用P、V操作实

55、现上述四个人的同步与互斥。中国矿大20056、 有10个计算进程P1，P2，P10，它们负责各自的计算，计算完成后必须把一个单元的计算结果依次写入缓冲区B的一个单元，然后，继续循环地计算，写缓冲区工作。进程P0负责循环地从缓冲区B依次取出数据单元打印。缓冲区B有依次排列的5个单元组成。问：1(10分)用P、V操作实现它们的同步。2(10分)你设置的信号量各自可能的最大值、最小值是多少？它们有何物理意义？7、 有两个优先级相同的并发进程m1,m2，各自计算过程如下所示。它们利用信号量s1,s2同步，信号量s1,s2初始值设置为0。X,y,z是它们共享的变量。问m1,m2运行结束后，x,y,z在理

56、论上可能的值分别是多少?进程m1 进程m2 x=1 y=2 V(s1) P(s1) z=x+1 z=y+1 P(s2) V(s2) x=z+x y=y+z苏州大学20078、(15分)设有五个哲学家，他们花费一生中的时光思考和吃饭。这些哲学家共用一个圆桌，每个哲学家都有一把椅子。桌子中央是一碗米饭。桌上总共有6根筷子，在每个两边分开各放一根，桌子中央还有一根。当一个哲学家思考时，他与其他同事不交互，一个哲学家一次只能拿起一根筷子，显然他不能从其他哲学家手里抢走筷子，吃完后放下所有的筷子。哲学家只有在饥饿时才试图从两边或者桌子中央取2根筷子进餐。试问：(1)用P、V操作描述满足上述要求的哲学家进

57、程，要求不能产生死锁。(2)分析上述解决方案的利弊。9、某数据库有一个写进程，多个读进程，它们之间读、写操作的交互要求是： 写进程正在写该数据库时不能有其他进程读该数据库，也不能有其他进程写该数据库；读进程之间不互斥，可以同时读该数据库。 请用信号量及P、V操作描述这一组进程的工作过程。解：本题中，允许读进程同时读数据库，但写进程正在写数据库时不允许其他进程读数据库，也不允许其他进程写该数据库。 为了解决读、写进程之间的同步，应设置两个信号量和一个共享变量；读互斥信号量rmutex，用于使读进程互斥地访问共享变量count，其初值为1，写互斥信号量wmutex，用于实现写进程与读进程的互斥及写

58、进程与写进程的互斥，其初值为1；共享变量count，用于记录当前正在读数据库的读进程数目，初值为0。其工作过程如下：同教材。10、(中国科学院软件研究所95年试题) 多个进程共享一个文件，其中只读文件的称为读者，只写文件的称为写者。读者可以同时读，但写者只能独立写。请：(1)说明进程间的相互制约关系，应设置哪些信号量？(2)用P、V操作写出其同步算法。(3)修改上述的同步算法，使得它对写者优先，即一旦有写者到达，后续的读者必须等待。而无论是否有读者在读文件。解：(1)进程间的相互制约关系有三类： 一是读者之间允许同时读； 二是读者与写者之间须互斥； 三是写者之间须互斥。 为解决读者、写者之间的

59、同步，应设置两个信号量和一个共享变量：读互斥信号量rmutex，用于使读者互斥地访问共享变量count，其初值为1，写互斥信号量wmutex，用于实现写者与读者的互斥及写者及写者的互斥，其初值为1，共享变量count，用于记录当前正在读文件的读者数目，初值为0。(2)进程间的控制算法如下： reader:begin repeat p(rmutex); if(count=0)p(wmutex); count:=count+1; v(rmutex); 读文件； p(rmutex); count:=count-1; if(count=0)v(wmutex); v(rmutex); until fal

60、se endWriter:begin repeat p(wmutex); 写文件； v(wmutex); until false; end(3)为了提高写者的优先级，增加一个信号量s，其初值为1，表示未有写进程正在写。用于在写进程到达后封锁后续的读者。 其过程如下：Reader:begin repeat p(s); p(rmutex); if(count=0)p(wmutex); count:=count+1; v(rmutex); v(s); 读文件； p(rmutex); count:=count-1; if(count=0)v(wmutex); v(rmutex); until fals