pv操作习题
设一民航售票系统有n个售票处。每个售票处通过终端访问系统中的公用数据区，假定公用数据区中分别用R1、R2、R3、…Rn表示×月×日×次航班的现存票数。设P1、P2、P3、Pn表示各售票处的处理进程，试用信号量实现进程间的互斥关系
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
Signal (s);
输出“票已售完”；
end;
until false;
end
parend
end
生产围棋的工人不小心把相等数量的黑子和白子混装在一个箱子里，现要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程组成，功能如下：
（1）进程A专门拣黑子，进程B专门拣白子；
（2）每个进程每次只拣一个子，当一个进程在拣子时不允许另一个进程去拣子；
s:semaphore:=1;
parbegin
process A：begin
L1: Wait(s);
拣黑子；
Signal(s);
goto L1;
end;
process B：begin
L2:Wait(s);
拣白子；
Signal(s);
goto L2;
end;
parend;
某车站售票厅共有20 个售票窗口，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，厅外的购票者可立即进入，否则需要在外面等待。每个购票者可看成一
个进程。
s:semaphore=20;
parbegin
process Pi(i=1,2,……)
begin Wait(s);
进入售票厅；
购票；
退出；
Signal(s);
end;
parend
有座东西方向架设、可双向通行的单车道简易桥，最大负荷为4 辆汽车。请定义合适的信号量，正确使用wait/signal 操作，实现双向车辆的过桥过程。
信号量应该有4 个：
S ,初值为1,代表桥的互斥使用的信号量；Scounteast,初值为1,代表由东向西行驶的桥上的车辆计数器的互斥使用；
Scountwest,初值为1,代表由西向东行驶的桥上的车辆计数器的互斥使用；
Scount4 ,初值为4,代表桥上车辆的计数信号量。
var S,Scounteast,Scounwest,Scount4:semaphore；
S: = 1；Scounteast＝1；
Scountwest: = 1；Scount4: = 4；
Counteast，Countwest：integer；
Counteast: = 0；Countwest: = 0；
Cobegin ,
process east( i )
begin
P( Scounteast ) ;
if Counteast = 0 then P( S ) ;
Counteast : = Counteast + l ;
V( Scounteast ) ;
P( Scount4 ) ;
上桥：过桥：下桥；
V ( Scount4 ) ;
P ( Scounteast ) ;
Counteast: = Counteast - 1 ;
if Counteast = 0 then V( S ) ;
V ( Scounteast ) ;
end ;
process west( i )
begin
P( Scountwest ) ;
if Countwest = 0 then P( S ) ;
Countwest: = Countwest + 1 ;
V( Scountwest ) ;
P ( Scount4 ) ;
上桥；过桥：下桥：
V ( Scount4 ) ;
P ( Scountwest ) ;
Countwest:= Countwest - l ;
if Countwest = 0 then V( S ) ;
V( Scountwest ) ;
end ;
Coend
有一单向行驶的公路桥，每次只允许一辆汽车通过。当汽车到达桥头时，若桥上无车，便可上桥；否则需等待，直到桥上的汽车下桥为止，若每一辆汽车为一个进程，请用Wait、Signal操作原语保证汽车按要求过桥。
汽车进程：
Pi(i=1,2,3,…)
到达桥头；
P(S)；
上桥行驶；
到达桥另一端；
V(S)；
某超市门口为顾客准备了100辆手推车，每位顾客在进去买东西时取一辆推车，在买完东西结完帐以后再把推车还回去。试用Wait/Signal操作正确实现顾客进程的同步互斥关系。semaphore S_CartNum=100;// 空闲的手推车数量，初值为100
void consumer(void) // 顾客进程
{
Wait(S_CartNum);
买东西；
结帐；
Signal(S_CartNum);
}
桌子上有一个水果盘，每一次可以往里面放入一个水果。爸爸专向盘子中放苹果，儿子专等吃盘子中的苹果。把爸爸、儿子看作二个进程，试用Wait/Signal操作使这四个进程能正确地并发执行。
?semaphore S_PlateNum; // 盘子容量，初值为1
?semaphore S_AppleNum; // 苹果数量，初值为0
父while(TRUE)
{
Wait(S_PlateNum);
往盘子中放入一个苹果；
Signal(S_AppleNum);
}
子while(TRUE)
{
Wait(S_AppleNum);
从盘中取出苹果；
Signal(S_PlateNum);
吃苹果;
}
桌上有一空盘，允许存放一只水果，爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用。
请用Wait/Signal原语实现爸爸、儿子、女儿三个并发进程的同步。
int S=1; //S 表示盘子是否为空；
int Sa=0; //Sa表示盘中是否有苹果；
int Sb=0; //Sb表示盘中是否有桔子；
父亲while(TRUE)
{
Wait(S);
将水果放入盘中;
if (放入的是桔子)
Signal(Sb);
Else
Signal(Sa);
}
儿子while(TRUE)
{
Wait(Sb);
从盘中取出桔子；
Signal(S);
吃桔子;
}
女儿while(TRUE)
{
Wait(Sa);
从盘中取出苹果；
Signal(S);
吃苹果;
}
父亲-母亲-儿子-女儿一个苹果或桔子
信号量：s=1(空盘);s1=0(苹果);s2=0(桔子);
爸爸：while(true) { wait(s); 放苹果; signal(s1); }
妈妈：while(true) { wait(s); 放桔子; signal(s2); }
儿子：while(true) { wait(s2); 取桔子; signal(s); }
女儿：while(true) { wait(s1); 取苹果; signal(s); }
父亲-母亲-儿子-女儿两个苹果或桔子
信号量：s=2(可用);s1=0(苹果);s2=0(桔子);mutex=1;
爸爸：wait(s); wait(mutex);放苹果; signal(s1); signal(mutex);
妈妈：wait(s); wait(mutex); 放桔子; signal(s2); signal(mutex);
儿子：wait(s2); wait(mutex); 取桔子; signal(s); signal(mutex);
女儿：wait(s1); wait(mutex); 取苹果; signal(s); signal(mutex);
有一个仓库(无限大)，可以存放A和B两种产品，但要求：
(1) 每次只能存入一种产品(A或B)；
(2) －N＜A产品数量－B产品数量＜M
其中，N和M是正整数。
试用Wait/Signal操作描述产品A与产品B的入库过程。
int mutex=1; //互斥信号量
int sa=M-1; //表示当前允许A产品比B产品多入库的数量
int sb=N-1; //表示当前允许B产品比A产品多入库的数量
main( )
{
while (1)
{
取一个产品；
if (取的是A产品)
{
P(sa);
P(mutex);
将产品入库；
V(mutex);
V(sb);
}
else
{
P(sb);
P(mutex);
将产品入库；
V(mutex);
V(sa);
}
}
}
某仓库存放两种零件A和B，最大数量均为m个。有一车间不断地取A和B进行装配，每次各取一个。为避免零件锈蚀，遵循先入库者先出库的原则。有两个供应商分别不断地供应A、B零件(每次一个)。为保证齐套和合理库存，当某种零件的数量比另一种的数量超过n(n (1) 问共需设置几个进程? (2) 用Wait/Signal操作解决上述问题中的同步互斥关系。 本题中给出的两种零件数量关系为： A零件数量-B零件数量≤n B零件数量-A零件数量≤n A零件数量≤m B零件数量≤m semaphore mutex=1; semaphore emptya=m; semaphore emptyb=m; semaphore fulla=0; semaphore fullb=0; semaphore sa=n; semaphore sb=n; main() { cobegin Provider_A(); Provider_B(); Assembling_shop(); conend } Provider_A() { while(true) { wait(emptya); wait(sa); wait(mutex); 将零件A放入仓库； signal(mutex); signal(fulla); signal(sb); } } Provider_B() { while(true) { wait(emptyb); wait(sb); wait(mutex); 将零件A放入仓库； signal(mutex); signal(fullb); signal(sa); } } Assembling_shop() { while(true) { wait(fulla); wait(fullb); wait(mutex); 装配零件; signal(mutex); signal(emptya); signal(emptyb); } } 设有两个生产者进程A、B和一个销售者进程C，他们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售者销售；销售者每次循环从仓库中取出一个产品进行销售。如果不允许同时入库，也不允许边入库边出库；而且要求生产和销售A产品和B产品的件数都满足一下关系： -N≤A产品数量－B产品数量≤M 其中，N和M是正整数。 试用信号量机制写出A、B、C三个进程的工作流程。 int mutex=1; //互斥信号量 int s1=M; //表示当前允许A产品比B产品 多入库的数量 int s2=N; //表示当前允许B产品比A产品 多入库的数量 int s=0; //表示当前仓库中产品的总数量 int sa=0; //表示当前仓库中A产品的数量 int sb=0; //表示当前仓库中B产品的数量 int dif=0;//表示所销售的A、B产品的数量差 Process_A: while (1) { wait(s1); produce a product A； signal(s2); wait(mutex); add the product A to the storehouse; 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); signal(sb); signal(s); } Process_C: while (1) { wait(s); if dif<=-n { wait(sa); wait(mutex); take a product A； signal(mutex); dif:=dif+1; } else if dif>=m { wait(sb); wait(mutex); take a product B; signal(mutex); dif:=dif-1; } else { wait(mutex); take a product; signal(mutex); if product_type=A { wait(sa); dif:=dif+1; } else { wait(sb); dif:=dif-1; } sell the product; } 一个数据采集系统，有数据采样进程和数据处理进程及数据输出进程。采样进程把采到的数据送入buf1中，由数据处理进程取出处理并存入buf2中，然后由数据输出进程将其从buf2中输出，试给出实现三个进程同步的算法。 信号量设置： semphore empty1=1; Semphore full1=0; semphore empty2=1; sSemphore full2=0; Process_A() { while(true) { 采集一个数据; Wait(empty1); 将数据存入buf1中； Signal(full1); } } Process_B() { while(true) { Wait(full1); 从buf1中取出数据; Signal(empty1); 处理数据; Wait(empty2); 将处理结果存入buf2; Signal(full2); } } Process_C() { while(true) { Wait(full2); 从buf2中取出结果； Signal(empty2); 打印输出； } } 在天津大学与南开大学之间有一条弯曲的小路，这条路上每次每个方向上只允许一辆自行车通过。但其中有一个小的安全岛M，同时允许两辆自行车停留，可供两辆自行车已从两端进入小路的情况下错车使用。 begin t:=1;s:=1;l:=1;k:=1;m=2; cobegin Process_T2N() begin wait(t); wait(l); 通过L路段; wait(m); 进入安全岛M； signal(l); wait(k); 通过K路段 signal(m); signal(k); signal(t); end Process_N2T() begin wait(s); wait(k); 通过K路段; wait(m); 进入安全岛M; signal(k); wait(l); 通过L路段; signal(m); signal(l); signal(s); end coend end 1.某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请用PV操作实现管理。 解：定义一个信号量S，初值为20 parbegin process pl(l=1,2,……) begin wait(S); 进入售票厅； 购票； 退出； signal(S) end 2.桌上有一空盘，允许存放一个水果，爸爸可向盘内放苹果，妈妈可向盘内放桔子，儿子专等吃盘内的桔子，女儿专等吃盘中的苹果，请用P、V 操作实现爸爸、妈妈、儿子、女儿四个并发进程的同步与互斥。 int S=1;int Sa=0;int Sb=0; main() {cobegin father(); mather(); son(); daughter(); coend} father() mather() {while(1) { while(1) {p(S); {p(S) ; 将一个苹果放入盘中将一个桔子放入盘中 V(Sa);} V(Sb);} } } son() daughter() { while(1) { while(1) {p(Sb); { p(Sa); 从盘中取出桔子从盘中取出苹果 V(S);吃桔子；} V(S);吃苹果；} } 3.生产围棋的工人不小心把相等数量的黑子和白子混装在一个盒子里，现在要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程PA和PB组成，系统功能如下： （1）PA专拣黑子，PB专拣白子； （2）每个进程每次只拣一个子，当一个进程拣子时，不允许另一个进程去拣子； （3）当一个进程拣一个子（黑或白）后，必须让另一个进程去拣一个子（白或黑） 请回答：①这两个并发进程之间的关系是同步还是互斥 ②写出PV操作管理时应定义的信号量及其初值。 ③根据定义的信号量，写出用PV操作管理两个并发进程的程序 答：①两个进程之间是同步关系 ②定义两个信号量S1和S2，初值为1和0 ③process PA process PA begin begin repeat repeat wait(S1) wait(S2) 拣黑子拣白子 signal(S2) signal(S1) until false until false end end 4.有一阅览室，读者进入时必须先在一张登记表上登记，该表为每一座位列出一个表目，包括座号、姓名，读者离开时要注销登记信息；假若阅览室共有100个座位。试用信号量和PV操作来实现用户进程的同步算法。 解：设置如下3个信号量 seat：表示阅览室中空座位数，其初值为100. （一）图书馆有100个座位，每位进入图书馆的读者要在登记表上登记，退出时要在登记表上注销。要几个程序有多少个进程（答：一个程序；为每个读者设一个进程） （1）当图书馆中没有座位时，后到的读者在图书馆为等待（阻塞）（2）当图书馆中没有座位时，后到的读者不等待，立即回家。 解（1 ) 设信号量：S=100; MUTEX=1 P(S) P(MUTEX) 登记 V(MUTEX) 阅读 P(MUTEX) 注销 V(MUTEX) V(S) 解(2) 设整型变量COUNT=100; 信号量：MUTEX=1; P(MUTEX); IF (COUNT==0) { V(MUTEX); RETURN; } COUNT=COUNT-1; 登记 V(MUTEX); 阅读 P(MUTEX); COUNT=COUNT+1; V(MUTEX); RETURN; （二）有一座东西方向的独木桥；用P,V操作实现：（1）每次只允许一个人过桥； （2）当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。 （3）当独木桥上有自东向西的行人时，同方向的行人可以同时过桥，从西向东的方向，只允许一个人单独过桥。（此问题和读者与写者问题相同,东向西的为读者，西向东的为写者）。 （1）解 设信号量MUTEX=1 P (MUTEX) 过桥 V (MUTEX) (2)解 设信号量：MUTEX=1 (东西方互斥) MD=1 (东向西使用计数变量互斥) MX=1 (西向东使用计数变量互斥) 设整型变量：CD=0 (东向西的已上桥人数) CX=0 (西向东的已上桥人数) 从东向西： P (MD) IF (CD=0) {P (MUTEX) } CD=CD+1 V (MD) 过桥 P (MD) CD=CD-1 IF (CD=0) {V (MUTEX) } V (MD) 从西向东： P (MX) IF (CX=0) {P (MUTEX) } CX=CX+1 V (MX) 过桥 P (MX) CX=CX-1 IF (CX=0) {V (MUTEX) } V (MX) (3) 解：从东向西的，和（2）相同；从西向东的和（1）相同。 1、进程P0和P1的共享变量定义及其初值为： boolean falg[2]; int turn=0; falg[0]=FALSE; falg[1]=FALSE; 若进程P0和P1访问临界资源的类C伪代码实现如下： 则并发执行进程P0和P1时产生的情形是【全国联考2010】 A. 不能保证进程互斥进入临界区、会出现“饥饿”现象 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则将不停地循环且不能进入临界区，直到进程退出临界区为止。 因此，该算法实现了临界区互斥。 “饥饿”出现的时机：使用忙等待实现互斥，当一个进程离开临界区时，如果有多个进程等待进入临界区，系统会随机选择一个进程执行，因为这种随机性，会导致有些进程长期得不到执行，因而导致“饥饿”。 本题中，如果P1已经等在while上的时候，P0至多执行一次临界区，否则下次执行的时候，即便它在P1测试条件前出了临界区并重新设定了flag，但由于它必须要设定turn=1（此时P1不会再设置turn了），因此这样P0必然卡在while上，从而换到P1执行。所以不会出现“饥饿”现象。 2、在一间酒吧里有三个音乐爱好者队列，第一个音乐爱好者只有随身听，第二个只有音乐磁带，第三个只有电池，而要听音乐就必须有随身听，音乐磁 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。 使用PV操作实现进程互斥时应该注意的是： （1）每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。 （2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。（3）互斥信号量的初值一般为1。 利用信号量和PV操作实现进程同步 PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。 使用PV操作实现进程同步时应该注意的是： 一、PV操作知识 PV操作与信号灯的处理相关，P表示通过的意思，V表示释放的意思。 1962年，狄克斯特拉离开数学中心进入位于荷兰南部的艾恩德霍芬技术大学(Eindhoven Technical University)任数学教授。在这里，他参加了X8计算机的开发，设计与实现了具有多道程序运行能力的操作系统——THE Multiprogramming System。THE是艾恩德霍芬技术大学的荷兰文Tchnische Hoogeschool Eindhov –en的词头缩写。狄克斯特拉在THE这个系统中所提出的一系统方法和技术奠定了计算机现代操作系统的基础，尤其是关于多层体系结构，顺序进程之间的同步和互斥机制这样一些重要的思想和概念都是狄克斯特拉在THE中首先提出并为以后的操作系统如UNIX等所采用的。 为了在单处理机的情况下确定进程(process)能否占有处理机，狄克斯特拉将每个进程分为“就绪”(ready)、“运行”(running)和“阻塞”(blocking)三个工作状态。由于在任一时刻最多只有一个进程可以使用处理机，正占用着处理机的进程称为“运行”进程。当某进程已具备了使用处理机的条件，而当前又没有处理机供其使用，则使该进程处于“就绪”状态。当运行进程由于某种原因无法继续运行下去时，就停止其占用处理机，使之进入“阻塞”状态，待造成其退出运行的条件解除，再进入“就绪”状态。而对系统中所有同时运行的进程，在一个进程访问共享数据时，另一个进程不访问该数据）和互斥（mutually- exclusive，指两个进程不能同时在一个临界区中使用同一个可重复使用的资源，诸如读写缓冲区）两个关系，狄克斯特拉巧妙地利用火车运行控制系统中的“信号灯”(semaphore，或叫”信号量”)概念加以解决。 所谓信号灯，实际上就是用来控制进程状态的一个代表某一资源的存储单元。例如，P1和P2是分别将数据送入缓冲B和从缓冲B读出数据的两个进程，为了防止这两个进程并发时产生错误，狄克斯特拉设计了一种同步机制叫“PV操作”，P操作和V操作是执行时不被打断的两个操作系统原语。执行P操作P（S）时信号量S的值减1，若结果不为负则P（S）执行完毕，否则执行P操作的进程暂停以等待释放。执行V操作V（S）时，S 的值加1，若结果不大于0则释放一个因执行P（S）而等待的进程。对P1和P2可定义两个信号量S1和S2，初值分别为1和0。进程P1在向缓冲B送入数据前执行P操作P（S1），在送入数据后执行V操作V（S2）。进程P2在从缓冲B读取数据前先执行P操作P（S2），在读出数据后执行V操作V（S1）。当P1往缓冲B送入一数据后信号量S1之值变为0，在该数据读出后S1之值才又变为1，因此在前一数未读出前后一数不会送入，从而保证了P1和P2之间的同步。我国读者常常不明白这一同步机制为什么叫PV操作，原来这是狄克斯特拉用荷兰文定义的，因为在荷兰文中，通过叫passeren，释放叫vrijgeven，PV操作因此得名。这是在计算机术语中不是用英语表达的极少数的例子之一。 二、PV操作释疑 信号量 信号量是最早出现的用来解决进程同步与互斥问题的机制， 包括一个称为信号量的变量及对它进行的两个原语操作。 一. 信号量的概念 1．信号量的类型定义 每个信号量至少须记录两个信息：信号量的值和等待该信号量的进程队列。它的类型定义如下：（用类PASCAL语言表述） semaphore = record value: integer; queue: ^PCB; 用P，V操作实现下述问题的解。 一、桌上有一个盘子，可以放一个水果；父亲总是放苹果到盘子中；母亲总是放香蕉到盘子中。一个儿子专等吃盘中的香蕉，而一个女儿专等吃盘中的苹果。父母只放水果不吃，儿女只吃水果不放。实现父亲，母亲，儿子，女儿的进程同步。 二、在公共汽车上，司机和售票员的活动分别是： 司机的活动：启动车辆，正常行车，到站停车。 售票员的活动：上下乘客，关车门，售票，开车门，上下乘客。 在汽车不停的到站，停站，行驶过程中，这两个活动有什么同步关系？用信号量和P，V操作实现它们的同步。 三、某寺庙，有小，老和尚若干，有一个水缸，有小和尚提水入缸供老和尚饮用。水缸可以放10桶水，水从一个井里面提。水井狭窄，每次只能容纳一个桶取水。水桶总数为3个。每次入、取缸水只能是1桶，且不可以同时进行。试给出取水，入水的算法描述。 四、一个快餐厅有4类职员：（1）领班：接受顾客点菜，出菜单；（2）厨师：根据菜单，准备顾客的饭菜；（3）打包工：将做好的饭菜打包；（4）出纳员：收款并提交食品。每个职员可被看作一个进程，试用一种同步机制写出能让四类职员正确并发运行的程序。 五、假设有一个作业由四个进程组成，这四个进程在运行时必须按如图所示的次序依次执行，试用P,V原语表达四个进程的同步关系： 六、观察者和报告者是两个并发执行的进程，观察者不断观察并对通过的卡车计数，报告者定时的将观察者的计数值打印，打印完毕，将计数值清零。 七、假定阅览室最多可同时容纳100个人阅读，读者进入时，必须在阅览室门口的一个登记表上登记，内容包括姓名、座号等，离开时要撤掉登记内容。用P、V操作描述读者进程的同步算法。 1.读写操作 1、、设有一台计算机，有两条I/O通道，分别接一台卡片输入机和一台打印机。卡片机把一 叠卡片逐一输入到缓冲区B1中，加工处理后在搬到缓冲区B2中，并在打印机上印出，问： ①系统要设几个进程来完成这个任务？各自的工作是什么？ ②这些进程间有什么样的相互制约关系？ ③用P、V操作写出这些进程的同步算法。 ①系统可设三个进程来完成这个任务：R进程负责从卡片输入机上读入卡片信息，输入到缓冲区B1中；C进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区B2中；P进程负责从缓冲区B2中取出信息，并在打印机上印出。 ②R进程受C进程影响，B1放满信息后R进程要等待——等C进程将其中信息全部取走，才能继续读入信息；C进程受R进程和P进程的约束：B1中信息放满后C进程才可从中取出它们，且B2被取空后C进程才可将加工结果送入其中；P进程受C进程的约束：B2中信息放满后P进程才可从中取出它们,进行打印。 ③信号量含义及初值： B1full——缓冲区B1满，初值为0； B1empty——缓冲区B1空，初值为0； B2full——缓冲区B2满，初值为0； B2empty——缓冲区B2空，初值为0； R进程C进程P进程 B1 B2 2、用P.V操作处理生产者和消费者问题如下： mutex初值为1；empty初值为n；full初值为0 生产者消费者 L1：生产产品 L2：P（full） P（empty） P（mutex） P（mutex）取出产品 产品装入缓冲区 V（empty） V（full） V（mutex） V（mutex） GOTO L2 GOTO L1 （1）信号量mutex,empty,full的作用是什么？ （2）为什么P操作的顺序不能调换？ （1）mutex起互斥作用，empty与full为同步作用。 在计算机操作系统中，PV操作是进程管理中的难点。 首先应弄清PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下： P（S）：①将信号量S的值减1，即S=S-1； ②如果S30，则该进程继续执行；否则该进程置为等待状态，排入等待队列。 V（S）：①将信号量S的值加1，即S=S+1； ②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。 PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。 什么是信号量？信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。 一般来说，信号量S30时，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。 使用PV操作实现进程互斥时应该注意的是： （1）每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。 （2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。（3）互斥信号量的初值一般为1。 利用信号量和PV操作实现进程同步 PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。 使用PV操作实现进程同步时应该注意的是： （1）分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量。 4有三个并发进程，R负责从输入设备读入信息并传送给M，M将信息加工并传送给P，P将打印输出，写出下列条件下的并发程序： 单缓冲区， 缓冲区信号量初值mutex1=1; mutex2=1; buffeR-M // R 和M之间的buf bufferM_P // M 和P之间的buf 另外R 自己的缓存区data_buf1, 另外M 自己的缓存区data_buf2, 另外P 自己的缓存区data_buf3, Procedure R： begin while true do data_buf1 = 读入数据 P(mutex1); buffeR-M = data_buf1; V(mutex1); end end; Procedure M: begin while true do P(mutex2); P(mutex1); Data_buf2 = bufferR_M; 处理Data_buf2； BufferM_P = data_buf2 V(mutex1); V(mutex2); end end; Procedure P: begin while true do P(mutex2); Data_buf3:= BufferM_P; V(mutex2); V(empty); 打印输出数据 end end; 双缓冲区， 缓冲区信号量初值mutex1=1; mutex2=1; Empty1 = 2, full1 = 0; empty2=2, full2=0; buffeR-M[2] // R 和M之间的buf，有两个bufferM_P[2] // M 和P之间的buf 有两个另外R 自己有缓存区data_buf1, 另外M 自己有缓存区data_buf2, 另外P 自己有缓存区data_buf3, var：i,j,k,n Procedure R： begin while true do data_buf1 = 读入数据 P(empty1) P(mutex1); buffeR-M[i] = data_buf1; i=(i+1)mod 2; V(mutex1); V(full1) end end; Procedure M: begin while true do P(full1); P(mutex1); Data_buf2 = bufferR_M[j]; j=(j+1) mod 2 V(mutex1); P(empty1); 处理Data_buf2； P(empty2); P(mutex2) BufferM_P[k] = data_buf2; k=(k+1) mod 2 V(mutex2); V(full2); end end; Procedure P: begin while true do P(full2); ？？？信号量的PV操作是如何定义的？试说明信号量的PV操作的物理意义。 参考答案：P（S）：将信号量S减1，若结果大于或等于0，则该进程继续执行；若结果小于0，则该进程被阻塞，并将其插入到该信号量的等待队列中，然后转去调度另一进程。 V（S）：将信号量S加1，若结果大于0，则该进程继续执行；若结果小于或等于0，则从该信号量的等待队列中移出一个进程，使其从阻塞状态变为就绪状态，并插入到就绪队列中，然后返回当前进程继续执行。 PV操作的物理含义：信号量S值的大小表示某类资源的数量。当S>0时，其值表示当前可供分配的资源数目；当S<0时，其绝对值表示S信号量的等待队列中的进程数目。每执行一次P操作，S值减1，表示请求分配一个资源，若S≥0，表示可以为进程分配资源，即允许进程进入其临界区；若S<0，表示已没有资源可供分配，申请资源的进程被阻塞，并插入S的等待队列中，S的绝对值表示等待队列中进程的数目，此时CPU将重新进行调度。每执行一次V操作，S值加1，表示释放一个资源，若S>0，表示等待队列为空；若S≤0，则表示等待队列中有因申请不到相应资源而被阻塞的进程，于是唤醒其中一个进程，并将其插入就绪队列。无论以上哪种情况，执行V操作的进程都可继续运行。 1、设公共汽车上，司机和售票员的活动分别是： 司机的活动：启动车辆； 正常行车； 到站停车； 售票员的活动： 关车门； 售票； 开车门； 在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用P、V操作实现它们的同步。 设两个信号量S和C，初值为S＝0；C＝0； 司机： L1：正常行车售票员： L2：售票 到站停车 P（S） V（S）开车门 P（C）关车门 启动开车 V（C） GO TO L1 GO TO L2 2、请用PV操作实现他们之间的同步关系： （1）桌上一个盘子，只能放一只水果。爸爸放苹果，妈妈放桔子，儿子只吃桔子，女儿只吃苹果。 （2）桌上一个盘子，只能放一只水果。爸爸放苹果，妈妈放桔子，儿子吃桔子、苹果。 参考答案： 第一步：确定进程 4个进程Father（爸爸）、Mother（妈妈）、Son（儿子）、Daughter（女儿） Father进程： 将苹果放入盘中 计算机操作系统P V操 作例题 WTD standardization office【WTD 5AB- WTDK 08- WTD 2C】 问题1一个司机与售票员的例子在公共汽车上，为保证乘客的安全，司机和售票员应协调工作： 停车后才能开门，关车门后才能行车。用PV操作来实现他们之间的协调。 S1：是否允许司机启动汽车的变量 S2：是否允许售票员开门的变量 driver()有三个进程R、M、P，它们共享一个缓冲区。R负责从输入设备读信息，每次读出一个记录并把它存放在缓冲区中：M在缓冲区加工读入的记录；P把加工后的记录打印输出。输入的记录经加工输出后，缓冲区中又可存放下一个记录。请用P、V操作为同步机构写出他们并发执行时能正确工作的程序。 答：三个进程共用一个缓冲区，他们必须同步工作，可定义三个信号量： S1：表示是否可把读人的记录放到缓冲区，初始值为1. S2：表示是否可对缓冲区中的记录加工，初始值为0. S3：表示记录是否加工好，可以输出，初始值也为0. 三个进程可如下设计： Begin S1，S2，S3：semaphore； S1：＝l；S2：＝S3：＝0； cobegin process R begin L1：读记录； P（S1）； 记录存入缓冲区； V（S2）； goto L1； end； process M begin L2：P（S2）； 加工记录； V（S3）； goto L2； end； process P begin L3：P（S3）； 输出加工后的记录； V（S1）； goto L3； end； coend； end. 6.现有4个进程R1，R2，W1，W2，它们共享可以存放一个数的缓冲器B.进程R1每次把从键盘上投入的一个数存放到缓冲器B中，供进程W1打印输出；进程R2每次从磁盘上读一个数放到缓冲器B中，供进程W2打印输出。当一个进程把数据存放到缓冲器后，在该数还没有被打印输出之前不准任何进程再向缓冲器中存数。在缓冲器 问题1 一个司机与售票员的例子 在公共汽车上，为保证乘客的安全，司机和售票员应协调工作： 停车后才能开门，关车门后才能行车。用PV操作来实现他们之间的协调。 S1：是否允许司机启动汽车的变量 S2：是否允许售票员开门的变量 driver()//司机进程 { while (1)//不停地循环 { P(S1);//请求启动汽车 启动汽车; 正常行车； 到站停车； V(S2); //释放开门变量，相当于通知售票员可以开门 } } busman()//售票员进程 { while(1) { 关车门; V(S1)；//释放开车变量，相当于通知司机可以开车 售票 P(S2)；//请求开门 开车门； 上下乘客； } } 注意：busman() driver() 两个不停循环的函数 问题2 图书馆有100个座位，每位进入图书馆的读者要在登记表上登记，退出时要在登记表上注销。要几个程序？有多少个进程？（答：一个程序；为每个读者设一个进程）（1）当图书馆中没有座位时，后到的读者在图书馆为等待（阻塞） （2）当图书馆中没有座位时，后到的读者不等待，立即回家。 解（1 ) 设信号量：S=100; MUTEX=1 P(S) P(MUTEX) 登记 V(MUTEX) 阅读 P(MUTEX) 注销 V(MUTEX) V(S) 解(2) 设整型变量COUNT=100; 信号量：MUTEX=1; P(MUTEX); IF (COUNT==0) { V(MUTEX); RETURN; } COUNT=COUNT-1; 登记 V(MUTEX); 阅读 P(MUTEX); COUNT=COUNT+1; V(MUTEX); RETURN; 问题3 有一座东西方向的独木桥；用P,V操作实现： （1）每次只允许一个人过桥； （2）当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。（3）当独木桥上有自东向西的行人时，同方向的行人可以同时过桥，从西向东的方向，只允许一个人单独过桥。（此问题和读者与写者问题相同,东向西的为读者，西向东的为写者）。 （1）解 设信号量MUTEX=1 P (MUTEX) 过桥 V (MUTEX) (2)解 设信号量：MUTEX=1 (东西方互斥) MD=1 (东向西使用计数变量互斥) MX=1 (西向东使用计数变量互斥) 设整型变量：CD=0 (东向西的已上桥人数) CX=0 (西向东的已上桥人数) 从东向西： P (MD) IF (CD=0) 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 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) 0PA:beginL1:read from disk; P(avail1); put to buffer1; V(full1); goto L1; End; PB:beginL2:P(full1); get from buffer1; V(avail1); P(avail2); put to buffer2; V(full2); goto L2; End; PC:beginL3: P(full2); get from buffer2; V(avail2); print RECORD; goto L3 end ; Cobegin PA;PB;PC;Coend. 第一步:确定进程间的关系。售票员关车门后，要向司机发开车信号，司机接到开车信号后才能启动车辆。在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门，让乘客上下车。因此司机启动车辆的动作必须与售票员的动作取得同步;售票员开车门的动作也必须同司机停车取得同步。第二步:确定信号量及其值。由于司机与售票员之间要互通消息，司机进程设置一个私有信号量run，用于判断是否关车门，司机能否启动车辆，初值为1。售票员进程设置一个私有信号量stop，用于判断是否停车，售票员是否能够开车门，初值为0 第三步: 确定P(wait)、V(signal)操作的位置司机操作中，是否关门?没关则等待，这是一个P操作，P(run); 司机操作中，设立停车标志，这是一个V操作，V(stop); 售票员操作中，是否停车?没停则等待，这是一个P操作，P(stop); 售票员操作中，设立关门标志，这是一个V 操作，V(run) lstop ,run:semaphore run:=1; //是否关车门stop:=0; //是否停车Driver:begin cobegin driver: begin L1: P(run); 启动车辆; 正常行车; 到站停车; V(stop); goto L1; end; Conductor:begin L2:上乘客; 关车门; V(run); 售票; P(stop); 开车门; 下乘客; goto L2; end; coend; 操作系统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操作首先是一个原语操作，对于每一个进程来说，都只能进行一次。而且必须成对使用。且在P,V愿语执行期间不允许有中断的发生。 对于具体的实现，方法非常多，可以用硬件实现，也可以用软件实现。这里不再赘述。 2 The Most Important Conceptions 临界资源是指每次仅允许一个进程访问的资源。属于临界资源可以是硬件的打印机、磁带机等,软件的有消息缓冲队列、变量、数组、缓冲区等。每个进程中访问临界资源的那段程序称为临界区（临界资源是一次仅允许一个进程使用的共享资源）。每次只准许一个进程进入临界区，该进程进入后不允许其他进程进入。 一、用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() { cobegin P1( ); 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所示。假定这些生产者和消费者是互相等效的。只要缓冲区未满，生产者就可以把产品送入缓冲区，类似地，只要缓冲区未空，消费者便可以从缓冲区中取走物品并消耗它。生产者和消费者的同步关系将禁止生产者向满的缓冲区输送产品，也禁止消费者从空的缓冲区中提取物品。 图2．4 生产者-消费者问题 为解决这一类生产者-消费者问题，应该设置两个同步信号量，一个说明空缓冲单元的 ################################## 1 #################################3 empty=1; apple=0; //表示盘中有苹果 orange=0; //表示盘中有桔子 Parbegin: father: begin L1: P(empty); 放苹果; V(apple); goto L1; End; mother: begin: L2: P(empty); 放桔子; V(orange); goto L2; End; daughter: begin: L3: P(apple); 取苹果; V(empty); goto L3; End; son: begin: L4: P(orange); 去桔子; V(empty); goto L4; End; Parend; ################################## 2 ############################# S=1; //是否允许向盘子中存放水果 SP=0; //盘子中是否有苹果 S0=0; //盘子中是否有桔子 begin S := 1; SP := 0; S0 := 0; Cobegin Process father begin: L1: 准备一个苹果; P(S); 放入苹果; V(SP); goto L1; End; Process mother begin: L2: 准备一个桔子; P(S); 放入桔子; V(S0); goto L2; End; Process daughter begin: L3: P(SP); 取出苹果; V(S); goto L3; End; Process son begin: L4: P(S0); 取出桔子; P就是请求资源，V就是释放资源。 问题1 一个司机与售票员的例子 在公共汽车上，为保证乘客的安全，司机和售票员应协调工作： 停车后才能开门，关车门后才能行车。用PV操作来实现他们之间的协调。 S1：是否允许司机启动汽车的变量 S2：是否允许售票员开门的变量 driver()//司机进程 { while (1)//不停地循环 { P(S1);//请求启动汽车 启动汽车; 正常行车； 到站停车； V(S2); //释放开门变量，相当于通知售票员可以开门 } } busman()//售票员进程 { while(1) { 关车门; V(S1)；//释放开车变量，相当于通知司机可以开车 售票 P(S2)；//请求开门 开车门； 上下乘客； } } 注意：busman() driver() 两个不停循环的函数 问题2 图书馆有100个座位，每位进入图书馆的读者要在登记表上登记，退出时要在登记表上注销。要几个程序？有多少个进程？（答：一个程序；为每个读者设一个进程） （1）当图书馆中没有座位时，后到的读者在图书馆为等待（阻塞） （2）当图书馆中没有座位时，后到的读者不等待，立即回家。 解（1 ) 设信号量：S=100; MUTEX=1 P(S) P(MUTEX) 登记 V(MUTEX) 阅读 P(MUTEX) 注销 V(MUTEX) V(S) 解(2) 设整型变量COUNT=100; 信号量：MUTEX=1; P(MUTEX); IF (COUNT==0) { V(MUTEX); RETURN; } COUNT=COUNT-1; 登记 V(MUTEX); 阅读 P(MUTEX); COUNT=COUNT+1; V(MUTEX); RETURN; 问题3 有一座东西方向的独木桥；用P,V操作实现： （1）每次只允许一个人过桥； （2）当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。 （3）当独木桥上有自东向西的行人时，同方向的行人可以同时过桥，从西向东的方向，只允许一个人单独过桥。（此问题和读者与写者问题相同,东向西的为读者，西向东的为写者）。 （1）解 设信号量MUTEX=1 P (MUTEX) 过桥 V (MUTEX) (2)解 设信号量：MUTEX=1 (东西方互斥) MD=1 (东向西使用计数变量互斥) MX=1 (西向东使用计数变量互斥) 1、(2009全国试题)三个进程P1、P 2、P3互斥使用一个包含N(N>0)个单元的缓冲区。P1每次用produce( )生成一个正整数并用put( )送入缓冲区某个单元中；P2每次用getodd( )从缓冲区中取出一个奇数并用countodd( )统计奇数个数；P3每次用geteven( )从缓冲区中取出一个偶数并用counteven( )统计偶数个数。请用信号量机制实现这三个进程的同步与互斥 活动，并说明所定义的信号量的含义。要求用伪代码描述。 2、请用信号量解决以下的“过独木桥”问题：同一方向的行人可连续过桥，当 某一方向有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。 3、有一阅览室，共有100个座位。为了很好利用它，读者进入时必须先在登记 表上进行登记。该表表目设有座位号和读者姓名；离开时再将其登记项摈除。试问： ⑴为描述读者的动作，应设哪几个进程？它们之间的关系是什么？ ⑵试用P、V操作描述进程之间的同步或算法。 4、某自动质量检测系统有三个进程Q、A、B组成。进程Q每次取一件产品检测，把检测后的产品存放在货架F上，F的容量为每次只能存放一件产品。若货架上存放的是合格产品则让进程A取出，并在产品上贴标签后包装；若货架上存放的是不合格产品则让进程B取出后，将其丢入废物箱。回答下列问题： （1）写出用PV操作管理时应定义的信号量及初值：①。 （2）完成下列算法中的填空，使它们能按上述要求正确地并发执行。 进程Q: 取一件产品检测; ② ; F:=检测后的产品 If F=合格产品 then ③ else ④进程A: _____⑤ ; y:=F中产品 ; ______⑥ ; 对产品贴标签且包装; 进程B：____⑦ ; z:=F中产品; ____⑧ ; 把产品丢入废物箱; 5、《操作系统》课程的期末考试即将举行，假设把学生和监考老师都看作进程，学生有N人，教师1人。考场门口每次只能进出一个人，进考场的原则是先来先进。当N个学生都进入了考场后，教师才能发卷子。学生交卷后即可离开考场，p_v操作例题
PV操作题解
pv操作的一些习题
PV操作的例题
pv操作总结
pv操作练习题
操作系统关于PV操作
经典PV操作讲解和练习题
操作系统 PV操作习题答案
信号量地PV操作(例题)
计算机操作系统PV操作例题
计算机操作系统PV操作例题
操作系统PV操作经典例题与答案
操作系统pv操作
操作系统pv操作
操作系统PV操作习题
福州大学,操作系统,pv操作,吃水果问题
P,V操作经典例题
操作系统PV操作补充题