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

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

2、程之間,進(jìn)程的同步（直接作用）,進(jìn)程的同步：synchronism指系統(tǒng)中多個(gè)進(jìn)程中發(fā)生的事件存在某種時(shí)序關(guān)系，需要相互合作，共同完成一項(xiàng)任務(wù)。具體說，一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài),例: 司機(jī) P1 售票員 P2 while (true) while (true)

3、 { { 啟動(dòng)車輛； 關(guān)門； 正常運(yùn)行； 售票； 到站停車； 開門； } },進(jìn)程的互斥（間接作用）mutual exclusion 由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競(jìng)爭使用

4、這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥臨界資源：critical resource 系統(tǒng)中某些資源一次只允許一個(gè)進(jìn)程使用，稱這樣的資源為臨界資源或互斥資源或共享變量,臨界區(qū)（互斥區(qū)）：critical section一個(gè)程序片段的集合，這些程序片段分散在不同的進(jìn)程中，對(duì)某個(gè)共享的數(shù)據(jù)結(jié)構(gòu)（共享資源）進(jìn)行操作 在進(jìn)程中涉及到臨界資源的程序段叫臨界區(qū) 多個(gè)進(jìn)程的臨界區(qū)稱為相關(guān)臨界區(qū),,a := a -1 print

5、(a),a := a +1 print (a),進(jìn)程的互斥（間接作用）,使用互斥區(qū)的原則：,有空讓進(jìn)：當(dāng)無進(jìn)程在互斥區(qū)時(shí)，任何有權(quán)使用互斥區(qū)的進(jìn)程可進(jìn)入無空等待：不允許兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入互斥區(qū)多中擇一：當(dāng)沒有進(jìn)程在臨界區(qū)，而同時(shí)有多個(gè)進(jìn)程要求進(jìn)入臨界區(qū)，只能讓其中之一進(jìn)入臨界區(qū)，其他進(jìn)程必須等待有限等待：任何進(jìn)入互斥區(qū)的要求應(yīng)在有限的時(shí)間內(nèi)得到滿足讓權(quán)等待：處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用CPU，以使其他進(jìn)程有機(jī)會(huì)得到CPU

6、的使用權(quán),使用互斥區(qū)的原則：前提：任何進(jìn)程無權(quán)停止其它進(jìn)程的運(yùn)行 進(jìn)程之間相對(duì)運(yùn)行速度無硬性規(guī)定進(jìn)程互斥的解決有兩種做法:由競(jìng)爭各方平等協(xié)商引入進(jìn)程管理者，由管理者來協(xié)調(diào)競(jìng)爭各方對(duì)互斥資源的使用具體方法：硬件（當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū),就屏蔽所有中斷，但成本高）軟件（用編程解決，但常常忙等待 ）,進(jìn)程互斥的軟件方法,通過平等協(xié)商方式實(shí)現(xiàn)進(jìn)程互斥的最初方法是軟件方法 其基本思路是在進(jìn)入?yún)^(qū)檢查和設(shè)置一些標(biāo)志，如果已有進(jìn)程在

7、臨界區(qū)，則在進(jìn)入?yún)^(qū)通過循環(huán)檢查進(jìn)行等待；在退出區(qū)修改標(biāo)志 其中的主要問題是設(shè)置什么標(biāo)志和如何檢查標(biāo)志,軟件解法 (1),free: 表示臨界區(qū)標(biāo)志 true: 有進(jìn)程在臨界區(qū) false:無進(jìn)程在臨界區(qū)(初值) .... while (free); free = true; 臨界區(qū) free = false;,,,軟件解法 (2),

8、turn: true P進(jìn)入臨界區(qū) false Q進(jìn)入臨界區(qū) ....P: while (not turn); 臨界區(qū) turn = false;Q: while (turn); 臨界區(qū) turn = true;,,,,,軟件解法的缺點(diǎn)： 1. 忙等待 2. 實(shí)現(xiàn)過于復(fù)雜，需要高的編程技巧,硬件解法 (1) “測(cè)試并設(shè)置”指令,boolean

9、TS (boolean *lock) { boolean old; old = *lock; *lock = true; },while TS(&lock); 臨界區(qū) lock = false;,,,硬件解法 (2) “交換”指令,void SWAP(int *a, int *b){int temp;temp = *a;*a = *b;*b = temp;},key = tr

10、ue; do { SWAP(&lock,key); }while(key); 臨界區(qū) lock:=false;,,,硬件解法 (3) “開關(guān)中斷”指令,進(jìn)入臨界區(qū)前執(zhí)行： 執(zhí)行“關(guān)中斷”指令離開臨界區(qū)后執(zhí)行： 執(zhí)行“開中斷”指令,5.2 進(jìn)程的同步機(jī)制──信號(hào)量及P.V操作（解決進(jìn)程同步與互斥）5.2.1概念,同步機(jī)制： 信號(hào)量及P、V操作；管程；條件臨界域；路徑

11、表達(dá)式等（用于集中式系統(tǒng)中） 會(huì)合；通信順序進(jìn)程；分布進(jìn)程；遠(yuǎn)程過程調(diào)用等（適用于分布式系統(tǒng)中）,信號(hào)量分類,公用信號(hào)量私用信號(hào)量二元信號(hào)量一般信號(hào)量,同步機(jī)制應(yīng)滿足的基本要求：* 描述能力* 可以實(shí)現(xiàn)* 效率高* 使用方便,信號(hào)量：semaphore,是一個(gè)數(shù)據(jù)結(jié)構(gòu)定義如下： struc semaphore {int value;pointer_PCB queue; }信號(hào)量說

12、明： semaphore s;,P、V操作,P(s){ s.value = s.value --; if (s.value < 0) { 該進(jìn)程狀態(tài)置為等待狀態(tài) 將該進(jìn)程的PCB插入相應(yīng)的等待隊(duì)列末尾s.queue; }},P、V操作,V(s){ s.value = s.value ++; if (s.value < = 0) { 喚醒相應(yīng)等待隊(duì)列s.queue中等待的一

13、個(gè)進(jìn)程 改變其狀態(tài)為就緒態(tài) 并將其插入就緒隊(duì)列 }},P、V操作為原語操作原語：primitive or atomic action 是由若干多機(jī)器指令構(gòu)成的完成某種特定功能的一段程序，具有不可分割性即原語的執(zhí)行必須是連續(xù)的，在執(zhí)行過程中不允許被中斷 實(shí)現(xiàn)：開關(guān)中斷,信號(hào)量的使用： 必須置一次且只能置一次初值 初值不能為負(fù)數(shù) 只能執(zhí)行P、V操作,用P、V操作解決進(jìn)程間互斥

14、問題,經(jīng)典的生產(chǎn)者─消費(fèi)者問題,消費(fèi)者,生產(chǎn)者,經(jīng)典的生產(chǎn)者─消費(fèi)者問題,同步問題： P進(jìn)程不能往“滿”的緩沖區(qū)中放產(chǎn)品，設(shè)置信號(hào)量為S1 Q進(jìn)程不能從“空”的緩沖區(qū)中取產(chǎn)品，設(shè)置信號(hào)量S2,S1初值為1，S2初值為0,P： Q：while (true) { while (true) { 生產(chǎn)一個(gè)產(chǎn)品;

15、 P(s2); P(s1) ; 從緩沖區(qū)取產(chǎn)品; 送產(chǎn)品到緩沖區(qū); V(s1); V(s2); 消費(fèi)產(chǎn)品;}; };,單緩沖區(qū)生產(chǎn)者-消費(fèi)者問題,,多個(gè)緩沖區(qū)的生產(chǎn)者和消費(fèi)者,P：i = 0;while (t

16、rue) { 生產(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); 消費(fèi)產(chǎn)品; j = (j+1) % n; };,【思考題】要不要對(duì)緩沖區(qū)（臨界資源）進(jìn)行互斥操作？,Q：

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

18、uffer [i]放產(chǎn)品; V(mutex); V(S2); i = (i+1) % n; };,有錯(cuò)誤？若顛倒兩個(gè)P操作的順序？,Q： j = 0; while (true) { P(S2); P(mutex); 從Buffer[j]取產(chǎn)品; j = (j+1) % n; V(mutex); V(S1); 消費(fèi)產(chǎn)品;};,n個(gè)緩

19、沖區(qū)、m個(gè)生產(chǎn)者和k個(gè)消費(fèi)者,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); };,正確,P.V操作討論1) 信號(hào)量的物理含義：S>0表示有S個(gè)資源可用S=0表示無資源可用S<0則| S |表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)

20、P(S):表示申請(qǐng)一個(gè)資源 V(S)表示釋放一個(gè)資源。信號(hào)量的初值應(yīng)該大于等于0,2) P.V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)如果P(S1)和P(S2)兩個(gè)操作在一起，那么P操作的順序至關(guān)重要,一個(gè)同步P操作與一個(gè)互斥P操作在一起時(shí)同步P操作在互斥P操作前而兩個(gè)V操作無關(guān)緊要,3）P.V操作的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：簡單，而且表達(dá)能力強(qiáng)（用P.V

21、操作可解決任何同步互斥問題）缺點(diǎn)：不夠安全；P.V操作使用不當(dāng)會(huì)出現(xiàn)死鎖；遇到復(fù)雜同步互斥問題時(shí)實(shí)現(xiàn)復(fù)雜,當(dāng)同時(shí)需要多種資源時(shí)怎么辦?,單個(gè)信號(hào)量使用很不方便，容易產(chǎn)生混亂,且前面已經(jīng)提到對(duì)多個(gè)信號(hào)量進(jìn)行P操作時(shí),如果順序稍有差錯(cuò)會(huì)導(dǎo)致錯(cuò)誤發(fā)生，因此可以采用信號(hào)量集的方法,信號(hào)量集——AND型信號(hào)量集,AND型信號(hào)量集是指同時(shí)需要多種資源且每種占用一個(gè)時(shí)的信號(hào)量操作 AND型信號(hào)量集的基本思想：在一個(gè)原語中申請(qǐng)整段代碼需要的多個(gè)

22、臨界資源，要么全部分配給它，要么一個(gè)都不分配AND型信號(hào)量集P原語為SwaitAND型信號(hào)量集V原語為Ssignal,Swait(S1, S2, …, Sn)//P原語；{while (TRUE) {if (S1 >=1 && S2 >= 1 && … && Sn >= 1){//滿足資源要求時(shí)的處理； for (i = 1; i <= n

23、; ++i) -–Si; //注：與P的處理不同，這里是在確信可滿足 // 資源要求時(shí)，才進(jìn)行減1操作；break;}else {//某些資源不夠時(shí)的處理； 調(diào)用進(jìn)程進(jìn)入第一個(gè)小于1信號(hào)量的等待隊(duì)列Sj.queue; 阻塞調(diào)用進(jìn)程; }}},Ssignal(S1, S2, …, Sn){for (i = 1; i <= n; ++i) { ++Si;//釋放占用

24、的資源； for (在Si.queue中等待的每一個(gè)進(jìn)程P) //檢查每種資源的等待隊(duì)列的所有進(jìn)程； { 從等待隊(duì)列Si.queue中取出進(jìn)程P;,if (判斷進(jìn)程P是否通過Swait中的測(cè)試) //注：與signal不同，這里要進(jìn)行重新判斷； {//通過檢查（資源夠用）時(shí)的處理； 進(jìn)程P進(jìn)入就緒隊(duì)列; } else {//未通過檢查（

25、資源不夠用）時(shí)的處理； 進(jìn)程P進(jìn)入某等待隊(duì)列； } } }},一般“信號(hào)量集”,一般信號(hào)量集是指同時(shí)需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個(gè)臨界值時(shí)的信號(hào)量處理 一般信號(hào)量集的基本思路就是在AND型信號(hào)量集的基礎(chǔ)上進(jìn)行擴(kuò)充，在一次原語操作中完成所有的資源申請(qǐng),進(jìn)程對(duì)信號(hào)量Si的測(cè)試值為ti（表示信號(hào)量的判斷條件，要求Si >= ti；即當(dāng)資源數(shù)量低于ti時(shí)，便不予分配）占

26、用值為di（表示資源的申請(qǐng)量，即Si = Si - di）對(duì)應(yīng)的P、V原語格式為：Swait(S1, t1, d1; ...; Sn, tn, dn);Ssignal(S1, d1; ...; Sn, dn);,一般“信號(hào)量集”可以用于各種情況的資源分配和釋放，幾種特殊情況：,Swait(S, d, d)表示每次申請(qǐng)d個(gè)資源，當(dāng)少于d個(gè)時(shí)，便不分配Swait(S, 1, 1)表示互斥信號(hào)量Swait(S, 1, 0)可作為一

27、個(gè)可控開關(guān)（當(dāng)S?1時(shí)，允許多個(gè)進(jìn)程進(jìn)入臨界區(qū)；當(dāng)S=0時(shí)，禁止任何進(jìn)程進(jìn)入臨界區(qū)）,,【思考題】,1.用P.V操作解決下圖之同步問題:,,,,,,,,get,copy,put,f,s,t,g,用P.V操作解決司機(jī)與售票員的問題,5.2.2 IPC經(jīng)典問題,1.讀者寫者問題 有兩組并發(fā)進(jìn)程: 讀者和寫者,共享一組數(shù)據(jù)區(qū) 要求： 允許多個(gè)讀者同時(shí)執(zhí)行讀操作 不允許讀者、寫者同時(shí)操作 不

28、允許多個(gè)寫者同時(shí)操作,第一類：讀者優(yōu)先,如果讀者來：1）無讀者、寫者，新讀者可以讀2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等如果寫者來：1）無讀者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待,,第一類讀者寫者問題的解法,讀者： while (true) { P(mutex); readcount ++;

29、if (readcount==1) P (w); V(mutex); 讀 P(mutex); readcount --; if (readcount==0) V(w); V(mutex); };,寫者： while (true) {

30、 P(w); 寫 V(w); };,第一類讀者寫者問題的解法（一般信號(hào)量集）,讀者：swait(wmutex,1,1; rcount,R,0);寫；ssignal(wmutex,1);,寫者：swait(rcount,1,1; wmutex,1,0);寫；ssignal(rcount,1);,2.哲學(xué)家就餐問題,有五個(gè)哲學(xué)

31、家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子 每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩只筷子，并且每個(gè)人只能直接從自己的左邊或右邊去取筷子,#define N 5 void philosopher (int i) { while (true) { 思考； 取fork[i]; 取fork[(i+1) % 5]； 進(jìn)食

32、； 放fork[i]; 放fork[(i+1) % 5]； }},為防止死鎖發(fā)生可采取的措施：最多允許4個(gè)哲學(xué)家同時(shí)坐在桌子周圍僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子（?）給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反之 為了避免死鎖，把哲學(xué)家分為三種狀態(tài)，思考，饑餓，進(jìn)食，并且一次拿到兩只筷子，否則不拿,,哲學(xué)家就餐問題解法（1）,#define N 5 void

33、 philosopher (int i) { while (true) { 思考； 取fork[i]; 取fork[(i+1) % 5]； 進(jìn)食； 放fork[i]; 放fork[(i+1) % 5]； }},,哲學(xué)家就餐問題解法（2）,#define N 5#define THINKING 0#define HUNGRY 1#define EATING

34、 2#typedef int semaphore;int state[N];semaphore mutex=1;semaphore s[N];,,void test(int i){ if (state[ i ] == HUNGRY) && (state [ (i-1) % 5] != EATING) && (state [ (i+1) %

35、 5] != EATING) { state[ i ] = EATING; V(&s[ i ]); } },,void philosopher (int i) { while (true) { 思考; P(&mutex); state[i] = HUNGRY

36、; test(i); V(&mutex); P(&s[i]); 拿左筷子； 拿右筷子； 進(jìn)食；,放左筷子； 放右筷子； P(&mutex) state[ i ] = THINKING； test([i-1] % 5); test([i+1] % 5);

37、 V(&mutex);}}state[ i ] = THINKINGs[ i ] = 0,【作業(yè)】,1. 推廣例子中的消息緩沖問題。 消息緩沖區(qū)為k個(gè)，有1個(gè)發(fā)送進(jìn)程， n個(gè)接收進(jìn)程，每個(gè)接收進(jìn)程對(duì)發(fā)送來的消息都必須取一次 若有m個(gè)發(fā)送進(jìn)程呢？,2.第二類讀者寫者問題：寫者優(yōu)先條件：1）多個(gè)讀者可以同時(shí)進(jìn)行讀2）寫者必須互斥（只允許一個(gè)寫者寫，也不能讀者寫者同時(shí)進(jìn)行）3）寫者優(yōu)先于讀者（一旦有

38、寫者，則后續(xù)讀者必須等待，喚醒時(shí)優(yōu)先考慮寫者）,3.有一個(gè)系統(tǒng)，定義P、V操作如下：P(s): s:=s-1; if s<0 then 將本進(jìn)程插入相應(yīng)隊(duì)列末尾等待；V(s)： s:=s+1; if s<=0 then 從相應(yīng)等待隊(duì)列隊(duì)尾喚醒一個(gè)進(jìn)程，將其插入就緒隊(duì)列；,問題：1）這樣定義P、V操作是否有問題？2）用這樣的P、V操

39、作實(shí)現(xiàn)N個(gè)進(jìn)程競(jìng)爭使用某一共享變量的互斥機(jī)制。3）對(duì)于2）的解法，有無效率更高的方法。如有，試問降低了多少復(fù)雜性？,4.理發(fā)師睡覺問題 理發(fā)店里有一位理發(fā)師，一把理發(fā)椅和N把供等候理發(fā)的顧客坐的椅子 如果沒有顧客,則理發(fā)師便在理發(fā)椅上睡覺。當(dāng)一個(gè)顧客到來時(shí)，他必須先喚醒理發(fā)師如果顧客到來時(shí)理發(fā)師正在理發(fā)，則如果有空椅子，可坐下來等；否則離開,5.3 進(jìn)程通信,概述消息緩沖通信方式,5.3.1 概述,P.V操作實(shí)現(xiàn)的是進(jìn)程之

40、間的低級(jí)通訊，所以P.V為低級(jí)通訊原語。它只能傳遞簡單的信號(hào)，不能傳遞交換大量信息如果要在進(jìn)程間傳遞大量信息則要用Send / Receive原語（高級(jí)通訊原語）,進(jìn)程通信的方式共享內(nèi)存： 相互通信的進(jìn)程間設(shè)有公共內(nèi)存，一組進(jìn)程向該公共內(nèi)存中寫，另一組進(jìn)程從公共內(nèi)存中讀，通過這種方式實(shí)現(xiàn)兩組進(jìn)程間的信息交換這種通信模式需要解決兩個(gè)問題？,消息傳遞：系統(tǒng)為進(jìn)程提供了兩個(gè)高級(jí)通訊原語send和receive send：

41、當(dāng)要進(jìn)行消息傳遞時(shí)執(zhí)行send receive：當(dāng)接收者要接收消息時(shí)執(zhí)行receive,共享文件模式：,管道通信,消息傳遞模式,消息緩沖 在內(nèi)存中開設(shè)緩沖區(qū)，發(fā)送進(jìn)程將消息送入緩沖區(qū)，接收進(jìn)程接收傳遞來的緩沖區(qū)信箱通信,直接方式：,發(fā)送進(jìn)程發(fā)消息時(shí)要指定接收進(jìn)程的名字， 反過來，接收時(shí)要指明發(fā)送進(jìn)程的名字 Send(receiver,message) Receiver(sender,message)* 對(duì)稱

42、形式：一對(duì)一* 非對(duì)稱形式：多對(duì)一 （顧客/服務(wù)員）有緩沖（有界，無界），無緩沖,間接方式：,發(fā)送進(jìn)程發(fā)消息時(shí)不指定接收進(jìn)程的名字，而是指定一個(gè)中間媒介，即信箱。進(jìn)程間通過信箱實(shí)現(xiàn)通信 發(fā)送原語：send(MB,Message) 接收原語：receive(MB,Message),5.3.2 消息緩沖,（有界緩沖區(qū)原理）： 在操作系統(tǒng)空間設(shè)置一組緩沖區(qū)，當(dāng)發(fā)送進(jìn)程需要發(fā)送消息時(shí)，執(zhí)行send系統(tǒng)調(diào)用，產(chǎn)生自愿性中斷，進(jìn)

43、入操作系統(tǒng)，操作系統(tǒng)為發(fā)送進(jìn)程分配一個(gè)空緩沖區(qū)，并將所發(fā)送的消息從發(fā)送進(jìn)程copy到緩沖區(qū)中，然后將該載有消息的緩沖區(qū)連接到接收進(jìn)程的消息鏈鏈尾，如此就完成了發(fā)送過程。發(fā)送進(jìn)程返回到用戶態(tài)繼續(xù)執(zhí)行,5.3.2 消息緩沖（續(xù)1）,（有界緩沖區(qū)原理）： 在以后某個(gè)時(shí)刻，當(dāng)接收進(jìn)程執(zhí)行到receive接收原語時(shí)，也產(chǎn)生自愿性中斷進(jìn)入操作系統(tǒng)，由操作系統(tǒng)將載有消息的緩沖區(qū)從消息鏈中取出，并把消息內(nèi)容copy到接收進(jìn)程空間，之后收回緩沖區(qū)，如

44、此就完成了消息的接收，接收進(jìn)程返回到用戶態(tài)繼續(xù)進(jìn)行,PCB,......Send(R, M)......SIZE:消息長度TEXT:消息正文,......消息鏈指針......,......Receive(pid, N)......SIZE:消息長度TEXT:消息正文......,M:,N:,接受進(jìn)程 R,發(fā)送進(jìn)程 S,,,,,,消息緩沖區(qū)結(jié)構(gòu)： 消息長度 消息正文 發(fā)送者 消息隊(duì)

45、列指針,用P.V操作來實(shí)現(xiàn)Send原語:Send（R，M） P(m-mutex);Begin 把緩沖區(qū)掛到接收進(jìn)程 根據(jù)R找接收進(jìn)程， 的消息鏈鏈尾; 如果沒找到出錯(cuò)返回; V(m-mutex); 申請(qǐng)空緩沖區(qū)P（s-b）； V(s-m); P(b-mutex); END

46、 摘空緩沖區(qū); V(b-mutex); 把消息從M處copy到空緩沖區(qū);其中s-b初值:n ;s-m初值:0,5.3.3 信箱通信,信箱組成信箱說明 與 信箱體可存放信件數(shù)，已存放信件數(shù)，指針信箱使用規(guī)則 若發(fā)送信件時(shí)信箱已滿，則發(fā)送進(jìn)程被置為“等信箱”狀態(tài)，直到信箱有空時(shí)才被釋放若取信件時(shí)信箱中無信，則接收進(jìn)程被置為“等信件”狀態(tài)，直到有信件時(shí)才被釋放,5.3.3 信箱通信（續(xù)1）,Send實(shí)現(xiàn)s

47、end（N，M）：把信件M送到指定的信箱N中步驟：查找指定信箱N；若信箱未滿，則把信件M送入信箱且釋放“等信件”者；若信箱已滿置發(fā)送信件進(jìn)程為“等信箱”狀態(tài)；,5.3.3 信箱通信（續(xù)2）,Receive實(shí)現(xiàn)receive（N，X）：從指定信箱N中取出一封信，存放到指定的地址X中步驟：查找指定信箱N；若信箱中有信，則取出一封信存于X中且釋放“等信箱”者；若信箱中無信件則置接收信件進(jìn)程“等信件”狀態(tài)；,5.3.3 信箱通

48、信（續(xù)3）,應(yīng)用實(shí)例磁盤管理進(jìn)程：從信箱中收取信件，處理，啟動(dòng)磁盤工作 其他進(jìn)程：要求訪問磁盤，向磁盤管理進(jìn)程發(fā)一封信作業(yè)： 用進(jìn)程通信的辦法解決生產(chǎn)者消費(fèi)者問題,5.3.4 管道通信方式 Pipe 也稱共享文件方式，基于文件系統(tǒng)，利用一個(gè)打開的共享文件連接兩個(gè)相互通信的進(jìn)程，文件作為緩沖傳輸介質(zhì),5.4 線程的基本概念,線程的引入線程與進(jìn)程的對(duì)比線程的實(shí)現(xiàn)實(shí)例：Solaris,5.4.1 線程的引

49、入,進(jìn)程的兩個(gè)基本屬性：資源的擁有者： 給每個(gè)進(jìn)程分配一虛擬地址空間，保存進(jìn)程映像，控制一些資源（文件，I/O設(shè)備），有狀態(tài)、優(yōu)先級(jí)、調(diào)度調(diào)度單位： 進(jìn)程是一個(gè)執(zhí)行軌跡 以上兩個(gè)屬性構(gòu)成進(jìn)程并發(fā)執(zhí)行的基礎(chǔ),5.4.1 線程的引入（續(xù)1）,系統(tǒng)必須完成的操作：創(chuàng)建進(jìn)程撤消進(jìn)程進(jìn)程切換缺點(diǎn)： 時(shí)間空間開銷大，限制并發(fā)度的提高,5.4.1 線程的引入（續(xù)2）,在操作系統(tǒng)中，進(jìn)程的引入提高了計(jì)算機(jī)資源的利用

50、效率。但在進(jìn)一步提高進(jìn)程的并發(fā)性時(shí)，人們發(fā)現(xiàn)進(jìn)程切換開銷占的比重越來越大，同時(shí)進(jìn)程間通信的效率也受到限制線程的引入正是為了簡化進(jìn)程間的通信，以小的開銷來提高進(jìn)程內(nèi)的并發(fā)程度,5.4.1 線程的引入（續(xù)3）,線程：有時(shí)稱輕量級(jí)進(jìn)程 進(jìn)程中的一個(gè)運(yùn)行實(shí)體 是一個(gè)CPU調(diào)度單位 資源的擁有者還是進(jìn)程或稱任務(wù)將原來進(jìn)程的兩個(gè)屬性分開處理,5.4.1 線程的引入（續(xù)4）,線程：有執(zhí)行狀態(tài)（狀態(tài)轉(zhuǎn)換）不運(yùn)行時(shí)保存上

51、下文有一個(gè)執(zhí)行棧有一些局部變量的靜態(tài)存儲(chǔ)可存取所在進(jìn)程的內(nèi)存和其他資源可以創(chuàng)建、撤消另一個(gè)線程,線程和進(jìn)程：單進(jìn)程、單線程單進(jìn)程、多線程多進(jìn)程、一個(gè)進(jìn)程一個(gè)線程多進(jìn)程、一個(gè)進(jìn)程多個(gè)線程,引入線程的好處：,創(chuàng)建一個(gè)新線程花費(fèi)時(shí)間少（結(jié)束亦如此）兩個(gè)線程的切換花費(fèi)時(shí)間少 （如果機(jī)器設(shè)有“存儲(chǔ)[恢復(fù)]所有寄存器”指令，則整個(gè)切換過程用幾條指令即可完成）因?yàn)橥贿M(jìn)程內(nèi)的線程共享內(nèi)存和文件，因此它們之間相互通信無須調(diào)用內(nèi)核

52、適合多處理機(jī)系統(tǒng),例子1：,LAN中的一個(gè)文件服務(wù)器，在一段時(shí)間內(nèi)需要處理幾個(gè)文件請(qǐng)求因此有效的方法是：為每一個(gè)請(qǐng)求創(chuàng)建一個(gè)線程在一個(gè)SMP機(jī)器上：多個(gè)線程可以同時(shí)在不同的處理器上運(yùn)行,例子2：,一個(gè)線程顯示菜單，并讀入用戶輸入；另一個(gè)線程執(zhí)行用戶命令考慮一個(gè)應(yīng)用：由幾個(gè)獨(dú)立部分組成，這幾個(gè)部分不需要順序執(zhí)行，則每個(gè)部分可以以線程方式實(shí)現(xiàn)當(dāng)一個(gè)線程因I/O阻塞時(shí)，可以切換到同一應(yīng)用的另一個(gè)線程,5.4.2 線程與進(jìn)程的比較

53、,調(diào)度并發(fā)性擁有資源系統(tǒng)開銷,5.4.3 線程的實(shí)現(xiàn)機(jī)制,用戶級(jí)線程核心級(jí)線程兩者結(jié)合方法,一、用戶級(jí)線程（User Level Thread）,由應(yīng)用程序完成所有線程的管理 通過線程庫(用戶空間) 一組管理線程的過程核心不知道線程的存在線程切換不需要核心態(tài)特權(quán)調(diào)度是應(yīng)用特定的,線程庫,創(chuàng)建、撤消線程在線程之間傳遞消息和數(shù)據(jù)調(diào)度線程執(zhí)行保護(hù)和恢復(fù)線程上下文,對(duì)用戶級(jí)線程的核心活動(dòng),核心不知道線程的活動(dòng)，

54、但仍然管理線程的進(jìn)程的活動(dòng)當(dāng)線程調(diào)用系統(tǒng)調(diào)用時(shí)，整個(gè)進(jìn)程阻塞但對(duì)線程庫來說，線程仍然是運(yùn)行狀態(tài) 即線程狀態(tài)是與進(jìn)程狀態(tài)獨(dú)立的,用戶級(jí)線程的優(yōu)點(diǎn)和缺點(diǎn),優(yōu)點(diǎn)：線程切換不調(diào)用核心調(diào)度是應(yīng)用程序特定的：可以選擇最好的算法ULT可運(yùn)行在任何操作系統(tǒng)上（只需要線程庫）缺點(diǎn)：大多數(shù)系統(tǒng)調(diào)用是阻塞的，因此核心阻塞進(jìn)程，故進(jìn)程中所有線程將被阻塞核心只將處理器分配給進(jìn)程，同一進(jìn)程中的兩個(gè)線程不能同時(shí)運(yùn)行于兩個(gè)處理器上,二、核心級(jí)線程（

55、KLT）,所有線程管理由核心完成沒有線程庫，但對(duì)核心線程工具提供API核心維護(hù)進(jìn)程和線程的上下文線程之間的切換需要核心支持以線程為基礎(chǔ)進(jìn)行調(diào)度例子：Windows NT，OS/2,核心級(jí)線程的優(yōu)點(diǎn)和缺點(diǎn),優(yōu)點(diǎn)：對(duì)多處理器，核心可以同時(shí)調(diào)度同一進(jìn)程的多個(gè)線程阻塞是在線程一級(jí)完成核心例程是多線程的缺點(diǎn)：在同一進(jìn)程內(nèi)的線程切換調(diào)用內(nèi)核，導(dǎo)致速度下降,三、兩者分析,針對(duì)不同的操作系統(tǒng)開銷和性能（線程的調(diào)度和切換速度）系統(tǒng)

56、調(diào)用（阻塞）線程執(zhí)行時(shí)間靈活性可擴(kuò)充性搶占CPU共享進(jìn)程的資源,四、ULT和KLT結(jié)合方法,線程創(chuàng)建在用戶空間完成大量線程調(diào)度和同步在用戶空間完成程序員可以調(diào)整KLT的數(shù)量可以取兩者中最好的例子：Solaris,5.4.4 實(shí)例：Solaris,進(jìn)程：用戶地址空間用戶棧進(jìn)程控制塊,實(shí)例：Solaris（續(xù)1）,用戶級(jí)線程（線程庫）： 可在應(yīng)用進(jìn)程中建立多個(gè)ULT 每個(gè)ULT需要：棧、程序計(jì)數(shù)器

57、不受調(diào)度程序的調(diào)度，線程切換快 對(duì)操作系統(tǒng)不可見 提供應(yīng)用程序并行性接口,實(shí)例：Solaris（續(xù)2）,核心級(jí)線程： 設(shè)置了大量KLT 有一個(gè)小的數(shù)據(jù)結(jié)構(gòu)和棧 完成內(nèi)核的所有工作 調(diào)度處理器的單位，其結(jié)構(gòu)由核心維護(hù),實(shí)例：Solaris（續(xù)3）,輕型進(jìn)程（LWP）： 每個(gè)ULT利用LWP與內(nèi)核通信 每個(gè)LWP支持一個(gè)或多個(gè)用戶級(jí)線程，并映射到一個(gè)核心級(jí)線程 每個(gè)LWP對(duì)應(yīng)用程序可見

58、，內(nèi)核看到的是多個(gè)LWP而看不到ULT,Solaris：,如果邏輯并行性不需要硬件并行性的支持，則可使用ULT 例子：多個(gè)窗口，任一時(shí)刻只有一個(gè)窗口是活躍的 如果內(nèi)核級(jí)線程可能被阻塞，則可以指定兩個(gè)或多個(gè)LWP，避免整個(gè)應(yīng)用程序的阻塞,線程與進(jìn)程的關(guān)系,1:1,每一執(zhí)行的線程是有自己的地址空間和資源的唯一進(jìn)程.,各種UNIX版本,M:1,進(jìn)程定義了所擁有的地址空間和動(dòng)態(tài)資源。在該進(jìn)程中多個(gè)線程可被創(chuàng)建和執(zhí)行.,Wi