第三講進(jìn)程通信與控制

1、.1第三講 進(jìn)程同步與通信 目的與要求：了解并發(fā)程序的高級(jí)語(yǔ)言表示目的與要求：了解并發(fā)程序的高級(jí)語(yǔ)言表示與操作系統(tǒng)支持下的實(shí)現(xiàn)；同步與互斥問(wèn)題。與操作系統(tǒng)支持下的實(shí)現(xiàn)；同步與互斥問(wèn)題。重點(diǎn)與難點(diǎn)：并發(fā)程序中的同步與互斥重點(diǎn)與難點(diǎn)：并發(fā)程序中的同步與互斥.2并發(fā)與并行的區(qū)別并發(fā)并發(fā)是指多個(gè)任務(wù)在單處理機(jī)下分時(shí)運(yùn)行，是指多個(gè)任務(wù)在單處理機(jī)下分時(shí)運(yùn)行，從宏觀上看它們同時(shí)都在向前推進(jìn)，但從從宏觀上看它們同時(shí)都在向前推進(jìn)，但從微觀上來(lái)看，它們正在分時(shí)地輪流使用處微觀上來(lái)看，它們正在分時(shí)地輪流使用處理機(jī)。理機(jī)。并行并行是指多個(gè)任務(wù)在多個(gè)處理機(jī)上正在同是指多個(gè)任務(wù)在多個(gè)處理機(jī)上正在同時(shí)運(yùn)行，從微觀上看這些任

2、務(wù)分別是在各時(shí)運(yùn)行，從微觀上看這些任務(wù)分別是在各自的物理處理機(jī)上分別運(yùn)行。自的物理處理機(jī)上分別運(yùn)行。.33.1 并發(fā)原理1、并發(fā)帶來(lái)的問(wèn)題一個(gè)簡(jiǎn)單的例子一個(gè)簡(jiǎn)單的例子（ECHOECHO（回顯）是一個(gè)共享程（回顯）是一個(gè)共享程序）序）Void echo( )Void echo( )char out,in;char out,in; cinin; cinin; Out=in; Out=in; coutout; coutin; cinin; Out=in; Out=in; Coutout; Coutin; Cinin; Out=in; Out=in; Coutout; Coutin; Cinin; O

3、ut=in; Out=in; Coutout; Cout=1) X1X1-1： AjX1； 輸出一張票輸出一張票 else 輸出輸出“票售完票售完” void T2（X2） 按旅客訂票要求找到按旅客訂票要求找到AjX2Aj； if (X2 =1) X2X2-1： AjX2； 輸出一張票輸出一張票 else輸出輸出“票售完票售完” .11考慮以下的執(zhí)行次序:(a)和(b)按按(a)的序列執(zhí)行時(shí)，結(jié)果是正確的。按的序列執(zhí)行時(shí)，結(jié)果是正確的。按(b)的序列執(zhí)行情況，則兩個(gè)旅客可的序列執(zhí)行情況，則兩個(gè)旅客可能各自都買到一張同天同次航班的機(jī)票，可是，能各自都買到一張同天同次航班的機(jī)票，可是，Aj的值實(shí)際

4、上只減去了的值實(shí)際上只減去了1,造造成余票數(shù)的不正確。成余票數(shù)的不正確。設(shè)設(shè)Aj=50則則x1=50此時(shí)此時(shí)x2=50此時(shí)此時(shí)x1=49此時(shí)此時(shí)x2=49此時(shí)此時(shí)Aj=49此時(shí)此時(shí)Aj=49.12特別是，當(dāng)某次航班只有一張余票時(shí)，就可能把特別是，當(dāng)某次航班只有一張余票時(shí)，就可能把這一張票同時(shí)售給了兩位旅客，顯然這是不能允許的。這一張票同時(shí)售給了兩位旅客，顯然這是不能允許的。設(shè)設(shè)Aj=1則則x1=1此時(shí)此時(shí)x2=1此時(shí)此時(shí)x1=0此時(shí)此時(shí)x2=0此時(shí)此時(shí)Aj=0此時(shí)此時(shí)Aj=0.13出錯(cuò)原因是什么？出錯(cuò)原因是什么？余票額是共享變量！沒(méi)有建立對(duì)共享變量余票額是共享變量！沒(méi)有建立對(duì)共享變量的使用與保

5、護(hù)機(jī)制。的使用與保護(hù)機(jī)制。 由以上的例子說(shuō)明什么？由以上的例子說(shuō)明什么？ 要想實(shí)現(xiàn)多道程序并發(fā)執(zhí)行，必須設(shè)法對(duì)要想實(shí)現(xiàn)多道程序并發(fā)執(zhí)行，必須設(shè)法對(duì)共享變量（資源）加入一定的管理機(jī)制和共享變量（資源）加入一定的管理機(jī)制和一定的保護(hù)措施，保證共享資源的一定的保護(hù)措施，保證共享資源的協(xié)調(diào)使協(xié)調(diào)使用用，以避免出現(xiàn)與時(shí)間有關(guān)的錯(cuò)誤，以保，以避免出現(xiàn)與時(shí)間有關(guān)的錯(cuò)誤，以保持并發(fā)程序的可再現(xiàn)性。持并發(fā)程序的可再現(xiàn)性。.14思考：對(duì)共享變量（資源）如何加思考：對(duì)共享變量（資源）如何加上這種規(guī)則（機(jī)制）呢？上這種規(guī)則（機(jī)制）呢？這是這是現(xiàn)代操作系統(tǒng)必須解決的核心問(wèn)題！現(xiàn)代操作系統(tǒng)必須解決的核心問(wèn)題！同步機(jī)制：信

6、號(hào)傳遞？同步機(jī)制：信號(hào)傳遞？互斥機(jī)制：加鎖？互斥機(jī)制：加鎖？.15同步關(guān)系同步關(guān)系（亦稱直接制約關(guān)系）（亦稱直接制約關(guān)系）: : 指完成同一任務(wù)的伙伴進(jìn)程間，因需指完成同一任務(wù)的伙伴進(jìn)程間，因需要在某些位置上協(xié)調(diào)它們的工作而相互等要在某些位置上協(xié)調(diào)它們的工作而相互等待、相互交換信息所產(chǎn)生的制約關(guān)系。待、相互交換信息所產(chǎn)生的制約關(guān)系。如：如：接力跑比賽中，運(yùn)動(dòng)員之間要配合默接力跑比賽中，運(yùn)動(dòng)員之間要配合默契。一棒一棒接著跑。契。一棒一棒接著跑。3.2 進(jìn)程的互斥與同步.16例例 ：在計(jì)算機(jī)系統(tǒng)中對(duì)同一緩沖區(qū)的：在計(jì)算機(jī)系統(tǒng)中對(duì)同一緩沖區(qū)的數(shù)據(jù)的輸入與輸出操作。緩沖區(qū)滿才能輸數(shù)據(jù)的輸入與輸出操作。

7、緩沖區(qū)滿才能輸出，緩沖區(qū)空才能輸入。出，緩沖區(qū)空才能輸入。 緩沖區(qū)緩沖區(qū)輸入輸入進(jìn)程進(jìn)程輸出輸出進(jìn)程進(jìn)程.17互斥關(guān)系互斥關(guān)系（亦稱間接制約關(guān)系）（亦稱間接制約關(guān)系）: : 即進(jìn)程間因相互競(jìng)爭(zhēng)使用獨(dú)占型資即進(jìn)程間因相互競(jìng)爭(zhēng)使用獨(dú)占型資源（互斥資源）所產(chǎn)生的制約關(guān)系。源（互斥資源）所產(chǎn)生的制約關(guān)系。例（例（1 1）：上例中）：上例中ECHOECHO程序中的變量程序中的變量OUTOUT和和ININ，例（例（2 2）：飛機(jī)訂票系統(tǒng)中的余票額）：飛機(jī)訂票系統(tǒng)中的余票額AjAj必必須互斥使用。須互斥使用。例（例（3 3）：多個(gè)用戶進(jìn)程同用一臺(tái)打印機(jī)）：多個(gè)用戶進(jìn)程同用一臺(tái)打印機(jī)時(shí)。時(shí)。.18 既同步又要

8、互斥的例子：既同步又要互斥的例子：1 1、客車上的司機(jī)和售票員各司其職、客車上的司機(jī)和售票員各司其職為完成同一個(gè)運(yùn)送乘客的任務(wù)相互配為完成同一個(gè)運(yùn)送乘客的任務(wù)相互配合。合?；コ猓核緳C(jī)開(kāi)車時(shí)售票員不要開(kāi)門，互斥：司機(jī)開(kāi)車時(shí)售票員不要開(kāi)門，售票員開(kāi)門時(shí)司機(jī)不要開(kāi)車；售票員開(kāi)門時(shí)司機(jī)不要開(kāi)車；同步：司機(jī)停車時(shí)售票員才能開(kāi)門，同步：司機(jī)停車時(shí)售票員才能開(kāi)門，售票員關(guān)門時(shí)司機(jī)才能開(kāi)車）。售票員關(guān)門時(shí)司機(jī)才能開(kāi)車）。.19正常行車正常行車到站停車到站停車啟動(dòng)汽車啟動(dòng)汽車售票售票開(kāi)車門開(kāi)車門關(guān)車門關(guān)車門司機(jī)進(jìn)程司機(jī)進(jìn)程售票員進(jìn)程售票員進(jìn)程.20互斥與同步的例子：互斥與同步的例子：2 2、有限緩沖區(qū)問(wèn)題。互斥

9、：存時(shí)不要、有限緩沖區(qū)問(wèn)題?；コ猓捍鏁r(shí)不要取，取時(shí)不要存。同步：有數(shù)據(jù)才能取，取時(shí)不要存。同步：有數(shù)據(jù)才能取，有空區(qū)才能存。取，有空區(qū)才能存。PkP2C1C2CmP1存存取取.21互斥與同步的例子：互斥與同步的例子：3 3、讀者與寫者問(wèn)題。、讀者與寫者問(wèn)題。（Readers/WritersReaders/Writers問(wèn)題）問(wèn)題）4 4、哲學(xué)家就餐問(wèn)題。（就餐和思考、哲學(xué)家就餐問(wèn)題。（就餐和思考需同步與互斥）需同步與互斥）.22一一、兩個(gè)基本概念：、兩個(gè)基本概念：臨界資源臨界資源（critical resource）：一次僅允）：一次僅允許一個(gè)進(jìn)程使用的資源。許一個(gè)進(jìn)程使用的資源。如：上例如：

10、上例ECHO程序中的共享變量程序中的共享變量IN，OUT,飛機(jī)訂票系統(tǒng)的余票額飛機(jī)訂票系統(tǒng)的余票額Aj等。等。3.3 3.3 臨界資源和臨界區(qū)臨界資源和臨界區(qū).23臨界段（區(qū)）臨界段（區(qū)）（critical section) ：各進(jìn)程：各進(jìn)程必須互斥執(zhí)行的程序段。必須互斥執(zhí)行的程序段。如：飛機(jī)余票額如：飛機(jī)余票額Aj的操作的程序段。的操作的程序段。.24u二、臨界資源須互斥使用例例1 1打印機(jī)：打印機(jī)： P1,P2P1,P2兩進(jìn)程使用同一打印機(jī)。兩進(jìn)程使用同一打印機(jī)。如果不互斥使用會(huì)交叉輸出。如果不互斥使用會(huì)交叉輸出。 例例2 2共享變量：共享變量：共享變量是臨界資源。共享變量是臨界資源。 .

11、25Cobegin void A( ) N=count; N=N+100; count=N; ; void B( ) M=count; M=M+200; count=M; ;Coend;如下例對(duì)共享變量如下例對(duì)共享變量countcount的互斥訪問(wèn)。的互斥訪問(wèn)?；コ鈭?zhí)行互斥執(zhí)行例例:若若count為為300,如互斥執(zhí)如互斥執(zhí)行結(jié)果行結(jié)果count為為600,臨界區(qū)臨界區(qū)臨界區(qū)臨界區(qū).26Cobegin void A( ) N=count; N=N+100; count=N; ; void B( ) M=count; M=M+200; count=M; ;Coend;若不互斥若不互斥,可能結(jié)果為

12、可能結(jié)果為500.（設(shè)（設(shè)count初值為初值為300）不互斥執(zhí)行不互斥執(zhí)行設(shè)設(shè)A在此處中斷，在此處中斷，執(zhí)行完執(zhí)行完B.27三、進(jìn)程互斥進(jìn)入臨界區(qū)的一般結(jié)構(gòu)三、進(jìn)程互斥進(jìn)入臨界區(qū)的一般結(jié)構(gòu) 進(jìn)入臨界段之前要申請(qǐng)，獲得批進(jìn)入臨界段之前要申請(qǐng)，獲得批準(zhǔn)方可進(jìn)入；準(zhǔn)方可進(jìn)入； 退出臨界段之后要聲明，以便其退出臨界段之后要聲明，以便其他進(jìn)程進(jìn)入。他進(jìn)程進(jìn)入。While( 1 ) 進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) 臨界區(qū)臨界區(qū)退出區(qū)退出區(qū) 剩余區(qū)（其余代碼）剩余區(qū)（其余代碼） ;.28Cobegin void A( ) N=count; N=N+100; count=N; ; void B( ) M=count; M=M

13、+200; count=M; ;Coend;例如上例對(duì)共享變量例如上例對(duì)共享變量countcount的互斥訪問(wèn)。的互斥訪問(wèn)。臨界區(qū)臨界區(qū)臨界區(qū)臨界區(qū)Entry code(Entry code(請(qǐng)求獨(dú)占請(qǐng)求獨(dú)占) )exit code(exit code(釋放釋放) )Entry code(Entry code(請(qǐng)求獨(dú)占請(qǐng)求獨(dú)占) )exit code(exit code(釋放釋放) ).29例如：對(duì)打印機(jī)（臨界資源）的互斥使用例如：對(duì)打印機(jī)（臨界資源）的互斥使用Entry code(Entry code(請(qǐng)求獨(dú)占請(qǐng)求獨(dú)占) )exit code(exit code(釋釋放放) )使用打印機(jī)的程

14、序段使用打印機(jī)的程序段P1P1臨界區(qū)臨界區(qū)Entry code(Entry code(請(qǐng)求獨(dú)占請(qǐng)求獨(dú)占) )exit code(exit code(釋釋放放) )使用打印機(jī)的程序段使用打印機(jī)的程序段P2P2臨界區(qū)臨界區(qū)臨界資源臨界資源.30四、臨界區(qū)進(jìn)入準(zhǔn)則（同步機(jī)制）四、臨界區(qū)進(jìn)入準(zhǔn)則（同步機(jī)制）準(zhǔn)則準(zhǔn)則1 1：空閑讓進(jìn)。若無(wú)進(jìn)程進(jìn)入空閑空閑讓進(jìn)。若無(wú)進(jìn)程進(jìn)入空閑的臨界區(qū)，一次僅允許一個(gè)進(jìn)程進(jìn)入。的臨界區(qū)，一次僅允許一個(gè)進(jìn)程進(jìn)入。準(zhǔn)則準(zhǔn)則2 2：忙則等待。任何時(shí)候，處于臨忙則等待。任何時(shí)候，處于臨界區(qū)內(nèi)的進(jìn)程不可多于一個(gè)，如果已有界區(qū)內(nèi)的進(jìn)程不可多于一個(gè)，如果已有進(jìn)程進(jìn)入自己的臨界區(qū)，則其他

15、進(jìn)程必進(jìn)程進(jìn)入自己的臨界區(qū)，則其他進(jìn)程必須等待。須等待。.31準(zhǔn)則準(zhǔn)則3 3：有限等待。進(jìn)入臨界區(qū)的進(jìn)程有限等待。進(jìn)入臨界區(qū)的進(jìn)程要在有限時(shí)間內(nèi)退出，以便其他進(jìn)程及要在有限時(shí)間內(nèi)退出，以便其他進(jìn)程及時(shí)進(jìn)入自己的臨界區(qū)。時(shí)進(jìn)入自己的臨界區(qū)。準(zhǔn)則準(zhǔn)則4 4：讓權(quán)等待。如果進(jìn)程不能進(jìn)入讓權(quán)等待。如果進(jìn)程不能進(jìn)入自己的臨界區(qū)，則應(yīng)讓出自己的臨界區(qū)，則應(yīng)讓出CPUCPU，避免進(jìn)程，避免進(jìn)程出現(xiàn)出現(xiàn)“忙等忙等”現(xiàn)象。現(xiàn)象。.323.4 互斥實(shí)現(xiàn)方法互斥實(shí)現(xiàn)方法一、利用硬件方法解決進(jìn)程互斥問(wèn)題一、利用硬件方法解決進(jìn)程互斥問(wèn)題1 1、 禁止中斷禁止中斷臨界段不能被中斷，以保證互斥。臨界段不能被中斷，以保證互斥

16、。while(1)while(1) ; ; ; 缺點(diǎn)缺點(diǎn)：（：（1 1）代價(jià)較高，執(zhí)行效率低；）代價(jià)較高，執(zhí)行效率低；（2 2）不能用于多處理機(jī)系統(tǒng)。）不能用于多處理機(jī)系統(tǒng)。.332 2、專用機(jī)器指令、專用機(jī)器指令（1 1）“Test and Set”Test and Set”指令指令該指令功能描述為：該指令功能描述為：int ts(static int lock)int ts(static int lock) int ts=lock; int ts=lock; lock=1; lock=1;return(ts);return(ts); 這里：這里：tsts函數(shù)作為一個(gè)原語(yǔ)執(zhí)行（即不存在函數(shù)作

17、為一個(gè)原語(yǔ)執(zhí)行（即不存在中斷）。中斷）。locklock有兩種狀態(tài)：當(dāng)有兩種狀態(tài)：當(dāng)lock=0lock=0時(shí)，時(shí)，表示該資源空閑；當(dāng)表示該資源空閑；當(dāng)lock=1lock=1時(shí)，表示該資源正時(shí)，表示該資源正在被使用。在被使用。.34 例例1：利用：利用testset指令實(shí)現(xiàn)互斥的循環(huán)進(jìn)程描述：指令實(shí)現(xiàn)互斥的循環(huán)進(jìn)程描述：P(i):While(1) while (ts(lock) No-op; ; lock=0; Main( ) lock=0; cobegin p(1);P(2);P(n);coend .假設(shè)進(jìn)程假設(shè)進(jìn)程P2欲進(jìn)程臨界區(qū)，調(diào)用過(guò)欲進(jìn)程臨界區(qū)，調(diào)用過(guò)程程P（2），執(zhí)行），執(zhí)行ts

18、(lock)后返回后返回ts為假，并置為假，并置lock=1,故故P2進(jìn)入進(jìn)入臨界區(qū)，若此時(shí)有進(jìn)程臨界區(qū)，若此時(shí)有進(jìn)程P1欲進(jìn)入臨欲進(jìn)入臨界區(qū)，調(diào)用界區(qū)，調(diào)用P(1),執(zhí)行測(cè)試執(zhí)行測(cè)試ts(lock),因因lock為為1，故，故ts返回真，故返回真，故P1被拒絕進(jìn)入臨界區(qū)。被拒絕進(jìn)入臨界區(qū)。.35（2 2）SwapSwap指令實(shí)現(xiàn)進(jìn)程指令實(shí)現(xiàn)進(jìn)程該指令功能描述為：該指令功能描述為：void swapvoid swap（static int a,bstatic int a,b）；）；int tempint temp；temp=atemp=a；a=ba=b；b=tempb=temp； 這里，這里，

19、SWAPSWAP指令也是原語(yǔ)。指令也是原語(yǔ)。在利用在利用SwapSwap實(shí)現(xiàn)進(jìn)程互斥時(shí)，可為臨界資源設(shè)置一個(gè)實(shí)現(xiàn)進(jìn)程互斥時(shí)，可為臨界資源設(shè)置一個(gè)全局變量全局變量locklock，其初值為，其初值為0 0，在每個(gè)進(jìn)程中再利，在每個(gè)進(jìn)程中再利用一個(gè)局部變量用一個(gè)局部變量keykey。然后通過(guò)。然后通過(guò)swapswap指令實(shí)現(xiàn)互指令實(shí)現(xiàn)互斥。斥。.36例例2：利用：利用swap指令實(shí)現(xiàn)互斥的描述指令實(shí)現(xiàn)互斥的描述.37 P(I)：/*I為進(jìn)程號(hào)，如為為進(jìn)程號(hào)，如為P（2）為進(jìn)程）為進(jìn)程P2調(diào)用調(diào)用While(1)Keyi=1;Do s); while (keyi); ; lock=0; Main(

20、) lock=0; cobegin p(1);P(2);P(n); coend例：例：P2先調(diào)用先調(diào)用P過(guò)程，則此時(shí)過(guò)程，則此時(shí)lock=1,Key2=0,P2進(jìn)入臨界區(qū)。當(dāng)進(jìn)入臨界區(qū)。當(dāng)P2正在臨正在臨界區(qū)時(shí)，若有另一進(jìn)程又想進(jìn)入臨界區(qū)時(shí)，若有另一進(jìn)程又想進(jìn)入臨界區(qū)，執(zhí)行界區(qū)，執(zhí)行P（1），此時(shí)），此時(shí)key1=1,lock=1,兩者交換還是兩者交換還是1，故，故P1只能只能循環(huán)等待。直至循環(huán)等待。直至P2退出臨界區(qū)，交退出臨界區(qū)，交換使換使lock=0為止。為止。.38v3、使用特殊機(jī)器指令實(shí)現(xiàn)互斥的優(yōu)缺點(diǎn)、使用特殊機(jī)器指令實(shí)現(xiàn)互斥的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：優(yōu)點(diǎn)：（1）可用于：含有任意數(shù)量進(jìn)程的單處理

21、）可用于：含有任意數(shù)量進(jìn)程的單處理機(jī)或共享主存的多處理機(jī)；機(jī)或共享主存的多處理機(jī)；（2）比較簡(jiǎn)單，易于驗(yàn)證；）比較簡(jiǎn)單，易于驗(yàn)證；（3）可支持多個(gè)臨界段，每個(gè)臨界段用各）可支持多個(gè)臨界段，每個(gè)臨界段用各自的變量加以定義。如自的變量加以定義。如lock變量的改變。變量的改變。.39缺點(diǎn)：缺點(diǎn)：（1）由于采用忙碌由于采用忙碌-等待等待(死等，一直循環(huán)判死等，一直循環(huán)判斷等待，等到可以進(jìn)入臨界區(qū)為止斷等待，等到可以進(jìn)入臨界區(qū)為止)，所以在，所以在進(jìn)程等待進(jìn)入臨界段時(shí)，將耗費(fèi)處理機(jī)時(shí)間。進(jìn)程等待進(jìn)入臨界段時(shí)，將耗費(fèi)處理機(jī)時(shí)間。（2）有可能產(chǎn)生饑餓。）有可能產(chǎn)生饑餓。（3）有可能產(chǎn)生死鎖。如：）有可能產(chǎn)

22、生死鎖。如：P1在執(zhí)行在執(zhí)行TS或或SWAP指令時(shí)，擁有更高優(yōu)先級(jí)的進(jìn)程指令時(shí)，擁有更高優(yōu)先級(jí)的進(jìn)程P2中中斷斷P1，并且，并且P2又要使用又要使用P1所占用的資源。所占用的資源。.40二、利用軟件方法解決進(jìn)程互斥問(wèn)題二、利用軟件方法解決進(jìn)程互斥問(wèn)題假如有假如有2 2個(gè)進(jìn)程個(gè)進(jìn)程P1P1和和P2P2，它們共享一個(gè)臨界資，它們共享一個(gè)臨界資源源R R，則，則P1P1與與P2P2并發(fā)執(zhí)行，并發(fā)執(zhí)行，P1P1與與P2P2互斥使用互斥使用R R。并發(fā)執(zhí)行的程序段如下：并發(fā)執(zhí)行的程序段如下：mainmain（）（）cobegin cobegin p1p1；p2p2； .41互斥執(zhí)行的程序段用軟件實(shí)現(xiàn)?；?/p>

23、斥執(zhí)行的程序段用軟件實(shí)現(xiàn)。算法算法1 1（單標(biāo)志算法）（單標(biāo)志算法）我們?cè)O(shè)置一個(gè)公用整型變量我們?cè)O(shè)置一個(gè)公用整型變量turnturn，用于指示被允許進(jìn)入臨界區(qū)的進(jìn)程的用于指示被允許進(jìn)入臨界區(qū)的進(jìn)程的編號(hào)，即若編號(hào)，即若turn=1turn=1，表示允許進(jìn)程，表示允許進(jìn)程P1P1進(jìn)入臨界區(qū)。算法進(jìn)入臨界區(qū)。算法1 1對(duì)對(duì)P1P1、P2P2進(jìn)程的描進(jìn)程的描述如下：述如下：.42P1P1：whilewhile（1 1） whilewhile（turnturn！1 1） no-opno-op； critical sectioncritical sectionturnturn2 2； P2P2：whil

24、ewhile（1 1） whilewhile（turnturn！2 2） no-opno-op； critical sectioncritical sectionturnturn1 1； 測(cè)試自己能測(cè)試自己能否進(jìn)入臨界否進(jìn)入臨界區(qū)區(qū)把臨界區(qū)使把臨界區(qū)使用權(quán)交給用權(quán)交給P2P2.43對(duì)算法一的評(píng)價(jià)：對(duì)算法一的評(píng)價(jià)：該算法可確保每次只允許一個(gè)進(jìn)程進(jìn)該算法可確保每次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)。入臨界區(qū)。2 2個(gè)進(jìn)程是輪流地進(jìn)入臨界區(qū)。個(gè)進(jìn)程是輪流地進(jìn)入臨界區(qū)。不能保證實(shí)現(xiàn)不能保證實(shí)現(xiàn)“空閑讓進(jìn)空閑讓進(jìn)”的準(zhǔn)則。的準(zhǔn)則。 如當(dāng)進(jìn)程如當(dāng)進(jìn)程P2P2暫時(shí)并未要求訪問(wèn)該臨暫時(shí)并未要求訪問(wèn)該臨界資源，而界資源，

25、而P1P1又想再次訪問(wèn)該資源，但又想再次訪問(wèn)該資源，但它卻無(wú)法進(jìn)入臨界區(qū)。它卻無(wú)法進(jìn)入臨界區(qū)。.44算法算法2 2（雙標(biāo)志、先檢查算法）（雙標(biāo)志、先檢查算法）基本思想：在每一個(gè)進(jìn)程訪問(wèn)臨界資源基本思想：在每一個(gè)進(jìn)程訪問(wèn)臨界資源之前，先去查看一下臨界資源是否正被之前，先去查看一下臨界資源是否正被訪問(wèn)。若正被訪問(wèn)，該進(jìn)程需等待；否訪問(wèn)。若正被訪問(wèn)，該進(jìn)程需等待；否則進(jìn)入自己的臨界區(qū)。為此，設(shè)置一個(gè)則進(jìn)入自己的臨界區(qū)。為此，設(shè)置一個(gè)數(shù)組，使其中每個(gè)元素的初值為數(shù)組，使其中每個(gè)元素的初值為0 0，表示，表示所有進(jìn)程都未進(jìn)入臨界區(qū)。若所有進(jìn)程都未進(jìn)入臨界區(qū)。若flag0=1flag0=1時(shí)，表示進(jìn)程時(shí)，

26、表示進(jìn)程P1P1正在臨界區(qū)內(nèi)執(zhí)行；若正在臨界區(qū)內(nèi)執(zhí)行；若且且flag1= 1flag1= 1時(shí)，表示進(jìn)程時(shí)，表示進(jìn)程P2P2正在臨界正在臨界區(qū)內(nèi)執(zhí)行。算法區(qū)內(nèi)執(zhí)行。算法2 2的描述如下：的描述如下：.45Int flag2=0Int flag2=0，00；P1P1：whilewhile（1 1） while while（flag1flag1） no-opno-op； flag0=1flag0=1； critical sectioncritical section flag0=0 flag0=0； P2P2：whilewhile（1 1） while while（flag0flag0） no-o

27、pno-op； flag1=1flag1=1； critical sectioncritical section flag1=0 flag1=0； 測(cè)試對(duì)方是測(cè)試對(duì)方是否在臨界區(qū)，否在臨界區(qū)，如果在，在如果在，在此循環(huán)等待此循環(huán)等待如果對(duì)方不如果對(duì)方不在臨界區(qū)，在臨界區(qū)，自己進(jìn)入臨自己進(jìn)入臨界區(qū)界區(qū).46對(duì)算法對(duì)算法2 2的評(píng)價(jià)：的評(píng)價(jià)：算法算法2 2解決了有空讓進(jìn)的問(wèn)題。解決了有空讓進(jìn)的問(wèn)題。違背了違背了“忙則等待忙則等待”的準(zhǔn)則。即的準(zhǔn)則。即當(dāng)當(dāng)P1P1和和P2P2都未進(jìn)入臨界區(qū)時(shí)，它們各自都未進(jìn)入臨界區(qū)時(shí)，它們各自的訪問(wèn)標(biāo)志都為的訪問(wèn)標(biāo)志都為0.0.如果如果P1P1和和P2P2幾乎是在幾

28、乎是在同時(shí)都要求進(jìn)入臨界區(qū)，因而都發(fā)現(xiàn)對(duì)同時(shí)都要求進(jìn)入臨界區(qū)，因而都發(fā)現(xiàn)對(duì)方的訪問(wèn)標(biāo)志方的訪問(wèn)標(biāo)志flagflag為為0 0。于是。于是2 2個(gè)進(jìn)程都個(gè)進(jìn)程都先后進(jìn)入臨界區(qū)，顯然，這時(shí)又違背了先后進(jìn)入臨界區(qū)，顯然，這時(shí)又違背了“忙則等待忙則等待”的準(zhǔn)則。的準(zhǔn)則。.47算法算法3 3（雙標(biāo)志、先修改后檢查算法）（雙標(biāo)志、先修改后檢查算法） 算法算法3 3中仍然使用了數(shù)組中仍然使用了數(shù)組flag flag ，但但flag0=1flag0=1表示進(jìn)程表示進(jìn)程P1P1希望進(jìn)入臨界區(qū)，希望進(jìn)入臨界區(qū)，然后再去查看然后再去查看P2P2的標(biāo)志。若此時(shí)的標(biāo)志。若此時(shí)flag1=1flag1=1，則，則P1P1

29、等待；否則，等待；否則，P1P1進(jìn)入臨進(jìn)入臨界區(qū)；對(duì)于進(jìn)程界區(qū)；對(duì)于進(jìn)程P2P2亦然。亦然。.48Int flag2=0Int flag2=0，00；P1P1：whilewhile（1 1） Flag0=1 Flag0=1； whilewhile（flag1flag1） no-opno-op； critical sectioncritical section flag0=0 flag0=0； P2P2：whilewhile（1 1） Flag1=1 Flag1=1； whilewhile（flag0flag0） no-opno-op； critical sectioncritical sect

30、ion flag1=0 flag1=0； 測(cè)試對(duì)方是測(cè)試對(duì)方是否在臨界區(qū)否在臨界區(qū).49對(duì)算法對(duì)算法3 3的評(píng)價(jià)：的評(píng)價(jià)：算法算法3 3又會(huì)造成最終誰(shuí)都不能進(jìn)入臨又會(huì)造成最終誰(shuí)都不能進(jìn)入臨界區(qū)的后果。因而它既違背了界區(qū)的后果。因而它既違背了“有空讓進(jìn)有空讓進(jìn)”的準(zhǔn)則的準(zhǔn)則1 1，又違背了，又違背了“有限等待有限等待”的準(zhǔn)則的準(zhǔn)則3 3。例如，當(dāng)例如，當(dāng)P1P1和和P2P2幾乎在同時(shí)要進(jìn)入臨界區(qū)，幾乎在同時(shí)要進(jìn)入臨界區(qū)，雙方都在雙方都在“謙讓謙讓”，結(jié)果誰(shuí)也進(jìn)不了臨界，結(jié)果誰(shuí)也進(jìn)不了臨界區(qū)。區(qū)。 .50算法算法4 4（先修改、后檢查、后修改者等待（先修改、后檢查、后修改者等待算法）算法）Int

31、flag2=0Int flag2=0，00；P1:whileP1:while（1 1）Flag0=1Flag0=1；turn=2turn=2；While(flag1&turn=2While(flag1&turn=2） no-opno-op； critical sectioncritical section Flag0=0 Flag0=0； P2P2：whilewhile（1 1）Flag1=1Flag1=1；turn=1turn=1；While(flag0&turn=1While(flag0&turn=1） no-opno-op； critical sectio

32、ncritical section Flag1=0 Flag1=0； .51評(píng)價(jià)：該算法是組合了算法評(píng)價(jià)：該算法是組合了算法1 1和算法和算法3 3中的中的關(guān)鍵概念而形成的，保證了關(guān)鍵概念而形成的，保證了“忙則等待忙則等待”，又實(shí)現(xiàn)了又實(shí)現(xiàn)了“有空讓進(jìn)有空讓進(jìn)”。Int flag2=0Int flag2=0，00；P1:whileP1:while（1 1）Flag0=1Flag0=1；turn=2turn=2；While(flag1&turn=2While(flag1&turn=2） no-opno-op； critical sectioncritical section Fl

33、ag0=0 Flag0=0； P2P2：whilewhile（1 1）Flag1=1Flag1=1；turn=1turn=1；While(flag0&turn=1While(flag0&turn=1） no-opno-op； critical sectioncritical section Flag1=0 Flag1=0； .523.5. 3.5. 信號(hào)量和信號(hào)量和PVPV操作操作(semaphore)(semaphore) 由于實(shí)現(xiàn)互斥的軟件方法和硬件方法都存由于實(shí)現(xiàn)互斥的軟件方法和硬件方法都存在缺陷，故需要尋找其他機(jī)制。現(xiàn)寄希望于在缺陷，故需要尋找其他機(jī)制?，F(xiàn)寄希望于操作系

34、統(tǒng)和程序設(shè)計(jì)提供對(duì)并發(fā)的支持。操作系統(tǒng)和程序設(shè)計(jì)提供對(duì)并發(fā)的支持。（信號(hào)量、管程、消息傳遞）（信號(hào)量、管程、消息傳遞）信號(hào)量機(jī)制是一種卓有成效的解決進(jìn)程同步信號(hào)量機(jī)制是一種卓有成效的解決進(jìn)程同步問(wèn)題的工具。問(wèn)題的工具。.53一、一、信號(hào)量的定義信號(hào)量的定義信號(hào)量一般由兩個(gè)成員組成。其中一個(gè)信號(hào)量一般由兩個(gè)成員組成。其中一個(gè)成員為整型變量，表示該信號(hào)量的值；成員為整型變量，表示該信號(hào)量的值；另一個(gè)是指向另一個(gè)是指向PCBPCB的指針。的指針。.54信號(hào)量的信號(hào)量的C C語(yǔ)言描述如下：語(yǔ)言描述如下：struct semaphoreint value;/信號(hào)量的值域信號(hào)量的值域struct PCB

35、*queue; /* *queuequeue為等待進(jìn)程鏈表指針為等待進(jìn)程鏈表指針S;信號(hào)量變量信號(hào)量變量S S的值只能通過(guò)的值只能通過(guò)P P、V V操作操作來(lái)改變它。來(lái)改變它。.55二、二、P P和和V V操作原語(yǔ)的偽代碼形式如下：操作原語(yǔ)的偽代碼形式如下：P操作操作(或或wait操作操作)描述：描述：Void P(semaphore S) S.value-; if (s.value0)Block(S.queue );V操作操作(或或singal操作操作)描述：描述：Void V(semaphore S)s.value+;if (s.value=0)wakeup(S.queue); 通過(guò)對(duì)信號(hào)

36、量做通過(guò)對(duì)信號(hào)量做P P、V V操作來(lái)實(shí)現(xiàn)互斥操作來(lái)實(shí)現(xiàn)互斥訪問(wèn)臨界區(qū)。訪問(wèn)臨界區(qū)。.56三、三、N N個(gè)進(jìn)程利用信號(hào)量、個(gè)進(jìn)程利用信號(hào)量、PVPV操作互操作互斥使用臨界段的一般結(jié)構(gòu)：斥使用臨界段的一般結(jié)構(gòu)：設(shè)互斥信號(hào)量設(shè)互斥信號(hào)量S S的初值為的初值為1 1 P(S) P(S)V(S)V(S)臨界區(qū)臨界區(qū)非臨界段非臨界段Do while(1)臨界資源臨界資源如打印機(jī)如打印機(jī)S.value-; if S.value-; if (S.value0)(S.value0) Block(S.L ) Block(S.L )S.value+;S.value+;if(S.value=0)if(S.value

37、=0,s.value=0,則該進(jìn)程繼續(xù)執(zhí)行；則該進(jìn)程繼續(xù)執(zhí)行；如果如果s.value0,s.value0,s.value0,則該進(jìn)程繼續(xù)執(zhí)則該進(jìn)程繼續(xù)執(zhí)行；（行；（S0S0說(shuō)明等待隊(duì)列說(shuō)明等待隊(duì)列queuequeue中無(wú)等待的中無(wú)等待的進(jìn)程）進(jìn)程） 如果如果s.value=0,s.value=0,則釋放信號(hào)量則釋放信號(hào)量隊(duì)列隊(duì)列L L上的第一個(gè)上的第一個(gè)PCBPCB所對(duì)應(yīng)的進(jìn)程（把阻所對(duì)應(yīng)的進(jìn)程（把阻塞態(tài)改為就緒態(tài)），執(zhí)行塞態(tài)改為就緒態(tài)），執(zhí)行V V操作的進(jìn)程繼續(xù)操作的進(jìn)程繼續(xù)執(zhí)行。執(zhí)行。.61五、五、信號(hào)量機(jī)制物理含義信號(hào)量機(jī)制物理含義1 1、信號(hào)量初值、信號(hào)量初值S.valueS.valu

38、e表示系統(tǒng)中某種資表示系統(tǒng)中某種資源的數(shù)目，又稱資源信息量。源的數(shù)目，又稱資源信息量。2 2、執(zhí)行一次、執(zhí)行一次P P操作意味著請(qǐng)求分配一個(gè)單操作意味著請(qǐng)求分配一個(gè)單位資源，因此位資源，因此S.valueS.value的值減的值減1 1；當(dāng)當(dāng)S.value0S.value0S.value0時(shí)時(shí), ,表示等待隊(duì)列無(wú)等待該表示等待隊(duì)列無(wú)等待該信號(hào)量的進(jìn)程信號(hào)量的進(jìn)程, ,其值表示還可用的資源數(shù)其值表示還可用的資源數(shù)目目. .做做P P操作的進(jìn)程繼續(xù)執(zhí)行操作的進(jìn)程繼續(xù)執(zhí)行. .623 3、執(zhí)行一次、執(zhí)行一次V V操作意味著釋放一個(gè)單位資源，操作意味著釋放一個(gè)單位資源，因此因此S.valueS.val

39、ue的值加的值加1 1；若若s.value=0s.value0s.value0時(shí)時(shí), ,表示等待隊(duì)列無(wú)等待該表示等待隊(duì)列無(wú)等待該信號(hào)量的進(jìn)程信號(hào)量的進(jìn)程, ,其值表示還可用的資源數(shù)其值表示還可用的資源數(shù)目目. .做做V V操作的進(jìn)程繼續(xù)執(zhí)行。操作的進(jìn)程繼續(xù)執(zhí)行。.63六、信號(hào)量的一般應(yīng)用u1 1、用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥、用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥要使要使N N個(gè)進(jìn)程互斥使用某臨界資源（如打印個(gè)進(jìn)程互斥使用某臨界資源（如打印機(jī)），只要在每個(gè)進(jìn)程的使用臨界資源的臨機(jī)），只要在每個(gè)進(jìn)程的使用臨界資源的臨界區(qū)（即程序段）前加界區(qū)（即程序段）前加P P操作，退出臨界區(qū)前操作，退出臨界區(qū)前加加V V操作，并且操作

40、，并且n n個(gè)個(gè)進(jìn)程共享一個(gè)互斥信號(hào)量進(jìn)程共享一個(gè)互斥信號(hào)量S,S,初值為初值為1 1（即只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)）。（即只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)）。.64例例1：進(jìn)程：進(jìn)程Pa（分配進(jìn)程）和（分配進(jìn)程）和Pb（釋放進(jìn)程）（釋放進(jìn)程）對(duì)某一打印機(jī)分配表的互斥使用情況，可用信對(duì)某一打印機(jī)分配表的互斥使用情況，可用信號(hào)量實(shí)現(xiàn)。設(shè)互斥信號(hào)量號(hào)量實(shí)現(xiàn)。設(shè)互斥信號(hào)量mutex，其初值為，其初值為1。則則Pa和和Pb的臨界區(qū)代碼可按下述方式組織：的臨界區(qū)代碼可按下述方式組織：Pa:P(mutex)分配打印機(jī)分配打印機(jī)（讀寫分配表）（讀寫分配表）V(mutex) Pb:P(mutex)釋放打印機(jī)釋放打印機(jī)（

41、讀寫分配表）（讀寫分配表）V(mutex) mutex.value-; if (mutex.value0)Block(mutex.L );mutex.value+;if (mutex.value=1) Ri:=Ri-1; Aj:=Ri;V(S);輸出一張票；輸出一張票； else V(S); 輸出輸出“票已售完票已售完”； ;/*過(guò)程結(jié)束過(guò)程結(jié)束 cobegin P(1),P(2),P(n).66u2 2、用信號(hào)量實(shí)現(xiàn)進(jìn)程同步、用信號(hào)量實(shí)現(xiàn)進(jìn)程同步u根據(jù)信號(hào)量的初值，在某個(gè)進(jìn)程根據(jù)信號(hào)量的初值，在某個(gè)進(jìn)程的程序段的程序段前前加加P P操作，在另一個(gè)的操作，在另一個(gè)的程序段程序段后后加加V V操

42、作操作.67例例2 2、有有P1,P2 P1,P2 兩進(jìn)程，必須在兩進(jìn)程，必須在P P1 1執(zhí)行完執(zhí)行完S1S1語(yǔ)句后，語(yǔ)句后，P2P2才能執(zhí)行才能執(zhí)行S2S2。請(qǐng)用。請(qǐng)用PVPV操作實(shí)現(xiàn)同步操作實(shí)現(xiàn)同步（需同步的兩進(jìn)程共享信號(hào)量（需同步的兩進(jìn)程共享信號(hào)量s s，初值為，初值為0 0。）。）P2: P1: S1;V(s); P(s);S2;.68例例2 2、有有P1,P2 P1,P2 兩進(jìn)程，必須在兩進(jìn)程，必須在P P1 1執(zhí)行完執(zhí)行完S1S1語(yǔ)句后，語(yǔ)句后，P2P2才能執(zhí)行才能執(zhí)行S2S2。請(qǐng)用。請(qǐng)用PVPV操作實(shí)現(xiàn)同步操作實(shí)現(xiàn)同步（需同步的兩進(jìn)程共享信號(hào)量（需同步的兩進(jìn)程共享信號(hào)量s s，

43、初值為，初值為0 0。）。）P2: P1: S1;V(s); P(s);S2;信號(hào)量初值為信號(hào)量初值為0，則，則P2不可能不可能先執(zhí)行，因?yàn)閳?zhí)行先執(zhí)行，因?yàn)閳?zhí)行P（s）操作）操作時(shí)，時(shí)，S=-1=n) notfull.wait;Bufferin=nextp;In=(in+1) mod n;Count+;If notempty.queue notempty.signal;Entyp get(item) if (count=0) notempty.wait; nextc=bufferout; out=(out+1) mod n; count-; If notfull.queue notfull.s

44、ignal; csignal(notfull); in=out=0; count=0;共享變量共享變量說(shuō)明說(shuō)明放產(chǎn)品放產(chǎn)品過(guò)程過(guò)程取產(chǎn)品過(guò)取產(chǎn)品過(guò)程程局部變量置局部變量置初值初值如果緩如果緩沖池已沖池已滿，放滿，放產(chǎn)品過(guò)產(chǎn)品過(guò)程入等程入等待隊(duì)列待隊(duì)列如果等如果等待取的待取的隊(duì)列中隊(duì)列中有進(jìn)程，有進(jìn)程，則喚醒則喚醒如無(wú)產(chǎn)品如無(wú)產(chǎn)品可取，則可取，則該進(jìn)程進(jìn)該進(jìn)程進(jìn)入等待隊(duì)入等待隊(duì)列列如果等如果等待放的待放的隊(duì)列中隊(duì)列中有進(jìn)程，有進(jìn)程，則喚醒則喚醒.109Void producer( ) while(1) produce an item in nextp; producer-consumer.put

45、(item); Void consumer( ) while(1) producer-consumer.get(item);Consume the item in nextc; ;Main ( ) Cobegin producer( );consumer( ); . .110三、管程與進(jìn)程的異同三、管程與進(jìn)程的異同(1)二者都定義了數(shù)據(jù)結(jié)構(gòu)。進(jìn)程定義的是私有二者都定義了數(shù)據(jù)結(jié)構(gòu)。進(jìn)程定義的是私有數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)PCB,管程定義的是公共數(shù)據(jù)結(jié)構(gòu)，如管程定義的是公共數(shù)據(jù)結(jié)構(gòu)，如消息隊(duì)列。消息隊(duì)列。 (2)二者都在各自的數(shù)據(jù)結(jié)構(gòu)上進(jìn)行有意義的操二者都在各自的數(shù)據(jù)結(jié)構(gòu)上進(jìn)行有意義的操作。進(jìn)程是由順序程

46、序執(zhí)行有關(guān)操作，管程主作。進(jìn)程是由順序程序執(zhí)行有關(guān)操作，管程主要是進(jìn)行同步操作和初啟操作。要是進(jìn)行同步操作和初啟操作。 (3)二者設(shè)置的目的不同。進(jìn)程是為了更好地實(shí)二者設(shè)置的目的不同。進(jìn)程是為了更好地實(shí)現(xiàn)系統(tǒng)的并發(fā)性而設(shè)置的，管程是為了解決進(jìn)現(xiàn)系統(tǒng)的并發(fā)性而設(shè)置的，管程是為了解決進(jìn)程的公共變量，為了解決共享資源的互斥使用程的公共變量，為了解決共享資源的互斥使用問(wèn)題而設(shè)置的。問(wèn)題而設(shè)置的。 .111（4）進(jìn)程通過(guò)調(diào)用管程中的過(guò)程對(duì)共享變量）進(jìn)程通過(guò)調(diào)用管程中的過(guò)程對(duì)共享變量實(shí)行操作。此時(shí)，該過(guò)程就如通常的子程序一實(shí)行操作。此時(shí)，該過(guò)程就如通常的子程序一樣被調(diào)用而處于被動(dòng)工作方式，因此，稱管程樣被

47、調(diào)用而處于被動(dòng)工作方式，因此，稱管程為被動(dòng)成分。與此相對(duì)應(yīng)的進(jìn)程則處于主動(dòng)工為被動(dòng)成分。與此相對(duì)應(yīng)的進(jìn)程則處于主動(dòng)工作方式而被稱為主動(dòng)成分。作方式而被稱為主動(dòng)成分。（5）由于進(jìn)程是主動(dòng)成分，故進(jìn)程之間能被）由于進(jìn)程是主動(dòng)成分，故進(jìn)程之間能被并發(fā)執(zhí)行，然而管程是被動(dòng)成分，管程和調(diào)用并發(fā)執(zhí)行，然而管程是被動(dòng)成分，管程和調(diào)用它的進(jìn)程不能并發(fā)執(zhí)行。它的進(jìn)程不能并發(fā)執(zhí)行。 （6）進(jìn)程可由）進(jìn)程可由“創(chuàng)建創(chuàng)建”而誕生，由而誕生，由“撤消撤消”而消亡，有生命期，管程是操作系統(tǒng)中的固有而消亡，有生命期，管程是操作系統(tǒng)中的固有成分，無(wú)需進(jìn)程創(chuàng)建，也不能為進(jìn)程所撤消，成分，無(wú)需進(jìn)程創(chuàng)建，也不能為進(jìn)程所撤消，只能被

48、進(jìn)程調(diào)用。只能被進(jìn)程調(diào)用。.1123.5 進(jìn)程通信一、進(jìn)程通信的概念與類型一、進(jìn)程通信的概念與類型1 1、概念、概念進(jìn)程通信指進(jìn)程之間的信息交換。進(jìn)程通信指進(jìn)程之間的信息交換。2 2、類型。依據(jù)交換信息量的多少。、類型。依據(jù)交換信息量的多少。（1 1）低級(jí)通信。如進(jìn)程的同步與）低級(jí)通信。如進(jìn)程的同步與互斥的信號(hào)量機(jī)制。特點(diǎn)：互斥的信號(hào)量機(jī)制。特點(diǎn)：一是效率低一是效率低二是通信對(duì)用戶不透明。二是通信對(duì)用戶不透明。.113（2 2）高級(jí)通信。指用戶可直接通）高級(jí)通信。指用戶可直接通過(guò)操作系統(tǒng)提供的一組通信命令高效過(guò)操作系統(tǒng)提供的一組通信命令高效地傳送大量數(shù)據(jù)的一種通信方式。特地傳送大量數(shù)據(jù)的一種通

49、信方式。特點(diǎn)：點(diǎn)：一是效率高。一是效率高。二是通信對(duì)用戶透明。二是通信對(duì)用戶透明。.114 二、高級(jí)通信機(jī)制的類型1 1、共享存儲(chǔ)器系統(tǒng)、共享存儲(chǔ)器系統(tǒng)通信的進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)或通信的進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲(chǔ)區(qū)，進(jìn)程之間能夠通過(guò)它們共享存儲(chǔ)區(qū)，進(jìn)程之間能夠通過(guò)它們進(jìn)行通信。進(jìn)行通信。（1 1）基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式）基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式進(jìn)程間同步處理由程序員解決。進(jìn)程間同步處理由程序員解決。（2 2）基于共享存儲(chǔ)區(qū)的通信方式）基于共享存儲(chǔ)區(qū)的通信方式.1152 2、消息傳遞系統(tǒng)、消息傳遞系統(tǒng)在消息傳遞中，進(jìn)程間的數(shù)據(jù)在消息傳遞中，進(jìn)程間的數(shù)據(jù)交換以消息為單位。程序員直接利用交

50、換以消息為單位。程序員直接利用系統(tǒng)提供的通信命令（原語(yǔ)）來(lái)實(shí)現(xiàn)。系統(tǒng)提供的通信命令（原語(yǔ)）來(lái)實(shí)現(xiàn)。（1 1）直接通信方式。）直接通信方式。發(fā)送進(jìn)程直接將消息發(fā)送給接收發(fā)送進(jìn)程直接將消息發(fā)送給接收進(jìn)程并將它掛在接收進(jìn)程的消息緩進(jìn)程并將它掛在接收進(jìn)程的消息緩沖隊(duì)列上，接收進(jìn)程從消息緩沖隊(duì)沖隊(duì)列上，接收進(jìn)程從消息緩沖隊(duì)列取得消息。列取得消息。.116（2 2）間接通信方式。）間接通信方式。發(fā)送進(jìn)程將消息發(fā)送到某種中間發(fā)送進(jìn)程將消息發(fā)送到某種中間實(shí)體中，接收進(jìn)程從中取得消息。實(shí)體中，接收進(jìn)程從中取得消息。這種中間實(shí)體一般為信箱，故也稱這種中間實(shí)體一般為信箱，故也稱之為信箱通信方式。之為信箱通信方式。.

51、1173 3、管道通信方式、管道通信方式管道是指用于連接一個(gè)讀進(jìn)程和管道是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程以實(shí)現(xiàn)它們之間通信的一個(gè)寫進(jìn)程以實(shí)現(xiàn)它們之間通信的共享文件，又稱為共享文件，又稱為pipepipe文件。文件。管道通信須提供管道通信須提供3 3方面的協(xié)調(diào)能力：方面的協(xié)調(diào)能力：（1 1）互斥）互斥（2 2）同步）同步（3 3）對(duì)方是否存在）對(duì)方是否存在.118三、直接通信和間接通信 1.直接通信方式指發(fā)送進(jìn)程利用操作系統(tǒng)提供的發(fā)送指發(fā)送進(jìn)程利用操作系統(tǒng)提供的發(fā)送和接收命令（原語(yǔ)）進(jìn)行通信。發(fā)送消和接收命令（原語(yǔ)）進(jìn)行通信。發(fā)送消息時(shí)直接指明接收者或發(fā)送者進(jìn)程息時(shí)直接指明接收者或發(fā)送者進(jìn)程I

52、DID。發(fā)送原語(yǔ)：發(fā)送原語(yǔ)：sendsend（receiver,messagereceiver,message）; ;接收原語(yǔ)：接收原語(yǔ)：receiver(sender,message);receiver(sender,message);.119舉例：（舉例：（UNIXUNIX中兩進(jìn)程利用信號(hào)通信）。中兩進(jìn)程利用信號(hào)通信）。Process AProcess A send(1040, SIGUSR1); #send(1040, SIGUSR1); #向向10401040號(hào)進(jìn)程發(fā)送號(hào)進(jìn)程發(fā)送 一個(gè)一個(gè)SIGUSR1SIGUSR1信號(hào)。信號(hào)。Process BProcess B receive(SI

53、GUSR1,func);#receive(SIGUSR1,func);#當(dāng)收到當(dāng)收到SIGUSR1SIGUSR1信信 號(hào)時(shí)，就執(zhí)行號(hào)時(shí)，就執(zhí)行func(),func(),如果如果SIGUSR1SIGUSR1 信號(hào)未到，則系統(tǒng)登記信號(hào)未到，則系統(tǒng)登記funcfunc函數(shù)，函數(shù)， 待其信號(hào)到時(shí)再調(diào)用執(zhí)行。待其信號(hào)到時(shí)再調(diào)用執(zhí)行。.1202.間接通信方式基本思想：系統(tǒng)為每個(gè)信箱設(shè)一個(gè)消息基本思想：系統(tǒng)為每個(gè)信箱設(shè)一個(gè)消息隊(duì)列，消息發(fā)送和接收都指向該消息隊(duì)列，隊(duì)列，消息發(fā)送和接收都指向該消息隊(duì)列，（每個(gè)進(jìn)程可以對(duì)消息隊(duì)列發(fā)送并接收（每個(gè)進(jìn)程可以對(duì)消息隊(duì)列發(fā)送并接收/ /只只發(fā)送發(fā)送/ /只接收只接收)

54、 ) 缺點(diǎn)：必須有一個(gè)通信雙方共享的一個(gè)缺點(diǎn)：必須有一個(gè)通信雙方共享的一個(gè)邏輯消息隊(duì)列（邏輯消息隊(duì)列（UNIXUNIX的的PIPEPIPE，F(xiàn)IFOFIFO及及IPCIPC消消息傳遞機(jī)制都屬于這種形式），使用時(shí)消息傳遞機(jī)制都屬于這種形式），使用時(shí)消息發(fā)送者約定寫方式打開(kāi)信箱息發(fā)送者約定寫方式打開(kāi)信箱, ,消息接收者消息接收者約定讀方式打開(kāi)信箱或同時(shí)讀寫打開(kāi)。約定讀方式打開(kāi)信箱或同時(shí)讀寫打開(kāi)。優(yōu)點(diǎn)：很容易建立雙向通信鏈優(yōu)點(diǎn)：很容易建立雙向通信鏈( (只要對(duì)信只要對(duì)信箱說(shuō)明為讀寫打開(kāi)箱說(shuō)明為讀寫打開(kāi)) )。 .121四、用消息傳遞實(shí)現(xiàn)互斥四、用消息傳遞實(shí)現(xiàn)互斥.122Program muluale

55、xclusionProgram mulualexclusionConst n=;(Const n=;(* *進(jìn)程個(gè)數(shù)進(jìn)程個(gè)數(shù)* *) )Procedure P(I:integer);Procedure P(I:integer);Var msg:message;Var msg:message;BeginBeginrepeatrepeatreceive(mutex,msg);receive(mutex,msg);send(mutex,msg);send(mutex,msg);foreverforeverEnd;End;Begin(*main program*)Create-mailbox(mute

56、x);Send(mutex,null); ParbeginP(1);P(2);P(n); ParendEnd.123又例：用消息傳遞解決有限緩沖區(qū)的生又例：用消息傳遞解決有限緩沖區(qū)的生產(chǎn)者產(chǎn)者/ /消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題使用兩個(gè)郵箱（兩個(gè)緩沖區(qū)）。使用兩個(gè)郵箱（兩個(gè)緩沖區(qū)）。生產(chǎn)者將生產(chǎn)出的數(shù)據(jù)作為消息送生產(chǎn)者將生產(chǎn)出的數(shù)據(jù)作為消息送到郵箱到郵箱mayconsume,mayconsume,只要郵箱中有消息，只要郵箱中有消息，消費(fèi)者就可以消費(fèi)。消費(fèi)者就可以消費(fèi)。最初，郵箱最初，郵箱mayproducemayproduce充滿了與緩充滿了與緩沖區(qū)容量相同數(shù)量的空消息，沖區(qū)容量相同數(shù)量的空消息，may

57、producemayproduce中的消息隨生產(chǎn)者的生產(chǎn)而中的消息隨生產(chǎn)者的生產(chǎn)而減少，隨消費(fèi)者的消費(fèi)而增加。減少，隨消費(fèi)者的消費(fèi)而增加。.124Program producerconsumerConst capacity=.;null=;Var I:integer;Procedure producer; var pmsg:message;Begin while true do begin receive(mayproduce,psmg); pmsg:=produce; send(maysonsume,pmsg) endEnd;Procdure consumer;Var cmsg:messag

58、e;BeginWhile true do begin receive(mayconsume,cmsg); consume(cmsg); send(mayprocedure,null) endEnd;Begin父進(jìn)程父進(jìn)程Create mailbox(mayproduce);Create mailbox(mayconsume);For I=1 to capacity do send(mayproduce,null); Parbeginproducer;consumer ParendEnd.125 邏輯通信鏈容量： 在通信發(fā)送者和接收者之間存在一條邏輯通在通信發(fā)送者和接收者之間存在一條邏輯通信鏈，設(shè)鏈的容量是指該鏈暫存消息的能力。信鏈，設(shè)鏈的容量是指該鏈暫存消息的能力。 1.1.容量為容量為0 0。表示通信鏈不能暫存任何消息，。表示通信鏈不能暫存任何消息，鏈中無(wú)緩沖鏈中無(wú)緩沖( (不計(jì)鏈頭的發(fā)送緩沖和鏈尾的接收不計(jì)鏈頭的發(fā)送緩沖和鏈尾的接收緩沖緩沖) )，這要求接收方必須在發(fā)送方之前發(fā)接收，這要求接收方必須在發(fā)送方之前發(fā)接收請(qǐng)求，否則發(fā)送失敗。請(qǐng)求，否則發(fā)送失敗。 2.2.有限容量。隊(duì)列的長(zhǎng)度為