操作系统生产与消费者问题.docx

一、 生产者和消费者问题
1、有n个缓冲区，一个生产者和一个消费者情况：

main ()
{ int S=1; //可否进入缓冲区
int full=0; //产品数目
int empty=n //可用缓冲区数
int buffer[n];
int in=0; //指向下一个可放产品的缓冲区
int out=0; //指向下一个可取产品的缓冲区
producer();
consumer();
}

producer()
{
While(生产未结束)
{ produce a product
P(empty);
P(S);
Buffer[in]= product;
in=(in+1)mod n;
V(S);
V(full);
}
}

consumer()
{
While(消费未结束)
{ P(full);
P(S);
Take a product from Buffer[out]
Out=(out+1)mod n;
V(S);
V(empty);
}
Consume the product
}

2、 m个生产者和k个消费者共享n个缓冲区的情况：

main()
{
int B[n]; //缓冲区
int p=r=0; //p表示生产者指针， r表示消费者指针
int S=1; //可否进入缓冲区
int full=0; //产品数目
int empty=n; //可用缓冲区数
producer-i(i=1,2,…,m);
consumer-j(j=1,2,…,k);
}

Producer-i(i=1,2,…,m)
{
while (producing does not end )
{
produce a product
P(empty);
P(S);
B[p]=product;
p=(p+1)mod n; //每放入一个产品，位置指针后移一位
V(S);
V(full);
}
}

Consumer-j(j=1,2,…,k)
{
while (continue to consume)
{
P(full);
P(S);
Take a product from B[r]
r=(r+1)mod n; // 从第一个开始，消费一个后，指向下一个
V(S);
V(empty);
Consume
}
}

二、 读者与写者问题
1、 读者与写者有相同的优先级的情况：

main()
{
int S=1; //读者与写者，写者与写者间的互斥，即可否修改文件
int Sr=1; //可否修改读者个数
int rc=0; //读者个数
reader();
writer();
}

reader()
{
While(读过程未结束)
{
P(Sr);
if( rc==0)
{ P(S);
rc=rc+1;
V(Sr);
read file F
}

else
{
rc=rc+1;
V(Sr);
read file F
}
P(Sr);
rc=rc-1;
if(rc==0) V(S);
V(Sr);
}
}

writer()
{
While(写过程未结束)
{
P(S);
Write file F
V(S);
}
}

2、写者优先问题：

main()
{
int S=1; //读者与写者，写者与写者间的互斥，即可否修改文件
int Sn=n; //最多有n个进程可以同时进行读操作
reader();
writer()
}

reader(i)
{
P(S);
P(Sn);
V(S);
Read file F
V(Sn);
}

writer(j)
{
P(S)
Write file F
V(S);
}
例题
1、 有一个阅览室，读者进入时必须先在一张登记表上进行登记。该表为每一座位列出一个表目，包括座号、姓名。读者离开时要撤消登记信息。阅览室有100个座位，试问：
（1） 为描述读者的动作，应编写几个程序？，应该设置几个进程？进程和程序之间的关系如何？
（2） 试用P、V操作描述这些进程之间的同步算法。

2、 若系统有某类资源m*n+1个，允许作业执行过程中动态申请该类资源，但在该系统上运行的每一个作业对该类资源的占有量在任一时刻都不会超过m+1个。当作业申请资源时，只要资源尚未分配完，则总能满足它的要求。但用限制系统中可同时执行的作业个数来防止死锁。你认为作业调度允许同时执行的最大作业数应为多少？证明之。

3、若系统有同类资源m个，被n个进程共享，试问：当m>n和m<n，每个进程最多可申请多少个这类资源而使系统一定不会发生死锁？

S
F
Pa
Pb
Pc
4、设Pa, Pb, Pc为一组合作进程，其进程流程图如下所示。试用信号灯的P、V操作实现这三个进程的同步。

5、医生给病人看病，需要化验，于是医生开出化验单，病人到化验室化验，化验结果送回医生处供医生诊断。医生看病为一个进程，化验室化验为一个进程，二者需要交换信息，试用信号灯的P、V操作实现这两个进程的同步关系。

6、设有两个优先级相同的进程P1、P2如下：令信号量S1, S2的初值为0，试问P1、P2并发运行结束后X=? y=? z=?
进程P1 进程P2
y=1; x=1;
y=y+2; x=x+1;
V(S1); P(S1);
Z=y+1; x=x+y;
P(S2); V(S2);
Y=z+y; z=x+z;

7、在一个盒子里，混装了数量相等的围棋白子和黑子。现在要用自动分拣系统把白子和黑子分开。该系统设有两个进程P1、P2，其中P1将拣白子，P2将拣黑子。规定每个进程每次只拣一子。当一进程正在拣子时，不允许另一进程去拣，当一进程拣了一子时，必须让另一进程去拣。试写出两个并发进程能正确执行的程序。

8、桌上有一只盘子，每次只能放入一个水果。爸爸专向盘中放苹果，妈妈专向盘中放橘子，一个女儿专等吃盘中的苹果，一个儿子专等吃盘中的橘子。试用P、V操作写出他们能同步的程序。

Main()
{
Int Sp=1; // 是否有空盘子
Int Sa=0; // 盘中是否有苹果
Int So=0; // 盘中是否有橘子
Pf( );
Pm( );
Pd( );
Ps( );
}

Pf( )
{
P(Sp);
向盘中放苹果;
V(Sa);
}

Pm( )
{
P(Sp);
向盘中放橘子;
V(So);
}

Pd( )
{
P(Sa);
取盘中的苹果;
V(Sp);
}

Ps( )
{
P(So);
取盘中的橘子;
V(Sp);
}

9、桌上有一只盘子，最多可容纳两个水果。每次只能放入一个或取出一个水果。爸爸专向盘中放苹果，妈妈专向盘中放橘子，两个女儿专等吃盘中的苹果，两个儿子专等吃盘中的橘子。试用P、V操作写出他们能同步与互斥的程序。（南京大学）

Main()
{
Int S=1; // 是否可以更改盘子内的空间数
Int empty=2; // 盘子内的初始空间数
Int Sa=0; // 盘中是否有苹果
Int So=0; // 盘中是否有橘子
Pf( );
Pm( );
Pd_i( );
Ps_j( );
}

Pf( )
{
P(empty);
P(S);
向盘中放苹果;
V(S);
V(Sa);
}

Pm( )
{
P(empty);
P(S);
向盘中放橘子;
V(S);
V(So);
}

Pd_i( )
{
P(Sa);
P(S);
取盘中的苹果;
V(S);
V(empty);
}

Ps_j( )
{
P(So);
P(S);
取盘中的橘子;
V(S);
V(empty);
}

10、某寺庙，有小和尚、老和尚若干。有一水缸，由小和尚提水入缸，老和尚从缸中取水饮用。水缸可容纳10桶水，水取自同一水井中，水井径窄，每次只能容一个水桶取水。水桶总数为3个，每次入、取缸水仅为1桶，且不可同时进行。试给出取水、入水的算法描述。
（北京邮电大学）

Main( )
{
Int mutex1=1; //是否可以使用水井
Int mutex2=1; //是否可以使用水缸
Int empty=10; //水缸初始空间数
Int full=0; //水缸满否
Int count=3; //水桶初始个数
Pin_i( ); //入水进程
Pout_j( ); //取水进程
}

Pin_i( )
{
P(empty); //水缸满否？满则阻塞入水进程
P(count); //申请打水的桶
P(mutex1); //互斥使用水井
从井中取水
V(mutex1);
P(mutex2); //互斥使用水缸
向缸中入水
V(mutex2);
V(full); //水缸多了一桶水
V(count); //归还水桶
}

Pout_j( )
{
P(full); 水缸是否有水？无则阻塞取水进程
P(count); //申请取水的桶
P(mutex2); //互斥使用水缸
从缸中取水
V(mutex2);
V(empty); //水缸少了一桶水
V(count); //归还水桶
}

11、有一个理发师，有n张可供顾客等待理发的椅子，如果没有顾客，则理发师睡觉；如果有一顾客进入理发店发现理发师在睡觉，则把他叫醒进行理发，如果理发师正在理发时又有顾客来到，若有空椅子，就在空椅子上等待，若没有空椅子就离开理发店。写一个算法描述理发师和顾客之间的关系。要求不能带有竞争条件。（西安电子科技大学）
Main( )
{
Int mutex=1; //可否修改顾客数
Int wakeup=0; //理发师等唤醒的信号
Int wait=0; //顾客是否可以等待
Int rc=0; //初始顾客数
P1( ); //顾客进程
P2( ); //理发师进程
}
P1( )
{
P(mutex); //可否修改顾客数
rc=rc+1;
if (rc==1) //如果是第一个顾客就唤醒理发师
V(wakeup);
else
{
if (rc<=n) //当顾客人数少于n时，在椅子上等待
P(wait);
else
{
rc=rc-1;
该顾客离开理发店
}
}
V(mutex);
}

P2( )
{
P(wakeup); //理发师睡觉，等待被唤醒
While(rc!=0)
{
理发
P(mutex);
rc=rc-1;
if(rc!=0)
V(wait); //让等待中的一个顾客理发
V(mutex);
}
}

12、如何让五个哲学家吃通心面问题满足同步机制。
解： 改变5个哲学家申请叉子的顺序。规定奇数号的哲学家先拿起他左边的叉子，然后再去拿右边的叉子；偶数号的哲学家则正好相反。即：拿到一个叉子的哲学家才有权拿另一个叉子，而没有拿到叉子的哲学家则退出竞争。
Pi(i=0,1,2,3,4) ( )
{
Think for a while
if(odd(i)) //若为奇数号
{
P(fork(i+1)MOD5);
P(fork(i));
}
else
{
P(fork(i));
P(fork(i+1)MOD5);
}
Eat for a while
V (fork(i));
V(fork(i+1)MOD5);
}