进程同步典型例题(操作系统).doc

进程同步练习题
1. 在公共汽车上，司机和售票员的工作流程如图所示。为保证乘客的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。

图 司机和售票员工作流程图
① 约束：怎么密切配合协调工作才能保证安全呢？
a) 关车门之后再启动车辆；利用前驱图解释
b) 到站停车之后再开车门；
② 根据约束定义信号量；
关车门和启动车辆需要一个信号量进行同步S1；到站停车和开车门之间需要一个信号量进行同步S2；
③ 建立几个进程呢？
a) 为司机建立一个进程Driver；
b) 为售票员建立一个进程Conductor；
Driver：
Repeat
启动车辆；
正常行驶；
到站停车；
Until false;
Conductor：
Repeat
关车门；
售票；
开车门；
Until false;

④ 加入同步关系：
Var s1,s2:semorphore=0,0;
Driver：
Repeat
Wait (s1);
启动车辆；
正常行驶；
到站停车；
Signal(s2)
Until false;
Conductor：
Repeat
关车门；
Signal(s1);
售票；
Wait(s2)
开车门；
Until false;
main()
{
Driver();
Conductor ();
}
2. 桌子上有一只盘子，盘子中只能放一只水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用PV操作实现他们之间的同步机制。
分析：
①约束：
a) 爸爸和妈妈竞争盘子，往盘子放水果，爸爸在放时，妈妈等待，或者相反；
b) 爸爸和女儿要同步，即爸爸放完苹果之后通知女儿来吃；同时女儿吃完之后要通知盘子可用；
c) 妈妈和儿子要同步，即妈妈放完橘子之后通知儿子来吃；同时儿子吃完之后要通知盘子可用；
② 经上述分析可知：
需要3个信号量：S1表示临界资源盘子，初值1；爸爸和女儿需要一个信号量进行同步S2=0
妈妈和儿子需要一个信号量进行同步S3=0;
③ 建立进程？
爸爸： 妈妈： 女儿： 儿子：
Repeat repeat repeat repeat
取一个苹果； 取一个橘子； 从盘子取一个苹果； 从盘子取一个橘子；
放入盘子； 放入盘子 吃苹果； 吃橘子；
Until false; Until false; Until false; Until false;
④ 加入同步关系。
爸爸： 妈妈： 女儿： 儿子：
Repeat repeat repeat repeat
wait(S2); wait(S3);
取一个苹果； 取一个橘子； 从盘子取一个苹果； 从盘子取一个橘子；
Wait(S1); Wait(S1); signal(S1); signal(S1);
放入盘子； 放入盘子 吃苹果； 吃橘子；
Signal(S2); Signal(S3);
Until false; Until false; Until false; Until false;

3. a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：
（1）当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；
（2）当ab之间无车辆在行驶时，到达a点（或b点）的车辆可以进入ab段，但不能从a点和b点同时驶入；
（3）当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。
请用信号量为工具，对ab段实现正确管理以保证行驶安全。
分析：
① 约束：
a) ab两点的单行车道是一种临界资源；两端的车辆对该资源进行竞争；
b) 同步关系：（1），（3）；
② 经上述分析可知：
首先，设置互斥信号量Sab=1，用于a、b点的车辆互斥进入ab段；
然后，分别设置共享变量ab=0用于记录当前ab段上由a点进入的车辆数量；共享变量ba=0用于记录当前ab=段上由b点进入车辆的数量；
最后，设置互斥信号量S1=1用于ab段的车辆互斥访问共享变量ab；设置互斥信号量S2=1用于ba段的车辆互斥访问共享变量ba
③建立进程？
semaphore S1=1,S2=1,Sab=1;
int ab=ba=0;
Pab： pba：
Repeat repeat
Wait(S1) Wait(s2)
abcount=abcount+1; bacount=bacount+1;
if abcount=1 then wait(sab) if bacount==1 then wait(sab)
signal(S1) signal(s2)
进入车道行驶； 进入车道行驶；
Wait(s1) Wait(s2)
abcount=abcount-1; bacount=bacount-1;
if abcount==0 then signal(sab) if bacount==0 then signalsab)
signal(s1) signal(s2);
until false; until false;
main()
{
Pab();
Pba();
}

5．一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。
分析：
① 约束：
a) 桥属于临界资源，两岸的人对该资源进行竞争；
b) 桥上的人数是有限制的，设这个桥由N个桥墩构成，桥上同时只能有N个人过桥，其它人要进行等待。相当于共享资源数。
② 设置信号量
信号量s：互斥使用桥，初值为1
变量count1：方向1上过河人计数器
变量count2：方向2上过河人计数器
信号量scount1：对方向1上过河人计数器count1的互斥使用，初值为1
信号量scount2：对方向2上过河人计数器count2的互斥使用，初值为1
信号量scount：代表桥上过河人的计数信号量，初值为桥墩个数N
③ 建立进程
Semaphore s, scount1, scount2, scount;
int count1, count2;
s=1; scount1=1; scount2=1; scount=N;
count1=0; count2=0;

void direct1(int i)
{
wait(scount1);
count1++;
if(count1==1)
wait(s);
signal(scount1);

wait(scount);
上桥，过桥，下桥；
signal(scount);

wait(scount1);
count1--;
if(count1==0)
signals);
signal(scount1);
}

void direct2(int i)
{
wait(scount2);
count2++;
if(count2==1)
wait(s);
signal(scount2);

wait(scount);
上桥，过桥，下桥；
signal(scount);

wait(scount2);
count2--;
if(count2==0)
signal(s);
signal(scount2);
}

main()
{
cobegin{
direct1(1)
…
direct1(n);
direct2(1);
…
direct2(m);
}
}
6．有一个仓库，可以存放A和B两种产品，但要求：
（1）每次只能存入一种产品（A或B）；
（2）-N＜A产品数量－B产品数量＜M。其中，N和M是正整数。
试用同步算法描述产品A与产品B的入库过程。
分析：
① 约束：
a) 仓库是一种临界资源，两种产品为之竞争；
b) A产品数量不能比B产品数量多M个以上即A产品数量比B产品数量最多多M-1个；A产品数量不能比B产品数量少N个以上即B产品数量比A产品最多多N-1个。
② 设置信号量
设置互斥信号量mutex互斥使用仓库；
设置两个信号量来控制A、B产品的存放数量，
sa表示当前允许A产品比B产品多入库的数量（当前允许A产品入库数量）；
sb表示当前允许B产品比A产品多入库的数量（当前允许B产品入库数量）。
初始时，sa为M一1，sb为N一1。当往库中存放入一个A产品时，则允许存入B产品的数量也增加1;当往库中存放入一个B产品时，则允许存入A产品的数量也增加1。
③ 建立进程
semaphore mutex=1，sa=M-1， sb=N-1;
process puta()
{ while(1)
{ 取一个产品；
wait(sa);
wait(mutex);
将产品入库；
signal(mutex);
signal(sb);
}
}
process putb()
{ while(1)
{ 取一个产品；
wait(sb);
wait(mutex);
将产品入库；
signal(mutex);
signal(sa);
}
}
main()
{ cobegin{
puta();
putb();
}
}

4．将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写者”与其他“读者”或“写者”同时访问数据。另外，要保证：一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。试用P、V操作正确实现“读者”与“写者”的同步。（第二类读者写者问题，信号量解决方法）

分析：
① 约束：
a) 写者与写者之间需要互斥访问；
b) 读者与写者之间需要互斥；（有一个读者在读就让写者等待），因此，此时需要一个计数变量记录读者的数量。
c) 允许多个读者同时读数据；
d) 一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。
② 建立进程
Write:
Repeat
执行读操作
Until false;
Read:
Repeat
执行写操作；
Until false;
③ 设置信号量
a) 设置互斥信号量mutex=1实现写者与写者之间的互斥访问；
Write:
Repeat
Wait(mutex)
执行读操作；
Signal(mutex);
Until false;

b) 实现读者与写者之间的互斥，设置整型变量readcount=0记录读者数量，if readcount==1 then wait(mutex)
Read：
Repeat
readcount++;
if(readcount==1) wait(mutex);

执行读操作；

readcount- -;
if(readcount==0) signal(mutex);
until false;
由于readcount 是共享变量，所以读者之间要互斥访问，因此设置一个互斥信号量rmutex=1.
Read：
Repeat
Wait(rmutex)
readcount++;
if(readcount==1) wait(mutex);
signal(rmutex)
执行读操作；
Wait(rmutex)
readcount- -;
if(readcount==0) signal(mutex);
signalrmutex)
until false;

c) 要想实现d）的互斥，需让读者和写者再共享一个互斥信号量s，因此设置互斥信号量s=1，一旦有写者等待时，就wait（s）让读者等待。
Write:
Repeat
wait(wmutex);
writecount++;
if(writecount==1) wait(s);
signal(wmutex);

Wait(mutex)
执行读操作；
Signal(mutex);

wait(wmutex);
writecount- -;
if(writecount==0)signal(s);
signal(wmutex);

Until false;

Read：
Repeat
Wait(s);
Wait(rmutex)
readcount++;
if(readcount==1) wait(mutex);
signal(rmutex)
signal(s);
执行读操作；
Wait(rmutex)
readcount- -;
if(readcount==0) signal(mutex);
signal(rmutex)
until false;

④ 完整代码
Process reader()
{ while(1)
{
wait(s)
wait(rmutex);
if(readcount==0)wait(mutex);
readcount++;
signal(rmutex);
signal(s);

perform read operation;

wait(rmutex);
readcount- -;
if(readcount==0)signal(mutex);
signal(rmutex);
}
}
Process writer()
{ while(1)
{
wait(wmutex);
writecount++;
if(writecount==1) wait(s);

signal(wmutex);
wait(mutex);
perform write operation;
signal(mutex);

wait(wmutex);
writecount- -;
if(writecount==0)signal(s);
signal(wmutex);
}
}
Main( )
{
cobegin
{ reader();
writer();
}
}

1、在公共汽车上，司机和售票员的工作流程如图所示。为保证乘客的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。

图 司机和售票员工作流程图

【答案】
设置两个资源信号量：S1、S2。 S1表示是否允许司机启动汽车，其初值为0；S2表示是否允许售票员开门，其初值为0.
semaphoere S1=S2=0;
void Driver()
{
while(1)
{
wait(S1);
启动车辆；
正常行车；
到站停车；
signal(S2);
}
}
void Busman()
{
while(1)
{
关车门；
signal(S1)；
售票；
wait(S2)；
开车门；
}
}
main()
{
cobegin{
Driver();
Busman();
}
}
2. 桌子上有一只盘子，盘子中只能放一只水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用PV操作实现他们之间的同步机制。
【答案】
信号量S用来实现盘子的互斥访问，S1表示盘子中苹果个数，S2表示盘子中橘子的个数。
semaphore S=1,S1=S2=0;
void father()
{
while(1)
{
准备苹果;
wait(S);
将苹果放在盘子内；
signal(S1);
}
}
void mother()
{
while(1)
{
准备橘子;
wait(S);
将橘子放在盘子内；
signal(S2);
}
}
void daughter()
{
while(1)
{
wait(Sl);
从盘子里拿走苹果；
signal(S);
吃苹果;
}
}
void son()
{
while(1)
{
wait(S2);
从盘子里拿走橘子；
signal(S);
吃橘子;
}
}
main()
{
cobegin{
father();
mother();
daughter();
son();
}
}

3. a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：
（1）当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；
（2）当ab之间无车辆在行驶时，到达a点（或b点）的车辆可以进入ab段，但不能从a点和b点同时驶入；
（3）当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。
请用信号量为工具，对ab段实现正确管理以保证行驶安全。
【答案】
此题是读者-写者问题的变形。设置3个信号量S1、S2和Sab，分别用于从a点进入的车互斥访问共享变量ab（用于记录当前ab段上由a点进入车辆的数量），从b点进入的车互斥访问共享变量ba（用于记录当前ab段上由b点进入车辆的数量）和a、b点的车辆互斥进入ab段。3个信号量的初值分别为1、1和1，两个共享变量ab和ba的初值分别为0、0。
semaphore S1=1,S2=1,Sab=1;
int ab=ba=0;
void Pab()
{
while(1)
{
wait(S1);
if(ab==0)
wait(Sab);
ab=ab+1;
signal(S1);
车辆从a点驶向b点;
wait(S1);
ab=ab-1;
if(ab==0)
signal(Sab);
signal(S1);
}
}
void Pba()
{
while(1)
{
wait(S2);
if(ba==0)
wait(Sab);
ba=ba+1;
signal(S2);
车辆从b点驶向a点;
wait(S2);
ba=ba-1;
if(ba==0)
signal(Sab);
signal(S2);
}
}
main()
{
cobegin{
Pab();
Pba();
}
}

4. 将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写者”与其他“读者”或“写者”同时访问数据。另外，要保证：一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。试用P、V操作正确实现“读者”与“写者”的同步。（第二类读者写者问题，信号量解决方法）
【答案】
为了使写者优先，可在原来的读优先算法的基础上增加一个互斥信号量s，初值为1，使得当至少有一个写者准备访问共享对象时，它可以使后续的读者进程等待；
整型变量writecount，初值为0，用来对写者进行计数；
互斥信号量wmutex，初值为1，用来实现多个写者对writecount进行互斥访问。
Process reader()
{ while(1)
{
wait(s);
wait(rmutex);
if(readcount==0)wait(mutex);
readcount++;
signal(rmutex);
signal(s);

perform read operation;

wait(rmutex);
readcount--;
if(readcount==0)signal(mutex);
signal(rmutex);
}
}
Process writer()
{ while(1)
{
wait(wmutex);
if(writecount==0)wait(s);
writecount++;
signal(wmutex);

wait(mutex);
perform write operation;
signal(mutex);

wait(wmutex);
writecount--;
if(writecount==0)signal(s);
signal(wmutex);
}
}
Main( )
{
cobegin
{ reader();
writer();
}
}

5. 一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。
【答案】
信号量s：互斥使用桥，初值为1
信号量scount1：对方向1上过河人计数器count1的互斥使用，初值为1
信号量scount2：对方向2上过河人计数器count2的互斥使用，初值为1
信号量scount：代表桥上过河人的计数信号量，初值为桥墩个数N
变量count1：方向1上过河人计数器
变量count2：方向2上过河人计数器
Semaphore s, scount1, scount2, scount;
int count1, count2;
s=1; scount1=1; scount2=1; scount=N;
count1=0; count2=0;

void direct1(int i)
{
wait(scount1);
if(count1==0)
wait(s);
count1++;
signal(scount1);

wait(scount);
上桥，过桥，下桥；
signal(scount);

wait(scount1);
count1--;
if(count1==0)
signal(s);
signal(scount1);
}

void direct2(int i)
{
wait(scount2);
if(count2==0)
wait(s);
count2++;
signal(scount2);

wait(scount);
上桥，过桥，下桥；
signal(scount);

wait(scount2);
count2--;
if(count2==0)
signal(s);
signal(scount2);
}

main()
{
cobegin{
direct1(1);
…
direct1(n);
direct2(1);
…
direct2(m);
}
}

6、有一个仓库，可以存放A和B两种产品，但要求：（1）每次只能存入一种产品（A或B）；（2）-N＜A产品数量－B产品数量＜M。其中，N和M是正整数。试用同步算法描述产品A与产品B的入库过程。
【答案】
A产品的数量不能比B产品的数量少N个以上，A产品的数量不能比B产品的数量多M个以上．
设置两个信号量来控制A、B产品的存放数量，sa表示当前允许A产品比B产品多入库的数量（当前允许A产品入库数量），即在当前库存量和B产品不入库的情况下，还可以允许sa个A产品入库；
sb表示当前允许B产品比A产品多入库的数量（当前允许B产品入库数量），即在当前库存量和A产品不入库的情况下，还可以允许sb个B产品入库。
初始时，sa为M一1，sb为N一1。当往库中存放入一个A产品时，则允许存入B产品的数量也增加1;当往库中存放入一个B产品时，则允许存入A产品的数量也增加1。

semaphore mutex=1，sa=M-1， sb=N-1;
process puta()
{ while(1)
{ 取一个产品；
wait(sa);
wait(mutex);
将产品入库；
signal(mutex);
signal(sb);
}
}
process putb()
{ while(1)
{ 取一个产品；
wait(sb);
wait(mutex);
将产品入库；
signal(mutex);
signal(sa);
}
}
main()
{ cobegin{
puta();
putb();
}
}