操作系统经典问题

操作系统经典问题介绍

一 生产者-消费者问题扩展 1.扩展一

设有一个可以装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的机会也多一次。

The P,V code Using Pascal

Semaphore mutex=1，sa=N，sb=M; cobegin

procedure A: procedure B: while(TURE) while(TURE) begin begin p(sa); p(sb); p(mutex); p(mutex); A产品入库； B产品入库； V(mutex); V(mutex); V(sb); V(sa); end end coend 2.扩展二

设有一个可以装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个。

The P,V code Using Pascal

semaphore mutex=1,a,b=m,empty1,empty2=N,full1,full2=0; cobegin process(A); process(B); process(C) coend

A物品入库： process A begin

while(TRUE) begin p(empty1); P(a);

p(mutex); 2.扩展二

设有一个可以装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个。

The P,V code Using Pascal

semaphore mutex=1,a,b=m,empty1,empty2=N,full1,full2=0; cobegin process(A); process(B); process(C) coend

A物品入库： process A begin

while(TRUE)

begin p(empty1); P(a); p(mutex);

3.扩展三

设P,Q,R共享一个缓冲区，P，Q构成一对生产者-消费者，R既为生产者又

为消费者。使用P,V实现其同步。

问题分析： 略。

The P,V code Using Pascal

var mutex,full,empty:semaphore; full:=1; empty:=0; mutex:=1; cobegin

Procedure P Procedure Q Procedure R begin begin begin while true while true if empty:=1 then p(empty); p(full); begin P(mutex); P(mutex); p(empty); Product one； consume one； P(mutex); v(mutex); v(mutex); product； v(full); v(empty); v(mutex);

end end v(full); end

if full:=1 then

begin

p(full); p(mutex);

消费一个产品；

v(mutex);

v(empty); end

coend

2.读者一写者问题(Readers-Writers Problem)

问题描述：有一个许多进程共享的数据区，这个数据区的一块空间；有一些只读取这个数据区的进程（Reader）和一程(Writer)，此外还需要满足以下条件： （1）任意多个读进程可以同时读这个文件； （2）一次只有一个写进程可以往文件中写；

（3）如果一个写进程正在进行操作，禁止任何读进程度文件。 实验要求用信号量来实现读者写者问题的调度算法。实验类通过P()、V()两个方法实现了P、V原语的功能。实验的任务法以及Writer类的Write方法。 我们需要分两种情况实现该问题：

读优先：要求指一个读者试图进行读操作时，如果这时正有其直接开始读操作，而不需要等待。

写优先：一个读者试图进行读操作时，如果有其他写者在等写操作，他要等待该写者完成写操作后才开始读操作。

The P,V code Using Pascal

读者优先算法：

rwmutex 用于写者与其他读者/写者互斥的访问共享数据 rmutex 用于读者互斥的访问 readcount 读者计数器

var rwmutex,rmutex：semaphore:=1,1； int readcount=0; cobegin

procedure reader_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);

endprocedure Writer_j begin //j=1,2,…. P(rwmutex); 写更新； V(rwmutex); end Coend

写者优先：

1）多个读者可以同时进行读

2）写者必须互斥（只允许一个写者写，也不能读者写者同时进

3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒如果读者数是固定的，我们可采用下面的算法：

rwmutex： 用于写者与其他读者/写者互斥的访问共享数据 rmutex： 该信号量初始值设为10，表示最多允许10个读者 var rwmutex,rmutex：semaphore:=1,10； cobegin

procedure reader_i begin //i=1,2,…. P(rwmutex); //读者、写者互斥 P(rmutex);

V(rwmutex); //释放读写互斥信号量，允许其它读、写进程访问资源 读数据； V(rmutex); end

procedure Writer_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支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；

The P,V code Using Pascal

解法一：

semaphore Fork[i]:=1(i=0,1,2,3,4) begin Thiking; Being hangery; P(Fork[i mod 5]); p(Fork[(i+1)mod 5]); Eating;

v(Fork[i mod 5]); v(Fork[(i+1)mod 5]); end 解法二：

semaphore c[0]?c[4],初值均为1； Integer i=0,1,...,4; procedure philosopher_i begin

if i mod 2==0 then

begin p(c[i]); p(c[i+1]mod 5); Eating; v(c[i]); v(c[i+1]mod 5); end else begin

p(c[i+1]mod 5); p(c[i]); Eating; v(c[i+1]mod 5); v(c[i]); end

end

4.理发师问题

问题描述：

理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。

The P,V code Using Pascal

1)控制变量waiting用来记录等候理发的顾客数，初值均为0；

2)信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0；

3)信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为0；

4)信号量mutex用于互斥，初值为1 int waiting=0；//等候理发的顾客数 int chairs=n；//为顾客准备的椅子数 semaphore customers=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吸烟者的序号代表他们拥有的东西，用他们的序号和供应者产生的两样东西比较，如果都不相等，则说明他拥有的东西和供应者产生的东西匹配，它可以吸烟。如果其中一个相等，则推出，继续排队。

k mutex信号量代表一个只能进入的门，每次只有一个吸烟者可以进入进行比较和吸烟。

k每个吸烟者在吸烟完毕之后出门之前要叫醒供应者，调用seller进程。

The P,V code Using Pascal

var s, 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]

问题描述：

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

k供应者seller随即产生两样东西，提供它们，这里用普通变量来表示 k吸烟者进程smoker根据其排号不同，拥有不同的一件东西。假设1号吸烟者拥有烟草tobacco，2号吸烟者拥有纸paper，3号吸烟者拥有火柴match。其他号码错误返回。

k吸烟者的序号代表他们拥有的东西，用他们的序号和供应者产生的两样东西比较，如果都不相等，则说明他拥有的东西和供应者产生的东西匹配，它可以吸烟。如果其中一个相等，则推出，继续排队。

k mutex信号量代表一个只能进入的门，每次只有一个吸烟者可以进入进行比较和吸烟。

k每个吸烟者在吸烟完毕之后出门之前要叫醒供应者，调用seller进程。 The P,V code Using Pascal

var s, 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 代表烟草、纸、火柴

if flag2&flag3 then V(S1); //供纸和火柴

else if flag1&fiag3 then V(S2); //供烟草和火柴 else V(S3); //供烟草和纸 untile false; end

process吸烟者1 begin repeat P(S1); 取原料； 做香烟；

V(S); 吸香烟； untile false; end

process吸烟者2 begin repeat P(S2); 取原料； 做香烟； V(S); 吸香烟； untile false; end

process吸烟者3 begin repeat P(S3); 取原料； 做香烟； V(S); 吸香烟； untile false; end coend

本文来源：https://www.bwwdw.com/article/5mut.html