进程同步与互斥应用例子.ppt

《进程同步与互斥应用例子.ppt》由会员分享，可在线阅读，更多相关《进程同步与互斥应用例子.ppt（29页珍藏版）》请在三一办公上搜索。

1、进程同步与互斥,例题,进程互斥,进程互斥：并发进程之间相互竞争临界资源的排他性关系。解题步骤：确定临界资源及个数；确定进程的关键工作步（使用临界资源的）；确定信号量的初值(临界资源的个数)；写出伪代码。使用P(wait)操作和V(signal)操作对进程互斥进行控制。,例1：过独木桥。,进程的互斥,P1 P2 由西向东过独木桥；由东向西过独木桥；,P1,P2,分析：进程P1、P2因竞争独木桥这个资源而成为互斥关系。设：信号量m表示独木桥资源，初值为1表示资源可用。int m=1;cobegin p1()/p2()coend,进程的互斥,p1()P(m)；通过独木桥；V(m)；,p2()P(m)

2、；通过独木桥；V(m)；,练习：过十字路口（单道）。,进程的互斥,P1 P2 P3 P4 通过路口；通过路口；通过路口；通过路口；,P2,P3,P4,P1,分析：进程P1、P2、P3、P4因竞争十字路口这个资源而成为互斥关系。设：信号量m表示十字路口资源，初值为1表示资源可用。int m=1;cobegin p1()/p2()/p3()/p4()coend,进程的互斥,p1()P(m)；通过路口；V(m)；,p2()P(m)；通过路口；V(m)；,p3()P(m)；通过路口；V(m)；,p4()P(m)；通过路口；V(m)；,有一个阅览室，共有100个座位。读者进入阅览室时必须在入口处进行登记

3、；离开阅览室时必须进行注销。试用PV操作描述读者进入/离开阅览室的同步与互斥关系。Reader进程登记进入阅览室读书离开阅览室注销,进程的互斥,分析：在入口和出口处读者应该互斥进行登记和注销，100个座位，100个互斥资源设置信号量教室内空座位数量，seat，初值100为入口处进行登记设置互斥信号量Sin，初值 1，表示当前可用为出口处进行注销设置互斥信号量Sout，初值 1，表示当前可用,begin Sin,Sout,seat：semaphore;seat:=100;Sin:=1;Sout:=1;cobeginprocess Reader-i(i=1,2,n);beginP(seat);P(

4、Sin);登记;V(Sin);进入阅览室;读书;离开阅览室;P(Sout);注销;V(Sout);V（seat）;endcoend;end;,问题,若有一售票厅只能容纳300人，当少于300人时，可以进入。否则，需在外等候，若将每一个购票者作为一个进程，请用P、V操作编程。,例2：读写数据库。某数据库有一个写进程、多个读进程，它们之间读、写操作的互斥要求是：写进程运行时，其他读、写进程不能对数据库进行操作。读进程之间不互斥，可以同时读数据库。请用信号量及PV操作描述这一组进程的工作过程。（读者-写者问题）,进程的互斥,数据库,写者,读者,写者 读者 写数据库；读数据库；,分析：写进程write

5、r、读进程reader因竞争数据库这个资源而成为互斥关系。因为写进程执行时，不能执行其他读写进程，所以还必须设置一个计数器统计读进程的个数。如果是第一个读进程，就与写进程竞争数据库。如果是最后一个读进程，就释放数据库。因计数器是一个临界资源，所以多个读进程对计数器的操作又是互斥操作。设：信号量rmutex表示数据库资源，初值为1表示资源可用；wmutex表示计数器count资源，初值为1表示可用。int rmutex=1，wmutex=1;cobegin reader()/writer()coend,进程的互斥,小结进程互斥：进程之间要竞争临界资源。信号量表示临界资源是否可用，或临界资源的数量

6、。信号量的个数与临界资源的个数一致。对同一个信号量的PV操作要在同一个进程中完成。P操作：进入临界区前V操作：离开临界区后,进程的互斥,进程同步,进程同步：并发进程之间相互合作，完成一项工作，它们之间有一定的时序关系。解题步骤：确定进程的个数及每个进程的工作；确定关键工作步（需要控制的）；确定信号量表示的含义，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。写出伪代码。在同步关系的控制中，同一信号量的P(wait)、V(signal)操作成对出现，但它们分别在不同的进程代码中。,例1：假设有三个并发进程P，Q，R，其中P负责从输入设备上读入信息并传送给Q

7、，Q将信息加工后传送给R，R则负责将信息打印输出。进程P、Q共享一个缓冲区，进程Q、R共享另一个缓冲区。,进程的同步,3个进程P、Q、RP进程：从输入设备上读入信息将信息放入缓冲区1Q进程：从缓冲区1取出信息将信息放入缓冲区2中R进程：从缓冲区2取出信息将信息打印输出,确定进程的同步、互斥关系同步：P当缓存区1无数据时，才可以向缓冲区1写入信息同步：Q当缓存区1有数据时，才可以从缓冲区1读取信息同步：Q当缓存区2无数据时，才可以向缓冲区2写入信息同步：R当缓存区2有数据时，才可以从缓冲区2读取信息设置信号量缓存区1无数据，empty1，初值1缓存区1有数据，full1，初值0缓存区2无数据，e

8、mpty2，初值1缓存区2有数据，full2，初值0,process P()while(1)从输入设备上读入信息;P（empty1）;将信息放入缓冲区1；V（full1）;,process Q()while(1)P（full1）;从缓冲区1取出信息;V（empty1）;P（empty2）;将信息放入缓冲区2；V（full2）;,process R()while(1)P（full2）;从缓冲区2取出信息;V（empty2）;将信息打印输出;,进程的同步,例2：公共汽车中的司机和售票员。,司机 P1 售票员 P2 while(true)while(true)启动车辆；关门；正常运行；售票；到站停车

9、；开门；,解法：信号量表示进程能否开始。设信号量m1表示司机进程P1能否启动汽车，初值为0，m2表示售票员进程p2能否开门，初值为0。int m1=0,m20;cobegin p1()/p2()coend,进程的同步,p1()while(1)P(m1);启动汽车；正常行驶；到站停车；V(m2);,p2()while(1)关门；V(m1);售票；(m2);开门；,进程的同步,例3-2：吃水果。,父亲 P1 儿子 P2 女儿 P3 while(true)while(true)while(true)洗水果；取桔子；取苹果；放水果；吃桔子；吃苹果；,桔子,父亲,儿子,女儿,0,苹果,分析：父亲先放水果

10、，儿子女儿再吃水果；儿子女儿取完水果，父亲再放水果，这三个进程是一个同步关系。解法：设信号量m1表示父亲能否放水果，m2表示儿子能否取桔子，m3表示女儿能否取苹果。int m1=1,m2=0,m3=0；cobegin p1()/p2()/p3()coend,进程的同步,p1()while(1)洗水果；P(m1)；放水果；if(是桔子)V(m2)；else V(m3)；,p2()while(1)P(m2)；取桔子；V(m1)；吃桔子；,p3()while(1)P(m3)；取苹果；V(m1)；吃苹果；,进程的同步,例3-3：吃水果。,父亲 P1 母亲 P2 儿子 P3 while(true)whi

11、le(true)while(true)洗桔子；洗苹果；取水果；放桔子；放苹果；吃水果；,0,父亲,儿子,母亲,桔子,苹果,分析：父母亲先放水果，儿子再取水果吃；父亲与儿子，母亲与儿子是一个同步关系，父亲与母亲要竞争空盘子。解法：设信号量m1表示是否有空盘子，信号量m2表示儿子能否取水果。int m1=1,m2=0；cobegin p1()/p2()/p3()coend,进程的同步,p1()while(1)洗桔子；P(m1)；放桔子；V(m2)；,p2()while(1)洗苹果；P(m1)；放苹果；V(m2)；,p3()while(1)P(m2)；取水果；V(m1)；吃水果；,0,进程的同步,例

12、3-4：吃水果。,父亲 P1 母亲 P2 儿子 P3 女儿P4 while(true)while(true)while(true)while(true)洗桔子；洗苹果；取苹果；取桔子；放桔子；放苹果；吃苹果；吃桔子；,桔子,父亲,女儿,母亲,苹果,儿子,分析：父母亲先放水果，儿子女儿再取水果；父亲与女儿，母亲与儿子是一个同步关系，父亲与母亲要竞争空盘子。解法一：设信号量m1表示是否有空盘子，信号量m2表示儿子能否取苹果，m3表示女儿能否取桔子。int m1=1,m2=0,m3=0；cobegin p1()/p2()/p3()/p4()coend,进程的同步,p1()while(1)洗桔子；P(

13、m1)；放桔子；V(m3)；,p2()while(1)洗苹果；P(m1)；放苹果；V(m2)；,p3()while(1)P(m2)；取苹果；V(m1)；吃苹果；,p4()while(1)P(m3)；取桔子；V(m1)；吃桔子；,问题,有一只铁笼子，每次只能放入一只动物，猎手向笼中放入老虎，农民向笼中放入猪，动物园等待取笼中的老虎，饭店等待取笼中的猪，试用P、V操作写出能同步执行的程序。,例4。设有六个进程P1、P2、P3、P4、P5、P6，它们并发执行。由P1开始执行，P6执行后结束。当进程P1执行后，进程P2、P3才能执行；当进程P2执行后，进程P4才能执行；当进程P3执行后，进程P5才能执

14、行；当进程P4、P5都执行后，进程P6才能执行；请用P、V操作编程.,进程的同步,解：这是一个同步问题，信号量初值：S2=0，S3=0，S4=0，S5=0，S6=0 进程P1 进程P2 进程P3 执行P1 P(S2)P(S3)V(S2)执行P2 执行P3 V(S3)V(S4)V(S5)进程P4 进程P5 进程P6P(S4)P(S5)P(S6)执行P4 执行P5 P(S6)V(S6)V(S6)执行P6,进程的同步,小结进程同步有一定的时序关系。信号量表示进程的关键工作是否可以开始或已经结束。信号量的个数与进程的个数一致，有时可以省略部分信号量。对同一个信号量的PV操作不在一个进程中。表示是否可以开始：P自己，V别人,进程的同步,