进程同步算法习题课.ppt

《进程同步算法习题课.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、)}…售票员进程：while(1){关门signal(S1)售票wait(S2)开门}…【例题2】1.用wait、signal操作解决下图之同步问题提示：分别考虑对缓冲区S和T的同步，再合并考虑getcopyputst解:设置四个信号量Sin=1，Sout=0，Tin=1，Tout=0；get：while（1）{wait(Sin）;将数放入S;signal(Sout);}copy：while（1）{wait(Sout）;wait(Tin）;将数从S取出放入T;signal(Tout);signal(Sin

3、);}put：while（1）{wait(Tout）;将数从T取走;signal(Tin);}思考题：如果S和T是由多个缓冲区组成的缓冲池，上述算法将如何修改？【例题3】桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。试用wait、signal操作实现爸爸、儿子、女儿三个并发进程的同步。分析：设置一个信号量S表示空盘子数，一个信号量So表示盘中桔子数，一个信号量Sa表示盘中苹果数，初值分别为1，0，0。解:算法如下：Father(){while

4、(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的入库过程。解:分析：设两

5、个同步信号量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

6、，…An1通过m个缓冲区向进程B1、B2、…Bn2不断发送消息。发送和接收工作遵循下列规则：（1）每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度。（2）对每个消息，B1，B2，…Bn2都须各接收一次，读入各自的数据区内。（3）m个缓冲区都满时，发送进程等待，没有可读消息时，接收进程等待。试用wait、signal操作组织正确的发送和接收工作。分析：每个缓冲区只要写一次但要读n2次，因此，可以看成n2组缓冲区，每个发送者要同时写n2个缓冲区，而每个接收者只要读它自己的缓冲区。Sin[n

7、2]=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(

8、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(mu