资源预览内容
第1页 / 共29页
第2页 / 共29页
第3页 / 共29页
第4页 / 共29页
第5页 / 共29页
第6页 / 共29页
第7页 / 共29页
第8页 / 共29页
第9页 / 共29页
第10页 / 共29页
亲,该文档总共29页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
进程同步与互斥例题进程互斥进程互斥: 并发进程之间相互竞争临界资源的排他性关系 。 解题步骤: n 确定临界资源及个数; n 确定进程的关键工作步(使用临界资源的); n 确定信号量的初值(临界资源的个数); n 写出伪代码。 使用P(wait)操作和V(signal)操作对进程互斥进 行控制。例1:过独木桥。进程的互斥P1 P2 由西向东过独木桥; 由东向西过独木桥 ; P1P2分析:进程P1、P2因竞争独木桥这个资源而成为互斥关系 。 设:信号量m表示独木桥资源,初值为1表示资源可用。int m=1;cobeginp1() / p2()coend进程的互斥p1()p1() P(mP(m) ) ;通过独木桥;通过独木桥;V(mV(m) ) ; p2()p2() P(mP(m) ) ;通过独木桥;通过独木桥;V(mV(m) ); 练习:过十字路口(单道)。进程的互斥P1 P2 P3 P4 通过路口; 通过路口; 通过路口; 通过路口; P2P3P4P1分析:进程P1、P2、P3、P4因竞争十字路口这个资源而 成为互斥关系。 设:信号量m表示十字路口资源,初值为1表示资源可用。int m=1;cobeginp1() / 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;cobeginreader() / 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,初值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:公共汽车中的司机和售票员。 司机 P1 售票员 P2while (true) while (true) 启动车辆; 关门;正常运行; 售票;到站停车; 开门; 解法:信号量表示进程能否开始。 设信号量m1表示司机进程P1能否启动汽车,初值为0, m2表示售票员进程p2能否开门,初值为0。int m1=0,m20 ; cobeginp1() / 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; cobeginp1() / 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; cobeginp1() / p2() / p3() coend进程的同步p1()p1() while(1) while(1) 洗桔子;
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号