1、第3章 進(jìn)程同步與通信,進(jìn)程同步與互斥,經(jīng)典進(jìn)程同步問題,管程,AND信號(hào)量,進(jìn)程通信, 吃水果問題 取動(dòng)物問題 超市購物問題 生產(chǎn)者消費(fèi)者問題 哲學(xué)家進(jìn)餐問題,3.2經(jīng)典進(jìn)程同步問題,吃水果問題1,題目：桌子上有一個(gè)水果盤，允許存放一個(gè)水果。父親專門向盤子中放蘋果，兒子專等吃盤子中的蘋果。只要盤子空，則父親可向盤中放水果，僅當(dāng)盤中有水果時(shí)，兒子可從中取出。 把父親、兒子看作二個(gè)進(jìn)程，試用P、V操作使這兩個(gè)進(jìn)程能正確地并發(fā)執(zhí)行。,使用信號(hào)量解決吃水果問題1,題目：桌子上有一個(gè)水果盤，允許存放一個(gè)水果。父親專門向盤子中放蘋果，兒子專等吃盤子中的蘋果。只要盤子空，則父親可向盤中放水果，僅當(dāng)盤中有水

2、果時(shí)，兒子可從中取出。,分析：父親和兒子兩個(gè)進(jìn)程相互制約，父親進(jìn)程執(zhí)行完即往盤中放入蘋果后，兒子進(jìn)程才能執(zhí)行即吃蘋果。因此該問題為進(jìn)程間的同步問題。,semaphore EmptyPlate=1, Apple=0;,void father( ) / 父親進(jìn)程 while(1) P(EmptyPlate); 往盤子中放入一個(gè)蘋果； V(Apple); ,void son( ) / 兒子進(jìn)程 while(1) P(Apple); 從盤中取出一個(gè)蘋果； V(EmptyPlate); 吃蘋果； ,吃水果問題2,題目：桌上有一只盤子，允許存放一個(gè)水果，父親專向盤中放蘋果，母親專向盤中放桔子，兒子專等吃盤

3、里的桔子，女兒專等吃盤里的蘋果。只要盤子空，則父親或母親可向盤中放水果，僅當(dāng)盤中有自己需要的水果時(shí)，兒子或女兒可從中取出。 請(qǐng)給出四人之間的同步關(guān)系，并用PV操作實(shí)現(xiàn)四人正確活動(dòng)的程序。,使用信號(hào)量解決吃水果問題2,分析：四人之間的關(guān)系： 1.父親、母親要互斥使用盤子，所以兩者之間是互斥關(guān)系；2.父親放的蘋果，女兒吃，所以兩者是同步關(guān)系； 3.母親放的桔子，兒子吃，所以兩者也是同步關(guān)系。,semaphore EmptyPlate=1, Apple=0, Orange=0;,void father( ) / 父親進(jìn)程 while(1) P(EmptyPlate); 往盤子中放入一個(gè)蘋果； V(A

4、pple); ,void mother( ) / 母親進(jìn)程 while(1) P(EmptyPlate); 往盤子中放入一個(gè)桔子； V(Orange); ,使用信號(hào)量解決吃水果問題2,分析：四人之間的關(guān)系： 1.父親，母親要互斥使用盤子，所以兩者之間是互斥關(guān)系；2.父親放的蘋果，女兒吃，所以兩者是同步關(guān)系； 3.母親放的桔子，兒子吃，所以兩者也是同步關(guān)系。,void son( ) / 兒子進(jìn)程 while(1) P(Orange); 從盤中取出一個(gè) 桔子； V(EmptyPlate); 吃桔子； ,semaphore EmptyPlate=1, Apple=0, Orange=0;,void

5、daughter( ) / 女子進(jìn)程 while(1) P(Apple); 從盤中取出一個(gè) 蘋果； V(EmptyPlate); 吃蘋果； ,取動(dòng)物問題,題目：有一只鐵籠子，每次只能放入一只動(dòng)物，獵人向籠中放入老虎，農(nóng)民向籠中放入豬，動(dòng)物園等待取籠中的老虎，飯店等待取籠中的豬。 試用P、V操作寫出能同步執(zhí)行的程序。,使用信號(hào)量解決取動(dòng)物問題,分析：四者之間的關(guān)系： 1.獵人和農(nóng)民要互斥使用籠子，所以兩者之間是互斥關(guān)系；2.獵人放老虎，動(dòng)物園取老虎，所以兩者是同步關(guān)系； 3.農(nóng)民房豬，飯店取豬，所以兩者也是同步關(guān)系。,semaphore EmptyCage=1, Tiger=0, Pig=0;,

6、void hunter( ) / 獵人進(jìn)程 while(1) P(EmptyCage); 往籠子里放入一只老虎； V(Tiger); ,void farmer( ) / 農(nóng)民進(jìn)程 while(1) P(EmptyCage); 往籠子里放入一只豬； V(Pig); ,void zoo( ) / 動(dòng)物園進(jìn)程 while(1) P(Tiger); 從籠子里取出一只老虎； V(EmptyCage);； ,void restaurant( ) / 飯店進(jìn)程 while(1) P(Pig); 從籠子里取出一只豬； V(EmptyCage);； ,超市購物問題1,題目：某小型超級(jí)市場(chǎng)，可容納100個(gè)人同時(shí)購

7、物。入口處備有購物車，每個(gè)購物者可拿一輛購物車入內(nèi)購物。出口處結(jié)帳，并歸還購物車。 試用PV操作寫出購物者的同步算法,semaphore s=100 void consumeri(void) (i=1,2,k) while(TRUE) P(s); 進(jìn)入超市取一輛購物車； 購物; 結(jié)帳，并歸還購物車; V(s); ,超市購物問題2,題目：某小型超級(jí)市場(chǎng)，可容納100個(gè)人同時(shí)購物。入口處備有購物車，每個(gè)購物者可拿一輛購物車入內(nèi)購物。出口處結(jié)帳，并歸還購物車。 （出、入口禁止多人同時(shí)通過） 試用PV操作寫出購物者的同步算法,semaphore s=100 void consumeri(void) (

8、i=1,2,k) while(TRUE) P(s); 進(jìn)入超市取一輛購物車； 購物; 結(jié)帳，并歸還購物車; V(s); ,？,程序應(yīng)該 如何修改？,超市購物問題2,題目：某小型超級(jí)市場(chǎng)，可容納100個(gè)人同時(shí)購物。入口處備有購物車，每個(gè)購物者可拿一輛購物車入內(nèi)購物。出口處結(jié)帳，并歸還購物車。（出、入口禁止多人同時(shí)通過） 試用PV操作寫出購物者的同步算法,semaphore mutex = 1, s = 100; void consumeri(void) (i=1,2,k) while(TRUE) P(s); P(mutex); 進(jìn)超市入口處，取一輛購物車； V(mutex); 購物; P(mut

9、ex); 結(jié)帳，并歸還購物車; V(mutex); V(s); ,生產(chǎn)者-消費(fèi)者問題,有兩組進(jìn)程共享一個(gè)環(huán)形的緩沖池。一組進(jìn)程被稱為生產(chǎn)者，另一組進(jìn)程被稱為消費(fèi)者。 緩沖池是由若干個(gè)大小相等的緩沖區(qū)組成的，每個(gè)緩沖區(qū)可以容納一個(gè)產(chǎn)品。 生產(chǎn)者進(jìn)程不斷地將生產(chǎn)的產(chǎn)品放入緩沖池，消費(fèi)者進(jìn)程不斷地將產(chǎn)品從緩沖池中取出。,用信號(hào)量解決“生產(chǎn)者-消費(fèi)者”問題（初步設(shè)想）,void consumer()/消費(fèi)者進(jìn)程 while (true) P(full); data_c = bufferj; j = (j + 1) % n; V(empty); consume the item in data_c; ,

10、semaphore empty = n;semaphore full = 0;,int i,j;ITEM buffern;ITEM data_p, data_c;,void producer() /生產(chǎn)者進(jìn)程 while (true) produce an item in data_p; P(empty); bufferi = data_p; i = (i + 1) % n; V(full); ,用信號(hào)量解決“生產(chǎn)者-消費(fèi)者”問題,void consumer()/消費(fèi)者進(jìn)程 while (true) P(full); P(mutex); data_c = bufferj; j = (j + 1

11、) % 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() /生產(chǎn)者進(jìn)程 while (true) produce an item in data_p; P(empty); P(mutex); bufferi = data_p; i = (i + 1) % n; V(mutex); V(full); ,semaphore mutex =1;,哲學(xué)家進(jìn)

12、餐問題,五個(gè)哲學(xué)家，他們的生活方式是交替地思考和進(jìn)餐。 哲學(xué)家們共用一張圓桌，圍繞著圓桌而坐，在圓桌上有五個(gè)碗和五支筷子，平時(shí)哲學(xué)家進(jìn)行思考，饑餓時(shí)拿起其左、右的兩支筷子，試圖進(jìn)餐，進(jìn)餐完畢又進(jìn)行思考。 這里的問題是：哲學(xué)家只有在靠近他的兩支筷子都拿到時(shí)才能進(jìn)餐，而拿到兩支筷子的條件是他的左、右鄰居此時(shí)都沒有進(jìn)餐。,semaphore chopstick5 =1,1,1,1,1; void philosopher (int i ) /*哲學(xué)家進(jìn)程*/ while (true) P(chopsticki); P(chopstick(i + 1) % 5); eating; /* 進(jìn)餐 */ V(chopsticki); V(chopstick(i + 1) % 5); thinking; /* 思考 */ ,用信號(hào)量解決哲學(xué)家進(jìn)餐問題,哲學(xué)家能順利地進(jìn)餐嗎,？,semaphore chopstick5 =1,1,1,1,1; void philosopher (int i ) /哲學(xué)家進(jìn)程 while (true) if( i %2 = = 0 ) /偶數(shù)號(hào)哲學(xué)家 P(chopsticki); P(chopstick(i + 1) % 5); eating; /* 進(jìn)餐 */ V(chopsticki)