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

进程同步与互斥 例题 进程互斥 进程互斥： 并发进程之间相互竞争临界资源的排他性关系 。 解题步骤： n 确定临界资源及个数； n 确定进程的关键工作步（使用临界资源的）； n 确定信号量的初值(临界资源的个数)； n 写出伪代码。 使用P(wait)操作和V(signal)操作对进程互斥进 行控制。 例1：过独木桥。 进程的互斥 P1 P2 由西向东过独木桥； 由东向西过独木桥 ； P1 P2 分析：进程P1、P2因竞争独木桥这个资源而成为互斥关系 。 设：信号量m表示独木桥资源，初值为1表示资源可用。 int m=1; cobegin p1() / p2() coend 进程的互斥 p1()p1() P(mP(m) ) ； 通过独木桥；通过独木桥； V(mV(m) ) ； p2()p2() P(mP(m) ) ； 通过独木桥；通过独木桥； V(mV(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()p1() P(mP(m) ) ； 通过路口；通过路口； V(mV(m) ) ； p2()p2() P(mP(m) ) ； 通过路口；通过路口； V(mV(m) )； p3()p3() P(mP(m) ) ； 通过路口；通过路口； V(mV(m) ) ； p4()p4() P(mP(m) ) ； 通过路口；通过路口； V(mV(m) )； 有一个阅览室，共有100个座位。读者进入阅览 室时必须在入口处进行登记；离开阅览室时必 须进行注销。试用PV操作描述读者进入/离开阅 览室的同步与互斥关系。 Reader进程 登记 进入阅览室 读书 离开阅览室 注销 进程的互斥 分析： 在入口和出口处读者应该互斥进行登记和注销， 100个座位，100个互斥资源 设置信号量 教室内空座位数量，seat，初值100 为入口处进行登记设置互斥信号量Sin，初值 1，表 示当前可用 为出口处进行注销设置互斥信号量Sout，初值 1，表 示当前可用 begin Sin, Sout, seat：semaphore; seat :=100; Sin := 1; Sout := 1; cobegin process Reader-i ( i = 1,2,n ); begin P(seat); P(Sin); 登记; V(Sin); 进入阅览室; 读书; 离开阅览室; P(Sout); 注销; V(Sout); V（seat）; end coend; end; 问题 若有一售票厅只能容纳300人，当少于 300人时，可以进入。否则，需在外等候 ， 若将每一个购票者作为一个进程，请用P 、V操作编程。 例2：读写数据库。某数据库有一个写进程、多个读进程，它们之 间读、写操作的互斥要求是：写进程运行时，其他读、写进程不能 对数据库进行操作。读进程之间不互斥，可以同时读数据库。请用 信号量及PV操作描述这一组进程的工作过程。（读者-写者问题） 进程的互斥 数据库 写 者 读 者 写者 读者 写数据库； 读数据库； 分析：写进程writer、读进程reader因竞争数据库这个资 源而成为互斥关系。因为写进程执行时，不能执行其他 读写进程，所以还必须设置一个计数器统计读进程的个 数。如果是第一个读进程，就与写进程竞争数据库。如 果是最后一个读进程，就释放数据库。因计数器是一个 临界资源，所以多个读进程对计数器的操作又是互斥操 作。 设：信号量rmutex表示数据库资源，初值为1表示资源可 用；wmutex表示计数器count资源，初值为1表示可用 。 int rmutex=1，wmutex=1; cobegin reader() / writer() coend 进程的互斥 小结 n进程互斥：进程之间要竞争临界资源。 n信号量表示临界资源是否可用，或临界资源 的数量。 n信号量的个数与临界资源的个数一致。 n对同一个信号量的PV操作要在同一个进程中 完成。 P操作：进入临界区前 V操作：离开临界区后 进程的互斥 进程同步 进程同步： 并发进程之间相互合作，完成一项工作，它们之 间有一定的时序关系。 解题步骤： n 确定进程的个数及每个进程的工作； n 确定关键工作步（需要控制的）； n 确定信号量表示的含义，当信号量的值为0时，表 示期望的消息尚未产生；当信号量的值非0时，表 示期望的消息已经存在。 n 写出伪代码。在同步关系的控制中，同一信号量 的P(wait)、V(signal)操作成对出现，但它们分别 在不同的进程代码中。 例1：假设有三个并发进程P，Q，R，其中P负责从输入设 备上读入信息并传送给Q，Q将信息加工后传送给R，R则 负责将信息打印输出。进程P、Q共享一个缓冲区，进程Q 、R共享另一个缓冲区。 进程的同步 3个进程P、Q、R P进程： 从输入设备上读入信息 将信息放入缓冲区1 Q进程： 从缓冲区1取出信息 将信息放入缓冲区2中 R进程： 从缓冲区2取出信息 将信息打印输出 确定进程的同步、互斥关系 同步：P当缓存区1无数据时，才可以向缓冲区1写入信息 同步：Q当缓存区1有数据时，才可以从缓冲区1读取信息 同步：Q当缓存区2无数据时，才可以向缓冲区2写入信息 同步：R当缓存区2有数据时，才可以从缓冲区2读取信息 设置信号量 缓存区1无数据，empty1，初值1 缓存区1有数据，full1，初值0 缓存区2无数据，empty2，初值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) 启动车辆； 关门； 正常运行； 售票； 到站停车； 开门； 解法：信号量表示进程能否开始。 设信号量m1表示司机进程P1能否启动汽车，初值为0， m2表示售票员进程p2能否开门，初值为0。 int m1=0,m20 ; cobegin p1() / p2() coend 进程的同步 p1()p1() while(1) while(1) P(m1); P(m1); 启动汽车；启动汽车； 正常行驶；正常行驶； 到站停车；到站停车； V(m2);V(m2); p2()p2() while(1) while(1) 关门；关门； V(m1);V(m1); 售票；售票； (m2);(m2); 开门； 开门； 进程的同步 例3-2：吃水果。 父亲 P1 儿子 P2 女儿 P3 while (true) while (true) while(true) 洗水果； 取桔子； 取苹果； 放水果； 吃桔子； 吃苹果； 桔子 父亲 儿子 女儿 0 苹果 分析：父亲先放水果，儿子女儿再吃水果；儿子女儿取完 水果，父亲再放水果，这三个进程是一个同步关系。 解法：设信号量m1表示父亲能否放水果，m2表示儿子能 否取桔子，m3表示女儿能否取苹果。 int m1=1,m2=0,m3=0； cobegin p1() / p2() / p3() coend 进程的同步 p1()p1() while(1) while(1) 洗水果；洗水果； P(m1) P(m1) ； 放水果；放水果； if (if (是桔子是桔子) V(m2) ) V(m2) ； else V(m3)else V(m3)； p2()p2() while(1) while(1) P(m2) P(m2) ； 取桔子；取桔子； V(m1)V(m1)； 吃桔子；吃桔子； p3()p3() while(1) while(1) P(m3) P(m3) ； 取苹果；取苹果； V(m1)V(m1)； 吃苹果；吃苹果； 进程的同步 例3-3：吃水果。 父亲 P1 母亲 P2 儿子 P3 while (true) while (true) while(true) 洗桔子； 洗苹果； 取水果； 放桔子； 放苹果； 吃水果； 0 父亲 儿子 母亲 桔子苹果 分析：父母亲先放水果，儿子再取水果吃；父亲与儿子， 母亲与儿子是一个同步关系，父亲与母亲要竞争空盘子。 解法：设信号量m1表示是否有空盘子，信号量m2表示儿 子能否取水果。 int m1=1,m2=0； cobegin p1() / p2() / p3() coend 进程的同步 p1()p1() while(1) while(1) 洗桔子；洗桔子； P(m1) P(m1) ； 放桔子；放桔子； V(m2) V(m2) ； p2()p2() while(1) while(1) 洗苹果洗苹果 ； P(m1)P(m1)； 放苹果；放苹果； V(m2)V(m2)； p3()p3() while(1) while(1) P(m2) P(m2) ； 取水果；取水果； V(m1)V(m1)； 吃水果；吃水果； 0 进程的同步 例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()p1() while(1) while(1) 洗桔子；洗桔子； P(m1) P(m1) ； 放桔子；放桔子； V(m3) V(m3) ； p2()p2() while(1) while(1) 洗苹果洗苹果 ； P(m1)P(m1)； 放苹果；放苹果； V(m2)V(m2)； p3()p3() while(1) while(1) P(m2) P(m2) ； 取苹果；取苹果； V(m1)V(m1)； 吃苹果；吃苹果； p4()p4() while(1) while(1) P(m3) P(m3) ； 取桔子；取桔子； V(m1)V(m1)； 吃桔子；吃桔子； 问题 有一只铁笼子，每次只能放入一只动物，猎手 向笼中放入老虎，农民向笼中放入猪，动物园 等待取笼中的老虎，饭店等待取笼中的猪，试 用P、V操作写出能同步执行的程序。 例4。设有六个进程P1、P2、P3、P4、P5、P6， 它们并发执行。由P1开始执行，P6执行后结束。 当进程P1执行后，进程P2、P3才能执行；当进程 P2执行后，进程P4才能执行；当进程P3执行后， 进程P5才能执行；当进程P4、P5都执行后，进程 P6才能执行；请用P、V操作编程. 进程的同步 解：这是一个同步问题，信号量初值：S2=0，S3=0，S4=0 ，S5=0，S6=0 进程