并發(fā)性：互斥和同步課件

第5章并發(fā)：互斥與同步Chapter5Concurrency:MutualExclusionandSynchronization內(nèi)容提要并發(fā)原理互斥的軟硬件實(shí)現(xiàn)信號(hào)量（semaphore，旗語/信號(hào)燈）monitor，監(jiān)視器/監(jiān)控程序）消息傳遞讀者-寫者問題1操作系統(tǒng)設(shè)計(jì)的核心問題進(jìn)程與線程的管理（本章中的進(jìn)程也代表線程）多道程序設(shè)計(jì)技術(shù)——管理單[核]處理器系統(tǒng)中的多個(gè)進(jìn)程多處理技術(shù)——管理多[核]處理器系統(tǒng)中的多個(gè)進(jìn)程分布式處理技術(shù)——管理多臺(tái)分布式計(jì)算機(jī)系統(tǒng)中的多個(gè)進(jìn)程并發(fā)（concurrency）~多道程序設(shè)計(jì)/多任務(wù)處理所有問題的基礎(chǔ)/根源操作系統(tǒng)設(shè)計(jì)的基礎(chǔ)并發(fā)發(fā)生的上下文多個(gè)應(yīng)用程序（多道）結(jié)構(gòu)化應(yīng)用程序（模塊）操作系統(tǒng)結(jié)構(gòu)（結(jié)構(gòu)化/模塊）2并發(fā)相關(guān)術(shù)語原子操作（atomicoperation）——不可分割臨界區(qū)（criticalsection）——不允許多個(gè)進(jìn)程同時(shí)進(jìn)入的一段訪問共享資源的代碼死鎖（deadlock）——兩個(gè)及以上進(jìn)程，因每個(gè)進(jìn)程都在等待其他進(jìn)程做完某事（如釋放資源），而不能繼續(xù)執(zhí)行活鎖（livelock）——兩個(gè)及以上進(jìn)程，為響應(yīng)其他進(jìn)程中的變化，而不斷改變自己的狀態(tài)，但是沒有做任何有用的工作互斥（mutualexclusion）——當(dāng)一個(gè)進(jìn)程在臨界區(qū)訪問共享資源時(shí)，不允許其他進(jìn)程進(jìn)入訪問競(jìng)爭(zhēng)條件（racecondition）——多個(gè)進(jìn)程/線程讀寫共享數(shù)據(jù)，其結(jié)果依賴于它們執(zhí)行的相對(duì)速度饑餓（starvation）——可運(yùn)行的進(jìn)程長(zhǎng)期未被調(diào)度執(zhí)行3上篇并發(fā)性引發(fā)的問題資源競(jìng)爭(zhēng)共享、分配管理困難難調(diào)試（不可再現(xiàn)）

進(jìn)程的相互作用通過共享的競(jìng)爭(zhēng)通過共享的合作通過通信的合作進(jìn)程的互斥機(jī)制軟件方法（Dekker算法、Peterson算法）硬件件方法（關(guān)中斷、專用指令TestSet/Exchange）45.1并發(fā)的原理5并發(fā)的基本特征并發(fā)在同一時(shí)間間隔內(nèi)發(fā)生的進(jìn)程或線程，在此期間，它們可能交替地共享相同的資源異步性相對(duì)執(zhí)行速度不可預(yù)測(cè)是多道程序系統(tǒng)的基本特性影響進(jìn)程執(zhí)行速度的因素其他進(jìn)程的活動(dòng)OS處理中斷的方式OS的調(diào)度策略存在的問題全局資源的共享充滿危險(xiǎn)OS對(duì)資源分配的管理難以達(dá)到最優(yōu)調(diào)試程序設(shè)計(jì)錯(cuò)誤非常困難（不可再現(xiàn)性）65.1.1與執(zhí)行速度有關(guān)的錯(cuò)誤解決辦法:控制訪問全局共享資源的代碼！voidecho(){ chin=getchar(); chout=chin; putchar(chout);}ProcessP1

ProcessP2?

?chin=getchar(); ?? chin=getchar();?

chout=chin;?

putchar(chout);chout=chin; ?putchar(chout); ?P1中chin的值在賦值給chout前被P2修改75.1.2競(jìng)爭(zhēng)條件在并發(fā)環(huán)境中發(fā)生多個(gè)進(jìn)程共享數(shù)據(jù)多個(gè)進(jìn)程讀取且至少一個(gè)進(jìn)程寫入共享數(shù)據(jù)的最終結(jié)果取決于進(jìn)程執(zhí)行的相對(duì)速度85.1.3OS必須考慮的問題并發(fā)環(huán)境中跟蹤每個(gè)進(jìn)程，知道它們的狀態(tài)為每個(gè)進(jìn)程分配和回收各種資源（管理資源）處理機(jī)（進(jìn)程調(diào)度）存儲(chǔ)器（內(nèi)存管理）文件（文件系統(tǒng)）I/O設(shè)備（I/O管理）保護(hù)進(jìn)程擁有的數(shù)據(jù)和物理資源保證進(jìn)程的結(jié)果與相對(duì)執(zhí)行速度無關(guān)（邏輯上的正確性）95.1.4

進(jìn)程間的相互作用間接作用因?yàn)楣蚕矶?jìng)爭(zhēng)通過共享實(shí)現(xiàn)合作直接作用通過通信的合作10進(jìn)程間的競(jìng)爭(zhēng)現(xiàn)象特點(diǎn)：獨(dú)立設(shè)計(jì)的進(jìn)程，每個(gè)進(jìn)程不知道其他進(jìn)程的存在（“萍水相逢”、“我不知道你是誰”）兩個(gè)或更多進(jìn)程在各自的執(zhí)行過程中需要訪問相同的資源（I/O設(shè)備、存儲(chǔ)器、CPU、時(shí)鐘等）（“獨(dú)木橋上，狹路相逢”）進(jìn)程之間沒有信息交換的要求（“井水不犯河水”）相互間產(chǎn)生的影響：執(zhí)行結(jié)果不會(huì)受影響執(zhí)行時(shí)間受影響競(jìng)爭(zhēng)引發(fā)的控制問題互斥(mutualexclusion)死鎖(deadlock)饑餓(starvation)11互斥的關(guān)聯(lián)概念互斥（mutualexclusion）多個(gè)進(jìn)程需要訪問一個(gè)不可共享的資源時(shí)，任何時(shí)候只能有一個(gè)訪問這個(gè)資源臨界資源（criticalresource）不可共享的資源臨界區(qū)（criticalsection）訪問臨界資源的那部分代碼死鎖(deadlock)一組進(jìn)程中，每個(gè)進(jìn)程都無限等待該組進(jìn)程中另一進(jìn)程所占用的資源饑餓(starvation)一組進(jìn)程中，某個(gè)或某些進(jìn)程無限等待該組進(jìn)程中其他進(jìn)程所占用的資源12互斥機(jī)制原理—程序框架voidP1(){while(true){/*precedingcode*/entercritical(Ra);/*criticalsectionRa*/exitcritical(Ra);/*followingcode*/}}voidP2(){….}voidmain(){parbegin(P1(),P2(),…,Pn());}voidPn(){….}競(jìng)爭(zhēng)資源Ra的臨界區(qū)13進(jìn)程間通過共享的合作特點(diǎn)沒有意識(shí)到其他進(jìn)程的存在，但知道要維護(hù)數(shù)據(jù)的完整性共享變量、文件或數(shù)據(jù)庫等相互間產(chǎn)生的影響：執(zhí)行結(jié)果可能會(huì)受影響執(zhí)行時(shí)間受影響共享引發(fā)的控制問題互斥死鎖饑餓數(shù)據(jù)的一致性P1:

P2:?

?a=a+1; ?? b=2*b;b=b+1; ?

?

a=2*a;14進(jìn)程間通過通信的合作特點(diǎn)進(jìn)程直接知道合作伙伴采用消息傳送的方式通信（發(fā)送/接收消息）相互間產(chǎn)生的影響：同“通過共享的合作”引發(fā)的控制問題:死鎖饑餓155.1.5互斥的要求在具有相同資源或共享對(duì)象的臨界區(qū)的所有進(jìn)程中，一次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)（強(qiáng)制排它）一個(gè)在非臨界區(qū)停止的進(jìn)程必須不干涉其他進(jìn)程（充分并發(fā)）沒有進(jìn)程在臨界區(qū)中時(shí)，任何需要訪問臨界區(qū)的進(jìn)程必須能夠立即進(jìn)入（空閑讓進(jìn)）決不允許出現(xiàn)一個(gè)需要訪問臨界區(qū)的進(jìn)程被無限延遲（有限等待）相關(guān)進(jìn)程的執(zhí)行速度和處理機(jī)數(shù)目沒有任何要求或限制（滿足異步）當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)，應(yīng)該立即釋放處理機(jī)，防止進(jìn)程忙等待（讓權(quán)等待）16實(shí)現(xiàn)互斥的方法軟件方法Dekker算法Peterson算法硬件方法TestSet指令Exchange指令OS或程序設(shè)計(jì)語言的支持信號(hào)量管程消息機(jī)制17第一種嘗試的方案用turn序來輪流18第一種嘗試的特點(diǎn)可以保證互斥硬性規(guī)定進(jìn)入的順序兩個(gè)進(jìn)程輪流進(jìn)入臨界區(qū)存在問題忙等待

(busywaiting):為了等待一事件的發(fā)生，重復(fù)執(zhí)行一段循環(huán)代碼----白白消耗CPU時(shí)間必須輪流進(jìn)入臨界區(qū)----不合理，限制推進(jìn)速度如果一個(gè)進(jìn)程失敗，另一個(gè)將被永遠(yuǎn)阻塞結(jié)論難以支持并發(fā)處理19第二種嘗試的方案用flag[i]標(biāo)志進(jìn)程i進(jìn)入臨界區(qū)20第二種嘗試的特點(diǎn)每個(gè)進(jìn)程應(yīng)有自己進(jìn)入臨界區(qū)的“鑰匙”進(jìn)程設(shè)置標(biāo)志表示自己進(jìn)入和離開可以檢查對(duì)方標(biāo)志先查對(duì)方標(biāo)志再設(shè)置自己進(jìn)入臨界區(qū)的標(biāo)志存在問題一個(gè)進(jìn)程在臨界區(qū)內(nèi)失敗，另一進(jìn)程永遠(yuǎn)被阻塞不能保證互斥!（見示意圖）結(jié)論錯(cuò)誤方案，不能保證進(jìn)程的運(yùn)行結(jié)果與執(zhí)行速度無關(guān)21第二種嘗試的失效示意圖P0:

●while(Flag[1])/*donothing*/;Flag[0]=true;/*criticalsection*/Flag[0]=false;● ● P1:

●while(Flag[0])/*donothing*/;Flag[1]=true;/*criticalsection*/Flag[1]=false;● ● 如果在紅線處被切換，則可能兩個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)22第三種嘗試的方案將flag[i]標(biāo)志的設(shè)置，提前到循環(huán)等待之前23第三種嘗試的特點(diǎn)先表示自己想進(jìn)入臨界區(qū)，再檢查對(duì)方是否已進(jìn)入可以保證互斥問題可能導(dǎo)致死鎖!死鎖產(chǎn)生的原因兩進(jìn)程都堅(jiān)持要進(jìn)入（見示意圖）第三種嘗試的死鎖時(shí)序P1:

●Flag[0]=true;while(Flag[1]);● ● P2:

●Flag[1]=true;while(Flag[0]);● ● 第四種嘗試的方案在循環(huán)等待中用延時(shí)給其他進(jìn)程進(jìn)入的機(jī)會(huì)26第四種嘗試的特點(diǎn)解決思路

禮讓，等一會(huì).可以保證互斥問題會(huì)導(dǎo)致活鎖死鎖與活鎖死鎖:都想進(jìn)入臨界區(qū)，但都不能進(jìn)入活鎖:本來可以進(jìn)入臨界區(qū)，但都進(jìn)入不了27第四種嘗試的活鎖時(shí)序P0:

●Flag[0]=true;while(Flag[1]){Flag[0]=false;delay();Flag[0]=true;}/*criticalsection*/Flag[0]=false;● P1:

●Flag[1]=true;while(Flag[0]){Flag[1]=false;delay();Flag[1]=true;}/*criticalsection*/Flag[1]=false;● booleanflag[2];intturn;voidP0(){while(true){flag[0]=true;//自己想進(jìn)臨界區(qū)//flag[1]==false時(shí)進(jìn)入臨界區(qū)

while(flag[1]){//flag[1]==true時(shí)等待if(turn==1){//turn==1時(shí)禮讓flag[0]=false;while(turn==1)/*donothing*/;flag[0]=true;}}/*criticalsection*/turn=1;flag[0]=false;/*remainder*/}}Dekker算法1965年荷蘭數(shù)學(xué)家T.J.Dekker（德克）避免“無原則”的禮讓規(guī)定各進(jìn)程進(jìn)入臨界區(qū)的順序用全局?jǐn)?shù)組變量flag表示互斥進(jìn)程的位置用全局變量turn解決同時(shí)發(fā)生的沖突參見附錄A“并發(fā)主題”中的A.1.1（P502）Dekker

算法描述29Dekker

算法描述（續(xù)）voidP1(){while(true){flag[1]=true;//自己想進(jìn)臨界區(qū)//flag[0]==false時(shí)進(jìn)入臨界區(qū)while(flag[0]){//flag[0]==true時(shí)等待if(turn==0){//turn==0時(shí)禮讓flag[1]=false;while(turn==0)/*donothing*/;flag[1]=true;}}/*criticalsection*/turn=0;flag[1]=false;/*remainder*/}}voidmain(){flag[0]=false;flag[1]=false;turn=1;parbegin(P0,P1);}算法的問題邏輯復(fù)雜正確性難證明存在輪流問題存在忙等待30booleanflag[2];intturn;voidP0(){while(true){flag[0]=true;turn=1;while(flag[1]&&turn==1)/*donothing*/;/*criticalsection*/flag[0]=false;/*remainder*/}}Peterson算法1981年數(shù)學(xué)家G.L.Peterson（彼得森）簡(jiǎn)單出色（不存在輪流問題）flag和turn的含義同Dekker的但先設(shè)turn=別人，且只有“flag[別人]”和“turn=別人”同時(shí)為真時(shí)才循環(huán)等待參見附錄A“并發(fā)主題”中的A.1.2（P505）Peterson

算法描述31Peterson

算法描述（續(xù)）voidP1(){while(true){flag[1]=true;turn=0;while(flag[0]&&turn==0)

/*donothing*/;/*criticalsection*/flag[1]=false;/*remainder*/}}voidmain(){flag[0]=false;flag[1]=false;parbegin(P0,P1);}32硬件實(shí)現(xiàn)方法—關(guān)中斷中斷禁用的（關(guān)中斷）原理單CPU體系結(jié)構(gòu)如果進(jìn)程訪問臨界資源時(shí)（執(zhí)行臨界區(qū)代碼）不被中斷，就能保證互斥地訪問途徑使用關(guān)/開中斷指令x86的開/關(guān)指令為STI/CLI缺點(diǎn)限制了處理器交替執(zhí)行各進(jìn)程的能力不能用于多[核]處理器結(jié)構(gòu)●●●關(guān)中斷指令臨界區(qū)開中斷指令●●●33硬件實(shí)現(xiàn)方法—專用指令適用范圍單處理器或共享主存多[核]處理器結(jié)構(gòu)對(duì)同一存儲(chǔ)單元的訪問是互斥的軟件算法第二種嘗試失敗的原因如果測(cè)flag[1]和置位flag[0]在一個(gè)指令周期完成就不會(huì)出錯(cuò)34比較和交換指令原子指令——一個(gè)指令周期內(nèi)完成,不會(huì)被中斷由兩部分構(gòu)成：比較內(nèi)存單元與測(cè)試值，不同則產(chǎn)生交換檢查內(nèi)存單元*word的值是否與測(cè)試值testval相等，若相等就用newval取代該值，否則保持不變總是返回舊內(nèi)存單元的值。若返回值=測(cè)試值，則表示該內(nèi)存單元已經(jīng)被更新486以上的x86/x64CPU的對(duì)應(yīng)指令為CMPXCHG，可用于操作系統(tǒng)支持并發(fā)比較和交換指令的定義（等價(jià)代碼段）intcompare_and_swap(int*word,inttestval,intnewval){ intoldval; oldval=*word if(oldval==testval)*word=newval; returnoldval;}例如：(bolt=門閂/鎖條)If(compare_and_s,0,1)==0)

{/*criticalsection*/}TestSet指令(TS)定義（邏輯）——比較并交換指令的bool特例原子指令等價(jià)代碼段：booleantestset(inti){ if(i==0){ i=l; returntrue; }else returnfalse;}37TestSet指令

—解決方案/*programmutualexclusion*/constintn=/*numberofprocesses*/;intbolt;voidp(inti){ while(true){while(!testset(bolt))/*donothing*/; /*criticalsection*/ bolt=0; /*remainder*/}}voidmain(){bolt=0;parbegin(p(1),p(2),…,p(n));}第二種嘗試的專用指令版只有測(cè)試bolt==0的進(jìn)程才能進(jìn)入臨界區(qū)(bolt=門閂/鎖條)38exchange指令定義（邏輯）——交換一個(gè)寄存器和內(nèi)存單元的內(nèi)容原子操作x86CPU的對(duì)應(yīng)指令為XCHG等價(jià)代碼段：voidexchange(intregister,intmemory){ inttemp; temp=memory; memory=register; register=temp;}39exchange指令—

解決方案/*programmutualexclusion*/constintn=/*numberofprocesses*/intbolt;voidp(inti){intkeyi=1;while(true){ doexchange(keyi,bolt);

while(keyi!=0);/*criticalsection*/ bolt=0;/*remainder*/}}voidmain(){bolt=0;parbegin(p(1),p(2),…,p(n));}只有發(fā)現(xiàn)bolt=0的進(jìn)程才能進(jìn)入臨界區(qū)算法的本質(zhì)：bolt+∑keyi=nbolt=0：臨界區(qū)無進(jìn)程bolt=1：只有keyi=0的進(jìn)程在臨界區(qū)40機(jī)器指令方法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)適用于單處理器或共享主存多[核]處理器系統(tǒng)，進(jìn)程數(shù)目任意簡(jiǎn)單且易于證明可以使用多個(gè)變量支持多個(gè)臨界區(qū)缺點(diǎn)忙等待（busywaiting）/自旋等待（spinwaiting）可能饑餓可能死鎖41下篇信號(hào)量（semaphore）管程（monitor）消息傳遞讀者-寫者問題42常用并發(fā)機(jī)制并發(fā)機(jī)制說明信號(hào)量用于進(jìn)程間傳遞信號(hào)的一個(gè)整數(shù)值，只有初始化、增、減三種原子操作，可阻塞/解除阻塞進(jìn)程二元信號(hào)量取值只為0和1的信號(hào)量互斥量似二元信號(hào)量，但要求為其加鎖和解鎖的須是同一進(jìn)程條件變量一種數(shù)據(jù)類型，用于阻塞進(jìn)程/線程，直到特定條件為真管程一種編程語言結(jié)構(gòu)，封裝了代表臨界區(qū)的若干過程事件標(biāo)志用于同步機(jī)制的內(nèi)存字，其每個(gè)位關(guān)聯(lián)不同的事件信箱/消息進(jìn)程間交換信息的一種方法，也可用于同步自旋鎖一種互斥機(jī)制，進(jìn)程在一無條件循環(huán)中執(zhí)行，等待鎖變量值變?yōu)榭捎?3445.3

信號(hào)量(semaphore)semaphore[‘sem?f?:(r)]——信號(hào)燈/機(jī)/量、 旗語、（鐵道）臂板信號(hào)裝置信號(hào)量機(jī)制由（1972年的圖靈獎(jiǎng)獲得者，實(shí)現(xiàn)了ALGOL60的編譯器、提出了圖論中最短路徑的Dijkstra算法的）荷蘭計(jì)算機(jī)科學(xué)家E.W.Dijkstra提出(1965)，是解決并發(fā)進(jìn)程問題的第一個(gè)重要進(jìn)展，需要OS支持兩個(gè)或多個(gè)進(jìn)程可以通過傳遞信號(hào)進(jìn)行合作，從而可以迫使進(jìn)程在某指定位置停住，直到它收到特定信號(hào)信號(hào)量機(jī)制可以滿足任何復(fù)雜的合作要求信號(hào)量的（整數(shù)）值在并發(fā)中常用來表示可用資源的數(shù)目信號(hào)量機(jī)制的組成由OS提供的用于進(jìn)程并發(fā)控制的一種特殊數(shù)據(jù)結(jié)構(gòu)含有一個(gè)整數(shù)變量和三個(gè)專門操作：初始化、P（荷蘭語proberen，測(cè)試/通過）操作和V（荷蘭語verhogen，增量/釋放）操作EdsgerWybeDijkstra(1930-2002)45對(duì)信號(hào)量的操作初始化通常將信號(hào)量的值初始化為非負(fù)整數(shù)（=可用資源數(shù)）P操作/semWait操作/Down操作信號(hào)量的值減1若信號(hào)量的值變成負(fù)數(shù)，則執(zhí)行P操作的進(jìn)程被阻塞V操作/semSignal操作/Up操作信號(hào)量的值加1如果信號(hào)量的值不是正數(shù)（其絕對(duì)值=現(xiàn)被阻塞的進(jìn)程數(shù)[等待隊(duì)列的長(zhǎng)度]），則使一個(gè)因執(zhí)行P操作被阻塞的進(jìn)程解除阻塞（喚醒）此外，沒有其他檢查和修改信號(hào)量值的操作46信號(hào)量和P、V操作原語的描述structsemaphore{//定義結(jié)構(gòu)intcount;queueType*queue;}s;voidP(semaphores){//P操作s.count--;if(s.count<0)Block(CurruntProcess,s.queue);}voidV(semaphores){//V操作s.count++;if(s.count<=0)WakeUp(s.queue);}//初始化s.count=nr;s.queue=malloac(m*sizeof(queueType));47信號(hào)量和wait、signal原語的描述(~P&V)structsemaphore{ intcount; queueTypequeue;};voidsemWait(semaphores){ s.count--; if(s.count<0){ /*placethisprocessins.queue*/ /*blockthisprocess*/ }}voidsemSignal(semaphores){ s.count++; if(s.count<=0){ /*removeaprocessPfroms.queue*/ /*placeprocessPonreadylist*/ }}48二元信號(hào)量信號(hào)量的取值只能是0或1和一般信號(hào)量具有相同的表達(dá)能力因count不能<0，得用另外的方法來判斷等待隊(duì)列是否為空49二元信號(hào)量和操作原語的描述structsemaphore{intcount;queueType*queue;}s;voidsemWaitB(semaphores){if(s.count==1)s.count=0;elseBlock(CurruntProcess,s.queue);}voidsemSignalB(semaphores){if(s.queueisempty)s.count==1;elseWakeUp(s.queue);}50強(qiáng)信號(hào)量與弱信號(hào)量在一個(gè)信號(hào)量上等待的各個(gè)進(jìn)程形成隊(duì)列，這些進(jìn)程以什么順序進(jìn)出隊(duì)列？強(qiáng)信號(hào)量進(jìn)出隊(duì)列的順序是FIFO（First-InFirst-Out，先進(jìn)先出）保證不會(huì)饑餓弱信號(hào)量沒有規(guī)定進(jìn)程從隊(duì)列移出的順序不能保證不會(huì)饑餓51信號(hào)量的實(shí)際含義信號(hào)量s（s.count）的初值系統(tǒng)中某類資源的數(shù)目，應(yīng)該>=0進(jìn)程執(zhí)行P(s)/semWait(s)操作申請(qǐng)一個(gè)單位的資源(s.count--)當(dāng)s.count<0時(shí)，資源已分配完畢，進(jìn)程自己阻塞在s的隊(duì)列上----讓權(quán)等待進(jìn)程執(zhí)行V(s)/semSignal(s)操作釋放一個(gè)單位資源(s.count++)若s.count<=0，則喚醒一個(gè)等待進(jìn)程s.count>=0：可用的資源數(shù)/可以執(zhí)行P(s)而不會(huì)阻塞的進(jìn)程數(shù)<0：|s.count|為在隊(duì)列中等待的進(jìn)程數(shù)52信號(hào)量的實(shí)現(xiàn)基本要求保證P/semWait和V/semSignal操作的原子性，以保證信號(hào)量操作的互斥軟件方案Dekker算法Peterson算法硬件支持方案可以采用TS指令關(guān)中斷53信號(hào)量的TestSet指令實(shí)現(xiàn)方案structsemaphore{

intflag;intcount;queueType*queue;}s;voidsemWaitT(semaphores){

while(!testset(s.flag));s.count--;if(s.count<0)Block(CurruntProcess,s.queue);s.flag=0;}voidsemSignalT(semaphores){

while(!testset(s.flag));s.count++;if(s.count<=0)WakeUp(s.queue);s.flag=0;}臨界區(qū)54信號(hào)量的關(guān)中斷實(shí)現(xiàn)方案structsemaphore{intcount;queueType*queue;}s;voidsemWaitI(semaphores){

inhibitinterrupts;s.count--;if(s.count<0)Block(CurruntProcess,s.queue);

allowinterrupts;}voidsemSignalI(semaphores){

inhibitinterrupts;s.count++;if(s.count<=0)WakeUp(s.queue);

allowinterrupts;}臨界區(qū)55信號(hào)量的優(yōu)缺點(diǎn)優(yōu)點(diǎn)簡(jiǎn)單，而且表達(dá)能力強(qiáng)用P、V操作可解決多種類型的同步/互斥問題缺點(diǎn)不夠安全，P、V操作使用不當(dāng)會(huì)產(chǎn)生死鎖遇到復(fù)雜同步互斥問題時(shí)實(shí)現(xiàn)復(fù)雜56信號(hào)量機(jī)制的應(yīng)用實(shí)現(xiàn)互斥進(jìn)程同步生產(chǎn)者-消費(fèi)者問題讀者-寫者問題其它5.3.1用信號(hào)量實(shí)現(xiàn)互斥n個(gè)進(jìn)程訪問同一個(gè)共享資源（臨界資源）將信號(hào)量s初始化為1每個(gè)進(jìn)程進(jìn)入臨界區(qū)之前執(zhí)行P操作s--若s>=0，則進(jìn)程進(jìn)入臨界區(qū)若s<0，則進(jìn)程被阻塞不能進(jìn)入臨界區(qū)，加入等待隊(duì)列進(jìn)程離開臨界區(qū)時(shí)執(zhí)行V操作s++若s<=0，則喚醒一個(gè)被阻塞的進(jìn)程，將其移出等待隊(duì)列，置為就緒狀態(tài)，使其在下次操作系統(tǒng)調(diào)度時(shí)可進(jìn)入臨界區(qū)這樣可以保證最多只有一個(gè)進(jìn)程在臨界區(qū)，從而實(shí)現(xiàn)了共享資源的互斥訪問5758用信號(hào)量實(shí)現(xiàn)互斥（續(xù)）一種可能的執(zhí)行情況用信號(hào)量實(shí)現(xiàn)進(jìn)程同步進(jìn)程的同步（synchronization）指系統(tǒng)中一些進(jìn)程需要相互合作，共同完成一項(xiàng)任務(wù)。具體說，一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于阻塞狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài)。司機(jī)(P1) 售票員(P2)

REPEAT REPEAT

啟動(dòng) 關(guān)門

正常行駛售票

到站停車 開門

UNTILFALSEUNTILFALSE5960用信號(hào)量實(shí)現(xiàn)進(jìn)程同步--舉例例:有三個(gè)進(jìn)程并發(fā)運(yùn)行，合作完成輸入數(shù)據(jù)、計(jì)算和打印輸出工作進(jìn)程PI將輸入的數(shù)據(jù)寫入緩沖區(qū)B1,進(jìn)程PC讀出B1中的數(shù)據(jù)，完成計(jì)算，把結(jié)果寫入緩沖區(qū)B2進(jìn)程PP讀出B2中的結(jié)果，打印輸出同步要求:（讀出數(shù)據(jù)后緩沖區(qū)為空）(1)先寫后讀（不能讀空緩沖區(qū)）(2)未讀完不能寫（不能寫非空緩沖區(qū)）61用信號(hào)量實(shí)現(xiàn)進(jìn)程同步（續(xù)）設(shè)置四個(gè)信號(hào)量：empty1、full1、empty2、full2初始分別為：1、0、1、0（即兩個(gè)緩沖區(qū)都為空）三個(gè)進(jìn)程的描述PI:while(1){P(empty1);

輸入數(shù)據(jù)寫到B1;V(full1);}

PP:while(1){P(full2);

讀取B2中的結(jié)果并輸出到打印機(jī);V(empty2);}

PC:while(1){P(full1);

從B1中讀取數(shù)據(jù);V(empty1);

計(jì)算;P(empty2);

結(jié)果寫到B2;V(full2);}

625.3.2生產(chǎn)者/消費(fèi)者問題并發(fā)處理的最常見問題類型問題描述若干進(jìn)程通過無限/有限的共享緩沖區(qū)交換數(shù)據(jù)一組“生產(chǎn)者”進(jìn)程不斷寫入另一組“消費(fèi)者”進(jìn)程不斷讀出共享緩沖區(qū)無限/共有N個(gè)任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩沖區(qū)進(jìn)行操作63無限緩沖區(qū)的(二元信號(hào)量)解決方案intn;/*緩沖區(qū)中產(chǎn)品數(shù)*/Binary_semaphores=1;/*互斥*/Binary_semaphoredelay=0;/*等待*/voidproducer(){while(true){produce();semWaitB(s);append();n++;if(n==1)semSignalB(delay);semSignalB(s);}}voidconsumer(){semWaitB(delay);while(true){semWaitB(s);take();n--;semSignalB(s);consume();if(n==0)semWaitB(delay);} 少執(zhí)行一次}voidmain(){n=0;parbegin(producer,consumer);}存在漏洞：超前消費(fèi)切換→64基于二元信號(hào)量的正確解決方案intn;Binary_semaphores=1;Binary_semaphoredelay=0;voidproducer(){while(true){produce();semWaitB(s);append();n++;if(n==1)semSignalB(delay);semSignalB(s);}}voidconsumer(){intm;semWaitB(delay);while(true){semWaitB(s);take();n--;

m=n;semSignalB(s);consume();if(m==0)semWaitB(delay);}}65基于計(jì)數(shù)信號(hào)量的正確解決方案semaphoren=0;/*緩沖區(qū)中的產(chǎn)品數(shù)*/semaphores=1;/*互斥*/voidproducer(){while(true){produce();semWait(s);append();semSignal(s);semSignal(n);}}voidconsumer(){while(true){semWait(n);semWait(s);take();semSignal(s);consume();}}voidmain(){parbegin(producer,consumer);}顛倒順序后會(huì)產(chǎn)生死鎖有限緩沖區(qū)的生產(chǎn)者/消費(fèi)者問題對(duì)象被阻塞事件解除阻塞事件生產(chǎn)者插入滿緩沖區(qū)消費(fèi)者移出一項(xiàng)消費(fèi)者從空緩沖區(qū)移出生產(chǎn)者插入一項(xiàng)6667有限循環(huán)緩沖區(qū)的解決方案constintsizebuffer=Nsemaphoren=0;/*產(chǎn)品數(shù)*/semaphores=1;/*互斥*/semaphoree=N;/*空閑數(shù)*/voidproducer(){while(true){produce();semWait(e);semWait(s);append();semSignal(s);semSignal(n);}}voidconsumer(){while(true){semWait(n);semWait(s);take();semSignal(s);semSignal(e);consume();}}voidmain(){parbegin(producer,consumer);}68理發(fā)店問題用信號(hào)量或管程實(shí)現(xiàn)并發(fā)的經(jīng)典例子（參見P511的附錄A.3）問題描述：3個(gè)理發(fā)師、3張理發(fā)椅、一張沙發(fā)4個(gè)位、一個(gè)收銀機(jī)、室內(nèi)最多容納20個(gè)顧客、共有50個(gè)顧客，有位則坐，無位則站69動(dòng)機(jī)同步機(jī)制與同步策略的分離是靈活的，同時(shí)也是危險(xiǎn)的集中管理（封裝）以策安全管程(monitor)是一種封裝同步機(jī)制與同步策略的程序設(shè)計(jì)語言結(jié)構(gòu)Ada95、并發(fā)Pascal、Modula-3、Java、C#、Delphi、Python、Ruby、Mesa等1972年由英國計(jì)算機(jī)科學(xué)家C.A.R.Hoare和美籍丹麥計(jì)算機(jī)科學(xué)家P.B.Hansen發(fā)明5.4管程701974年Hoare提出的管程方案1975年Hansen在并發(fā)Pascal上實(shí)現(xiàn)主要特點(diǎn)：本地變量只能由管程過程訪問（封裝）進(jìn)程通過調(diào)用管程過程進(jìn)入管程（調(diào)用）每次只能一個(gè)進(jìn)程在執(zhí)行相關(guān)管程的過程（互斥）主要缺陷可能增加了兩次多余的進(jìn)程切換對(duì)進(jìn)程調(diào)度有特殊要求（不允許插隊(duì)）5.4.1使用信號(hào)的管程管程的結(jié)構(gòu)和應(yīng)用管程軟件模塊的組成若干過程一個(gè)初始化序列局部數(shù)據(jù)條件變量管程提供的互斥機(jī)制管程中的數(shù)據(jù)每次只能被一個(gè)進(jìn)程訪問可將共享數(shù)據(jù)結(jié)構(gòu)放入管程以得到保護(hù)可用這些數(shù)據(jù)代表臨界資源管程對(duì)同步的支持通過cwait(c)、csignal(c)操作管程中的條件變量實(shí)現(xiàn)同步7172有限緩沖區(qū)生產(chǎn)者/消費(fèi)者的管程解決方案Amonitorboundedbuffer{/*管程體*/charbuffer[N];intnextin,nextout;/*局部數(shù)據(jù)*/intcount;/*產(chǎn)品數(shù)*/condnotfull,notempty;/*條件變量*/voidappend(charx){/*添加過程*/if(count==N)cwait(notfull);buffer[nextin]=x;nextin=(nextin+1)%N;count++;csignal(notempty);}voidtake(charx){/*取出過程*/if(count==0)cwait(notempty);x=buffer[nextout];nextout=(nextout+1)%N;count--;csignal(notfull);}{nextin=0;nextout=0;count=0;}/*初始化*/}voidproducer(){charx;/*產(chǎn)品=字符*/while(true){produce(x);append(x);}}voidcomsumer(){管程過程調(diào)用charx;while(true){take(x);comsume(x);}}voidmain(){parbegin(producer,consumer);}使用信號(hào)的管程存在的問題定義要求在條件隊(duì)列中至少有一個(gè)進(jìn)程?當(dāng)另一進(jìn)程為該條件產(chǎn)生csignal信號(hào)時(shí)，則產(chǎn)生此信號(hào)的進(jìn)程必須立即退出管程（或阻塞在管程上），以便讓隊(duì)列中被喚醒的進(jìn)程能夠立即進(jìn)入管程運(yùn)行如果產(chǎn)生csignal信號(hào)的進(jìn)程在管程內(nèi)的運(yùn)行還未結(jié)束，則需要兩次額外的進(jìn)程切換（阻塞以讓被喚醒的進(jìn)程運(yùn)行，等其運(yùn)行結(jié)束后再恢復(fù)運(yùn)行）進(jìn)程調(diào)度程序必須保證在激活被喚醒的進(jìn)程前沒有其他進(jìn)程進(jìn)入管程，否則可能造成永久阻塞解決辦法：采用使用通知和廣播的管程741980年2月美國計(jì)算機(jī)科學(xué)家B.W.Lampson和D.D.Redell為Mesa語言開發(fā)的一種管程方案（也可用于Modula-3）主要特點(diǎn)：用cnotify原語代替原來的csignal操作（發(fā)通知的進(jìn)程不需立即退出管程，接到通知的進(jìn)程也不立即被喚醒，只是轉(zhuǎn)為就緒，等待合適的時(shí)候再進(jìn)入管程運(yùn)行）用while循環(huán)代替if判斷（有額外的條件變量檢查，但可避免額外的兩次進(jìn)程切換）等待條件增加計(jì)時(shí)器，等待超時(shí)的進(jìn)程將被轉(zhuǎn)為就緒cnotify原語通知特定等待條件隊(duì)列中的第一個(gè)等待進(jìn)程，但當(dāng)前執(zhí)行cnotify原語的進(jìn)程繼續(xù)執(zhí)行被通知的等待進(jìn)程轉(zhuǎn)為就緒，但必須重新檢查條件。cbroadcast原語通知特定等待條件隊(duì)列中的所有等待進(jìn)程，但當(dāng)前執(zhí)行cnotify原語的進(jìn)程繼續(xù)執(zhí)行5.4.2使用通知和廣播的管程75有限緩沖區(qū)生產(chǎn)者/消費(fèi)者的管程解決方案Bmonitorboundedbuffer{charbuffer[N];intnextin,nextout;intcount;condnotfull,notempty;voidappend(charx){

while(count==N)cwait(notfull);buffer[nextin]=x;nextin=(nextin+1)%N;count++;

cnotify(notempty);}voidtake(charx){

while

(count==0)cwait(notempty);x=buffer[nextout];nextout=(nextout+1)%N;count--;

cnotify(notfull);}{nextin=0;nextout=0;count=0;}}voidproducer(){charx;while(true){produce(x);append(x);}}voidcomsumer(){charx;while(true){take(x);comsume(x);}}voidmain(){parbegin(producer,consumer);}765.5消息傳遞進(jìn)程交互的兩個(gè)基本要求同步：互斥進(jìn)程間需同步。同步指對(duì)進(jìn)程執(zhí)行時(shí)序的約束，包括互斥和時(shí)序的先后限制通信：合作進(jìn)程間交換信息消息傳遞進(jìn)程通信的一種常用方法適用范圍廣，可用于多核、SMP和分布式系統(tǒng)由原語對(duì)“send（發(fā)送）和receive（接收）”提供主要功能：send(目的,信息)receive(源,信息)實(shí)現(xiàn)形式有多種775.5.1消息傳遞的同步消息傳遞自然地隱含了同步只有當(dāng)一個(gè)進(jìn)程發(fā)送消息之后，接收者才能收到消息調(diào)用send原語的兩種可能結(jié)果發(fā)送者進(jìn)程被阻塞，直到這個(gè)消息被接收發(fā)送者進(jìn)程不被阻塞調(diào)用receive原語的兩種可能結(jié)果接收者進(jìn)程接收消息時(shí)，消息已發(fā)出，接收者不阻塞接收者進(jìn)程接收消息時(shí)，消息未發(fā)出，接收者被阻塞，直到發(fā)送者進(jìn)程發(fā)出此消息78三種組合方式消息傳遞實(shí)現(xiàn)的三種常用組合方式“阻塞send，阻塞receive”方式，即“會(huì)合”原則，適用于進(jìn)程間的緊密同步（如打電話）“無阻塞send，阻塞receive”方式，最有用的組合（如收發(fā)短信）“無阻塞send，無阻塞receive”方式，不要求任何一方等待。危險(xiǎn)：信息可能會(huì)丟失（如貼/看小廣告）“無阻塞send”是最自然的選擇。但錯(cuò)誤可能會(huì)導(dǎo)致進(jìn)程重復(fù)傳遞消息，消耗系統(tǒng)資源。且必須使用應(yīng)答消息以證實(shí)收到消息“阻塞receive”是常用的選擇。但若消息丟失或發(fā)送者進(jìn)程失效，會(huì)導(dǎo)致接收者進(jìn)程被長(zhǎng)期阻塞795.5.2消息傳遞的尋址send原語中指明接收者是必要的receive原語有時(shí)也指明發(fā)送者直接尋址方案發(fā)送者在發(fā)送時(shí)給出了接收者進(jìn)程的具體標(biāo)識(shí)號(hào)，如進(jìn)程ID間接尋址方案發(fā)送者將消息發(fā)送到共享的信箱中臨時(shí)保管，接收者從信箱中獲得這些消息耦合方式：“一對(duì)一”、“多對(duì)一”、“一對(duì)多”或“多對(duì)多”進(jìn)程與信箱的關(guān)聯(lián)：靜態(tài)方式（端口）和動(dòng)態(tài)方式（使用連接原語connect和disconnect）805.5.3消息格式取決于運(yùn)行環(huán)境單機(jī)系統(tǒng)分布式系統(tǒng)兩類格式定長(zhǎng)格式變長(zhǎng)格式消息格式消息頭——消息類型、目標(biāo)ID、源ID、消息長(zhǎng)度、控制信息消息體——消息內(nèi)容消息類型消息內(nèi)容目標(biāo)ID源ID消息長(zhǎng)度控制信息消息頭消息體5.5.4排隊(duì)原則先進(jìn)先出（FIFO）原則優(yōu)先級(jí)原則81用于進(jìn)程間通信和同步的消息系統(tǒng)設(shè)計(jì)同步send——阻塞、無阻塞receive——阻塞、無阻塞、測(cè)試是否到達(dá)尋址直接sendreseive——顯式、隱式間接靜態(tài)動(dòng)態(tài)所有權(quán)格式內(nèi)容長(zhǎng)度——固定、可變排隊(duì)規(guī)則FIFO優(yōu)先級(jí)825.5.5消息傳遞實(shí)現(xiàn)互斥使用“無阻塞send，阻塞receive”組合一組進(jìn)程共享一個(gè)信箱box，信箱被初始化為一條無內(nèi)容的空消息（代表進(jìn)入臨界區(qū)的鑰匙）每個(gè)進(jìn)程在進(jìn)入臨界區(qū)前，首先嘗試接收消息，離開臨界區(qū)時(shí)將接收到的消息放回信箱每次只有接收到消息的那個(gè)進(jìn)程才可以進(jìn)入臨界區(qū)（互斥）消息函數(shù)似在進(jìn)程間傳遞一個(gè)可使用臨界區(qū)的令牌/*programmutualexclusion*/constintn=/*進(jìn)程數(shù)*/;voidP(inti){/*進(jìn)程i*/messagemsg;while(true){receive(box,msg);/*信箱空時(shí)被阻塞*//*臨界區(qū)*/;send(box,msg);/*其余部分*/;}}voidmain(){create_mailbox(box);send(box,null);parbegin(P(1),…,P(n));}83消息傳遞實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者問題/*互斥程序*/constintcapacity=N;/*緩沖區(qū)容量*/;messagenull=/*空消息*/;voidproducer(){

messagepmsg;

while(true){receive(mayproduce,pmsg);pmsg=produce();send(maycomsume,pmsg);}}voidcomsumer(){

messagecmsg;

while(true){receive(mayconsume,cmsg);consume(cmsg);send(mayproduce,null);}}voidmain(){create_mailbox(mayproduce);create_mailbox(mayconsume);for(inti=1;i<capacity;i++)send(mayproduce,null);

parbegin(producer(),consumer());}/*初始時(shí)：mayconsume信箱為空，mayproduce信箱則被N個(gè)null信號(hào)填充*/845.6讀者-寫者問題同步與并發(fā)機(jī)制設(shè)計(jì)的著名問題問題描述有一個(gè)多個(gè)進(jìn)程共享的數(shù)據(jù)區(qū)，有一些只讀取這個(gè)數(shù)據(jù)區(qū)的進(jìn)程(reader)和一些只往數(shù)據(jù)區(qū)中寫數(shù)據(jù)的進(jìn)程(writer)必須滿足下列條件：任意多的讀進(jìn)程可以同時(shí)讀這個(gè)數(shù)據(jù)區(qū)一次只有一個(gè)寫進(jìn)程可以往數(shù)據(jù)區(qū)寫如果一個(gè)寫進(jìn)程正在往數(shù)據(jù)區(qū)中寫，禁止任何讀進(jìn)程讀數(shù)據(jù)區(qū)5.6.1讀者優(yōu)先信號(hào)量方案voidwriter(){while(true){P(wsem);WRITEUNIT();V(wsem);}}voidmain(){readcount=0;parbegin(reader(),writer());}信號(hào)量wsem用于互斥信號(hào)量x用于保證readcount被正確更新色塊為臨界區(qū)寫進(jìn)程可能處于饑餓狀態(tài)85/*programreader_and_writer*/intreadcount;semaphorex=1,wsem=1;voidreader(){while(true){P(x);readcount++;if(readcount==1)P(wsem);V(x);READUNIT();P(x);readcount--;

if(readcount==0)V(wsem);V(x);}只有第一個(gè)進(jìn)入數(shù)據(jù)區(qū)的讀者進(jìn)程才P}

信號(hào)量wsem；只有最后一個(gè)離開數(shù)據(jù)區(qū)的讀者進(jìn)程才V信號(hào)量wsem/*programreader_and_writer*/intreadcount,writecount;semaphorex=1,y=1,z=1,rsem=1,wsem=1;voidreader(){while(true){P(z);P(rsem); P(x);readcount++;if(readcount==1)P(wsem);V(x); V(rsem);V(z); READUNIT();P(x);readcount--;if(readcount==0)V(wsem);V(x);}}voidwriter(){while(true){P(y);writecount++;if(writecount==1)P(rsem);V(y);P(wsem);WRITEUNIT();V(wsem);P(y);writecount--;if(writecount==0)V(rsem);V(y);}}voidmain(){readcount=writecount=0;parbegin(reader(),writer());}為保證寫者進(jìn)程優(yōu)先進(jìn)入，只允許一個(gè)讀者進(jìn)程在rsem上排隊(duì)，信號(hào)量z用于其余讀者進(jìn)程排隊(duì)865.6.2寫者優(yōu)先信號(hào)量方案信號(hào)量rsem用于在寫數(shù)據(jù)區(qū)時(shí)禁止讀者進(jìn)程進(jìn)入信號(hào)量y則用于保證writecount更新的正確性基于消息傳遞的寫者優(yōu)先方案voidreader(inti){messagermsg;while(true){rmsg.id=i;send(readrequest,rmsg);receive(mbox[i],rmsg);READUNIT();rmsg.id=i;send(finished,rmsg);}}voidwriter(intj){messagewmsg;while(true){wmsg.id=j;send(writerequest,wmsg);receive(mbox[j],wmsg);