計(jì)算機(jī)操作系統(tǒng)-進(jìn)程同步與通信.ppt

1、計(jì)算機(jī)操作系統(tǒng)第三章 進(jìn)程同步與通信,計(jì)算機(jī)信息工程學(xué)院,主講教師 王帥強(qiáng) ,3.1 進(jìn)程互斥和同步,3.1.1 互斥算法 3.1.2 信號(hào)量(semaphore) 3.1.3 經(jīng)典進(jìn)程同步問(wèn)題 3.1.4 管程(monitor),返回,在多道程序系統(tǒng)中，由于資源共享和進(jìn)程合作，使各進(jìn)程之間存在兩種類型的制約關(guān)系： （1）間接制約關(guān)系（互斥） （2）直接制約關(guān)系（同步） 進(jìn)程同步指多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)，用于保證這種關(guān)系的 相應(yīng)機(jī)制稱為進(jìn)程同步機(jī)制 互斥指進(jìn)程之間競(jìng)爭(zhēng)使用某種資源,進(jìn)程同步與互斥,3.1.1 互斥算法,3.1.1.1臨界資源 3.1.1.2臨界區(qū)的訪問(wèn)過(guò)程 3.1.1.

2、3同步機(jī)制應(yīng)遵循的準(zhǔn)則 3.1.1.4進(jìn)程互斥的硬件方法,3.1.1.1臨界資源,進(jìn)程間資源訪問(wèn)沖突 共享變量的修改沖突 操作順序沖突 進(jìn)程間的制約關(guān)系 間接制約：進(jìn)行競(jìng)爭(zhēng)獨(dú)占分配到的部分或全部共享資源，“互斥” 直接制約：進(jìn)行協(xié)作等待來(lái)自其他進(jìn)程的信息，“同步”,硬件或軟件（如外設(shè)、共享代碼段、共享數(shù)據(jù)結(jié)構(gòu)），多個(gè)進(jìn)程在對(duì)其進(jìn)行訪問(wèn)時(shí)（關(guān)鍵是進(jìn)行寫入或修改），必須互斥地進(jìn)行有些共享資源可以同時(shí)訪問(wèn)，如只讀數(shù)據(jù),多道程序環(huán)境進(jìn)程之間存在資源共享，進(jìn)程的運(yùn)行時(shí)間受影響,舉例1：共享變量的修改沖突,舉例2：競(jìng)爭(zhēng)條件Race Condition,count+ could be implemented

3、 as register1 = count register1 = register1 + 1 count = register1 count- could be implemented as register2 = count register2 = register2 - 1 count = register2,假定初始狀態(tài)下count = 5 S0: producer execute register1 = count register1 = 5S1: producer execute register1 = register1 + 1 register1 = 6 S2: consume

4、r execute register2 = count register2 = 5 S3: consumer execute register2 = register2 - 1 register2 = 4 S4: producer execute count = register1 count = 6 S5: consumer execute count = register2 count = 4,count- register2 = count register2 = register2 - 1 count = register2,count+ register1 = count regis

5、ter1 = register1 + 1 count = register1,假設(shè)有兩個(gè)進(jìn)程producer:做count+，進(jìn)程consumer做count 且兩個(gè)進(jìn)程并發(fā)執(zhí)行。,競(jìng)爭(zhēng)條件race condition,多個(gè)進(jìn)程并發(fā)訪問(wèn)和操作同一數(shù)據(jù)且執(zhí)行結(jié)果與特定訪問(wèn)順序有關(guān)，稱為競(jìng)爭(zhēng)條件。 如何防止出現(xiàn)競(jìng)爭(zhēng)條件？ 同步,舉例3 操作順序沖突,有3個(gè)進(jìn)程：get, copy和put，它們對(duì)4個(gè)存儲(chǔ)區(qū)域f、s、t和g進(jìn)行操作。,有6種可能的操作順序，只有一種結(jié)果是正確的。,進(jìn)程的交互關(guān)系：可以按照相互感知的程度來(lái)分類,互斥，指多個(gè)進(jìn)程不能同時(shí)使用同一個(gè)資源； 死鎖，指多個(gè)進(jìn)程互不相讓，都得不到

6、足夠的資源； 饑餓，指一個(gè)進(jìn)程一直得不到資源（其他進(jìn)程可能輪流占用資源）,3.1.1.2 臨界區(qū)的訪問(wèn)過(guò)程,臨界區(qū),臨界區(qū)(critical section)：進(jìn)程中訪問(wèn)臨界資源的一段代碼。 進(jìn)入?yún)^(qū)(entry section)：在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入臨界區(qū)的一段代碼。如果可以進(jìn)入臨界區(qū)，通常設(shè)置相應(yīng)正在訪問(wèn)臨界區(qū)標(biāo)志 退出區(qū)(exit section)：用于將正在訪問(wèn)臨界區(qū)標(biāo)志清除。 剩余區(qū)(remainder section)：代碼中的其余部分。,臨界區(qū),3.1.1.3 同步機(jī)制應(yīng)遵循的準(zhǔn)則,空閑則入：其他進(jìn)程均不處于臨界區(qū)； 忙則等待：已有進(jìn)程處于其臨界區(qū)； 有限等待：等待進(jìn)入臨

7、界區(qū)的進(jìn)程不能死等； 讓權(quán)等待：不能進(jìn)入臨界區(qū)的進(jìn)程，應(yīng)釋放CPU（如轉(zhuǎn)換到阻塞狀態(tài)）,3.1.1.4 進(jìn)程互斥的硬件方法,在許多機(jī)器中，都提供了專門的硬件指令Test and Set,它可以用做解決臨界區(qū)問(wèn)題。,Test-and-Set指令,該指令讀出標(biāo)志后設(shè)置為TRUE boolean TS(var lock boolean):boolean begin ts:=lock; lock = TRUE; end lock表示資源的兩種狀態(tài)：TRUE表示正被占用，F(xiàn)ALSE表示空閑,利用TS實(shí)現(xiàn)進(jìn)程互斥,利用TS實(shí)現(xiàn)進(jìn)程互斥：每個(gè)臨界資源設(shè)置一個(gè)公共布爾變量lock，初值為FALSE 在進(jìn)入?yún)^(qū)利

8、用TS進(jìn)行檢查：有進(jìn)程在臨界區(qū)時(shí)，重復(fù)檢查；直到其它進(jìn)程退出時(shí)，檢查通過(guò)；,While TS(Lock) Do skip;,Critical section;,Lock:=false;,Remainder section;,Until false,repeat,硬件方法的優(yōu)點(diǎn) 適用于任意數(shù)目的進(jìn)程，在單處理器或多處理器上 簡(jiǎn)單，容易驗(yàn)證其正確性 可以支持進(jìn)程內(nèi)存在多個(gè)臨界區(qū)，只需為每個(gè)臨界區(qū)設(shè)立一個(gè)布爾變量 硬件方法的缺點(diǎn) 等待要耗費(fèi)CPU時(shí)間，不能實(shí)現(xiàn)讓權(quán)等待 可能饑餓：從等待進(jìn)程中隨機(jī)選擇一個(gè)進(jìn)入臨界區(qū)，有的進(jìn)程可能一直選不上 可能死鎖,3.1.1.4進(jìn)程互斥的硬件方法,3.1.2 信號(hào)量

9、(semaphore),3.1.2.1 信號(hào)量和P、V原語(yǔ) 3.1.2.2 信號(hào)量集,前面的互斥算法是平等進(jìn)程間的一種協(xié)商機(jī)制，OS可從進(jìn)程管理者的角度來(lái)處理互斥的問(wèn)題，信號(hào)量就是OS提供的管理公有資源的有效手段。 信號(hào)量代表可用資源實(shí)體的數(shù)量。,3.1.2.1 信號(hào)量和P、V原語(yǔ),1965年，由荷蘭學(xué)者Dijkstra提出是一種卓有成效的進(jìn)程同步機(jī)制。 每個(gè)信號(hào)量 s 除一個(gè)整數(shù)值s.value（計(jì)數(shù)）外，還有一個(gè)進(jìn)程等待隊(duì)列 s.queue，其中是阻塞在該信號(hào)量的各個(gè)進(jìn)程的標(biāo)識(shí) 信號(hào)量只能通過(guò)初始化和兩個(gè)標(biāo)準(zhǔn)的原語(yǔ)來(lái)訪問(wèn)作為OS核心代碼執(zhí)行，不受進(jìn)程調(diào)度的打斷 初始化指定一個(gè)非負(fù)整數(shù)值，表

10、示空閑資源總數(shù)（又稱為資源信號(hào)量）若為非負(fù)值表示當(dāng)前的空閑資源數(shù)，若為負(fù)值其絕對(duì)值表示當(dāng)前等待臨界區(qū)的進(jìn)程數(shù),信號(hào)量數(shù)據(jù)結(jié)構(gòu)的定義,Type semaphore=record value:integer; L:list of process; end (類pascal語(yǔ)言) 或 typedef struct int value; struct process *; semaphore; （語(yǔ)言）,1. P原語(yǔ)wait(s),Procedure wait(s) var s:semaphore; begin s.value:=s.value -1;/表示申請(qǐng)一個(gè)資源; if (s.value 0)

11、then/表示沒(méi)有空閑資源; begin 調(diào)用進(jìn)程進(jìn)入等待隊(duì)列s.; 阻塞調(diào)用進(jìn)程; end; end,2. V原語(yǔ)signal(s),Procedure signal(s) var s:semaphore; begin s.value:=s.value+1;/表示釋放一個(gè)資源； if (s.value = 0)/表示有進(jìn)程處于阻塞狀態(tài)； begin 從等待隊(duì)列s.中取出一個(gè)進(jìn)程P; 進(jìn)程P進(jìn)入就緒隊(duì)列; end; end,V原語(yǔ)通常喚醒進(jìn)程等待隊(duì)列中的頭一個(gè)進(jìn)程。,3. 利用信號(hào)量實(shí)現(xiàn)互斥,為臨界資源設(shè)置一個(gè)互斥信號(hào)量mutex(MUTual Exclusion)，其初值為1；在每個(gè)進(jìn)程中將

12、臨界區(qū)代碼置于P(mutex)和V(mutex)原語(yǔ)之間 必須成對(duì)使用P和V原語(yǔ)：遺漏P原語(yǔ)則不能保證互斥訪問(wèn)，遺漏V原語(yǔ)則不能在使用臨界資源之后將其釋放（給其他等待的進(jìn)程）；P、V原語(yǔ)不能次序錯(cuò)誤、重復(fù)或遺漏,4. 利用信號(hào)量來(lái)描述前趨關(guān)系,前趨關(guān)系：并發(fā)執(zhí)行的進(jìn)程P1和P2中，分別有代碼C1和C2，要求C1在C2開(kāi)始前完成； 為每個(gè)前趨關(guān)系設(shè)置一個(gè)互斥信號(hào)量S12，其初值為0,3.1.2.2 信號(hào)量集,基本思想：在一個(gè)原語(yǔ)中，將一段代碼同時(shí)需要的多個(gè)臨界資源，要么全部分配給它，要么一個(gè)都不分配。稱為Swait(Simultaneous Wait)。在Swait時(shí)，各個(gè)信號(hào)量的次序并不重要，

13、雖然會(huì)影響進(jìn)程歸入哪個(gè)阻塞隊(duì)列，但是由于是對(duì)資源全部分配或不分配，所以總有進(jìn)程獲得全部資源并在推進(jìn)之后釋放資源，因此不會(huì)死鎖。,1. AND型信號(hào)量集,信號(hào)量集用于同時(shí)需要多個(gè)資源時(shí)的信號(hào)量操作； AND型信號(hào)量集用于同時(shí)需要多種資源且每種占用一個(gè)時(shí)的信號(hào)量操作；,Swait(S1, S2, , Sn)/P原語(yǔ)； if (S1 =1 and S2 = 1 and and Sn = 1) /滿足資源要求時(shí)的處理； for i = 1 to n do Si= Si -1; /注：與wait的處理不同，這里是在確信可滿足 /資源要求時(shí)，才進(jìn)行減1操作； endfor; else /某些資源不夠時(shí)的處

14、理； 調(diào)用進(jìn)程進(jìn)入第一個(gè)小于1信號(hào)量的等待隊(duì)列Sj.; 阻塞調(diào)用進(jìn)程; endif,Ssignal(S1, S2, , Sn) for i = 1 to n do Si:= Si +1;/釋放占用的資源； for (each process P waiting in Si.) /檢查每種資源的等待隊(duì)列的所有進(jìn)程； 從等待隊(duì)列Si.中取出進(jìn)程P; if (判斷進(jìn)程P是否通過(guò)Swait中的測(cè)試) /注：與signal不同，這里要進(jìn)行重新判斷； begin/通過(guò)檢查（資源夠用）時(shí)的處理； 進(jìn)程P進(jìn)入就緒隊(duì)列; end else /未通過(guò)檢查（資源不夠用）時(shí)的處理； 進(jìn)程P進(jìn)入某等待隊(duì)列； endif

15、 endfor endfor,2. 一般“信號(hào)量集”,一次需要N個(gè)某類臨界資源時(shí)，就要進(jìn)行N次wait操作低效又可能死鎖 基本思想：在AND型信號(hào)量集的基礎(chǔ)上進(jìn)行擴(kuò)充：進(jìn)程對(duì)信號(hào)量Si的測(cè)試值為ti（用于信號(hào)量的判斷，即Si = ti，表示資源數(shù)量低于ti時(shí)，便不予分配），占用值為di（用于信號(hào)量的增減，即Si = Si - di和Si = Si + di） Swait(S1, t1, d1; .; Sn, tn, dn); Ssignal(S1, d1; .; Sn, dn);,一般信號(hào)量集用于同時(shí)需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個(gè)臨界值時(shí)的處理；,Swait(S1,

16、 t1, d1; .; Sn, tn, dn); /P原語(yǔ)； if (S1 =t1 and .Sn=tn) then /滿足資源要求時(shí)的處理； for i = 1 to n do Si= Si -di; endfor; else /某些資源不夠時(shí)的處理； 調(diào)用進(jìn)程進(jìn)入第一個(gè)小于tj信號(hào)量的等待隊(duì)列Sj.queue; 阻塞調(diào)用進(jìn)程; endif,Ssignal(S1, d1; .; Sn, dn); for i = 1 to n do Si:= Si +di;/釋放占用的資源； for (each process P waiting in Si.queue) /檢查每種資源的等待隊(duì)列的所有進(jìn)程；

17、 從等待隊(duì)列Si.L中取出進(jìn)程P; if (判斷進(jìn)程P是否通過(guò)Swait中的測(cè)試) /注：與signal不同，這里要進(jìn)行重新判斷； begin/通過(guò)檢查（資源夠用）時(shí)的處理； 進(jìn)程P進(jìn)入就緒隊(duì)列; end else /未通過(guò)檢查（資源不夠用）時(shí)的處理； 進(jìn)程P進(jìn)入某等待隊(duì)列； endif endfor endfor,3.1.3 經(jīng)典進(jìn)程同步問(wèn)題,1. 生產(chǎn)者消費(fèi)者問(wèn)題(the producer-consumer problem),問(wèn)題描述：若干進(jìn)程通過(guò)有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，生產(chǎn)者進(jìn)程不斷寫入，而消費(fèi)者進(jìn)程不斷讀出；共享緩沖區(qū)共有N個(gè)；任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩沖區(qū)進(jìn)行操作。,定

18、義信號(hào)量： full是 滿緩沖區(qū)數(shù)目，初值為0，empty是空緩沖區(qū)數(shù)目，初值為N。實(shí)際上，full和empty是同一個(gè)含義：full + empty = N mutex用于訪問(wèn)緩沖區(qū)時(shí)的互斥，初值是1,生產(chǎn)者消費(fèi)者問(wèn)題,采用AND信號(hào)量集：Swait(empty, mutex), Ssignal(full, mutex), ,生產(chǎn)者消費(fèi)者問(wèn)題,讀者寫者問(wèn)題,問(wèn)題描述：對(duì)共享資源的讀寫操作，任一時(shí)刻“寫者”最多只允許一個(gè)，而“讀者”則允許多個(gè) “讀寫”互斥， “寫寫”互斥， 讀讀允許,Wmutex表示允許寫，初值是1。 公共變量Rcount表示“正在讀”的進(jìn)程數(shù)，初值是0； Rmutex表示對(duì)

19、Rcount的互斥操作，初值是1。,讀者寫者問(wèn)題,P(Rmutex); +Rcount; if (Rcount = 1) P(Wmutex); V(Rmutex); read; P(Rmutex); -Rcount; if (Rcount = 0) V(Wmutex); V(Rmutex);,Reader:,P(Wmutex); write; V(Wmutex);,Writer:,采用一般信號(hào)量集機(jī)制：?jiǎn)栴}增加一個(gè)限制條件：同時(shí)讀的讀者最多R個(gè) Wmutex表示允許寫，初值是1 Rcount表示允許讀者數(shù)目，初值為R,讀者寫者問(wèn)題,3. 哲學(xué)家進(jìn)餐問(wèn)題,問(wèn)題描述：（由Dijkstra首先提出并

20、解決）5個(gè)哲學(xué)家圍繞一張圓桌而坐，桌子上放著5支筷子，每?jī)蓚€(gè)哲學(xué)家之間放一支；哲學(xué)家的動(dòng)作包括思考和進(jìn)餐，進(jìn)餐時(shí)需要同時(shí)拿起他左邊和右邊的兩支筷子，思考時(shí)則同時(shí)將兩支筷子放回原處。如何保證哲學(xué)家們的動(dòng)作有序進(jìn)行？如：不出現(xiàn)相鄰者同時(shí)要求進(jìn)餐；不出現(xiàn)有人永遠(yuǎn)拿不到筷子；,筷子是臨界資源，可以用信號(hào)量表示 var chopstic:array0,1,2,3,4 of semaphore; 初始化為1 repeat wait(chopstici); wait(chopstic (i +1) mod 5 ); . . Eat; signal(chopstici); signal(chopstic (i

21、 +1) mod 5 ); . Think; until false;,3. 哲學(xué)家進(jìn)餐問(wèn)題,采用一般信號(hào)量集機(jī)制：,Repeat think; swait(chopstic( i +1) mod 5,chopstici); eat; signal(chopstic( i +1) mod 5,chopstici); until false;,3.1.4 管程(monitor),用信號(hào)量可實(shí)現(xiàn)進(jìn)程間的同步，但由于信號(hào)量的控制分布在整個(gè)程序中，其正確性分析很困難。管程是管理進(jìn)程間同步的機(jī)制，它保證進(jìn)程互斥地訪問(wèn)共享變量，并方便地阻塞和喚醒進(jìn)程。管程可以函數(shù)庫(kù)的形式實(shí)現(xiàn)。相比之下，管程比信號(hào)量好控制

22、。,1. 信號(hào)量同步的缺點(diǎn),同步操作分散：信號(hào)量機(jī)制中，同步操作分散在各個(gè)進(jìn)程中，使用不當(dāng)就可能導(dǎo)致各進(jìn)程死鎖（如P、V操作的次序錯(cuò)誤、重復(fù)或遺漏） 易讀性差：要了解對(duì)于一組共享變量及信號(hào)量的操作是否正確，必須通讀整個(gè)系統(tǒng)或者并發(fā)程序； 不利于修改和維護(hù)：各模塊的獨(dú)立性差，任一組變量或一段代碼的修改都可能影響全局； 正確性難以保證：操作系統(tǒng)或并發(fā)程序通常很大，很難保證這樣一個(gè)復(fù)雜的系統(tǒng)沒(méi)有邏輯錯(cuò)誤；,2. 管程的引入,1973年，Hoare和Hanson所提出；其基本思想是把信號(hào)量及其操作原語(yǔ)封裝在一個(gè)對(duì)象內(nèi)部。即：將共享變量以及對(duì)共享變量能夠進(jìn)行的所有操作集中在一個(gè)模塊中。 管程的定義：管程

23、是關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)及一組針對(duì)該資源的操作過(guò)程所構(gòu)成的軟件模塊,這些過(guò)程能同步進(jìn)程和改變管程中的數(shù)據(jù)。 管程可增強(qiáng)模塊的獨(dú)立性：系統(tǒng)按資源管理的觀點(diǎn)分解成若干模塊，用數(shù)據(jù)表示抽象系統(tǒng)資源，同時(shí)分析了共享資源和專用資源在管理上的差別，按不同的管理方式定義模塊的類型和結(jié)構(gòu)，使同步操作相對(duì)集中，從而增加了模塊的相對(duì)獨(dú)立性 引入管程可提高代碼的可讀性，便于修改和維護(hù)，正確性易于保證：采用集中式同步機(jī)制。一個(gè)操作系統(tǒng)或并發(fā)程序由若干個(gè)這樣的模塊所構(gòu)成，一個(gè)模塊通常較短，模塊之間關(guān)系清晰。,管程由三部分組成： （1）局部于管程的共享變量說(shuō)明 （2）對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程 （3）對(duì)局部于管程的數(shù)

24、據(jù)設(shè)置初始值的語(yǔ)句。,3. 管程的主要特性,模塊化：一個(gè)管程是一個(gè)基本程序單位，可以單獨(dú)編譯； 抽象數(shù)據(jù)類型：管程是一種特殊的數(shù)據(jù)類型，其中不僅有數(shù)據(jù)，而且有對(duì)數(shù)據(jù)進(jìn)行操作的代碼 信息封裝：管程是半透明的，管程中的外部過(guò)程（函數(shù)）實(shí)現(xiàn)了某些功能，至于這些功能是怎樣實(shí)現(xiàn)的，在其外部則是不可見(jiàn)的；,4. 管程的實(shí)現(xiàn)要素,管程中的共享變量在管程外部是不可見(jiàn)的，外部只能通過(guò)調(diào)用管程中所說(shuō)明的外部過(guò)程（函數(shù)）來(lái)間接地訪問(wèn)管程中的共享變量； 為了保證管程共享變量的數(shù)據(jù)完整性，規(guī)定管程互斥進(jìn)入； 管程通常是用來(lái)管理資源的，因而在管程中應(yīng)當(dāng)設(shè)有進(jìn)程等待隊(duì)列以及相應(yīng)的等待及喚醒操作；,5. 管程中的多個(gè)進(jìn)程進(jìn)入

25、,當(dāng)一個(gè)進(jìn)入管程的進(jìn)程執(zhí)行等待操作時(shí)，它應(yīng)當(dāng)釋放管程的互斥權(quán)；當(dāng)一個(gè)進(jìn)入管程的進(jìn)程執(zhí)行喚醒操作時(shí)（如喚醒），管程中便存在兩個(gè)同時(shí)處于活動(dòng)狀態(tài)的進(jìn)程。 管程中的喚醒切換方法： P等待Q繼續(xù)，直到Q等待或退出； Q等待P繼續(xù)，直到P等待或退出； 規(guī)定喚醒為管程中最后一個(gè)可執(zhí)行的操作；,入口等待隊(duì)列：因?yàn)楣艹淌腔コ膺M(jìn)入的，所以當(dāng)一個(gè)進(jìn)程試圖進(jìn)入一個(gè)巳被占用的管程時(shí)它應(yīng)當(dāng)在管程的入口處等待，因而在管程的入口處應(yīng)當(dāng)有一個(gè)進(jìn)程等待隊(duì)列，稱作入口等待隊(duì)列。 緊急等待隊(duì)列：如果進(jìn)程喚醒進(jìn)程，則等待繼續(xù)，如果進(jìn)程在執(zhí)行又喚醒進(jìn)程，則等待繼續(xù)，.，如此，在管程內(nèi)部，由于執(zhí)行喚醒操作，可能會(huì)出現(xiàn)多個(gè)等待進(jìn)程（已被喚

26、醒，但由于管程的互斥進(jìn)入而等待），因而還需要有一個(gè)進(jìn)程等待隊(duì)列，這個(gè)等待隊(duì)列被稱為緊急等待隊(duì)列。它的優(yōu)先級(jí)應(yīng)當(dāng)高于入口等待隊(duì)列的優(yōu)先級(jí)。,5. 管程中的多個(gè)進(jìn)程進(jìn)入,6. 條件變量(condition),由于管程通常是用于管理資源的，因而在管程內(nèi)部，應(yīng)當(dāng)存在某種等待機(jī)制。當(dāng)進(jìn)入管程的進(jìn)程因資源被占用等原因不能繼續(xù)運(yùn)行時(shí)使其等待。為此在管程內(nèi)部可以說(shuō)明和使用一種特殊類型的變量-條件變量。每個(gè)表示一種等待原因，并不取具體數(shù)值相當(dāng)于每個(gè)原因?qū)?yīng)一個(gè)隊(duì)列。,7. 管程的格式,TYPE monitor_name = MONITOR; 共享變量說(shuō)明 define 本管程內(nèi)所定義、本管程外可調(diào)用的過(guò)程（函數(shù)

27、）名字表 use 本管程外所定義、本管程內(nèi)將調(diào)用的過(guò)程（函數(shù)）名字表 PROCEDURE 過(guò)程名（形參表）； 過(guò)程局部變量說(shuō)明； BEGIN 語(yǔ)句序列； END; .,FUNCTION 函數(shù)名（形參表）：值類型； 函數(shù)局部變量說(shuō)明； BEGIN 語(yǔ)句序列； END; . BEGIN 共享變量初始化語(yǔ)句序列； END;,8. 管程的的組成,名稱：為每個(gè)共享資源設(shè)立一個(gè)管程 數(shù)據(jù)結(jié)構(gòu)說(shuō)明：一組局部于管程的控制變量 操作原語(yǔ)：對(duì)控制變量和臨界資源進(jìn)行操作的一組原語(yǔ)過(guò)程（程序代碼），是訪問(wèn)該管程的唯一途徑。這些原語(yǔ)本身是互斥的，任一時(shí)刻只允許一個(gè)進(jìn)程去調(diào)用，其余需要訪問(wèn)的進(jìn)程就等待。 初始化代碼：對(duì)控

28、制變量進(jìn)行初始化的代碼,9. 例子：生產(chǎn)者-消費(fèi)者問(wèn)題,建立一個(gè)管程，命名為PC，其中包括兩個(gè)過(guò)程 （1）put(item) 生產(chǎn)者利用該過(guò)程，將自己生產(chǎn)的消息放到緩沖池中， 并用整型變量count來(lái)表示在緩沖池中已有的消息數(shù)，當(dāng) count=n時(shí)，表示緩沖池已滿，生產(chǎn)者需等待。 （2）get(item) 消費(fèi)者利用該過(guò)程從緩沖池中取出一個(gè)消息，當(dāng)count=0 時(shí)，表示緩沖池中無(wú)可用消息，消費(fèi)者需等待。,type produce-consumer=monitor var in,out,count:integer; buffer:array0,n-1 of item; notfull, not

29、empty : condition; procedure entry put(item) begin if count=n then notfull.wait; buffer(in):=nextp; in:=(in+1) mod n; count:=count+1; if notempty.queue then notempty.signal; end,PC管程的描述：,Procedure entry get(item) begin if count=0 then notempty.wait; nextc:=buffer(out) out:=(out+1) mod n; count:=coun

30、t -1; if notfull.queue then notfull.signal; end begin in:=out:=0; count:=0; end,其中的生產(chǎn)者和消費(fèi)者描述為： producer : begin repeat produce an item in nextp; pc.put(item); until false; end consumer : begin repeat pc.get(item); consume the item in nextc; until false; end,10. 管程和進(jìn)程的異同點(diǎn),設(shè)置進(jìn)程和管程的目的不同 系統(tǒng)管理數(shù)據(jù)結(jié)構(gòu) 進(jìn)程：PCB

31、 管程：等待隊(duì)列 管程被進(jìn)程調(diào)用 管程是操作系統(tǒng)的固有成分，無(wú)創(chuàng)建和撤消,進(jìn)程間通信示意圖,communication?,inter-process communication,machine,process A,process B,3.2.1 進(jìn)程間通信的類型,低級(jí)通信：只能傳遞狀態(tài)和整數(shù)值（控制信息），包括進(jìn)程互斥和同步所采用的信號(hào)量和管程機(jī)制。 優(yōu)點(diǎn)：速度快 缺點(diǎn)： 傳送信息量?。盒实?，每次通信傳遞的信息量固定，若傳遞較多信息則需要進(jìn)行多次通信。 編程復(fù)雜：用戶直接實(shí)現(xiàn)通信的細(xì)節(jié)，編程復(fù)雜，容易出錯(cuò)。 高級(jí)通信：能夠傳送任意數(shù)量的數(shù)據(jù)，包括三類：共享存儲(chǔ)區(qū)、管道、消息。,1. 低級(jí)通信

32、和高級(jí)通信,2. 直接通信和間接通信,直接通信：信息直接傳遞給接收方，如管道。 在發(fā)送時(shí)，指定接收方的地址或標(biāo)識(shí)，也可以指定多個(gè)接收方或廣播式地址； 在接收時(shí)，允許接收來(lái)自任意發(fā)送方的消息，并在讀出消息的同時(shí)獲取發(fā)送方的地址。 間接通信：借助于收發(fā)雙方進(jìn)程之外的共享數(shù)據(jù)結(jié)構(gòu)作為通信中轉(zhuǎn)，如消息隊(duì)列。通常收方和發(fā)方的數(shù)目可以是任意的。,3. 高級(jí)通信機(jī)制,共享存儲(chǔ)器系統(tǒng) 消息傳遞系統(tǒng) 管道通信 基于socket的通信,3.2.2 共享存儲(chǔ)區(qū)系統(tǒng),相互通信的進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲(chǔ)區(qū)，進(jìn)程之間通過(guò)它們進(jìn)行通信。,1. 基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式 如生產(chǎn)者和消費(fèi)者問(wèn)題,屬于低級(jí)通信 。,2.基

33、于共享存儲(chǔ)區(qū)的通信方式 為傳輸大量數(shù)據(jù),在內(nèi)存中劃出一塊共享存儲(chǔ)區(qū),諸進(jìn)程可通過(guò)對(duì)共享存儲(chǔ)區(qū)的數(shù)據(jù)進(jìn)行讀和寫進(jìn)行通信。,共享內(nèi)存 Shared Memory,共享內(nèi)存是進(jìn)程間最有效也是最快的通信方式。 共享內(nèi)存是內(nèi)存塊方式的數(shù)據(jù)塊，其數(shù)據(jù)長(zhǎng)度可為系統(tǒng)參數(shù)限制內(nèi)的任意長(zhǎng)度。 多個(gè)進(jìn)程可將同一物理內(nèi)存映射到自己的地址空間。 共享內(nèi)存處理函數(shù)： 創(chuàng)建一個(gè)共享段: shmget( key, size, flags ) 把共享內(nèi)存鏈接到調(diào)用進(jìn)程的數(shù)據(jù)段中: shmat( shmid, *shmaddr, flags ) 分離一個(gè)共享段: shmdt( *shmaddr ) 對(duì)共享段的各種控制操作: sh

34、mctl( ),Shared Memory Example,#include #include #include #include #define SHMSZ 27 main() int shmid; key_t key; char c, *shm, *s; key = 5678; /* selected key */ /* Create the segment.*/ if (shmid = shmget(key,SHMSZ,IPC_CREAT | 0666) 0) perror(shmget); exit(1); /* Now we attach the segment to our dat

35、a space.*/ if (shm = shmat(shmid, NULL, 0) = (char *) -1) perror(shmat); exit(1); /* put some things into the memory */ for (s = shm, c = a; c = z; c+) *s+ = c; *s = NULL; /* wait until first character is changed to * */ while (*shm != *) sleep(1); exit(0); ,#include #include #include #include #defi

36、ne SHMSZ 27 main() int shmid; key_t key; char *shm, *s; key = 5678; /* selected key by server */ /* Locate the segment. */ if (shmid = shmget(key,SHMSZ,0666) 0) perror(shmget); exit(1); /* Now we attach the segment to our data space. */ if (shm = shmat(shmid, NULL, 0) = (char *) -1) perror(shmat); e

37、xit(1); /* read what the server put in the memory. */ for (s = shm; *s != NULL; s+) putchar(*s); putchar(n); /* change the first character in segment to * */ *shm = *; exit(0); ,3.2.3 消息傳遞系統(tǒng),進(jìn)程間的數(shù)據(jù)交換以消息(message)為單位,在計(jì)算機(jī)網(wǎng)絡(luò)中, message又稱為報(bào)文。 系統(tǒng)提供了一組通信原語(yǔ)來(lái)實(shí)現(xiàn)通信.,發(fā)送原語(yǔ)的定義：send(p,message) 發(fā)送消息到進(jìn)程P,接收原語(yǔ)的定義：rec

38、eive(Q,message)接收來(lái)自進(jìn)程Q的消息,(1) 直接通信方式 發(fā)送進(jìn)程直接將消息發(fā)送給接收進(jìn)程,并把它掛在接收進(jìn)程的消息緩沖隊(duì)列上, 接收進(jìn)程從它的消息緩沖隊(duì)列上取得消息。,消息傳遞系統(tǒng),(2）間接通信方式 消息通過(guò)郵箱或端口來(lái)發(fā)送和接收。郵箱可以被抽象為一個(gè)對(duì)象，進(jìn)程可以向其中存放消息也可以從中刪除消息。,每個(gè)郵箱要有一個(gè)唯一的標(biāo)識(shí)符。一個(gè)進(jìn)程可以通過(guò)不同的郵箱和其它進(jìn)程通信。 信箱通信原語(yǔ)：信箱的創(chuàng)建和撤銷、信息的發(fā)送和接收,例如：若兩個(gè)進(jìn)程共享一個(gè)郵箱，發(fā)送原語(yǔ)和接收原語(yǔ)分別是： send(A,message) ：發(fā)送一個(gè)消息到郵箱A Receive(A,message)：接

39、收來(lái)自信箱A的消息。,舉例1：消息緩沖隊(duì)列通信機(jī)制,廣泛應(yīng)用于本地進(jìn)程之間的通信中。 數(shù)據(jù)結(jié)構(gòu) 1. 消息緩沖區(qū) TYPE message buffer = record sender : 發(fā)送者進(jìn)程標(biāo)志符 size : 消息長(zhǎng)度 text : 消息正文 next : 指向下一個(gè)消息緩沖區(qū)的指針 end,2. PCB 中有關(guān)通信的數(shù)據(jù)項(xiàng) type processcontrol block =record . . mq : 消息隊(duì)列隊(duì)首指針 mutex : 消息隊(duì)列互斥信號(hào)量 sm : 消息隊(duì)列資源信號(hào)量 . . end,舉例1：消息緩沖隊(duì)列通信機(jī)制,procedure send(receiver ,a) a為發(fā)送進(jìn)程在自己的內(nèi)存空間設(shè)置的發(fā)送區(qū)。 begin getbuf(a.size, i ); 申請(qǐng)緩沖區(qū)i i.sender :=a.sender ; i.text:=a.text; i.next:=0; getid(PCB set, receiver , j) wait(j.mutex) insert(j.mq, i );