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

进程同步与互斥 例题 进程互斥 进程互斥 并发进程之间相互竞争临界资源的排他性关系 解题步骤 确定临界资源及个数 确定进程的关键工作步 使用临界资源的 确定信号量的初值 临界资源的个数 写出伪代码 使用P wait 操作和V signal 操作对进程互斥进行控制 例1 过独木桥 进程的互斥 P1P2 由西向东过独木桥 由东向西过独木桥 P1 P2 分析 进程P1 P2因竞争独木桥这个资源而成为互斥关系 设 信号量m表示独木桥资源 初值为1表示资源可用 intm 1 cobeginp1 p2 coend 进程的互斥 p1 P m 通过独木桥 V m p2 P m 通过独木桥 V m 练习 过十字路口 单道 进程的互斥 P1P2P3P4 通过路口 通过路口 通过路口 通过路口 P2 P3 P4 P1 分析 进程P1 P2 P3 P4因竞争十字路口这个资源而成为互斥关系 设 信号量m表示十字路口资源 初值为1表示资源可用 intm 1 cobeginp1 p2 p3 p4 coend 进程的互斥 p1 P m 通过路口 V m p2 P m 通过路口 V m p3 P m 通过路口 V m p4 P m 通过路口 V m 有一个阅览室 共有100个座位 读者进入阅览室时必须在入口处进行登记 离开阅览室时必须进行注销 试用PV操作描述读者进入 离开阅览室的同步与互斥关系 Reader进程 登记进入阅览室读书离开阅览室注销 进程的互斥 分析 在入口和出口处读者应该互斥进行登记和注销 100个座位 100个互斥资源设置信号量教室内空座位数量 seat 初值100为入口处进行登记设置互斥信号量Sin 初值1 表示当前可用为出口处进行注销设置互斥信号量Sout 初值1 表示当前可用 beginSin Sout seat semaphore seat 100 Sin 1 Sout 1 cobeginprocessReader 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表示可用 intrmutex 1 wmutex 1 cobeginreader writer coend 进程的互斥 小结进程互斥 进程之间要竞争临界资源 信号量表示临界资源是否可用 或临界资源的数量 信号量的个数与临界资源的个数一致 对同一个信号量的PV操作要在同一个进程中完成 P操作 进入临界区前V操作 离开临界区后 进程的互斥 进程同步 进程同步 并发进程之间相互合作 完成一项工作 它们之间有一定的时序关系 解题步骤 确定进程的个数及每个进程的工作 确定关键工作步 需要控制的 确定信号量表示的含义 当信号量的值为0时 表示期望的消息尚未产生 当信号量的值非0时 表示期望的消息已经存在 写出伪代码 在同步关系的控制中 同一信号量的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 初值0 processP while 1 从输入设备上读入信息 P empty1 将信息放入缓冲区1 V full1 processQ while 1 P full1 从缓冲区1取出信息 V empty1 P empty2 将信息放入缓冲区2 V full2 processR while 1 P full2 从缓冲区2取出信息 V empty2 将信息打印输出 进程的同步 例2 公共汽车中的司机和售票员 司机P1售票员P2while true while true 启动车辆 关门 正常运行 售票 到站停车 开门 解法 信号量表示进程能否开始 设信号量m1表示司机进程P1能否启动汽车 初值为0 m2表示售票员进程p2能否开门 初值为0 intm1 0 m2 0 cobeginp1 p2 coend 进程的同步 p1 while 1 P m1 启动汽车 正常行驶 到站停车 V m2 p2 while 1 关门 V m1 售票 m2 开门 进程的同步 例3 2 吃水果 父亲P1儿子P2女儿P3while true while true while true 洗水果 取桔子 取苹果 放水果 吃桔子 吃苹果 桔子 父亲 儿子 女儿 0 苹果 分析 父亲先放水果 儿子女儿再吃水果 儿子女儿取完水果 父亲再放水果 这三个进程是一个同步关系 解法 设信号量m1表示父亲能否放水果 m2表示儿子能否取桔子 m3表示女儿能否取苹果 intm1 1 m2 0 m3 0 cobeginp1 p2 p3 coend 进程的同步 p1 while 1 洗水果 P m1 放水果 if 是桔子 V m2 elseV m3 p2 while 1 P m2 取桔子 V m1 吃桔子 p3 while 1 P m3 取苹果 V m1 吃苹果 进程的同步 例3 3 吃水果 父亲P1母亲P2儿子P3while true while true while true 洗桔子 洗苹果 取水果 放桔子 放苹果 吃水果 0 父亲 儿子 母亲 桔子 苹果 分析 父母亲先放水果 儿子再取水果吃 父亲与儿子 母亲与儿子是一个同步关系 父亲与母亲要竞争空盘子 解法 设信号量m1表示是否有空盘子 信号量m2表示儿子能否取水果 intm1 1 m2 0 cobeginp1 p2 p3 coend 进程的同步 p1 while 1 洗桔子 P m1 放桔子 V m2 p2 while 1 洗苹果 P m1 放苹果 V m2 p3 while 1 P m2 取水果 V m1 吃水果 0 进程的同步 例3 4 吃水果 父亲P1母亲P2儿子P3女儿P4while true while true while true while true 洗桔子 洗苹果 取苹果 取桔子 放桔子 放苹果 吃苹果 吃桔子 桔子 父亲 女儿 母亲 苹果 儿子 分析 父母亲先放水果 儿子女儿再取水果 父亲与女儿 母亲与儿子是一个同步关系 父亲与母亲要竞争空盘子 解法一 设信号量m1表示是否有空盘子 信号量m2表示儿子能否取苹果 m3表示女儿能否取桔子 intm1 1 m2 0 m3 0 cobeginp1 p2 p3 p4 coend 进程的同步 p1 while 1 洗桔子 P m1 放桔子 V m3 p2 while 1 洗苹果 P m1 放苹果 V m2 p3 while 1 P m2 取苹果 V m1 吃苹果 p4 while 1 P m3 取桔子 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进程P1进程P2进程P3执行P1P S2 P S