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

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

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

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

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

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

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

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

8、turn: true P進入臨界區(qū) false Q進入臨界區(qū) ....P: while (not turn); 臨界區(qū) turn = false;Q: while (turn); 臨界區(qū) turn = true;,,,,,軟件解法的缺點： 1. 忙等待 2. 實現(xiàn)過于復雜，需要高的編程技巧,硬件解法 (1) “測試并設置”指令,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) “開關中斷”指令,進入臨界區(qū)前執(zhí)行： 執(zhí)行“關中斷”指令離開臨界區(qū)后執(zhí)行： 執(zhí)行“開中斷”指令,5.2 進程的同步機制──信號量及P.V操作（解決進程同步與互斥）5.2.1概念,同步機制： 信號量及P、V操作；管程；條件臨界域；路徑

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

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

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

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

15、 P(s2); P(s1) ; 從緩沖區(qū)取產(chǎn)品; 送產(chǎn)品到緩沖區(qū); V(s1); V(s2); 消費產(chǎn)品;}; };,單緩沖區(qū)生產(chǎn)者-消費者問題,,多個緩沖區(qū)的生產(chǎn)者和消費者,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); 消費產(chǎn)品; j = (j+1) % n; };,【思考題】要不要對緩沖區(qū)（臨界資源）進行互斥操作？,Q：

17、 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); 往B

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

19、沖區(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); };,正確,P.V操作討論1) 信號量的物理含義：S>0表示有S個資源可用S=0表示無資源可用S<0則| S |表示S等待隊列中的進程個數(shù)

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

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

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

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

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

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

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

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

28、允許多個寫者同時操作,第一類：讀者優(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); };,第一類讀者寫者問題的解法（一般信號量集）,讀者：swait(wmutex,1,1; rcount,R,0);寫；ssignal(wmutex,1);,寫者：swait(rcount,1,1; wmutex,1,0);寫；ssignal(rcount,1);,2.哲學家就餐問題,有五個哲學

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

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

33、 philosopher (int i) { while (true) { 思考； 取fork[i]; 取fork[(i+1) % 5]； 進食； 放fork[i]; 放fork[(i+1) % 5]； }},,哲學家就餐問題解法（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]); 拿左筷子； 拿右筷子； 進食；,放左筷子； 放右筷子； 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個，有1個發(fā)送進程， n個接收進程，每個接收進程對發(fā)送來的消息都必須取一次 若有m個發(fā)送進程呢？,2.第二類讀者寫者問題：寫者優(yōu)先條件：1）多個讀者可以同時進行讀2）寫者必須互斥（只允許一個寫者寫，也不能讀者寫者同時進行）3）寫者優(yōu)先于讀者（一旦有

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

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

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

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

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

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

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

45、列指針,用P.V操作來實現(xiàn)Send原語:Send（R，M） P(m-mutex);Begin 把緩沖區(qū)掛到接收進程 根據(jù)R找接收進程， 的消息鏈鏈尾; 如果沒找到出錯返回; V(m-mutex); 申請空緩沖區(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ā)送信件時信箱已滿，則發(fā)送進程被置為“等信箱”狀態(tài)，直到信箱有空時才被釋放若取信件時信箱中無信，則接收進程被置為“等信件”狀態(tài)，直到有信件時才被釋放,5.3.3 信箱通信（續(xù)1）,Send實現(xiàn)s

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

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

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

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

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

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

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

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

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

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

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

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