2.5.1 生产者—消费者问题
1．利用记录型信号量解决P-C问题
问题描述：在生产者和消费者之间有n个缓冲区组成的循环缓冲池，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。
1)进程互斥、同步分析：
P,C进程对缓冲区的访问时互斥；
P,C进程之间是同步；
2)信号量分析
若采用记录型信号量，则需3个信号量
mutex:用于互斥访问缓冲区，
初值为1；
empty:空缓冲区数量,决定能否执行P进程，
初值为n；
full:满缓冲区数量，决定能否执行C进程，
初值为0；
Var mutex，empty，full:semaphore:=1,n,0；
buffer:array[0，…，n-1] ofitem；
in，out: integer:=0，0；
begin
parbegin
proceducer: begin
repeat
produceran item nextp；
wait(empty)；
wait(mutex)；
buffer(in):=nextp；
in:=(in+1) mod n；
signal(mutex)；
signal(full)；
untilfalse；
end
consumer: begin
repeat
wait(full)；
wait(mutex)；
nextc:=buffer(out)；
out:=(out+1) modn；
signal(mutex)；
signal(empty)；
consumerthe item in nextc；
untilfalse；
end
parend
end
注：1）互斥信号P,V操作成对出现在一个程序段中
2）同步信号P,V操作成对出现在两个程序段中
3）应先资源信号再互斥信号P操作，否则易死锁
例如缓冲区全满的情况：
empty=0,则full=n,若mutex=1
执行wait(empty);wait(mutex);
当empty信号受阻时不会再测试mutex信号
执行wait(mutex);wait(empty);
当mutex满足时再测试empty信号P进程即会受阻，若要执行P进程就必须先由C进程取走消息，但此时缓冲区访问权在P进程C进程无法访问缓冲区，也就无法取走消息，取不走消息，P进程始终不能执行，因此陷入死锁。
2．利用AND信号量集解决P-C问题
Var mutex，empty，full:
semaphore:=1，n，0；
buffer:array[0，…，n-1] ofitem；
inout: integer:=0，0；
begin
parbegin
producer:
begin
repeat
produce an item in nextp；
Swait(empty,mutex)；
buffer(in):=nextp；
in:=(in+1)modn；
Ssignal(mutex,full)；
untilfalse；
end
consumer:
begin
repeat
Swait(full，mutex)；
Nextc:=buffer(out)；
Out:=(out+1) mod n；
Ssignal(mutex，empty)；
consumerthe item in nextc；
untilfalse；
end
parend
end
3．利用管程解决生产者—消费者问题
先建立一个管程,并命名ProceducerConsumer,简称PC。其中包括两个过程：
(1)put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中已有的产品数目，当count≥n时，表示缓冲池已满，生产者须等待。
(2)get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当count≤0时，表示缓冲池中已无可取用的产品，消费者应等待。
PC管程可描述如下：
typeproducer-consumer=monitor
Var in,out,count: integer；
buffer: array[0, …, n-1] ofitem；
notfull，notempty:condition；
procedureentry put(item)
begin
ifcount>=n then notfull.wait；
buffer(in):=nextp；
in:=(in+1)mod n；
count:=count+1；
if notempty.queue thennotempty.signal
end
procedureentry get(item)
begin
ifcount<=0 then notempty.wait；
nextc:=buffer(out)；
out:=(out+1)mod n；
count:=count-1；
if notfull.quenethen notfull.signal；
end
beginin:=out:=0；
count:=0
end
P,C进程调用管程：
producer:
begin
repeat
producean item in nextp；
PC.put(item)；
untilfalse；
end
consumer:
begin
repeat
PC.get(item)；
consumethe item in nextc；
untilfalse；
end
2.5.2 哲学家
进餐问题
问题描述：五个哲学家共用一个圆桌，圆桌上有五个碗和五只筷子，哲学家交替进行思考和进餐，当哲学家饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。
1)进程互斥、同步分析
每个筷子只能由一位哲学家使用，是互斥
2)信号量分析
每个筷子对应一个信号量
1．利用记录型信号量解决哲学家进餐问题
五个筷子对应五个信号量构成信号量数组，其描述如下：
Varchopstick: array[0，…，4] of semaphore；
所有信号量均被初始化为1，第i位哲学家的活动可描述为：
repeat
wait(chopstick[i])；
wait(chopstick[(i+1)mod5])；
eat；
signal(chopstick[i])；
signal(chopstick[(i+1)mod5])；
untilfalse；
采用记录型信号量易导致问题：产生死锁
解决办法：
(1) 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐。
(2) 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。
(3) 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。
2．利用AND信号量集解决哲学家进餐问题
第i个哲学家思考-进餐过程如下：
Varchopsiick array of
semaphore:=(1,1,1,1,1)；
processi
repeat
think；
Sswait(chopstick[(i+1)mod5]，chopstick[i])；
eat；
Ssignat(chopstick[(i+1)mod5]，chopstick[i])；
untilfalse；
2.5.3 读者—写者问题
问题描述：多个读者、写者进程要同时访问一个文件或记录。
原则：1)多个读可同时；
2)多个写不能同时；
3)有写不能读，有读不能写；
1）进程互斥、同步分析：
读、写操作是互斥
2）信号量分析：
wmutex:进程互斥信号量
rmutex:用于访问readcount公共变量的信号量
1．利用记录型信号量解决读者—写者问题
varrmutex，wmutex: semaphore:=1,1；
readcount: integer:=0；
begin
parbegin
Reader:
begin
repeat
wait(rmutex)；
ifreadcount=0 then wait(wmutex)；
readcount:=readcount+1；
signal(rmutex)；
perform read operation；
wait(rmutex)；
readcount:=readcount-1；
ifreadcount=0 then signal(wmutex)；
signal(rmutex)；
untilfalse；
end
Reader:
begin
repeat
wait(wmutex)；
wait(rmutex)；
readcount:=readcount+1；
signal(rmutex)；
perform read operation；
wait(rmutex)；
readcount:=readcount-1；
ifreadcount=0 then signal(wmutex)；
signal(rmutex)；
untilfalse；
end
writer:
begin
repeat
wait(wmutex)；
performwrite operation；
signal(wmutex)；
untilfalse；
end
parend
end
2．利用一般信号量集解决读者—写者问题
1)若最多只允许RN个读者同时读，对应信号量L；
2)对于写、写进程的互斥对应信号量mx；
描述如下：
Var RNinteger；
L，mx:semaphore:=RN,1；
begin
parbegin
reader:
begin
repeat
Swait(L,1,1)；
Swait(mx,1,0)；
performread operation；
Ssignal(L,1)；
untilfalse；
end
writer:
begin
repeat
Swait(mx,1,1；L,RN,0)；
performwrite operation；
Ssignal(mx,1)；
untilfalse；
end
parend
end
