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

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

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

一個(gè)程序片段的集合，我們把在每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段代碼稱為臨界區(qū)。1.5進(jìn)程的同步（直接作用） 指系統(tǒng)中一些進(jìn)程需要相互合作，共同完成一項(xiàng)任務(wù)。具體說(shuō)，一個(gè)進(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ìng)爭(zhēng)使用這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥。2.進(jìn)程的互斥2.1臨界區(qū)的使用原則1）空閑讓進(jìn)：當(dāng)無(wú)進(jìn)程在臨界區(qū)時(shí)，任何有權(quán)使用臨界區(qū)的進(jìn)程可進(jìn)入。2）忙則等待：不允許兩個(gè)以上的進(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解決互斥問(wèn)題的方法有兩個(gè)進(jìn)程Pi,Pj，其中的Pi軟件方法：算法1：?jiǎn)螛?biāo)志while(turn!=i);criticalsectionturn=j;remaindersection設(shè)立一個(gè)公用整型變量turn：描述允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)識(shí)在進(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)識(shí)：進(jìn)程Pi退出時(shí)，改turn為進(jìn)程Pj的標(biāo)識(shí)j；缺點(diǎn)：強(qiáng)制輪流進(jìn)入臨界區(qū)，沒(méi)有考慮進(jìn)程的實(shí)際需要。容易造成資源利用不充分：在Pi出讓臨界區(qū)之后，Pj使用臨界區(qū)之前，Pi不可能再次使用臨界區(qū)；算法2：雙標(biāo)志、先檢查設(shè)立一個(gè)標(biāo)志數(shù)組flag[]：描述進(jìn)程是否在臨界區(qū)，初值均為FALSE。先檢查，后修改：在進(jìn)入?yún)^(qū)檢查另一個(gè)進(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í)，會(huì)同時(shí)進(jìn)入：“Pi<a>;Pj<a>;Pi<b>;Pj<b>”。即在檢查對(duì)方flag之后和切換自己flag之前有一段時(shí)間，結(jié)果都檢查通過(guò)。這里的問(wèn)題出在檢查和修改操作不能連續(xù)進(jìn)行。算法3：雙標(biāo)志、后檢查類似于算法2，與互斥算法2的區(qū)別在于先修改后檢查?？煞乐箖蓚€(gè)進(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í)，會(huì)都進(jìn)不了臨界區(qū)："Pi<a>Pj<a>Pi<b>Pj<b>"。即在切換自己flag之后和檢查對(duì)方flag之前有一段時(shí)間，結(jié)果都切換flag，都檢查不通過(guò)。

算法4(Peterson’sAlgorithm)：

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

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

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

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

{

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

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

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

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

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

BEGIN

語(yǔ)句序列；

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

BEGIN

語(yǔ)句序列；

END;......BEGIN

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

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

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

發(fā)送原語(yǔ)