PV操作飞机票、理发师、银行、缓冲区、吸烟

一、飞机票问题

Var A : ARRAY[1..m] of integer; mutex : semaphore; mutex:= 1; cobegin process Pi var Xi:integer; begin <span style="white-space:pre"> </span>L1: 按旅客定票要求找到A[j]; P(mutex); Xi := A[j]; if Xi>=1 then begin Xi:=Xi-1;A[j]:=Xi; V(mutex); {输出一张票}； end; else begin V(mutex); {输出“票已售完”}； end; goto L1; end; coend

二、理发师睡眠问题

理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子

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

一个顾客到来时，它必须叫醒理发师

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

 

<pre name="code" class="plain">int waiting=0; //等候理发顾客坐的椅子数 int CHAIRS=N; //为顾客准备的椅子数 semaphore customers, barbers, mutex; customers=0; barbers=0; mutex=1; process barber( ) { while(true) { P(customers); //有顾客吗?若无顾客,理发师睡眠 P(mutex); //若有顾客时，进入临界区 waiting--; //等候顾客数少一个 V(barbers); //理发师准备为顾客理发 V(mutex); //退出临界区 cut_hair(); //理发师正在理发(非临界区) } } process customer_i( ) { P(mutex); //进入临界区 if(waiting<CHAIRS) { //有空椅子吗 waiting++; //等候顾客数加1 V(customers); //唤醒理发师 V(mutex); //退出临界区 P(barbers); //理发师忙，顾客坐下等待 get_haircut(); //否则顾客坐下理发 } else V(mutex); //人满了,走吧！ }

三、银行业务问题

某大型银行办理人民币储蓄业务，由n个储蓄员负责。每个顾客进入银行后先至取号机取一个号，并且在等待区找到空沙发坐下等着叫号。取号机给出的号码依次递增，并假定有足够多的空沙发容纳顾客。当一个储蓄员空闲下来，就叫下一个号。

 

var customer_count, server_count, mutex: semaphore; customer_count:=0; server_count:=n; mutex:=1; process customeri(i=1,2,….) begin take a number; P(mutex); 等待区找到空沙发坐下; V(mutex); V(customer_count); P(server_count); end; Process servers j(j=1,2,3,…) Begin L: P(customer_count); P(mutex); 被呼号顾客离开沙发走出等待区; V(mutex); 为该号客人服务; 客人离开; V(server_count); go to L; end;

四、缓冲区管理

 

*有n个进程将字符逐个读入到一个容量为80的缓冲区中(n>1)，当缓冲区满后，由输出进程Q负责一次性取走这80个字符。这种过程循环往复，请用信号量和P、V操作写出n个读入进程(P1，P2，…Pn)和输出进程Q能正确工作的的动作序列

var mutex,empty,full:semaphore; count,in:integer buffer:array[0..79] of char; mutex=1;empty=80;full=0; count=0;in=0; process Pi(i=1,...,n)) begin L: 读入一字符到x; P(empty); P(mutex); Buffer[in]=x; in=(in+1) % 80; count++; if (count==80) {count=0; V(mutex); V(full); } else V(mutex); goto L; end; process Q begin while(true) { P(full); P(mutex); for(int j=0; j< 80;j++) read buffer[j]; in:=0; V(mutex); for (int j=0; j< 80;j++) V(empty); } end;

五、吸烟者问题(patil，1971)。

 

三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者有丰富货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸和第三个有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样东西放在桌子上，唤醒另一个吸烟者。

 

semaphor:s0,s1,s2,s3; S0=1;S1=0;S2=0;S3=0; Process businessman { //供应者进程 L1：i:=RAND( ) mod 3; j:=RAND( ) mod 3; If (i=j) then goto L1; P(S0); Put_items [i]_on_table; Put_items [j]_on_table; if (i=0 and j=1) or (i=1 and j=0) V(S[3]); if (i=1 and j=2) or (i=2and j=1) V(S[1]); if (i=0 and j=2) or (i=2 and j=0) V(S[2]); goto L1; } Process consumer (k) { //吸烟者进程，k=1,2,3 L1： P(S[k]); take_one_item_from_table; take_one_item_from_table; V(S0); make_cigarette_and_smokeing goto L1; }