cha3進(jìn)程同步與通信

第二章復(fù)習(xí)程序執(zhí)行的兩種方式，主要區(qū)別進(jìn)程的概念進(jìn)程與程序的主要區(qū)別進(jìn)程的存儲(chǔ)方式進(jìn)程的七種狀態(tài)及其轉(zhuǎn)換掛起狀態(tài)和活動(dòng)狀態(tài)的區(qū)別掛起狀態(tài)和阻塞狀態(tài)的區(qū)別什么是操作系統(tǒng)的內(nèi)核什么是原語核心態(tài)和用戶態(tài)的區(qū)別引入進(jìn)程和線程的主要目的進(jìn)程和線程的區(qū)別第三章進(jìn)程同步與通信3.1同步與互斥的概念3.2互斥的實(shí)現(xiàn)方法3.3信號(hào)量3.4經(jīng)典的進(jìn)程同步問題3.5管程3.6進(jìn)程通信3.1進(jìn)程間的關(guān)系直接制約關(guān)系：2獲得1的消息才可繼續(xù)運(yùn)行進(jìn)程1進(jìn)程2消息間接制約關(guān)系：1釋放資源后2才可使用進(jìn)程－進(jìn)程關(guān)系資源進(jìn)程1進(jìn)程2進(jìn)程－資源－進(jìn)程關(guān)系臨界資源臨界資源一次只允許一個(gè)進(jìn)程使用的資源物理設(shè)備，變量，數(shù)據(jù)……臨界區(qū)進(jìn)程中訪問臨界資源的代碼段臨界資源的例子AR1=XR1=R1+1X=R1BR2=XR2=R2+1X=R2R1=XR2=XR1=R1+1X=R1R2=R2+1X=R2X3344進(jìn)程A和B共享變量X，并對(duì)X進(jìn)行訪問：臨界資源的正確使用進(jìn)入?yún)^(qū)檢查是否可以進(jìn)入 可以－設(shè)置資源的使用標(biāo)志 不行－等待臨界區(qū)使用臨界資源的代碼退出區(qū)清除資源使用標(biāo)志剩余區(qū)不使用臨界資源的部分進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)剩余區(qū)臨界區(qū)的使用規(guī)則每次只能一個(gè)進(jìn)程進(jìn)入臨界區(qū)進(jìn)程在臨界區(qū)內(nèi)停留有限時(shí)間資源空閑時(shí)讓申請(qǐng)進(jìn)程在有限時(shí)間內(nèi)進(jìn)入空閑讓進(jìn)忙則等待有限等待讓權(quán)等待什么是同步多個(gè)進(jìn)程之間有合作關(guān)系各自的執(zhí)行速度不同在關(guān)鍵點(diǎn)上要協(xié)調(diào)進(jìn)度計(jì)算進(jìn)程打印進(jìn)程計(jì)算進(jìn)程快－緩沖裝滿－計(jì)算進(jìn)程等待(打印進(jìn)程)打印進(jìn)程快－緩沖用完－打印進(jìn)程等待(計(jì)算進(jìn)程)緩沖同步過程計(jì)算進(jìn)程打印進(jìn)程數(shù)據(jù)用完，等待執(zhí)行等待生產(chǎn)數(shù)據(jù)，發(fā)送通知數(shù)據(jù)用完，等待時(shí)間什么是互斥多個(gè)進(jìn)程共享某個(gè)資源資源每次只給一個(gè)進(jìn)程使用一個(gè)進(jìn)程釋放后另個(gè)進(jìn)程才可使用進(jìn)程1進(jìn)程2i個(gè)進(jìn)程競爭進(jìn)程1獲得，其他進(jìn)程等待進(jìn)程1釋放，進(jìn)程j獲得，其他進(jìn)程等待打印機(jī)……互斥過程進(jìn)程1進(jìn)程2獲得資源執(zhí)行執(zhí)行等待時(shí)間發(fā)出申請(qǐng)未獲得等待釋放資源，通知獲得資源執(zhí)行釋放資源，通知3.2互斥的實(shí)現(xiàn)方法互斥算法硬件方法鎖機(jī)制假設(shè)兩個(gè)進(jìn)程：P0P1具有互斥關(guān)系P0P1是循環(huán)進(jìn)程算法1設(shè)置整型變量turn=i表示允許進(jìn)程i誰進(jìn)入臨界區(qū)Intturn=0P0:Do{Whileturn=1;臨界區(qū)Turn=1;剩余區(qū)}WhiletrueP1:Do{Whileturn=0;臨界區(qū)Turn=0;剩余區(qū)}Whiletrue可以實(shí)現(xiàn)互斥問題：強(qiáng)迫兩進(jìn)程輪流進(jìn)入臨界區(qū)違反“空閑讓進(jìn)”原則算法2設(shè)置整型數(shù)組flag[]表示進(jìn)程狀態(tài)Booleanflag[2]={false,false}P0:Do{Whileflag[1];flag[0]=true;臨界區(qū)flag[0]=false;剩余區(qū)}WhiletrueP1:Do{Whileflag[0];flag[1]=true;臨界區(qū)flag[1]=false;剩余區(qū)}Whiletrue問題：有時(shí)不能實(shí)現(xiàn)互斥1234abcd1－通過a－通過2b3c同時(shí)進(jìn)入臨界區(qū)算法3設(shè)置整型數(shù)組flag[]表示進(jìn)程的愿望Booleanflag[2]={false,false}P0:Do{flag[0]=true;

Whileflag[1];臨界區(qū)flag[0]=false;剩余區(qū)}WhiletrueP1:Do{flag[1]=true;Whileflag[0];臨界區(qū)flag[1]=false;剩余區(qū)}Whiletrue問題：有時(shí)不能實(shí)現(xiàn)互斥1234abcd1a2－循環(huán)b－循環(huán)同時(shí)希望互相等待算法4設(shè)置整型數(shù)組flag[]表示進(jìn)程的愿望設(shè)置整型變量turn表示允許誰進(jìn)入臨界區(qū)P0:Do{flag[0]=true;

Turn=1;Whileflag[1]andturn==1;臨界區(qū)flag[0]=false;剩余區(qū)}WhiletrueP1:Do{flag[1]=true;Turn=0;Whileflag[0]andturn==0;臨界區(qū)flag[1]=false;剩余區(qū)}Whiletrue1234abcd硬件方法主要思想用一條指令完成標(biāo)志的檢查和修改禁止中斷方法硬件指令方法禁止中斷方法限制了并行——關(guān)中斷后不會(huì)發(fā)生進(jìn)程切換，降低執(zhí)行效率系統(tǒng)失去控制——當(dāng)進(jìn)程關(guān)中斷后不再開中斷，系統(tǒng)會(huì)崩潰P0:關(guān)中斷；臨界區(qū)開中斷；剩余區(qū)P1:關(guān)中斷；臨界區(qū)開中斷；剩余區(qū)硬件指令方法－TS指令

lock初值為假，即資源可用，因此ts返回結(jié)果為真，鎖定資源，用完資源后lock恢復(fù)為假P0:Whilets(lock)；臨界區(qū)Lock=false；剩余區(qū)P1:Whilets(lock)；臨界區(qū)Lock=false；剩余區(qū)Booleants(booleanx){Booleanold;old=x;x

=true;Returnold;}lock初值ts返回值lock終值truetruetruefalsefalsetrue硬件指令方法－swap指令P0:Key=true;Whilekeyswap(lock,key)；臨界區(qū)Lock=false；剩余區(qū)Swap(booleana,booleanb){Booleantemp;temp=a;a=b;b=temp;}lock初值key終值lock終值truetruetruefalsefalsetrueP1:Key=true;Whilekeyswap(lock,key)；臨界區(qū)Lock=false；剩余區(qū)當(dāng)key=false才能進(jìn)入臨界區(qū)硬件方法的特點(diǎn)優(yōu)點(diǎn)適用范圍廣：對(duì)進(jìn)程一視同仁簡單：設(shè)置方法支持多個(gè)臨界區(qū)：對(duì)資源一視同仁缺點(diǎn)忙等待：空循環(huán)，違反讓權(quán)等待原則饑餓現(xiàn)象：隨機(jī)選擇，違反有限等待原則鎖機(jī)制使用鎖變量表示資源狀態(tài)w=0資源空閑w=1資源被占用使用原語對(duì)鎖變量進(jìn)行操作加鎖lock(w)開鎖unlock(w)鎖的使用lock(w){whilew==1;w=1;}unlock(w){w=0;}P0：……lock(w);臨界區(qū)；unlock(w)；……P1：……lock(w);臨界區(qū)；unlock(w)；……通過原語保證資源狀態(tài)的檢查和修改作為一個(gè)整體來執(zhí)行，從而能正確的實(shí)現(xiàn)互斥3.3信號(hào)量信號(hào)量的構(gòu)成整型變量s>0資源的可用數(shù)量=0資源正好夠用<0資源的缺少數(shù)量（q中的進(jìn)程數(shù)）隊(duì)列q等待使用該資源的進(jìn)程信號(hào)量的操作P操作(wait操作)－ 申請(qǐng)資源V操作(signal操作)－釋放資源信號(hào)量的定義structsemaphore{intcount;queuetypequeue;};wait(semaphores){s.count--;ifs.count<0{阻塞該進(jìn)程；進(jìn)程插入s.queue;}}signal(semaphores){s.count++;ifs.count<=0{從s.queue取出頭個(gè)進(jìn)程；進(jìn)程插入就緒隊(duì)列;}}P操作V操作信號(hào)量及P、V操作討論（續(xù)1）1)信號(hào)量的物理含義：

S>0表示有S個(gè)資源可用

S=0表示無資源可用

S<0則|S|表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)P(S)：表示申請(qǐng)一個(gè)資源V(S)：表示釋放一個(gè)資源。信號(hào)量的初值應(yīng)該大于等于0【思考題】司機(jī)進(jìn)程：while(1){啟動(dòng)車輛正常駕駛到站停車}…售票員進(jìn)程：while(1){關(guān)門售票開門}…用P.V操作解決司機(jī)與售票員的問題司機(jī)進(jìn)程：while(1){

啟動(dòng)車輛正常駕駛

到站停車}…售票員進(jìn)程：while(1){關(guān)門

售票開門}…同步信號(hào)量：S1——開車信號(hào)量（初值為0）S2——開門信號(hào)量（初值為0）P(S1)V(S1)V(S2)P(S2)信號(hào)量及P、V操作討論（續(xù)2）2)P.V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)如果P(S1)和P(S2)兩個(gè)操作在一起，那么P操作的順序至關(guān)重要。一個(gè)同步P操作與一個(gè)互斥P操作在一起時(shí)同步P操作在互斥P操作前而兩個(gè)V操作無關(guān)緊要信號(hào)量及P、V操作討論（續(xù)3）3）P、V操作的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：簡單，而且表達(dá)能力強(qiáng)（用P、V操作可解決任何同步互斥問題）缺點(diǎn)：不夠安全，P、V操作使用不當(dāng)會(huì)出現(xiàn)死鎖；遇到復(fù)雜同步互斥問題時(shí)實(shí)現(xiàn)復(fù)雜三、利用P、V操作解決合作進(jìn)程的執(zhí)行次序

若干個(gè)進(jìn)程為了完成一個(gè)共同任務(wù)而并發(fā)執(zhí)行，在這些進(jìn)程中，有些進(jìn)程之間有次序的要求，有些進(jìn)程之間沒有次序的要求，為了描述方便，可以用一個(gè)圖來表示進(jìn)程集合的執(zhí)行次序。如圖P1P2P3P4P1P2P3P4P5P6P1P2P3P4sf1)串行2)串/并行3)并行例題1如圖，試用信號(hào)量實(shí)現(xiàn)這三個(gè)進(jìn)程的同步。

Pa：…V(SB);V(SC);Pb：P(SB);…Pc：P(SC);…PaPbPcSBSC為進(jìn)程Pa和Pb設(shè)置共享公用信號(hào)量SB，為進(jìn)程Pa和Pc設(shè)置共享公用信號(hào)量SC，初值均為0【思考題1】如圖，試用信號(hào)量實(shí)現(xiàn)這三個(gè)進(jìn)程的同步。PaPbPcSBSC【思考題2】如圖，試用信號(hào)量實(shí)現(xiàn)這6個(gè)進(jìn)程的同步S12S13S14S45S26P3P1P2P4P5P6S35S56為進(jìn)程P1和P2設(shè)置共享公用信號(hào)量S12，

P1和P3設(shè)置共享公用信號(hào)量S13，

P1和P4設(shè)置共享公用信號(hào)量S14，

P2和P6設(shè)置共享公用信號(hào)量S26，

P3和P5設(shè)置共享公用信號(hào)量S35，

P4和P5設(shè)置共享公用信號(hào)量S45，

P5和P6設(shè)置共享公用信號(hào)量S56，初值均為0解P4：

P5：

P6：P(S14);P(S35);P(S26);…P(S45);P(S56);…

…

V(S45)；V(S56);P1：P2：P3：…P(S12);P(S13)V(S12);…

…

V(S13)；V(S14);V(S26);V(S35)

總結(jié)進(jìn)程互斥：在OS中，當(dāng)某一進(jìn)程正在訪問cs時(shí)，就不允許其它進(jìn)程來讀寫(訪問)，否則就會(huì)發(fā)生后果無法估計(jì)的錯(cuò)誤，進(jìn)程之間的這種相互制約關(guān)系為進(jìn)程互斥。進(jìn)程同步：并發(fā)進(jìn)程在一些關(guān)鍵點(diǎn)上可能需要互相等待與互通消息，這種相互制約的等待與互通消息，稱為進(jìn)程同步。進(jìn)程同步與互斥關(guān)系：都反映了在異步環(huán)境下并發(fā)進(jìn)程間的相互制約關(guān)系。可歸于同步范疇，但互斥是同步問題的一個(gè)特例，互斥解決臨界區(qū)的使用，同步是并發(fā)進(jìn)程在一些關(guān)鍵點(diǎn)上需互相等待互發(fā)消息。3.4經(jīng)典的進(jìn)程同步問題

生產(chǎn)者/消費(fèi)者問題讀者/寫者問題哲學(xué)家進(jìn)餐問題生產(chǎn)者/消費(fèi)者問題描述通過一個(gè)有界緩沖池(包含N個(gè)緩沖區(qū))可以把一群生產(chǎn)者p1,p2…,pm，和一群消費(fèi)者Q1,Q2,…,Qn聯(lián)系起來。如圖只要緩沖池未滿，生產(chǎn)者就可以把消息送入緩沖池;只要緩沖池未空，消費(fèi)者就可以從緩沖區(qū)中取走消息。圖....生產(chǎn)者(m)：P放消息消費(fèi)者(n)：Q取消息Buffer(n-1)n個(gè)緩沖區(qū)(Buffer)Buffer(0)Buffer(i)生產(chǎn)消息；申請(qǐng)空緩沖區(qū)；放消息；指針↘移動(dòng)；滿緩沖區(qū)+1；申請(qǐng)滿緩沖區(qū)；取消息；指針↗移動(dòng)；釋放空緩沖區(qū)；消費(fèi)消息；Buffer(i)i:0，n-1i=(i+1)%nBuffer(j)j:0，n-1j=(j+1)%n同步信號(hào)量：S1空緩沖區(qū)數(shù)，n；S2滿緩沖區(qū)數(shù)，0?；コ庑盘?hào)量：mutex，1圖生產(chǎn)者(m)：P消費(fèi)者(n)：Q生產(chǎn)消息；申請(qǐng)空緩沖區(qū)；放消息；指針↘移動(dòng)；滿緩沖區(qū)+1；申請(qǐng)滿緩沖區(qū)；取消息；指針↗移動(dòng)；釋放空緩沖區(qū)；消費(fèi)消息；Buffer(i)i:0，n-1i=(i+1)%nBuffer(j)j:0，n-1j=(j+1)%n同步信號(hào)量：S1空緩沖區(qū)數(shù)，n；S2滿緩沖區(qū)數(shù)，0。互斥信號(hào)量：mutex，1buffer:array[0..n-1]ofmessage;i,j=0;生產(chǎn)者P：i=0;

while(1){

生產(chǎn)消息;

P(S1);P(mutex);

往Buffer[i]放消息;i=(i+1)%n;

V(mutex);V(S2);

};消費(fèi)者Q：j=0;while(1){

P(S2);P(mutex);

從Buffer[j]取消息;j=(j+1)%n;

V(mutex);V(S1);

消費(fèi)消息;};【思考題】如果生產(chǎn)者消費(fèi)者問題中的緩沖池是無界的，又該如何解呢？Buffer(0)Buffer(1)．．．Buffer(i)．．．生產(chǎn)者(m)：P消費(fèi)者(n)：Q生產(chǎn)消息；放消息；指針↘移動(dòng)；滿緩沖區(qū)+1；申請(qǐng)滿緩沖區(qū)；取消息；指針↗移動(dòng)；消費(fèi)消息；Buffer(i)i=i+1Buffer(j)j=j+1互斥信號(hào)量：mutex，1同步信號(hào)量：S1滿緩沖區(qū)，0。Q：J=0;while(1){

P(S1);P(mutex);

從Buffer[j]取消息;j=j+1;

V(mutex);

消費(fèi)消息;};互斥信號(hào)量：mutex，1同步信號(hào)量：S1滿緩沖區(qū)，0。P：i=0;while(1){

生產(chǎn)消息;

P(mutex);

往Buffer[i]放消息;i=i+1;

V(mutex);

V(S1);

};【練習(xí)題】有一個(gè)倉庫，可以存放A和B兩種產(chǎn)品，但要求：（1）

每次只能存入一種產(chǎn)品（A或B）（2）

－N＜A產(chǎn)品數(shù)量－B產(chǎn)品數(shù)量＜M。其中，N和M是正整數(shù)。試用P、V操作描述產(chǎn)品A與B的入庫過程。分析：(1)互斥地使產(chǎn)品入庫(2)A-B<M，B-A<N，A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量少N個(gè)以上，A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量多M個(gè)以上倉庫生產(chǎn)產(chǎn)品申請(qǐng)入庫A產(chǎn)品入庫允許B多放入一個(gè)A產(chǎn)品入庫B產(chǎn)品入庫A-B<M，B-A<N生產(chǎn)產(chǎn)品申請(qǐng)入庫B產(chǎn)品入庫允許A多放入一個(gè)互斥信號(hào)量：mutex，1同步信號(hào)量：Sa：表示允許產(chǎn)品A比B多入庫的數(shù)量，初值為M-1；Sb：表示允許產(chǎn)品B比A多入庫的數(shù)量，初值為N-1

B產(chǎn)品入庫進(jìn)程：

while(1){

生產(chǎn)產(chǎn)品

P(Sb);P(mutex);B產(chǎn)品入庫

V(mutex);V(Sa);};A產(chǎn)品入庫進(jìn)程：

while(1){

生產(chǎn)產(chǎn)品;

P(Sa);

P(mutex);A產(chǎn)品入庫

V(mutex);

V(Sb);

};讀者/寫者問題

有兩組并發(fā)進(jìn)程:

讀者和寫者,共享一組數(shù)據(jù)區(qū)要求：允許多個(gè)讀者同時(shí)執(zhí)行讀操作不允許讀者、寫者同時(shí)操作不允許多個(gè)寫者同時(shí)操作第一類：讀者優(yōu)先如果讀者來：1）無讀者、寫者，新讀者可以讀2）有寫者等待寫，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等如果寫者來：1）無讀者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待讀者操作（Reader）：判斷讀者數(shù)，為0則申請(qǐng)數(shù)據(jù)區(qū)；讀者數(shù)+1；讀數(shù)據(jù)；讀者數(shù)-1判斷讀者數(shù)，為0則釋放數(shù)據(jù)區(qū)；寫者操作（Reader）：申請(qǐng)數(shù)據(jù)區(qū)；寫數(shù)據(jù)；釋放數(shù)據(jù)區(qū)；全局變量：readcount(讀者數(shù))，0互斥信號(hào)量：mutex(臨界資源數(shù)據(jù)區(qū))，1 Rmutex(臨界資源readcount)，1讀者操作（Reader）：判斷讀者數(shù)，為0則申請(qǐng)數(shù)據(jù)區(qū)；讀者數(shù)+1；讀數(shù)據(jù)；讀者數(shù)-1判斷讀者數(shù)，為0則釋放數(shù)據(jù)區(qū)；repeatP(Rmutex); ifreadcount=0thenP(mutex);readcount:=readcount+1;V(Rmutex);

讀數(shù)據(jù)；

P(Rmutex);readcount:=readcount-1;ifreadcount=0thenV(mutex);V(Rmutex);untilfalse;全局變量：readcount(讀者數(shù))，0互斥信號(hào)量：mutex(臨界資源數(shù)據(jù)區(qū))，1 Rmutex(臨界資源readcount)，1寫者操作（Reader）：申請(qǐng)數(shù)據(jù)區(qū)；寫數(shù)據(jù)；釋放數(shù)據(jù)區(qū)；寫者（Writer）：repeat P(mutex);

寫；

V(mutex);untilfalse;全局變量：readcount(讀者數(shù))，0互斥信號(hào)量：mutex(臨界資源數(shù)據(jù)區(qū))，1 Rmutex(臨界資源readcount)，1【思考題】寫優(yōu)先修改讀者寫者問題的算法，使之對(duì)寫者優(yōu)先，即一旦有寫者到達(dá)，后續(xù)的讀者必須必須等待，無論是否有讀者在讀。讀者操作（Reader）：是否有寫者正在寫或請(qǐng)求寫？讀者數(shù)+1；判斷讀者數(shù)，為1則申請(qǐng)數(shù)據(jù)區(qū)；允許寫者申請(qǐng)寫；讀數(shù)據(jù)；讀者數(shù)-1判斷讀者數(shù)，為0則釋放數(shù)據(jù)區(qū)；寫者操作（Writer）：申請(qǐng)寫操作；申請(qǐng)數(shù)據(jù)區(qū)；寫數(shù)據(jù)；釋放數(shù)據(jù)區(qū)；釋放寫操作;全局變量：readcount(讀者數(shù))，0互斥信號(hào)量：mutex(臨界資源數(shù)據(jù)區(qū))，1；

Rmutex(臨界資源readcount)，1；

Wmutex(讀者、寫者互斥，寫者與寫者互斥)，1全局變量：readcount(讀者數(shù))，0互斥信號(hào)量：mutex(臨界資源數(shù)據(jù)區(qū))，1；

Rmutex(臨界資源readcount)，1；

Wmutex(讀者、寫者互斥，寫者與寫者互斥)，1Repeat P(Wmutex);P(Rmutex); ifreadcount=0thenP(mutex);readcount:=readcount+1;V(Rmutex); V(Wmutex);

讀數(shù)據(jù)；

P(Rmutex);readcount:=readcount-1;ifreadcount=0thenV(mutex);V(Rmutex);untilfalse;寫者（Writer）：Repeat P(Wmutex); P(mutex);

寫；

V(mutex); V(Wmutex);untilfalse;哲學(xué)家就餐問題思考思考思考思考思考準(zhǔn)備進(jìn)餐進(jìn)餐準(zhǔn)備進(jìn)餐進(jìn)餐問題描述五位哲學(xué)家圍桌而坐哲學(xué)家在思考問題時(shí)不需要任何資源，思考完問題后進(jìn)入進(jìn)餐態(tài)。每人必須獲得左右兩支筷子才能進(jìn)餐哲學(xué)家i：思考；取左手筷子；取右手筷子；吃通心粉；放左手筷子；放右手筷子；第i根筷子第(i+1)%5根筷子Philosopheri：repeat

思考；

P(fork[i]);P(fork[(i+1)%5])；進(jìn)食；

V(fork[i]);V(fork[(i+1)%5])；Untilfalse;互斥信號(hào)量：筷子fork[i]，i取值0-4哲學(xué)家進(jìn)餐問題分析死鎖思考思考思考思考思考準(zhǔn)備進(jìn)餐準(zhǔn)備進(jìn)餐準(zhǔn)備進(jìn)餐準(zhǔn)備進(jìn)餐準(zhǔn)備進(jìn)餐思考P（left_stick）P（right_stick)V（left_stick）eatV（right_stick)解決方法：

1、至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢后釋放出他用過的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。---限制并發(fā)執(zhí)行的進(jìn)程數(shù)

2、僅當(dāng)哲學(xué)家的左右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。---采用信號(hào)量集

3、規(guī)定奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；偶數(shù)號(hào)哲學(xué)家則相反。---保證總會(huì)有一個(gè)哲學(xué)家能同時(shí)獲得兩只筷子而進(jìn)餐

【思考題】

有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上進(jìn)行登記，該表為每一座位列一表目，包括座號(hào)和讀者姓名。讀者離開時(shí)要消掉登記信號(hào)，閱覽室中共有100個(gè)座位，請(qǐng)問：(1)為描述讀者的動(dòng)作，應(yīng)編寫幾個(gè)程序？設(shè)置幾個(gè)進(jìn)程？進(jìn)程與程序間的對(duì)應(yīng)關(guān)系如何？(2)用類Pascal語言和P,V操作寫出這些進(jìn)程間的同步算法。答：(1)應(yīng)編寫1個(gè)程序；設(shè)置2個(gè)進(jìn)程；

進(jìn)程與程序間的對(duì)應(yīng)關(guān)系是：多對(duì)1。進(jìn)閱覽室（P1）：申請(qǐng)空座位；填寫登記表;讀者+1；就座，閱讀；出閱覽室（P2）：讀者-1；消掉登記表；釋放空座位；離開閱覽室;同步信號(hào)量：S1座位數(shù)，100；S2讀者，0互斥信號(hào)量：mutex(臨界資源登記表)，1(2) begin

S1:=100;(有100個(gè)座位)

S2:=0;(閱讀者)

mutex:=1;

cobegin

P1:repeat

P(S1);

P(mutex);

登記信息;

V(mutex);

V(S2)

就座，閱讀；

untilfalse

coend

endP2:repeat

P(S2)

P(mutex);

消掉信息;

V(mutex);

V(S1);

離開閱覽室;

untilfalse2.5管程(monitor)機(jī)制同步操作分散：信號(hào)量機(jī)制中，同步操作分散在各個(gè)進(jìn)程中，使用不當(dāng)就可能導(dǎo)致各進(jìn)程死鎖;易讀性差：要了解對(duì)于一組共享變量及信號(hào)量的操作是否正確，必須通讀整個(gè)系統(tǒng)或者并發(fā)程序；不利于修改和維護(hù)：各模塊的獨(dú)立性差，任一組變量或一段代碼的修改都可能影響全局；正確性難以保證：操作系統(tǒng)或并發(fā)程序通常很大，很難保證這樣一個(gè)復(fù)雜的系統(tǒng)沒有邏輯錯(cuò)誤；信號(hào)量同步的缺點(diǎn)：2.5.1管程的基本概念管程的定義：管程是關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)及一組針對(duì)該資源的操作過程所構(gòu)成的軟件模塊。管程可增強(qiáng)模塊的獨(dú)立性：引入管程可提高代碼的可讀性，便于修改和維護(hù)，正確性易于保證：條件變量(condition)在管程內(nèi)部可以說明和使用一種特殊類型的變量----條件變量。每個(gè)條件變量表示一種阻塞原因，并不取具體數(shù)值－－相當(dāng)于每個(gè)原因?qū)?yīng)一個(gè)隊(duì)列。

條件變量(condition)同步操作原語C.wait和C.signal：針對(duì)條件變量c，執(zhí)行C.wait（c）的進(jìn)程將自己阻塞在c隊(duì)列中，C.signal(c)將c隊(duì)列中的一個(gè)進(jìn)程喚醒。

C.signal(c)

操作的作用，是重新啟動(dòng)一個(gè)被阻塞的進(jìn)程，但如果沒有進(jìn)程被阻塞，則C.signal(c)操作不產(chǎn)生任何效果，這與信號(hào)量機(jī)制中的signal操作不同。管程中的多個(gè)進(jìn)程進(jìn)入當(dāng)一個(gè)進(jìn)入管程的進(jìn)程執(zhí)行喚醒操作時(shí)（如進(jìn)程Ｐ喚醒進(jìn)程Ｑ），管程結(jié)構(gòu)不允許被喚醒的進(jìn)程重新執(zhí)行（管程內(nèi)只能有一個(gè)進(jìn)程）。這種情況有三種可能的解決辦法：P等待Q繼續(xù)，直到Q等待或退出；Hoare采用。Q等待P繼續(xù)，直到P等待或退出；Lampson和Redell采用。規(guī)定喚醒為管程中最后一個(gè)可執(zhí)行的操作，這樣被喚醒的進(jìn)程可以立即執(zhí)行。管程示意圖urgentqueue5.管程的組成管程的組成名稱：數(shù)據(jù)結(jié)構(gòu)說明：一組局部于管程的共享變量操作原語：對(duì)共享變量進(jìn)行操作的一組原語過程（程序代碼），初始化代碼：對(duì)控制變量進(jìn)行初始化的代碼monitorpccharbuffer[n];intnextin,nextout;intcount;conditionnotfull,notempty;append（charx）{ifcount==ncwait(notfull);buffer[nextin]=x;nextin=(nextin+1)%n;count++;csignal(notempty);}take（charx）{ifcount==0cwait(notempty);x=buffer[nextout];nextout=(nextout+1)%n;count--;csignal(notfull);}將進(jìn)程阻塞在notfull的隊(duì)列上2.5.2利用管程解決生產(chǎn)者-消費(fèi)者問題用管程解決PC問題main(){cobeginproducer;consumer;coend}producer(){charx;whiletrue{(produce(x);

append(x);}}consumer(){charx;whiletrue{(take(x);

consume(x);}}管程機(jī)制(復(fù)習(xí))引入原因過多信號(hào)量的使用，容易造成死鎖管程的基本概念把數(shù)據(jù)及其上的一組操作看作一個(gè)整體——管程管程組成局部于管程的局部變量局部于管程的數(shù)據(jù)初值設(shè)置在數(shù)據(jù)上的一組操作2.6進(jìn)程的通信進(jìn)程之間的信息交換低級(jí)通信－－進(jìn)程同步進(jìn)程的同步，簡單的信號(hào)交換如：鎖、信號(hào)量高級(jí)通信－－進(jìn)程通信高效、大量數(shù)據(jù)傳遞2.6.1進(jìn)程通信的類型1.共享存儲(chǔ)器系統(tǒng)

在共享存儲(chǔ)器系統(tǒng)中，相互通信的進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲(chǔ)區(qū)，進(jìn)程之間能夠通過這些空間進(jìn)行通信。共享存儲(chǔ)器系統(tǒng)消息傳遞系統(tǒng)管道通信系統(tǒng)2.6.1進(jìn)程通信的類型

基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式

在這種通信方式中，諸進(jìn)程公用某些數(shù)據(jù)結(jié)構(gòu)，借以實(shí)現(xiàn)諸進(jìn)程間的信息交換。

程序員：提供對(duì)公用數(shù)據(jù)結(jié)構(gòu)的設(shè)置及對(duì)進(jìn)程間同步的控制操作系統(tǒng)：提供共享存儲(chǔ)器

特點(diǎn)：低效，只適合傳遞相對(duì)少量的數(shù)據(jù)。

基于共享存儲(chǔ)區(qū)的通信方式

在存儲(chǔ)器中劃出了一塊共享存儲(chǔ)區(qū)，諸進(jìn)程可通過對(duì)共享存儲(chǔ)區(qū)中數(shù)據(jù)的讀或?qū)憗韺?shí)現(xiàn)通信。

2.6.1進(jìn)程通信的類型2.6.1進(jìn)程通信的類型2.消息傳遞系統(tǒng)消息傳遞系統(tǒng)：進(jìn)程間的數(shù)據(jù)交換，以格式化的消息為單位。計(jì)算機(jī)網(wǎng)絡(luò)：消息稱為報(bào)文。程序員直接利用系統(tǒng)提供的一組通信命令(原語)進(jìn)行通信。2.6.1進(jìn)程通信的類型進(jìn)程2讀出寫入進(jìn)程1寫入進(jìn)程3讀出3.管道通信

所謂“管道”，是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個(gè)共享文件，又名pipe文件。

在進(jìn)程之間通信時(shí)，源進(jìn)程可以直接或間接地將消息傳送給目標(biāo)進(jìn)程。1.直接通信方式通信原語：Send(Receiver,message);發(fā)送一個(gè)消息給接收進(jìn)程Receive(Sender,message);接收Sender發(fā)來的消息2.6.2消息傳遞通信的實(shí)現(xiàn)方法1.直接通信方式利用直接通信原語解決生產(chǎn)者——消費(fèi)者問題

當(dāng)生產(chǎn)者生產(chǎn)出一個(gè)產(chǎn)品(消息)后，便用Send原語將消息發(fā)送給消費(fèi)者進(jìn)程；而消費(fèi)者進(jìn)程則利用Receive原語來得到一個(gè)消息。如果消息尚未產(chǎn)生出來，消費(fèi)者必須等待，直至生產(chǎn)者進(jìn)程將消息發(fā)送過來。Producer:repeat…produceaniteminnextp;…send(consumer,nextp);untilfalse;Consumer:repeatreceive(producer,nextc);…consumetheiteminnextc;untilfalse;1.直接通信方式2.6.2消息傳遞通信的實(shí)現(xiàn)方法2.間接通信方式—信箱消息在信箱中可以安全地保存，只允許核準(zhǔn)的目標(biāo)用戶隨時(shí)讀取。

利用信箱通信方式，既可實(shí)時(shí)通信，又可非實(shí)時(shí)通信。ABCDE中間實(shí)體信箱頭（信箱名、口令）信格信格信格信格信格存放多種格式消息定長消息變長消息2.間接通信方式系統(tǒng)為信箱通信提供若干原語：信箱的創(chuàng)建和撤消消息的發(fā)送和接收

進(jìn)程之間要利用信箱進(jìn)行通信時(shí)，必須使用共享信箱。

Send(mailbox,message);

將一個(gè)消息發(fā)送到指定進(jìn)程

Receive(mailbox,message);

從指定信箱中接收一個(gè)消息2.間接通信方式信箱的分類：私用信箱公用信箱共享信箱利用信箱通信時(shí)，發(fā)送進(jìn)程和接收進(jìn)程之間的四種關(guān)系：一對(duì)一關(guān)系多對(duì)一關(guān)系一對(duì)多關(guān)系多對(duì)多關(guān)系2.6.4消息緩沖隊(duì)列通信機(jī)制

發(fā)送進(jìn)程利用Send原語，將消息直接發(fā)送給接收進(jìn)程；接受進(jìn)程則利用Receive原語接收消息。1.消息緩沖隊(duì)列通信機(jī)制中的數(shù)據(jù)結(jié)構(gòu)(1)消息緩沖區(qū)typemessagebuffer=recordsender;發(fā)送者進(jìn)程標(biāo)識(shí)符

size;消息長度

text;消息正文

next;指向下一個(gè)消息緩沖區(qū)的指針

end2.6.4消息緩沖隊(duì)列通信機(jī)制(2)PCB中有關(guān)通信的數(shù)據(jù)項(xiàng)

增加用于對(duì)消息隊(duì)列進(jìn)行操作和實(shí)現(xiàn)同步的信號(hào)量，并將它們置入進(jìn)程的PCB中。typeprocesscontrolblock=record…mq;消息隊(duì)列隊(duì)首指針

mutex;消息隊(duì)列互斥信號(hào)量

sm;消息隊(duì)列資源信號(hào)量

…endtext:Hellosize:5sender:Asend(B,a)smmutexmqnext:0text:Hellosize:5sender:Atext:Hellosize:5sender:Areceive(b)發(fā)送區(qū)a接收區(qū)b

進(jìn)程A

進(jìn)程B第一消息緩沖區(qū)PCB(B)本章基礎(chǔ)要點(diǎn)進(jìn)程間的同步是指進(jìn)程間在邏輯上的相互制約關(guān)系。在進(jìn)程中訪問臨界資源的代碼稱為臨界區(qū)。為保證進(jìn)程互斥訪問臨界資源，應(yīng)在進(jìn)程的臨界區(qū)前設(shè)置進(jìn)入?yún)^(qū)，在臨界區(qū)后設(shè)置退出區(qū)。進(jìn)程間的相互制約關(guān)系有直接制約關(guān)系和間接制約關(guān)系。臨界區(qū)是一段程序。本章基礎(chǔ)要點(diǎn)并發(fā)進(jìn)程之間的基本關(guān)系是合作或共享資源，其中共享資源是指進(jìn)程之間的一種間接關(guān)系。訪問臨界資源應(yīng)遵循的準(zhǔn)則是：空閑讓進(jìn)、忙則等待、有限等待、讓權(quán)等待。如果信號(hào)量的當(dāng)前值為-4，則表示系統(tǒng)中在該信號(hào)量上有4個(gè)等待進(jìn)程。本章基礎(chǔ)要點(diǎn)在操作系統(tǒng)中，Wait、Signal原語是一種低級(jí)進(jìn)程通信原語。除初值外,信號(hào)量的值只能通過Wait、Signal操作來改變。對(duì)于兩個(gè)并發(fā)進(jìn)程，設(shè)互斥信號(hào)量為mutex，若mutex=0則表示：有一個(gè)進(jìn)程進(jìn)入臨界區(qū)。用Wait、Signal操作管理臨界區(qū)時(shí)，任何一個(gè)進(jìn)程在進(jìn)入臨界區(qū)之前應(yīng)調(diào)用Wait操作，退出臨界區(qū)時(shí)應(yīng)調(diào)用Signal操作。本章基礎(chǔ)要點(diǎn)信號(hào)量的物理意義是：當(dāng)信號(hào)量值大于0時(shí)表示可用資源的數(shù)目；當(dāng)信號(hào)量值小于0時(shí)，其絕對(duì)值為在該信號(hào)量上等待的進(jìn)程個(gè)數(shù)。信箱通信是一種間接通信方式。利用消息機(jī)制實(shí)現(xiàn)通信時(shí)，應(yīng)有發(fā)送原語和接收原語。進(jìn)程通信是指進(jìn)程之間的信息交換。第三章作業(yè)1、有一單向行駛公路橋，每次只允許一輛汽車通過。當(dāng)汽車到達(dá)橋頭時(shí)，若橋上無車，便可上橋；否則需等待，直到橋上的汽車下橋?yàn)橹?。若每一輛汽車為一個(gè)進(jìn)程，請(qǐng)用p，v操作保證汽車按要求過橋。第三章作業(yè)SemaphoreS=1;Pass(){到達(dá)橋頭；P（S）；上橋行駛；到達(dá)橋的另一端；V（S）；}第三章作業(yè)2、有3個(gè)并發(fā)進(jìn)程R、M、P，它們共享一個(gè)循環(huán)使用的緩沖區(qū)B，緩沖區(qū)B共有N個(gè)單元。進(jìn)程R負(fù)責(zé)從輸入設(shè)備讀信息，每讀一個(gè)字符后，把它存入到緩沖區(qū)Ｂ的一個(gè)單元中；進(jìn)程Ｍ負(fù)責(zé)處理讀入的字符，若發(fā)現(xiàn)讀入的字符中有空格符，則把它改成“，”；進(jìn)程Ｐ負(fù)責(zé)把處理后的字符取出并打印輸出。當(dāng)緩沖區(qū)單元中的字符被進(jìn)程Ｐ取出后，則又可用來存放下一次讀入的字符。請(qǐng)用ＰＶ操作寫出它們正確并發(fā)執(zhí)行的程序。提示１、這是一個(gè)三進(jìn)程同步問題，需要考慮該問題中臨界資源有哪些;2、三個(gè)進(jìn)程制約關(guān)系構(gòu)成一個(gè)