进程同步算法习题课

进程同步算法习题课,【例题1】,用wait、signal操作解决司机与售票员的问题,分析：为保证车辆行驶安全，售票员必须关好车门，然后通知司机启动车辆，在行驶过程中售票员不能打开车门，待车到站停稳后，司机通知售票员才能打开车门，如此不断重复。为此，须设置两个信号量S1，S2用来控制司机和售票员的行为，初值都为0。,解:算法如下：,司机进程：while(1)wait(S1)启动车辆正常驾驶到站停车signal(S2),售票员进程：while(1)关门signal(S1)售票wait(S2)开门,【例题2】,1.用wait、signal操作解决下图之同步问题提示：分别考虑对缓冲区S和T的同步，再合并考虑,get,copy,put,s,t,解:,设置四个信号量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);,put：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）NA产品数量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个缓冲区，而每个接收者只要读它自己的缓冲区。Sinn2=m；表示每个读进程开始有m个空缓冲区。Soutn2=0；表示每个读进程开始有0个可接收的消息。,解：,先将问题简化：设缓冲区的大小为1有一个发送进程A1有二个接收进程B1、B2设有信号量Sin1、Sin2初值为1设有信号量Sout1、Sout2初值为0,Bi：while(1)wait(Souti);从缓冲区取数signal(Sini);,A1:while(1)wait(Sin1);wait(Sin2);将数据放入缓冲区signal(Sout1);signal(Sout2);,向目标前进一步:,设缓冲区的大小为m有一个发送进程A1有二个接收进程B1、B2设有信号量Sin1、Sin2初值为m设有信号量Sout1、Sout2初值为0,Bi：while(1)wait(Souti);wait(mutex);从缓冲区取数signal(mutex);signal(Sini);,A1:while(1)wait(Sin1);wait(Sin2);wait(mutex);将数据放入缓冲区signal(mutex);signal(Sout1);signal(Sout2);,到达目标,设缓冲区的大小为m有n1个发送进程A1.An1有n2个接收进程B1Bn2设有n2个信号量Sinn2初值均为m设有n2个信号量Soutn2初值均为0,Bi：while(1)wait(Souti);wait(mutex);从缓冲区取数signal(mutex);signal(Sini);,Aj:while(1)for(i=1;i=n2;i+)wait(Sini);wait(mutex);将数据放入缓冲区signal(mutex);for(i=1;i=n2;i+)signal(Souti);,例题6,假设有一影院有1、2、3种不同的影片由观众选择放映。放映规则是：（1）任一时刻只放映一种影片，正在放映的影片是自动循环放映的，最后一个观众离开时结束当前影片的放映。（2）选择当前正在放映影片的观众可立即进入观看，观众人数不受限制。（3）等待观看其他影片的观众按到达顺序排队，当新的影片放映时，等待该影片的观众可依次进入观看。用一进程代表观众，试用信号量机制实现观众进程。,分析：影院一次只能放一部影片，希望观看的观众可能有不同的爱好，但每次只能满足部分观众的需求，希望观看另外两部影片的观众只能等待。分别为三部影片设置三个信号量s1、s2、s3，初值都为1。影院一次只能放一部影片，需设一互斥信号量mutex。由于同时观看影片的人有多个，因此须分别设置三个计数器count1、count2、count3，初值都为0，以统计观众人数，计数器是共享变量须互斥使用。,Vermutex,s1,s2,s3:semapore=1,1,1,1;Vercount1,count2,count3=0,0,0;Processvideoshow1/观看影片1的观众进程beginrepeatwait(s1);/观看影片1的观众进入影院count1=count1+1;if(count1=1)thenwait(m