进程同步与互斥(9页).doc

《进程同步与互斥(9页).doc》由会员分享，可在线阅读，更多相关《进程同步与互斥(9页).doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-进程同步与互斥-第 9 页进程同步与互斥进程的PV操作在操作系统中，P、V操作是进程管理中的难点。这是1968年荷兰人Dijkstra给出的一种解决并发进程间互斥和同步关系的通用方法。1. P、V操作的意义定义了信号量及其上的P操作和V操作，来实现并发进程间的同步和互斥，甚至可以用来管理资源的分配。P、V操作因交换的信息量少，属于进程的低级通信。2. 什么是信号量？信号量（semaphore）是由一个值和一个指针构成的数据结构。值为整型变量，表示信息量的值；指针指向进程控制块（PCB）队列的队头，表示等待该信号量的下一个进程。如下图所示。信号量的一般结构及PCB队列信号量的值与相应资源的使用

2、情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的初值不能为负，且其值只能由P、V操作来改变。3. P、V操作的含义P、V操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量S进行操作，具体定义如下： P（S）： 将信号量S的值减1，即S=S-1； 如果S0，则该进程继续执行；否则该进程状态置为阻塞状态，进程PCB排入信号量PCB队列末尾，放弃CPU，等待V操作的执行。 V（S）： 将信号量S的值加1，即S=S+1； 如果S0，释放信号量队列中第一个PCB所对应的进程，将进程状态由阻塞态改为就绪态。执行V操作

3、的进程继续执行。 一般来说，信号量S0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S0，表示有某些进程正在等待该资源，因此要唤醒一个阻塞状态的进程，使之成为就绪状态。 4. 利用信号量和P、V操作实现进程互斥一般地，n个进程利用信号量和P、V操作实现进程互斥的一般模型如下：进程P1 进程P2 进程PnP（S）； P（S）； P（S）；临界区； 临界区； 临界区；V（S）； V（S）； V（S）； 其中S是互斥信号量

4、，初值为1。 使用P、V操作实现进程互斥时应该注意的问题是： （1）每个程序中，用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查P、V操作的成对性。 （2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。（3）互斥信号量的初值一般为1。由于用于互斥的信号量sem与所有的并发进程有关，所以称之为公有信号量。公有信号量的值反映了公有资源的数量。只要把临界区置于P(sem)和V(sem)之间，即可实现进程间的互斥。就象火车中的每节车厢只有一个卫生间，该车厢的所有旅客共享这个公有资源：卫生间，所以旅客间必须互斥进入卫生

5、间，只要把卫生间放在P(sem)和V(sem)之间，就可以到达互斥的效果。以下例子说明进程的互斥实现。例1生产围棋的工人不小心把相等数量的黑子和白子混装载一个箱子里，现要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程组成，功能如下：（1）进程A专门拣黑子，进程B专门拣白子；（2）每个进程每次只拣一个子，当一个进程在拣子时不允许另一个进程去拣子；分析：第一步：确定进程间的关系。由功能（2）可知进程之间是互斥的关系。第二步：确定信号量及其值。由于进程A和进程B要互斥进入箱子去拣棋子，箱子是两个进程的公有资源，所以设置一个信号量s，其值取决于公有资源的数目，由于箱子只有一个，s的初值就设

6、为1。实现：begins:semaphore;s:=1;cobeginprocess AbeginL1: P(s);拣黑子；V(s);goto L1;end;process BbeginL2:P(s);拣白子；V(s);goto L2;end;coend;end;判断进程间是否互斥，关键是看进程间是否共享某一公有资源，一个公有资源与一个信号量相对应。确定信号量的值是一个关键点，它代表了可用资源实体数。如下实例：例2某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，厅外的购票者可立即进入，否则需要在外面等待。每个购票者可看成一个进程。分析：第一步：确定进程间的关系。

7、售票厅是各进程共享的公有资源，当售票厅中多于20名购票者时，厅外的购票者需要在外面等待。所以进程间是互斥的关系。第二步：确定信号量及其值。只有一个公有资源：售票厅，所以设置一个信号量s。售票厅最多容纳20个进程，即可用资源实体数为20，s的初值就设为20。实现：begins:semaphore;s:=20;cobeginprocess PI(I=1,2,)begin P(s);进入售票厅；购票；退出；V(s);end;coend 当购票者进入售票厅前要执行P(s)操作，执行后若s大于或等于零，说明售票厅的人数还未满可进入。执行后若s小于零，则说明售票厅的人数已满不能进入。这个实现中同时最多允许

8、20个进程进入售票厅购票，其余进程只能等待。 5. 利用信号量和P、V操作实现进程同步P、V操作是典型的进程同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值为非0时，表示期望的消息已经存在。用P、V操作实现进程同步时，调用P操作测试消息是否到达，调用V操作来发送消息。 使用P、V操作实现进程同步时应该注意的问题是： （1）分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程应先执行，哪些进程后执行，彼此间通过什么信号量进行协调，从而明确要设置哪些信号量。 （2）信号量的初值与相应资源的数量有关，也与P、V操作在

9、程序代码中出现的位置有关。 （3）同一信号量的P、V操作要成对出现，但它们分别在不同的进程代码中。与进程互斥不同，进程同步时的信号量只与制约进程及被制约进程有关而不是与整组并发进程有关，所以称该信号量为私有信号量。利用PV原语实现进程同步的方法是：首先判断进程间的关系为同步的，且为各并发进程设置私有信号量，然后为私有信号量赋初值，最后利用PV原语和私有信号量规定各进程的执行顺序。下面我们将例1增添一个条件，使其成为进程间是同步的。例3在例1的基础之上再添加一个功能：（3）当一个进程拣了一个棋子（黑子或白子）以后，必让另一个进程拣一个棋子（黑子或白子）。分析：第一步：确定进程间的关系。由功能（1

10、）（2）（3）可知，进程间的关系为同步关系。第二步：确定信号量及其值。进程A和B共享箱子这个公有资源，但规定两个进程必须轮流去取不同色的棋子，因而相互间要互通消息。对于进程A可设置一个私有信号量s1，该私有信号量用于判断进程A是否能去拣黑子，初值为1。对于进程B同样设置一个私有信号量s2，该私有信号量用于判断进程B是否能去拣白子，初值为0。当然你也可以设置s1初值为0，s2初值为1。实现:begins1,s2:semaphore;s1:=1;s2:=0;cobeginprocess AbeginL1: P(s1);拣黑子；V(s2);goto L1;end; process BbeginL2:

11、P(s2);拣白子；V(s1);goto L2;end;coend;end;另外一个问题就是P原语是不是一定在V原语的前面？回答是否定的。下面看一个例子。例4设在公共汽车上，司机和售票员的活动分别是：司机：启动车辆，正常行车，到站停车。售票员：上乘客，关车门，售票，开车门，下乘客。用PV操作对其控制。分析：第一步：确定进程间的关系。司机到站停车后，售票员方可工作。同样，售票员关车门后，司机才能工作。所以司机与售票员之间是一种同步关系。第二步：确定信号量及其值。由于司机与售票员之间要互通消息，司机进程设置一个私有信号量run，用于判断司机能否进行工作，初值为0。售票员进程设置一个私有信号量sto

12、p，用于判断是否停车，售票员是否能够开车门，初值为0。实现：begin stop ,run:semaphorestop:=0;run:=0;cobegindriver: beginL1: P(run);启动车辆；正常行车；到站停车； V(stop);goto L1;end;conductor:beginL2:上乘客；关车门；V(run);售票；P(stop);开车门；下乘客；goto L2;end;coend;end;用PV操作还可以实现进程同步与互斥的混合问题，典型的如：多个生产者和多个消费者共享容量为n的缓存区。这个例子在很多书中都有介绍，在这里就不说了。6. P、V操作举例【例1】生产者

13、-消费者问题在多道程序环境下，进程同步是一个十分重要又令人感兴趣的问题，而生产者-消费者问题是其中一个有代表性的进程同步问题。下面我们给出了各种情况下的生产者-消费者问题，深入地分析和透彻地理解这个例子，对于全面解决操作系统内的同步、互斥问题将有很大帮助。（1）一个生产者，一个消费者，公用一个缓冲区（Buffer）。缓冲区消费者生产者定义两个同步信号量：empty表示缓冲区是否为空，初值为1。full表示缓冲区中是否为满，初值为0。生产者进程while(TRUE)生产一个产品; P(empty); 产品送往Buffer; V(full);（2）一个生产者，一个消费者，公用n个环形缓冲区。定义两

14、个同步信号量：empty表示缓冲区是否为空，初值为n。full表示缓冲区中是否为满，初值为0。 设缓冲区的编号为1n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。生产者进程while(TRUE) 生产一个产品; P(empty); 产品送往buffer（in）； in=(in+1) mod n； V(full);（3）一组生产者，一组消费者，公用n个环形缓冲区 在这个问题中，不仅生产者与消费者之间要同步，而且各个生产者之间、各个消费者之间还必须互斥地访问缓冲区。定义四个信号量：empty表示缓冲区是否为空，初值为n。full表示缓冲区中是否为满

15、，初值为0。mutex1生产者之间的互斥信号量，初值为1。mutex2消费者之间的互斥信号量，初值为1。 设缓冲区的编号为1n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。生产者进程while(TRUE) 生产一个产品; P(empty); P(mutex1)； 产品送往buffer（in）； in=(in+1) mod n； V(mutex1); V(full); 需要注意的是无论在生产者进程中还是在消费者进程中，两个P操作的次序不能颠倒。应先执行同步信号量的P操作，然后再执行互斥信号量的P操作，否则可能造成进程死锁。【例2】桌上有一空盘，允

16、许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供取用，请用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。分析 在本题中，爸爸、儿子、女儿共用一个盘子，盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。本题实际上是生产者-消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。 解：在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否

17、为空，其初值为l；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。同步描述如下：int S1;int Sa0;int So0; main() cobegin /*表示并发操作*/ father(); /*父亲进程*/ son(); /*儿子进程*/ daughter(); /*女儿进程*/ coendfather() /*父亲进程*/ while(TRUE) P(S); /*盘子是否为空*/ 将水果放入盘中; if（放入的是桔子）V(So); else V(Sa); son() /*儿子进程*/ while(TRUE) P(So); /*盘中是否有桔子*/

18、从盘中取出桔子; V(S); 吃桔子; daughter() /*女儿进程*/ while(TRUE) P(Sa); /*盘中是否有苹果*/ 从盘中取出苹果; V(S); 吃苹果;说明：P、V操作有很多经典的实例，如生产者-消费者问题、读者-写者问题、哲学家就餐问题、理发店问题等，有兴趣的同学可以通过操作系统的其他教材了解一下。例进程P1、P2、P3、P4、P5的前趋图如下：若用PV操作控制进程并发执行的过程，则需要设置4个信号量S1、S2、S3和S4，且信号量初值都等于零。下图中a和b应分别填写（50），c和d应分别填写（51），e和f应分别填写（52）。（50）A. P（S1）和P（S2）

19、B. P（S1）和V（S2)C. V（S1）和V（S2）D. V（S1）和P（S2）（51）A. P（S1）、P（S2）和V（S3）、V（S4)B. P（S1）、P（S2）和P（S3）、P（S4)C. V（S1）、V（S2）和P（S3）、P（S4)D. V（S1）、V（S2）和V（S3）、V（S4)（52）A. P（S3）和P（S4）B. P（S3）和V（S4)C. V（S3）和V（S4）D. V（S3）和P（S4）分析：什么是前驱图？前驱图是一个有向无循环图,简称DAG (Directed Acyclic Graph).图中每个结点表示一个语句,一段程序或一个进程,从结点Si到结点Sj的有向

20、边表示它们的前趋关系,记为SiSj,即Si和Sj应顺序执行,Sj仅在Si执行完成后才能开始执行。也就是说：进程P3需要等待进程P1和进程P2运行结束之后，才能开始执行。S1用来表示进程P1进程运行结束，需要通知进程P3开始运行；S2用来表示进程P2进程运行结束，需要通知进程P3开始运行；所以说，当P1,P2执行完之后，需要使用V操作；所以a处填写V(S1)，b处填写V(S2)；P3进程开始运行的时候，先做P(S1)和P(S2操作，检查有无需要运行的P1和P2进程，检查有没有P1和P2进程的消息，然后开始运行，所以c处填写P（S1）和P（S2）当P3执行完毕之后，需要使用V操作通知P4和P5，所以d处填写V(S3)和V(S4)e处填写P(S3)，f处填写P(S4)；同样的道理;进程P4和P5执行的时候需要测试P3，P4有没有消息，所以参考答案：（50）C（51）A（52）A