当前位置：文档之家 › pv操作的一些习题

pv操作的一些习题

  • 格式：doc
  • 大小：119.50 KB
  • 文档页数：9

下载文档原格式

  / 9

合集下载

操作系统PV操作经典一百题

操作系统PV操作经典一百题
cobegin
procedure reader_i
begin // i=1,2,?.
P(rwmutex); //读者、写者互斥
P(rmutex);
V(rwmutex); // 释放读写互斥信号量，允许其它读、写进程访问资源
读数据；
V(rmutex);
end
procedure Writer_j
我们需要分两种情况实现该问题：
读优先： 要求指一个读者试图进行读操作时，如果这时正有其他读者在进行操作，他可直接开始读操作，而不需要等待。
写优先： 一个读者试图进行读操作时，如果有其他写者在等待进行写操作或正在进行写操作，他要等待该写者完成写操作后才开始读操作。
The P,V code Using Pascal
3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）
如果读者数是固定的，我们可采用下面的算法：
rwmutex：用于写者与其他读者/写者互斥的访问共享数据
rmutex： 该信号量初始值设为10，表示最多允许10个读者进程同时进行读操作
var rwmutex, rmutex ： semaphore := 1, 10 ；
操作系统P V题解
第一章 The P,V Theorem
在操作系统理论中有一个非常重要的概念叫做P,V原语。在我们研究进程间的互斥的时候经常会引入这个概念，将P,V操作方法与加锁的方法相比较，来解决进程间的互斥问题。实际上，他的应用范围很广，他不但可以解决进程管理当中的互斥问题，而且我们还可以利用此方法解决进程同步与进程通信的问题。
Figure 1.1: producer-consumer problem

有关pv操作类的题目

有关pv操作类的题目

有关pv操作类的题目1、假定系统有三个并发进程read, move和print共享缓冲器B1和B2。

进程read负责从输入设备上读信息，每读出一个记录后把它存放到缓冲器B1中。

进程move从缓冲器B1中取出一记录，加工后存入缓冲器B2。

进程print将B2中的记录取出打印输出。

缓冲器B1和B2每次只能存放一个记录。

要求三个进程协调完成任务，使打印出来的与读入的记录的个数，次序完全一样。

请用PV操作，写出它们的并发程序。

解：beginemptyB1 , fullB1, emptyB2, fullB2 : semaphoreB1,B2 : recordemptyB1 := 1,fullB1:=0,emptyB2:=1,fullB2:=0cobegin process readX : record;begin R: 接收来自输入设备上一个记录X:=接收的一个记录；P(emptyB1)；B1:=X;V(fullB1);goto R;end;Process moveY:record;beginM:P(fullB1);Y:=B1;V(emptyB1)加工YP(emptyB2)；B2:=Y;V(fullB2);goto M;end;Process printZ:record;beginP:P(fullB2);Z:=B2;V(emptyB2)打印Zgoto P;end;coend;end;2、用PV操作解决读者写者问题的正确程序如下：begin S, Sr: Semaphore; rc: integer;S:=1; Sr:=1; rc:=0;cobegin PROCESS Reader i ( i=1,2…)begin ( P(S5))P(Sr)rc:=rc+1;if rc=1 then P(S);V(Sr);read file;P(Sr);rc:=rc-1if rc=0 thenV(S);V(Sr);( V(S5) )end ;PROCESS Writer j (j=1,2…)begin P(S);Write file;V(S)end;coend ;end;请回答：（1）信号量Sr的作用；（2）程序中什么语句用于读写互斥，写写互斥；（3）若规定仅允许5个进程同时读怎样修改程序？解：（1）Sr用于读者计数变量rc的互斥信号量；（2）if rc=1 then P（S）中的P（S）用于读写互斥；写者进程中的P（S）用于写写互斥，读写互斥。

pv操作的一些习题

pv操作的一些习题
分析：本题需设置4个信号量，其中empty表示还可以向盘中放几个水果，其初值为2；apple对应已放入盘中的苹果，orange对应已放入盘中的橘子，它们的初值均为0；mutex用来实现对盘子的互斥访问，其初值为1。
Main(0
Cobegin{
Father()
{while(1)
{p(empty);
P(mutex);
1、进程P0和P1的共享变量定义及其初值为：
boolean falg[2];
int turn=0;fal[0]=FALSE; falg[1]=FALSE;
若进程P0和P1访问临界资源的类C伪代码实现如下：
则并发执行进程P0和P1时产生的情形是【全国联考2010】
A.不能保证进程互斥进入临界区、会出现“饥饿”现象
答案：设置6个信号量full1、empty1、B-M1、full2、empty2、B-M2，它们的含义和初值如下：
1)full1表示Buff1是否有数据，初值为0；
2)empty1表示Buff1有空间，初值为m；
3)B-M1表示Buff1是否可操作，初值为1；
4)Full2表示Buff2是否有数据，初值为0；
5)Empty2表示Buff2有空间，初值为n；
6)B-M2表示Buff2是否可操作，初值为1；
<PUT类进程>
{
repeat
P(empty1)；/*判断Buff1是否有空间，没有则等待*/
P(B-M1)；/*是否可操作Buff1*/
PUT；
V(B-M1)；/*设置Buff1可操作标志*/
V(full1)；/*设置Buff1有数据的标志*/
GET；
V(B-M2)；/*设置Buff2可操作标志*/

操作系统PV操作习题.

操作系统PV操作习题.

一、用P、V操作描述前趋关系。

P1、P2、P3、P4、P5、P6为一组合作进程，其前趋图如图2．3所示，试用P、V 操作描述这6个进程的同步。

p23图2．3说明任务启动后P1先执行，当它结束后P2、P3可以开始执行，P2完成后P4、P5可以开始执行，仅当P3、P4、P5都执行完后，P6才能开始执行。

为了确保这一执行顺序，设置5个同步信号量n、摄、f3、f4、g分别表示进程P1、P2、P3、P4、P5是否执行完成，其初值均为0。

这6个进程的同步描述如下：图2．3 描述进程执行先后次序的前趋图int f1=0; /*表示进程P1是否执行完成*／int f2=0; /*表示进程P2是否执行完成*／int f3=0; /*表示进程P3是否执行完成*／int f4=0; /*表示进程P4是否执行完成*／int f5=0; /*表示进程P5是否执行完成*／main(){cobeginP1( );P2( );P3( );P4( );P5( );P6( );coend}P1 ( ){┇v(f1);v(f1)：}P2 ( ){p(f1);┇v(f2);v(f2);)P3 ( ){p(f1);┇v(f3);}P4( ){p(f2);┇v(f4);}P5 ( ){p(f2);┇v(f5);}P6( ){p(f3);p(f4);p(f5);┇}二、生产者-消费者问题p25生产者-消费者问题是最著名的进程同步问题。

它描述了一组生产者向一组消费者提供产品，它们共享一个有界缓冲区，生产者向其中投放产品，消费者从中取得产品。

生产者-消费者问题是许多相互合作进程的一种抽象。

例如，在输入时，输入进程是生产者，计算进程是消费者;在输出时，计算进程是生产者，打印进程是消费者。

因此，该问题具有很大实用价值。

我们把一个长度为n的有界缓冲区(n>0)与一群生产者进程P１、P２、…、Pm和一群消费者进程C１、C２、…、Ck 联系起来，如图2．4所示。

操作系统PV操作经典例题与答案

操作系统PV操作经典例题与答案

操作系统PV操作经典例题与答案1. 推广例子中的消息缓冲问题。

消息缓冲区为k个，有1个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次若有m个发送进程呢？Send：SB=k; //信号量，标记当前空余缓冲区资源。

i = 0; //标记存放消息的缓冲区位置while (true) {P(SB);往Buffer [i]放消息;V(SM);i = (i+1) % k;};Receive：j = 0; //标记取产品的缓存区位置SM=0；//信号量，标记初始没有消息ReadCount=0；//读进程计数器Mutex =1；//读进程互斥信号量SW=0; //信号量，读进程在此信号量等待while (true) {P(SM);从Buffer[j]取消息;ReadCount++If（ReadCount<n）{< p="">V(SM);P(SW)}else{V(SB);j = (j+1) % k;for(int g=1; g< ReadCount;g++)V(SW);ReadCount=0；}};2.第二类读者写者问题：写者优先条件：1）多个读者可以同时进行读2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）rc=0, //正在读者计数器wc, //写计数器rw, //读等计数器R //等待读信号量W //等待写信号量读者：while (true) {P(mutex);if (wc >0){rw++P (R);}rc++;If（rw>0&&wc=0）{V(R)rw--}V(mutex);读P(mutex);rc --;if (rc==0){If（wc>0）V(w)}V(mutex);};写者：while (true) {P(mutex);wc ++;if((wc >1)||(rc>0)){P(W)}V(mutex);写P(mutex);Wc --;if（wc>0）V(W);Else if(rw>0)V(R)rw--V(mutex);};3.理发师睡觉问题理发店里有一位理发师，一把理发椅和N把供等候理发的顾客坐的椅子如果没有顾客,则理发师便在理发椅上睡觉。

PV操作题

PV操作题

PV操作题1.独木桥问题：若规定同一方向的人可连续过桥，但同时在桥上人数最多4人，当某方向无人过桥后，另一方向的人才能过桥．请用ＰＶ操作模拟实现．2.独木桥问题：若规定同一方向的人可连续过桥最多10人，当某方向连续通过达到10人后，另一方向的人才能过桥．请用ＰＶ操作模拟实现．3.类似题目：车辆过单行隧道，火车过单行轨道4．有一阅览室只能容纳100人(每人一个座位)，读者进入时必须先在一张登记表上登记一个座位，离开时要销掉登记内容。

请用PV机制描述读者进程的同步关系。

5．超市购物过程：共有100个购物篮，每人进入取一个篮子购物，出去结帐并归还篮子。

出入口共用一个通道。

6．地下停车场车位管理。

（共100个车位）7．某银行最多只允许容纳N个储户办理业务，如果此时银行只有一个柜员，将此柜员和储户的行为看成两个不同进程，请用PV操作模拟上述过程。

其中储户取号等待叫号，若叫到则到柜员处办理业务，结束自行离开；柜员按顺序叫号并为储户办理业务，若N个号已取完需结束当前业务后才能让后来者取号8. 某银行最多只允许容纳N个储户办理业务，如果此时银行有M个柜员，将此柜员和储户的行为看成两个不同进程，请用PV操作模拟上述过程。

其中储户取号等待叫号，若叫到则到柜员处办理业务，结束自行离开；柜员按顺序叫号并为储户办理业务，若N个号已取完需结束当前业务后才能让后来者取号，但是柜员间叫号是互斥的9.有个师傅和三个徒弟，徒弟不断组装产品，做一个产品需要A,B,C 三种零件(分别被三个徒弟掌握)，师傅不断提供上述三种零件，但每次只能将其中两种放到桌上，具有另一种零件的徒弟则组装产品，且做完后向师傅发信号，然后师傅再拿出两种零件放到桌上，如此反复，请用PV操作模拟上述活动。

10.书本上司机和售票员问题后续内容继续更新中……。

pv操作习题

pv操作习题
signal(mutex);
signal(sa);
signal(s);
}
Process_B:
while (1)
{
wait(s2);
produce a product B；
signal(s1);
wait(mutex);
add the product B to the storehouse;
signal(mutex);
if Counteast = 0 then P( S ) ;
Counteast : = Counteast + l ;
V( Scounteast ) ;
P( Scount4 ) ;
上桥：过桥：下桥；
V ( Scount4 ) ;
P ( Scounteast ) ;
Counteast: = Counteast - 1 ;
{
Wait(S_CartNum);
买东西；
结帐；
Signal(S_CartNum);
}
桌子上有一个水果盘，每一次可以往里面放入一个水果。爸爸专向盘子中放苹果，儿子专等吃盘子中的苹果。把爸爸、儿子看作二个进程，试用Wait/Signal操作使这四个进程能正确地并发执行。
semaphore S_PlateNum;//盘子容量，初值为1
Var s: semaphore :=1;
begin
parbegin
process Pi: begin
repeat
Wait (s);
按旅客定票要求找到Rk
if Rk>=1 then begin
Rk=Rk-1;
Signal (s);
输出一张票；
end;
else begin

典型例题PV操作

典型例题PV操作
试写出读者“进入”和“注销”之间的同步算法。
答：读者的动作有两个，一是填表进入阅览室读书，这时要考虑阅览室里是否有座位；二是读者阅读完毕，需要注销登记再离开阅览室，这时的操作要考虑阅览室里是否有读者存在。读者在阅览室读书时，由于没有引起资源的变动，不算动作变化。
因此，设置算法所涉及的三个信号量：empty资源信号量——表示阅览室里的空座位的数目，初值为100；full资源信号量——表示阅览室里有人的座位的数目（或表示阅览室里的读者的数目），初值为0；mutex互斥信号量——表示对登记表这个临界资源的互斥访问，初值设为1。
使用信号量机制对读者“进入”阅览室和“注销”登记之间的同步算法描述如下：
Semaphoreempty,full,mutex;//首先定义两个资源信号量empty、full和一个互斥信号量mutex
empty.value=100;full.value=0;mutex.value=1;
cobegin
process getin() //读者“进入”阅览室的进程过木桥；wait(SB);
countB:=countB-1;
if (countB=0) then signal(mutex);
signa(SB);
end
parend
end
2、有一阅览室，共有100个座位。为了很好利用它，读者进入时必须先在登记表上进行登记。该表表目设有座位号和读者姓名；离开时再将其登记项摈除。试用P、V操作描述进程之间的同步或算法。
Var SA,SB,mutex:semaphore:=1,1,1;
CountA,countB:integer:=0,0:
begin
parbegin
processA: begin

pv操作的一些习题

pv操作的一些习题

操作系统P V题解第一章The P,V Theorem在操作系统理论中有一个非常重要的概念叫做P,V原语。

在我们研究进程间的互斥的时候经常会引入这个概念，将P,V操作方法与加锁的方法相比较，来解决进程间的互斥问题。

实际上，他的应用范围很广，他不但可以解决进程管理当中的互斥问题，而且我们还可以利用此方法解决进程同步与进程通信的问题。

一Introduction of P,V Theorem阐述P,V原语的理论不得不提到的一个人便是赫赫有名的荷兰科学家E.W.Dijkstra。

如果你对这位科学家没有什么印象的话，提起解决图论中最短路径问题的Dijkstra算法应当是我们再熟悉不过的。

P,V原语的概念以及P,V操作当中需要使用到的信号量的概念都是由他在1965年提出的。

1 Some Conceptions信号量是最早出现的用来解决进程同步与互斥问题的机制，包括一个称为信号量的变量及对它进行的两个原语操作。

信号量为一个整数，我们设这个信号量为：S。

很显然，我们规定在S大于等于零的时候代表可供并发进程使用的资源实体数，S小于零的时候，表示正在等待使用临界区的进程的个数。

根据这个原则，在给信号量附初值的时候，我们显然就要设初值大于零。

p操作和v操作是不可中断的程序段，称为原语。

P,V原语中P是荷兰语的Passeren，相当于英文的pass,V是荷兰语的Verhoog,相当于英文中的incremnet。

P原语操作的动作是：（1）S减1；（2）若S减1后仍大于或等于零，则进程继续执行；（3）若S减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。

V原语操作的动作是：（1）S加1；（2）若相加结果大于零，则进程继续执行；（3）若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。

需要提醒大家的是：P,V操作首先是一个原语操作，对于每一个进程来说，都只能进行一次。

操作系统_PV操作_经典习题1

操作系统_PV操作_经典习题1

1、司机-售票员问题
2、理发师问题
理发店里有一位理发师，一把理发椅和N把供等候理发的顾客坐的椅子。

如果没有顾客，则理发师便在理发椅上睡觉。

当一个顾客到来时，他必须先唤醒理发师。

如果顾客到来时理发师正在理发，则如果有空椅子，可坐下来等；否则离开。

3、物流问题
在某个物流系统中，有一个位于上海的集装箱中转枢纽，这些集装箱又被装上其他运输工具继续各自的行程。

根据整体物流规划，从沿长江一线进入枢纽的集装箱，要从这里直接吊装到上
海至旧金山的定期集装箱班轮上。

而从沪杭高速公路进入枢纽的集装箱，要从这里换装到专门在京沪高速公路上行驶的集装箱运输车上。

现在需要设计为该物流系统上海集装箱中转枢纽使用的物流软件，为简化问题，假设该中转枢纽的场地每次只能接收一个方向来的同一批次的集装箱。

习题PV操作

习题PV操作

使用信号量解决吃水果问题2 使用信号量解决吃水果问题
分析：四人之间的关系： 分析：四人之间的关系： 1父亲，母亲要互斥使用盘子，所以两者之间是互斥关系； 父亲， 父亲 母亲要互斥使用盘子，所以两者之间是互斥关系； 2父亲放的苹果，女儿吃，所以两者是同步关系； 父亲放的苹果， 父亲放的苹果 女儿吃，所以两者是同步关系； 3母亲放的桔子，儿子吃，所以两者也是同步关系。 母亲放的桔子， 母亲放的桔子 儿子吃，所以两者也是同步关系。 semaphore S_Plate=1, S_Apple=0, S_Orange=0; void son( ) // 儿子进程 { while(1) { P(S_Orange); 桔子； 从盘中取出一个 桔子； V(S_Plate); 吃桔子； 吃桔子； } } void daughter( ) // 女子进程 { while(1) { P(S_Apple); 苹果； 从盘中取出一个 苹果； V(S_Plate号量解决吃水果问题
分析：四人之间的关系： 分析：四人之间的关系： 1父亲、母亲要互斥使用盘子，所以两者之间是互斥关系； 父亲、 父亲 母亲要互斥使用盘子，所以两者之间是互斥关系； 2父亲放的苹果，女儿吃，所以两者是同步关系； 父亲放的苹果， 父亲放的苹果 女儿吃，所以两者是同步关系； 3母亲放的桔子，儿子吃，所以两者也是同步关系。 母亲放的桔子， 母亲放的桔子 儿子吃，所以两者也是同步关系。 semaphore S_Plate=1, S_Apple=0, S_Orange=0; void father( ) // 父亲进程 { while(1) { P(S_Plate); 往盘子中放入一个苹果； 往盘子中放入一个苹果； V(S_Apple); } } void mother( ) // 母亲进程 { while(1) { P(S_Plate); 往盘子中放入一个桔子； 往盘子中放入一个桔子； V(S_Orange); } }

pv操作练习题

pv操作练习题

用P，V操作实现下述问题的解。

一、桌上有一个盘子，可以放一个水果；父亲总是放苹果到盘子中；母亲总是放香蕉到盘子中。

一个儿子专等吃盘中的香蕉，而一个女儿专等吃盘中的苹果。

父母只放水果不吃，儿女只吃水果不放。

实现父亲，母亲，儿子，女儿的进程同步。

二、在公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆，正常行车，到站停车。

售票员的活动：上下乘客，关车门，售票，开车门，上下乘客。

在汽车不停的到站，停站，行驶过程中，这两个活动有什么同步关系？用信号量和P，V操作实现它们的同步。

三、某寺庙，有小，老和尚若干，有一个水缸，有小和尚提水入缸供老和尚饮用。

水缸可以放10桶水，水从一个井里面提。

水井狭窄，每次只能容纳一个桶取水。

水桶总数为3个。

每次入、取缸水只能是1桶，且不可以同时进行。

试给出取水，入水的算法描述。

四、一个快餐厅有4类职员：（1）领班：接受顾客点菜，出菜单；（2）厨师：根据菜单，准备顾客的饭菜；（3）打包工：将做好的饭菜打包；（4）出纳员：收款并提交食品。

每个职员可被看作一个进程，试用一种同步机制写出能让四类职员正确并发运行的程序。

五、假设有一个作业由四个进程组成，这四个进程在运行时必须按如图所示的次序依次执行，试用P,V原语表达四个进程的同步关系：六、观察者和报告者是两个并发执行的进程，观察者不断观察并对通过的卡车计数，报告者定时的将观察者的计数值打印，打印完毕，将计数值清零。

七、假定阅览室最多可同时容纳100个人阅读，读者进入时，必须在阅览室门口的一个登记表上登记，内容包括姓名、座号等，离开时要撤掉登记内容。

用P、V操作描述读者进程的同步算法。

PV习题

PV习题

1、有一个报箱为A、B两人共同使用，每次只能装一份报纸。

A订阅《科技报》，B 订阅《新民晚报》，投递员C、D分属科技报社和新民晚报社，试用P、V操作写出他们的同步执行程序。

var s,science,night:semaphore:=1,0,0;beginparbeginA: begin while(true) C: begin while(true){ wait(science); { wait(s);取科技报; 投递科技报;signal(s); signal(science);} }end; end;B: begin while(true) D: begin while(true){wait(night); {wait(s);取新民晚报; 投递新民晚报;signal(s); signal(night);} }end; end;parend;end.2、设有两个优先级相同的进程P1和P2如下。

信号量S1和S2的初值均为0，试问P1、P2并发执行后，x、y、z的值各是多少？请写出判断的过程。

进程P1：进程P2：y=1; x=1;y=y+2; x=x+1;V(S1); P(S1);z=y+1; x=x+y;P(S2); V(S2);y=z+y; z=x+z;并发进程P1、P2中各语句执行的前趋图为：3的执行8可以并发执行：（17，z的值为9。

（212，z的值为9。

varmutex : semaphere;信号量，用于互斥full : semaphere; 信号量，用于同步table : array 0..n-1 of item; 登记表procedure reader; 读者进程beginP(full);P(mutex);Register_name(table)；V(mutex);Reading；P(mutex);Delet_name(table);V(mutex);V(full)end;beginseminitsal(mutex.v,1; full.v,100); 初始化cobeginreader;reader;...coendend.司机的活动：启动车辆，正常行车，到站停车。

pv操作例题

pv操作例题
P1、P2、P3、P4为具有同步关系的四个进 程，要求P1运行结束后P2和P3才能运行， 但P2和P3之间没有先后顺序关系，P2和P3 均运行结束后，P4才能运行。利用P、V操 作实现上述同步关系。
Type def semaphore; Semaphore s1=s2=s3=s4=0; PROC P1 执行P1的操作； V（S1）； V（S2）；
process p2 begin repeat p(s2); read A; v(s1); until false end
coend end
设P1为司机进程，它的任务是：启动、行驶、停车； P2为售票员进程，它的任务是：关门、售票、开门。用 P，V操作写出保证P1，P2安全运行的同步算法。
begin close,stop:semaphore; close:=0; stop:=0; cobegin
PROC P2 P(S1); 执行P2的操作； V（S3）；
PROC P3 P（S2）； 执行P3的操作； V（S4）；
PROC P4 P（S3）; P（S4）； 执行P4的操作
P1、P2、P3、P4为具有合作关系的四个进程，P1执行 三个计算操作并将结果分别存入X、Y、Z变量，P1运行 结束后，P2、P3和P4分别计算X、Y、Z变量的平方值 并将结果存入原变量。利用P、V操作实现上述进程间 的同步关系。
process P2 begin P（S1）； 执行工序2； V（S2）； end；
process P3 begin P（S2）； 执行工序3； end； Coend end
设P1、P2、P3为3个相互合作的进程，P1和P2各自从 外部设备读取数据分别存入X变量和Y变量，P3进程将X、 Y的值相加并将结果存入Z变量。试用P、V操作实现上 述同步关系。

pv操作典型例题

pv操作典型例题

例1 在某展示厅设置一个自动计数系统，以计数器count表示在场的人数，count是动态变化的，若有一个人进入展示厅进程pin对计数器count加1，当有一个人退出展示厅时，进程pout实现计数器减1。

由于进、出所以展示厅的人是随机的，用P-V操作实现。

（并发进程之间的互斥问题）解：定义信号量：S——表示是否有进程进入临界区，初值为1.（表示没有进程进入临界区）begincount: Integer;S: semaphore;count:=0;S:=1;cobeginprocess PinR1: Integer;beginP (S);R1:=count;R1:=R1+1;count:=R1;V(S);end;Process PoutR2: Integer;beginP (S);R2:=count;R2:=R2-1;count:=R2;V (S);end;count;end;例2 与生产者和消费过者相似的问题，把“A进程将记录送入缓冲器”看生产者生产了一件物品且把物品存入缓冲器，把“B进程从缓冲器中取出记录并加工”看作是消费者从缓冲器取出物品去消费，缓冲器中只能放一个记录（一件物品），用P-V操作实现。

（并发进程之间的同步问题）解：定义两个信号量为：sp和sg。

sp:表示生产者是否右以把物品存入缓冲器。

由于缓冲器只能存放一个物品，因此sp的初值为1，即sp:=1。

sg：表示缓冲是否存有物品，它的初值应该为0，即sg：=0，表示缓冲器中还没有物品存在。

生产者和消费者两个进程并发执行时，可按以下的方式实现同步：sp:=1;sg:=0;cobeginprocess producer (生产者进程)beginL1:produce a product;P(sp);Buffer:=product;V(sg);goto L1endprocess consumer(消费者进程)beginL2: P(sg);Take a product;V(sp);consume;goto L1end;coend;例3 如果一个生产者和一个消费共享缓冲器容量为可以存放n件物品时，生产者总可继续存入物品；同时当缓冲器的物品不为“0”时，消费者总可从缓冲器中取走物品，用P-V操作实现。

PV学习例题

PV学习例题

某条河上只有一个独木桥，以便行人过河。现在河的两边 都有人要过桥，若把过桥者看做一个进程，规定： 每次只 有一个人通过。为了保证过桥安全，请用P、V操作分别实 现正确的管理。 void main()
const int n = 进程数； Semaphore mutex = 1; void Process_EW( int i) { while ( true) { P(mutex); <临界区> V(mutex) <其余部分> // signal(s) // wait(s)

要求：“读－写” 互斥；“写－写” 互斥；“读－读” 允许

Wsem :用于互斥，只要一个写进程正在访问共享数据区， 其他的写进程和读进程都不能访问它。 Readcount：用于记录读进程的数目 信号量X用于确保readcount被正确更新。（互斥）
读/写问题 读进程具有优先权
Coend
}
5.6 经典同步问题
生产者/消费者问题

读写者问题 哲学家问题
例1、 生产者/消费者问题
(the producer/consumer problem)
（1）有一群生产者进程在生产消息,
并将消息提供给消 费者进程去消费。为使生产者进程和消费者进程能并发执 行, 在它们之间设置了一个具有n个缓冲区的缓冲池, 生产 者进程可将它所生产的消息放入一个缓冲区中, 消费者进 程可从一个缓冲区中取得一个消息消费。 （2）尽管所有的生产者进程和消费者进程都以异步方式 运行, 但它们之间必须保持同步, 即不允许消费进程者到 一个空缓冲区去取消息, 也不允许生产者进程向一个已装 有消息且尚未被取走消息的缓冲区中投放消息。 （3）任何时刻只能有一个进程可对共享缓冲区进行操作

PV操作的例题

PV操作的例题

PV操作的例题PV操作的例题一、线程是进程的一个组成部分，一个进程可以有多个线程，而且至少有一个可执行线程。

进程的多个线程都在进程的地址空间内活动。

资源是分给进程的，而不是分给线程的，线程需要资源时，系统从进程的资源配额中扣除并分配给它。

处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程。

线程在执行过程中，需要同步。

二、在计算机操作系统中，PV操作是进程管理中的难点。

首先应弄清PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：P（S）：①将信号量S的值减1，即S=S-1；②如果S>=0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。

V（S）：①将信号量S的值加1，即S=S+1；②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。

PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。

PV操作属于进程的低级通信。

什么是信号量？信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。

信号量的值与相应资源的使用情况有关。

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

注意，信号量的值仅能由PV操作来改变。

一般来说，信号量S>=0时，S表示可用资源的数量。

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

而执行一个V操作意味着释放一个单位资源，因此S 的值加1；若S?0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。

利用信号量和PV操作实现进程互斥的一般模型是：进程P1 进程P2 ……进程Pn………………P（S）；P（S）；P（S）；临界区；临界区；临界区；V（S）；V（S）；V（S）；……………………其中信号量S用于互斥，初值为1。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
填写登记表;
v(mutex);
进入阅览室阅读;
end
end
procedureLeave
begin
while(TRUE)
begin
p(mutex);
消掉登记;
v(mutex);
process1//只有随身听
begin
repeat
P(S1);
购买物品；听乐曲；
V(S);
untilefalse;
end
process2//只有磁带
begin
repeat
p(S2);
购买物品；听乐曲；
V(S);
untilefalse;
end
process3//只有电池
begin
repeat
P(S3);
【分析】顾客相当于生产者，柜员相当于消费者，所有顾客领取号码后就进入了一个等待队列，该等待队列相当于buffer。这个问题基本符合一般意义的“生产者—消费者”问题，但又有所不同，不同在于顾客（即生产者）“取号进入等待队列”操作不需要与柜员（消费者）同步（不需等待空的缓冲区）。
只需要两个信号量即可，一个用于互斥访问等待队列（对于顾客，就是互斥使用柜员机取号；对于柜员，就是叫号时候互斥访问等待队列），一个用于柜员“叫号”操作与顾客的同步（需测试是否有人在等）。
Var mutex=1,customer_count=0:semaphore;
Cobegin
process customer
begin
repeat
p(mutex);
取号码，进入队列；
v(mutex);
v(customer_count);
untilefalse;
end
process serversi(i=1,...,n)
begin
repeat
p(customer_count);
p(mutex);
从队列中取下一个号码；
v(mutex);
为该号码持有者服务；
untilefalse;
end
Coend
4、有一阅览室，读者进入时必须先在一张登记表上登记。该表中每个表项代表阅览室中的一个座位。读者离开时要消掉其登记信息。阅览室共有50个座位。登记表每次仅允许一位读者进行登记或注销。读者登记时，发现登记表满，他在阅览室外等待，直至有空位再登记进入。试用类Pascal语言和P、V操作，描述读者行为。【国防科技大学2000】(注：【南昌大学2002】类似)
答：信号量seats：表示可用座位数，初值为50；
信号量mutex：表示登记表是否正在使用，初值为1；
varseats,mutex:semaphore;
seats:=50;
mutex:=1;
cobegin
procedureEnter
begin
while(TRUE)
begin
p(seats);
p(mutex);
“饥饿”出现的时机：使用忙等待实现互斥，当一个进程离开临界区时，如果有多个进程等待进入临界区，系统会随机选择一个进程执行，因为这种随机性，会导致有些进程长期得不到执行，因而导致“饥饿”。
本题中，如果P1已经等在while上的时候，P0至多执行一次临界区，否则下次执行的时候，即便它在P1测试条件前出了临界区并重新设定了flag，但由于它必须要设定turn=1（此时P1不会再设置turn了），因此这样P0必然卡在while上，从而换到P1执行。所以不会出现“饥饿”现象。
processprovider
begin
repeat
flag1:=flag2:=flag3:=False;
取两种物品，设置flagi为True;
ifflag2&flag3thenV(S1);
elseifflag1&flag3thenV(S2);
elseV(S3);
P(S);
untilefalse;
end
分析：同步信号量S表示是否听完乐曲，初值为0；
资源信号量S1、S2、S3表示两种物品组合起来的临界资源，初值均为0。
VarS,S1,S2,S3:semaphore;
Varflag1,flag2,flag3:Boolean;//依次代表随身听、磁带和电池
S:=0;
S1:=S2:=S3:=0;
Cobegin
购买物品；听乐曲；
V(S);
untilefalse;
end
Coend
3、某银行有人民币储蓄业务，由n个柜员负责，有1台取号机。每个顾客进入银行后先取一个号，若有人取号则需等他人取完后才能取，取到号后等待叫号，当一个柜员人员空闲下来，就叫下一个号。试用P，V操作正确编写柜台人员和顾客进程的程序。【昆明理工大学2006】
B.不能保证进程互斥进入临界区、不会出现“饥饿”现象
C.能保证进程互斥进入临界区、会出现“饥饿”现象
D.能保证进程互斥进入临界区、不会出现“饥饿”现象
分析进程的执行过程：一开始，没有进程处于临界区中，现在进程P0开始执行，通过设置其数组元素和将turn置1来标识它希望进入临界区，由于进程P1并不想进入临界区，所以P0跳出while循环，进入临界区。如果进程P1现在开始执行，进程P1将阻塞在while循环直到flag[0]变为false，而该事件只有进程P0退出临界区时才会发生。
现在考虑两个进程几乎同时执行到while循环的情况，它们分别在turn中存入1和0，但只有后被保存进去的进程号才有效，前一个被重写而丢失。假设进程P1是后存入的，则turn为0。进程P0将循环0次而进入临界区，而进程P1则将不停地循环且不能进入临界区，直到进程退出临界区为止。
因此，该算法实现了临界区互斥。
2、在一间酒吧里有三个音乐爱好者队列，第一个音乐爱好者只有随身听，第二个只有音乐带和电池这三中物品。酒吧老板一次出售这三种物品中的任意两种，当一名音乐爱好者得到这三种物品并听完乐曲后，酒吧老板才能再一次出售这三种物品中任意两种，于是第二名音乐爱好者得到这三种物品。并开始听乐曲，全部买卖就这样进行下去。使用P，V操作正确解决这一买卖。【北京大学1999】
1、进程P0和P1的共享变量定义及其初值为：
boolean falg[2];
int turn=0;
falg[0]=FALSE; falg[1]=FALSE;
若进程P0和P1访问临界资源的类C伪代码实现如下：
则并发执行进程P0和P1时产生的情形是【全国联考2010】
A.不能保证进程互斥进入临界区、会出现“饥饿”现象