第三章進程的同步和通信

第三章進程的同步與通信1.3臨界資源（criticalresource）

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

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

算法4(Peterson’sAlgorithm)：

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

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

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

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

{

從等待隊列s.queue中取出一個進程P;

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

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

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

管程：集中式同步機制，它的基本思想是將共享變量以及對共享變量能夠進行的所有操作集中在一個模塊中，一個操作系統(tǒng)或并發(fā)程序由若干個這樣的模塊所構(gòu)成，由于一個模塊通常較短，模塊之間關(guān)系清晰，提高了可讀性，便于修改和維護，正確性易于保證管程的形式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）

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

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

發(fā)送原語