操作系统高分笔记PV操作.pdf

天勤论坛：天勤论坛：天勤论坛天勤论坛专为计算机考研学子打造的专业交流平台专为计算机考研学子打造的专业交流平台期待你的加入！期待你的加入！此文档由天勤论坛总结此文档由天勤论坛总结转载请注明出处！转载请注明出处！天道酬勤，厚德载物！天道酬勤，厚德载物！天勤论坛：第二章第二章 进程管理进程管理大纲要求一、一、进程与线程进程与线程1.进程概念2.进程的状态与转换3.进程控制4.进程组织5.进程通信共享存储系统，消息传递系统，管道通信。6.线程概念与多线程模型二、进程同步二、进程同步1.进程同步的基本概念2.实现临界区互斥的基本方法软件实现方法;硬件实现方法。3.信号量4.管程5.经典同步问题生产者-消费者问题，读者-写者问题，哲学家进餐问题。注：处理机调度以及死锁将在处理机调度与死锁处理机调度与死锁一章讲解。本章知识体系框架图天勤论坛：本章基础要点与核心考点一、核心考点：一、核心考点：1、（）进程的定义及特征、进程与程序的异同、进程的状态及引起状态转换的典型原因。2、（）临界区的定义及操作原则，进程同步与互斥，用信号量描述进程同步，进程通信。二、基础要点：二、基础要点：1、进程的并发执行是指若干进程在执行时间上是重叠的。2、进程是一个程序对某个数据集的一次运行活动。3、程序并发执行与顺序执行相比产生了一些新特性：间断性、失去封闭性、不可再现性。4、进程的基本特征是：动态性、并发性、独立性、异步性和结构特征。5、程序的顺序执行通常是在单道程序的工作环境中，具有运行结果可再现的特点。6、进程的基本状态有执行、就绪和阻塞。7、进程是动态的概念，而程序是静态的概念。8、进程控制块的初始化工作包括初始化标识符信息、初始化处理机状态信息、初始化处理机控制信息。9、当进程执行的时间片用完时，进程由执行状态转变为就绪状态。10、进程从结构上讲，包括程序段、数据段和进程控制块（PCB）三部分。11、在操作系统中引入线程概念的主要目的是减少程序并发执行时所需付出的时空开销，提高程序执行的并发程度。12、在进程中，访问临界资源的代码段称为临界区。为保证进程互斥访问临界资源，应在进程的临界区之前设置进入区，在临界区后设置退出区。13、访问临界资源应遵循的准则为：空闲让进、忙则等待、有限等待、让权等待。14、信号量的物理意义是当信号量值大于零时表示可用资源的数目：当信号量值小于零时，其绝对值为在该信号量上等待的进程个数。15、用 P、V 操作管理临界区时，任何一个进程在进入临界区之前应调用 P 操作，退出临界区时应调用 V 操作。知识点扩展与深度总结一、一、进程同步基本概念进程同步基本概念1两种形式的制约关系（课本 P38）（1）间接相互制约关系（互斥）：这种制约关系源于多个同种进程需要互斥地共享某种系统资源（比如打印机），互斥是设置在同种进程之间以达到互斥地修改资源数的目的（比如在生产者-消费者问题中，生产者与生产者之间需要互斥地访问缓冲池）。（2）直接相互制约关系（同步）：这种制约主要源于进程间的合作，同步设置在不同进程之间以达到多种进程间的同步（比如在生产者-消费者问题中，只要缓冲池不满，生产者就可以生产，只要缓冲池不空，消费者就可以消费）。注：只要是同类进程即为互斥关系，不同类进程即为同步关系。2临界资源与临界区（课本 P39-40）天勤论坛：【易错点解析】这是两个比较容易混淆的概念，有人可能会理解为临界区就是临界资源所在地址，这样理解显然是错误的。简单点说，临界资源是一种系统资源，需要不同进程互斥访问，而临界区则是每个进程中访问临界资源的一段代码，是属于对应进程的，临界区前后需要设置进入区和退出区以进行检查和恢复。3同步机制应遵循的规则（课本 P41）所有的同步机制都应遵循这四条准则（空闲让进，忙则等待，有限等待，让权等待），后面将在实现临界区互斥基本方法中举例说明。二、二、实现临界区互斥的基本方法实现临界区互斥的基本方法1软件方法：对临界区互斥访问技术的研究始于 20 世纪 60 年代，早期主要从软件方法上进行研究，下面我们介绍这些软件方法。它们有的是正确的，有的是不正确的。之所以介绍这些方法是为了说明用软件方法解决互斥和同步问题的困难和复杂性。例如有两个进程 P0和 P1，互斥地共享某个资源。P0和 P1是循环进程，它们执行一个无限循环程序，每次使用资源一个有限的时间间隔。注注：临界区互斥的软件实现方法在历年来各学校的操作系统考题中出现过，通常作为选择题出现，用来考察同步机制的四个准则，统考的两年中在 2010 年真题第 27 题以选择题的形式考察过，因此在这里比较详细地介绍一下，帮助大家熟悉和理解四个准则以及同步机制的实现过程。算法算法 1 1：设置一个公用整形变量 turn，用来指示允许进入临界区的进程标识。若 turn为 0，则允许进程 P0进入临界区；否则循环检查该变量，直到 turn 变为本进程标识；在退出区，修改允许进入进程的标识 turn 为 1。进程 P1的算法与此类似。两个进程的程序结构如下：int turn=0；P0:DoWhile(turn!=0);/当turn不为0时循环检查，直到为 0进入 P0的临界区代码 CS0;turn=1;进入 P0的其他代码;While(true)/循环执行这段代码P1:DoWhile(turn!=1);进入 P1的临界区代码 CS1;turn=0;进入 P1的其他代码;While(true)此方法可以保证互斥访问临界资源，但存在的问题是强制两个进程以交替次序进入临界区，很容易造成资源利用不充分。例如，当进程 P0退出临界区后将 turn 置为 1，以便允许进程 P1进入临界区，但如果进程 P1暂时并未要求访问该临界资源，而 P0又想再次访问临界资源，则它将无法进入临界区。可见，此算法不能保证实现“空闲让进”准则。算法算法 2 2：设置标志数组 flag表示进程是否在临界区中执行，初值均为假。在每个进程访问该临界资源之前，先检查另一个进程是否在临界区中，若不在则修改本进程的临界区标志为真并进入临界区，在退出区修改本进程临界区标志为假。两进程的程序结构如下：enum booleanfalse,true;boolean flag2=false,false;天勤论坛：P0:DoWhile flag1;/flag1为真表示 P1在访问临界区，P0等待。flag0=true;进程 P0的临界区代码 CS0;flag0=false;进程 P0的其他代码;While(true)P1:DoWhile flag0;/flag0为真表示 P0在访问临界区，P1等待。flag1=true;进程 P1的临界区代码 CS1;flag1=false;进程 P1的其他代码;While(true)此算法解决了“空闲让进”的问题，但又出现了新问题。即当两个进程都未进入临界区时，它们各自的访问标志都为 false，若此时刚好两个进程同时都想进入临界区，并且都发现对方的标志值为 false（当两进程交替执行了检查语句后，都满足 flag=false 的条件），于是两个进程同时进入了各自的临界区，这就违背了临界区的访问规则“忙则等待”。算法算法 3 3：本算法仍然设置标志数组 flag,但标志用来表示进程是否希望进入临界区，在每个进程访问临界资源之前，先将自己的标志设置为真，表示进程希望进入临界区，然后检查另一个进程的标志。若另一个进程的标志为真，则进程等待；否则进入临界区。两进程的程序结构如下：enum booleanfalse,true;boolean flag2=false,false;P0:Doflag0=true;While flag1;/flag1为真表示 P1希望访问临界区，P0等待。进程 P0的临界区代码 CS0;flag0=false;进程 P0的其他代码;While(true)P1:Doflag1=true;While flag0;/flag0为真表示 P0希望访问临界区，P1等待。进程 P1的临界区代码 CS1;flag1=false;进程 P1的其他代码;While(true)此算法可以有效地防止两进程同时进入临界区，但存在两个进程都进不了临界区的问题。即当两个进程同时想进入临界区时，它们分别将自己的标志位设置为 true，并且同时去检查对方的状态，发现对方也要进入临界区，于是对方互相谦让，结果都无法进入临界区。造成“死等”现象，违背了“有限等待”的准则。算法算法 4 4：本算法的思想是算法 3 和算法 1 的结合。标志数组 flag表示进程是否希望进入临界区或是否在临界区中执行。此外，还设置了一个 turn 变量，用于指示允许进入临界区的进程标识。两进程的程序结构如下：天勤论坛：enum booleanfalse,true;boolean flag2=false,false;int turn;P0:Doflag0=true;turn=1;/此时 P0未进入临界区，仍然允许 P1进入临界区。While(flag1&turn=1);/flag1为真表示 P1希望访问临界区，turn 为 1 表示 P1可以进入临界区，因此 P0等待。进程 P0的临界区代码 CS0;flag0=false;/表示 P0退出访问临界区。进程 P0的其他代码;While(true)P1:Doflag1=true;turn=0;/此时 P1未进入临界区，仍然允许 P0进入临界区。While(flag0&turn=0);/flag0为真表示 P0希望访问临界区，turn 为 0 表示 P0可以进入临界区，因此 P1等待。进程 P1的临界区代码 CS1;flag1=false;/表示 P1退出访问临界区。进程 P1的其他代码;While(true)至此，算法 4 可以完全正常工作。我们从上面的软件实现方法中可以看出，对于两个进程间的互斥，最主要的问题就是标志的检查和修改不能作为一个整体来执行，因此容易导致无法保证互斥访问的问题。2硬件方法：注：注：硬件方法在考题中基本不出现，只需简单了解即可。完全利用软件方法实现进程互斥有很大的局限性，现在已经很少单独采用软件方法。硬件方法的主要思想是用一条指令完成标志的检查和修改两个操作，因而保证了检查操作与修改操作不被打断；或通过中断屏蔽的方式来保证检查和修改作为一个整体执行。硬件方法主要有两种：一种是中断屏蔽，另一种是硬件指令。（在计算机组成原理中会详细讲解中断与指令，操作系统中很少涉及，因此不展开叙述了）三、信号量三、信号量1信号量的分类（课本 P41）：整型信号量（引入 PV 操作，存在“忙等”问题）、记录型信号量（引入进程链表）、AND 型信号量（引入多种临界资源的“AND 分配”）、信号量集（对 AND 信号量机制的扩充，可以一次分配多种、多个临界资源）2信号量的应用（课本 P42）：实现进程同步与互斥，实现前趋关系。3注意：信号量的初值不能为负数。信号量的引入与发展课本上讲的比较清楚，从整型信号量发展到记录型、AND 型信号量以及之后的信号量集，之前信号量类型存在的问题以及之后信号量类型的引入都有比较详细的介绍，这里就不展开叙述。信号量的应用重点在于进程同步与互斥，这部分将在经典同步问题中详细介绍。四、管程（课本四、管程（课本 P51P51）天勤论坛：为了解决大量分散的同步操作导致管理困难和死锁，因此引入管程概念。管程定义了一个数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。注：注：管程在考题基本不涉及，因此不展开叙述，课本上的内容了解即可。五、经典同步问题五、经典同步问题进程同步问题历来是操作系统考核的重点，基本以三种经典同步问题及其衍生问题为主要考察内容，下面将详细介绍这三种经典同步问题，并在后面的练习中提及一些衍生问题。1 1、生产者、生产者-消费者问题消费者问题生产者-消费者问题是最著名的进程同步问题。它描述了一组生产者向一组消费者提供产品，它们共享一个有界缓冲区，生产者向其中投入产品，消费者从中取走产品。这个问题是许多相互合作进程的一种抽象。例如，在输入时，输入进程是生产者，计算进程是消费者；在输出时，计算进程是生产者，打印进程是消费者。为解决这一问题，应当设置两个同步信号量，一个说明空缓冲区数目，用 empty表示，初值为有界缓冲区大小 n；另一个说明满缓冲区数目（即产品数目），用 full 表示，初值为 0。此外，还需要设置一个互斥信号量 mutex，其初值为 1，以保证多个生产者或者多个消费者互斥访问缓冲池。生产者-消费者问题的同步程序结构描述如下：Semaphore full=0;/*满缓冲单元的数目*/Semaphore empty=n;/*空缓冲单元的数目*/Semaphore mutex=1;/*对有界缓冲区进行操作的互斥信号量*/Buffer array0,.,n-1;/*存放产品的缓冲区*/Integer in=0,out=0;/*缓冲池的指针，指示生产者和消费者进程存取位置*/Main（）CobeginProducer();Consumer();Coend;Producer()While(true)Produce an item put in nextp;P(empty);P(mutex);Buffer(in)=nextp;/*将产品放入缓冲池*/in=(in+1)mod n;/*指针后移*/V(mutex);V(full);Consumer()天勤论坛：While()P(full);P(mutex);nextc=buffer(out);out=(out+1)mod n;V(mutex);V(empty);Consumer the item in nextc;【易错点解析】1）P（full）/P（empty）与 P（mutex）的顺序不可颠倒，必须先对资源信号量进行 P 操作，再对互斥信号量进行 P 操作，否则会导致死锁。（例如，此时缓冲区已满，而生产者先 P（mutex），取得缓冲池访问权，再 P（empty），此时由于缓冲池已满，empty=0，导致 P（empty）失败，生产者进程无法继续推进，始终掌握缓冲池访问权无法释放，因而消费者进程无法取出产品，导致死锁。）而 V(full)/V(empty)与 V(mutex)的顺序则没有要求，可以颠倒顺序。这个问题可以延伸到几乎所有 PV 操作题中，在有多个信号量同时存在的情况下，P 操作往往是不能颠倒顺序的，必须先对资源信号量进行 P 操作，再对互斥信号量进行P 操作，这样可以保证在占有信号量访问权的时候保证有资源可以使用，不然会导致占用使用权而无资源可用的死等。2）关于 mutex 互斥信号量的设置是否必要的问题。在生产者和消费者都唯一的问题中，生产者与消费者是同步关系（见两种形式的制约关系，课本 P38），生产者与消费者之间使用 empty 与 full 两个资源信号量进行同步，一定满足“放完才能取”的条件，因此此时互斥是多余的，mutex 可以去掉。但在多生产者和多消费者的情况下，需要保证多个生产者或者多个消费者互斥地访问缓冲池，否则会导致出错。例如，两个生产者执行了 P（empty）操作，此时第一个生产者执行 buffer(in):=nextp，这是第二个生产者也执行这条语句，由于第一个生产者没有来得及执行 in:=(in+1)mod n，即没有使指针后移，导致第二个生产者的数据覆盖掉了第一个生产者的数据而不是放在了第一个数据的下一个缓冲区，接下来两个进程分别执行一次后移指针操作，这样就导致了有一个空缓冲区（本来应当放置第二个数据的缓冲区）被当做已有数据缓冲区对待，导致出错。因此在多生产者或多消费者情况下，必须设置 mutex 互斥信号量，以保证对缓冲池的互斥访问。这里可记住一点：只要有多个同类进程，就一定需要互斥信号量，若同类进程只有一个，则记录型信号量即可完成进程同步。2 2、读者、读者-写者问题写者问题有一个许多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间；有一些只读取这个数据区的进程（读者）和一些只往数据区写数据的进程(写者)，此外还需要满足以下条件：（1）任意多个读者可以同时读这个文件；天勤论坛：（2）一次只有一个写者可以往文件中写；（3）如果一个写者正在进行操作，禁止任何读进程读文件。我们需要分两种情况实现该问题：读优先：一个读者试图进行读操作时，如果这时正有其他读者在进行读操作，他可直接开始读操作，而不需要等待。写优先：一个读者试图进行读操作时，如果有其他写者在等待进行写操作或正在进行写操作，他要等待该写者完成写操作后才开始读操作。读者优先算法：课本 P49 中给出的算法即为读者优先算法。写者优先算法：1）多个读者可以同时进行读2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）3）写者优先于读者（一旦有写者，则后续读者须等待，唤醒时优先考虑写者）如果读者数是固定的，我们可采用下面的算法：rwmutex：用于写者与其他读者/写者互斥的访问共享数据rmutex：该信号量初始值设为 10，表示最多允许 10 个读者同时进行读操作Semaphorerwmutex=1,rmutex=10；procedure reader_i()/第 i 个读者进程（i=1,2,）P(rwmutex);P(rmutex);V(rwmutex);/释放读写互斥信号量，允许其它读、写进程访问读数据;V(rmutex);procedure Writer_j/第 j 个写者进程（j=1,2,）P(rwmutex);for(i=1;i=10;i+)P(rmutex);/禁止新读者，并等待已进入的读者退出写更新;for(i=1;i=10;i+)V(rmutex);/恢复 rmutex 值为 10V(rwmutex);3 3、哲学家进餐问题、哲学家进餐问题5 个不讲卫生的哲学家围绕一张圆桌而坐，桌子上放着 5 支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。解法一：semaphore Fork4=0,1,2,3,4;philosopher_i()天勤论坛：Thinking;Being hungry;P(Forki mod 5);P(Fork(i+1)mod 5);Eating;V(Forki mod 5);V(Fork(i+1)mod 5);这种解法存在问题，会导致死锁，假如 5 个哲学家同时饥饿而各自拿左边的筷子时，会导致 5 个筷子的信号量均为 0，当他们试图拿右边的筷子时，都将因没有筷子而无限等待。对于这种死锁问题，可以采用以下几种解决方法：1）仅当哲学家的左右筷子均可用时，才允许其进餐。（即用 AND 信号量机制解决）解法如下：Semaphore array5=1,1,1,1,1;Philosopher_i()/i=0,1,2,3,4While(ture)Think;Sswait(chopstick(i+1)mod5,chopsticki);Eat;Ssignal(chopstick(i+1)mod5,chopsticki);2）规定奇数号哲学家先拿左边筷子，然后拿右边筷子；而偶数号哲学家相反。解法如下：semaphore c5=1,1,1,1,1;初值均为 1；philosopher_i()/i=0,1,2,3,4If(i mod 2!=0)/判断是否为奇数号哲学家/若为奇数号哲学家先拿左边筷子P(ci);P(ci+1 mod 5);Eating;V(ci);V(ci+1 mod 5);else/若为偶数号哲学家先拿右边筷子P(ci+1 mod 5);P(ci);Eating;天勤论坛：V(ci+1 mod 5);V(ci);关于解决信号量问题的解题思路：主要是看看进程等的信号和要发出的信号是什么，理清思路。等信号用 Wait/P,发信号用 signal/V。主要步骤是：(1)分析清楚题目涉及的进程间的制约关系。(2)设置信号量（包括信号量的个数和初值及其物理含义），合作进程间需要收发几条消息相应就设置几个信号量。(3)给出进程相应程序的算法描述或流程控制，并把 wait、signal 操作加到程序的适当处。第一二步是基础、关键，第三步是核心。掌握实现进程互斥与进程同步的第三步在形式上差异：即 wait、signal 操作总是配对出现的。但 wait,signal 在互斥问题中总是出现在同一个进程的代码中，且紧紧夹着临界区；而在同步问题中，却是分别出现在两个合作进程的代码中，需要等消息的一方用 wait 操作，相应的对同一信号量的 signal 操作则在发出此消息的另一方中。掌握这几点基本就差不多了。例题精析【例 1】简述进程同步与互斥地概念与区别。一般来说，一个进程相对另一个进程的运行速度是不确定的。也就是说，进程之间是在异步环境下运行的，每个进程都以各自独立的、不可预知的速度向运行的终点推进。但是，相互合作的几个进程需要在某些确定点上协调其工作。一个进程到达了这些点后，除非另一进程已完成了某些操作，否则就不得不停下来等待这些操作的结束。所谓进程同步是指多个相互合作的进程，在一些关键点上可能需要互相等待或互相交换信息，这种相互制约关系称为进程同步。在操作系统中，当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许去访问此临界资源，我们称进程之间的这种相互制约关系为互斥。其实互斥是进程同步的一种特殊情况，互斥也是为了达到让进程之间协调推进的目的。【例 2】结构 cobegin 语句 1；语句 2 coend 表示语句 1 和语句 2 并发执行。对下列程序段，X:=0;Y:=0;CobeginBeginX:=1;Y:=Y+X;天勤论坛：EndBeginY:=2;X:=X+3;EndCoend当这个程序执行完时，变量 X 和 Y 的值有可能为：.X=1,Y=2.X=1,Y=3.X=4,Y=6请选出下列答案中唯一正确的一个(A)(B)和(C)和(D)、和哈尔滨工业大学 1997答案：（D）分析：由于语句并发执行，所以可能的执行顺序有、（X=4,Y=6），（X=1,Y=3），、（X=4,Y=6）六种情况。所以应该选 D。、是为方便叙述加上的。这类题主要考对于并发执行的理解，列出所有可能情况时，注意 begin 和 end 中的语句还是按顺序执行的。【例 3】P1、P2、P3、P4、P5、P6 为一组合作进程，其前趋图如图所示，试用 P、V 操作完成这六个进程的同步。图中说明任务启动后 P1 先执行，当其结束后 P2、P3、P4 可以开始执行，P2 完成后 P5可以开始执行，仅当 P3、P4、P5 都执行完后，P6 才能开始执行。为了确保这一执行顺序，设 5 个同步信号量 f1、f2、f3、f4、f5 分别表示进程 P1、P2、P3、P4、P5 是否执行完成，其初值均为 0。这六个进程的同步描述如下：Semaphore f1=f2=f3=f4=f5=0;Main()CobeginP1();P2();P3();P4();P5();天勤论坛：CoendP1().V(f1);V(f1);V(f1);P2()P(f1);.V(f2);P3()P(f1);.V(f3);P4()P(f1);.V(f4);P5()P(f2);.V(f5);P6()P(f3);P(f4);P(f5);.【例 4】简述整型信号量（integer semaphore）与记录型信号量（recordsemaphore）的概念与联系。整型信号量：用于实现进程互斥和同步的一种特殊的整型量，除了初始化外，它仅能通天勤论坛：过两个标准化的原子操作 P(S)和 V(S)被访问。P、V 操作可描述为：P(S):while（S0）;S=S-1;V(S):S=S+1;记录型信号量：用于实现进程互斥和同步的一种特殊的记录，包含两个数据项：（1）信号量的值 value，它仅能通过 P(S)、V(S)被访问；（2）进程链表 L。记录型信号量可以描述为：Type semaphore=recordint Value;List_of_process L;End相应的 P(S)、V(S)可描述为：Procedure P(S)Semaphore S;S.value=S.value-1;If(S.value0)block(S.L);/*若信号量小于零则将进程阻塞并加入进程链表 L 中*/Procedure V(S)Semaphore S;S.value=S.value+1;If(S.value0)wakeup(S.L);/*若有阻塞进程，唤醒链表中的一个进程*/【例 5】今有三个并发进程 R、M、P，它们共享一个可循环使用的缓冲区 B，缓冲区 B 共有 N 个单元。进程 R 负责从输入设备读信息，每读一个字符后，把它存入缓冲区 B 的一个单元中；进程 M 负责处理读入的字符，若发现读入的字符中有空格符，则把它改成“，”；进程 P 负责把处理后的字符取出并打印输出。请用 P、V 操作作为同步机制写出它们能正确并发执行的程序。在本题中，三个并发进程 R、M、P 共享了一个可循环使用的缓冲区 B,进程 R 负责从输入设备读字符并存入缓冲单元中，进程 M 负责将读入字符中的空格符改成“，”，进程 P 负责处理后字符的打印输出。为此，应设置四个信号量 mutex、empty、full1、full2。Mutex用于实现对缓冲区的互斥访问，其初值为 1；empty 表示缓冲区中可用单元数目，其初值为N；full1 表示已读入字符个数，初值为 0；full2 表示已处理字符个数，其初值为 0。为了描述方便起见，还应设置三个指针 in、out1、out2，in 指向下一个可用缓冲单元，out1 指向下一个待处理字符，out2 指向下一个待输出字符。它们并发执行的同步机制描述如下：Semaphore empty=N;Semaphore full1=0;Semaphore full2=0;Semaphore mutex=1;Char bufferN;Int in=0,out1=0,out2=0;Main()Cobegin天勤论坛：R();M();P();CoendR()While(true)Char x;读入一个字符到 x;P(empty);P(mutex);Bufferin=x;in=(in+1)%N;V(mutex);V(full1);M()Char x;While(true)P(full1);P(mutex);x=bufferout1;If(x=)x=,;Bufferout1=x;Out1=(out1+1)%N;V(mutex);V(full2);P()Char x;While(true)P(full2);P(mutex);天勤论坛：x=bufferout2;Out2=(out2+1)%N;V(mutex);V(empty);输出字符 x;本题是“生产者-消费者”问题的一个衍生问题，较原始问题加入了一个既是生产者也是消费者的进程 M，因此本题中有两个生产者和两个消费者，所以一定要有 mutex 信号量保证进程对缓冲池的互斥访问（见知识点讲解中生产者-消费者问题易错点分析 2）。【例 6】某火车订票系统，提供给多个用户同时共享一个订票数据库。规定多个用户允许同时查询该数据库，有查询者时，用户不能订票；有用户订票而需要更新数据库时，不可以有其他用户使用数据库。请用 P、V 操作写出查询者和订票者的同步执行程序。本题是一个典型的“读者-写者”问题，查询者是读者，订票者是写者。读者-写者问题的主要要求是：（1）允许多个读者共享对象；（2）不允许写者和其他读者或写者同时访问共享对象。为了达到上述控制，引入一个变量 readcount，用于记录当前正在运行的读者进程数，以及读互斥信号量 rmutex 和写互斥信号量 wmutex。每个读者进程进入系统后需对readcount 加 1。当 readcount 值由 0 变为 1 时，说明是第一个读者进程进入，因此需要该读者进程对控制写者进程的信号量 wmutex 进行 P 操作，以便与写者进程互斥运行；当readcount 值由非 0 值增加时，说明不是第一个读者进程，此时控制写者进程的信号量已经过 P 操作，已经禁止写者进程进入，因此不需要再次对该信号量进行 P 操作。当读者进程退出时，需对 readcount 做减 1 操作。如发现减 1 后 readcount 变为 0，说明是最后一个读者进程退出，因此需要该读者对控制写者进程的信号量 wmutex 进行 V 操作，以便写者进程能够进入。同步程序描述如下：Semaphore rmutex=1,wmutex=1;Int readcount=0;Inquirer()/查询者进程While(1)P(rmutex);If(readcount=0)P(wmutex);/如果有查询者，不允许订票readcount=readcount+1;V(rmutex);查询数据库;P(rmutex);readcount=readcount-1;If(readcount=0)V(wmutex);/最后一个查询者走后允许订票V(rmutex);天勤论坛：Booker()/订票者进程While(1)P(wmutex);使用数据库，订票；V(wmutex);下面改进一下要求，规定允许多个用户同时查询数据库，当有订票者到达时，不允许后续查询者查询数据库，且多个订票者可以互斥使用数据库。（即写者优先算法）描述如下：Semaphore rmutex=wmutex=r=w=1;/加入 r、w 两个信号量实现订票者优先Int Readcount=0;Int Writecount=0;Inquirer()While(1)P(r);/需先检查有无订票者进程存在P(rmutex);If(readcount=0)P(w);Readcount=readcount+1;V(rmutex);V(r);查询数据库；P(rmutex);Readcount=readcount-1;If(readcount=0)v(w);/无查询者进程存在V(rmutex);Booker()While(1)P(wmutex);If(writecount=0)P(r);/第一个订票者进程进入即不允许后续查询者进程进入Writecount=writecount+1;V(wmutex);P(w);使用数据库，订票;天勤论坛：V(w);P(wmutex);Writecount=writecount-1;If(writecount=0)v(r);/无订票者时允许查询者进入V(wmutex);【例 7】四个哲学家甲、乙、丙、丁，坐在圆桌前思考问题。甲乙间有筷子 0，乙丙间有筷子 1，以此类推。每个哲学家饥饿时，就试图取用两边的筷子，只有两只筷子都拿到才开始进餐。请用 P、V 操作写出哲学家活动的同步执行程序。设置 4 个信号量：chopstick0，chopstick1,chopstick2,chopstick3,初值为 1，分别表示筷子是否可用。P0P3 表示四人活动的进程。Semaphore chopstick0=chopstick1=chopstick2=chopstick3=1=;P0()While(1)P(chopstick3);P(chopstick0);就餐；V(chopstick3);V(chopstick0);思考问题；P1()While(1)P(chopstick1);P(chopstick0);就餐；V(chopstick1);V(chopstick0);思考问题；P2()While(1)P(chopstick1);P(chopstick2);天勤论坛：就餐；V(chopstick1);V(chopstick2);思考问题；P3()While(1)P(chopstick3);P(chopstick2);就餐；V(chopstick3);V(chopstick2);思考问题；本题是典型的哲学家进餐问题。为避免四个哲学家同时饥饿而各自拿起一只筷子，都无限期等待而死锁，本题采用的方法是甲丙先拿起各自右边筷子，然后拿左边筷子，而乙丁则相反（设想哲学家都面对圆桌而坐）。另外解决死锁的方法还有（1）至多只允许 n-1 个哲学家同时进餐，以保证至少一个哲学家可以拥有两只筷子而可以进餐，最终会释放出他所使用的筷子，从而更多人可以进餐。（2）仅当哲学家的左右两只筷子同时可用时，才允许其拿起筷子进餐。下面给出至多只允许 3 个哲学家进餐的解法，其中使用了信号量数组：Var chopstick:array0.3 of semaphore:=(1,1,1,1);S:=semaphore:=3;/同时就餐人数上限为 3BeginParbeginP(i):beginRepeatP(s);/检查就餐是否达到 3P(chopsticki);P(chopsticki+1 mod 4);就餐;V(chopsticki);V(chopsticki+1 mod 4);V(s);/结束就餐思考问题;Until falseEndParendEnd天勤论坛：习题心选一、一、选择题选择题1设有 N 个进程共享一个程序段，而每次最多允许 M 个进程进入该程序段（NM），则所采用的互斥信号量的取值范围可能是（）(A)-N 到 M 间的所有整数(B)0 到 N-M 间的所有整数(C)M-N 到 N-M 间的所有整数(D)M-N 到 M 间的所有整数2对信号量 S 执行 P 操作后，使进程进入等待队列的条件是（）(A)S.value 0(B)S.value 0(C)S.value 0(D)S.value 03用信号量 mutex 实现 n 个进程互斥访问某临界资源，下列叙述正确的是（）(A)信号量 mutex 初值设置为 0(B)信号量 mutex 初值设置为 1(C)信号量 mutex 初值设置为 n(D)只有 n=2 时，信号量 mutex 初值才设为 14对计数信号量 S 执行 V 操作后，下列选项正确的是（）(A)当 S.value 0 时，唤醒一个阻塞队列进程(B)只有当 S.value 0 时，唤醒一个阻塞队列进程(C)当 S.value 0 时，唤醒一个就绪队列进程(D)只有当 S.value 0 时，唤醒一个就绪队列进程5如果系统有 n 个进程，则就绪队列中进程的个数最多有（）个(A)n+1(B)n(C)n-1(D)1选择题解答：选择题解答：1.（D）互斥信号量初值应等于最多允许访问该信号量的进程数目，即信号量可取的最大值；而至多有 N-M 个进程等待，此时信号量取最小值，为负值 M-N。2.（A）参见例题中例 4 关于记录型信号量的解释。此处极易出 S.Value 物理概念题，现总结如下：i.S.value0，表示某类可用资源的数量。ii.每次 P 操作，意味着请求分配一个单位的资源。iii.S.value0，表示某类资源已经没有了，或者说还有因请求该资源而被阻塞的进程。iv.S.value0 时的绝对值，表示等待进程数目。v.切忌看清题目中陈述，是执行 P 操作前还是 P 操作后。本题若改为 P 操作前，则答案为 B。3.（B）信号量是用来控制进程互斥或同步的变量。当用来控制多个进程互斥访问某临界资源时，其初值只能为 1，和进程数无关。另外，信号量只能通过 P、V 操作才能改变其值。注意互斥信号量与记录型信号量相区别。4.（A）应包括 S.value=0 的情况，由于 S 执行 V 操作后 S.value=0，说明在执行 V操作前其值为-1，即阻塞队列中有一个进程。注意本题和第二题的细微差别。另外，计数信号量即记录型信号量。5.（C）系统中有 n 个进程，其中至少有一个进程正在执行（处理机至少有一个），因此就绪队列中进程个数最多有 n-1 个。B 容易被错选，以为会有处理机为空儿就绪队列全满的情况，实际调度无此状态。二、二、综合题综合题1问题描述：问题描述：问题描述：问题描述：某寺庙，有小和尚和老和尚若干，有一个水缸，由小和尚提水入