Chapter+6+进程同步与互斥应用例子

1、进程同步与互斥进程同步与互斥 例题 进程互斥 进程互斥进程互斥： 并发进程之间相互竞争临界资源的排他性关系。并发进程之间相互竞争临界资源的排他性关系。 解题步骤解题步骤： n 确定临界资源及确定临界资源及个数个数； n 确定进程的确定进程的关键工作步关键工作步（使用临界资源的）；（使用临界资源的）； n 确定信号量的初值确定信号量的初值(临界资源的个数临界资源的个数)； n 写出写出伪代码伪代码。 使用使用P(wait)操作和操作和V(signal)操作对进程互斥进操作对进程互斥进 行控制。行控制。 例例1：过独木桥。：过独木桥。 进程的互斥进程的互斥 P1 P2 由西向东过独木桥；由西向东过

2、独木桥； 由东向西过独木桥；由东向西过独木桥； P1 P2 分析分析：进程：进程P1、P2因竞争独木桥这个资源而成为互斥关系。因竞争独木桥这个资源而成为互斥关系。 设设：信号量：信号量m表示独木桥资源，初值为表示独木桥资源，初值为1表示资源可用。表示资源可用。 int m=1; cobegin p1() / p2() coend 进程的互斥进程的互斥 练习练习：过十字路口（单道）。：过十字路口（单道）。 进程的互斥进程的互斥 P1 P2 P3 P4 通过路口；通过路口； 通过路口；通过路口； 通过路口；通过路口； 通过路口；通过路口； P2 P3 P4 P1 分析分析：进程：进程P1、P2、P

3、3、P4因竞争十字路口这个资源而成因竞争十字路口这个资源而成 为互斥关系。为互斥关系。 设设：信号量：信号量m表示十字路口资源，初值为表示十字路口资源，初值为1表示资源可用。表示资源可用。 int m=1; cobegin p1() / p2() /p3() / p4() coend 进程的互斥进程的互斥 有一个阅览室，共有有一个阅览室，共有100100个座位。读者进入阅览室个座位。读者进入阅览室 时必须在入口处进行登记；离开阅览室时必须进时必须在入口处进行登记；离开阅览室时必须进 行注销。试用行注销。试用PVPV操作描述读者进入操作描述读者进入/ /离开阅览室的离开阅览室的 同步与互斥关系同

4、步与互斥关系。 ReaderReader进程进程 登记登记 进入阅览室进入阅览室 读书读书 离开阅览室离开阅览室 注销注销 进程的互斥进程的互斥 分析：分析： 在入口和出口处读者应该在入口和出口处读者应该互斥互斥进行登记和注销，进行登记和注销， 100100个座位，个座位，100100个个互斥互斥资源资源 设置信号量设置信号量 教室内空座位数量，教室内空座位数量，seatseat，初值，初值100100 为入口处进行登记设置互斥信号量为入口处进行登记设置互斥信号量SinSin，初值，初值 1 1，表示，表示 当前可用当前可用 为出口处进行注销设置互斥信号量为出口处进行注销设置互斥信号量Sout

5、Sout，初值，初值 1 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 人时，可以进入。否则，需在外等候， 若将每一个

6、购票者作为一个进程，请用P、 V操作编程。 例例2：读写数据库：读写数据库。某数据库有一个写进程、多个读进程，它们之间某数据库有一个写进程、多个读进程，它们之间 读、写操作的互斥要求是：写进程运行时，其他读、写进程不能对数读、写操作的互斥要求是：写进程运行时，其他读、写进程不能对数 据库进行操作。读进程之间不互斥，可以同时读数据库。请用信号量据库进行操作。读进程之间不互斥，可以同时读数据库。请用信号量 及及PV操作描述这一组进程的工作过程。（操作描述这一组进程的工作过程。（读者读者-写者问题写者问题） 进程的互斥进程的互斥 数据库数据库 写写 者者 读读 者者 写者写者 读者读者 写数据库；写

7、数据库； 读数据库；读数据库； 分析分析：写进程写进程writer、读进程、读进程reader因竞争数据库这个资源因竞争数据库这个资源 而成为互斥关系。因为写进程执行时，不能执行其他读写而成为互斥关系。因为写进程执行时，不能执行其他读写 进程，所以还必须设置一个计数器统计读进程的个数。如进程，所以还必须设置一个计数器统计读进程的个数。如 果是第一个读进程，就与写进程竞争数据库。如果是最后果是第一个读进程，就与写进程竞争数据库。如果是最后 一个读进程，就释放数据库。因计数器是一个临界资源，一个读进程，就释放数据库。因计数器是一个临界资源， 所以多个读进程对计数器的操作又是互斥操作。所以多个读进程

8、对计数器的操作又是互斥操作。 设设：信号量信号量rmutex表示数据库资源，初值为表示数据库资源，初值为1表示资源可用；表示资源可用； wmutex表示计数器表示计数器count资源，初值为资源，初值为1表示可用。表示可用。 int rmutex=1，wmutex=1; cobegin reader() / writer() coend 进程的互斥进程的互斥 小结小结 n 进程互斥：进程之间要竞争临界资源。进程互斥：进程之间要竞争临界资源。 n 信号量表示临界资源是否可用，或临界资源信号量表示临界资源是否可用，或临界资源 的数量。的数量。 n 信号量的个数与临界资源的个数一致。信号量的个数与临

9、界资源的个数一致。 n 对同一个信号量的对同一个信号量的PV操作要在同一个进程中操作要在同一个进程中 完成。完成。 P操作：进入临界区前操作：进入临界区前 1. V操作：离开临界区后操作：离开临界区后 进程的互斥进程的互斥 进程同步 进程同步进程同步： 并发进程之间相互合作，完成一项工作，它们之并发进程之间相互合作，完成一项工作，它们之 间有一定的时序关系。间有一定的时序关系。 解题步骤解题步骤： n确定进程的确定进程的个数个数及每个进程的及每个进程的工作工作； n确定确定关键工作步关键工作步（需要控制的）；（需要控制的）； n确定信号量表示的确定信号量表示的含义，含义，当信号量的值为当信号量

10、的值为0时，表时，表 示期望的消息尚未产生；当信号量的值非示期望的消息尚未产生；当信号量的值非0时，表时，表 示期望的消息已经存在。示期望的消息已经存在。 1.写出写出伪代码伪代码。在同步关系的控制中，同一信号量。在同步关系的控制中，同一信号量 的的P(wait)、V(signal)操作成对出现，但它们分别操作成对出现，但它们分别 在不同的进程代码中。在不同的进程代码中。 例例1：假设有三个并发进程假设有三个并发进程P，Q，R，其中，其中P负责从输入设负责从输入设 备上读入信息并传送给备上读入信息并传送给Q，Q将信息加工后传送给将信息加工后传送给R，R则负则负 责将信息打印输出。进程责将信息打

11、印输出。进程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无数据，

12、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取出信息

13、取出信息; V（empty2）; 将信息打印输出将信息打印输出 ; 进程的同步进程的同步 例例2 2：公共汽车中的司机和售票员。：公共汽车中的司机和售票员。 司机司机 P1 P1 售票员售票员 P2P2 while (true) while (true) while (true) while (true) 启动车辆启动车辆； 关门关门； 正常运行；正常运行； 售票；售票； 到站停车到站停车； 开门开门； 解法解法：信号量表示进程能否开始。：信号量表示进程能否开始。 设信号量设信号量m1表示司机进程表示司机进程P1能否启动汽车，初值为能否启动汽车，初值为0， m2表示售票员进程表示售票员进程p2

14、能否开门，初值为能否开门，初值为0。 int m1=0,m20 ; cobegin p1() / p2() coend 进程的同步进程的同步 进程的同步进程的同步 例例3-23-2：吃水果。：吃水果。 父亲父亲 P1 P1 儿子儿子 P2 P2 女儿女儿 P3P3 while (true) while (true) while(true) while (true) while (true) while(true) 洗水果；洗水果； 取桔子取桔子； 取苹果取苹果； 放水果放水果； 吃桔子；吃桔子； 吃苹果；吃苹果； 桔子桔子 父亲父亲 儿子儿子 女儿女儿 0苹果苹果 分析分析：父亲先放水果，儿子

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

16、rue) while (true) while(true) while (true) while (true) while(true) 洗桔子；洗桔子； 洗苹果；洗苹果； 取水果取水果； 放桔子放桔子； 放苹果；放苹果； 吃水果；吃水果； 0 父亲父亲 儿子儿子 母亲母亲 桔子桔子苹果苹果 分析分析：父母亲先放水果，儿子再取水果吃；父亲与儿子，母：父母亲先放水果，儿子再取水果吃；父亲与儿子，母 亲与儿子是一个同步关系，父亲与母亲要竞争空盘子。亲与儿子是一个同步关系，父亲与母亲要竞争空盘子。 解法：解法：设信号量设信号量m1表示是否有空盘子，信号量表示是否有空盘子，信号量m2表示儿子表示儿子 能

17、否取水果。能否取水果。 int m1=1,m2=0； cobegin p1() / p2() / p3() coend 进程的同步进程的同步 0 进程的同步进程的同步 例例3-43-4：吃水果。：吃水果。 父亲父亲 P1 P1 母亲母亲 P2 P2 儿子儿子 P3P3 女儿女儿P4P4 while(true) while (true) while(true) while(true)while(true) while (true) while(true) while(true) 洗桔子；洗桔子； 洗苹果；洗苹果； 取苹果取苹果； 取桔子；取桔子； 放桔子放桔子； 放苹果；放苹果； 吃苹果；吃苹果

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

19、的同步 问题 有一只铁笼子，每次只能放入一只动物，猎手有一只铁笼子，每次只能放入一只动物，猎手 向笼中放入老虎，农民向笼中放入猪，动物园向笼中放入老虎，农民向笼中放入猪，动物园 等待取笼中的老虎，饭店等待取笼中的猪，试等待取笼中的老虎，饭店等待取笼中的猪，试 用用P、V操作写出能同步执行的程序。操作写出能同步执行的程序。 例例4 4。设有六个进程设有六个进程P1P1、P2P2、P3P3、P4P4、P5P5、P6P6，它，它 们并发执行。由们并发执行。由P1P1开始执行，开始执行，P6P6执行后结束。当进执行后结束。当进 程程P1P1执行后，进程执行后，进程P2P2、P3P3才能执行；当进程才能执行；当进程P2P2执行执行 后，进程后，进程P4P4才能执行；当进程才能执行；当进程P3P3执行后，进程执行后，进程P5P5才才 能执行；当进程能执行；当