Chapter进程同步与互斥应用例子解析实用PPT课件

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

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

3、进行注销。试用PVPV操作描述读者进入操作描述读者进入/ /离开阅离开阅览室的同步与互斥关系览室的同步与互斥关系。ReaderReader进程进程 登记登记进入阅览室进入阅览室读书读书离开阅览室离开阅览室注销注销 进程的互斥进程的互斥第6页/共29页 分析：分析：在入口和出口处读者应该在入口和出口处读者应该互斥互斥进行登记和注销，进行登记和注销， 100100个座位，个座位，100100个个互斥互斥资源资源 设置信号量设置信号量 教室内空座位数量，教室内空座位数量，seatseat，初值，初值100100 为入口处进行登记设置互斥信号量为入口处进行登记设置互斥信号量SinSin，初值，初值 1

4、 1，表示当前可用表示当前可用 为出口处进行注销设置互斥信号量为出口处进行注销设置互斥信号量SoutSout，初值，初值 1 1，表示当前可用表示当前可用第7页/共29页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;第8页/共29页问题 若有一售票厅只能容纳300人，当

5、少于300人时，可以进入。否则，需在外等候，若将每一个购票者作为一个进程，请用P、V操作编程。第9页/共29页例2：读写数据库。某数据库有一个写进程、多个读进程，它们之间读、写操作的互斥要求是：写进程运行时，其他读、写进程不能对数据库进行操作。读进程之间不互斥，可以同时读数据库。请用信号量及PV操作描述这一组进程的工作过程。（读者-写者问题） 进程的互斥进程的互斥数据库写者读者写者 读者 写数据库； 读数据库； 第10页/共29页分析：写进程writer、读进程reader因竞争数据库这个资源而成为互斥关系。因为写进程执行时，不能执行其他读写进程，所以还必须设置一个计数器统计读进程的个数。如果

6、是第一个读进程，就与写进程竞争数据库。如果是最后一个读进程，就释放数据库。因计数器是一个临界资源，所以多个读进程对计数器的操作又是互斥操作。 设：信号量rmutex表示数据库资源，初值为1表示资源可用；wmutex表示计数器count资源，初值为1表示可用。 int rmutex=1，wmutex=1; cobegin reader() / writer() coend进程的互斥进程的互斥第11页/共29页小结1.进程互斥：进程之间要竞争临界资源。2.信号量表示临界资源是否可用，或临界资源的数量。3.信号量的个数与临界资源的个数一致。4.对同一个信号量的PV操作要在同一个进程中完成。P操作：进

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

8、责将信息打印输出。进程P、Q共享一个缓冲区，进程Q、R共享另一个缓冲区。 进程的同步进程的同步3个进程P、Q、RP进程：从输入设备上读入信息将信息放入缓冲区1Q进程：从缓冲区1取出信息将信息放入缓冲区2中R进程：从缓冲区2取出信息将信息打印输出第14页/共29页 确定进程的同步、互斥关系 同步：P当缓存区1无数据时，才可以向缓冲区1写入信息 同步：Q当缓存区1有数据时，才可以从缓冲区1读取信息 同步：Q当缓存区2无数据时，才可以向缓冲区2写入信息 同步：R当缓存区2有数据时，才可以从缓冲区2读取信息 设置信号量 缓存区1无数据，empty1，初值1 缓存区1有数据，full1，初值0 缓存区2

9、无数据，empty2，初值1 缓存区2有数据，full2，初值0第15页/共29页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）;将信息打印输出 ; 第16页/共29页进程的同步进程的同步例2 2：公共汽车中的司机和售票员。 司机 P1

10、P1 售票员 P2P2 while (true) while (true) while (true) while (true) 启动车辆； 关门； 正常运行； 售票； 到站停车； 开门； 第17页/共29页 解法：信号量表示进程能否开始。 设信号量m1表示司机进程P1能否启动汽车，初值为0，m2表示售票员进程p2能否开门，初值为0。int m1=0,m20 ;cobegin p1() / p2()coend进程的同步进程的同步第18页/共29页进程的同步进程的同步例3-23-2：吃水果。 父亲 P1 P1 儿子 P2 P2 女儿 P3P3 while (true) while (true) w

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

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

13、3-4：吃水果。 父亲 P1 P1 母亲 P2 P2 儿子 P3P3 女儿P4P4 while(true) while (true) while(true) while(true)while(true) while (true) while(true) while(true) 洗桔子； 洗苹果； 取苹果； 取桔子； 放桔子； 放苹果； 吃苹果； 吃桔子； 桔子父亲女儿母亲苹果儿子第23页/共29页 分析：父母亲先放水果，儿子女儿再取水果；父亲与女儿，母亲与儿子是一个同步关系，父亲与母亲要竞争空盘子。 解法一：设信号量m1表示是否有空盘子，信号量m2表示儿子能否取苹果，m3表示女儿能否取桔子。i

14、nt m1=1,m2=0,m3=0；cobegin p1() / p2() / p3() / p4()coend进程的同步进程的同步第24页/共29页问题 有一只铁笼子，每次只能放入一只动物，猎手向笼中放入老虎，农民向笼中放入猪，动物园等待取笼中的老虎，饭店等待取笼中的猪，试用P、V操作写出能同步执行的程序。第25页/共29页例例4 4。设有六个进程P1P1、P2P2、P3P3、P4P4、P5P5、P6P6，它们并发执行。由P1P1开始执行，P6P6执行后结束。当进程P1P1执行后，进程P2P2、P3P3才能执行；当进程P2P2执行后，进程P4P4才能执行；当进程P3P3执行后，进程P5P5才

15、能执行；当进程P4P4、P5P5都执行后，进程P6P6才能执行；请用P P、V V操作编程. .进程的同步进程的同步第26页/共29页解：这是一个同步问题，信号量初值：S2=0S2=0，S3=0S3=0，S4=0S4=0，S5=0S5=0，S6=0S6=0 进程进程P1P1 进程进程P2P2 进程进程P3P3 执行执行P1P1 P(S2) P(S2) P(S3)P(S3) V(S2) V(S2) 执行执行P2P2 执行执行P3P3 V(S3) V(S3) V(S4) V(S4) V(S5)V(S5) 进程进程P4P4 进程进程P5P5 进程进程P6P6 P(S4)P(S4) P(S5) P(S5)