嵌入式系統(tǒng)及應(yīng)用：進(jìn)程間的制約關(guān)系(經(jīng)典同步問題)

1、經(jīng)典進(jìn)程同步問題經(jīng)典進(jìn)程同步問題讀者-寫者問題哲學(xué)家就餐問題“理發(fā)店”問題讀者-寫者問題數(shù)據(jù)對(duì)象可以為多個(gè)并發(fā)進(jìn)程所共享 有兩種并發(fā)進(jìn)程: 讀者：寫者：共享一組數(shù)據(jù)區(qū)同步要求：同一時(shí)刻只允許一個(gè)寫者寫。同一時(shí)刻可允許多個(gè)讀者讀。不允許讀者、寫者同時(shí)操作。讀者-寫者問題 程序描述讀者： 讀者讀取所需數(shù)據(jù)寫者： 寫者對(duì)數(shù)據(jù)進(jìn)行修改讀者優(yōu)先的讀者-寫者問題如果讀者來：1）無讀者、寫者，新讀者可以讀2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等如果寫者來：1）無讀者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待用P、V信號(hào)量來解決讀者-寫者問題讀者： 讀者讀取

2、所需數(shù)據(jù)寫者： 寫者對(duì)數(shù)據(jù)進(jìn)行修改設(shè)置信號(hào)量wrt，初始值為1;用P、V信號(hào)量來解決讀者-寫者問題讀者： P（wrt） 讀者讀取所需數(shù)據(jù) V（wrt）寫者： P（wrt） 寫者對(duì)數(shù)據(jù)進(jìn)行修改 V（wrt）設(shè)置信號(hào)量wrt，初始值為1;不滿足讀者優(yōu)先要求用P、V信號(hào)量來解決讀者-寫者問題讀者： P（wrt） 讀者讀取所需數(shù)據(jù) V（wrt）寫者： P（wrt） 寫者對(duì)數(shù)據(jù)進(jìn)行修改 V（wrt）設(shè)置信號(hào)量wrt，初始值為1;添加共享變量reader，初始值為0；用P、V信號(hào)量來解決讀者-寫者問題讀者： reader=reader+1 if reader=1 P（wrt） 讀者讀取所需數(shù)據(jù) V（wrt

3、）寫者： P（wrt） 寫者對(duì)數(shù)據(jù)進(jìn)行修改 V（wrt）設(shè)置信號(hào)量wrt，初始值為1;添加共享整型變量reader，初始值為0；問題：讀者讀完數(shù)據(jù)退出時(shí)數(shù)據(jù)是否需要更新？用P、V信號(hào)量來解決讀者-寫者問題讀者： reader=reader+1 if reader=1 P（wrt） 讀者讀取所需數(shù)據(jù) reader=reader-1 V（wrt） 寫者： P（wrt） 寫者對(duì)數(shù)據(jù)進(jìn)行修改 V（wrt）設(shè)置信號(hào)量wrt，初始值為1;添加共享整型變量reader，初始值為0；用P、V信號(hào)量來解決讀者-寫者問題讀者： reader=reader+1 if reader=1 P（wrt） 讀者讀取所需數(shù)據(jù)

4、 reader=reader-1 if reader=0 V（wrt） 寫者： P（wrt） 寫者對(duì)數(shù)據(jù)進(jìn)行修改 V（wrt）設(shè)置信號(hào)量wrt，初始值為1;添加共享整型變量reader，初始值為0；用P、V信號(hào)量來解決讀者-寫者問題讀者： P(mutex) reader=reader+1 if reader=1 P（wrt） V(mutex) 讀者讀取所需數(shù)據(jù) P(mutex) reader=reader-1 if reader=0 V（wrt） v(mutex) 寫者： P（wrt） 寫者對(duì)數(shù)據(jù)進(jìn)行修改 V（wrt）設(shè)置信號(hào)量wrt，初始值為1;mutex,初始值1；設(shè)置共享整型變量read

5、er，初始值為0；“理發(fā)店”問題理發(fā)店中有k張理發(fā)椅和n張給等待理發(fā)的顧客坐的座椅。入口座椅座椅座椅座椅座椅理發(fā)椅n張理發(fā)椅理發(fā)椅k張出口若沒有顧客，理發(fā)師就坐在理發(fā)椅上打盹；當(dāng)顧客來時(shí)，就喚醒打盹的理發(fā)師進(jìn)行理發(fā)；若理發(fā)師全在工作，又來新顧客，則就坐在空座椅上等待理發(fā)，沒有空座椅就離去。試用信號(hào)量上的P、V操作描述理發(fā)師和顧客的行為，保證該過程的正確實(shí)現(xiàn)?！袄戆l(fā)店”問題 程序描述理發(fā)師程序barber() cut_hair();顧客程序customer() get_haircut(); “理發(fā)店”問題-P、V信號(hào)量解法設(shè)置同步信號(hào)量custs：記錄等待理發(fā)的顧客數(shù)(不包括正在理發(fā)的顧客)，初

6、值為0；barbs：正在等待為顧客理發(fā)的理發(fā)師數(shù)，初值為k；“理發(fā)店”問題-P、V信號(hào)量解法理發(fā)師程序barber() P(custs); /申請(qǐng)顧客 cut_hair();顧客程序customer() P(barbs); /申請(qǐng)理發(fā)師 get_haircut();“理發(fā)店”問題-P、V信號(hào)量解法理發(fā)師程序barber() P(custs); /申請(qǐng)顧客 cut_hair(); V(barbs); /釋放理發(fā)師 顧客程序customer() V(custs); /釋放顧客 P(barbs); /申請(qǐng)理發(fā)師 get_haircut();“理發(fā)店”問題-P、V信號(hào)量解法設(shè)置同步信號(hào)量custs：記

7、錄等待理發(fā)的顧客數(shù)(不包括正在理發(fā)的顧客)，初值為0；barbs：正在等待為顧客理發(fā)的理發(fā)師數(shù)，初值為k；設(shè)置變量waiting，它的初值為0。記錄等待理發(fā)的顧客數(shù)“理發(fā)店”問題-P、V信號(hào)量解法顧客程序customer() if(waitingn) waiting=waiting+1; V(custs); P(barbs); get_haircut(); 理發(fā)師程序barber() P(custs); cut_hair(); V(barbs); “理發(fā)店”問題-P、V信號(hào)量解法顧客程序customer() if(waitingn) waiting=waiting+1; V(custs); P

8、(barbs); get_haircut(); 理發(fā)師程序barber() P(custs); cut_hair(); waiting=waiting-1; V(barbs); “理發(fā)店”問題-P、V信號(hào)量解法設(shè)置同步信號(hào)量custs：記錄等待理發(fā)的顧客數(shù)(不包括正在理發(fā)的顧客)，初值為0；barbs：正在等待為顧客理發(fā)的理發(fā)師數(shù)，初值為k；設(shè)置變量waiting，它的初值為0。記錄等待理發(fā)的顧客數(shù)設(shè)置互斥信號(hào)量mutex：互斥使用waiting“理發(fā)店”問題-P、V信號(hào)量解法理發(fā)師程序barber() P(custs); P(mutex); waiting=waiting-1; V(mute

9、x); cut_hair(); V(barbs); 顧客程序customer() P(mutex); if(waitingn) waiting=waiting+1; V(custs); V(mutex); P(barbs); get_haircut(); else V(mutex);哲學(xué)家就餐問題問題描述：有五個(gè)哲學(xué)家圍坐在一圓桌旁，每人面前有一盤食物，每兩人之間放一只筷子哲學(xué)家的動(dòng)作包括思考和進(jìn)餐，進(jìn)餐時(shí)需要同時(shí)拿起他左邊和右邊的兩支筷子，思考時(shí)則同時(shí)將兩支筷子放回原處。如何保證哲學(xué)家們的動(dòng)作有序進(jìn)行？如：不出現(xiàn)相鄰者同時(shí)要求進(jìn)餐；不出現(xiàn)有人永遠(yuǎn)拿不到筷子；哲學(xué)家就餐問題 程序描述哲學(xué)家進(jìn)程

10、： think(); eat();哲學(xué)家就餐問題解法15個(gè)哲學(xué)家須互斥使用5只筷子，若其中一個(gè)拿到他右邊的那只筷子，那么坐在他右邊的哲學(xué)家的左手就暫時(shí)不能拿那只筷子。為此，給每只筷子編號(hào)，為04 對(duì)應(yīng)設(shè)置5個(gè)互斥信號(hào)量：chopsticki (0i4) 初值為10432143210哲學(xué)家編號(hào)筷子編號(hào)第i個(gè)哲學(xué)家的“思考-就餐-思考”過程可描述為： philosopher(i) while(TRUE) think(); P(chopsticki); P(chopstick(i+1) mod 5); eat(); V(chopsticki); V(chopstick(i+1) mod 5); 為防

11、止死鎖發(fā)生可采取的措施：最多允許4個(gè)哲學(xué)家同時(shí)坐在桌子周圍僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反之 哲學(xué)家就餐問題解法2設(shè)置5個(gè)互斥信號(hào)量：chopsticki (0i4) /對(duì)應(yīng)筷子 初值=1設(shè)置信號(hào)量seat / 代表了座位數(shù)初始值=4；0432143210哲學(xué)家編號(hào)筷子編號(hào)第i個(gè)哲學(xué)家的“思考-就餐-思考”過程可描述為： philosopher(i) while(TRUE) think(); P(seat); P(chopsticki); P(chopstick(i+1) mod 5); eat();

12、V(chopsticki); V(chopstick(i+1) mod 5); V(seat); 哲學(xué)家就餐問題解法3僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子把哲學(xué)家分為三種狀態(tài):THINKING 思考狀態(tài)：哲學(xué)家就餐后，就由就餐狀態(tài)EATING轉(zhuǎn)變成思考狀態(tài)。 EATING 就餐狀態(tài)：處于該狀態(tài)的哲學(xué)家已拿到自己左右的兩只筷子，由饑餓狀態(tài)轉(zhuǎn)變成為就餐狀態(tài)。 HUNGRY 饑餓狀態(tài)：當(dāng)某哲學(xué)家在思考中想吃飯時(shí)，就由思考狀態(tài)轉(zhuǎn)變成為饑餓狀態(tài)。哲學(xué)家就餐問題解法3 初始化設(shè)置數(shù)組statei (0i4)每個(gè)哲學(xué)家一個(gè)，表示哲學(xué)家的狀態(tài)。設(shè)置信號(hào)量數(shù)組si (0i4)每個(gè)哲學(xué)家一個(gè)，表示

13、是否可以就餐。初值都為0。在拿不到筷子就餐時(shí)，用它來與占用筷子的哲學(xué)家取得同步，以期歸還筷子時(shí)，能喚醒受阻塞的哲學(xué)家。設(shè)置兩個(gè)變量，表示第i個(gè)哲學(xué)家左右相鄰哲學(xué)家的編號(hào)：LEFT=(i+4) mod 5，RIGHT=(i+1) mod 5(0i4)設(shè)置互斥信號(hào)量mutex，初值為1。為保證各哲學(xué)家在測試他左右相鄰者的狀態(tài)和設(shè)置新狀態(tài)時(shí)，能互斥地進(jìn)行哲學(xué)家 i 程序philosopher (i) while (true) thinking( ); take_chopstick(i)； eat； put _ chopstick(i); 測試狀態(tài)子程序test(i) if(statei=HUNGRY & stateLEFT!=EATING & stateRIGHT!=EATING) statei=EATING; V(si); 歸還筷子子程序put_chopstick(i) P(mutex); statei=THINKING; test(LEFT); test(RIGHT); V(mutex);獲取筷子子程序take_chopstick(i) P(mutex); statei=HUNGRY; test(i); V(mutex); P(si);測試狀態(tài)子程序test(i) if(statei=HUNGRY & sta