并發(fā)進(jìn)程及死鎖問題課件

第五章并發(fā)進(jìn)程及死鎖問題進(jìn)程間的聯(lián)系進(jìn)程的同步機(jī)制──信號量及P.V操作（解決進(jìn)程同步互斥問題）第五章并發(fā)進(jìn)程及死鎖問題進(jìn)程間的聯(lián)系5.1進(jìn)程間的制約關(guān)系相交進(jìn)程與無關(guān)進(jìn)程相交進(jìn)程：指多個并發(fā)進(jìn)程在邏輯上有某種聯(lián)系無關(guān)進(jìn)程（不相交進(jìn)程）：在邏輯上無任何聯(lián)系的進(jìn)程5.1進(jìn)程間的制約關(guān)系相交進(jìn)程與無關(guān)進(jìn)程直接作用和間接作用直接作用： 進(jìn)程間的相互聯(lián)系是有意識的安排的，直接作用只發(fā)生在相交進(jìn)程間間接作用： 進(jìn)程間要通過某種中介發(fā)生聯(lián)系，是無意識安排的，可發(fā)生在相交進(jìn)程之間，也可發(fā)生在無關(guān)進(jìn)程之間直接作用和間接作用相互感知程度

交互關(guān)系

一個進(jìn)程對其他進(jìn)程的影響

相互不感知(完全不了解其它進(jìn)程的存在)競爭(competition)一個進(jìn)程的操作對其他進(jìn)程的結(jié)果無影響

間接感知(雙方都與第三方交互，如共享資源)通過共享進(jìn)行協(xié)作

一個進(jìn)程的結(jié)果依賴于從其他進(jìn)程獲得的信息

直接感知(雙方直接交互，如通信)通過通信進(jìn)行協(xié)作

一個進(jìn)程的結(jié)果依賴于從其他進(jìn)程獲得的信息

相互感知程度交互關(guān)系一個進(jìn)程對其他進(jìn)程的影響相互不感知進(jìn)程的同步（直接作用）進(jìn)程的同步：synchronism 指系統(tǒng)中多個進(jìn)程中發(fā)生的事件存在某種時序關(guān)系，需要相互合作，共同完成一項任務(wù)。具體說，一個進(jìn)程運行到某一點時要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài)進(jìn)程的同步（直接作用）進(jìn)程的同步：synchronism例:

司機(jī)P1售票員P2

while(true)while(true)

{{

啟動車輛；關(guān)門；

正常運行；售票；

到站停車；開門；

}}

例:

司機(jī)P1售票員P進(jìn)程的互斥（間接作用）mutualexclusion

由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競爭使用這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥臨界資源：criticalresource 系統(tǒng)中某些資源一次只允許一個進(jìn)程使用，稱這樣的資源為臨界資源或互斥資源或共享變量進(jìn)程的互斥（間接作用）mutualexclusion臨界區(qū)（互斥區(qū)）：criticalsection

一個程序片段的集合，這些程序片段分散在不同的進(jìn)程中，對某個共享的數(shù)據(jù)結(jié)構(gòu)（共享資源）進(jìn)行操作在進(jìn)程中涉及到臨界資源的程序段叫臨界區(qū)多個進(jìn)程的臨界區(qū)稱為相關(guān)臨界區(qū)臨界區(qū)（互斥區(qū)）：criticalsectiona:=a-1print(a)a:=a+1print(a)P1互斥P2互斥Ifa<0thena:=a+1elsea:=a-1P3互斥

進(jìn)程的互斥（間接作用）a:=a-1a:=a+1P1互斥P2互斥If并發(fā)進(jìn)程及死鎖問題課件使用互斥區(qū)的原則：有空讓進(jìn)：當(dāng)無進(jìn)程在互斥區(qū)時，任何有權(quán)使用互斥區(qū)的進(jìn)程可進(jìn)入無空等待：不允許兩個以上的進(jìn)程同時進(jìn)入互斥區(qū)多中擇一：當(dāng)沒有進(jìn)程在臨界區(qū)，而同時有多個進(jìn)程要求進(jìn)入臨界區(qū)，只能讓其中之一進(jìn)入臨界區(qū)，其他進(jìn)程必須等待有限等待：任何進(jìn)入互斥區(qū)的要求應(yīng)在有限的時間內(nèi)得到滿足讓權(quán)等待：處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用CPU，以使其他進(jìn)程有機(jī)會得到CPU的使用權(quán)使用互斥區(qū)的原則：有空讓進(jìn)：當(dāng)無進(jìn)程在互斥區(qū)時，任何有權(quán)使用使用互斥區(qū)的原則：前提：任何進(jìn)程無權(quán)停止其它進(jìn)程的運行 進(jìn)程之間相對運行速度無硬性規(guī)定進(jìn)程互斥的解決有兩種做法:由競爭各方平等協(xié)商引入進(jìn)程管理者，由管理者來協(xié)調(diào)競爭各方對互斥資源的使用具體方法：硬件（當(dāng)一個進(jìn)程進(jìn)入臨界區(qū),就屏蔽所有中斷，但成本高）軟件（用編程解決，但常常忙等待）使用互斥區(qū)的原則：進(jìn)程互斥的軟件方法通過平等協(xié)商方式實現(xiàn)進(jìn)程互斥的最初方法是軟件方法

其基本思路是在進(jìn)入?yún)^(qū)檢查和設(shè)置一些標(biāo)志，如果已有進(jìn)程在臨界區(qū)，則在進(jìn)入?yún)^(qū)通過循環(huán)檢查進(jìn)行等待；在退出區(qū)修改標(biāo)志

其中的主要問題是設(shè)置什么標(biāo)志和如何檢查標(biāo)志進(jìn)程互斥的軟件方法通過平等協(xié)商方式實現(xiàn)進(jìn)程互斥的最初方法是軟軟件解法(1)free:表示臨界區(qū)標(biāo)志

true:有進(jìn)程在臨界區(qū)

false:無進(jìn)程在臨界區(qū)(初值)

....

while(free);

free=true;

臨界區(qū)free=false;軟件解法(1)free:表示臨界區(qū)標(biāo)志

軟件解法(2)turn:true P進(jìn)入臨界區(qū)false Q進(jìn)入臨界區(qū)....P:while(notturn);臨界區(qū)turn=false;Q:while(turn);臨界區(qū)turn=true;軟件解法(2)turn:true P進(jìn)入臨界區(qū)軟件解法的缺點：1.忙等待2.實現(xiàn)過于復(fù)雜，需要高的編程技巧

軟件解法的缺點：硬件解法(1)

“測試并設(shè)置”指令booleanTS(boolean*lock){booleanold;old=*lock;*lock=true;}whileTS(&lock);臨界區(qū)lock=false;硬件解法(1)

“測試并設(shè)置”指令boolean硬件解法(2)

“交換”指令voidSWAP(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}key=true;do{SWAP(&lock,key);}while(key);臨界區(qū)lock:=false;硬件解法(2)

“交換”指令voidSWAP(i硬件解法(3)

“開關(guān)中斷”指令進(jìn)入臨界區(qū)前執(zhí)行：執(zhí)行“關(guān)中斷”指令離開臨界區(qū)后執(zhí)行：執(zhí)行“開中斷”指令硬件解法(3)

“開關(guān)中斷”指令進(jìn)入臨界區(qū)前執(zhí)行：5.2進(jìn)程的同步機(jī)制──

信號量及P.V操作（解決進(jìn)程同步與互斥）

5.2.1概念同步機(jī)制：信號量及P、V操作；管程；條件臨界域；路徑表達(dá)式等（用于集中式系統(tǒng)中）

會合；通信順序進(jìn)程；分布進(jìn)程；遠(yuǎn)程過程調(diào)用等（適用于分布式系統(tǒng)中）5.2進(jìn)程的同步機(jī)制──

信號量及P.V操作（解決進(jìn)程同步信號量分類公用信號量私用信號量二元信號量一般信號量信號量分類公用信號量同步機(jī)制應(yīng)滿足的基本要求：*描述能力*可以實現(xiàn)*效率高*使用方便同步機(jī)制應(yīng)滿足的基本要求：信號量：semaphore是一個數(shù)據(jù)結(jié)構(gòu)定義如下：strucsemaphore{ intvalue; pointer_PCBqueue;}信號量說明：semaphores;信號量：semaphore是一個數(shù)據(jù)結(jié)構(gòu)P、V操作P(s){s.value=s.value--;if(s.value<0){ 該進(jìn)程狀態(tài)置為等待狀態(tài)將該進(jìn)程的PCB插入相應(yīng)的等待隊列末尾s.queue;}}P、V操作P(s)P、V操作V(s){s.value=s.value++;if(s.value<=0){喚醒相應(yīng)等待隊列s.queue中等待的一個進(jìn)程改變其狀態(tài)為就緒態(tài)并將其插入就緒隊列

}}P、V操作V(s)P、V操作為原語操作原語：primitiveoratomicaction是由若干多機(jī)器指令構(gòu)成的完成某種特定功能的一段程序，具有不可分割性 即原語的執(zhí)行必須是連續(xù)的，在執(zhí)行過程中不允許被中斷實現(xiàn)：開關(guān)中斷P、V操作為原語操作信號量的使用：

必須置一次且只能置一次初值初值不能為負(fù)數(shù)

只能執(zhí)行P、V操作信號量的使用：用P、V操作解決進(jìn)程間互斥問題P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)用P、V操作解決進(jìn)程間互斥問題P(mutex)V(mutex經(jīng)典的生產(chǎn)者─消費者問題消費者生產(chǎn)者經(jīng)典的生產(chǎn)者─消費者問題消費者生產(chǎn)者經(jīng)典的生產(chǎn)者─消費者問題同步問題： P進(jìn)程不能往“滿”的緩沖區(qū)中放產(chǎn)品，設(shè)置信號量為S1Q進(jìn)程不能從“空”的緩沖區(qū)中取產(chǎn)品，設(shè)置信號量S2經(jīng)典的生產(chǎn)者─消費者問題同步問題：S1初值為1，S2初值為0P：Q：while(true){while(true){生產(chǎn)一個產(chǎn)品;P(s2);P(s1);從緩沖區(qū)取產(chǎn)品;送產(chǎn)品到緩沖區(qū);V(s1);V(s2);消費產(chǎn)品;};};單緩沖區(qū)生產(chǎn)者-消費者問題S1初值為1，S2初值為0P：并發(fā)進(jìn)程及死鎖問題課件多個緩沖區(qū)的生產(chǎn)者和消費者P：

i=0;

while(true){

生產(chǎn)產(chǎn)品;

P(S1);

往Buffer[i]放產(chǎn)品;

V(S2);

i=(i+1)%n;};Q：j=0;while(true){P(S2);從Buffer[j]取產(chǎn)品;V(S1);消費產(chǎn)品;j=(j+1)%n;};多個緩沖區(qū)的生產(chǎn)者和消費者P：

i=0;

while(【思考題】要不要對緩沖區(qū)（臨界資源）進(jìn)行互斥操作？【思考題】要不要對緩沖區(qū)（臨界資源）進(jìn)行互斥操作？Q：j=0;while(true){P(S2);P(mutex);從Buffer[j]取產(chǎn)品;V(mutex);V(S1);消費產(chǎn)品;j=(j+1)%n;};n個緩沖區(qū)、m個生產(chǎn)者和k個消費者P：

i=0;

while(true){

生產(chǎn)產(chǎn)品;

P(S1);

P(mutex);往Buffer[i]放產(chǎn)品;V(mutex);

V(S2);

i=(i+1)%n;};有錯誤？若顛倒兩個P操作的順序？Q：n個緩沖區(qū)、m個生產(chǎn)者和k個消費者P：

i=0;

wQ：j=0;while(true){P(S2);P(mutex);從Buffer[j]取產(chǎn)品;j=(j+1)%n;V(mutex);V(S1);消費產(chǎn)品;};n個緩沖區(qū)、m個生產(chǎn)者和k個消費者P：

i=0;

while(true){

生產(chǎn)產(chǎn)品;

P(S1);

P(mutex);往Buffer[i]放產(chǎn)品;i=(i+1)%n;V(mutex);

V(S2);

};正確Q：n個緩沖區(qū)、m個生產(chǎn)者和k個消費者P：

i=0;

wP.V操作討論1)信號量的物理含義：S>0表示有S個資源可用S=0表示無資源可用S<0則|S|表示S等待隊列中的進(jìn)程個數(shù)P(S):表示申請一個資源V(S)表示釋放一個資源。信號量的初值應(yīng)該大于等于0P.V操作討論2)P.V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作當(dāng)為互斥操作時，它們同處于同一進(jìn)程當(dāng)為同步操作時，則不在同一進(jìn)程中出現(xiàn)如果P(S1)和P(S2)兩個操作在一起，那么P操作的順序至關(guān)重要,一個同步P操作與一個互斥P操作在一起時同步P操作在互斥P操作前而兩個V操作無關(guān)緊要2)P.V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作3）P.V操作的優(yōu)缺點優(yōu)點：簡單，而且表達(dá)能力強(qiáng)（用P.V操作可解決任何同步互斥問題）缺點：不夠安全；P.V操作使用不當(dāng)會出現(xiàn)死鎖；遇到復(fù)雜同步互斥問題時實現(xiàn)復(fù)雜3）P.V操作的優(yōu)缺點當(dāng)同時需要多種資源時怎么辦?

單個信號量使用很不方便，容易產(chǎn)生混亂,且前面已經(jīng)提到對多個信號量進(jìn)行P操作時,如果順序稍有差錯會導(dǎo)致錯誤發(fā)生，因此可以采用信號量集的方法當(dāng)同時需要多種資源時怎么辦?單個信號量信號量集——AND型信號量集

AND型信號量集是指同時需要多種資源且每種占用一個時的信號量操作

AND型信號量集的基本思想：在一個原語中申請整段代碼需要的多個臨界資源，要么全部分配給它，要么一個都不分配AND型信號量集P原語為SwaitAND型信號量集V原語為Ssignal信號量集——AND型信號量集AND型信號量集是指同時需要多Swait(S1,S2,…,Sn) //P原語；{while(TRUE){if(S1>=1&&S2>=1&&…&&Sn>=1){ //滿足資源要求時的處理；for(i=1;i<=n;++i)-–Si;//注：與P的處理不同，這里是在確信可滿足//資源要求時，才進(jìn)行減1操作；break;}else{ //某些資源不夠時的處理；

調(diào)用進(jìn)程進(jìn)入第一個小于1信號量的等待隊列Sj.queue;

阻塞調(diào)用進(jìn)程;}}}Swait(S1,S2,…,Sn) //P原語；Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //釋放占用的資源；for(在Si.queue中等待的每一個進(jìn)程P)//檢查每種資源的等待隊列的所有進(jìn)程；{從等待隊列Si.queue中取出進(jìn)程P;

Ssignal(S1,S2,…,Sn)if(判斷進(jìn)程P是否通過Swait中的測試)//注：與signal不同，這里要進(jìn)行重新判斷；{//通過檢查（資源夠用）時的處理；

進(jìn)程P進(jìn)入就緒隊列;}else{//未通過檢查（資源不夠用）時的處理；

進(jìn)程P進(jìn)入某等待隊列；}}}}if(判斷進(jìn)程P是否通過Swait中的測試)一般“信號量集”一般信號量集是指同時需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個臨界值時的信號量處理

一般信號量集的基本思路就是在AND型信號量集的基礎(chǔ)上進(jìn)行擴(kuò)充，在一次原語操作中完成所有的資源申請一般“信號量集”一般信號量集是指同時需要多種資源、每種占用的進(jìn)程對信號量Si的測試值為ti（表示信號量的判斷條件，要求Si>=ti；即當(dāng)資源數(shù)量低于ti時，便不予分配）占用值為di（表示資源的申請量，即Si=Si-di）對應(yīng)的P、V原語格式為：Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);進(jìn)程對信號量Si的一般“信號量集”可以用于各種情況的資源分配和釋放，幾種特殊情況：Swait(S,d,d)表示每次申請d個資源，當(dāng)少于d個時，便不分配Swait(S,1,1)表示互斥信號量Swait(S,1,0)可作為一個可控開關(guān)（當(dāng)S

1時，允許多個進(jìn)程進(jìn)入臨界區(qū)；當(dāng)S=0時，禁止任何進(jìn)程進(jìn)入臨界區(qū)）一般“信號量集”可以用于各種情況的資源分配和釋放，幾種特殊情【思考題】1.用P.V操作解決下圖之同步問題:getcopyputfstg【思考題】1.用P.V操作解決下圖之同步問題:getcopy用P.V操作解決司機(jī)與售票員的問題司機(jī)進(jìn)程：while(true){啟動車輛正常駕駛到站停車}…售票員進(jìn)程：while(true){關(guān)門售票開門}…用P.V操作解決司機(jī)與售票員的問題司機(jī)進(jìn)程：售票員進(jìn)程：5.2.2IPC經(jīng)典問題1.讀者寫者問題

有兩組并發(fā)進(jìn)程:讀者和寫者,共享一組數(shù)據(jù)區(qū)要求：允許多個讀者同時執(zhí)行讀操作不允許讀者、寫者同時操作不允許多個寫者同時操作5.2.2IPC經(jīng)典問題1.讀者寫者問題第一類：讀者優(yōu)先如果讀者來：1）無讀者、寫者，新讀者可以讀2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等如果寫者來：1）無讀者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待第一類：讀者優(yōu)先如果讀者來：第一類讀者寫者問題的解法讀者：while(true){P(mutex);readcount++;if(readcount==1)P(w);V(mutex);讀P(mutex);readcount--;if(readcount==0)V(w);V(mutex);};寫者：while(true){P(w);寫V(w);};第一類讀者寫者問題的解法讀者：寫者：第一類讀者寫者問題的解法

（一般信號量集）讀者：swait(wmutex,1,1;rcount,R,0);寫；ssignal(wmutex,1);寫者：swait(rcount,1,1;wmutex,1,0);寫；ssignal(rcount,1);第一類讀者寫者問題的解法

（一般信號量集）讀者：寫者：2.哲學(xué)家就餐問題 有五個哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子每個哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉 為了吃通心粉，每個哲學(xué)家必須拿到兩只筷子，并且每個人只能直接從自己的左邊或右邊去取筷子2.哲學(xué)家就餐問題 有五個哲學(xué)家圍坐在一圓桌旁，桌中央有一盤#defineN5voidphilosopher(inti){while(true){

思考；取fork[i];取fork[(i+1)%5]；進(jìn)食；放fork[i];放fork[(i+1)%5]；}}#defineN5

為防止死鎖發(fā)生可采取的措施：最多允許4個哲學(xué)家同時坐在桌子周圍僅當(dāng)一個哲學(xué)家左右兩邊的筷子都可用時，才允許他拿筷子（

）給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之為了避免死鎖，把哲學(xué)家分為三種狀態(tài)，思考，饑餓，進(jìn)食，并且一次拿到兩只筷子，否則不拿 為防止死鎖發(fā)生可采取的措施：哲學(xué)家就餐問題解法（1）#defineN5voidphilosopher(inti){while(true){

思考；取fork[i];取fork[(i+1)%5]；進(jìn)食；放fork[i];放fork[(i+1)%5]；}}哲學(xué)家就餐問題解法（1）#defineN5哲學(xué)家就餐問題解法（2）#defineN5#defineTHINKING0#defineHUNGRY1#defineEATING2#typedefintsemaphore;intstate[N];semaphoremutex=1;semaphores[N];哲學(xué)家就餐問題解法（2）#defineN5voidtest(inti){if(state[i]==HUNGRY)&&(state[(i-1)%5]!=EATING)&&(state[(i+1)%5]!=EATING){state[i]=EATING;V(&s[i]);}}voidtest(inti)voidphilosopher(inti){while(true){思考;P(&mutex);state[i]=HUNGRY;test(i);V(&mutex);P(&s[i]);拿左筷子；拿右筷子；進(jìn)食；

放左筷子；放右筷子；P(&mutex)state[i]=THINKING；test([i-1]%5);test([i+1]%5);V(&mutex);}}state[i]=THINKINGs[i]=0voidphilosopher(inti)【作業(yè)】1.推廣例子中的消息緩沖問題。消息緩沖區(qū)為k個，有1個發(fā)送進(jìn)程，n個接收進(jìn)程，每個接收進(jìn)程對發(fā)送來的消息都必須取一次若有m個發(fā)送進(jìn)程呢？【作業(yè)】1.推廣例子中的消息緩沖問題。2.第二類讀者寫者問題：寫者優(yōu)先條件：1）多個讀者可以同時進(jìn)行讀2）寫者必須互斥（只允許一個寫者寫，也不能讀者寫者同時進(jìn)行）3）寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待，喚醒時優(yōu)先考慮寫者）2.第二類讀者寫者問題：3.有一個系統(tǒng)，定義P、V操作如下：P(s):s:=s-1;ifs<0then

將本進(jìn)程插入相應(yīng)隊列末尾等待；V(s)：s:=s+1;ifs<=0then從相應(yīng)等待隊列隊尾喚醒一個進(jìn)程，將其插入就緒隊列；3.有一個系統(tǒng)，定義P、V操作如下：

問題：1）這樣定義P、V操作是否有問題？2）用這樣的P、V操作實現(xiàn)N個進(jìn)程競爭使用某一共享變量的互斥機(jī)制。3）對于2）的解法，有無效率更高的方法。如有，試問降低了多少復(fù)雜性？問題：4.理發(fā)師睡覺問題 理發(fā)店里有一位理發(fā)師，一把理發(fā)椅和N把供等候理發(fā)的顧客坐的椅子如果沒有顧客,則理發(fā)師便在理發(fā)椅上睡覺。當(dāng)一個顧客到來時，他必須先喚醒理發(fā)師 如果顧客到來時理發(fā)師正在理發(fā)，則如果有空椅子，可坐下來等；否則離開4.理發(fā)師睡覺問題5.3進(jìn)程通信概述消息緩沖通信方式5.3進(jìn)程通信概述5.3.1概述 P.V操作實現(xiàn)的是進(jìn)程之間的低級通訊，所以P.V為低級通訊原語。它只能傳遞簡單的信號，不能傳遞交換大量信息

如果要在進(jìn)程間傳遞大量信息則要用Send/Receive原語（高級通訊原語）5.3.1概述 P.V操作實現(xiàn)的是進(jìn)程之間的低級通訊，所以進(jìn)程通信的方式共享內(nèi)存：相互通信的進(jìn)程間設(shè)有公共內(nèi)存，一組進(jìn)程向該公共內(nèi)存中寫，另一組進(jìn)程從公共內(nèi)存中讀，通過這種方式實現(xiàn)兩組進(jìn)程間的信息交換這種通信模式需要解決兩個問題？進(jìn)程通信的方式消息傳遞：系統(tǒng)為進(jìn)程提供了兩個高級通訊原語send和receivesend： 當(dāng)要進(jìn)行消息傳遞時執(zhí)行sendreceive： 當(dāng)接收者要接收消息時執(zhí)行receive消息傳遞：共享文件模式：管道通信共享文件模式：管道通信消息傳遞模式消息緩沖在內(nèi)存中開設(shè)緩沖區(qū)，發(fā)送進(jìn)程將消息送入緩沖區(qū)，接收進(jìn)程接收傳遞來的緩沖區(qū)信箱通信消息傳遞模式消息緩沖直接方式：發(fā)送進(jìn)程發(fā)消息時要指定接收進(jìn)程的名字，反過來，接收時要指明發(fā)送進(jìn)程的名字Send(receiver,message)Receiver(sender,message)*對稱形式：一對一*非對稱形式：多對一（顧客/服務(wù)員）有緩沖（有界，無界），無緩沖直接方式：發(fā)送進(jìn)程發(fā)消息時要指定接收進(jìn)程的名字，間接方式：發(fā)送進(jìn)程發(fā)消息時不指定接收進(jìn)程的名字，而是指定一個中間媒介，即信箱。進(jìn)程間通過信箱實現(xiàn)通信

發(fā)送原語：send(MB,Message)接收原語：receive(MB,Message)間接方式：發(fā)送進(jìn)程發(fā)消息時不指定接收進(jìn)程的名字，而是指定5.3.2消息緩沖（有界緩沖區(qū)原理）：在操作系統(tǒng)空間設(shè)置一組緩沖區(qū)，當(dāng)發(fā)送進(jìn)程需要發(fā)送消息時，執(zhí)行send系統(tǒng)調(diào)用，產(chǎn)生自愿性中斷，進(jìn)入操作系統(tǒng)，操作系統(tǒng)為發(fā)送進(jìn)程分配一個空緩沖區(qū)，并將所發(fā)送的消息從發(fā)送進(jìn)程copy到緩沖區(qū)中，然后將該載有消息的緩沖區(qū)連接到接收進(jìn)程的消息鏈鏈尾，如此就完成了發(fā)送過程。發(fā)送進(jìn)程返回到用戶態(tài)繼續(xù)執(zhí)行5.3.2消息緩沖（有界緩沖區(qū)原理）：5.3.2消息緩沖（續(xù)1）（有界緩沖區(qū)原理）：在以后某個時刻，當(dāng)接收進(jìn)程執(zhí)行到receive接收原語時，也產(chǎn)生自愿性中斷進(jìn)入操作系統(tǒng)，由操作系統(tǒng)將載有消息的緩沖區(qū)從消息鏈中取出，并把消息內(nèi)容copy到接收進(jìn)程空間，之后收回緩沖區(qū)，如此就完成了消息的接收，接收進(jìn)程返回到用戶態(tài)繼續(xù)進(jìn)行5.3.2消息緩沖（續(xù)1）（有界緩沖區(qū)原理）：PCB......Send(R,M)......SIZE:消息長度TEXT:消息正文......消息鏈指針............Receive(pid,N)......SIZE:消息長度TEXT:消息正文......M:N:接受進(jìn)程R發(fā)送進(jìn)程S消息消息消息......PCB..................M:N:接受進(jìn)程消息緩沖區(qū)結(jié)構(gòu)：消息長度消息正文發(fā)送者消息隊列指針消息緩沖區(qū)結(jié)構(gòu)：用P.V操作來實現(xiàn)Send原語:Send（R，M）P(m-mutex);Begin把緩沖區(qū)掛到接收進(jìn)程根據(jù)R找接收進(jìn)程，的消息鏈鏈尾;如果沒找到出錯返回;V(m-mutex);申請空緩沖區(qū)P（s-b）；V(s-m);P(b-mutex);END摘空緩沖區(qū);V(b-mutex);把消息從M處copy到空緩沖區(qū);其中s-b初值:n;s-m初值:0用P.V操作來實現(xiàn)Send原語:5.3.3信箱通信信箱組成信箱說明

與

信箱體可存放信件數(shù)，已存放信件數(shù)，指針信箱使用規(guī)則若發(fā)送信件時信箱已滿，則發(fā)送進(jìn)程被置為“等信箱”狀態(tài)，直到信箱有空時才被釋放若取信件時信箱中無信，則接收進(jìn)程被置為“等信件”狀態(tài)，直到有信件時才被釋放5.3.3信箱通信信箱組成5.3.3信箱通信（續(xù)1）Send實現(xiàn)send（N，M）：把信件M送到指定的信箱N中步驟：查找指定信箱N；若信箱未滿，則把信件M送入信箱且釋放“等信件”者；若信箱已滿置發(fā)送信件進(jìn)程為“等信箱”狀態(tài)；5.3.3信箱通信（續(xù)1）Send實現(xiàn)5.3.3信箱通信（續(xù)2）Receive實現(xiàn)receive（N，X）：從指定信箱N中取出一封信，存放到指定的地址X中步驟：查找指定信箱N；若信箱中有信，則取出一封信存于X中且釋放“等信箱”者；若信箱中無信件則置接收信件進(jìn)程“等信件”狀態(tài)；5.3.3信箱通信（續(xù)2）Receive實現(xiàn)5.3.3信箱通信（續(xù)3）應(yīng)用實例磁盤管理進(jìn)程：從信箱中收取信件，處理，啟動磁盤工作其他進(jìn)程：要求訪問磁盤，向磁盤管理進(jìn)程發(fā)一封信作業(yè)：

用進(jìn)程通信的辦法解決生產(chǎn)者消費者問題

5.3.3信箱通信（續(xù)3）應(yīng)用實例5.3.4管道通信方式Pipe

也稱共享文件方式，基于文件系統(tǒng)，利用一個打開的共享文件連接兩個相互通信的進(jìn)程，文件作為緩沖傳輸介質(zhì)發(fā)送進(jìn)程接收進(jìn)程字符流方式寫入讀出先進(jìn)先出順序5.3.4管道通信方式Pipe發(fā)送進(jìn)程接收進(jìn)程字符流方式5.4線程的基本概念線程的引入線程與進(jìn)程的對比線程的實現(xiàn)實例：Solaris5.4線程的基本概念線程的引入5.4.1線程的引入進(jìn)程的兩個基本屬性：資源的擁有者：

給每個進(jìn)程分配一虛擬地址空間，保存進(jìn)程映像，控制一些資源（文件，I/O設(shè)備），有狀態(tài)、優(yōu)先級、調(diào)度調(diào)度單位：

進(jìn)程是一個執(zhí)行軌跡

以上兩個屬性構(gòu)成進(jìn)程并發(fā)執(zhí)行的基礎(chǔ)5.4.1線程的引入進(jìn)程的兩個基本屬性：5.4.1線程的引入（續(xù)1）系統(tǒng)必須完成的操作：創(chuàng)建進(jìn)程撤消進(jìn)程進(jìn)程切換缺點：時間空間開銷大，限制并發(fā)度的提高5.4.1線程的引入（續(xù)1）系統(tǒng)必須完成的操作：5.4.1線程的引入（續(xù)2）在操作系統(tǒng)中，進(jìn)程的引入提高了計算機(jī)資源的利用效率。但在進(jìn)一步提高進(jìn)程的并發(fā)性時，人們發(fā)現(xiàn)進(jìn)程切換開銷占的比重越來越大，同時進(jìn)程間通信的效率也受到限制線程的引入正是為了簡化進(jìn)程間的通信，以小的開銷來提高進(jìn)程內(nèi)的并發(fā)程度5.4.1線程的引入（續(xù)2）在操作系統(tǒng)中，進(jìn)程的引入提高了5.4.1線程的引入（續(xù)3）線程：有時稱輕量級進(jìn)程

進(jìn)程中的一個運行實體是一個CPU調(diào)度單位資源的擁有者還是進(jìn)程或稱任務(wù)將原來進(jìn)程的兩個屬性分開處理5.4.1線程的引入（續(xù)3）線程：有時稱輕量級進(jìn)程5.4.1線程的引入（續(xù)4）線程：有執(zhí)行狀態(tài)（狀態(tài)轉(zhuǎn)換）不運行時保存上下文有一個執(zhí)行棧有一些局部變量的靜態(tài)存儲可存取所在進(jìn)程的內(nèi)存和其他資源可以創(chuàng)建、撤消另一個線程5.4.1線程的引入（續(xù)4）線程：線程和進(jìn)程：單進(jìn)程、單線程單進(jìn)程、多線程多進(jìn)程、一個進(jìn)程一個線程多進(jìn)程、一個進(jìn)程多個線程線程和進(jìn)程：PCB用戶棧單線程進(jìn)程模型用戶地址空間核心棧線程控制塊：包含了寄存器映像，線程優(yōu)先數(shù)和線程狀態(tài)信息PCB用單線程進(jìn)程模型用戶地址空間核線程控制塊：PCB多線程進(jìn)程模型用戶地址空間用戶棧核心棧線程控制塊用戶棧核心棧線程控制塊用戶棧核心棧線程控制塊PCB多線程進(jìn)程模型用戶用核線程用核線程用核線程引入線程的好處：創(chuàng)建一個新線程花費時間少（結(jié)束亦如此）兩個線程的切換花費時間少（如果機(jī)器設(shè)有“存儲[恢復(fù)]所有寄存器”指令，則整個切換過程用幾條指令即可完成）因為同一進(jìn)程內(nèi)的線程共享內(nèi)存和文件，因此它們之間相互通信無須調(diào)用內(nèi)核適合多處理機(jī)系統(tǒng)引入線程的好處：創(chuàng)建一個新線程花費時間少（結(jié)束亦如此）例子1：LAN中的一個文件服務(wù)器，在一段時間內(nèi)需要處理幾個文件請求因此有效的方法是：為每一個請求創(chuàng)建一個線程在一個SMP機(jī)器上：多個線程可以同時在不同的處理器上運行例子1：LAN中的一個文件服務(wù)器，在一段時間內(nèi)需要處理幾個文例子2：一個線程顯示菜單，并讀入用戶輸入；另一個線程執(zhí)行用戶命令考慮一個應(yīng)用：由幾個獨立部分組成，這幾個部分不需要順序執(zhí)行，則每個部分可以以線程方式實現(xiàn)當(dāng)一個線程因I/O阻塞時，可以切換到同一應(yīng)用的另一個線程例子2：一個線程顯示菜單，并讀入用戶輸入；5.4.2線程與進(jìn)程的比較調(diào)度并發(fā)性擁有資源系統(tǒng)開銷5.4.2線程與進(jìn)程的比較調(diào)度5.4.3線程的實現(xiàn)機(jī)制用戶級線程核心級線程兩者結(jié)合方法5.4.3線程的實現(xiàn)機(jī)制用戶級線程一、用戶級線程（UserLevelThread）由應(yīng)用程序完成所有線程的管理

通過線程庫(用戶空間)一組管理線程的過程核心不知道線程的存在線程切換不需要核心態(tài)特權(quán)調(diào)度是應(yīng)用特定的一、用戶級線程（UserLevelThread）由應(yīng)用程線程庫創(chuàng)建、撤消線程在線程之間傳遞消息和數(shù)據(jù)調(diào)度線程執(zhí)行保護(hù)和恢復(fù)線程上下文線程庫創(chuàng)建、撤消線程對用戶級線程的核心活動核心不知道線程的活動，但仍然管理線程的進(jìn)程的活動當(dāng)線程調(diào)用系統(tǒng)調(diào)用時，整個進(jìn)程阻塞但對線程庫來說，線程仍然是運行狀態(tài)

即線程狀態(tài)是與進(jìn)程狀態(tài)獨立的對用戶級線程的核心活動核心不知道線程的活動，但仍然管理線程的