第三章進(jìn)程的同步和通信

第三章進(jìn)程的同步與通信1.3臨界資源（criticalresource）

系統(tǒng)中某些資源一次只允許一個進(jìn)程使用，稱這樣的資源為臨界資源或互斥資源或共享變量。如磁帶機(jī)，打印機(jī)等。1.4臨界區(qū)(criticalsection)

一個程序片段的集合，我們把在每個進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)。1.5進(jìn)程的同步（直接作用） 指系統(tǒng)中一些進(jìn)程需要相互合作，共同完成一項(xiàng)任務(wù)。具體說，一個進(jìn)程運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài)。1.6進(jìn)程的互斥（間接作用） 由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競爭使用這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥。2.進(jìn)程的互斥2.1臨界區(qū)的使用原則1）空閑讓進(jìn)：當(dāng)無進(jìn)程在臨界區(qū)時(shí)，任何有權(quán)使用臨界區(qū)的進(jìn)程可進(jìn)入。2）忙則等待：不允許兩個以上的進(jìn)程同時(shí)進(jìn)入臨界區(qū)。3）有限等待：任何進(jìn)入互斥區(qū)的要求應(yīng)在有限的時(shí)間內(nèi)得到滿足，以免陷入“死等”。4）讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)入“忙等”。2.2解決互斥問題的方法有兩個進(jìn)程Pi,Pj，其中的Pi軟件方法：算法1：單標(biāo)志while(turn!=i);criticalsectionturn=j;remaindersection設(shè)立一個公用整型變量turn：描述允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)識在進(jìn)入?yún)^(qū)循環(huán)檢查是否允許本進(jìn)程進(jìn)入：turn為i時(shí)，進(jìn)程Pi可進(jìn)入；在退出區(qū)修改允許進(jìn)入進(jìn)程標(biāo)識：進(jìn)程Pi退出時(shí)，改turn為進(jìn)程Pj的標(biāo)識j；缺點(diǎn)：強(qiáng)制輪流進(jìn)入臨界區(qū)，沒有考慮進(jìn)程的實(shí)際需要。容易造成資源利用不充分：在Pi出讓臨界區(qū)之后，Pj使用臨界區(qū)之前，Pi不可能再次使用臨界區(qū)；算法2：雙標(biāo)志、先檢查設(shè)立一個標(biāo)志數(shù)組flag[]：描述進(jìn)程是否在臨界區(qū)，初值均為FALSE。先檢查，后修改：在進(jìn)入?yún)^(qū)檢查另一個進(jìn)程是否在臨界區(qū)，不在時(shí)修改本進(jìn)程在臨界區(qū)的標(biāo)志；在退出區(qū)修改本進(jìn)程在臨界區(qū)的標(biāo)志；while(flag[j]);<a>flag[i]=TRUE;<b>criticalsectionflag[i]=FALSE;remaindersectionPi:優(yōu)點(diǎn)：不用交替進(jìn)入，可連續(xù)使用；缺點(diǎn)：Pi和Pj可能同時(shí)進(jìn)入臨界區(qū)。在Pi和Pj都不在臨界區(qū)時(shí)，假設(shè)按下面序列執(zhí)行時(shí)，會同時(shí)進(jìn)入：“Pi<a>;Pj<a>;Pi<b>;Pj<b>”。即在檢查對方flag之后和切換自己flag之前有一段時(shí)間，結(jié)果都檢查通過。這里的問題出在檢查和修改操作不能連續(xù)進(jìn)行。算法3：雙標(biāo)志、后檢查類似于算法2，與互斥算法2的區(qū)別在于先修改后檢查?？煞乐箖蓚€進(jìn)程同時(shí)進(jìn)入臨界區(qū)。flag[i]=TRUE;<a>while(flag[j]);<b>criticalsectionflag[i]=FALSE;remaindersection缺點(diǎn)：Pi和Pj可能都進(jìn)入不了臨界區(qū)。在Pi和Pj都不在臨界區(qū)時(shí)，假設(shè)按下面序列執(zhí)行時(shí)，會都進(jìn)不了臨界區(qū)："Pi<a>Pj<a>Pi<b>Pj<b>"。即在切換自己flag之后和檢查對方flag之前有一段時(shí)間，結(jié)果都切換flag，都檢查不通過。

算法4(Peterson’sAlgorithm)：

先修改、后檢查、后修改者等待結(jié)合算法1和算法3，是正確的算法turn=j;描述可進(jìn)入的進(jìn)程（同時(shí)修改標(biāo)志時(shí)）在進(jìn)入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后：檢查對方flag，如果不在臨界區(qū)則自己進(jìn)入－－空閑則入否則再檢查turn：保存的是較晚的一次賦值，則較晚的進(jìn)程等待，較早的進(jìn)程進(jìn)入－－先到先入，后到等待flag[i]=TRUE;turn=j;while(flag[j]&&turn==j);criticalsectionflag[i]=FALSE;remaindersection??分析算法4，能否出現(xiàn)算法3和算法2中的問題硬件方法完全利用軟件方法，有很大局限性（如不適于多進(jìn)程），現(xiàn)在已很少采用?？梢岳媚承┯布噶睿渥x寫操作由一條指令完成，因而保證讀操作與寫操作不被打斷；Test-and-Set指令該指令讀出標(biāo)志后設(shè)置為TRUE：booleanTS(boolean*lock){booleanold;old=*lock;*lock=TRUE;returnold;}lock表示資源的兩種狀態(tài)：TRUE表示正被占用，F(xiàn)ALSE表示空閑Test-and-Set指令,可保證在一個指令周期內(nèi)對一個存儲單元的讀和寫，其功能如右：互斥算法（TS指令）利用TS實(shí)現(xiàn)進(jìn)程互斥：每個臨界資源設(shè)置一個公共布爾變量lock，初值為FALSE在進(jìn)入?yún)^(qū)利用TS進(jìn)行檢查：有進(jìn)程在臨界區(qū)時(shí)，重復(fù)檢查；直到其它進(jìn)程退出時(shí)，檢查通過；相當(dāng)于測試并加鎖相當(dāng)于解鎖測試并加鎖：lock(int*lock){whileTS(&lock);}解鎖：unlock(int*lock){*lock=FALSE;}Swap指令（或Exchange指令）交換兩個字（字節(jié)）的內(nèi)容voidSWAP(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}Swap指令（或Exchange指令）,可保證在一個指令周期內(nèi)交換一個寄存器和一個存儲單元內(nèi)容，其工作原理如下：互斥算法（Swap指令）利用Swap實(shí)現(xiàn)進(jìn)程互斥：每個臨界資源設(shè)置一個公共布爾變量lock，初值為FALSE。每個進(jìn)程設(shè)置一個私有布爾變量keykey=TRUE;do{SWAP(&lock,&key);}while(key);lock=FALSE;criticalsectionremaindersection進(jìn)入臨界區(qū)前執(zhí)行：執(zhí)行“關(guān)中斷”指令離開臨界區(qū)后執(zhí)行：執(zhí)行“開中斷”指令互斥算法（開關(guān)中斷”指令）特點(diǎn)：代價(jià)高，CPU只能交替執(zhí)行不能用于多處理機(jī)結(jié)構(gòu)，因?yàn)殛P(guān)中斷只能屏蔽本機(jī)的中斷硬件方法的優(yōu)點(diǎn)[WS]適用于任意數(shù)目的進(jìn)程，在單處理器或多處理器上（除中斷方法）簡單，容易驗(yàn)證其正確性可以支持進(jìn)程內(nèi)存在多個臨界區(qū)，只需為每個臨界區(qū)設(shè)立一個布爾變量硬件方法的缺點(diǎn)[WS]等待要耗費(fèi)CPU時(shí)間，不能實(shí)現(xiàn)"讓權(quán)等待"可能“饑餓”（不公平）：從等待進(jìn)程中隨機(jī)選擇一個進(jìn)入臨界區(qū)，有的進(jìn)程可能一直選不上可能死鎖：進(jìn)程P1執(zhí)行TS或Exchange指令并進(jìn)入臨界區(qū)，然后P1被P2中斷并把CPU給具有更高優(yōu)先級的P2,若P2試圖使用與P1相同的資源，由于互斥機(jī)制，它被拒絕訪問，因此進(jìn)入忙等待循環(huán)，又因P2優(yōu)先級高于P1，所以P1總得不到調(diào)度執(zhí)行。3.信號量機(jī)制3.1信號量簡介1965年，由荷蘭學(xué)者Dijkstra提出（所以P、V分別是荷蘭語的test(proberen)和increment(verhogen)），是一種卓有成效的進(jìn)程同步機(jī)制。P原語--P(s)或wait(s){--s.count; //表示申請一個資源;if(s.count<0) //表示沒有空閑資源;{

調(diào)用進(jìn)程進(jìn)入等待隊(duì)列s.queue;

阻塞調(diào)用進(jìn)程;}}P(Semaphores)在互斥問題中，申請使用臨界資源時(shí)調(diào)用它V原語—V(s)或signal(s){++s.count; //表示釋放一個資源；

if(s.count<=0)//表示有進(jìn)程處于阻塞狀態(tài)；

{

從等待隊(duì)列s.queue中取出一個進(jìn)程P;

進(jìn)程P進(jìn)入就緒隊(duì)列;}}V原語通常喚醒進(jìn)程等待隊(duì)列中的頭一個進(jìn)程V(Semaphores)功能：釋放資源，或喚醒進(jìn)程使用時(shí)機(jī)：進(jìn)程退出臨界區(qū)之后P.V操作討論1)信號量的物理含義：S>0表示有S個資源可用S=0表示無資源可用S<0則|S|表示S等待隊(duì)列中的進(jìn)程個數(shù)P(S):表示申請一個資源V(S)表示釋放一個資源。信號量的初值應(yīng)該大于等于03.2利用信號量實(shí)現(xiàn)互斥為臨界資源設(shè)置一個互斥信號量mutex(MUTualExclusion)，其初值為1；在每個進(jìn)程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間必須成對使用P和V原語：遺漏P原語則不能保證互斥訪問，遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進(jìn)程）；P、V原語不能次序錯誤、重復(fù)或遺漏V(mutex);criticalsectionremaindersectionP(mutex);4.進(jìn)程的同步機(jī)制──管程4.1管程的提出采用PV同步機(jī)制來編寫并發(fā)程序，對于共享變量及信號量變量的操作將被分散于各個進(jìn)程中缺點(diǎn)：（１）易讀性差，因?yàn)橐私鈱τ谝唤M共享變量及信號量的操作是否正確，則必須通讀整個系統(tǒng)或者并發(fā)程序（２）不利于修改和維護(hù)，因?yàn)槌绦虻木植啃院懿睿匀我唤M變量或一段代碼的修改都可能影響全局（３）正確性難以保證，因?yàn)椴僮飨到y(tǒng)或并發(fā)程序通常很大，要保證這樣一個復(fù)雜的系統(tǒng)沒有邏輯錯誤是很難的管程：一種同步機(jī)制

(管程-類程-進(jìn)程)4.2管程定義:指關(guān)于共享資源的數(shù)據(jù)及在其上操作的一組過程或共享數(shù)據(jù)結(jié)構(gòu)及其規(guī)定的所有操作

系統(tǒng)按資源管理的觀點(diǎn)分解成若干模塊，用數(shù)據(jù)表示抽象系統(tǒng)資源，同時(shí)分析了共享資源和專用資源在管理上的差別，按不同的管理方式定義模塊的類型和結(jié)構(gòu)，使同步操作相對集中，從而增加了模塊的相對獨(dú)立性

管程：集中式同步機(jī)制，它的基本思想是將共享變量以及對共享變量能夠進(jìn)行的所有操作集中在一個模塊中，一個操作系統(tǒng)或并發(fā)程序由若干個這樣的模塊所構(gòu)成，由于一個模塊通常較短，模塊之間關(guān)系清晰，提高了可讀性，便于修改和維護(hù)，正確性易于保證管程的形式TYPEmonitor_name=MONITOR;共享變量說明define本管程內(nèi)所定義、本管程外可調(diào)用的過程（函數(shù)）名字表use本管程外所定義、本管程內(nèi)將調(diào)用的過程（函數(shù)）名字表PROCEDURE過程名（形參表）； 過程局部變量說明；

BEGIN

語句序列；

END;......FUNCTION函數(shù)名（形參表）：值類型； 函數(shù)局部變量說明；

BEGIN

語句序列；

END;......BEGIN

共享變量初始化語句序列；END;5.高級通信方式一、共享存儲器系統(tǒng)（Shared-memorysystem）

相互通信的進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲區(qū)。一組進(jìn)程向該公共區(qū)中寫，另一組進(jìn)程從公共區(qū)中讀，通過這種方式實(shí)現(xiàn)兩組進(jìn)程間的信息交換。因此又分為：基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式：進(jìn)程之間能夠通過某種類型的數(shù)據(jù)結(jié)構(gòu)（如有界緩沖區(qū)）交換信息，如生產(chǎn)者和消費(fèi)者問題。操作系統(tǒng)只負(fù)責(zé)提供共享存儲區(qū)，而共享數(shù)據(jù)結(jié)構(gòu)和對進(jìn)程間的同步處理都是程序員的事。因而，通信效率低，只適合于傳遞少量信息。一、共享存儲器系統(tǒng)（續(xù)）2.基于共享存儲區(qū)的通信方式：系統(tǒng)在存儲中劃出一塊共享存儲區(qū)，各進(jìn)程間可通過對共享存儲區(qū)中的數(shù)據(jù)進(jìn)行讀或?qū)憗韺?shí)現(xiàn)通信。進(jìn)程在通信之前應(yīng)向系統(tǒng)申請共享存儲區(qū)中的一個分區(qū)，并指定該分區(qū)的關(guān)鍵字，若系統(tǒng)已經(jīng)給其他進(jìn)程分配了這樣的分區(qū)，則將該分區(qū)的描述符返回給申請者.接著，申請者把獲得的共享存儲區(qū)連接到本進(jìn)程上，此后就像讀寫普通存儲器一樣。主要用于UNIXSystemV中。二、消息系統(tǒng)（MessageSystem）直接通信方式：發(fā)送進(jìn)程發(fā)消息時(shí)要指定接收進(jìn)程的名字，反過來，接收時(shí)要指明發(fā)送進(jìn)程的名字。系統(tǒng)提綱兩條原語：

Send(receiver,message)Receiver(sender,message進(jìn)程間的信息交換以消息或報(bào)文為單位，程序員利用系統(tǒng)提供的一組通信命令（原語）實(shí)現(xiàn)通信。操作系統(tǒng)隱藏了通信的實(shí)現(xiàn)細(xì)節(jié)，簡化了編程的復(fù)雜性。分為兩種：二、消息系統(tǒng)（MessageSystem）間接通信方式：收發(fā)雙方進(jìn)程通過某種中間實(shí)體，作為通信進(jìn)程間的媒介，即信箱（MailBox）。發(fā)送進(jìn)程發(fā)消息時(shí)不指定接收進(jìn)程的名字，而是指定一個中間媒介。通常收方和發(fā)方的數(shù)目可以是任意的。這種方式廣泛應(yīng)用于多機(jī)系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)中

發(fā)送原語