典型问题.doc

1.
有一个盒子，混装了数量相等的围棋白子和黑子。现在要用自动分拣系统把白子和黑子分开。设系统有两个进程P1和P2，其中P1拣白子，P2拣黑子。当一个进程在拣子时，不允许另一进程去拣。试写出这两个并发进程能正确执行的程序。

begin
mutex := 1;
cobegin
P1:
begin
repeat
P(mutex);
拣白子；
V(mutex);
until false
end

P2:
begin
repeat
P(mutex);
拣黑子；
V(mutex);
until false
end
coend
end

加上“当以一进程拣了一子时，必须让另一个进程去拣”条件：

设置两个信号量S1和S2来协调进程P1和P2之间的同步。假定先让P1拣白子，则信号量S1和S2的初值分别为1和0。两个并发进程相应的程序如下：
begin
S1 :=1; S2 := 0;
cobegin
P1:
begin
repeat
P(S1);
拣白子；
V(S2);
until false
end

P2:
begin
repeat
P(S2);
拣黑子；
V(S1);
until false
end
coend
end

2.
用PV操作实现下述问题的解。
桌上有一个盘子，可以存放一个水果，父亲总是放苹果到盘子中，而母亲则总是放香蕉到盘子中；一个儿子专等吃盘中的香蕉，而一个女儿专等吃盘中的苹果。
由于父亲和母亲可以同时向盘子放水果，所以盘子是临界资源，应设置一个互斥信号量mutex来实现放水果的互斥，其初值为1.此外父亲和女儿，母亲和儿子之间存在同步关系，及分别设置信号量apple和banana来分别实现这种同步关系，其初值均为0。
4个进程的并发程序如下：
begin
mutex := 1;
apple := 0; banana := 0;
cobegin
father:
begin
repeat
P(mutex);
向盘中放苹果；
V(apple);
until false;
end;
mother:
begin
repeat
P(mutex);
向盘中放香蕉；
V(banana);
until false
end;
daughter:
begin
repeat
P(apple);
取盘中的苹果；
V(mutex);

until false;
end;
son:
begin
repeat
P(banana);
取盘中的香蕉；
V(mutex);
until false;
end;
coend;
end;

升级版

桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，可向盘中放桔子；儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿3个并发进程的同步。
begin
mutex := 1;
apple := 0; banana := 0;
cobegin
father:
begin
repeat
P(mutex);
将水果放入盘中；
if 放入的是桔子 then V(orange)
else V(apple);
until false;
end;

daughter:
begin
repeat
P(apple);
取盘中的苹果；
V(mutex);
until false;
end

son:
begin
repeat
P(orange);
取盘中的香蕉；
V(mutex);
until false;
end;
coend;
end;

桌上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子放苹果，妈妈专向盘子中放桔子；两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。请用P、V操作来实现爸爸、妈妈、儿子和女儿之间的同步与互斥关系。
与上一例不同的是，现在盘子可以放入两个水果，因此除了互斥信号量mutex之外，还应对允许向盘中放入水果的个数进行计数，即再设置一个信号量empty，其初值为2.此外由于盘子中可以放两个水果，即当盘中有一个水果时，存在着既可以放有可以取得情况，因此，除了对放水果进行互斥外，对取水果也应进行互斥。此时，4个进程的并发程序如下：
begin
mutex := 1; empty := 2;
apple := 0; orange := 0;
cobegin
father:
begin
repeat
P(empty);
P(mutex);
向盘中放苹果；
V(mutex);
V(apple);
until false
end

mother:
begin
repeat
P(empty);
P(mutex);
向盘中放桔子；
V(mutex);
V(orange);
until false
end

daughteri(i = 1, 2;):
begin
repeat
P(apple);
P(mutex);
取盘中苹果；
V(mutex);
V(empty);
until false
end

soni(i = 1, 2):
begin
repeat
P(orange);
P(mutex);
取盘中桔子；
V(mutex)
V(empty);
until false
end

coend
end;

3.
有一个理发师，一把理发椅和n-1把供等候理发的顾客坐的椅子。
（1）如果没有顾客，则理发师便在理发椅子上睡觉；
（2）当一个顾客到来时，必须唤醒理发师进行理发；
（3）如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他就坐下来等，如果没有空椅子，他就离开。
为理发师和顾客各编写一段程序描述他们的行为，要求不能带有竞争条件。
本题可看作是n个生产者和一个消费者问题。顾客作为生产者，每到来一个就使计数器rc加1，以便让理发师理发（消费）至最后一个顾客（产品）。并且，第一个到来的顾客应负责唤醒理发师；如果不是第一个到达的顾客，则在有空椅子的情况下坐下等待，否则离开理发厅（该信息可由计数器rc获得）。理发师与顾客的并发程序描述如下：
beign
mutex := 1;
wakeup := 0; wait := n;
cobegin
customeri(i = 1;…):
begin
P(mutex);
rc = rc + 1;
if (rc = 1) then V(wakeup)
else
if rc ≤ n then P(wait) /*顾客人数≤ n 时在椅子上等待*/
else
begin
rc := rc - 1; /*是第n+1个顾客时则离开理发厅*/
该顾客离开
end;
V(mutex)
end;
barber:
begin
P(wakeup); /*没有顾客时，理发师睡觉（阻塞），直到第一个顾客来时唤醒*/
repeat
理发；
P(mutex);
rc := rc - 1;
if (rc ≠ 0) then V(wait); /*让等待中的一个顾客准备理发*/
V(mutex)
until rc = 0 /*理发重复到没有顾客为止*/
end
conend;
end;

扩展版：
一个理发店由一个有N个沙发的等候室和一个放有一张理发椅的理发室组成。没有顾客要理发时，理发师便去睡觉。当一个顾客走进理发店时，如果所有的沙发都已被占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成后，顾客必须付费，直到理发师收费后才能离开理发店。试用信号量实现这一同步问题。
本题中，顾客进程和理发师进程之间存在着多种同步关系：
（1）只有在理发椅空闲时，顾客才能坐到理发椅上等待理发师理发，否则顾客必须等待；只有当理发椅上有顾客时，理发师才可以开始理发，否则他也必须等待。这种同步关系类似于单缓冲（对应于理发椅）的生产者-消费者问题中的同步关系，故可通过信号量empty和full来控制。
（2）理发师为顾客理发时，顾客必须等待理发的完成，并在理发完成后由理发师唤醒他，这可单独使用一个信号量cut来控制。
（3）顾客理完发后必须向理发师付费，并等理发师收费后顾客才能离开；而理发师则必须等待顾客付费，并在收费后唤醒顾客以允许他离开，这可分别通过两个信号量payment和receipt来控制。
（4）等候室中的N张沙发是顾客进程竞争的资源，故还需为他们设置一个信号量sofa。
（5）为了控制顾客的人数，使顾客能在所有的沙发都被占用时离开理发店，还必须设置一个整型变量count来对理发店中的顾客进行计数，该变量将被多个顾客进程互斥地访问并修改，这可通过一个互斥信号量mutex来实现。
为了解决上述问题，需设置一个整型变量count用来对理发店中的顾客进行计数，并需设置7个信号量，其中：mutex用来实现顾客进程对count变量的互斥访问，其初值为1；sofa是对应于等候室中N张沙发的资源信号量，其初值为N；empty表示有是否空闲的理发椅，其初值为1；full表示理发椅上是否坐有等待理发的顾客，其初值为0；cut用来等待理发的完成，其初值为0；payment用来等待付费，其初值为0；receipt用来等待收费，其初值为0。具体算法描述如下
Var count :integer := 0;
mutex, sofa empty, full :semaphore := 1, N, 1, 0;
cut, pament, receipt :semaphore := 0, 0 , 0;
beigin
parbegin
guest:
begin
wait(mutex);
if (count > N) then
begin
signal(mutex);
exit shop;
end
else
begin
count: = count + 1;
if (count > 1) then
begin
wait(sofa);
sit on sofa;
wait(empty);
get up from sofa;
signal(sofa)
end
else /*count = 1*/
wait(empty);
sit on the baber_chair;
signal(full);
wait(cut);
pay;
signal(payment);
wait(receipt);
get up from the baber_chair;
signal(empty);
wait(mutex);
count := count – 1;
signal(mutex);
exit shop;
end
end
baber:
begin
repeat
wait(full);
cut hair;
signal(cut);
wait(payment);
accept payment;
signal(receipt);
until false;
end
parend
end

4.

设有P1，P2，P3进程共享某一文件F，P1对F只读不写，P2对F只写不读，P3对F先读后写。当一个进程写F时，其他进程对F不能进行读写，但多个进程同时读F是允许的。试用P、V实现P1，P2，P3的同步与互斥。
begin
rmutex := 1; wmutex := 1;
count := 0;
cobegin
P1:
begin
repeat
P(rmutex);
count : = count + 1;
if count = 1 then P(mutex);
V(rmutex);
读文件F；
P(rmutex);
count : = count – 1;
if count = 0 then V(wmutex);
V(rmutex)
until false
end;
P2:
begin
repeat
P(wmutex);
写文件F；
V(wmutex);
until false
end;
P3
begin
repeat
P(rmutex);
count : = count + 1;
if count = 1 then P(wmutex);
V(rmutex);
读文件F；
P(rmutex);
count : = count – 1;
if count = 0 then V(wmutex);
V(rmutex);
P(wmutex);
写文件F;
V(wmutex);
until false
end;
coend
end

5.
吸烟者问题：
假设系统有3个吸烟者（smoker）进程和1个供货商进程（Agent）进程。每个吸烟者连续不断地制造香烟并吸掉它。但是，制造一支香烟需要3种材料—烟、纸、火柴。一个吸烟者进程有纸，另一个有烟，第三个有火柴。供货商进程可以无限地提供这三种材料。供货商将两种材料一起放在桌子上，持有另一种材料的吸烟者即可制造一支香烟并吸掉它。当此吸烟者抽香烟时，他发出一个信号通知供货商进程，供货商马上给出另外两种材料，如此循环往复。试编写一个程序使供货商与吸烟者同步执行。

begin
sale := 1; S1 := 0; S2 := 0; S3 := 0;
a := 1;
cobegin
Agent:
begin
repeat
P(sale);
if a = 1 then
begin
将烟和火柴放在桌子上；
V(S1)
end;
if a = 2 then
begin
将纸和火柴放在桌子上；
V(S2)
end;
if a = 3 then
begin
将烟和纸放在桌子上；
V(S3)
end
until false
end;
Smoker1:
begin
repeat
P(S1);
购买烟和火柴；
a : = 2;
V(sale);
吸烟
until false
end;
Smoker2:
begin
repeat
P(S2);
购买纸和火柴；
a : = 3;
V(sale);
吸烟
until false
end;
Smoker3:
begin
repeat
P(S3);
购买烟和纸；
a : = 1;
V(sale);
吸烟
until false
end;
coend
end