进程同步与通信.ppt

第3章进程同步与通信 进程同步与互斥 经典进程同步问题 管程 AND信号量 进程通信 吃水果问题 取动物问题 超市购物问题 生产者 消费者问题 哲学家进餐问题 3 2经典进程同步问题 吃水果问题1 题目 桌子上有一个水果盘 允许存放一个水果 父亲专门向盘子中放苹果 儿子专等吃盘子中的苹果 只要盘子空 则父亲可向盘中放水果 仅当盘中有水果时 儿子可从中取出 把父亲 儿子看作二个进程 试用P V操作使这两个进程能正确地并发执行 使用信号量解决吃水果问题1 题目 桌子上有一个水果盘 允许存放一个水果 父亲专门向盘子中放苹果 儿子专等吃盘子中的苹果 只要盘子空 则父亲可向盘中放水果 仅当盘中有水果时 儿子可从中取出 分析 父亲和儿子两个进程相互制约 父亲进程执行完即往盘中放入苹果后 儿子进程才能执行即吃苹果 因此该问题为进程间的同步问题 semaphoreEmptyPlate 1 Apple 0 voidfather 父亲进程 while 1 P EmptyPlate 往盘子中放入一个苹果 V Apple voidson 儿子进程 while 1 P Apple 从盘中取出一个苹果 V EmptyPlate 吃苹果 吃水果问题2 题目 桌上有一只盘子 允许存放一个水果 父亲专向盘中放苹果 母亲专向盘中放桔子 儿子专等吃盘里的桔子 女儿专等吃盘里的苹果 只要盘子空 则父亲或母亲可向盘中放水果 仅当盘中有自己需要的水果时 儿子或女儿可从中取出 请给出四人之间的同步关系 并用PV操作实现四人正确活动的程序 使用信号量解决吃水果问题2 分析 四人之间的关系 1 父亲 母亲要互斥使用盘子 所以两者之间是互斥关系 2 父亲放的苹果 女儿吃 所以两者是同步关系 3 母亲放的桔子 儿子吃 所以两者也是同步关系 semaphoreEmptyPlate 1 Apple 0 Orange 0 voidfather 父亲进程 while 1 P EmptyPlate 往盘子中放入一个苹果 V Apple voidmother 母亲进程 while 1 P EmptyPlate 往盘子中放入一个桔子 V Orange 使用信号量解决吃水果问题2 分析 四人之间的关系 1 父亲 母亲要互斥使用盘子 所以两者之间是互斥关系 2 父亲放的苹果 女儿吃 所以两者是同步关系 3 母亲放的桔子 儿子吃 所以两者也是同步关系 voidson 儿子进程 while 1 P Orange 从盘中取出一个桔子 V EmptyPlate 吃桔子 semaphoreEmptyPlate 1 Apple 0 Orange 0 voiddaughter 女子进程 while 1 P Apple 从盘中取出一个苹果 V EmptyPlate 吃苹果 取动物问题 题目 有一只铁笼子 每次只能放入一只动物 猎人向笼中放入老虎 农民向笼中放入猪 动物园等待取笼中的老虎 饭店等待取笼中的猪 试用P V操作写出能同步执行的程序 使用信号量解决取动物问题 分析 四者之间的关系 1 猎人和农民要互斥使用笼子 所以两者之间是互斥关系 2 猎人放老虎 动物园取老虎 所以两者是同步关系 3 农民房猪 饭店取猪 所以两者也是同步关系 semaphoreEmptyCage 1 Tiger 0 Pig 0 voidhunter 猎人进程 while 1 P EmptyCage 往笼子里放入一只老虎 V Tiger voidfarmer 农民进程 while 1 P EmptyCage 往笼子里放入一只猪 V Pig voidzoo 动物园进程 while 1 P Tiger 从笼子里取出一只老虎 V EmptyCage voidrestaurant 饭店进程 while 1 P Pig 从笼子里取出一只猪 V EmptyCage 超市购物问题1 题目 某小型超级市场 可容纳100个人同时购物 入口处备有购物车 每个购物者可拿一辆购物车入内购物 出口处结帐 并归还购物车 试用PV操作写出购物者的同步算法 semaphores 100voidconsumeri void i 1 2 k while TRUE P s 进入超市取一辆购物车 购物 结帐 并归还购物车 V s 超市购物问题2 题目 某小型超级市场 可容纳100个人同时购物 入口处备有购物车 每个购物者可拿一辆购物车入内购物 出口处结帐 并归还购物车 出 入口禁止多人同时通过 试用PV操作写出购物者的同步算法 semaphores 100voidconsumeri void i 1 2 k while TRUE P s 进入超市取一辆购物车 购物 结帐 并归还购物车 V s 程序应该如何修改 超市购物问题2 题目 某小型超级市场 可容纳100个人同时购物 入口处备有购物车 每个购物者可拿一辆购物车入内购物 出口处结帐 并归还购物车 出 入口禁止多人同时通过 试用PV操作写出购物者的同步算法 semaphoremutex 1 s 100 voidconsumeri void i 1 2 k while TRUE P s P mutex 进超市入口处 取一辆购物车 V mutex 购物 P mutex 结帐 并归还购物车 V mutex V s 生产者 消费者问题 有两组进程共享一个环形的缓冲池 一组进程被称为生产者 另一组进程被称为消费者 缓冲池是由若干个大小相等的缓冲区组成的 每个缓冲区可以容纳一个产品 生产者进程不断地将生产的产品放入缓冲池 消费者进程不断地将产品从缓冲池中取出 用信号量解决 生产者 消费者 问题 初步设想 voidconsumer 消费者进程 while true P full data c buffer j j j 1 n V empty consumetheitemindata c semaphoreempty n semaphorefull 0 inti j ITEMbuffer n ITEMdata p data c voidproducer 生产者进程 while true produceanitemindata p P empty buffer i data p i i 1 n V full 用信号量解决 生产者 消费者 问题 voidconsumer 消费者进程 while true P full P mutex data c buffer j j j 1 n V mutex V empty consumetheitemindata c semaphoreempty n semaphorefull 0 inti j ITEMbuffer n ITEMdata p data c voidproducer 生产者进程 while true produceanitemindata p P empty P mutex buffer i data p i i 1 n V mutex V full semaphoremutex 1 哲学家进餐问题 五个哲学家 他们的生活方式是交替地思考和进餐 哲学家们共用一张圆桌 围绕着圆桌而坐 在圆桌上有五个碗和五支筷子 平时哲学家进行思考 饥饿时拿起其左 右的两支筷子 试图进餐 进餐完毕又进行思考 这里的问题是 哲学家只有在靠近他的两支筷子都拿到时才能进餐 而拿到两支筷子的条件是他的左 右邻居此时都没有进餐 semaphorechopstick 5 1 1 1 1 1 voidphilosopher inti 哲学家进程 while true P chopstick i P chopstick i 1 5 eating 进餐 V chopstick i V chopstick i 1 5 thinking 思考 用信号量解决哲学家进餐问题 哲学家能顺利地进餐吗 semaphorechopstick 5 1 1 1 1 1 voidphilosopher inti 哲学家进程 while true if i 2 0 偶数号哲学家 P chopstick i P chopstick i 1 5