当前位置:文档之家› 进程同步与互斥汇总

进程同步与互斥汇总

进程同步与互斥进程的PV操作在操作系统中,P、V操作是进程管理中的难点。

这是1968年荷兰人Dijkstra 给出的一种解决并发进程间互斥和同步关系的通用方法。

1. P、V操作的意义定义了信号量及其上的P操作和V操作,来实现并发进程间的同步和互斥,甚至可以用来管理资源的分配。

P、V操作因交换的信息量少,属于进程的低级通信。

2. 什么是信号量?信号量(semaphore)是由一个值和一个指针构成的数据结构。

值为整型变量,表示信息量的值;指针指向进程控制块(PCB)队列的队头,表示等待该信号量的下一个进程。

如下图所示。

信号量的一般结构及PCB队列信号量的值与相应资源的使用情况有关。

当它的值大于0时,表示当前可用资源的数量;当它的值小于0时,其绝对值表示等待使用该资源的进程个数。

注意,信号量的初值不能为负,且其值只能由P、V操作来改变。

3. P、V操作的含义P、V操作由P操作原语和V操作原语组成(原语是不可中断的过程),对信号量S进行操作,具体定义如下:P(S):①将信号量S的值减1,即S=S-1;②如果S≥0,则该进程继续执行;否则该进程状态置为阻塞状态,进程PCB 排入信号量PCB队列末尾,放弃CPU,等待V操作的执行。

V(S):①将信号量S的值加1,即S=S+1;②如果S≤0,释放信号量队列中第一个PCB所对应的进程,将进程状态由阻塞态改为就绪态。

执行V操作的进程继续执行。

一般来说,信号量S≥0时,S表示可用资源的数量。

执行一次P操作意味着请求分配一个单位资源,因此S的值减1;当S<0时,表示已经没有可用资源,请求者必须等待别的进程释放该类资源,它才能运行下去。

而执行一个V操作意味着释放一个单位资源,因此S的值加1;若S≤0,表示有某些进程正在等待该资源,因此要唤醒一个阻塞状态的进程,使之成为就绪状态。

4. 利用信号量和P、V操作实现进程互斥一般地,n个进程利用信号量和P、V操作实现进程互斥的一般模型如下:进程P1进程P2……进程Pn…… …… ……P(S); P(S); P(S);临界区;临界区;临界区;V(S); V(S); V(S);…… …… …… ……其中S是互斥信号量,初值为1。

使用P、V操作实现进程互斥时应该注意的问题是:(1)每个程序中,用户实现互斥的P、V操作必须成对出现,先做P操作,进临界区,后做V操作,出临界区。

若有多个分支,要认真检查P、V操作的成对性。

(2)P、V操作应分别紧靠临界区的头尾部,临界区的代码应尽可能短,不能有死循环。

(3)互斥信号量的初值一般为1。

由于用于互斥的信号量sem与所有的并发进程有关,所以称之为公有信号量。

公有信号量的值反映了公有资源的数量。

只要把临界区置于P(sem)和V(sem)之间,即可实现进程间的互斥。

就象火车中的每节车厢只有一个卫生间,该车厢的所有旅客共享这个公有资源:卫生间,所以旅客间必须互斥进入卫生间,只要把卫生间放在P(sem)和V(sem)之间,就可以到达互斥的效果。

以下例子说明进程的互斥实现。

例1生产围棋的工人不小心把相等数量的黑子和白子混装载一个箱子里,现要用自动分拣系统把黑子和白子分开,该系统由两个并发执行的进程组成,功能如下:(1)进程A专门拣黑子,进程B专门拣白子;(2)每个进程每次只拣一个子,当一个进程在拣子时不允许另一个进程去拣子;分析:第一步:确定进程间的关系。

由功能(2)可知进程之间是互斥的关系。

第二步:确定信号量及其值。

由于进程A和进程B要互斥进入箱子去拣棋子,箱子是两个进程的公有资源,所以设置一个信号量s,其值取决于公有资源的数目,由于箱子只有一个,s的初值就设为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名购票者时,厅外的购票者可立即进入,否则需要在外面等待。

每个购票者可看成一个进程。

分析:第一步:确定进程间的关系。

售票厅是各进程共享的公有资源,当售票厅中多于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小于零,则说明售票厅的人数已满不能进入。

这个实现中同时最多允许20个进程进入售票厅购票,其余进程只能等待。

5. 利用信号量和P、V操作实现进程同步P、V操作是典型的进程同步机制之一。

用一个信号量与一个消息联系起来,当信号量的值为0时,表示期望的消息尚未产生;当信号量的值为非0时,表示期望的消息已经存在。

用P、V操作实现进程同步时,调用P操作测试消息是否到达,调用V操作来发送消息。

使用P、V操作实现进程同步时应该注意的问题是:(1)分析进程间的制约关系,确定信号量种类。

在保持进程间有正确的同步关系情况下,哪个进程应先执行,哪些进程后执行,彼此间通过什么信号量进行协调,从而明确要设置哪些信号量。

(2)信号量的初值与相应资源的数量有关,也与P、V操作在程序代码中出现的位置有关。

(3)同一信号量的P、V操作要成对出现,但它们分别在不同的进程代码中。

与进程互斥不同,进程同步时的信号量只与制约进程及被制约进程有关而不是与整组并发进程有关,所以称该信号量为私有信号量。

利用PV原语实现进程同步的方法是:首先判断进程间的关系为同步的,且为各并发进程设置私有信号量,然后为私有信号量赋初值,最后利用PV原语和私有信号量规定各进程的执行顺序。

下面我们将例1增添一个条件,使其成为进程间是同步的。

例3在例1的基础之上再添加一个功能:(3)当一个进程拣了一个棋子(黑子或白子)以后,必让另一个进程拣一个棋子(黑子或白子)。

分析:第一步:确定进程间的关系。

由功能(1)(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:P(s2);拣白子;V(s1);goto L2;end;coend;end;另外一个问题就是P原语是不是一定在V原语的前面?回答是否定的。

下面看一个例子。

例4设在公共汽车上,司机和售票员的活动分别是:司机:启动车辆,正常行车,到站停车。

售票员:上乘客,关车门,售票,开车门,下乘客。

用PV操作对其控制。

分析:第一步:确定进程间的关系。

司机到站停车后,售票员方可工作。

同样,售票员关车门后,司机才能工作。

所以司机与售票员之间是一种同步关系。

第二步:确定信号量及其值。

由于司机与售票员之间要互通消息,司机进程设置一个私有信号量run,用于判断司机能否进行工作,初值为0。

售票员进程设置一个私有信号量stop,用于判断是否停车,售票员是否能够开车门,初值为0。

实现:begin stop ,run:semaphorestop:=0;run:=0;cobegindriver: begin消费者进程 while(True){ P(full); 从Buffer 取出一个产品; V(empty); 消费该产品; } L1: P(run);启动车辆;正常行车;到站停车;V(stop);goto L1;end;conductor:beginL2:上乘客;关车门;V(run);售票;P(stop);开车门;下乘客;goto L2;end;coend;end;用PV 操作还可以实现进程同步与互斥的混合问题,典型的如:多个生产者和多个消费者共享容量为n 的缓存区。

这个例子在很多书中都有介绍,在这里就不说了。

6. P 、V 操作举例【例1】生产者-消费者问题在多道程序环境下,进程同步是一个十分重要又令人感兴趣的问题,而生产者-消费者问题是其中一个有代表性的进程同步问题。

下面我们给出了各种情况下的生产者-消费者问题,深入地分析和透彻地理解这个例子,对于全面解决操作系统内的同步、互斥问题将有很大帮助。

(1)一个生产者,一个消费者,公用一个缓冲区(Buffer )。

定义两个同步信号量:empty ——表示缓冲区是否为空,初值为1。

full ——表示缓冲区中是否为满,初值为0。

生产者进程while(TRUE){生产一个产品;P(empty);产品送往Buffer;V(full);}(2)一个生产者,一个消费者,公用n 个环形缓冲区。

缓冲区 消费者 生产者消费者进程 while(TRUE){ P(full); 从buffer (out )中取出产品; out=(out+1) mod n ; V(empty); 消费该产品; } 消费者进程 while(TRUE){ P(full); P(mutex2); 从buffer (out )中取出产品; out=(out+1) mod n ; V (mutex2); V(empty); 消费该产品; }定义两个同步信号量:empty ——表示缓冲区是否为空,初值为n 。

full ——表示缓冲区中是否为满,初值为0。

设缓冲区的编号为1~n -1,定义两个指针in 和out ,分别是生产者进程和消费者进程使用的指针,指向下一个可用的缓冲区。

生产者进程 while(TRUE){ 生产一个产品;P(empty);产品送往buffer (in ); in=(in+1) mod n ;V(full); } (3)一组生产者,一组消费者,公用n个环形缓冲区 在这个问题中,不仅生产者与消费者之间要同步,而且各个生产者之间、各个消费者之间还必须互斥地访问缓冲区。

相关主题