一真经之银行排队问题(北京大学2000)
问题描述：
银行有n个柜员,每个顾客进入银行后先取一个号,并且等着叫号,当一个柜员空闲后，就叫下一个号. 问题分析：
将顾客号码排成一个队列,顾客进入银行领取号码后,将号码由队尾插入;柜员空闲时,从队首取得顾客号码,并且为这个顾客服务,由于队列为若干进程共享, 所以需要互斥.柜员空闲时,若有顾客,就叫下一个顾客为之服务.因此,需要设臵一个信号量来记录等待服务的顾客数.
The P,V code Using Pascal
begin
var mutex=1,customer_count=0:semaphore; cobegin
process customer begin repeat 取号码； p(mutex); 进入队列； v(mutex);
v(customer_count); end
process serversi(i=1,...,n) begin repeat
p(customer_count); p(mutex);
从队列中取下一个号码； v(mutex);
为该号码持有者服务； end coend
20
CHAPTER 3. 九阴真经之研究生题辑21
end
_思考：
某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题
(1)用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。
(2)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。 定义信号量S,初值为20，当s > 0时，它表示可以继续进入购票厅的人数，当s = 0时,表示厅内已有20人正在购票，当s < 0时jSj表示正等待进入的人数。
The P,V code Using Pascal
var S:semaphore; S=20; cobegin
procedure P_i: begin p(s); .
Enter and buy ticket; . v(s) end coend
(2)最大值为20，最小值为20-N。
二真经之生产消费问题扩展(浙江大学2001)
假设缓冲区buf1和缓冲区buf2无限大，进程p1向buf1写数据，进程p2向buf2写数据，要求buf1数据个数和buf2数据个数的差保持在(m,n)之间(m 题中没有给出两个进程执行顺序之间的制约关系，只给出了一个数量上的制约关 系，即m·—buf1数据个数－buf2数据个数·n．不需要考虑缓冲区的大小，只需要考虑两个进程的同步和互斥．p2向buf2写数据比p1向buf1写数据的次数最少不超过m次，最多不能超过n次，反之也成立．所以是一个生产者和消费者问题。将等式展开得：(1)m·(buf1数据个数－buf2数据个数)·n; (2)m·(buf2数据个数－buf1数据个数)·n;由于m,n都是正数，等式只有一个成立，不妨设(1)成立．在进程p1和p2都没有运行时，两个缓冲区数据个数之差为0,因此，p1必须先运行，向buf1至少写m+1个数据后再唤醒p2运行．信号量s1表示p1一次写入的最大量,初值为n，s2表示p2一次写入的最大量,初值为-m. The P,V code Using Pascal begin var mutex1=1,mutex2=1,s1=n,s2=-m:semaphore; CHAPTER 3. 九阴真经之研究生题辑22 cobegin process p1 begin repeat get data; p(s1); p(mutex1); 写数据到buf1; v(mutex1); v(s2); end process p2 begin repeat; get data; p(s2); p(mutex2); 写数据到buf2; v(mutex2); v(s1); end coend end _思考： p1和p2每次执行时需要进行一些额外的操作．对于p2来说，它首先必须在自己的 缓冲区buf2中写入至少m个数据，此后p1和p2的同步可简单通过两个信号量来控制．题目的一个变形是要求：-m·(buf2数据个数－buf1数据个数)·n;那么信号量的初值就变成m和n,若只有p1向buf1放入数据而p2不放入数据到buf2中，则p1最多可放m次．因此，设臵信号量s1,初值为m,此外，每当p2放入一个数据到buf2中时，则使信号量s1增１，即p1增加一次放入数据到buf1的机会．反之，若只有p2向buf2放入数据而p1不放入数据到buf1中，则p2最多可放次．因此，设臵信号量s2,初值为n,此外，每当p1放入一个数据到buf1中时，则使信号量s2增１，即p2增加一次放入数据到buf1的机会． The P,V code Using Pascal begin var mutex1=1,mutex2=1,s1=m,s2=n:semaphore; cobegin process p1 begin repeat get data; p(s1); p(mutex1); 写数据到buf1; CHAPTER 3. 九阴真经之研究生题辑23 v(mutex1); v(s2);//p1每放入一个数据到buf1同时使s2增加１ end process p2 begin repeat; get data; p(s2); p(mutex2); 写数据到buf2; v(mutex2); v(s1);//p2每放入一个数据到buf2同时使s1增加１ end coend end 三华南理工2000 一个从键盘输入到打印机输出的数据处理流程图如图所示。其中键盘输入进程通过缓冲区buf1把数绝传送给计算进程，计算进程把处理结果通过buf2传送给打印进程。假设上述两个缓冲区的大小分别为n1和n2，试写出键盘输入进程、计算进程及打印进程间的同步算法。 问题分析： 本题解决的试具有多个缓冲区的生产者和消费者之间的多阶段同步问题。由于每个缓冲区中均有多个存储单元，因而要护持使用。所以要为每个缓冲区设臵一个互斥信号量。 The P,V code Using Pascal Begin var empty1,empty2,full1,full2,mutex1,mutex2:semaphore; empty1:=n1; empty2:=n2; full1:=0; full2:=0; mutex1:=mutex2:=1; cobegin procedure Input procedure Calculate procedure Print_Out begin begin begin Input a data; p(full1); p(full2); p(empty1); p(mutex1); p(mutex2); p(mutex1); Get from buf1; Get Data from buf2; CHAPTER 3. 九阴真经之研究生题辑24 Put to buf1; v(mutex1); v(mutex2); v(mutex1); v(empty1); v(empty2); v(full1); Calculate it; Print out the data; end p(empty2); end p(mutex2); put result to buf2; v(mutex2); v(full2); end coend 四真经之生产者消费者扩展(同济1996) 设有N个计算进程和M个打印进程共享同一个缓冲区，缓冲区长度为8。各计算进程不断地把计算得到的结果送入缓冲区，各打印进程不断的从缓冲区取数并打印。要求：既不漏打，也不重复打印任一个结果。并且，为了高效地工作，计算机进程在使用缓冲区的同时，允许打印进程从缓冲区中取数，反之亦然。请用P、V操作作为同步机制，并用类PASCAL或类C，描述对应于计算进程和打印进程的程序。 五真经之理发师问题扩展(电子科技大学2000) 有一个理发师,一把理发椅和n把供等候理发的顾客坐的椅子,若没有顾客,则理发师睡觉,当一个顾客到来时,必须唤醒理发师进行理发, 若理发师正在理发,又有顾客到来,则若有空椅子可坐就坐下来等,若没有空椅子就离开. 问题分析：需要设臵一个信号量barber,初值为0,用于控制理发师和顾客之间的同步关系.还需要设臵一个信号量customer,初值为0,用于离开顾客与等候顾客之间的同步控制,为了记录等候的顾客数, 应该设臵一个计数器count,初值为0.当一个顾客到达时,需要在count上做加1操作,并根据count值的不同分别采取不同的动作，当顾客离开时,要对count上做减1操作,并根据count值的不同分别采取不同的动作;由于count是共享变量,因此要互斥使用，为此设臵一个互斥信号量mutex; The P,V code Using Pascal begin var barber=0,customer=0,count=0,mutex=1:semaphore; cobegin process barber begin repeat p(customer); p(mutex); count = count -1; v(barber); v(mutex); 理发; until false end CHAPTER 3. 九阴真经之研究生题辑25 process customer begin repeat; p(mutex); if(count 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库os例题在线全文阅读。
相关推荐：