進程并發(fā)與互斥教學教材

3.5進程并發(fā)與互斥3.5.1互斥算法3.5.2信號量(semaphore)3.5.3同步算法3.5.4經(jīng)典的進程互斥同步問題13.5.1互斥算法3.5.1.1臨界資源3.5.1.2臨界區(qū)的訪問過程3.5.1.3同步機制應遵循的準則23.5.1.1臨界資源進程間資源訪問沖突共享變量的修改沖突（空間）操作順序沖突（時間）在多道程序環(huán)境下——各進程之間存在資源共享，進程的運行時間和空間將會受影響進程間的制約關系間接制約：進行競爭——獨占分配到的部分或全部共享資源，“互斥”直接制約：進行協(xié)作——等待來自其他進程的信息，“同步”3共享變量的修改沖突4有6種可能的操作順序，只有一種結果是正確的。6互斥：指多個進程不能同時使用同一個資源為保證系統(tǒng)正常工作，多個并發(fā)進程在對共享的硬件或軟件（如外設、共享代碼段、共享數(shù)據(jù)結構）進行訪問時（關鍵是進行寫入或修改），必須互斥地進行。——有些共享資源可以同時訪問，如只讀數(shù)據(jù)。系統(tǒng)資源中每次只允許一個進程使用，而不能由多個進程同時共享的資源稱為臨界資源。73.5.1.2臨界區(qū)的訪問過程臨界區(qū)臨界資源（CriticalResources）：一種一次只能為一個進程服務的資源。臨界區(qū)（CriticalSection）：進程中訪問臨界資源的程序。每個使用該資源的進程都要包含一個臨界區(qū)。8臨界區(qū)(criticalsection)：進程中訪問臨界資源的一段代碼。進入?yún)^(qū)(entrysection)：在進入臨界區(qū)之前，檢查可否進入臨界區(qū)的一段代碼。如果可以進入臨界區(qū)，通常設置相應“正在訪問臨界區(qū)”標志退出區(qū)(exitsection)：用于將“正在訪問臨界區(qū)”標志清除。剩余區(qū)(remaindersection)：代碼中的其余部分。9。兩個進程不能同時進入訪問同一臨界資源的臨界區(qū)，這稱為進程互斥。103.5.1.3互斥機制應遵循的準則空閑則進：當沒有進程在臨界區(qū)時，任何需要進入臨界區(qū)的進程都允許立即進入。

忙則等待：在共享同一對象的所有進程中，一次只能有一個進程進入臨界區(qū)。其它要求進入臨界區(qū)的進程只能等待。

有限等待：任何一個進程經(jīng)有限時間等待后都能進入臨界區(qū)，不允許出現(xiàn)進程“死等”的情況。讓權等待：當一個進程不能進入臨界區(qū)時要立即阻塞自己，釋放處理機讓其它進程使用，避免“忙等”。111、進程互斥的軟件方法算法:加鎖法設立一個公用整型變量key［Ｓ］：描述允許進入臨界區(qū)的標志進程在進入?yún)^(qū)循環(huán)檢查是否允許進入臨界區(qū)：key［Ｓ］為1時，進程P可進入（否則是無限等待）；加鎖（置key［Ｓ］為0)，進入臨界區(qū)；進程P退出臨界區(qū)時解鎖，在退出區(qū)修改允許進入標識key［Ｓ］為1；缺點：多個進程可能同時進入臨界區(qū)。12算法如下：ProcessP(1) ProcessP(2)Begin begin…… ……While(key［Ｓ］=0)doskip;While(key［Ｓ］=0)doskip;key［Ｓ］=0; key［Ｓ］=0;Criticalsection; Criticalsection;key［Ｓ］=1; key［Ｓ］=1;…… ……end. end.132、進程互斥的硬件方法為保證第一步和第二步執(zhí)行不可分離。有些機器在硬件中設置了“測試與設置”指令，Test-and-Set指令（TS指令）該指令讀出標志后設置為TRUEbooleanTS(boolean*lock){booleanold;old=*lock;*lock=TRUE;returnold;}lock表示資源的兩種狀態(tài)：TRUE表示正被占用，F(xiàn)ALSE表示空閑14互斥算法（TS指令）利用TS實現(xiàn)進程互斥：每個臨界資源設置一個公共布爾變量lock，初值為FALSE在進入?yún)^(qū)利用TS進行檢查：有進程在臨界區(qū)時，重復檢查；直到其它進程退出時，檢查通過；15Swap指令（或Exchange指令）交換兩個字（字節(jié)）的內(nèi)容voidSWAP(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}16互斥算法（Swap指令）利用Swap實現(xiàn)進程互斥：每個臨界資源設置一個公共布爾變量lock，初值為FALSE。每個進程設置一個私有布爾變量keykey=TRUE;do{SWAP(&lock,&key);}while(key)doskip;lock=FALSE;criticalsectionremaindersection17優(yōu)點適用于任意數(shù)目的進程，在單處理器或多處理器上更顯其優(yōu)越簡單，容易驗證其正確性可以支持進程內(nèi)存在多個臨界區(qū)，只需為每個臨界區(qū)設立一個布爾變量缺點等待要耗費CPU時間，即“忙等”，不能實現(xiàn)“讓權等待”可能產(chǎn)生“餓死”現(xiàn)象：有的進程可能永遠執(zhí)行不了18試考慮以下進程PA和PB反復使用臨界區(qū)的情況： PA A：lock(key［Ｓ］) 〈Ｓ〉unlock(key［Ｓ］) GotoA PB B：lock(key［Ｓ］) ＜Ｓ＞ unlock(key［Ｓ］) GotoB193.5.2信號量(semaphore)3.5.2.1信號量和P、V原語3.5.2.2利用信號量實現(xiàn)互斥多數(shù)互斥算法缺乏公平性，只有獲得處理機的進程才可進行進入臨界區(qū)的測試，且測試結果具有偶然性。需要一個地位高于進程的管理者來解決公有資源的使用問題。OS可從進程管理者的角度來處理互斥的問題，信號量就是OS提供的管理公有資源的有效手段。信號量代表可用資源實體的數(shù)量。203.5.2.1信號量和P、V原語為了實現(xiàn)進程的互斥和同步，操作系統(tǒng)中引進了信號量(Semaphore)的概念。信號量具有以下特性：(1)信號量是一個整形變量。

2)每一個信號量表示一種系統(tǒng)資源的狀況，其值表示該資源當前可用的數(shù)量，初值為非零。(3)每一個信號量都對應一個空或非空的等待隊列。該隊列就是信號量所代表的資源的等待隊列。

4)對信號量只能實施P、V操作，只有P、V操作原語才能改變其值。21信號量只能通過初始化和兩個標準的原語來訪問——作為OS核心代碼執(zhí)行，不受進程調(diào)度的打斷初始化資源信號量為指定一個非負整數(shù)值，表示空閑資源總數(shù)——若為非負值表示當前的空閑資源數(shù)，若為負值其絕對值表示當前等待臨界區(qū)的進程數(shù)221．P操作原語procedureP(vars:semaphore)begins:=s-1;ifs<0thenW(s);end23w(s)表示將調(diào)用P操作原語的進程置成等待信號量s的狀態(tài)。進程執(zhí)行P操作時，首先將信號量s減1，其結果若s≥o，則該進程繼續(xù)運行；若結果s<o則阻塞該進程，并把它插入到信號量s的等待隊列中。242．V操作原語ProcedureV(vars:semaphore)begins:=s+1;ifs≤0thenR(s);end25R(s)表示從信號量s的等待隊列中釋放一個進程。進程執(zhí)行V操作時，首先將信號量s加1，如果s>o，則該進程繼續(xù)執(zhí)行。如果s≤0則釋放s信號量等待隊列中隊首的進程，解除其阻塞狀態(tài)。調(diào)用V操作的當前進程繼續(xù)執(zhí)行。26P、V操作的物理意義：執(zhí)行P操作：s:=s-1意味著把s對應的一個資源分配給調(diào)用P操作的進程，資源的數(shù)量減少一個。若s減一后其值為0，表示此類資源已全部分配給各個進程了。27在此之后若又有進程請求該資源，在該進程調(diào)用P操作時，s減1后成為負值，則執(zhí)行W(s)，該進程將轉(zhuǎn)換為阻塞態(tài)并進入信號量s對應的等待隊列中。當信號量s為負值時，它的絕對值表示在該信號量等待隊列中的進程數(shù)目。28執(zhí)行V操作時：s:=s+1意味著調(diào)用V操作的進程釋放了一個信號量s對應的資源。s加一后，若s為負值，表明s對應的等待隊列中仍有等待該資源的阻塞進程，則調(diào)用R(s)釋放等待隊列中的一個進程。29被釋放的進程是在執(zhí)行P操作時因資源不足而進入阻塞態(tài)的，由于V操作釋放了它所需的資源，它就轉(zhuǎn)換為就緒態(tài)可以繼續(xù)執(zhí)行。30記錄型信號量每個信號量s除一個整數(shù)值s.count（計數(shù)）外，還有一個進程等待隊列s.queue，其中是阻塞在該信號量的各個進程的標識311.P原語wait(s)--s.count; //表示申請一個資源;if(s.count<0) //表示沒有空閑資源;{調(diào)用進程進入等待隊列s.queue;阻塞調(diào)用進程;}322.V原語signal(s)++s.count; //表示釋放一個資源；if(s.count<=0) //表示有進程處于阻塞狀態(tài)；{從等待隊列s.queue中取出一個進程P;進程P進入就緒隊列;}V原語通常喚醒進程等待隊列中的頭一個進程333.5.2.2利用信號量實現(xiàn)互斥在實現(xiàn)進程互斥時，信號量的初值設為1，表示中只允許一個進程進入臨界區(qū)。在進程執(zhí)行過程中，當進入臨界區(qū)時執(zhí)行P操作，在離開臨界區(qū)時執(zhí)行V操作，使臨界區(qū)位于對同一個信號量的P操作和V操作之間。34mutex為互斥信號量，其初值為1；在每個進程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間必須成對使用P和V原語：遺漏P原語則不能保證互斥訪問，遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進程）；P、V原語不能次序錯誤、重復或遺漏35在進程互斥中使用的信號量，每個進程都可以對它實施P操作，這樣的信號量又稱為公用信號量。36s:semaphore;s:=1;進程A進程B．．．．．．

．．．．．．

P(s);P(s);臨界區(qū)CRA;臨界區(qū)CRB;V(s);V(s);．．．．．．．．．．．．用信號量實現(xiàn)兩并發(fā)進程的互斥37s=10-101進程s:=s-1CRAs:=s+1R(s)AP(s)V(s)進程s:=s-1W(s)[阻塞等待]CRBs:=s+1BP(s)V(s)--------t1----------t2---------------t3----------------t4---->383.5.3進程同步

1、同步概念直接制約一組并發(fā)進程，各自的執(zhí)行結果互為對方的執(zhí)行條件，從而限制各進程的執(zhí)行速度的過程消息(事件）進程互相給對方進程發(fā)送執(zhí)行條件已經(jīng)具備的信號同步一組并發(fā)進程，因直接制約而互相發(fā)送消息而進行互相合作、互相等待，使得各進程按一定的速度執(zhí)行的過程稱為進程間的同步39PC （計算進程） : A: 計算 得到計算結果 Buf←計算結果 Goto APP

（打印進程） : B: 打印Buf中的數(shù)據(jù) 清除Buf中的數(shù)據(jù) Goto B40一般來說，可以把各進程之間發(fā)送的消息作為信號量看待。與進程互斥時不同的是，這里的信號量只與制約進程及被制約進程有關而不是與整組并發(fā)進程有關。因此，稱該信號量為私用信號量（PrivateSemaphvre）。412、同步的實現(xiàn)方法

利用信號量來描述前趨關系前趨關系：并發(fā)執(zhí)行的進程P1和P2中，分別有代碼C1和C2，要求C1在C2開始前完成；為每個前趨關系設置一個信號量S12，其初值為042s1,s2:semaphore;s1=1,s2=0;cobegin repeatT1; repeatT2;coend;設定兩個信號量s1和s2，s1的初值為1，s2的初值為0。如上例，有兩個進程T1和T2，要求T1和T2同步運行，則43procedureT1:procedureT2:begin begin．．． ．．． P(s1); P(s2); m1; m2;

V(s2); V(s1);．．． ．．．end; end;44只能由一個進程對其實施P操作的信號量稱為該進程的私有信號量。s1是T1的私有信號量，s2是T2的私有信號量。在兩個進程相互推進的運行過程中，哪個進程的私有信號量為1，就表示它可以向前推進。453.5.4經(jīng)典互斥同步問題生產(chǎn)者－消費者問題(theproducer-consumerproblem)問題描述：若干進程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，“生產(chǎn)者”進程不斷寫入，而“消費者”進程不斷讀出；共享緩沖區(qū)共有N個；任何時刻只能有一個進程可對共享緩沖區(qū)進行操作。46生產(chǎn)者進程不斷生產(chǎn)產(chǎn)品并把它們放入緩沖區(qū)內(nèi)，消費者進程不斷從緩沖區(qū)中取走產(chǎn)品進行消費。當緩沖區(qū)中產(chǎn)品已經(jīng)放滿時，表示生產(chǎn)速度高于消費而出現(xiàn)了供過于求。這時，生產(chǎn)者進程不能再生產(chǎn)而必須等待產(chǎn)品被消費。當緩沖區(qū)取空時，表示消費速度高于生產(chǎn)而出現(xiàn)了供不應求。這時，消費者進程不能再消費而必須等待產(chǎn)品的生產(chǎn)。生產(chǎn)和消費的進程必須達到同步運行，才能使供需平衡。47緩沖區(qū)是一個臨界資源，兩個進程訪問緩沖區(qū)必須互斥地執(zhí)行。設一個公用信號量mutex，其初值為1。設生產(chǎn)者進程的私有信號量為empty，表示緩沖區(qū)中空閑位置的數(shù)目，即可以容納產(chǎn)品的數(shù)目，初值為n。設消費者進程的私有信號量為full，表示緩沖區(qū)內(nèi)已有產(chǎn)品的數(shù)目，其初值為0。48mutex,empty,full:semaphore;mutex:=1;empty:=n;full=0;cobeginproducer:begin L1: produceaproduct; P(empty); P(mutex); Addtobuffer; V(full); V(mutex); gotoL1; end;49 consumer:begin L2: P(full); P(mutex); takeonefrombuffer; V(empty); V(mutex); consumeproduct; gotoL2; end;coend;50采用信號量機制：full是“滿”數(shù)目，初值為0，empty是“空”數(shù)目，初值為N。實際上，full和empty是同一個作用，始終有full+empty=Nmutex用于訪問緩沖區(qū)時的互斥，初值是1每個進程中各個P操作的次序是重要的：先檢查資源數(shù)目，再檢查是否互斥——否則可能死鎖(為什么？)51無論是生產(chǎn)者進程還是消費者進程，其中V操作的次序是無關緊要的，但P操作的次序不能顛倒。52讀者－寫者問題(thereaders-writersproblem)問題描述：對共享資源的讀寫操作，任一時刻“寫者”最多只允許一個，而“讀者”則允許多個“讀－寫”互斥，“寫－寫”互斥，“讀－讀”允許53采用信號量機制：mutex互斥信號量:實現(xiàn)讀者與寫者、寫者與寫者之間的互斥，初值是1。Rcount讀者共享的變量:表示“正在讀”的進程數(shù)，初值是0；Rmutex表示對Rcount的互斥操作，初值是1。P(Rmutex);if(Rcount==0)thenP(mutex);++Rcount;V(Rmutex);read;P(Rmutex);--Rcount;if(Rcount==0)thenV(mutex);V(Rmutex);ReaderP(mutex);write;V(mutex);Writer54哲學家用餐問題

在該問題中設想有5位哲學家，他們共同坐在一張餐桌前用餐，用餐過后開始思考問題。他們的生活方式可描述為一個單調(diào)的循環(huán)：思考-饑餓-用餐-再思考-。已知餐桌上擺的是面條，每個人必須左右手各拿到一把叉子才可以開始進餐。而餐桌上只有5把叉子，任兩個哲學家之間有一把，見圖所示。55第i位哲學家的行為過程可描述為下面的形式。ProcessPhilosopher(i)BeginWhile(true)BeginThinking();P(mutex[i]); //請求左叉子P(mutex[i+1]mod5); //請求右叉子Eating(); //用餐過程V(mutex[i]); //釋放左叉子V(mutex[i+1]mod5); //釋放右叉子End;End;56附：信號量集一段處理代碼需要同時獲取兩個或多個臨界資源——可能死鎖：各進程分別獲得部分臨界資源，然后等待其余的臨界資源，“各不相讓”基本思想：在一個原語中，將一段代碼同時需要的多個臨界資源，要么全部分配給它，要么一個都不分配。稱為Swait(SimultaneousWait)。在Swait時，各個信號量的次序并不重要，雖然會影響進程歸入哪個阻塞隊列，但是由于是對資源全部分配或不分配，所以總有進程獲得全部資源并在推進之后釋放資源，因此不會死鎖。信號量集用于同時需要多個資源時的信號量操作1.AND型信號量集AND型信號量集用于同時需要多種資源且每種占用一個時的信號量操作；57

Swait(S1,S2,…,Sn)

//P原語；{while(TRUE){if(S1>=1&&S2>=1&&…&&Sn>=1){ //滿足資源要求時的處理；for(i=1;i<=n;++i)--Si; //注：與wait的處理不同，這里是在確信可滿足//資源要求時，才進行減1操作；break;}else{ //某些資源不夠時的處理；調(diào)用進程進入第一個小于1信號量的等待隊列Sj.queue;阻塞調(diào)用進程;}}}58

Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //釋放占用的資源；for(eachprocessPwaitinginSi.queue)//檢查每種資源的等待隊列的所有進程；{從等待隊列Si.queue中取出進程P;if(判斷進程P是否通過Swait中的測試)//注：與signal不同，這里要進行重新判斷；{ //通過檢查（資源夠用）時的處理； 進程P進入就緒隊列;}else{ //未通過檢查（資源不夠用）時的處理； 進程P進入某等待隊列；}}}}592.一般“信號量集”一次需要N個某類臨界資源時，就要進行N次wait操作－－低效又可能死鎖基本思想：在AND型信號量集的基礎上進行擴充：進程對信號量Si的測試值為ti（用于信號量的判斷，即Si<ti，表示資源數(shù)量低于ti時，便不予分配），占用值為di（用于信號量的增減，即Si=Si-di和Si=Si+di）Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);一般信號量集用于同時需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個臨界值時的處理60一般“信號量集”的幾種特定情況：Swait(S,d,d)表示每次申請d個資源，當少于d個時，便不分配；Swait(S,1,1)表示互斥信號量；Swait(S,1,0)作為一個可控開關當S>=1時，允許多個進程進入臨界區(qū)；當S=0時，禁止任何進程進入臨界區(qū)；一般“信號量集”未必成對使用Swait和Ssignal如：一起申請，但不一起釋放；61獨木橋問題:某一條河上有一座獨木橋，有人從北向南過橋，有人自南向北過橋，由于獨木橋一次只能承載一人，所以請用信號量設計一種算法，讓南北雙方都能合理通行。公共汽車問題：在公共汽車上，售票員和司機需要合理配合才能保證運行。設售票員必須等汽車停止才能開門、上客、關門、售票；而司機必須等門關好了才能開車、行駛、到站、停車?，F(xiàn)在請你用PV原語操作來同步司機和售票員的工作。思考題62假定一個閱覽室最多可同時容納100個人閱讀，讀者進入和離開閱覽室時，都必須在閱覽室門口的一個登記表上登記。假定每次只允許一個人登記和去掉登記，設閱覽室內(nèi)有100個座位。請用P,V原語編寫讀者進程的同步算法。63附：管程(monitor)用信號量可實現(xiàn)進程間的同步，但由于信號量的控制分布在整個程序中，其正確性分析很困難。管程是管理進程間同步的機制，它保證進程互斥地訪問共享資源，并方便地阻塞和喚醒進程。管程可以函數(shù)庫的形式實現(xiàn)。相比之下，管程比信號量好控制。64信號量同步的缺點同步操作分散：信號量機制中，同步操作分散在各個進程中，使用不當就可能導致各進程死鎖（如P、V操作的次序錯誤、重復或遺漏）易讀性差：要了解對于一組共享變量及信號量的操作是否正確，必須通讀整個系統(tǒng)或者并發(fā)程序；不利于修改和維護：各模塊的獨立性差，任一組變量或一段代碼的修改都可能影響全局；正確性難以保證：操作系統(tǒng)或并發(fā)程序通常很大，很難保證這樣一個復雜的系統(tǒng)沒有邏輯錯誤；65管程的引入

這是一種具有面向?qū)ο蟪绦蛟O計思想的同步機制。它提供了與信號量機制相同的功能。管程（Monitor）概念是著名學者Hore于1974年提出的，并在很多系統(tǒng)中得到實現(xiàn)，諸如Pascal、Java、Modula-3等。管程是由局部數(shù)據(jù)結構、多個處理過程和一套初始化代碼組成的模塊。管程的特征為：

（1）管程內(nèi)的數(shù)據(jù)結構只能被管程內(nèi)的過程訪問，任何外部訪問都是不允許的；（2）進程可通過調(diào)用管程的一個過程進入管程；（3）任何時間只允許一個進程進入管程，其他要求進入管程的進程統(tǒng)統(tǒng)被阻塞到等待管程的隊列上。66下圖是管程的一個結構模型67l

P（c）：當遇到同步約束，就將進程阻塞在條件變量c關聯(lián)的等待隊列上。l

V（c）：從條件變量c關聯(lián)的等待隊列上喚醒一個進程，讓它恢復運行。若隊列上沒有進程在等待，就什么也不做。管程的語言結構可描述為下屬形式：Type管程名=MonitorBegin數(shù)據(jù)結構定義；局部變量定義；條件變量定義；

Porcedure

過程名（形式參數(shù)）

Begin

……… //過程體

End;

………

End;68模塊化：一個管程是一個基本程序單位，可以單獨編譯復合數(shù)據(jù)類型：管程是一種特殊的數(shù)據(jù)類型，其中不僅有數(shù)據(jù)，而且有對數(shù)據(jù)進行操作的代碼信息封裝：管程是半透明的，管程中的外部過程（函數(shù)）實現(xiàn)了某些功能，至于這些功能是怎樣實現(xiàn)的，在其外部則是不可見的管程的主要特性69管程中的共享變量在管程外部是不可見的，外部只能通過調(diào)用管程中所說明的外部過程（函數(shù)）來間接地訪問管程中的共享變量為了保證管程共享變量的數(shù)據(jù)完整性，規(guī)定管程互斥進入管程通常是用來管理資源的，因而在管程中應當設有進程等待隊列以及相應的等待及喚醒操作管程的實現(xiàn)要素70TypePC=MonitorBeginVarChar:buffer[N];VarInteger:counter,in,out;VarCondition:notfull,notempty;

PorcedurePUT（varchar:item）Begin ifcount=NthenP(notfull); Buffer[in]:=item; in:=(in+1)modN; Count:=count+1; V(notempty);End;PorcedureGET（char:item）Begin ifcount=0thenP(notempty); item:=Buffer[out]; out:=(out+1)modN; Count:=count-1; V(notfull);End;Begincount,in,out=0,0,0;End;End;利用管程PC解決生產(chǎn)者-消費者問題71ProcedureConsumer()BeginVarchar:x;While(true)BeginGET(x);Consume_the_item_in_x();EndEnd;應用程序算法如下。ProcedureProducer()BeginVarchar:x;While(true)BeginProduce_an_item_in_x();PUT(x);End;End;72管程的優(yōu)點管程可增強模塊的獨立性：系統(tǒng)按資源管理的觀點分解成若干模塊，用數(shù)據(jù)表示抽象系統(tǒng)資源，同時分析了共享資源和專用資源在管理上的差別，按不同的管理方式定義模塊的類型和結構，使同步操作相對集中，從而增加了模塊的相對獨立性引入管程可提高代碼的可讀性，便于修改和維護，正確性易于保證：采用集中式同步機制。一個操作系統(tǒng)或并發(fā)程序由若干個這樣的模塊所構成，一個模塊通常較短，模塊之間關系清晰。733.6進程間通信

(IPC,INTER-PROCESSCOMMUNICATION)3.6.1進程間通信的類型3.6.2共享存儲器系統(tǒng)3.6.3管道(pipe)3.6.4消息傳遞741.低級通信和高級通信低級通信：只能傳遞狀態(tài)和整數(shù)值（控制信息），包括進程互斥和同步所采用的信號量。優(yōu)點：速度快。缺點：傳送信息量小。效率低，每次通信傳遞的信息量固定，若傳遞較多信息則需要進行多次通信。主要用于控制進程執(zhí)行速度的作用。用戶直接實現(xiàn)通信的細節(jié)，編程復雜，容易出錯。高級通信：能夠傳送任意數(shù)量的數(shù)據(jù)，目的主要是用于交換信息。

3.6.1進程間通信的類型752.進程的通信方式共享存儲區(qū)方式不要求數(shù)據(jù)移動，可以任意讀寫和使用任意數(shù)據(jù)結構，需要進程互斥和同步的輔助來確保數(shù)據(jù)一致性管道方式消息或郵箱機制消息的發(fā)送不需要接收方準備好，隨時可發(fā)送763.6.2共享存儲器系統(tǒng)

這種通信需要在內(nèi)存中開辟一個共享的存儲空間，供進程之間進行數(shù)據(jù)傳遞。比如計算進程將所得的結果送入內(nèi)存共享區(qū)的緩沖區(qū)環(huán)中，打印進程從中將結果取出來，就是一個利用共享存儲器進行通信的例子。這種通信方式在UNIX、Linux、Windows及OS/2等系統(tǒng)中都有具體的實現(xiàn)。共享存儲器系統(tǒng)中，共享的空間一般應當是需要互斥訪問的臨界資源。諸多進程為了避免丟失數(shù)據(jù)或重復取數(shù)，需要執(zhí)行特定的同步協(xié)議。

在利用共享存儲器進行通信之前，信息的發(fā)送者和接收者都要將共享空間納入到自己的虛地址空間中，讓它們都能訪問該區(qū)域。存儲器管理模塊將共享空間映射成實際的內(nèi)存空間。77（1）創(chuàng)建或刪除共享存儲區(qū)（2）共享存儲區(qū)的附接與斷接（3）共享存儲區(qū)狀態(tài)查詢（4）共享存儲區(qū)管理

共享存儲器系統(tǒng)的特點：

利用共享存儲器系統(tǒng)進行通信的效率特別高，適用于通信速度要求特別高的場合。

這種同步與互斥機制的實現(xiàn)一般要由程序員來承擔，系統(tǒng)僅僅提供一個共享內(nèi)存空間的管理機制。

78Linux的共享存儲區(qū)創(chuàng)建或打開共享存儲區(qū)(shmget)：依據(jù)用戶給出的整數(shù)值key，創(chuàng)建新區(qū)或打開現(xiàn)有區(qū)，返回一個共享存儲區(qū)ID。連接共享存儲區(qū)(shmat)：連接共享存儲區(qū)到本進程的地址空間，可以指定虛擬地址或由系統(tǒng)分配，返回共享存儲區(qū)首地址。父進程已連接的共享存儲區(qū)可被fork創(chuàng)建的子進程繼承。拆除共享存儲區(qū)連接(shmdt)：拆除共享存儲區(qū)與本進程地址空間的連接。共享存儲區(qū)控制(shmctl)：對共享存儲區(qū)進行控制。如：共享存儲區(qū)的刪除需要顯式調(diào)用shmctl(shmid,IPC_RMID,0)；793.6.3管道通信

管道（Pipe）是可供進程共享的一種外存文件，主要用于連接一個寫入進程和一個讀出進程，以實現(xiàn)它們之間的數(shù)據(jù)通信。寫入進程按字符流的形式將數(shù)據(jù)寫入管道文件中，讓讀出進程從中獲得數(shù)據(jù)。由于管道機制特別適用于大容量數(shù)據(jù)的通信，因此在許多操作系統(tǒng)中被采用。管道通信機制分為無名管道和有名管道80進程通信實例——管道(pipe)

UNIX最早的消息傳遞機制是管道，管道是一條在進程間以字節(jié)流方式傳送的通信通道。管道邏輯是被看作是管道文件，物理上則是由文件系統(tǒng)的高級緩沖區(qū)（通常幾十KB）來實現(xiàn)，是單向的。在使用管道前要建立相應的管道，然后才可使用。利用UNIX提供的系統(tǒng)調(diào)用pipe，可建立一條同步通信管道。其格式為： pipe(fd) intfd［2］；這里，fd［1］為寫入端，fd［0］為讀出端。81示例例：用C語言編寫一個程序，建立一個pipe，同時父進程生成一個子進程，子進程向pipe中寫入一字符串，父進程從pipe中讀出該字符串。解：程序如下： #include〈stdio.h〉 main() { intx，fd［2］； charbuf［30］，s［30］； pipe(fd)；/*創(chuàng)建管道*/ while((x=fork())==-1)；/*創(chuàng)建子進程失敗時，循環(huán)*/ if(x==0)82 { sprintf(buf，″Thisisanexample＼n″)； write(fd［1］，buf，30)；/*把buf中字符寫入管道*/ exit(0)； } else/*父進程返回*/ { wait(0)； read(fd［0］，s，30)；/*父進程讀管道中字符*/ printf(″%s″，s)； } }831.Linux管道通過pipe系統(tǒng)調(diào)用創(chuàng)建無名管道，得到兩個文件描述符，分別用于寫和讀。intpipe(intfildes[2]);文件描述符fildes[0]為讀端，fildes[1]為寫端；通過系統(tǒng)調(diào)用write和read進行管道的寫和讀；進程間雙向通信，通常需要兩個管道；只適用于父子進程之間或父進程安排的各個子進程之間；Linux中的命名管道，可通過mknod系統(tǒng)調(diào)用建立：指定mode為S_IFIFOintmknod(constchar*path,mode_tmode,dev_tdev);842.WindowsNT管道無名管道：類似于Linux管道，CreatePipe可創(chuàng)建無名管道，得到兩個讀寫句柄；利用ReadFile和WriteFile可進行無名管道的讀寫；BOOLCreatePipe(PHANDLEhReadPipe, //addressofvariableforreadhandle PHANDLEhWritePipe, //addressofvariableforwritehandle LPSECURITY_ATTRIBUTESlpPipeAttributes, //pointertosecurityattributes DWORDnSize //numberofbytesreservedforpipe);85

系統(tǒng)中的進程在交互傳送數(shù)據(jù)時，涉及到對數(shù)據(jù)結構的互斥使用問題。為實施互斥，進程之間需要同步。提供這些功能的一個好方法是消息傳遞。還有一個優(yōu)點是，消息傳遞可較容易地在單處理機系統(tǒng)、分布式系統(tǒng)、共享存儲器的多處理機系統(tǒng)中實現(xiàn)。

消息傳遞中的管理機制由操作系統(tǒng)提供，主要體現(xiàn)為以下兩個原語。發(fā)送原語：send(destination,message)，其中，destination為消息的目的地（接收進程名）。該原語表示發(fā)送消息到進程destination。接收原語：receive(source,message)，其中，source是消息發(fā)出地（發(fā)送進程名）。該原語表示從進程source接收消息。3.6.4消息傳遞86

在這種方式中要解決的關鍵問題仍然是同步問題：僅當一條消息從某個進程發(fā)送后，其他進程才可能接收到消息。那么，消息發(fā)送者通過send原語發(fā)出一條消息后，應當如何處理呢？有兩種選擇：要么將發(fā)送進程阻塞起來，直到消息被接收為止，再把它喚醒；要么不阻塞發(fā)送進程。同樣地，消息接收者通過receive原語要接收一條消息時，如果能立即收到，可繼續(xù)運行。如果消息尚未發(fā)出的話，也有兩種選擇：要么阻塞進程等待消息；要么不阻塞進程，放棄接收。

這樣一來，系統(tǒng)可選擇的處理有以下幾種：

會合（renezvous）方式

寬松同步方式

不阻塞發(fā)送者，只阻塞接收者方式一、實現(xiàn)同步的方法

87

在消息傳遞中，發(fā)送者需要明確消息發(fā)往哪里，接收者需要指明消息的來源。通常，按send和receive原語的實現(xiàn)方式可分為直接尋址和間接尋址兩類。1.直接尋址（DirectAddressing）

實現(xiàn)直接尋址的一個較為簡單的方案是，讓send原語明確指出接收者的進程號，receive原語明確指出發(fā)送者的進程號，系統(tǒng)根據(jù)這兩個原語實現(xiàn)直接通信。這種一對一的通信，用來處理并發(fā)進程之間的合作是相當有效的。2.間接尋址（IndirectAddressing）

在間接尋址方式中，消息并不直接從發(fā)送進程傳到接收進程，而是要經(jīng)過一個中間介質(zhì)——臨時保存消息的隊列，通常稱為“信箱”。因此，兩個通信進程的操作是，一個進程將消息發(fā)到信箱中，另一個從信箱中取消息。二、直接通信和間接通信

883.7線程(THREAD)3.7.1線程的引入3.7.2進程和線程的比較3.7.3線程的執(zhí)行3.7.4線程的分類

引入線程的目的是以小的系統(tǒng)開銷來提高進程內(nèi)的并發(fā)程度。893.7.1線程的引入為提高進程內(nèi)各個功能模塊的并發(fā)性傳統(tǒng)os：為進程創(chuàng)建一些子孫進程進程：資源分配單位（存儲器、文件）和CPU調(diào)度（分派）單位，由PCB和進程間上下文確定。

由于進程是資源的擁有者，故其在創(chuàng)建、撤銷及狀態(tài)轉(zhuǎn)換時，系統(tǒng)要付出較大的時間和空間開銷，從而使得系統(tǒng)中的進程不宜過多，切換頻率不宜太高，因此限制了并發(fā)程度的提高。為了減少程序并發(fā)所付出的時間和空間開銷，使os具有更好的并發(fā)性，把進程的兩個基本屬性分開。90現(xiàn)代os：一個進程可以創(chuàng)建多個線程線程：“輕量級進程（LightweightProcess）”，是進程的一個實體，使被獨立調(diào)度和分派的基本單位，表示進程中的一個控制點（執(zhí)行體），執(zhí)行一系列指令。91進程只作為其他資源分配單位線程作為CPU調(diào)度單位只擁有必不可少的資源，如：線程狀態(tài)、寄存器上下文和棧同樣具有就緒、阻塞和執(zhí)行三種