第3章-進(jìn)程同步與通信

1、1 李李 彤彤 博士博士 2 http:/ 課件下載課件下載 3 版權(quán)申明版權(quán)申明 本課程的全部課件經(jīng)著作權(quán)人授權(quán)，免費(fèi)本課程的全部課件經(jīng)著作權(quán)人授權(quán)，免費(fèi) 在中華人民共和國(guó)境內(nèi)普通高等學(xué)校用于與在中華人民共和國(guó)境內(nèi)普通高等學(xué)校用于與 操作系統(tǒng)操作系統(tǒng)CDIO之路之路（李彤等編著，（李彤等編著， 清華大學(xué)出版社清華大學(xué)出版社2012年版）相配套的教學(xué)活動(dòng)。年版）相配套的教學(xué)活動(dòng)。 超出本范圍將違反中華人民共和國(guó)法律，必受超出本范圍將違反中華人民共和國(guó)法律，必受 追究！追究！ 4 第第3章章 進(jìn)程同步與通信進(jìn)程同步與通信 3.1進(jìn)程的并發(fā)執(zhí)行進(jìn)程的并發(fā)執(zhí)行 3.2進(jìn)程的互斥進(jìn)程的互斥 3.3進(jìn)程

2、的同步進(jìn)程的同步 3.4 信號(hào)量信號(hào)量 3.5管程管程 3.6 進(jìn)程的高級(jí)通信進(jìn)程的高級(jí)通信 3.7死鎖死鎖 3.8經(jīng)典同步與互斥問(wèn)題經(jīng)典同步與互斥問(wèn)題 3.9 UNIX系統(tǒng)軟中斷系統(tǒng)軟中斷 3.10 UNIX系統(tǒng)管道系統(tǒng)管道 3.11 UNIX系統(tǒng)進(jìn)程間通信系統(tǒng)進(jìn)程間通信IPC 5 3.1進(jìn)程的并發(fā)執(zhí)行進(jìn)程的并發(fā)執(zhí)行 3.1.1 與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤 3.1.2 Bernstein條件條件 3.1.3 臨界資源與臨界區(qū)臨界資源與臨界區(qū) 6 3.1.1 與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤 無(wú)關(guān)的進(jìn)程無(wú)關(guān)的進(jìn)程:指它們分別在不同的變量集上操指它們分別在不同的變量集上操 作，變量集之間的

3、交集為空集。作，變量集之間的交集為空集。 交互的進(jìn)程交互的進(jìn)程:指它們共享某些變量，變量集之指它們共享某些變量，變量集之 間的交集不為空集。間的交集不為空集。 導(dǎo)致與時(shí)間有關(guān)的錯(cuò)誤導(dǎo)致與時(shí)間有關(guān)的錯(cuò)誤 的原因的原因: 并發(fā)進(jìn)程中共享了公共變量，使得程序的執(zhí)行與并發(fā)進(jìn)程中共享了公共變量，使得程序的執(zhí)行與 并發(fā)進(jìn)程執(zhí)行的速度有關(guān)。并發(fā)進(jìn)程執(zhí)行的速度有關(guān)。 7 并發(fā)執(zhí)行帶來(lái)的問(wèn)題：并發(fā)執(zhí)行帶來(lái)的問(wèn)題： 間斷間斷(異步異步)性：性：走走停停走走停停，一個(gè)程序可能走，一個(gè)程序可能走 到中途停下來(lái)，失去原有的時(shí)序關(guān)系；到中途停下來(lái)，失去原有的時(shí)序關(guān)系； 失去封閉性：失去封閉性：共享資源，受其他程序的控制邏

4、共享資源，受其他程序的控制邏 輯的影響。如：一個(gè)程序?qū)懙酱鎯?chǔ)器中的數(shù)據(jù)輯的影響。如：一個(gè)程序?qū)懙酱鎯?chǔ)器中的數(shù)據(jù) 可能被另一個(gè)程序修改，失去原有的不變特征?？赡鼙涣硪粋€(gè)程序修改，失去原有的不變特征。 失去可再現(xiàn)性：失去可再現(xiàn)性：失去封閉性失去封閉性 失去可再現(xiàn)性；失去可再現(xiàn)性； 外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化，失外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化，失 去原有的可重復(fù)特征。去原有的可重復(fù)特征。 3.1.1 與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤 8 舉例：棧的讀、寫程序段并發(fā)執(zhí)行舉例：棧的讀、寫程序段并發(fā)執(zhí)行 Procedure getaddr(top) begin local r r (top

5、) top top-1 return (r) end Procedure reladdr(blk) begin top top+1 (top) blk end 3.1.1 與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤 9 讀、寫并發(fā)可能導(dǎo)致錯(cuò)誤：讀、寫并發(fā)可能導(dǎo)致錯(cuò)誤： a b e f Top (a) a b e f Top (b) (Reladdr()執(zhí)執(zhí) 行語(yǔ)句：行語(yǔ)句： top top+1 后后) a b e f Top (c) geladdr() 取數(shù)據(jù)失敗取數(shù)據(jù)失敗 3.1.1 與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤 10 3.1.2 Bernstein條件條件 Bernstein條件條件表明：兩個(gè)交

6、互的進(jìn)程（或兩相鄰表明：兩個(gè)交互的進(jìn)程（或兩相鄰 語(yǔ)句），當(dāng)它們變量集的交集分別只屬于它們語(yǔ)句），當(dāng)它們變量集的交集分別只屬于它們 各自的引用變量集的時(shí)候，可以并發(fā)執(zhí)行；否各自的引用變量集的時(shí)候，可以并發(fā)執(zhí)行；否 則，不滿足則，不滿足Bernstein條件。條件。 Bernstein條件條件 進(jìn)程的執(zhí)行進(jìn)程的執(zhí)行 與時(shí)間無(wú)關(guān)與時(shí)間無(wú)關(guān) 成立成立 注意：是充分條件，而非必要條件注意：是充分條件，而非必要條件 11 程序程序 P(i) 針對(duì)針對(duì)共享變量共享變量的讀集和寫集的讀集和寫集 R(i) 和和W(i) 條件：任意兩個(gè)程序條件：任意兩個(gè)程序P(i)和和P(j)，有：，有： R(i) W(j)=

7、 ; W(i) R(j)= ; W(i) W(j)=; 并發(fā)執(zhí)行的條件：達(dá)到封閉性和可再現(xiàn)性。并發(fā)執(zhí)行的條件：達(dá)到封閉性和可再現(xiàn)性。1966年，年， 由由Bernstein給出并發(fā)執(zhí)行的條件。給出并發(fā)執(zhí)行的條件。 前兩條保證一個(gè)程序的兩次讀之間數(shù)據(jù)不變化；前兩條保證一個(gè)程序的兩次讀之間數(shù)據(jù)不變化； 最后一條保證寫的結(jié)果不丟掉。最后一條保證寫的結(jié)果不丟掉。 現(xiàn)在的問(wèn)題是這個(gè)條件不好檢查。現(xiàn)在的問(wèn)題是這個(gè)條件不好檢查。 3.1.2 Bernstein條件條件 12 3.1.3 臨界資源與臨界區(qū)臨界資源與臨界區(qū) 臨界資源：臨界資源：一次只允許被一個(gè)進(jìn)程使用的資源一次只允許被一個(gè)進(jìn)程使用的資源 臨界區(qū)

8、：臨界區(qū)：在進(jìn)程中訪問(wèn)臨界資源的那一段程序。在進(jìn)程中訪問(wèn)臨界資源的那一段程序。 1.不能讓一個(gè)進(jìn)程無(wú)限地留在它的臨界區(qū)內(nèi)。不能讓一個(gè)進(jìn)程無(wú)限地留在它的臨界區(qū)內(nèi)。 2.不應(yīng)對(duì)不應(yīng)對(duì)CPU的數(shù)量和速度做任何假設(shè)。的數(shù)量和速度做任何假設(shè)。 3.不能強(qiáng)迫一個(gè)進(jìn)程無(wú)期限地等待進(jìn)入臨界區(qū)。不能強(qiáng)迫一個(gè)進(jìn)程無(wú)期限地等待進(jìn)入臨界區(qū)。 4.在非臨界區(qū)運(yùn)行的任一進(jìn)程不得妨礙正等待進(jìn)入在非臨界區(qū)運(yùn)行的任一進(jìn)程不得妨礙正等待進(jìn)入 臨界區(qū)的其他進(jìn)程的進(jìn)展。臨界區(qū)的其他進(jìn)程的進(jìn)展。 臨界資源臨界資源 硬件硬件臨界資源臨界資源 軟件軟件臨界資源臨界資源 管理臨界區(qū)的方法管理臨界區(qū)的方法 13 3.2進(jìn)程的互斥進(jìn)程的互斥 3

9、.2.1 軟件實(shí)現(xiàn)方法軟件實(shí)現(xiàn)方法 3.2.2 硬件實(shí)現(xiàn)方法硬件實(shí)現(xiàn)方法 14 3.2.1 軟件實(shí)現(xiàn)方法軟件實(shí)現(xiàn)方法 （1） 嚴(yán)格輪換法嚴(yán)格輪換法 :設(shè)置一個(gè)公共整型變量，標(biāo)識(shí)允許進(jìn)設(shè)置一個(gè)公共整型變量，標(biāo)識(shí)允許進(jìn) 入臨界區(qū)的進(jìn)程。入臨界區(qū)的進(jìn)程。 兩個(gè)進(jìn)程的嚴(yán)格輪換法的實(shí)現(xiàn)兩個(gè)進(jìn)程的嚴(yán)格輪換法的實(shí)現(xiàn) int turn=1; /*公共變量公共變量*/ 進(jìn)程進(jìn)程1： while (TRUE) while (turn != 1); /*進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)*/ Critial_region1(); /*臨界區(qū)臨界區(qū)*/ turn = 2;/*退出區(qū)退出區(qū)*/ other_region1(); /*剩余區(qū)剩

10、余區(qū)*/ 進(jìn)程進(jìn)程2： while (TRUE) while (turn != 2);/*進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)*/ Critial_region2();/*臨界區(qū)臨界區(qū)*/ turn = 1;/*退出區(qū)退出區(qū)*/ other_region2();/*剩余區(qū)剩余區(qū)*/ 15 （2） Dekker算法算法:在嚴(yán)格輪換法的基礎(chǔ)上再引在嚴(yán)格輪換法的基礎(chǔ)上再引 入一個(gè)入一個(gè)警告變量警告變量 （3） Peterson算法算法 enum boolean false, true; Boolean flag2 = false, false; /*標(biāo)識(shí)數(shù)組標(biāo)識(shí)數(shù)組*/ Int turn; /*公共變量公共變量*/ 進(jìn)程進(jìn)

11、程1：while (TRUE) flag0 = true; /*進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)*/ turn = 2; /*進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)* while (flag1 /*進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)*/ Critial_region1(); /*臨界區(qū)臨界區(qū)*/ flag0 = false; /*退出區(qū)退出區(qū)*/ other_region1(); /*剩余區(qū)剩余區(qū)*/ 16 進(jìn)程進(jìn)程2： while (TRUE) flag1 = true; /*進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)*/ turn = 1; /*進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)*/ while (flag0 /*進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)*/ Critial_region2(); /*臨界區(qū)臨界區(qū)*/ flag1 =

12、false; /*退出區(qū)退出區(qū)*/ other_region2(); /*剩余區(qū)剩余區(qū)*/ 兩個(gè)進(jìn)程的兩個(gè)進(jìn)程的Peterson算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)： 17 3.2.2 硬件實(shí)現(xiàn)方法硬件實(shí)現(xiàn)方法 1、 關(guān)中斷關(guān)中斷 disable； /*關(guān)中斷，進(jìn)區(qū)關(guān)中斷，進(jìn)區(qū)*/ Critial_region();/*臨界區(qū)臨界區(qū)*/ enable；/*開(kāi)中斷，退出區(qū)開(kāi)中斷，退出區(qū)*/ other_region(); /*剩余區(qū)剩余區(qū)*/ 2、 使用測(cè)試和設(shè)置指令使用測(cè)試和設(shè)置指令 （TestAndSet） 用用C語(yǔ)言語(yǔ)言描述該指令描述該指令（當(dāng)臨（當(dāng)臨 界區(qū)被占用）界區(qū)被占用） TestAndSet(us

13、e) while (use = 1); use = 1; 進(jìn)程在退出區(qū)進(jìn)程在退出區(qū) boolean use = 0; /*初始資源空閑初始資源空閑*/ 進(jìn)程進(jìn)程i： TestAndSet(use); /*進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)*/ Critial_region();/*臨界區(qū)臨界區(qū)*/ use = 0;/*退出區(qū)退出區(qū)*/ other_region();/*剩余區(qū)剩余區(qū)*/ 18 3、使用對(duì)換指令（、使用對(duì)換指令（Swap） C語(yǔ)言描述語(yǔ)言描述 Swap( boolean *a, boolean *b) boolean temp; temp = *a; *a = *b; *b = temp; 對(duì)換指令對(duì)

14、換指令實(shí)現(xiàn)進(jìn)程互斥實(shí)現(xiàn)進(jìn)程互斥 boolean k = true; /*初始化為初始化為1*/ boolean use =false;/*初始資源空初始資源空 閑閑*/ while ( k != 0) Swap( /*進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)*/ Critial_region(); /*臨界區(qū)臨界區(qū)*/ use = 0; /*退出區(qū)退出區(qū)*/ other_region()； /*剩余區(qū)剩余區(qū)*/ 19 3.3進(jìn)程的同步進(jìn)程的同步 3.3.1同步的概念同步的概念 3.3.2同步的實(shí)現(xiàn)方法同步的實(shí)現(xiàn)方法 3.3.3 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 20 3.3.1同步的概念同步的概念 指兩個(gè)或多個(gè)進(jìn)程為了合

15、作完成同一個(gè)任務(wù)，基于指兩個(gè)或多個(gè)進(jìn)程為了合作完成同一個(gè)任務(wù)，基于 某個(gè)條件，在執(zhí)行速度或某些個(gè)確定的時(shí)序點(diǎn)上必須相某個(gè)條件，在執(zhí)行速度或某些個(gè)確定的時(shí)序點(diǎn)上必須相 互協(xié)調(diào)，存在依賴或相互依賴的關(guān)系。互協(xié)調(diào)，存在依賴或相互依賴的關(guān)系?；コ馐且环N特殊互斥是一種特殊 的同步。的同步。 21 3.3.2同步的實(shí)現(xiàn)方法同步的實(shí)現(xiàn)方法 由兩條進(jìn)程之間的通信原語(yǔ)組成：由兩條進(jìn)程之間的通信原語(yǔ)組成：sleep和和wakeup。 其描述如下：其描述如下： 進(jìn)程進(jìn)程1： /*其他代碼其他代碼*/ S1; /*S1語(yǔ)句，須在進(jìn)程語(yǔ)句，須在進(jìn)程2的的S2語(yǔ)句之前執(zhí)行語(yǔ)句之前執(zhí)行*/ wakeup(進(jìn)程進(jìn)程2); /

16、*喚醒進(jìn)程喚醒進(jìn)程2*/ /*其他代碼其他代碼*/ 進(jìn)程進(jìn)程2： /*其他代碼其他代碼*/ sleep; /*阻塞自己阻塞自己*/ S2; /*S2語(yǔ)句，須在進(jìn)程語(yǔ)句，須在進(jìn)程1的的S1語(yǔ)之后執(zhí)行語(yǔ)之后執(zhí)行*/ /*其他代碼其他代碼*/ 22 3.3.3 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 滿足兩個(gè)同步條件：滿足兩個(gè)同步條件： 第一，緩沖區(qū)中至少有一個(gè)消息，消費(fèi)者才能從中取第一，緩沖區(qū)中至少有一個(gè)消息，消費(fèi)者才能從中取 走消息；否則，消費(fèi)者必須等待（即阻塞）。走消息；否則，消費(fèi)者必須等待（即阻塞）。 第二，緩沖區(qū)未滿的情況下，生產(chǎn)者才能放入消息；第二，緩沖區(qū)未滿的情況下，生產(chǎn)者才能放入消息； 否

17、則，生產(chǎn)者必須等待，直到消費(fèi)者從中取走消息后將否則，生產(chǎn)者必須等待，直到消費(fèi)者從中取走消息后將 其喚醒。其喚醒。 23 #define N 10 /*緩沖區(qū)的大小緩沖區(qū)的大小*/ int count = 0 /*緩沖區(qū)中的消息數(shù)量緩沖區(qū)中的消息數(shù)量*/ void producer() /*生產(chǎn)者進(jìn)程生產(chǎn)者進(jìn)程*/ int information; while (true) /*無(wú)限循環(huán)無(wú)限循環(huán)*/ information = produce_new(); /*生產(chǎn)一個(gè)新產(chǎn)品生產(chǎn)一個(gè)新產(chǎn)品*/ if (count = N) sleep； /*若緩若緩 沖區(qū)已滿沖區(qū)已滿 ，休眠，休眠*/ inse

18、rt_new(); /*將新產(chǎn)品將新產(chǎn)品 放入緩沖區(qū)放入緩沖區(qū)*/ count = count + 1; /*緩沖區(qū)中的消息數(shù)量加緩沖區(qū)中的消息數(shù)量加1*/ if (count = 1) wakeup(consumer);/*若置入前緩沖區(qū)空，喚若置入前緩沖區(qū)空，喚 醒消費(fèi)者醒消費(fèi)者*/ 用用sleep和和wakeup原語(yǔ)來(lái)描述生產(chǎn)者原語(yǔ)來(lái)描述生產(chǎn)者消費(fèi)者問(wèn)題：消費(fèi)者問(wèn)題： 3.3.3 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 24 void consumer()/*消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程*/ int information; while (true) /*無(wú)限循環(huán)無(wú)限循環(huán)*/ if (count =

19、0) sleep;/*若緩沖區(qū)為空，休眠若緩沖區(qū)為空，休眠*/ information = remove ();/*從緩沖區(qū)取走一個(gè)產(chǎn)品從緩沖區(qū)取走一個(gè)產(chǎn)品*/ count = count - 1;/*緩沖區(qū)中的消息數(shù)量減緩沖區(qū)中的消息數(shù)量減1*/ if (count = N-1) wakeup(producer); /*若取走前緩沖若取走前緩沖 區(qū)滿，喚醒生產(chǎn)者區(qū)滿，喚醒生產(chǎn)者*/ consume_one();/*消費(fèi)一個(gè)產(chǎn)品消費(fèi)一個(gè)產(chǎn)品*/ 3.3.3 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 25 3.4 信號(hào)量信號(hào)量 3.4.1 信號(hào)量的原理信號(hào)量的原理 3.4.2 用信號(hào)量實(shí)現(xiàn)進(jìn)程的互斥用信

20、號(hào)量實(shí)現(xiàn)進(jìn)程的互斥 3.4.3 用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步 3.4.4 用信號(hào)量解決生產(chǎn)者用信號(hào)量解決生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 3.4.5 信號(hào)量小結(jié)及其不足信號(hào)量小結(jié)及其不足 26 信號(hào)量信號(hào)量(semaphore) 1965年，信號(hào)量及年，信號(hào)量及P、V原語(yǔ)由荷蘭學(xué)者原語(yǔ)由荷蘭學(xué)者Dijkstra 提出（提出（P、V分別是荷蘭語(yǔ)的分別是荷蘭語(yǔ)的test(proberen)和和 increment(verhogen)），是一種卓有成效的進(jìn)程互），是一種卓有成效的進(jìn)程互 斥和同步的機(jī)制。斥和同步的機(jī)制。 通常，信號(hào)量代表資源，信號(hào)量的值代表資源的通常，信號(hào)量代表資源，信號(hào)量

21、的值代表資源的 數(shù)目。數(shù)目。 本書將本書將P、原語(yǔ)分別稱為、原語(yǔ)分別稱為Down、Up操作，它們操作，它們 必須為原語(yǔ)。必須為原語(yǔ)。 27 3.4.1 信號(hào)量的原理信號(hào)量的原理 整形信號(hào)量整形信號(hào)量是一種特殊的是一種特殊的整型變量整型變量，被用于描述資源。，被用于描述資源。 信號(hào)量的值為信號(hào)量的值為整數(shù)，整數(shù)，代表系統(tǒng)擁有的資源的數(shù)目。代表系統(tǒng)擁有的資源的數(shù)目。 記錄型信號(hào)量記錄型信號(hào)量 包含兩個(gè)分量：包含兩個(gè)分量： value：通常用：通常用S.value表示，表示， 為為整數(shù)整數(shù)。 queue：通常用：通常用S.queue 表示，初值為表示，初值為空空。 28 Down和和Up操作操作 信

22、號(hào)量只能被信號(hào)量只能被Up和和Down使用。使用。 Up操作（代表釋放資源）：操作（代表釋放資源）： 1、S.value=S.value+1， 2、若、若S.value0，繼續(xù)執(zhí)行；否則，喚醒在，繼續(xù)執(zhí)行；否則，喚醒在S信號(hào)量的等待信號(hào)量的等待 隊(duì)列隊(duì)列S.queue中的第一個(gè)進(jìn)程或線程。中的第一個(gè)進(jìn)程或線程。 Down操作（代表申請(qǐng)資源）操作（代表申請(qǐng)資源） ： 1、S.value=S.value-1 2、若、若S.value大于或等于大于或等于0，繼續(xù)執(zhí)行；否則阻塞該進(jìn)程，繼續(xù)執(zhí)行；否則阻塞該進(jìn)程， 并將其插入到該信號(hào)量并將其插入到該信號(hào)量S的等待隊(duì)列的等待隊(duì)列S.queue的隊(duì)尾。的隊(duì)尾

23、。 29 信號(hào)量按其信號(hào)量按其取值分類取值分類： 1、二元信號(hào)量、二元信號(hào)量：僅允許信號(hào)量的取值為：僅允許信號(hào)量的取值為0或者或者1。 2、一般信號(hào)量、一般信號(hào)量：允許初值為：允許初值為非負(fù)整數(shù)非負(fù)整數(shù)。 信號(hào)量按信號(hào)量按用途分類用途分類： 1、私有信號(hào)量、私有信號(hào)量：指信號(hào)量是屬于某個(gè)進(jìn)程私有，并區(qū)分：指信號(hào)量是屬于某個(gè)進(jìn)程私有，并區(qū)分 信號(hào)量的擁有者和相關(guān)進(jìn)程對(duì)信號(hào)量的操作權(quán)限；初值常信號(hào)量的擁有者和相關(guān)進(jìn)程對(duì)信號(hào)量的操作權(quán)限；初值常 為為非負(fù)整數(shù)非負(fù)整數(shù)。 2、公有信號(hào)量、公有信號(hào)量：指信號(hào)量被所有的相關(guān)進(jìn)程所共享，所：指信號(hào)量被所有的相關(guān)進(jìn)程所共享，所 有相關(guān)進(jìn)程擁有對(duì)該信號(hào)量的相同的

24、操作權(quán)限初值為有相關(guān)進(jìn)程擁有對(duì)該信號(hào)量的相同的操作權(quán)限初值為1。 3.4.1 信號(hào)量的原理信號(hào)量的原理 30 設(shè)設(shè)S為互斥信號(hào)量為互斥信號(hào)量 初值初值1。 3.4.3 用信號(hào)量實(shí)現(xiàn)進(jìn)程的互斥用信號(hào)量實(shí)現(xiàn)進(jìn)程的互斥 31 Down(S) Up(S) P1P2P3 臨界區(qū)臨界區(qū) Down(S) Down(S) Up(S) Up(S) 3.4.3 用信號(hào)量實(shí)現(xiàn)進(jìn)程的互斥用信號(hào)量實(shí)現(xiàn)進(jìn)程的互斥 32 3.4.2 用信號(hào)量實(shí)現(xiàn)進(jìn)程的互斥用信號(hào)量實(shí)現(xiàn)進(jìn)程的互斥 用信號(hào)量解決進(jìn)程的互斥問(wèn)題的互斥模型如下：用信號(hào)量解決進(jìn)程的互斥問(wèn)題的互斥模型如下： Down(S); /*進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)*/ Critial_re

25、gion(); /*臨界區(qū)臨界區(qū)*/ Up(S); /*退出區(qū)退出區(qū)*/ Other_region(); /*剩余區(qū)剩余區(qū)*/ 33 3.4.3 用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步 Semaphore S=0; /*公共信號(hào)量初始化為公共信號(hào)量初始化為0*/ 進(jìn)程進(jìn)程1： /*其他代碼其他代碼*/ S1; /*S1語(yǔ)句，須在進(jìn)程語(yǔ)句，須在進(jìn)程2的的S2語(yǔ)句之前執(zhí)行語(yǔ)句之前執(zhí)行*/ Up(S);/*Up原語(yǔ)原語(yǔ)*/ /*其他代碼其他代碼*/ 進(jìn)程進(jìn)程2： /*其他代碼其他代碼*/ Down(S);/*Down原語(yǔ)原語(yǔ)*/ S2; /*S2語(yǔ)句，須在進(jìn)程語(yǔ)句，須在進(jìn)程1的的S1語(yǔ)句之后執(zhí)

26、行語(yǔ)句之后執(zhí)行*/ /*其他代碼其他代碼*/ 34 問(wèn)題描述：若干進(jìn)程通過(guò)有限的共享緩沖區(qū)交換問(wèn)題描述：若干進(jìn)程通過(guò)有限的共享緩沖區(qū)交換 數(shù)據(jù)。其中，數(shù)據(jù)。其中，“生產(chǎn)者生產(chǎn)者”進(jìn)程不斷寫入，而進(jìn)程不斷寫入，而“消費(fèi)者消費(fèi)者”進(jìn)進(jìn) 程不斷讀出；共享緩沖區(qū)共有程不斷讀出；共享緩沖區(qū)共有N個(gè)；任何時(shí)刻只能有個(gè)；任何時(shí)刻只能有 一個(gè)進(jìn)程可對(duì)共享緩沖區(qū)進(jìn)行操作。一個(gè)進(jìn)程可對(duì)共享緩沖區(qū)進(jìn)行操作。 共享緩沖區(qū) 生產(chǎn)指針消費(fèi)指針 Producer 1 Producer 2 . Producer M Consumer 1 Consumer 2 . Consumer N 滿 空 指針移動(dòng)方向 生產(chǎn)者生產(chǎn)者消費(fèi)者

27、問(wèn)題消費(fèi)者問(wèn)題 35 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 #define N 10 /*緩沖區(qū)的大小緩沖區(qū)的大小*/ Semaphore full=0 /*滿的緩沖區(qū)單元的個(gè)數(shù)滿的緩沖區(qū)單元的個(gè)數(shù)*/ Semaphore empty=N /*空的緩沖區(qū)單元的個(gè)數(shù)空的緩沖區(qū)單元的個(gè)數(shù)*/ Semaphore mutex=1 /*控制對(duì)緩沖區(qū)訪問(wèn)的互斥信號(hào)量控制對(duì)緩沖區(qū)訪問(wèn)的互斥信號(hào)量*/ void producer() /*生產(chǎn)者進(jìn)程生產(chǎn)者進(jìn)程*/ while (true) /*無(wú)限循環(huán)無(wú)限循環(huán)*/ produce_new(); /*生產(chǎn)一個(gè)新產(chǎn)品生產(chǎn)一個(gè)新產(chǎn)品*/ Down(empty); /*

28、申請(qǐng)一個(gè)空的緩沖區(qū)申請(qǐng)一個(gè)空的緩沖區(qū)*/ Down(mutex); /*申請(qǐng)?jiān)L問(wèn)臨界區(qū)申請(qǐng)?jiān)L問(wèn)臨界區(qū)*/ insert_new(); /*將新產(chǎn)品放入緩沖區(qū)將新產(chǎn)品放入緩沖區(qū)*/ Up(mutex); /*離開(kāi)臨界區(qū)離開(kāi)臨界區(qū)*/ Up(full)； /*遞增滿的緩沖區(qū)單元個(gè)數(shù)遞增滿的緩沖區(qū)單元個(gè)數(shù)*/ 36 void consumer() /*消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程*/ while (true) /*無(wú)限循環(huán)無(wú)限循環(huán)*/ Down(full); /*申請(qǐng)一個(gè)滿的申請(qǐng)一個(gè)滿的 緩沖區(qū)緩沖區(qū)*/ Down(mutex); /*申請(qǐng)?jiān)L問(wèn)臨界區(qū)申請(qǐng)?jiān)L問(wèn)臨界區(qū)*/ remove (); /*從緩沖區(qū)取走

29、一個(gè)產(chǎn)品從緩沖區(qū)取走一個(gè)產(chǎn)品*/ Up(mutex); /*離開(kāi)臨界區(qū)離開(kāi)臨界區(qū)*/ Up(empty); /*遞增空的緩沖區(qū)單元個(gè)數(shù)遞增空的緩沖區(qū)單元個(gè)數(shù)*/ consume_one(); /*消費(fèi)一個(gè)產(chǎn)品消費(fèi)一個(gè)產(chǎn)品*/ 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 37 嚴(yán)格的嚴(yán)格的Bernstein條件。條件。 互斥做得太過(guò)分了?；コ庾龅锰^(guò)分了。 N個(gè)進(jìn)程，可同時(shí)讀，不可同時(shí)寫讀、讀寫、個(gè)進(jìn)程，可同時(shí)讀，不可同時(shí)寫讀、讀寫、 寫寫。寫寫。 讀者讀者寫者問(wèn)題寫者問(wèn)題 38 問(wèn)題描述：?jiǎn)栴}描述： 有兩組并發(fā)進(jìn)程有兩組并發(fā)進(jìn)程: : 讀者和寫者讀者和寫者, ,共享一共享一 組數(shù)據(jù)區(qū)。組數(shù)據(jù)區(qū)。 要求：

30、要求： 允許多個(gè)讀者同時(shí)執(zhí)行讀操作；允許多個(gè)讀者同時(shí)執(zhí)行讀操作； 不允許讀者、寫者同時(shí)操作；不允許讀者、寫者同時(shí)操作； 不允許多個(gè)寫者同時(shí)操作。不允許多個(gè)寫者同時(shí)操作。 讀者讀者寫者問(wèn)題寫者問(wèn)題 39 如果讀者到：如果讀者到： 1 1）無(wú)讀者、寫者，新讀者可以讀；）無(wú)讀者、寫者，新讀者可以讀； 2 2）有寫者等，但有其它讀者正在讀，則新讀）有寫者等，但有其它讀者正在讀，則新讀 者也可以讀；者也可以讀； 3 3）有寫者寫，新讀者等。）有寫者寫，新讀者等。 如果寫者到：如果寫者到： 1 1）無(wú)讀者、寫者，新寫者可以寫；）無(wú)讀者、寫者，新寫者可以寫； 2 2）有讀者，新寫者等待；）有讀者，新寫者等待

31、； 3 3）有其它寫者，新寫者等待。）有其它寫者，新寫者等待。 讀者讀者寫者問(wèn)題寫者問(wèn)題 40 初值：初值： readcount=0(變量變量) w=1(信號(hào)量信號(hào)量) 讀者讀者寫者問(wèn)題寫者問(wèn)題 41 讀者：讀者： while (true) readcount +; if (readcount=1) Down(w); 讀讀 readcount -; if (readcount=0) Up(w); ; 寫者：寫者： while (true) Down(w); 寫寫 Up(w); ; 讀者讀者寫者問(wèn)題寫者問(wèn)題 42 初值：初值： readcount=0(變量變量) w=1(信號(hào)量信號(hào)量) mute

32、x=1 (信號(hào)量信號(hào)量) 讀者讀者寫者問(wèn)題寫者問(wèn)題 43 讀者：讀者： while (true) Down(mutex); readcount +; if (readcount=1) Down(w); Up(mutex); 讀讀 Down(mutex); readcount -; if (readcount=0) Up(w); Up(mutex); ; 寫者：寫者： while (true) Down(w); 寫寫 Up(w); ; 讀者讀者寫者問(wèn)題寫者問(wèn)題 44 問(wèn)題描述：?jiǎn)栴}描述： 有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人 面

33、前有一只空盤子，每?jī)扇酥g放一把叉子。面前有一只空盤子，每?jī)扇酥g放一把叉子。 每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉。每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉。 為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩把叉子，并且每個(gè)人為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩把叉子，并且每個(gè)人 只能直接從自己的左邊或右邊去取叉子。只能直接從自己的左邊或右邊去取叉子。 哲學(xué)家就餐問(wèn)題哲學(xué)家就餐問(wèn)題 45 哲學(xué)家就餐問(wèn)題哲學(xué)家就餐問(wèn)題 46 #define N 5 void philosopher (int i) while (true) 思考；思考； Down(forki); Down(fork(i+1)

34、% 5)； 進(jìn)食；進(jìn)食； Up(forki); Up(fork(i+1) % 5)； 哲學(xué)家就餐問(wèn)題哲學(xué)家就餐問(wèn)題 47 為防止死鎖發(fā)生可采取的措施：為防止死鎖發(fā)生可采取的措施： 最多允許最多允許4 4個(gè)哲學(xué)家同時(shí)坐在桌子周圍；個(gè)哲學(xué)家同時(shí)坐在桌子周圍； 僅當(dāng)一個(gè)哲學(xué)家左右兩邊的叉子都可用時(shí)，才允許僅當(dāng)一個(gè)哲學(xué)家左右兩邊的叉子都可用時(shí)，才允許 他拿叉子；他拿叉子； 給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿左給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿左 邊的叉子，偶數(shù)號(hào)的哲學(xué)家則反之；邊的叉子，偶數(shù)號(hào)的哲學(xué)家則反之； 為了避免死鎖，把哲學(xué)家分為三種狀態(tài)，思考，饑為了避免死鎖，把哲學(xué)家分為三種狀

35、態(tài)，思考，饑 餓，進(jìn)食，并且一次拿到兩把叉子，否則不拿。餓，進(jìn)食，并且一次拿到兩把叉子，否則不拿。 哲學(xué)家就餐問(wèn)題哲學(xué)家就餐問(wèn)題 48 3.4.5 信號(hào)量小結(jié)及其不足信號(hào)量小結(jié)及其不足 信號(hào)量以及信號(hào)量以及Up和和Down操作解決互斥問(wèn)題不會(huì)出現(xiàn)忙操作解決互斥問(wèn)題不會(huì)出現(xiàn)忙 等待，用于解決同步問(wèn)題不會(huì)丟失信號(hào)。等待，用于解決同步問(wèn)題不會(huì)丟失信號(hào)。 缺點(diǎn)：缺點(diǎn)： 第一，降低了通信效率；第一，降低了通信效率； 第二，增加了程序的復(fù)雜程度。第二，增加了程序的復(fù)雜程度。 49 3.5管程管程 3.5.1 管程的定義、結(jié)構(gòu)和原理管程的定義、結(jié)構(gòu)和原理 3.5.2 用管程解決生產(chǎn)者用管程解決生產(chǎn)者消費(fèi)者問(wèn)

36、題消費(fèi)者問(wèn)題 3.5.3 管程的不足管程的不足 50 3.5.1 管程的定義、結(jié)構(gòu)和原理管程的定義、結(jié)構(gòu)和原理 管程管程:關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)及一組針對(duì)該資源關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)及一組針對(duì)該資源 的操作過(guò)程所構(gòu)成的的操作過(guò)程所構(gòu)成的軟件模塊軟件模塊。由。由三個(gè)部分三個(gè)部分組成組成,模型模型 如下：如下： Monitor monitor_name /*管程名管程名*/ /*局部于管程的變量和數(shù)據(jù)結(jié)構(gòu)說(shuō)明局部于管程的變量和數(shù)據(jù)結(jié)構(gòu)說(shuō)明*/ define name1, name2, ; /*能被其他模塊引用的過(guò)程名列表能被其他模塊引用的過(guò)程名列表*/ use; /*引用的模塊外定義的過(guò)程名列表引

37、用的模塊外定義的過(guò)程名列表*/ Procedure P1 ( , 形式參數(shù)形式參數(shù), ) P1局部變量說(shuō)明；局部變量說(shuō)明； P1的過(guò)程體的過(guò)程體 51 Procedure P2 ( , 形式參數(shù)形式參數(shù), ) P2局部變量說(shuō)明；局部變量說(shuō)明； P2的過(guò)程體的過(guò)程體 Procedure Pn ( , 形式參數(shù)形式參數(shù), ) Pn局部變量說(shuō)明；局部變量說(shuō)明； Pn的過(guò)程體的過(guò)程體 Initialization code /*局部于管程的變量賦初值的語(yǔ)句局部于管程的變量賦初值的語(yǔ)句*/ 3.5.1 管程的定義、結(jié)構(gòu)和原理管程的定義、結(jié)構(gòu)和原理 52 如何通過(guò)管程來(lái)實(shí)現(xiàn)進(jìn)程的同步如何通過(guò)管程來(lái)實(shí)現(xiàn)進(jìn)程

38、的同步 : 管程中設(shè)置多個(gè)條件變量，對(duì)這些管程中設(shè)置多個(gè)條件變量，對(duì)這些條件變量條件變量的訪問(wèn)，的訪問(wèn)， 只能在管程中進(jìn)行，而且只能被只能在管程中進(jìn)行，而且只能被wait和和signal原語(yǔ)所訪原語(yǔ)所訪 問(wèn)。問(wèn)。 條件變量遵循條件變量遵循“先聲明，后使用先聲明，后使用”的原則的原則 條件變量、信號(hào)量的比較條件變量、信號(hào)量的比較 條件變量條件變量 信號(hào)量信號(hào)量 只能在管程中使用只能在管程中使用 被被wait和和signal原語(yǔ)操作原語(yǔ)操作 不能取任何值不能取任何值 signal原語(yǔ)原語(yǔ)不能累加不能累加 信號(hào)量可在進(jìn)程中使用信號(hào)量可在進(jìn)程中使用 被被Down和和Up原語(yǔ)操作原語(yǔ)操作 可以是個(gè)數(shù)可以

39、是個(gè)數(shù) Up原語(yǔ)原語(yǔ)不會(huì)丟失不會(huì)丟失 3.5.1 管程的定義、結(jié)構(gòu)和原理管程的定義、結(jié)構(gòu)和原理 53 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 往緩沖區(qū)送產(chǎn)品（往緩沖區(qū)送產(chǎn)品（put過(guò)程）、取走產(chǎn)品（過(guò)程）、取走產(chǎn)品（get過(guò)程）。過(guò)程）。 Monitor prod_con /*管程名管程名*/ char buffern; /*緩沖區(qū)緩沖區(qū)*/ int k; /*緩沖區(qū)中的產(chǎn)品個(gè)數(shù)緩沖區(qū)中的產(chǎn)品個(gè)數(shù)*/ int nextempty, nextfull; /*送或取產(chǎn)品的指針?biāo)突蛉‘a(chǎn)品的指針*/ condition nonempty,nonfull; /*條件變量條件變量*/ define put, g

40、et; /*管程中定義的過(guò)程說(shuō)明管程中定義的過(guò)程說(shuō)明*/ use wait(), signal(); /*引用外部模塊的過(guò)程說(shuō)明引用外部模塊的過(guò)程說(shuō)明*/ procedure put(char product) /*向緩沖區(qū)送產(chǎn)品的函數(shù)向緩沖區(qū)送產(chǎn)品的函數(shù)*/ if k=n then wait(nonfull); /*緩沖區(qū)滿，等待緩沖區(qū)滿，等待*/ buffernextempty = product; k=k+1; /*產(chǎn)品數(shù)加產(chǎn)品數(shù)加1*/ nextempty=(nextempty+1) mod n; signal(nonempty); /*喚醒等待取產(chǎn)品者（即消費(fèi)者喚醒等待取產(chǎn)品者（即消

41、費(fèi)者) */ 54 procedure get(item :goods) /*取產(chǎn)品的函數(shù)取產(chǎn)品的函數(shù)*/ if k=0 then wait(nonempty); /*緩沖區(qū)空等待緩沖區(qū)空等待*/ goods = buffernextfull; k=k-1; nextfull = (nextfull+1) mod n; signal(nonfull); /*喚醒等待送產(chǎn)品的生產(chǎn)者喚醒等待送產(chǎn)品的生產(chǎn)者*/ /*初始化初始化*/ k=0; nextempty=0; nextfull=0; 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 55 生產(chǎn)者和消費(fèi)者描述：生產(chǎn)者和消費(fèi)者描述： void producer

42、() /*生產(chǎn)者進(jìn)程生產(chǎn)者進(jìn)程*/ while (true) produce item; prod_con.put(item); void consumer() /*消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程*/ while (true) prod_con.get(item); consume item; 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 56 3.5.3 管程的不足管程的不足 第一，管程對(duì)編譯器的依賴性。管程需要編第一，管程對(duì)編譯器的依賴性。管程需要編 譯器把互斥原語(yǔ)加在管程的開(kāi)始和結(jié)尾。譯器把互斥原語(yǔ)加在管程的開(kāi)始和結(jié)尾。 第二，管程只能在單臺(tái)計(jì)算機(jī)上發(fā)揮效果。第二，管程只能在單臺(tái)計(jì)算機(jī)上發(fā)揮效果。 直接支持管

43、程的原語(yǔ)沒(méi)有提供機(jī)器之間的信息交直接支持管程的原語(yǔ)沒(méi)有提供機(jī)器之間的信息交 換方法。換方法。 57 3.6 進(jìn)程的高級(jí)通信進(jìn)程的高級(jí)通信 3.6.1消息緩沖機(jī)制消息緩沖機(jī)制 3.6.2郵箱機(jī)制郵箱機(jī)制 3.6.3共享存儲(chǔ)區(qū)共享存儲(chǔ)區(qū) 3.6.4管道管道 58 3.6.1消息緩沖機(jī)制消息緩沖機(jī)制 消息緩沖機(jī)制消息緩沖機(jī)制:包含包含發(fā)送者發(fā)送者和和接收者接收者，消息緩沖區(qū)消息緩沖區(qū)。 消息緩沖區(qū)描述為：消息緩沖區(qū)描述為： struct message_buffer sender；/* 發(fā)送進(jìn)程標(biāo)識(shí)符發(fā)送進(jìn)程標(biāo)識(shí)符*/ size；/* 消息長(zhǎng)度消息長(zhǎng)度*/ text； /*消息正文消息正文*/ st

44、ruct message_buffer *next； /*指向下一個(gè)消息緩沖區(qū)的指針指向下一個(gè)消息緩沖區(qū)的指針*/ 其次，修改進(jìn)程控制塊（其次，修改進(jìn)程控制塊（PCB），增加幾個(gè)字段：），增加幾個(gè)字段： struct PCB mq； /*消息隊(duì)列隊(duì)首指針消息隊(duì)列隊(duì)首指針*/ mutex； /*消息隊(duì)列互斥信號(hào)量消息隊(duì)列互斥信號(hào)量*/ sm； /*消息隊(duì)列消息個(gè)數(shù)信號(hào)量消息隊(duì)列消息個(gè)數(shù)信號(hào)量*/ 59 發(fā)送原語(yǔ)發(fā)送原語(yǔ)send()描述如下：描述如下： send(receiver, a) /*發(fā)送原語(yǔ)發(fā)送原語(yǔ)*/ getbuf(a.size, i)； /*據(jù)據(jù)a長(zhǎng)度申請(qǐng)一緩沖區(qū)長(zhǎng)度申請(qǐng)一緩沖區(qū)i*

45、/ i.sender=a.sender; i.size=a.size; i.text=a.text; i.next=0; getid(PCB set, receiver, j); /*獲得接收者的標(biāo)識(shí)獲得接收者的標(biāo)識(shí)j*/ Down(j.mutex); insert(j.mq, i); /*將將i掛在接收進(jìn)程掛在接收進(jìn)程j的消息隊(duì)列的消息隊(duì)列*/ Up(j.mutex); Up(j.sm); /*消息個(gè)數(shù)信號(hào)量消息個(gè)數(shù)信號(hào)量sm*/ 3.6.1消息緩沖機(jī)制消息緩沖機(jī)制 60 接收原語(yǔ)接收原語(yǔ)receive() 描述如下：描述如下： receive(b) /*接收原語(yǔ)，接收原語(yǔ)，b為接收區(qū)為接收

46、區(qū)*/ j=internal name; /*內(nèi)部標(biāo)識(shí)符內(nèi)部標(biāo)識(shí)符*/ Down(j.sm); /*等消息等消息*/ Down(j.mutex); remove(j.mq, i); /*從消息緩沖隊(duì)列摘下一個(gè)消息從消息緩沖隊(duì)列摘下一個(gè)消息i*/ Up(j.mutex); b.sender=i.sender; b.size=i.size; b.text=i.text; 3.6.1消息緩沖機(jī)制消息緩沖機(jī)制 61 3.6.2郵箱機(jī)制郵箱機(jī)制 郵箱是一種數(shù)據(jù)結(jié)構(gòu)，包括郵箱是一種數(shù)據(jù)結(jié)構(gòu)，包括郵箱頭郵箱頭和和郵箱郵箱 體體。郵箱體由若干格子組成，郵箱頭是郵箱的。郵箱體由若干格子組成，郵箱頭是郵箱的 描述

47、信息，包括郵箱名、郵箱大小、郵箱屬性描述信息，包括郵箱名、郵箱大小、郵箱屬性 、已存消息數(shù)、空格子數(shù)等、已存消息數(shù)、空格子數(shù)等 62 3.6.2郵箱機(jī)制郵箱機(jī)制 deposit(boxname, msg) /*投遞原語(yǔ)投遞原語(yǔ)*/ Down(emptynum); /*有空位有空位*/ 選擇標(biāo)志位為空的格子；選擇標(biāo)志位為空的格子； 把消息把消息msg放入該空的格子中；放入該空的格子中； 置該格子的標(biāo)志位為滿；置該格子的標(biāo)志位為滿； Up(mesnum); remove(boxname, msg) /*讀取原語(yǔ)讀取原語(yǔ)*/ Down (mesnum); /*有滿位有滿位*/ 選擇標(biāo)志位為滿的格子；

48、選擇標(biāo)志位為滿的格子； 把該格的消息放入把該格的消息放入msg中；中； 置該格子的標(biāo)志位為空；置該格子的標(biāo)志位為空； Up(emptynum); 63 3.6.3共享存儲(chǔ)區(qū)共享存儲(chǔ)區(qū) 指兩個(gè)（或多個(gè)）協(xié)作進(jìn)程指兩個(gè)（或多個(gè)）協(xié)作進(jìn)程共同擁有共同擁有同一片內(nèi)存，同一片內(nèi)存， 其中任何一個(gè)進(jìn)程都可以訪問(wèn)這片內(nèi)存中的任何內(nèi)容其中任何一個(gè)進(jìn)程都可以訪問(wèn)這片內(nèi)存中的任何內(nèi)容 。 物理內(nèi)存 進(jìn)程1 進(jìn)程2 共享內(nèi)存1私有數(shù)據(jù) 程序代碼程序代碼 共享內(nèi)存2共享內(nèi)存2共享內(nèi)存2 虛擬內(nèi)存虛擬內(nèi)存 私有數(shù)據(jù) 進(jìn)程3 共享內(nèi)存1 程序代碼 虛擬內(nèi)存 私有數(shù)據(jù) 共享內(nèi)存1 圖圖3.1 共享內(nèi)存共享內(nèi)存 64 3.6

49、.4管道管道 指能夠連接一個(gè)寫進(jìn)程和一個(gè)讀進(jìn)程、專門用于進(jìn)指能夠連接一個(gè)寫進(jìn)程和一個(gè)讀進(jìn)程、專門用于進(jìn) 程之間的數(shù)據(jù)通信的共享文件。也稱為程之間的數(shù)據(jù)通信的共享文件。也稱為pipe文件。文件。 1.無(wú)名管道：無(wú)名管道：利用系統(tǒng)調(diào)用利用系統(tǒng)調(diào)用pipe()建立的無(wú)路徑名的無(wú)名建立的無(wú)路徑名的無(wú)名 文件，屬文件，屬臨時(shí)文件臨時(shí)文件，在物理上則由文件系統(tǒng)的高速緩沖，在物理上則由文件系統(tǒng)的高速緩沖 區(qū)構(gòu)成。無(wú)名管道通信的進(jìn)程之間必須是區(qū)構(gòu)成。無(wú)名管道通信的進(jìn)程之間必須是父子關(guān)系父子關(guān)系 。 2.有名管道：有名管道：可以在文件系統(tǒng)中長(zhǎng)期存在的、具有路徑可以在文件系統(tǒng)中長(zhǎng)期存在的、具有路徑 名的名的真實(shí)的

50、文件真實(shí)的文件，不能與文件系統(tǒng)里的任何文件重名，從，不能與文件系統(tǒng)里的任何文件重名，從 文件系統(tǒng)也是可以看到有名管道的。需要先用文件系統(tǒng)也是可以看到有名管道的。需要先用Open系統(tǒng)系統(tǒng) 調(diào)用打開(kāi)?？捎糜谶M(jìn)程之間的本地通信，也可用于網(wǎng)絡(luò)環(huán)調(diào)用打開(kāi)。可用于進(jìn)程之間的本地通信，也可用于網(wǎng)絡(luò)環(huán) 境下的不同機(jī)器之間的進(jìn)程間的通信。境下的不同機(jī)器之間的進(jìn)程間的通信。 65 寫寫 端端 讀讀 端端 fd1 write(fd1,buf,size) fd0 read(fd0,buf,size) pipe(fd) 為建立管道的進(jìn)程及其子孫進(jìn)程提供了一為建立管道的進(jìn)程及其子孫進(jìn)程提供了一 條以比特流方式傳送消息的通

51、信管道。條以比特流方式傳送消息的通信管道。 用用C語(yǔ)言編寫一個(gè)程序，建立一個(gè)語(yǔ)言編寫一個(gè)程序，建立一個(gè)pipe；父；父 進(jìn)程生成一個(gè)子進(jìn)程，子進(jìn)程向進(jìn)程生成一個(gè)子進(jìn)程，子進(jìn)程向pipe中寫入一中寫入一 個(gè)字符串，父進(jìn)程從個(gè)字符串，父進(jìn)程從pipe中讀出該字符串。中讀出該字符串。 3.6.4管道管道 #include Main() int x, fd2; char buf30, s30 pipe (fd); /* 創(chuàng)建管道創(chuàng)建管道 */ while (x=fork() = -1); /* 創(chuàng)建子進(jìn)程失敗時(shí)，循環(huán)創(chuàng)建子進(jìn)程失敗時(shí)，循環(huán) */ if (x = 0) /*子進(jìn)程子進(jìn)程*/ sprint

52、f (buf, “This is an examplen”); write (fd1, buf, 30); /* 把把buf中的字符串寫入管道中的字符串寫入管道 */ exit(0); else /* 父進(jìn)程父進(jìn)程*/ wait (0); read (fd0, s, 30); /* 父進(jìn)程讀管道中的字符串父進(jìn)程讀管道中的字符串*/ printf(“%s”,s); #include /*父進(jìn)程軌跡父進(jìn)程軌跡*/ Main() int x, fd2; char buf30, s30 pipe (fd); while (x=fork() = -1); if (x = 0) /* 子進(jìn)程子進(jìn)程*/ s

53、printf (buf, “This is an examplen”); write (fd1, buf, 30); exit(0); else /* 父進(jìn)程父進(jìn)程*/ wait (0); read (fd0, s, 30); printf(“%s”,s); #include /*子進(jìn)程軌跡子進(jìn)程軌跡*/ Main() int x, fd2; char buf30, s30 pipe (fd); while (x=fork() = -1); if (x = 0) /* 子進(jìn)程子進(jìn)程*/ sprintf (buf, “This is an examplen”); write (fd1, buf,

54、 30); exit(0); else /* 父進(jìn)程父進(jìn)程*/ wait (0); read (fd0, s, 30); printf(“%s”,s); 68 3.7死鎖死鎖 3.7.1什么是死鎖什么是死鎖 3.7.2死鎖的表示死鎖的表示 3.7.3死鎖的檢測(cè)和清除死鎖的檢測(cè)和清除 3.7.4死鎖的預(yù)防死鎖的預(yù)防 3.7.5死鎖的避免死鎖的避免 69 3.7.1什么是死鎖什么是死鎖 圖圖3.2 交通死鎖交通死鎖 死鎖：死鎖：兩個(gè)或兩個(gè)以上的進(jìn)程中的每一個(gè)進(jìn)程都在等待兩個(gè)或兩個(gè)以上的進(jìn)程中的每一個(gè)進(jìn)程都在等待 其中另一個(gè)進(jìn)程釋放資源而無(wú)法前進(jìn)的現(xiàn)象，而且等待其中另一個(gè)進(jìn)程釋放資源而無(wú)法前進(jìn)的現(xiàn)象

55、，而且等待 的資源系統(tǒng)已無(wú)法再提供（由于已被占用）、也無(wú)法由的資源系統(tǒng)已無(wú)法再提供（由于已被占用）、也無(wú)法由 這些進(jìn)程以外的其他進(jìn)程提供或者釋放。這些進(jìn)程以外的其他進(jìn)程提供或者釋放。 70 死鎖：死鎖：有一組并發(fā)進(jìn)程有一組并發(fā)進(jìn)程P1，P2，Pn，它們共享，它們共享 資源資源R1，R2，Rm(n1，m0，n m)；其中，；其中， 每個(gè)每個(gè)Pi(1in)擁有資源擁有資源Rj(1jm)，直到不再有剩余資，直到不再有剩余資 源；同時(shí)，各源；同時(shí)，各Pi又在不釋放又在不釋放Rj的前提下要求得到的前提下要求得到 Rk(kj，1km)，從而造成資源的相互占有和相互等，從而造成資源的相互占有和相互等 待。待

56、。 產(chǎn)生死鎖的產(chǎn)生死鎖的4個(gè)必要條件個(gè)必要條件： （1）互斥條件）互斥條件 （2）保持與等待條件（）保持與等待條件（部分分配條件部分分配條件） （3）不可搶占條件）不可搶占條件 （4）循環(huán)等待條件）循環(huán)等待條件 3.7.1什么是死鎖什么是死鎖 71 3.7.2死鎖的表示死鎖的表示 系統(tǒng)資源分配圖：系統(tǒng)資源分配圖：可定義為一個(gè)二元組，即可定義為一個(gè)二元組，即RAG=(V, E)，其中，其中V是頂點(diǎn)的集合，是頂點(diǎn)的集合，E是有向邊的集合。是有向邊的集合。 V 1、P=P1, P2, , Pn 由系統(tǒng)內(nèi)的進(jìn)程組成由系統(tǒng)內(nèi)的進(jìn)程組成 2、R=R1, R2, , Rm 由系統(tǒng)內(nèi)的所有資源組成由系統(tǒng)內(nèi)的所

57、有資源組成 (a)申請(qǐng)邊(b)分配邊 申請(qǐng)分配 進(jìn)程 進(jìn)程 資源 資源 圖圖3.3 申請(qǐng)邊和分配邊申請(qǐng)邊和分配邊 72 （1）系統(tǒng)資源分配圖中沒(méi)有環(huán)路，則系統(tǒng)沒(méi)有死鎖。）系統(tǒng)資源分配圖中沒(méi)有環(huán)路，則系統(tǒng)沒(méi)有死鎖。 （2）若出現(xiàn)了環(huán)路，且處于此環(huán)路中的每類資源均只）若出現(xiàn)了環(huán)路，且處于此環(huán)路中的每類資源均只 有一個(gè)實(shí)例時(shí)，則有環(huán)路就有死鎖。有一個(gè)實(shí)例時(shí)，則有環(huán)路就有死鎖。 （3）若出現(xiàn)了環(huán)路，但此環(huán)路中的每類資源的個(gè)數(shù)）若出現(xiàn)了環(huán)路，但此環(huán)路中的每類資源的個(gè)數(shù)不不 全為全為1，則環(huán)路的存在只是死鎖產(chǎn)生的必要條件而非，則環(huán)路的存在只是死鎖產(chǎn)生的必要條件而非 充分條件。充分條件。 (a)有死鎖(b)

58、無(wú)死鎖 進(jìn)程1 資源2 進(jìn)程2 資源1 進(jìn)程1 資源2 進(jìn)程2 資源1 圖圖3.4 資源分配圖的例子資源分配圖的例子 死鎖定理死鎖定理 73 由于有環(huán)路時(shí)既可能發(fā)生死鎖，也可能沒(méi)有死鎖。由于有環(huán)路時(shí)既可能發(fā)生死鎖，也可能沒(méi)有死鎖。 資源分配圖的化簡(jiǎn)法用來(lái)判斷系統(tǒng)是否發(fā)生死鎖。資源分配圖的化簡(jiǎn)法用來(lái)判斷系統(tǒng)是否發(fā)生死鎖。 具體步驟如下：具體步驟如下： （1）釋放資源。）釋放資源。 （2）分配資源。）分配資源。 （3）重復(fù)化簡(jiǎn)。）重復(fù)化簡(jiǎn)。 經(jīng)過(guò)化簡(jiǎn)法化簡(jiǎn)后，若所有的進(jìn)程都成為了孤立經(jīng)過(guò)化簡(jiǎn)法化簡(jiǎn)后，若所有的進(jìn)程都成為了孤立 結(jié)點(diǎn)，則稱該資源分配圖是可完全化簡(jiǎn)的，系統(tǒng)必結(jié)點(diǎn)，則稱該資源分配圖是可完

59、全化簡(jiǎn)的，系統(tǒng)必 定沒(méi)有死鎖；否則為不可化簡(jiǎn)的，系統(tǒng)必定處于死定沒(méi)有死鎖；否則為不可化簡(jiǎn)的，系統(tǒng)必定處于死 鎖狀態(tài)。鎖狀態(tài)。 資源分配圖的簡(jiǎn)化資源分配圖的簡(jiǎn)化 74 3.7.3死鎖的檢測(cè)和清除死鎖的檢測(cè)和清除 死鎖檢測(cè)的數(shù)據(jù)結(jié)構(gòu)：死鎖檢測(cè)的數(shù)據(jù)結(jié)構(gòu)： 1.向量向量Resource = (R1, R2, , Rm ) 用于表示系統(tǒng)用于表示系統(tǒng) 現(xiàn)有的資源總數(shù)；現(xiàn)有的資源總數(shù)； 2.向量向量Available = (V1, V2, , Vm ) 用于表示系統(tǒng)用于表示系統(tǒng) 當(dāng)前可供使用的資源總數(shù)；當(dāng)前可供使用的資源總數(shù)； 3.向量向量Process = (P1, P2, , Pn ) 用于表示用于表

60、示n個(gè)進(jìn)個(gè)進(jìn) 程被標(biāo)記的情況；程被標(biāo)記的情況； 75 3.7.3死鎖的檢測(cè)和清除死鎖的檢測(cè)和清除 4.矩陣矩陣 其中矩陣元素其中矩陣元素Aij表示第表示第i號(hào)進(jìn)程當(dāng)前分配到第號(hào)進(jìn)程當(dāng)前分配到第j類資源類資源 的數(shù)目；的數(shù)目； 5.矩陣矩陣 其中矩陣元素其中矩陣元素Rij表示第表示第i號(hào)進(jìn)程當(dāng)前請(qǐng)求第號(hào)進(jìn)程當(dāng)前請(qǐng)求第j類資源的類資源的 數(shù)目。數(shù)目。 nmnn m m AAA AAA AAA Allocation . . . . 21 22221 11211 nmnn m m RRR RRR RRR Request . . . . 21 22221 11211 76 死鎖檢測(cè)算法：死鎖檢測(cè)算法：