计算机操作系统进程同步算法习题选课件

进程同步算法习题课刘扬【例题1】司机进程：while(1){启动车辆正常驾驶到站停车}…售票员进程：while(1){关门售票开门}…用wait、signal操作解决司机与售票员的问题分析：为保证车辆行驶安全，售票员必须关好车门，然后通知司机启动车辆，在行驶过程中售票员不能打开车门，待车到站停稳后，司机通知售票员才能打开车门，如此不断重复。为此，须设置两个信号量S1，S2用来控制司机和售票员的行为，初值都为0。解:

算法如下：司机进程：while(1){wait(S1)启动车辆正常驾驶

到站停车signal(S2)}…售票员进程：while(1){关门signal(S1)售票wait(S2)开门}…【例题2】1.用wait、signal操作解决下图之同步问题提示：分别考虑对缓冲区S和T的同步，再合并考虑putcopygetst解:设置四个信号量Sin=1，Sout=0，Tin=1，Tout=0；

put：while（1）{wait(Sin）;将数放入S;

signal

(Sout);}

copy：while（1）{

wait

(Sout）;

wait

(Tin）;将数从S取出放入T;

signal

(Tout);

signal

(Sin);}get：while（1）{

wait

(Tout）;将数从T取走;signal(Tin);}思考题：如果S和T是由多个缓冲区组成的缓冲池，上述算法将如何修改？【例题3】桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。 试用wait、signal操作实现爸爸、儿子、女儿三个并发进程的同步。

分析：设置一个信号量S表示空盘子数，一个信号量So表示盘中桔子数，一个信号量Sa表示盘中苹果数，初值分别为1，0，0。解:算法如下：Father(){while(1){

wait(S);将水果放入盘中;if(是桔子)signal(So);elsesignal(Sa);}}Son(){while(1){wait(So)取桔子signal(S);吃桔子;}}Daughter(){while(1){wait(Sa)取苹果signal(S);吃苹果;}}【例题4】有一个仓库，可以存放A和B两种产品，但要求：（1）

每次只能存入一种产品（A或B）（2）

－N＜A产品数量－B产品数量＜M。其中，N和M是正整数。试用wait、signal操作描述产品A与B的入库过程。解:分析：设两个同步信号量Sa、Sb，其中：Sa表示允许A产品比B产品多入库的数量，初值为M-1。Sb表示允许B产品比A产品多入库的数量，初值为N-1。设互斥信号量mutex，初值为1。

B产品入库进程：j=0;while(1){

wait(Sb);wait(mutex);B产品入库

signal(mutex);signal(Sa);消费产品;};A产品入库进程：

i=0;

while(1){

生产产品;

wait(Sa);

wait(mutex);A产品入库

signal(mutex);

signal(Sb);

};算法如下：例题5

进程A1、A2，…An1通过m个缓冲区向进程B1、B2、…Bn2不断发送消息。发送和接收工作遵循下列规则：（1）每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度。（2）对每个消息，B1，B2，…Bn2都须各接收一次，读入各自的数据区内。（3）m个缓冲区都满时，发送进程等待，没有可读消息时，接收进程等待。试用wait、signal操作组织正确的发送和接收工作。分析：每个缓冲区只要写一次但要读n2次，因此，可以看成n2组缓冲区，每个发送者要同时写n2个缓冲区，而每个接收者只要读它自己的缓冲区。Sin[n2]=m；表示每个读进程开始有m个空缓冲区。Sout[n2]=0；表示每个读进程开始有0个可接收的消息。解：先将问题简化：设缓冲区的大小为1有一个发送进程A1有二个接收进程B1、B2设有信号量Sin[1]、Sin[2]初值为1设有信号量Sout[1]、Sout[2]初值为0Bi：while(1){

wait(Sout[i]);

从缓冲区取数signal(Sin[i]);}A1:

while(1){

wait(Sin[1]);

wait(Sin[2]);

将数据放入缓冲区

signal(Sout[1]);signal(Sout[2]);

}向目标前进一步:设缓冲区的大小为m有一个发送进程A1有二个接收进程B1、B2设有信号量Sin[1]、Sin[2]初值为m设有信号量Sout[1]、Sout[2]初值为0Bi：while(1){

wait(Sout[i]);

wait(mutex); 从缓冲区取数

signal(mutex);signal(Sin[i]);};A1:

while(1){

wait(Sin[1]);

wait(Sin[2]);

wait(mutex);

将数据放入缓冲区

signal(mutex);

signal(Sout[1]);signal(Sout[2]);

}到达目标设缓冲区的大小为m有n1个发送进程A1….An1有n2个接收进程B1…Bn2设有n2个信号量Sin[n2]初值均为m设有n2个信号量Sout[n2]初值均为0Bi：while(1){

wait(Sout[i]);

wait(mutex);

从缓冲区取数

signal(mutex);signal(Sin[i]);};Aj:while(1){for(i=1;i<=n2;i++)

wait(Sin[i]);

wait(mutex); 将数据放入缓冲区

signal(mutex);

for(i=1;i<=n2;i++) signal(Sout[2]);}【例题5】复印室里有一个操作员为顾客复印资料，有5把椅子供顾客休息等待复印。如果没有顾客，则操作员休息。当顾客来到复印室时，如果有空椅子则坐下来，并唤醒复印操作员；如果没有空椅子则必须离开复印室。

信号量：customers表示正在等待复印的顾客数量（不包括正在复印的顾客）operator记录正在等候顾客的操作员数，只有1和0mutex用于对waiting的访问;变量：

waiting表示等待的顾客数量。它实际上是customers的一个副本。之所以使用waiting是因为无法读取信号量的当前值。semaphorecustomers=0,operator=0,mutex=1;waiting=0；processoperator()//操作员进程{while(1){wait(customers);//等待顾客到来复印；signal(operator);//通知顾客已经完成复印}}processcusotmeri()//顾客进程i{wait(mutex);if(waiting<5){waiting++;signal(customers);signal(