os課件第二章進(jìn)程管理2.4-2

1、第二章 進(jìn)程管理 Process Management 在傳統(tǒng)的操作系統(tǒng)中，作為資源分配和獨(dú)立運(yùn)行的基本單位是進(jìn)程。OS所具有的四大特征也都是基于進(jìn)程而形成的。 本章主要內(nèi)容 進(jìn)程的基本概念 進(jìn)程控制 進(jìn)程同步 經(jīng)典進(jìn)程同步問題 管程機(jī)制 進(jìn)程通信 線程2.4 經(jīng)典進(jìn)程同步問題 Classical process synchronization problem一、生產(chǎn)者-消費(fèi)者問題(producer and consumer problem)1 問題描述：若干進(jìn)程通過有限的共享緩沖區(qū)（緩沖池）交換數(shù)據(jù)。“生產(chǎn)者”進(jìn)程不斷將信息放入緩沖區(qū);“消費(fèi)者”進(jìn)程不斷從緩沖區(qū)中取出信息；共享緩沖區(qū)共有N個

2、；任何時刻只能有一個進(jìn)程可對共享緩沖區(qū)進(jìn)行操作。設(shè)緩沖池為循環(huán)存儲結(jié)構(gòu)供應(yīng)方向使用方向主要考慮的問題： 緩沖區(qū)滿或空； 競爭條件。注 意： 1）緩沖池不滿就可放入，不空就可取出； 2）不允許消費(fèi)者到空緩沖中取消息（判空，則阻塞）； 3）不允許生產(chǎn)者向滿緩沖中放消息（判滿，則阻塞）； 4）對緩沖池的操作要求互斥。 (2)(3)要求同步，需設(shè)置私有信號量: empty生產(chǎn)者進(jìn)程的私用信號量（初值為n)； full消費(fèi)者進(jìn)程的私用信號量（初值為0） (4)要求互斥，設(shè)置公用信號量 mutex保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間的互斥（初值為1）。 2 執(zhí)行過程：生產(chǎn)者消費(fèi)者動畫演示（1）生產(chǎn)者消費(fèi)者動畫演

3、示（2）生產(chǎn)者消費(fèi)者動畫演示（3）生產(chǎn)者消費(fèi)者動畫演示（4）produce(data)；Begin wait(empty); wait(mutex); 送數(shù)據(jù)入緩沖區(qū)單元 Signal(mutex)； Signal(full);End；consume(data)；Begin wait(full); Wait(mutex); 消費(fèi)； signal(mutex); Signal(empty)；End；各生產(chǎn)者進(jìn)程使用的過程produce (data)各消費(fèi)者使用的過程consume (data)可描述如下：注：一般說來：singal原語是釋放資源的，可以任意順序出現(xiàn)，wait原語不然，如果次序混亂

4、將造成死鎖。設(shè)有n個緩沖區(qū)，為實(shí)現(xiàn)對緩沖池的互斥操作：互斥信號量mutex；資源信號量empty表示空緩沖的個數(shù)，full表示滿緩沖的個數(shù)； 定義數(shù)組buffer 表示緩沖區(qū)。 輸入指針in指示下一個可放消息的緩沖區(qū)；輸出指針out指示下一個可取消息的緩沖區(qū)。var mutex,empty,full：semaphore ：1，n，0； buffer：array0，n-1 of item; in , out : integer：=0，0；3 生產(chǎn)者消費(fèi)者問題完整描述：parbegin producer:begin repeat producer an item in nextp; wait(em

5、pty); wait(mutex) ; buffer(in):=nextp; in:=(in+1) mod n; signal(mutex); signal(full) ; until false; endconsumer: begin repeat wait(full) ; wait(mutex); nextc:=buffer(out); out:=(out+1) mod n; signal(mutex); signal(empty); until false; endParend1）wait(mutex)和signal(mutex)必成對出現(xiàn)2）empty和full的wait和signal

6、操作也必成對出現(xiàn)，但是在不同的進(jìn)程中。3）wait原語順序不能顛倒，signal原語順序可任意。思考： P82習(xí)題23、24 注 意：4 利用AND信號量解決parbegin producer:begin repeat producer an item in nextp; Swait(empty,mutex); buffer(in):=nextp; in:=(in+1) mod n; Ssignal(mutex,full);until false; endconsumer: begin repeat Swait(full,mutex) ; nextc:=buffer(out); out:=(o

7、ut+1) mod n; Ssignal(mutex,empty); until false; endParend1 問題描述二、哲學(xué)家進(jìn)餐問題（Dining Philosopher Problem）？準(zhǔn)備進(jìn)餐進(jìn)餐準(zhǔn)備進(jìn)餐進(jìn)餐 五個哲學(xué)家，共用一張圓桌，五支筷子。 哲學(xué)家有兩種狀態(tài)：“思考”和“進(jìn)餐”。 進(jìn)餐時只能取靠近他的左右的筷子，而且拿到兩支時才可進(jìn)餐。完后，放下筷子繼續(xù)思考。 基本工作：思考，進(jìn)餐。 同步？ 互斥？ 臨界資源為筷子。一只筷子(編號為i) 一個互斥信號量 可定義一個信號量數(shù)組來描述五支筷子。 var chopstick:array0.4 of semaphore 所有信號

8、量初值為1， 2 利用記錄型信號量解決無有:=1, 1, 1, 1, 1;Var chopstick: array 0.4 of semaphore:=1, 1, 1, 1, 1; Begin Parbegin process i ( i=0, 1, 2, 3, 4): begin Repeat until false; end parendend哲學(xué)家進(jìn)餐活動可描述為： Think； wait(chopsticki)； wait(chopsticki+1 mod 5)； eat ； signal(chopsticki； signal(chopsticki+1 mod 5)；此算法有無問題？“

9、Dead-Lock” 1) 規(guī)定在拿到左筷子后，先檢查右筷子是否可用。若不可 用，則先放下左筷子，等一段時間再重復(fù)整個過程。 但該方法可能出現(xiàn)“饑餓”現(xiàn)象哲學(xué)家進(jìn)餐“死鎖”問題解決方法 2）至多允許四個人同時進(jìn)餐，保證至少一個能進(jìn)餐。 設(shè)一個信號量v，初值為4。 3）規(guī)定奇數(shù)號人先拿左筷子，后拿右筷子；偶數(shù)號人先拿右筷子，后拿左筷子。五個哲學(xué)家都先競爭奇數(shù)號筷子，獲得后再競爭偶數(shù)號筷子。最后總有一個哲學(xué)家能獲得兩只筷子。0123401234 4）用AND信號量機(jī)制可獲得最簡潔解法。var chopstick:array 0,4 of semaphore:=(1,1,1,1,1);process

10、 i repeat think; Swait(chopstick(i+1) mod 5,chopsticki); eat; Ssignal(chopstick(i+1) mod 5,chopsticki); until false; 哲學(xué)家問題對于多個競爭進(jìn)程互斥地訪問有限資源(如I/O設(shè)備)這一類問題的建模十分有用。 3 用AND信號量機(jī)制解決1 問題描述： 一個數(shù)據(jù)對象被多個進(jìn)程共享。其中有些進(jìn)程要求讀，另一些進(jìn)程要求寫或修改。要求讀的進(jìn)程稱為“reader進(jìn)程”；其它的稱為“writer進(jìn)程”。允許多個reader進(jìn)程同時執(zhí)行；不允許一個writer進(jìn)程和其它reader進(jìn)程或write

11、r進(jìn)程同時訪問共享對象。 a、多個reader可同時訪問這組共享數(shù)據(jù)并發(fā)； b、多個writer不可同時訪問這組共享數(shù)據(jù)互斥； c、reader與writer不可同時訪問這組共享數(shù)據(jù)互斥 它為數(shù)據(jù)庫訪問建立了一個模型。 三、讀者-寫者問題（Reader/Writer Problem）r1r2rnwRreadcount信號量設(shè)置 Wmutex：W/R和W/W的互斥。 Rmutex：讀者對readcount的互斥操作?？刂谱兞吭O(shè)置：Readcount 記錄讀的個數(shù)。來一個讀者：2 操作過程：申請Rmutex若readcount=0申請Wmutexreadcount+1 讀操作釋放Rmutex走一個

12、讀者：申請Rmutexreadcount1若readcount=0釋放Wmutex釋放Rmutexvar rmutex,wmutex:semaphore:=1,1 readcount:integer:=0;Parbegin reader: begin wait(rmutex) if readcount=0 then wait(wmutex) readcount:=readcount+1 signal(rmutex) 讀操作 wait(rmutex) readcount:=readcount-1 if readcount=0 then signal(wmutex) signal(rmutex)e

13、ndwriter:begin wait(wmutex) 寫操作 signal(wmutex) EndParend 讀者寫者問題描述問？若一個Writer進(jìn)程正在寫，則Reader進(jìn)程和其他Writer進(jìn)程的狀態(tài)和所執(zhí)行到的位置？本算法為讀者優(yōu)先算法，即當(dāng)讀者進(jìn)行讀時，寫者必須等待，直到所有讀者均離開，寫者才能進(jìn)入。存在的問題是什么？寫者優(yōu)先：如果一個讀者申請進(jìn)行讀操作時已有另一寫者在等待訪問共享資源，則該讀者必須等到?jīng)]有寫者處于等待狀態(tài)后才能開始讀操作。存在的問題是什么？公平策略：規(guī)則1：在一個讀序列中，若有寫者等待，則不允許新來讀者開始執(zhí)行。2：一個寫操作結(jié)束時，所有等待讀者應(yīng)比下一寫者有更

14、高優(yōu)先權(quán)。問：對于該公平策略，應(yīng)如何予以解決呢？var RN integer; L,mx:semaphore:=RN,1; begin parbegin reader: begin repeat Swait(L,1,1)； Swait(mx,1,0); perform read operation Ssignal(L,1); until false; endwriter:begin repeat Swait(mx,1,1;L,RN,0);perform write operation Ssignal(mx,1);until false;endparendend 信號量集機(jī)制解決讀者寫者問題四、

15、打瞌睡的理發(fā)師問題 理發(fā)店里有一位理發(fā)師，一把理發(fā)椅和N把供等候理發(fā)的顧客坐的椅子； 理發(fā)師為理發(fā)椅上的顧客理發(fā)，沒有顧客就在理發(fā)椅上睡覺； 第一個顧客到來，他必須先喚醒理發(fā)師； 如果顧客來時理發(fā)師正在忙，若有空椅子，則坐下來等；否則離開。1 問題描述：說 明：理發(fā)師和每位顧客都分別是一個進(jìn)程。理發(fā)師：看是否有顧客，若沒有，在理發(fā)椅上睡覺；否則，為等待最久的顧客服務(wù)，等待人數(shù)減1。顧客：先看有無空座位(等候的顧客數(shù)是否少于椅子數(shù))，若有則等，等待人數(shù)加1；若理發(fā)師正瞌睡，則將其喚醒；否則，離開。理發(fā)師和顧客的關(guān)系？變量waiting，用于記錄等候的顧客數(shù)，初值為0。由于它不是信號量，因此可對其

16、進(jìn)行增減等操作。設(shè)顧客座椅數(shù)（chairs）為常量5。同 步# define CHAIRS 5 /*為等待的顧客準(zhǔn)備的椅子數(shù)*/semaphore customers=0; /*等待服務(wù)的顧客數(shù)*/ semaphore barbers=0; /*等待顧客的理發(fā)師數(shù)*/ semaphore mutex=1; /*用于互斥*/ int waiting=0; /*等待的顧客(還沒理發(fā)的)*/ 三個信號量Customers：用來記錄等候理發(fā)的顧客數(shù)(不包括正在理發(fā)的顧客)，初值為0；Barbers：等候顧客的理發(fā)師數(shù)，初值為0；Mutex：用于對waiting 變量的互斥。信號量設(shè)置和變量定義Void

17、 customers(void) wait(mutex); /*互斥進(jìn)入臨界區(qū)*/ If(waiting0 表示有S個資源可用S=0 表示無資源可用S0 則| S |表示S等待隊(duì)列中的進(jìn)程個數(shù)P(S): 表示申請一個資源 V(S)： 表示釋放一個資源。信號量的初值應(yīng)該大于等于01 信號量的物理含義：當(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):優(yōu)點(diǎn)： 簡單，而且表達(dá)能力強(qiáng)（用P.V

18、操作可解決任何同步互斥問題）。缺點(diǎn)： 不夠安全；P.V操作使用不當(dāng)會出現(xiàn)死鎖；遇到復(fù)雜同步互斥問題時實(shí)現(xiàn)復(fù)雜。3 P.V操作的優(yōu)缺點(diǎn)2.5 管程機(jī)制 Monitor Mechanism 集中管理分散在進(jìn)程中的臨界段。 1971年，Dijkstra提出，為每一臨界資源設(shè)置一個“秘書”進(jìn)程。訪問該臨界資源的進(jìn)程都需先報告“秘書”，由“秘書”實(shí)現(xiàn)諸進(jìn)程的同步。Hoare(1974)和Hansen(1975)，根據(jù)抽象數(shù)據(jù)類型的原理發(fā)展為管程（Monitors）。 把并發(fā)進(jìn)程間的共享資源和操作，集中于相應(yīng)的管程中。 管程與信號量機(jī)制功能等價，且更容易控制。一、管程的定義（The definition

19、of monitor）1 定義：Hansan “代表共享資源的數(shù)據(jù)結(jié)構(gòu)及并發(fā)進(jìn)程在其上執(zhí)行的一組操作就構(gòu)成管程。這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)”。2.5.1 管程的基本概念The basic concepts of monitor 2 基本思想：把共享資源以及針對共享資源的所有操作集中在一個模塊中，可以函數(shù)庫的形式實(shí)現(xiàn)。被請求和釋放資源的進(jìn)程所調(diào)用。 1) 管程名稱； 2) 局部于管程的共享變量說明(臨界資源描述)； 3) 對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程（即對臨界資源進(jìn)行操作的部分)； 4) 對局部于管程的數(shù)據(jù)設(shè)置初始值的語句。二、 管程的組成（The Composition of Mo

20、nitor）The Grammar of Monitortype monitor-name=monitor variable declarations define ; use ； procedure P1(); beginend; procedure Pn(); beginend; begin initialization code end 1）安全性。管程的局部變量僅能由此管程的過程訪問；反之，局部于管程的過程也僅能訪問管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。 2）封裝性。任意時刻，共享資源的進(jìn)程可以通過調(diào)用管程內(nèi)的一個過程進(jìn)入管程，因此管程有很好的封裝性。 3）互斥性。任意時刻，管程中只能有一個活躍的進(jìn)程，其

21、他調(diào)用者必須等待直至管程可用。即，進(jìn)程互斥的調(diào)用管程中的過程。 4）模塊性。管程是一個基本程序單位，可以單獨(dú)編譯。三、管程的特性（ The peculiarity of monitor） 管程實(shí)現(xiàn)互斥調(diào)用是通過編譯器自動實(shí)現(xiàn)的。當(dāng)管程被編譯器編譯時，在進(jìn)程的程序中加上測試信號量的P、V操作實(shí)現(xiàn)。 P操作位置就是調(diào)用管程中某個過程的語句前面。 V操作的位置是在調(diào)用語句結(jié)束時。程序員設(shè)計進(jìn)程的程序時，不需要在進(jìn)程的程序中顯式加入。四、管程實(shí)現(xiàn)互斥和同步1、 互斥 管程的第三個特性，使他們能有效的完成互斥。2 同步管程實(shí)現(xiàn)同步，需設(shè)置： 條件變量x，表示等待原因，可根據(jù)需要設(shè)置多個。 利用wait和

22、signal操作表示因等待原因出現(xiàn)而等待、喚醒一個某原因而等待的進(jìn)程。 管程提供了一種實(shí)現(xiàn)互斥的簡便途徑，但這還不夠。需要一種辦法使得進(jìn)程在無法繼續(xù)運(yùn)行時被阻塞。 如在生產(chǎn)者消費(fèi)者問題中，當(dāng)生產(chǎn)者發(fā)現(xiàn)緩沖區(qū)滿的時候如何阻塞呢？ 設(shè)var x:condition，則可有 wait(x)因等待x而阻塞，直至其他進(jìn)程執(zhí)行signal(x)。 signal(x)喚醒一個因等待x而阻塞的進(jìn)程。 如果x等待隊(duì)列中無進(jìn)程阻塞，該操作不產(chǎn)生任何作用。（與信號量的signal不同） 如：因共享資源忙而進(jìn)程等待，條件變量可定義為：nobusy：condiction。 則wait為：wait(nobusy)，sig

23、nal 為：signal(nobusy)條件變量和相關(guān)操作Type SSU=monitor var busy : boolean; nobusy : condition; define require, return; use wait, signal；procedure require; begin if busy then wait(nobusy); /*調(diào)用進(jìn)程加入等待隊(duì)列*/ busy := ture； end;procedure return; begin busy := false； signal(nobusy); /*從等待隊(duì)列中釋放進(jìn)程*/end;begin /*管程變量初始化

24、*/ busy := false；end;例 如當(dāng)已進(jìn)入管程的一個進(jìn)程（P）喚醒另一個進(jìn)程(Q)時，為了避免管程中同時有兩個活躍進(jìn)程，P進(jìn)程在signal之后該怎么辦？Hoare采用Hansen建議問 題？處理方法有三種：等待，繼續(xù)，直到等待或退出。等待，繼續(xù)，直到退出或等待。規(guī)定P的signal操作只能作為管程的最后一條語句。兩者必須有一個退出或停止使用管程Java圖211管程示意圖EntranceQueue ofEnteringProcessesMonitior Waiting Area Condition c1C1.wait.condition cn.Cn.waitUrgent Queu

25、ecsignal ExitM0NITOR Local DataCondition VariablesProcedure 1Procedure kInitialization Code一、定義管程 首先建立管程名為PC，并定義其包含的兩個過程：1）put(item)為生產(chǎn)者放消息過程。count表示已有的消息數(shù)目。countn，表緩沖池已滿。生產(chǎn)者需等待。2）get(item)為消費(fèi)者取消息過程。 count0，表緩沖池已空，消費(fèi)者等待。PC管程的描述為：Type producer-consumer =monitor var in,out,count:integer; buffer:array0

26、,n-1 of item; notfull,notempty:condition; 2.5.2 利用管程解決生產(chǎn)者消費(fèi)者問題procedure entry put(item) begin if countn then wait(notfull) bufferin:=nextp in:=(in+1) mod n count:=count+1 if notempty.quene then signal(notempty) endprocedure entry get(item) begin if count0 then wait(notempty) nextc:=bufferout out:=(o

27、ut+1) mod n count:=count-1 if notfull.queue then signal(notfull) endbegin in:=out:=0; count:=0; endproducer:begin repeat produce an item in nextp PC.put(nextp) until falseend consumer:begin repeat PC.get(item) consume the item in nextc until falseend二、進(jìn)程調(diào)用管程PC : producer-consumer ; /*管程實(shí)例化*/通過互斥自動化，

28、管程比信號量更容易保證進(jìn)程執(zhí)行的正確性。但管程是一個編程語言概念，編譯器必須要識別管程并用某種方式對其互斥做出安排。C、Pascal以及多數(shù)其他語言都沒有管程，所以這些編譯器不能遵守互斥規(guī)則。語言中增加信號量較容易。向庫里加入兩段小的匯編代碼，以執(zhí)行wait和signal系統(tǒng)調(diào)用。編譯器可以不知道它們的存在，只要操作系統(tǒng)知道信號量存在，或有一個基于信號量的操作系統(tǒng)，用戶仍可使用C/C+編寫用戶程序，但是如果使用管程，讀者就需要一種帶有管程的語言。管程和信號量區(qū)別管程和信號量區(qū)別另外，管程和信號量機(jī)制都是設(shè)計用來解決訪問公共內(nèi)存的一個或多個CPU上的互斥問題。通過將信號量放在共享內(nèi)存中，用TSL

29、或XCHG指令來避免競爭。如果一個分布式系統(tǒng)具有多個CPU，且每個CPU擁有自己的私有內(nèi)存，通過一個局域網(wǎng)相連，那么這些原語將失效。結(jié)論：信號量太低級了，而管程在少數(shù)幾種編程語言之外又無法使用，并且，這些原語均未提供機(jī)器間的信息交換方法。所以還需要其他的方法。 信號量設(shè)置sp:semaphore； /* 盤子里可以放幾個水果 */sg1:semaphore； /* 盤子里有桔子 */sg2:semaphore； /* 盤子里有蘋果 */信號量初值 sp := 1; /* 盤子里允許放一個水果*/ sg1 := 0; /* 盤子里沒有桔子 */ sg2 := 0; /* 盤子里沒有蘋果*/voi

30、d reader() while(1)wait(queue);wait(Rmutex); if(0 = readcount)wait(mutex); readcount = readcount + 1;signal(rdcntmutex);signal(queue); read . wait(Rmutex); readcount = readcount - 1; if(0 = readcount)signal(mutex);signal(Rmutex); void writer() while(1)wait(Wmutex); if(0 =writecount)wait(queue); writ

31、ecount = writecount + 1;signal(Wmutex); wait(mutex); write .signal(mutex);wait(Wmutex); writecount = writecount - 1; if(0 = writecount)signal(queue); signal(Wmutex); semaphore mutex=1, Rmutex=1, Wmutex=1, queue=1;int readcount = 0, writecount = 0;Readers-Writers Problem: Writer FirstReaders-Writers

32、Problem: Writer FirstShared variable: semaphore rsem, wsem = 1; semaphore x,y,z = 1; int readcount, writecount = 0; while(1) wait(z); /用來保證寫者優(yōu)先 wait(rsem); /判斷有沒有寫進(jìn)程在臨界區(qū)，有則等待，否則拒絕新的寫進(jìn)程進(jìn)來 wait(x); /開始對readcount的互斥訪問 readcount+; /更新讀進(jìn)程數(shù)量 if (readcount=1) wait(wsem); /第一個讀進(jìn)程需要判斷是否有寫進(jìn)程在進(jìn)行寫操作，有的話需要等待，沒有的

33、話不讓寫進(jìn)程進(jìn)行新寫操作 signal(x); /結(jié)束對readcount的互斥訪問 signal(rsem); /歸還鎖，讓寫進(jìn)程可以進(jìn)臨界區(qū) signal(z); Void reader () Readers-Writers Problem: Writer First R doReading(); wait(x); /開始對readcount的互斥訪問 readcount-; /更新讀進(jìn)程數(shù)量 if (readcount=0) signal(wsem); /最后一個離開臨界區(qū)的讀進(jìn)程需要?dú)w還鎖，讓寫進(jìn)程可以進(jìn)行寫操作 signal(x); /結(jié)束對readcount的互斥訪問 Reader

34、s-Writers Problem: Writer First RReaders-Writers Problem: Writer First: Wvoid writer() while(1) wait(y); /開始對writecount的互斥訪問 writecount+; /更新寫進(jìn)程數(shù)量 if (writecount=1) wait(rsem); /第一個寫進(jìn)程需要判斷是否有讀進(jìn)程在臨界區(qū)，有的話需要等待，沒有的話不讓新的讀進(jìn)程進(jìn)來 signal(y); /結(jié)束對writecount的互斥訪問 wait(wsem); /限制同一時刻只能有一個寫進(jìn)程進(jìn)行寫操作 doWriting(); si

35、gnal(wsem); /結(jié)束對寫操作的限制 wait(y); /開始對writecount的互斥訪問 writecount-; /更新寫進(jìn)程數(shù)量 if (writecount=0) signal(rsem); /最后一個離開臨界區(qū)的寫進(jìn)程需要?dú)w還鎖，讓讀進(jìn)程可以進(jìn)臨界區(qū) signal(y); /結(jié)束對writecount的互斥訪問 Readers-Writers Problem: Writer First: W2.6 進(jìn)程通信Process Communication概念：進(jìn)程間的信息交換。實(shí)例：信號量機(jī)制（低級通信）缺點(diǎn)：（1）效率低；（2）通信對用戶不透明。高級通信特點(diǎn)：效率高；用戶利用

36、OS提供的通信命令進(jìn)行數(shù)據(jù)的傳輸；通信實(shí)現(xiàn)細(xì)節(jié)對用戶透明。高級通信機(jī)制可歸結(jié)為三大類： 共享存儲器系統(tǒng) (Shared-Memory System) 消息傳遞系統(tǒng)（Message Passing System) 管道通信（Pipe Communication)2.6.1 進(jìn)程通信的類型The type of process communication一、共享存儲器系統(tǒng)(Shared-Memory System)1.基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式producer-consumer中的緩沖區(qū)，低效，傳遞少量數(shù)據(jù)，不透明。低級通信2.基于共享存儲區(qū)的通信方式（UNIX中速度最高的）系統(tǒng)提供：在進(jìn)程通信軟

37、件包IPC中。通信過程：（1）向系統(tǒng)申請一個或多個內(nèi)存存儲區(qū)（2）獲得分區(qū)獲后即可讀/寫.特點(diǎn)：高效，速度快。 單機(jī)、多機(jī)系統(tǒng)、網(wǎng)絡(luò)中的主要進(jìn)程通信方式，進(jìn)程間的數(shù)據(jù)交換以消息（message）( “報文”)為單位。通過內(nèi)存中開設(shè)的緩沖區(qū)，進(jìn)行消息的傳遞。 用戶利用一組通信命令實(shí)現(xiàn)通信。根據(jù)實(shí)現(xiàn)方式的不同，可分為直接通信和間接通信。 直接通信方式（direct Communication way） 一般在一臺機(jī)器的多進(jìn)程間，直接以接收者進(jìn)程的內(nèi)部標(biāo)識為目的標(biāo)識發(fā)送消息。通常，系統(tǒng)提供下述兩條通信原語： Send(Receiver,message) ； .發(fā)送原語 Receive(Sender,

38、message) ； .接收原語二、消息傳遞系統(tǒng)（Message Passing System)直接通信實(shí)例消息緩沖隊(duì)列通信機(jī)制 圖示repeat produce an item in nextp; send(consumer, nextp); until false; repeat receive( producer, nextc); consumer the item in nextc; until false;例：消息傳遞方式解決生產(chǎn)消費(fèi)問題。1間接通信： 建立一個通信參與者共享的邏輯實(shí)體信箱，發(fā)送者向信箱發(fā)送消息；接收者到信箱取消息。用于聯(lián)系不十分緊密的進(jìn)程之間。 間接通信方式（Ind

39、irect Communication way）優(yōu)點(diǎn)：信箱可實(shí)現(xiàn)“實(shí)時”或“非實(shí)時”通信。在讀/寫時間上具有隨機(jī)性。共享的邏輯實(shí)體可以是操作系統(tǒng)在核心空間提供的一組數(shù)據(jù)結(jié)構(gòu)，也可以磁盤上的文件為基礎(chǔ)，其特點(diǎn)是不只屬于通信中的任意一方，而是一個中間實(shí)體。ABCDESendReceive2信箱：包含有多個消息的隊(duì)列。系統(tǒng)為信箱通信提供若干條原語，實(shí)現(xiàn)對信箱的管理。1）信箱的創(chuàng)建和撤消 進(jìn)程利用信箱創(chuàng)建原語建立一個新信箱。信箱頭和信箱體2）消息的發(fā)送與接收 Send(mailbox,message) Receive(mailbox,message)信箱頭（信箱名、口令）信格信格信格信格信格 信箱頭：

40、描述郵箱名、屬性、大小及擁有該郵箱的進(jìn)程名； 信箱體：存放消息。私用信箱(private mailbox) ：由用戶進(jìn)程自己創(chuàng)建，并作為該進(jìn)程的一部分。擁有者可從中讀，其它進(jìn)程只能向其中發(fā)送。擁有者進(jìn)程結(jié)束，信箱消失。 公用信箱(public mailbox) ：由OS創(chuàng)建，允許系統(tǒng)中所有核準(zhǔn)用戶讀、放。 共享信箱(shared mailbox) ：由某進(jìn)程創(chuàng)建，指明共享屬性及共享進(jìn)程名。創(chuàng)建者和共享者有權(quán)從信箱中取走消息。3）信箱分類 發(fā)送者進(jìn)程和接收者進(jìn)程之間的關(guān)系存在以下幾種。一對一：專用的通信鏈路，兩個進(jìn)程間建立私用的通信連接，不受其他進(jìn)程的干擾和影響。多對一：允許提供服務(wù)的進(jìn)程與多個

41、用戶進(jìn)程交互，多個向一個發(fā)信息。用于現(xiàn)代操作系統(tǒng) （客戶/服務(wù)器）一對多：一個發(fā)送者和多個接收者的通信關(guān)系。發(fā)送進(jìn)程可利用廣播形式，向接收者發(fā)送消息。多對多：如公用信箱，允許多個進(jìn)程都能象信箱中投遞消息，也可從信箱中取走屬于自己的消息。3間接通信的靈活性1 通信鏈路(communication link)：在發(fā)送進(jìn)程和接收進(jìn)程之間為信息傳送而建立的一條通路。1）建立方式 顯示建立：由發(fā)送進(jìn)程利用建立命令建立，用完后用刪除命令拆除。（網(wǎng)絡(luò)中） 隱式建立：利用發(fā)送命令（原語），系統(tǒng)自動建立。（單機(jī)中）消息傳遞中的幾個問題2）連接方式 點(diǎn)點(diǎn)連接：一條鏈路只有兩個結(jié)點(diǎn)。 多點(diǎn)連接：一條鏈路連接多個結(jié)點(diǎn)

42、。3）通信方向 單向：發(fā)送進(jìn)程 接收進(jìn)程。 雙向：進(jìn)程 進(jìn)程4）鏈路的容量無容量：鏈路上沒有緩沖區(qū)，不能暫存信息。有容量：鏈路上有緩沖區(qū)，能暫存信息。2 消息的格式 字符流：發(fā)送方發(fā)送的數(shù)據(jù)沒有一定的格式，接收方不需要保留各次發(fā)送之間的分界 報文： 是網(wǎng)絡(luò)環(huán)境下采用的消息格式。 報頭(header) ：包括數(shù)據(jù)傳輸時所需的控制信息。如發(fā)送進(jìn)程名，報文長度、數(shù)據(jù)類型、發(fā)送時間等。 正文( text)：消息內(nèi)容。分為定長和變長兩種。3 進(jìn)程同步方式 根據(jù)收發(fā)進(jìn)程在進(jìn)行收發(fā)操作時是否等待，同步方式分為兩種：阻塞方式和非阻塞方式。2接收進(jìn)程執(zhí)行完Receive命令后怎么辦？（1）阻塞自己直到收到發(fā)送進(jìn)

43、程的消息。稱為阻塞接收。（2）不要求進(jìn)程等待，當(dāng)需要信件時，去查找并接收信件，需要時再發(fā)送回答信件。稱為非阻塞接收。3. 常用的進(jìn)程間通信模式： 非阻塞發(fā)送、阻塞接收（應(yīng)用最廣泛的進(jìn)程同步方式） 非阻塞發(fā)送、非阻塞接收（較常見的方式。如具有緩沖隊(duì)列的生產(chǎn)者-消費(fèi)者同步） 阻塞發(fā)送，阻塞接收（發(fā)送進(jìn)程和接收進(jìn)程間無緩沖）1發(fā)送進(jìn)程執(zhí)行完Send命令后怎么辦？ （1）阻塞自己等接收者回信后才繼續(xù)向前執(zhí)行，稱為阻塞發(fā)送。 （2）發(fā)送完消息后不等回信繼續(xù)執(zhí)行，稱為不阻塞發(fā)送。 管道：利用一個打開的共享文件，連接兩個相互通信的進(jìn)程。進(jìn)程通過兩個命令利用該共享文件通信。一個命令向該文件中寫入數(shù)據(jù)，另一個命

44、令從文件中讀出數(shù)據(jù)。共享文件稱pipe文件。它以字符流方式進(jìn)行數(shù)據(jù)傳送。發(fā)送進(jìn)程接收進(jìn)程字符流方式寫入有個讀出先進(jìn)先出順序三、管道通信（Pipe Communication) unix系統(tǒng)中1）互斥：管道可看作是臨界資源。對管道的操作是互斥的。2）同步：當(dāng)寫進(jìn)程把一定數(shù)量數(shù)據(jù)寫入pipe后,便去等待，直到讀出進(jìn)程取走數(shù)據(jù)后，把它喚醒。反之亦然。3）對方是否存在：只有確定對方存在時，才可通信。管道通信機(jī)制應(yīng)能提供三方面的協(xié)調(diào)功能： 2、操作 write(fd1,buf,size) 功能：把buf中的長度為size字符的消息送入管道入口fd1 fd1pipe入口 read(fd0,buf,size

45、) fd0Pipe的出口功能：從pipe出口fd0讀出size字符的消息置入 buf中。1、定義#include intpipe(intfd2)；參數(shù)filedis返回兩個文件描述符：fd0為讀而打開，fd1為寫而打開。fd1的輸出是fd0的輸入。Pipe文件的定義和操作 首先由Hansan提出，并在RC4000系統(tǒng)上實(shí)現(xiàn)。在一個消息定長的簡單直接通信消息系統(tǒng)中，進(jìn)程間通過兩個基本操作進(jìn)行通信。 Send(A,a)：發(fā)送者用以發(fā)送消息。A為接收者標(biāo)識符,a為消息的發(fā)送區(qū)始址。 Receive(b)：接收者用以接收當(dāng)前已到達(dá)的消息。b為消息的接收區(qū)始址。若當(dāng)前無消息到達(dá)，則接收者進(jìn)入等待狀態(tài)直到

46、到達(dá)一個消息。2.6.2 消息緩沖隊(duì)列通信機(jī)制message buffer queue communication mechanism發(fā)送不阻塞，接收阻塞1）消息緩沖區(qū)： Type message buffer =record sender : 發(fā)送者進(jìn)程標(biāo)識符 size : 消息長度 text :消息正文 next : 指向下一個消息緩沖區(qū)的指針 end一、 數(shù)據(jù)結(jié)構(gòu) 為保證消息緩沖隊(duì)列的互斥，協(xié)調(diào)發(fā)送進(jìn)程和接收進(jìn)程的同步，在接收進(jìn)程的PCB中增加的有關(guān)數(shù)據(jù)項(xiàng)。 Type process control block =record mq : 消息隊(duì)列隊(duì)首指針 mutex : 消息隊(duì)列互斥信號

47、量，初值為1 sm : 消息隊(duì)列私有信號量，記錄消息個數(shù)，初值為0； end2）PCB中有關(guān)通信的數(shù)據(jù)項(xiàng) 互斥使用緩沖隊(duì)列，即發(fā)送進(jìn)程把消息寫入緩沖區(qū)、把緩沖區(qū)掛入消息隊(duì)列時，應(yīng)禁止其他進(jìn)程對該緩沖隊(duì)列的訪問，同理，當(dāng)接收進(jìn)程正從消息隊(duì)列中取消息時，應(yīng)禁止其他進(jìn)程對該隊(duì)列的訪問。應(yīng)設(shè)mutex-互斥信號量 消息緩沖隊(duì)列是按接收進(jìn)程排列，每個接收進(jìn)程擁有自己的消息隊(duì)列。因此同一時間存在多個消息隊(duì)列；且這些隊(duì)列長度不固定。 當(dāng)緩沖隊(duì)列無消息時，接收進(jìn)程不能接收到任何消息。Sm為接收進(jìn)程的私用信號量(初值為0)說 明A的PCB.Send(B, a).Sender:ASIZE:消息長度TEXT:消息正

48、文B的PCB. mq Mutex sm.Receive(b).Sender:ASIZE:消息長度TEXT:消息正文.發(fā)送區(qū)a:接收區(qū)b發(fā)送進(jìn)程 A消息消息.Sender:ASIZE:消息長度TEXT:消息正文接收進(jìn)程 BSend(receiver，m) Begin 向系統(tǒng)申請一個消息緩沖區(qū)； 把m送入新申請的消息緩沖區(qū)， wait(mutex); 把消息緩沖區(qū)掛入接收進(jìn)程的消息隊(duì)列。 signal(mutex); signal(Sm);End;Receive(n) Begin wait(Sm); Wait(mutex); 摘下消息隊(duì)列中的消息n， Signal(mutex); 將消息n從緩沖區(qū)

49、復(fù)制到接收區(qū)； 釋放緩沖區(qū)；End; 發(fā)送進(jìn)程是否可以發(fā)送消息，則取決于是否申請到緩沖區(qū)。具體見課本P70二、發(fā)送原語procedure send(receiver,a) begin getbuf(a.size,i) i.sender:=a.sender i.size:=a.size i.text:=a.text i.next:=0 getid(PCB.receiver.j) wait(j.mutex) insert(j.mq.I) signal(j.mutex) signal(j.sm) enda為發(fā)送進(jìn)程在自己的內(nèi)存空間中設(shè)置的一發(fā)送區(qū)。把消息正文、發(fā)送進(jìn)程標(biāo)識符、消息長度等信息填入a中。

50、根據(jù)a.size申請一緩沖區(qū)i，把a(bǔ)中信息復(fù)制到i中，獲得接收進(jìn)程的內(nèi)部標(biāo)識符j，將i掛在j.mq上。因?yàn)橄㈥?duì)列為臨界資源，對其操作要求互斥。三、 接收原語procedure receive(b) begin j:=internal name wait(j.sm) wait(j.mutex) remove(j.mq.i) signal(j.mutex) b.sender:=i.sender b.size:=i.size b.text:=i.text end接收進(jìn)程調(diào)用接收原語，在自己的消息緩沖隊(duì)列mq中，摘下第一個消息緩沖區(qū)（如i），將其復(fù)制到以b為首址的指定消息接收區(qū)內(nèi)。2.7 線 程 (

51、 Thread)一、線程的引入 (the introduction of thread) 進(jìn)程的兩個基本屬性：是構(gòu)成進(jìn)程并發(fā)執(zhí)行的基礎(chǔ)。 資源的擁有者：每個進(jìn)程分配PCB，保存進(jìn)程映像，控制一些資源，狀態(tài)、優(yōu)先級等。 調(diào)度/執(zhí)行：進(jìn)程是一個執(zhí)行軌跡，在一個時刻只能有一個執(zhí)行控制流。 2.7.1 線程的基本概念(The Basic Concept of Thread)創(chuàng)建進(jìn)程：分配整套資源。(分配PCB，分配除CPU之外的其他所需資源)撤消進(jìn)程：釋放整套資源。（回收資源，撤銷PCB）進(jìn)程切換：切換整套資源。（保留當(dāng)前進(jìn)程的PCB環(huán)境，設(shè)置新選中進(jìn)程的CPU環(huán)境）時間空間開銷大，限制并發(fā)度。 進(jìn)程

52、操作存在的問題： 缺點(diǎn)： 將原來進(jìn)程的兩個屬性（資源分配單位和運(yùn)行調(diào)度單位）分開處理。 資源擁有單元稱為進(jìn)程（或任務(wù)）； 調(diào)度的單位稱為線程。 線程定義：輕型進(jìn)程（LWP） 解決方案：引入線程 是進(jìn)程中的一個運(yùn)行實(shí)體，是CPU調(diào)度的基本單位。為了減少時空開銷，提高并發(fā)度，引入線程。 輕型實(shí)體。只擁有少量運(yùn)行中必不可省的資源。TCB、描述處理器工作情況的一組寄存器（程序計數(shù)器、狀態(tài)寄存器、通用寄存器等）、堆棧（核心棧和用戶棧）； 獨(dú)立調(diào)度的基本單位。線程的切換開銷小，速度快。 共享進(jìn)程資源。進(jìn)程只是資源的擁有者，進(jìn)程創(chuàng)建線程，一個進(jìn)程可包含多個線程，它們共享進(jìn)程擁有的資源。一個線程可創(chuàng)建和撤銷另

53、一個線程。 并發(fā)執(zhí)行。多個線程可并發(fā)執(zhí)行。 具有就緒、阻塞和執(zhí)行三種基本狀態(tài)。運(yùn)行中也呈現(xiàn)間斷性。二、線程屬性（The Attribute of thread）三、進(jìn)程和線程的比較1 線程與進(jìn)程的關(guān)系一個進(jìn)程可以有多個線程，線程只能在一個進(jìn)程的地址空間內(nèi)活動。資源分配給進(jìn)程。同一進(jìn)程的所有線程共享該進(jìn)程的所有資源。處理機(jī)分配給線程。真正在處理機(jī)上運(yùn)行的是線程。進(jìn)程的“執(zhí)行”狀態(tài)實(shí)際是進(jìn)程中某線程的執(zhí)行狀態(tài)。線程在執(zhí)行過程中需要協(xié)作同步，不同進(jìn)程的線程要利用消息通信的辦法實(shí)現(xiàn)同步。UserStackKernelStackUserAddressSpaceProcessControlBlockSin

54、gle-ThreadedProcess ModelUserStackThreadControlBlockKernelStackThreadMultithreaded Process ModelUserAddressSpaceProcessControlBlockThreadControlBlockUserStackKernelStackThreadThreadControlBlockUserStackKernelStackThread單線程和多線程進(jìn)程模型多線程模型中線程為保持自己的控制流而獨(dú)有寄存器和堆棧，但三個線程同屬一個進(jìn)程，共享一個地址空間。進(jìn)程和線程關(guān)系表2、線程與進(jìn)程的比較 線程具

55、有許多傳統(tǒng)進(jìn)程所具有的特征，故又稱輕型進(jìn)程（Light-Weight-Process）或進(jìn)程元； 而把傳統(tǒng)的進(jìn)程稱為重型進(jìn)程（Heavy-Weight-Process），它相當(dāng)于只有一個線程的任務(wù)。 從調(diào)度、并發(fā)性、擁有資源和系統(tǒng)開銷四個方面比較進(jìn)程和線程。傳統(tǒng)操作系統(tǒng)引入線程的操作系統(tǒng)調(diào)度 基本單位是進(jìn)程 進(jìn)程切換要OS內(nèi)核干預(yù) 基本單位是線程； 同一進(jìn)程中線程切換不會引起進(jìn)程的切換； 進(jìn)程內(nèi)線程切換無需OS內(nèi)核干預(yù).并發(fā)性進(jìn)程間并發(fā) 進(jìn)程間可并發(fā)； 進(jìn)程中多個線程也可并發(fā)擁有資源基本單位是進(jìn)程基本單位是進(jìn)程系統(tǒng)開銷進(jìn)程的創(chuàng)建、切換、撤消時的開銷較大線程創(chuàng)建、切換、撤消時的開銷較小。進(jìn)程和線

56、程比較表2.7.2 線程間的同步和通信 Synchronization and comm. between threads 為使系統(tǒng)中的多線程能有條不紊地運(yùn)行，在系統(tǒng)中必須提供用于線程間同步和通信的機(jī)制。在多線程OS中通常提供多種同步機(jī)制： 互斥鎖 條件變量 計數(shù)信號量 多讀、寫鎖一、 互斥鎖(mutex) mutual exclusive lock互斥鎖是一種較簡單、對資源實(shí)現(xiàn)互斥訪問的機(jī)制。互斥鎖有兩種狀態(tài)，即開鎖(unlock)和關(guān)鎖(lock)狀態(tài)。相應(yīng)地，可用兩條命令（函數(shù)）對互斥鎖進(jìn)行操作，即 lock(mutex)和unlock(mutex)。同步方式： lock(mutex); 讀寫共享數(shù)據(jù)段； unlock(mutex); 為減少線程被阻塞的機(jī)會，在有的系統(tǒng)中還提供了一種用于mutex上的操作命令Trylock。 一個線程利用Trylock命令訪問mutex時，若mutex處于開鎖狀態(tài)， Trylock返回成功狀態(tài)碼，反之，Tr