Chapter-6-进程同步与互斥应用例子解析.ppt

进程互斥进程互斥进程互斥：并发进程之间相互竞争临界资源的排他性关系。并发进程之间相互竞争临界资源的排他性关系。解题步骤解题步骤：n 确定临界资源及确定临界资源及个数个数；n 确定进程的确定进程的关键工作步关键工作步（使用临界资源的）；（使用临界资源的）；n 确定信号量的初值确定信号量的初值(临界资源的个数临界资源的个数)；n 写出写出伪代码伪代码。使用使用P(wait)操作和操作和V(signal)操作对进程互斥进操作对进程互斥进行控制。行控制。例例1：过独木桥。：过独木桥。进程的互斥进程的互斥P1 P2 由西向东过独木桥；由西向东过独木桥； 由东向西过独木桥；由东向西过独木桥； P1P2分析分析：进程：进程P1、P2因竞争独木桥这个资源而成为互斥关系。因竞争独木桥这个资源而成为互斥关系。设设：信号量：信号量m表示独木桥资源，初值为表示独木桥资源，初值为1表示资源可用。表示资源可用。 int m=1; cobegin p1() / p2() coend进程的互斥进程的互斥练习练习：过十字路口（单道）。：过十字路口（单道）。进程的互斥进程的互斥P1 P2 P3 P4 通过路口；通过路口； 通过路口；通过路口； 通过路口；通过路口； 通过路口；通过路口； P2P3P4P1分析分析：进程：进程P1、P2、P3、P4因竞争十字路口这个资源而成因竞争十字路口这个资源而成为互斥关系。为互斥关系。设设：信号量：信号量m表示十字路口资源，初值为表示十字路口资源，初值为1表示资源可用。表示资源可用。 int m=1; cobegin p1() / p2() /p3() / p4() coend进程的互斥进程的互斥 有一个阅览室，共有有一个阅览室，共有100100个座位。读者进入阅览室个座位。读者进入阅览室时必须在入口处进行登记；离开阅览室时必须进时必须在入口处进行登记；离开阅览室时必须进行注销。试用行注销。试用PVPV操作描述读者进入操作描述读者进入/ /离开阅览室的离开阅览室的同步与互斥关系同步与互斥关系。ReaderReader进程进程 登记登记进入阅览室进入阅览室读书读书离开阅览室离开阅览室注销注销 进程的互斥进程的互斥 分析：分析：在入口和出口处读者应该在入口和出口处读者应该互斥互斥进行登记和注销，进行登记和注销， 100100个座位，个座位，100100个个互斥互斥资源资源 设置信号量设置信号量教室内空座位数量，教室内空座位数量，seatseat，初值，初值100100为入口处进行登记设置互斥信号量为入口处进行登记设置互斥信号量SinSin，初值，初值 1 1，表示，表示当前可用当前可用为出口处进行注销设置互斥信号量为出口处进行注销设置互斥信号量SoutSout，初值，初值 1 1，表，表示当前可用示当前可用begin Sin, Sout, seat：semaphore; seat :=100; Sin := 1; Sout := 1;cobeginprocess Reader-i ( i = 1,2,n );beginP(seat);P(Sin);登记登记;V(Sin);进入阅览室进入阅览室;读书读书;离开阅览室离开阅览室;P(Sout);注销注销;V(Sout);V（seat）;endcoend;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操作：进入临界区前操作：进入临界区前1. V操作：离开临界区后操作：离开临界区后进程的互斥进程的互斥进程同步进程同步进程同步：并发进程之间相互合作，完成一项工作，它们之并发进程之间相互合作，完成一项工作，它们之间有一定的时序关系。间有一定的时序关系。解题步骤解题步骤：n确定进程的确定进程的个数个数及每个进程的及每个进程的工作工作；n确定确定关键工作步关键工作步（需要控制的）；（需要控制的）；n确定信号量表示的确定信号量表示的含义，含义，当信号量的值为当信号量的值为0时，表时，表示期望的消息尚未产生；当信号量的值非示期望的消息尚未产生；当信号量的值非0时，表时，表示期望的消息已经存在。示期望的消息已经存在。 1.写出写出伪代码伪代码。在同步关系的控制中，同一信号量。在同步关系的控制中，同一信号量的的P(wait)、V(signal)操作成对出现，但它们分别操作成对出现，但它们分别在不同的进程代码中。在不同的进程代码中。 例例1：假设有三个并发进程假设有三个并发进程P，Q，R，其中，其中P负责从输入设负责从输入设备上读入信息并传送给备上读入信息并传送给Q，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无数据，empty2，初值1 缓存区2有数据，full2，初值0process 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 2：公共汽车中的司机和售票员。：公共汽车中的司机和售票员。 司机司机 P1 P1 售票员售票员 P2P2 while (true) while (true) while (true) while (true) 启动车辆启动车辆； 关门关门； 正常运行；正常运行； 售票；售票； 到站停车到站停车； 开门开门； 解法解法：信号量表示进程能否开始。：信号量表示进程能否开始。 设信号量设信号量m1表示司机进程表示司机进程P1能否启动汽车，初值为能否启动汽车，初值为0，m2表示售票员进程表示售票员进程p2能否开门，初值为能否开门，初值为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苹果苹果 分析分析：父亲先放水果，儿子女儿再吃水果；儿子女儿取完水：父亲先放水果，儿子女儿再吃水果；儿子女儿取完水果，父亲再放水果，这三个进程是一个同步关系。果，父亲再放水果，这三个进程是一个同步关系。 解法：解法：设信号量设信号量m1表示父亲能否放水果，表示父亲能否放水果，m2表示儿子能否表示儿子能否取桔子，取桔子，m3表示女儿能否取苹果。表示女儿能否取苹果。int m1=1,m2=0,m3=0；cobegin p1() / p2() / p3()coend进程的同步进程的同步进程的同步进程的同步例例3-33-3：吃水果。：吃水果。 父亲父亲 P1 P1 母亲母亲 P2 P2 儿子儿子 P3P3 while (true) while (true) while(true) while (true) while (true) while(true) 洗桔子；洗桔子； 洗苹果；洗苹果； 取水果取水果； 放桔子放桔子； 放苹果；放苹果； 吃水果；吃水果； 0父亲父亲儿子儿子母亲母亲桔子桔子苹果苹果 分析分析：父母亲先放水果，儿子再取水果吃；父亲与儿子，母：父母亲先放水果，儿子再取水果吃；父亲与儿子，母亲与儿子是一个同步关系，父亲与母亲要竞争空盘子。亲与儿子是一个同步关系，父亲与母亲要竞争空盘子。 解法：解法：设信号量设信号量m1表示是否有空盘子，信号量表示是否有空盘子，信号量m2表示儿子表示儿子能否取水果。能否取水果。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) 洗桔子；洗桔子； 洗苹果；洗苹果； 取苹果取苹果； 取桔子；取桔子； 放桔子放桔子； 放苹果；放苹果； 吃苹果；吃苹果； 吃桔子；吃桔子； 桔子桔子父亲父亲女儿女儿母亲母亲苹果苹果儿子儿子 分析分析：父母亲先放水果，儿子女儿再取水果；父亲与女儿，：父母亲先放水果，儿子女儿再取水果；父亲与女儿，母亲与儿子是一个同步关系，父亲与母亲要竞争空盘子。母亲与儿子是一个同步关系，父亲与母亲要竞争空盘子。 解法一：解法一：设信号量设信号量m1表示是否有空盘子，信号量表示是否有空盘子，信号量m2表示儿表示儿子能否取苹果，子能否取苹果，m3表示女儿能否取桔子。表示女儿能否取桔子。int m1=1,m2=0,m3=0；cobegin p1() / p2() / p3() / p4()coend进程的同步进程的同步问题 有一只铁笼子，每次只能放入一只动物，猎手有一只铁笼子，每次只能放入一只动物，猎手向笼中放入老虎，农民向笼中放入猪，动物园向笼中放入老虎，农民向笼中放入猪，动物园等待取笼中的老虎，饭店等待取笼中的猪，试等待取笼中的老虎，饭店等待取笼中的猪，试用用P、V操作写出能同步执行的程序。操作写出能同步执行的程序。例例4 4。设有六个进程设有六个进程P1P1、P2P2、P3P3、P4P4、P5P5、P6P6，它，它们并发执行。由们并发执行。由P1P1开始执行，开始执行，P6P6执行后结束。当进执行后结束。当进程程P1P1执行后，进程执行后，进程P2P2、P3P3才能执行；当进程才能执行；当进程P2P2执行执行后，进程后，进程P4P4才能执行；当进程才能执行；当进程P3P3执行后，进程执行后，进程P5P5才才能执行；当进程能执行；当进程P4P4、P5P5都执行后，进程都执行后，进程P6P6才能执行；才能执行；请用请用P P、V V操作编程操作编程. .进程的同步进程的同步解：这是一个同步问题，信号量初值：解：这是一个同步问题，信号量初值：S2=0S2=0，S3=0S3=0，S4=0S4=0，S5=0S5=0，S6=0S6=0 进程进程P1P1 进程进程P2P2 进程进程P3P3 执行执行P1 P(S2) P(S3)P1 P(S2) P(S3) V(S2) V(S2) 执行执行P2 P2 执行执行P3P3 V(S3) V(S4) V(S5) V(S3) V(S4) V(S5) 进程进程P4P4 进程进程P5P5 进程进程P6P6 P(S4) P(S5) P(S6)P(S4) P(S5) P(S6) 执行执行P4 P4 执行执行P5 P(S6)P5 P(S6) V(S6) V(S6) V(S6) V(S6) 执行执行P6P6进程的同步进程的同步小结小结n 进程同步有一定的进程同步有一定的时序关系时序关系。n 信号量表示进程的信号量表示进程的关键工作关键工作是否可以开始或是否可以开始或已经结束。已经结束。n 信号量的个数信号量的个数与进程的个数一致，有时可以与进程的个数一致，有时可以省略部分信号量。省略部分信号量。n 对同一个信号量的对同一个信号量的PV操作不在一个进程中。操作不在一个进程中。1. 表示是否可以表示是否可以开始开始：P自己，自己，V别人别人进程的同步进程的同步