进程同步习题全ppt课件.ppt

设有n个进程共享一个程序段 对如下两种情况 1 如果每次只允许一个进程进入该程序段 2 如果每次最多允许m个进程 M n 同时进入该程序段 试问 所采用的信号量初值是否相同 信号量值的变化范围如何 所采用信号量的初值不相同 在情况 1 中 信号量的初值为1 信号量值的变化范围是l 0 1 n 1 在情况 2 中 信号量的初值为M 信号量值的变化范围是M m 1 m 2 m n 进程同步习题 例 一个buffer 一个生产者 一个消费者 生产者只生产一个东西 消费者只进行一次消费 即 生产者只进行一次putdata操作 消费者只进行一次getdata操作 解答 设置信号量full 表示buffer是否有数据 初值为0生产者消费者putdataP full V full getdata 例 一个buffer 一个生产者 一个消费者 生产者不断进行putdata操作 消费者不断进行getdata操作 即生产者不断生产 消费者不断消费 解答 buffer为空时 才能进行putdata操作 只有buffer有数据时 才能进行getdata操作信号量full 是否有数据初值为0empty 是否为空 初值为1 生产者 repeatP empty putdataV full 消费者 repeatP full getdataV empty 例 一个buffer 多个生产者 多个消费者 多个生产者和消费者都在不断地存取buffer 即生产者不断地进行putdata操作 消费者不断进行getdata操作 解答 只有buffer为空时能进行putdata操作 只有buffer有数据时能进行putdata操作 不允许多个进程同时操作buffer 即不允许多个消费者同时进行getdata 不允许多个生产者进行putdata操作信号量full buffer是否有数据 初值为0empty buffer是否为空 初值为1mutex buffer是否可操作 初值为1 生产者irepeatP empty P mutex putdataV mutex V full 消费者irepeatP full P mutex getdataV mutex V empty 例 多个生产者 多个消费者 N个buffer 多次循环存取buffer 即多个生产者不断进行putdata操作 多个消费者不断进行getdata操作 解答 只有buffer有空间时才能进行putdata操作只有buffer有数据时才能进行getdata操作不允许多个消费者和多个生产者同时操作信号量full 表示buffer是否有数据 初值为0empty 表示buffer是否为空 初值为nmutex 表示buffer是否可操作 初值为1 生产者irepeatP empty P mutex putdataV mutex V full 消费者jrepeatP full P mutex putdataV mutex V empty 改进 putdata和getdata操作都在临界区中 因此多个进程对多个buffer的操作不能并行进行的 进程间并行操作的程度很低 实际上只要保证多个进程同时操作不同buffer就可以实现对整个buffer的并行操作 getEBuffer 返回空的buffer号getEBuffer return pbuffer 1 modngetDBuffer 返回有数据的buffer号getDBuffer return pdata 1 modn semaphoremutex empty full 1 n 0integerpbuff pdata 0 0生产者i消费者jrepeatrepeatP empty P full P mutex P mutex in getEBuffer out getDBuffer V mutex V mutex putdata in getdata out V full V empty 练习 如图 有多个PUT操作同时向Buff1放数据 有一个MOVE操作不断地将Buff1的数据移到Buff2 有多个GET操作不断地从Buff2中将数据取走 Buff1的容量是m Buff2的容量是n PUT MOVE GET每次操作一个数据 在操作的过程中要保证数据不丢失 试用P V原语协调PUT MOVE操作 并说明每个信号量的含义和初值 Buff1 Buff2 MOVE PUT GET 解答 三类进程 多个PUT类进程 一个MOVE类进程 多个GET类进程操作规则1只有buff1有空间才能进行PUT操作2只有buff1有数据 buff2有空间才能进行MOVE操作3只有buff2有数据才能进行GET操作4不允许多个进程同时操作buff15不允许多个进程同时操作buff2 操作流程repeat判断buff1是否有空间 没有则等待是否可操作buff1PUT设置buff1可操作标志设置buff1有数据的标志untilfalse repeat判断buff1是否有数据 没有则等待判断buff2是否有空间 没有则等待是否可操作buff1是否可操作buff2MOVE设置buff1可操作标志设置buff2可操作标志设置buff1有空间标志设置buff2有空间标志 repeat判断buff2是否有数据 没有则等待是否可操作buff2GET设置buff1可操作标志设置buff1有空间标志 4信号量设置6个信号量full1 buff1是否有数据 初值为0empty1 buff1有空间 初值为mmutex1 buff1是否可操作 初值为1full2 buff2是否有数据 初值为0empty2 buff2有空间 初值为nmutex2 buff2是否可操作 初值为1 5PV操作实现repeatp empty1 判断buff1是否有空间 没有则等待p mutex1 是否可操作buff1PUT v mutex1 设置buff1可操作标志v full 设置buff1有数据标志 repeatP full1 判断buff1是否有数据 没有则等待P empty2 判断buff2是否有空间 没有则等待P mutex1 是否可操作buff1P mutex2 是否可操作buff2MOVE V mutex1 设置buff1可操作标志V mutex2 设置buff2可操作标志V empty1 设置buff1有空间标志V full2 设置buff2有数据标志 repeatP empty2 判断buff2是否有空间 没有则等待P mutex2 是否可操作buff2GETV mutex2 设置buff2可操作标记V full2 设置buff2有数据标记 例 现有4个进程R1 R2 W1 W2 它们共享可以存放一个数据的缓冲器B 进程R1每次把磁盘上读出的一个数据存到缓冲器B中 供进程W1打印输出 进程R2每次从键盘上读一个数据存放到缓冲器B 供W2打印输出 当一个进程把数据存放到缓冲器后 在该数据还没有打印输出之前不准任何进程再想缓冲器中存数据 当一个进程已把缓冲器中的数据打印输出后 在缓冲器中还没有存如新数据之前不准任何进程再从缓冲器中取数打印 问怎样用PV操作使这4个进程并发执行时能相互协作地工作 R1 R2 W1 W2 解答 4个进程互斥 R1 W1同步 R2 W2同步mutex 表示能否把数据存如缓冲器 初始化时缓冲器为空 故初值为1S1 进程R1是否已向缓冲器存入一个数据 初值为0S2 进程R2是否已向缓冲器存入一个数据 初值为0 beginmutex s1 s2 semaphore s 1 s2 0 s2 0 cobeginprocessR1beginL1 从磁盘上读数据送x1 P mutex B x1 V s1 gotoL1end processW1beginL3 P s1 y B V mutex 打印ygotoL3end processR2beginL2 从键盘上读数据送x2 P mutex B x2 V s2 gotoL2end processW2beginL4 P s2 z B V mutex 打印z gotoL4end 例 假定有3个进程R W1 W2共享一个缓冲器 而B中每次只能存放一个数 当缓冲器中无数时 进程R可将M输入设备上读入的数存放到缓存器B中 若存放到缓存器中的是奇数 则允许进程W1将其取出打印 若存放到缓冲器中的是偶数 则允许进程W2将取出打印 同时规定 进程R必须等缓冲器中的数被取出打印后才能再存放一个数 进程W1或W2对每次存入缓冲器中的数只能打印一次 W1和W2都不能从空的缓冲器中取数 写出这3个并发进程能正确工作的程序 分析 把进程R看作是生产者 把进程W1和W2看作是消费者 现在有一个生产者 进程R 能生产不同的产品 读入奇数或偶数 把生产的产品存放在缓冲器B中 供不同的消费者 进程W1和进程W2 取用 可以看出 当进程R读入的是整数 则要把有奇数的消息发送给进程W1 当进程R读入的是偶数 则要把有偶数的消息发送给W2 在进程W1或进程W2从缓冲器中取出数后 应把缓冲器中又可有一个数的消息告诉进程R 于是 可以定义如下3个信号量 S表示是否可以把数存入缓冲器 由于缓冲器中每次只能放一个数 所以其初值取为 1 SO 表示缓冲器中是否有奇数 初值为 0 表示无奇数SE 表示缓冲器是否偶数 初值为0 表示无偶数 解答 integerB semaphoreS SO SESO 0 SE 0 integerxL1 从输入设备读入一个数X 读入的数P S B Xif B 偶数 V SO elseV SE gotoL1 例 设有一个具有N个信息元素的环形缓冲区 A进程顺序地把信息写入缓冲区 B进程依次从缓冲区读出信息 回答下列问题 1叙述A B两进程的相互制约关系2判别下列用PV操作表示的同步算法是否正确 如不正确 试说明理由 并修改成正确的算法 设置信号量初值 S1 0 S2 N 设置变量初值 in out 0 例 进程P1使用缓冲区buffer向进程P2 P3 P4发送消息 要求每当P1向buffer中发消息时 只有当P2 P3 P4进程都读取这条消息后才可再向buffer中发送消息 利用PV原语描述进程的动作序列 P1 buffer P2 P3 P4 解答 设置信号量初值S1 S2 S3 0 S 3进程P1进程P2进程P3进程P4P S P S1 P S2 P S3 P S 读消息读消息读消息P S V S V S V S 发送消息到BufferV S1 V S2 V S3 例 设A B为两个并发进程 它们共享一个临界区 其执行临界区的算法框图如下 试判断该算法是否有错 请说明理由 如果有错 请改正 S1 S2的初值为0 CSA CSB为临界区 CSA V S1 P S2 A进程 P S1 CSB V S2 B进程 分析 系统启动时 S1 S2为0 则B执行P S1 被阻塞 而A进程可直接访问临界资源 故A B两个并发进程不可能同时操作临界资源 该算法是可以保证互斥的 按题目要求 两个进程对临界资源的操作是没有先后顺序的 但是 在上面的实现中 只有A进程先操作完资源后 B资源才能操作 解答 该算法错误若A进程用不要求访问临界资源 则不会折行V S1 意味着B进程的申请永远得不到操作临界资源的机会 同理 若B不要求访问临界资源 则不会执行V S2 意味着进程A下次也得不到操作临界资源的机会 所以 问题在于本应该互斥控制而使用的却是同步控制 实现改正 信号量mutex 1A进程B进程repeatrepeatP mutex P mutex CSA CSB V mutex V mutex 例 当进程X和进程Y共享某个资源r 进程并发执行时的程序如下 semaphore 1ProcessXProcessYL1 P S L2 P S 使用资源r使用资源rV S V S gotoL1gotoL2 请回答 1两个进程并发执行时 能否保证互斥使用资源 为什么 2若要使两个进程交替使用资源 仍使用PV操作来进行管理 写出应定义的信号量机器初值3修改上述程序 使两个进程能交替使用资源r 解答 1能保证互斥使用资源 因为在两个进程中 使用资源r 都是作为临界区 由P S 和V S 操作保证互斥执行 S的初值定义为1 符合要求 2要使两个进程交替使用资源 仅仅保证互斥使用是不够的 必须要两个进程相互等待互相通知 为此 必须定义新的信号量 定义两个私有信号量S1和S2 假定进程X先使用资源 那么进程X的私有信号量S1的初值定义为1 进程Y的私有信号量S2的初值为0 轮流使用可以保证互斥 因此信号量S可以不要 3两个进程可以改为semaphoreS1 1semaphoreS2 0ProcessXProcessYL1 P s1 L2 P S2 使用资源r使用资源rV S2 V S1 gotoL1gotoL2 例 桌上有一空盘 只允许存放一个水果 爸爸可向盘中放苹果 也可向盘中放橘子 儿子专等吃盘中的橘子 女儿专等吃盘中的苹果 规定当盘中空时一次只能放一只水果供吃者取用 请用PV原语实现爸爸 儿子 女儿三个并发进程的同步 解答 信号量mutex 盘子是否为空信号量So 盘中是否有橘子信号量Sa 盘中是否有苹果Sempahoremutex 1 So 0 Sa 0 fatherP mutex 将水果放入盘中if 放入的是橘子 V So elseV Sa 儿子P So 从盘中取橘子V mutex 吃橘子 女儿P Sa 从盘中取苹果V mutex 吃苹果 读者 写者介绍 读者写者 readerwriter 共享文件要求 1允许多个读者同时对文件执行读操作2只允许一个写者对文件执行写操作3任何写者在完成写操作前不允许其他读者或写者工作4写者在执行写操作前 应让已有的写者和读者全部退出 单纯使用信号量不能解决问题 引入计数器readcount对读进程计算 mutex是用于对计数器readcount操作的互斥信号量 writeblock表示是否允许写的信号量 intreadcount 0semaphorewriteblock mutex writeblock 1 mutex 1 读者iP mutex readcount if readcount 1 P writeblock V mutex 读文件P mutex readcount if readcount 0 V writeblock V mutex 写者jP writeblock 写文件V writeblock 进程同步习题 一条小河上有一座独木桥 规定每次只允许一人过桥 如果把每个过桥这看作一个进程 为保证安全 请用信号量操作实现正确管理 进程同步习题 begins semaphore s 1 cobeginbeginwait s 过桥 signal s endCoendend 练习 a b两点间是一段东西向的单行车道 现要设计一个自动管理系统 管理规则如下 当ab间有车辆在行驶时同方向的车可以同时驶入ab段 但另一方向的车必须在ab段外等待 当ab之间无车时 到达a 或b 的车辆可以进入ab段 但不能从a b点同时驶入 当某方向在ab段行驶的车辆使出了ab段且无车辆进入ab段时 应让另一方向等待的车辆进入ab段行驶 请用wait signal工具对ab段实现正确管理 答案 Semaphores mutexab mutexbaPab Wait mutexab Countab Ifcountab 1thenwait s Signal mutexab wait mutexab countab ifcountab 0thensignal s signal mutexab 答案 Pba wait mutexba countba countba 1 Ifcountba 1thenwait s signal mutexba enter wait mutexba countba ifcountba 0thensignal s signal mutexba 桌子上有一只盘子 最多可容纳两个水果 每次只能放入或取出一个水果 爸爸专向盘子中放苹果 妈妈专向盘子中放橘子 两个儿子专等吃盘子中的橘子 两个女儿专等吃盘子中的苹果 请用信号量操作来实现爸爸 妈妈 儿子 女儿之间的同步与互斥关系 ParbeginFather beginL1 p empty p mutex 放苹果 v mutex v apple gotol1 end Mather beginL2 p empty p mutex 放橘子 v mutex v orange gotol2 end Daughter beginL3 p apple p mutex 取苹果 v mutex v empty gotol3 end L4 p orange p mutex 取橘子 v mutex v empty Gotol4 end 桌上有一个空的水果盘 盘中一次只能放一个水果 服务员 男顾客和女顾客共用这个盘子 服务员向盘中放草莓和香蕉 男顾客专等吃盘中的草莓 女顾客专等吃盘中的香蕉 规定每次当盘子空时只能放一个水果供顾客食用 请用信号量机制实现服务员 男顾客和女顾客三个进程的同步 题解 盘子是三个人的公有信号量 设为mutex 初值为1 服务员的私有信号量设为empty初值为1 男顾客的私有信号量为ba 初值为0 女顾客的私有信号量为cm 初值为0 waiter beginL1 p empty p mutex 放香蕉或草莓 v mutex 如果放香蕉则v ba 否则v cm gotoL1 end Woman beginL3 p cm p mutex 取草莓 v mutex v empty gotoL2 end Man beginL2 p ba p mutex 取香蕉 v mutex v empty gotoL2 end 汽车司机与售票员之间必须协同工作 一方面只有售票员把车门关好了司机才能开车 因此 售票员关好车门应通知司机开车 另一方面 只有当汽车已经停下 售票员才能开门上下客 故司机停车后应通知售票员 汽车当前正在始发站停车上客 试设必要的信号灯及赋初值 写出他们的同步过程 解答 可以用两个信号量s1 s2 分别表示可以开门和可以开车 其初始值都为0 用PV操作实现为 司机 售票员 L0 正常行车L1 售票到站停车P S1 V S1 开车门P S2 关车门启动开车V S2 gotoL0gotoL1 和尚挑水问题 寺庙里有多个小 老和尚 一水缸 小和尚取水 老和尚饮水 水缸容积10桶水 水取自同一水井 水井每次只容一个桶取水 桶总数3个 每次入 取水缸水仅为一桶 试用P V操作描述和尚取水 饮水的互斥与同步过程 mutex1 mutex2 1 分别代表水井和水缸empty 10 水缸的入水量full 0 水缸的取水量count 3 水桶个数 打水 beginp empty p count p mutex1 从水井打水 v mutex1 p mutex2 往缸中放水v mutex2 v full v count end 取水 beginp full p count p mutex2 从水缸取水v mutex2 v count v empty end 哲学家进餐问题设有5个哲学家 共享一张放有五把椅子的桌子 每人分得一把椅子 但是 桌子上总共只有5支筷子 在每人两边分开各放一支 哲学家们在肚子饥饿时才试图分两次从两边拾起筷子就餐 条件 1 只有拿到两支筷子时 哲学家才能吃饭 2 如果筷子已在他人手上 则该哲学家必须等待到他人吃完之后才能拿到筷子 3 任一哲学家在自己未拿到两支筷子吃饭之前 决不放下自己手中的筷子 试 1 描述一个保证不会出现两个邻座同时要求吃饭的通信算法 2 描述一个既没有两邻座同时吃饭 又没有人饿死 永远拿不到筷子 的算法 3 在什么情况下 5个哲学家全部吃不上饭 1 begin2 begin3 begin4 begin5 beginP s1 p s2 p s3 p s4 p s5 P s2 p s3 p s4 p s5 p s1 吃饭 吃饭 吃饭 吃饭 吃饭 V s1 v s2 v s3 v s4 v s1 V s2 v s3 v s4 v s5 v s5 Endendendendend Pi RepeatThinkforwhilep mutex p s i p s i 1 mod5 v mutex eatforwhile v s i v s i 1 mod5 untilfalse 利用AND型信号量机制实现 semaphorechopstick 5 1 1 1 1 1 while true think Swait chopstick I 1 5 chopstick I eat Ssignal chopstick I 1 5 chopstick I 限制人数semaphorechopstick 5 1 1 1 1 1 semaphoremutex 4 Repeatthink wait mutex 请求进餐wait chopstick i 请求左手边的筷子wait chopstick i 1 5 请求右手边的筷子eat signal chopstick i 1 5 释放右手边的筷子signal chopstick i 释放左手边的筷子signal mutex 释放信号量mutexuntilfalse 原理 规定奇数号的哲学家先拿起他左边的筷子 然后再去拿他右边的筷子 而偶数号的哲学家则相反 按此规定 将是1 2号哲学家竞争1号筷子 3 4号哲学家竞争3号筷子 即五个哲学家都竞争奇数号筷子 获得后 再去竞争偶数号筷子 最后总会有一个哲学家能获得两支筷子而进餐 而申请不到的哲学家进入阻塞等待队列 根FIFO原则 则先申请的哲学家会较先可以吃饭 因此不会出现饿死的哲学家 semaphorechopstick 5 1 1 1 1 1 voidphilosopher inti while true think if i 2 0 偶数哲学家 先右后左 wait chopstick i 1 mod5 wait chopstick i eat signal chopstick i 1 mod5 signal chopstick i Else 奇数哲学家 先左后右 wait chopstick i wait chopstick i 1 mod5 eat signal chopstick i signal chopstick i 1 mod5 经典理发师问题 假设后街有家理发店 店里有一个理发师 一把理发椅和n把等候理发的顾客椅子 1 如果没有顾客则理发师便在理发椅上看报纸 2 当有一个顾客到达时 首先查看理发师在干什么 如果在看报纸则告诉理发师理发 然后坐到理发椅上开始理发 如果理发师正在理发 则查看是否有空的椅子可坐 如果有 他就坐下等待 如果没有 则离开 3 理发师为一位顾客理完发后 查看是否有人等待 如有则唤醒一位为其理发 如没有则在理发椅上看报纸 4 顾客不分优先级 有一间酒吧里有3个音乐爱好者队列 第一队的音乐爱好者只有随身听 第二队的音乐爱好者只有音乐磁带 第三队的音乐爱好者只有电池 然而 要听音乐就必须随身听 音乐磁带和电池三种物品俱全 酒吧老板一次出售这三种物品中的任意两种 当一名音乐爱好者得到这三种物品并听完一首乐曲后 酒吧老板才能再一次出售这三种物品中的任意两种 于是第2名音乐爱好者得到这三种物品 并开始听乐曲 全部买卖就这样进行下去 试用信号量实现它们之间的同步关系 进程同步算法习题课 例题1 用wait signal操作解决司机与售票员的问题 分析 为保证车辆行驶安全 售票员必须关好车门 然后通知司机启动车辆 在行驶过程中售票员不能打开车门 待车到站停稳后 司机通知售票员才能打开车门 如此不断重复 为此 须设置两个信号量S1 S2用来控制司机和售票员的行为 初值都为0 解 算法如下 司机进程 while 1 wait S1 启动车辆正常驾驶到站停车signal S2 售票员进程 while 1 关门signal S1 售票wait S2 开门 例题2 1 用wait signal操作解决下图之同步问题提示 分别考虑对缓冲区S和T的同步 再合并考虑 get copy put s t 解 设置四个信号量Sin 1 Sout 0 Tin 1 Tout 0 get while 1 wait Sin 将数放入S signal Sout copy while 1 wait Sout wait Tin 将数从S取出放入T signal Tout signal Sin put while 1 wait Tout 将数从T取走 signal Tin 思考题 如果S和T是由多个缓冲区组成的缓冲池 上述算法将如何修改 例题3 桌上有一空盘 最多允许存放一只水果 爸爸可向盘中放一个苹果或放一个桔子 儿子专等吃盘中的桔子 女儿专等吃苹果 试用wait signal操作实现爸爸 儿子 女儿三个并发进程的同步 分析 设置一个信号量S表示空盘子数 一个信号量So表示盘中桔子数 一个信号量Sa表示盘中苹果数 初值分别为1 0 0 解 算法如下 Father while 1 wait S 将水果放入盘中 if 是桔子 signal So elsesignal Sa Son while 1 wait So 取桔子signal S 吃桔子 Daughter while 1 wait Sa 取苹果signal S 吃苹果 例题4 有一个仓库 可以存放A和B两种产品 但要求 1 每次只能存入一种产品 A或B 2 N A产品数量 B产品数量 M 其中 N和M是正整数 试用wait signal操作描述产品A与B的入库过程 解 分析 设两个同步信号量Sa Sb 其中 Sa表示允许A产品比B产品多入库的数量 初值为M 1 Sb表示允许B产品比A产品多入库的数量 初值为N 1 设互斥信号量mutex 初值为1 B产品入库进程 j 0 while 1 wait Sb wait mutex B产品入库signal mutex signal Sa 消费产品 A产品入库进程 i 0 while 1 生产产品 wait Sa wait mutex A产品入库signal mutex signal Sb 算法如下 例题5 进程A1 A2 An1通过m个缓冲区向进程B1 B2 Bn2不断发送消息 发送和接收工作遵循下列规则 1 每个发送进程一次发送一个消息 写入一个缓冲区 缓冲区大小等于消息长度 2 对每个消息 B1 B2 Bn2都须各接收一次 读入各自的数据区内 3 m个缓冲区都满时 发送进程等待 没有可读消息时 接收进程等待 试用wait signal操作组织正确的发送和接收工作 分析 每个缓冲区只要写一次