第3章 进程同步与通信_2.ppt

1、第3章 进程同步与通信,进程同步与互斥,经典进程同步问题,管程,AND信号量,进程通信, 吃水果问题 取动物问题 超市购物问题 生产者消费者问题 哲学家进餐问题,3.2经典进程同步问题,吃水果问题1,题目：桌子上有一个水果盘，允许存放一个水果。父亲专门向盘子中放苹果，儿子专等吃盘子中的苹果。只要盘子空，则父亲可向盘中放水果，仅当盘中有水果时，儿子可从中取出。 把父亲、儿子看作二个进程，试用P、V操作使这两个进程能正确地并发执行。,使用信号量解决吃水果问题1,题目：桌子上有一个水果盘，允许存放一个水果。父亲专门向盘子中放苹果，儿子专等吃盘子中的苹果。只要盘子空，则父亲可向盘中放水果，仅当盘中有水

2、果时，儿子可从中取出。,分析：父亲和儿子两个进程相互制约，父亲进程执行完即往盘中放入苹果后，儿子进程才能执行即吃苹果。因此该问题为进程间的同步问题。,semaphore S_EmptyPlate=1, S_Apple=0;,void father( ) / 父亲进程 while(1) P(S_EmptyPlate); 往盘子中放入一个苹果； V(S_Apple); ,void son( ) / 儿子进程 while(1) P(S_Apple); 从盘中取出一个苹果； V(S_EmptyPlate); 吃苹果； ,吃水果问题2,题目：桌上有一只盘子，允许存放一个水果，父亲专向盘中放苹果，母亲专向

3、盘中放桔子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，则父亲或母亲可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出。 请给出四人之间的同步关系，并用PV操作实现四人正确活动的程序。,使用信号量解决吃水果问题2,分析：四人之间的关系： 1.父亲、母亲要互斥使用盘子，所以两者之间是互斥关系；2.父亲放的苹果，女儿吃，所以两者是同步关系； 3.母亲放的桔子，儿子吃，所以两者也是同步关系。,semaphore S_EmptyPlate=1, S_Apple=0, S_Orange=0;,void father( ) / 父亲进程 while(1) P(S_EmptyPla

4、te); 往盘子中放入一个苹果； V(S_Apple); ,void mother( ) / 母亲进程 while(1) P(S_EmptyPlate); 往盘子中放入一个桔子； V(S_Orange); ,使用信号量解决吃水果问题2,分析：四人之间的关系： 1.父亲，母亲要互斥使用盘子，所以两者之间是互斥关系；2.父亲放的苹果，女儿吃，所以两者是同步关系； 3.母亲放的桔子，儿子吃，所以两者也是同步关系。,void son( ) / 儿子进程 while(1) P(S_Orange); 从盘中取出一个 桔子； V(S_EmptyPlate); 吃桔子； ,semaphore S_EmptyP

5、late=1, S_Apple=0, S_Orange=0;,void daughter( ) / 女子进程 while(1) P(S_Apple); 从盘中取出一个 苹果； V(S_EmptyPlate); 吃苹果； ,取动物问题,题目：有一只铁笼子，每次只能放入一只动物，猎人向笼中放入老虎，农民向笼中放入猪，动物园等待取笼中的老虎，饭店等待取笼中的猪。 试用P、V操作写出能同步执行的程序。,使用信号量解决取动物问题,分析：四者之间的关系： 1.猎人和农民要互斥使用笼子，所以两者之间是互斥关系；2.猎人放老虎，动物园取老虎，所以两者是同步关系； 3.农民房猪，饭店取猪，所以两者也是同步关系。

6、,semaphore S_EmptyCage=1, S_Tiger=0, S_Pig=0;,void hunter( ) / 猎人进程 while(1) P(S_EmptyCage); 往笼子里放入一只老虎； V(S_Tiger); ,void farmer( ) / 农民进程 while(1) P(S_EmptyCage); 往笼子里放入一只猪； V(S_Pig); ,void zoo( ) / 动物园进程 while(1) P(S_Tiger); 从笼子里取出一只老虎； V(S_EmptyCage);； ,void restaurant( ) / 饭店进程 while(1) P(S_Pig

7、); 从笼子里取出一只猪； V(S_EmptyCage);； ,超市购物问题1,题目：某小型超级市场，可容纳100个人同时购物。入口处备有购物车，每个购物者可拿一辆购物车入内购物。出口处结帐，并归还购物车。 试用PV操作写出购物者的同步算法,semaphore s=100 void consumeri(void) (i=1,2,k) while(TRUE) P(s); 进入超市取一辆购物车； 购物; 结帐，并归还购物车; V(s); ,超市购物问题2,题目：某小型超级市场，可容纳100个人同时购物。入口处备有购物车，每个购物者可拿一辆购物车入内购物。出口处结帐，并归还购物车。 （出、入口禁止多

8、人同时通过） 试用PV操作写出购物者的同步算法,semaphore s=100 void consumeri(void) (i=1,2,k) while(TRUE) P(s); 进入超市取一辆购物车； 购物; 结帐，并归还购物车; V(s); ,？,程序应该 如何修改？,超市购物问题2,题目：某小型超级市场，可容纳100个人同时购物。入口处备有购物车，每个购物者可拿一辆购物车入内购物。出口处结帐，并归还购物车。（出、入口禁止多人同时通过） 试用PV操作写出购物者的同步算法,semaphore mutex = 1, s = 100; void consumeri(void) (i=1,2,k)

9、while(TRUE) P(s); P(mutex); 进超市入口处，取一辆购物车； V(mutex); 购物; P(mutex); 结帐，并归还购物车; V(mutex); V(s); ,生产者-消费者问题,有两组进程共享一个环形的缓冲池。一组进程被称为生产者，另一组进程被称为消费者。 缓冲池是由若干个大小相等的缓冲区组成的，每个缓冲区可以容纳一个产品。 生产者进程不断地将生产的产品放入缓冲池，消费者进程不断地将产品从缓冲池中取出。,用信号量解决“生产者-消费者”问题（初步设想）,void consumer()/消费者进程 while (true) P(full); data_c = buf

10、ferj; j = (j + 1) % n; V(empty); consume the item in data_c; ,semaphore empty = n;semaphore full = 0;,int i,j;ITEM buffern;ITEM data_p, data_c;,void producer() /生产者进程 while (true) produce an item in data_p; P(empty); bufferi = data_p; i = (i + 1) % n; V(full); ,用信号量解决“生产者-消费者”问题,void consumer()/消费者进

11、程 while (true) P(full); P(mutex); data_c = bufferj; j = (j + 1) % n; V(mutex); V(empty); consume the item in data_c; ,semaphore empty = n;semaphore full = 0;,int i,j;ITEM buffern;ITEM data_p, data_c;,void producer() /生产者进程 while (true) produce an item in data_p; P(empty); P(mutex); bufferi = data_p;

12、 i = (i + 1) % n; V(mutex); V(full); ,semaphore mutex =1;,哲学家进餐问题,五个哲学家，他们的生活方式是交替地思考和进餐。 哲学家们共用一张圆桌，围绕着圆桌而坐，在圆桌上有五个碗和五支筷子，平时哲学家进行思考，饥饿时拿起其左、右的两支筷子，试图进餐，进餐完毕又进行思考。 这里的问题是：哲学家只有在靠近他的两支筷子都拿到时才能进餐，而拿到两支筷子的条件是他的左、右邻居此时都没有进餐。,semaphore chopstick5 =1,1,1,1,1; void philosopher (int i ) /*哲学家进程*/ while (tru

13、e) P(chopsticki); P(chopstick(i + 1) % 5); eating; /* 进餐 */ V(chopsticki); V(chopstick(i + 1) % 5); thinking; /* 思考 */ ,用信号量解决哲学家进餐问题,哲学家能顺利地进餐吗,？,semaphore chopstick5 =1,1,1,1,1; void philosopher (int i ) /哲学家进程 while (true) if( i %2 = = 0 ) /偶数号哲学家 P(chopsticki); P(chopstick(i + 1) % 5); eating; /* 进餐 */ V(chopstic