os经典问题.docx
《os经典问题.docx》由会员分享，可在线阅读，更多相关《os经典问题.docx（15页珍藏版）》请在冰点文库上搜索。
os经典问题
第二章TypicalExcises
一生产者-消费者问题扩展
1.扩展一（北大1991）
设有一个可以装A、B两种物品的仓库,其容量无限大，但要求仓库中A、B两种物品的数量满足下述不等式：
-M≤（A物品数量－B物品数量）≤N其中M和N为正整数。
试用信号量和PV操作描述A、B两种物品的入库过程。
问题分析：
若只放入A，而不放入B，则A产品最多可放入N次便被阻塞；若只放入B，而不放入A，则B产品最多可放入M次便被阻塞；每放入一次A，放入产品B的机会也多一次；同理，每放入一次B，放入产品A的机会也多一次。
TheP,VcodeUsingPascal
Semaphoremutex=1，sa=N，sb=M;
cobegin
procedureA:
procedureB:
while（TURE）while（TURE）
beginbegin
p（sa）;p（sb）;
p（mutex）;p（mutex）;
A产品入库；B产品入库；
V（mutex）;V（mutex）;
V（sb）;V（sa）;
endend
coend
2.扩展二（北大1995）
设有一个可以装A、B两种物品的仓库，其容量有限（分别为N），但要求仓库中A、B两种物品的数量满足下述不等式:
-M≤A物品数量－B物品数量≤N
其中M和N为正整数。
另外，还有一个进程消费A,B，一次取一个A，B组装成C。
试用信号量和PV操作描述A、B两种物品的入库过程。
问题分析：
已知条件-M≤A物品数量－B物品数量≤N可以拆成两个不等式，即
A物品数量－B物品数量≤N
B物品数量－A物品数量≤M
这两个不等式的含义是：
仓库中A物品可以比B物品多，但不能超过N个；Ｂ物品可以比A物品多，但不能超过M个。
TheP,VcodeUsingPascal
semaphoremutex=1,a,b=m,empty1,empty2=N,full1,full2=0;
cobegin
process（A）;
process（B）;
process（C）
coend
A物品入库：
processA
begin
while（TRUE）
begin
p（empty1）;
P（a）;
p（mutex）;
2.扩展二（北大1995）
设有一个可以装A、B两种物品的仓库，其容量有限（分别为N），但要求仓库中A、B两种物品的数量满足下述不等式:
-M≤A物品数量－B物品数量≤N
其中M和N为正整数。
另外，还有一个进程消费A,B，一次取一个A，B组装成C。
试用信号量和PV操作描述A、B两种物品的入库过程。
问题分析：
已知条件-M≤A物品数量－B物品数量≤N可以拆成两个不等式，即
A物品数量－B物品数量≤N
B物品数量－A物品数量≤M
这两个不等式的含义是：
仓库中A物品可以比B物品多，但不能超过N个；Ｂ物品可以比A物品多，但不能超过M个。
TheP,VcodeUsingPascal
semaphoremutex=1,a,b=m,empty1,empty2=N,full1,full2=0;
cobegin
process（A）;
process（B）;
process（C）
coend
A物品入库：
processA
begin
while（TRUE）
begin
p（empty1）;
P（a）;
p（mutex）;
3.扩展三
设P,Q,R共享一个缓冲区，P，Q构成一对生产者-消费者，R既为生产者又为消费者。
使用P,V实现其同步。
问题分析：
略。
TheP,VcodeUsingPascal
varmutex,full,empty:
semaphore;
full:
=1;
empty:
=0;
mutex:
=1;
cobegin
ProcedurePProcedureQProcedureR
beginbeginbegin
whiletruewhiletrueifempty:
=1then
p（empty）;p（full）;begin
P（mutex）;P（mutex）;p（empty）;
Productone；consumeone；P（mutex）;
v（mutex）;v（mutex）;product；
v（full）;v（empty）;v（mutex）;
endendv（full）;
end
iffull:
=1then
begin
p（full）; p（mutex）;
消费一个产品； v（mutex）; v（empty）; end
coend
2.读者一写者问题（Readers-WritersProblem）
问题描述：
有一个许多进程共享的数据区，这个数据区的一块空间；有一些只读取这个数据区的进程（Reader）和一程（Writer），此外还需要满足以下条件：
（1）任意多个读进程可以同时读这个文件；
（2）一次只有一个写进程可以往文件中写；
（3）如果一个写进程正在进行操作，禁止任何读进程度文件。
实验要求用信号量来实现读者写者问题的调度算法。
实验类通过P（）、V（）两个方法实现了P、V原语的功能。
实验的任务法以及Writer类的Write方法。
我们需要分两种情况实现该问题：
读优先：
要求指一个读者试图进行读操作时，如果这时正有其直接开始读操作，而不需要等待。
写优先：
一个读者试图进行读操作时，如果有其他写者在等写操作，他要等待该写者完成写操作后才开始读操作。
TheP,VcodeUsingPascal
读者优先算法：
rwmutex用于写者与其他读者/写者互斥的访问共享数据
rmutex用于读者互斥的访问
readcount读者计数器
varrwmutex,rmutex：
semaphore:
=1,1；
intreadcount=0;
cobegin
procedurereader_i
begin//i=1,2,….
P（rmutex）;
Readcount++;if（readcount==1）P（rwmutex）;
V（rmutex）;
读数据；
P（rmutex）;
Readcount--;if（readcount==0）V（rwmutex）;
V（rmutex）;
endprocedureWriter_j
begin//j=1,2,….
P（rwmutex）;
写更新；
V（rwmutex）;
end
Coend
写者优先：
1）多个读者可以同时进行读
2）写者必须互斥（只允许一个写者写，也不能读者写者同时进
3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒如果读者数是固定的，我们可采用下面的算法：
rwmutex：
用于写者与其他读者/写者互斥的访问共享数据
rmutex：
该信号量初始值设为10，表示最多允许10个读者
varrwmutex,rmutex：
semaphore:
=1,10；
cobegin
procedurereader_i
begin//i=1,2,….
P（rwmutex）;//读者、写者互斥
P（rmutex）;
V（rwmutex）;//释放读写互斥信号量，允许其它读、写进程访问资源
读数据；
V（rmutex）;
end
procedureWriter_j
begin//j=1,2,….
P（rwmutex）;
for（i=1;i<=10;i++）P（rmutex）;
//禁止新读者，并等待已进入的读者退出
写更新；
for（i=1;i<=10;i++）V（rmutex）;
//恢复允许rmutex值为10
V（rwmutex）;
end
Coend
问题扩展
如果读者写者均是平等的即二者都不优先，如何实现？
3.哲学家进餐问题
问题描述：
（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。
如何保证哲学家们的动作有序进行？
如：
不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；
TheP,VcodeUsingPascal
解法一：
semaphoreFork[i]:
=1（i=0,1,2,3,4）
begin
Thiking;
Beinghangery;
P（Fork[imod5]）;
p（Fork[（i+1）mod5]）;
Eating;
v（Fork[imod5]）;
v（Fork[（i+1）mod5]）;
end
解法二：
semaphorec[0]?
c[4],初值均为1；
Integeri=0,1,...,4;
procedurephilosopher_i
begin
ifimod2==0then
begin
p（c[i]）;
p（c[i+1]mod5）;
Eating;
v（c[i]）;
v（c[i+1]mod5）;
end
else
begin
p（c[i+1]mod5）;
p（c[i]）;
Eating;
v（c[i+1]mod5）;
v（c[i]）;
end
end
4.理发师问题
作者：
pz整理 来源：
希赛教育 2009年11月13日 发表评论 进入社区
4.理发师问题（BarberProblem）
问题描述：
理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。
TheP,VcodeUsingPascal
1）控制变量waiting用来记录等候理发的顾客数，初值均为0；
2）信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0；
3）信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为0；
4）信号量mutex用于互斥，初值为1
intwaiting=0；//等候理发的顾客数
intchairs=n；//为顾客准备的椅子数
semaphorecustomers=0,barbers=0,mutex=1;
cobegin
barber（）
begin
while（TRUE）;//理完一人,还有顾客吗?
P（cutomers）;//若无顾客,理发师睡眠
P（mutex）;//进程互斥
waiting:
=waiting–1;//等候顾客数少一个
V（barbers）;//理发师去为一个顾客理发
V（mutex）;//开放临界区
cut-hair（）;//正在理发
end
customer（）
begin
P（mutex）;//进程互斥
if（waiting）
begin
waiting:
=waiting+1;//等候顾客数加1
V（customers）;//必要的话唤醒理发师
V（mutex）;//开放临界区
P（barbers）;//无理发师,顾客坐着养神
get-haircut（）;//一个顾客坐下等理/
end
else
V（mutex）;//人满了,走吧!
end
coend
5.吸烟者问题
问题描述：
三个吸烟者在一间房间内，还有一个香烟供应者。
为了制造并抽掉香烟，每个吸烟者需要三样东西：
烟草、纸和火柴。
供应者有丰富的货物提供。
三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。
供应者将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。
当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地）在桌面上，然后唤醒另一个吸烟者。
试为吸烟者和供应者编写程序解决问题。
问题分析：
k供应者seller随即产生两样东西，提供它们，这里用普通变量来表示
k吸烟者进程smoker根据其排号不同，拥有不同的一件东西。
假设1号吸烟者拥有烟草tobacco，2号吸烟者拥有纸paper，3号吸烟者拥有火柴match。
其他号码错误返回。
k吸烟者的序号代表他们拥有的东西，用他们的序号和供应者产生的两样东西比较，如果都不相等，则说明他拥有的东西和供应者产生的东西匹配，它可以吸烟。
如果其中一个相等，则推出，继续排队。
kmutex信号量代表一个只能进入的门，每次只有一个吸烟者可以进入进行比较和吸烟。
k每个吸烟者在吸烟完毕之后出门之前要叫醒供应者，调用seller进程。
TheP,VcodeUsingPascal
vars,S1,S2,S3;semaphore;
S:
=1;S1:
=S2:
=S3:
=0;
fiag1,flag2,fiag3:
Boolean;
fiag1:
=flag2:
=flag3:
=true;
cobegin
process供应者
begin
repeat
P（S）;
取两样香烟原料放桌上，由flagi标记；
//nago1、nage2、nage3代表烟草、纸、火柴
5.吸烟者问题[1]
作者：
pz整理 来源：
希赛教育 2009年11月13日 发表评论 进入社区
5.吸烟者问题（SmokerProblem）
问题描述：
三个吸烟者在一间房间内，还有一个香烟供应者。
为了制造并抽掉香烟，每个吸烟者需要三样东西：
烟草、纸和火柴。
供应者有丰富的货物提供。
三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。
供应者将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。
当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地）在桌面上，然后唤醒另一个吸烟者。
试为吸烟者和供应者编写程序解决问题。
问题分析：
k供应者seller随即产生两样东西，提供它们，这里用普通变量来表示
k吸烟者进程smoker根据其排号不同，拥有不同的一件东西。
假设1号吸烟者拥有烟草tobacco，2号吸烟者拥有纸paper，3号吸烟者拥有火柴match。
其他号码错误返回。
k吸烟者的序号代表他们拥有的东西，用他们的序号和供应者产生的两样东西比较，如果都不相等，则说明他拥有的东西和供应者产生的东西匹配，它可以吸烟。
如果其中一个相等，则推出，继续排队。
kmutex信号量代表一个只能进入的门，每次只有一个吸烟者可以进入进行比较和吸烟。
k每个吸烟者在吸烟完毕之后出门之前要叫醒供应者，调用seller进程。
TheP,VcodeUsingPascal
vars,S1,S2,S3;semaphore;
S:
=1;S1:
=S2:
=S3:
=0;
fiag1,flag2,fiag3:
Boolean;
fiag1:
=flag2:
=flag3:
=true;
cobegin
process供应者
begin
repeat
P（S）;
取两样香烟原料放桌上，由flagi标记；
//nago1、nage2、nage3代表烟草、纸、火柴
ifflag2&flag3thenV（S1）;//供纸和火柴
elseifflag1&fiag3thenV（S2）;//供烟草和火柴
elseV（S3）;//供烟草和纸
untilefalse;
end
process吸烟者1
begin
repeat
P（S1）;
取原料；
做香烟；
V（S）;
吸香烟；
untilefalse;
end
process吸烟者2
begin
repeat
P（S2）;
取原料；
做香烟；
V（S）;
吸香烟；
untilefalse;
end
process吸烟者3
begin
repeat
P（S3）;
取原料；
做香烟；
V（S）;
吸香烟；
untilefalse;
end
coend
升级会员 