操作系統(tǒng)第3章進(jìn)程通信與控制

1、目的與要求目的與要求：了解并發(fā)程序的高級(jí)語(yǔ)了解并發(fā)程序的高級(jí)語(yǔ)言表示與操作系統(tǒng)支持下的實(shí)現(xiàn)；同言表示與操作系統(tǒng)支持下的實(shí)現(xiàn)；同步與互斥問(wèn)題。步與互斥問(wèn)題。重點(diǎn)與難點(diǎn)重點(diǎn)與難點(diǎn)：并發(fā)程序中的同步與互：并發(fā)程序中的同步與互斥斥并發(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)行，從微觀上看這些任務(wù)分別是在各時(shí)運(yùn)行，從微觀上看這些

2、任務(wù)分別是在各自的物理處理機(jī)上分別運(yùn)行。自的物理處理機(jī)上分別運(yùn)行。 程序并發(fā)執(zhí)行的特征程序并發(fā)執(zhí)行的特征3 3：程序執(zhí)行：程序執(zhí)行結(jié)果的不可再現(xiàn)性。結(jié)果的不可再現(xiàn)性。計(jì)算結(jié)果與執(zhí)行的速度有關(guān)，從而失去了可再計(jì)算結(jié)果與執(zhí)行的速度有關(guān)，從而失去了可再現(xiàn)性。如對(duì)共享變量的使用。例，有現(xiàn)性。如對(duì)共享變量的使用。例，有2 2個(gè)循環(huán)程個(gè)循環(huán)程序序A A和和B B，它們共享一個(gè)變量，它們共享一個(gè)變量n n。程序程序A: n+A: n+； / /* * n=n+1 n=n+1 程序程序B: coutn; /B: coutn; /* * 輸出輸出n n的值的值 n=0; n=0; / /* * 變量變量n n清

3、清0 0 程序程序A A和和B B以不同的速度運(yùn)行，以不同的速度運(yùn)行，（假定變量（假定變量n n的初值為的初值為100)100)。OSOS選擇執(zhí)行程序選擇執(zhí)行程序A A完成后再執(zhí)行程序完成后再執(zhí)行程序B BA A：n+n+； B B：coutncoutn； B B：n=0n=0；此時(shí)得到的此時(shí)得到的n n值分別為值分別為10l10l，10l10l，O O。OSOS選擇執(zhí)行程序選擇執(zhí)行程序B B完成后再執(zhí)行程序完成后再執(zhí)行程序A AB B：coutncoutn；B B：n=0n=0；A A：n+;n+;此時(shí)得到的此時(shí)得到的n n值分別為值分別為100, 0, 1100, 0, 1 OSOS選擇先

4、執(zhí)行程序選擇先執(zhí)行程序B B的一個(gè)語(yǔ)句后，的一個(gè)語(yǔ)句后，再執(zhí)行程序再執(zhí)行程序A A的一個(gè)語(yǔ)句，最后執(zhí)行程序的一個(gè)語(yǔ)句，最后執(zhí)行程序B B的第二個(gè)語(yǔ)句。的第二個(gè)語(yǔ)句。B B：coutn;coutin; cinin; Out=in; Out=in; coutout; coutin; cinin; Out=in; Out=in; Coutout; Coutin; Cinin; Out=in; Out=in; Coutout; Coutin; Cinin; Out=in; Out=in; Coutout; Cout=1) X1X1-1： AjX1； 輸出一張票輸出一張票 else 輸出輸出“票售完票售

5、完” void T2（X2） 按旅客訂票要求找到按旅客訂票要求找到AjX2Aj； if (X2 =1) X2X2-1： AjX2； 輸出一張票輸出一張票 else輸出輸出“票售完票售完” 考慮以下的執(zhí)行次序:(a)和(b)按按(a)的序列執(zhí)行時(shí)，結(jié)果是正確的。按的序列執(zhí)行時(shí)，結(jié)果是正確的。按(b)的序列執(zhí)行情況，則兩個(gè)旅客可的序列執(zhí)行情況，則兩個(gè)旅客可能各自都買到一張同天同次航班的機(jī)票，可是，能各自都買到一張同天同次航班的機(jī)票，可是，Aj的值實(shí)際上只減去了的值實(shí)際上只減去了1,造造成余票數(shù)的不正確。成余票數(shù)的不正確。設(shè)設(shè)Aj=50則則x1=50此時(shí)此時(shí)x2=50此時(shí)此時(shí)x1=49此時(shí)此時(shí)x2=

6、49此時(shí)此時(shí)Aj=49此時(shí)此時(shí)Aj=49特別是，當(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出錯(cuò)原因是什么？出錯(cuò)原因是什么？余票額是共享變量！沒(méi)有建立對(duì)共享變量余票額是共享變量！沒(méi)有建立對(duì)共享變量的使用與保護(hù)機(jī)制。的使用與保護(hù)機(jī)制。 由以上的例子說(shuō)明什么？由以上的例子說(shuō)明什么？ 要想實(shí)現(xiàn)多道程序并發(fā)執(zhí)行，必須設(shè)法對(duì)要想實(shí)現(xiàn)多道程序并發(fā)執(zhí)行，必須設(shè)法對(duì)共享變量（資源）

7、加入一定的管理機(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)性。思考：對(duì)共享變量（資源）如何加思考：對(duì)共享變量（資源）如何加上這種規(guī)則（機(jī)制）呢？上這種規(guī)則（機(jī)制）呢？這是這是現(xiàn)代操作系統(tǒng)必須解決的核心問(wèn)題！現(xiàn)代操作系統(tǒng)必須解決的核心問(wèn)題！ 同步機(jī)制：信號(hào)傳遞？同步機(jī)制：信號(hào)傳遞？ 互斥機(jī)制：加鎖？互斥機(jī)制：加鎖？同步關(guān)系同步關(guān)系（亦稱直接制約關(guān)系）（亦稱直接制約關(guān)系）: : 指完成同一任務(wù)的伙伴進(jìn)程間，因需指完成同

8、一任務(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)程的同步與互斥例例 ：在計(jì)算機(jī)系統(tǒng)中對(duì)同一緩沖：在計(jì)算機(jī)系統(tǒng)中對(duì)同一緩沖區(qū)的數(shù)據(jù)的輸入與輸出操作。緩沖區(qū)區(qū)的數(shù)據(jù)的輸入與輸出操作。緩沖區(qū)滿才能輸出，緩沖區(qū)空才能輸入。滿才能輸出，緩沖區(qū)空才能輸入。 緩沖區(qū)緩沖區(qū)輸入輸入進(jìn)程進(jìn)程輸出輸出進(jìn)程進(jìn)程已存滿，可取已存滿，可取已取空，可存已取空，可存互斥關(guān)系互斥關(guān)系（亦稱間

9、接制約關(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í)。 既同步又要互斥的例子：既同步又要互斥的例子： 1 1、客車上的司機(jī)和售票員各司其職、客車上的司機(jī)和售票員各司其職為完成同一個(gè)運(yùn)送乘客的任務(wù)相互配為完成

10、同一個(gè)運(yùn)送乘客的任務(wù)相互配合。合。 互斥：司機(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)車）。正常行車正常行車到站停車到站停車啟動(dòng)汽車啟動(dòng)汽車售票售票開(kāi)車門開(kāi)車門關(guān)車門關(guān)車門司機(jī)進(jìn)程司機(jī)進(jìn)程售票員進(jìn)程售票員進(jìn)程互斥與同步的例子：互斥與同步的例子： 2 2、有限緩沖區(qū)問(wèn)題?；コ猓捍鏁r(shí)不、有限緩沖區(qū)問(wèn)題。互斥：存時(shí)不要取，取時(shí)不要存。同步：有數(shù)據(jù)才要取，取時(shí)不要存。同步：有數(shù)據(jù)才能取，有空區(qū)才能存。能取，有空區(qū)才能存。P

11、kP2C1C2CmP1存存取取互斥與同步的例子：互斥與同步的例子： 3 3、讀者與寫(xiě)者問(wèn)題。、讀者與寫(xiě)者問(wèn)題。（Readers/WritersReaders/Writers問(wèn)題）問(wèn)題） 4 4、哲學(xué)家就餐問(wèn)題。（就餐和思、哲學(xué)家就餐問(wèn)題。（就餐和思考需同步與互斥）考需同步與互斥）一一、兩個(gè)基本概念：、兩個(gè)基本概念：臨界資源臨界資源（critical resource）：）：一次僅允一次僅允許一個(gè)進(jìn)程使用的資源。許一個(gè)進(jìn)程使用的資源。如：上例如：上例ECHO程序中的共享變量程序中的共享變量IN，OUT,飛機(jī)訂票系統(tǒng)的余票額飛機(jī)訂票系統(tǒng)的余票額Aj等。等。3.3 3.3 臨界資源和臨界區(qū)臨界資源和

12、臨界區(qū)臨界段（區(qū)）臨界段（區(qū)）（critical section) ：各進(jìn)程各進(jìn)程必須互斥執(zhí)行的程序段。必須互斥執(zhí)行的程序段。如：對(duì)余票額如：對(duì)余票額Aj進(jìn)行操作的那個(gè)程序段。進(jìn)行操作的那個(gè)程序段。u二、臨界資源須互斥使用例例1 1打印機(jī)：打印機(jī)： P1,P2P1,P2兩進(jìn)程使用同一打印機(jī)。兩進(jìn)程使用同一打印機(jī)。如果不互斥使用會(huì)交叉輸出。如果不互斥使用會(huì)交叉輸出。例例2 2共享變量：共享變量：共享變量是臨界資源。共享變量是臨界資源。 Cobegin void A( ) N=count; N=N+100; count=N; ; void B( ) M=count; M=M+200; count=

13、M; ;Coend;如下例對(duì)共享變量如下例對(duì)共享變量countcount的互斥訪問(wèn)。的互斥訪問(wèn)?；コ鈭?zhí)行互斥執(zhí)行例例:若若count為為300,如互斥執(zhí)如互斥執(zhí)行結(jié)果行結(jié)果count為為600,臨界區(qū)臨界區(qū)臨界區(qū)臨界區(qū)Cobegin void A( ) N=count; N=N+100; count=N; ; void B( ) M=count; M=M+200; count=M; ;Coend;若不互斥若不互斥,可能結(jié)果為可能結(jié)果為500,400.（設(shè)（設(shè)count初值為初值為300）不互斥執(zhí)行不互斥執(zhí)行設(shè)設(shè)A在此處中斷，在此處中斷，執(zhí)行完執(zhí)行完B三、進(jìn)程互斥進(jìn)入臨界區(qū)的一般結(jié)構(gòu)三、進(jìn)程互斥

14、進(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ū)（其余代碼） ;Cobegin 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)。臨界區(qū)臨界區(qū)臨界區(qū)臨界區(qū)Entry code(Ent

15、ry 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(釋放釋放) )例如：對(duì)打印機(jī)（臨界資源）的互斥使用例如：對(duì)打印機(jī)（臨界資源）的互斥使用Entry code(Entry code(請(qǐng)求獨(dú)占請(qǐng)求獨(dú)占) )exit code(exit code(釋放釋放) )使用打印機(jī)的程序段使用打印機(jī)的程序段P1P1：臨界區(qū)臨界區(qū)Entry code(Entry code(請(qǐng)求獨(dú)占請(qǐng)求獨(dú)占) )exit code(exit code(釋放釋放) )使用打印機(jī)的程序段

16、使用打印機(jī)的程序段P2P2：臨界區(qū)臨界區(qū)臨界資源臨界資源四、臨界區(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ū)，則其他進(jìn)程必進(jìn)程進(jìn)入自己的臨界區(qū)，則其他進(jìn)程必須等待。須等待。準(zhǔn)則準(zhǔn)則3 3：有限等待。進(jìn)入臨界區(qū)的進(jìn)程有限等待。進(jìn)入臨界區(qū)的進(jìn)程要在有限時(shí)間內(nèi)退出，以便其他進(jìn)程及要在有限時(shí)間內(nèi)退出，以便其

17、他進(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)象。四、臨界區(qū)進(jìn)入準(zhǔn)則（同步機(jī)制）四、臨界區(qū)進(jìn)入準(zhǔn)則（同步機(jī)制）Cobegin 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)。臨界區(qū)臨界區(qū)臨界區(qū)臨界區(qū)Entry code(Entr

18、y 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(釋放釋放) )3.4 互斥實(shí)現(xiàn)方法互斥實(shí)現(xiàn)方法2 2、專用機(jī)器指令、專用機(jī)器指令（1 1）“Test and SetTest and Set”指令指令管理思想：加鎖機(jī)制。開(kāi)始鎖打開(kāi)即未鎖上。先到的管理思想：加鎖機(jī)制。開(kāi)始鎖打開(kāi)即未鎖上。先到的進(jìn)程拿到鎖并進(jìn)入臨界區(qū)然后反鎖，直到從臨界區(qū)退進(jìn)程拿到鎖并進(jìn)入臨界區(qū)然后反鎖，直到從臨界區(qū)退出，開(kāi)鎖交還。出，開(kāi)鎖交還。該指令功能描述為：該指令功能描述為：int

19、 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ù)作為一個(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í)，表示該資源正在被使用。3.4 互斥實(shí)現(xiàn)方法互斥實(shí)現(xiàn)方法 例例1：利用：利用testset指令實(shí)現(xiàn)指令實(shí)現(xiàn)互斥的循環(huán)進(jìn)程描述

20、：互斥的循環(huán)進(jìn)程描述：P(i):While(1) while (ts(lock) 空操作空操作; /測(cè)試鎖是否已鎖上？測(cè)試鎖是否已鎖上？ ; lock=0; main( ) lock=0; cobegin p(1);P(2);P(n); coend .假設(shè)進(jìn)程假設(shè)進(jìn)程P(2)欲進(jìn)入臨欲進(jìn)入臨界區(qū)，調(diào)用過(guò)程界區(qū)，調(diào)用過(guò)程P（2），），執(zhí)行執(zhí)行ts(lock)后返回后返回ts為為假，并置假，并置lock=1,故故P(2)進(jìn)入臨界區(qū)，若此時(shí)有進(jìn)入臨界區(qū)，若此時(shí)有進(jìn)程進(jìn)程P(1)欲進(jìn)入臨界區(qū)，欲進(jìn)入臨界區(qū)，調(diào)用調(diào)用P(1),執(zhí)行測(cè)試執(zhí)行測(cè)試ts(lock),因因lock為為1，故，故ts返回真，故返回

21、真，故P(1)被拒被拒絕進(jìn)入臨界區(qū)。絕進(jìn)入臨界區(qū)。（2 2）SwapSwap指令實(shí)現(xiàn)進(jìn)程指令實(shí)現(xiàn)進(jìn)程管理思想：加鎖機(jī)制，一把鎖配管理思想：加鎖機(jī)制，一把鎖配n n把鑰匙，一個(gè)進(jìn)程一把鑰匙，一個(gè)進(jìn)程一把鑰匙，誰(shuí)能開(kāi)鎖誰(shuí)進(jìn)入臨界區(qū)。把鑰匙，誰(shuí)能開(kāi)鎖誰(shuí)進(jìn)入臨界區(qū)。該指令功能描述為：該指令功能描述為：void swapvoid swap（static int a,bstatic int a,b）；）；int tempint temp；temp=atemp=a；a=ba=b；b=tempb=temp； 這里，這里，SWAPSWAP指令也是原語(yǔ)。在利用指令也是原語(yǔ)。在利用SwapSwap實(shí)現(xiàn)實(shí)現(xiàn)進(jìn)程互斥時(shí)

22、，可為臨界資源設(shè)置一個(gè)全局變量進(jìn)程互斥時(shí)，可為臨界資源設(shè)置一個(gè)全局變量locklock，其，其初值為初值為0 0，在每個(gè)進(jìn)程中再利用一個(gè)局部變量，在每個(gè)進(jìn)程中再利用一個(gè)局部變量keykey。然后。然后通過(guò)通過(guò)swapswap指令實(shí)現(xiàn)互斥。指令實(shí)現(xiàn)互斥。3.4 互斥實(shí)現(xiàn)方法互斥實(shí)現(xiàn)方法2 2、專用機(jī)器指令、專用機(jī)器指令例例2：利用：利用swap指令實(shí)現(xiàn)互斥的描述指令實(shí)現(xiàn)互斥的描述/*I為進(jìn)程號(hào)，如為為進(jìn)程號(hào)，如為P（2） 為進(jìn)程為進(jìn)程P2調(diào)用調(diào)用P(I)： While(1) Keyi=1; Do swap(lock,keyi); while (keyi); ; lock=0; ; main( )

23、 lock=0; cobegin p(1);P(2);P(n); coend例：例：P(2)先調(diào)用先調(diào)用P過(guò)程，過(guò)程，則此時(shí)則此時(shí)lock=1,Key2=0,P(2)進(jìn)進(jìn)入臨界區(qū)。當(dāng)入臨界區(qū)。當(dāng)P(2)正正在臨界區(qū)時(shí)，若有另在臨界區(qū)時(shí)，若有另一進(jìn)程又想進(jìn)入臨界一進(jìn)程又想進(jìn)入臨界區(qū)，執(zhí)行區(qū)，執(zhí)行P(1)，此時(shí)，此時(shí)key1=1,lock=1,兩者交兩者交換還是換還是1，故，故P(1)只能只能循環(huán)等待。直至循環(huán)等待。直至P(2)退出臨界區(qū)，交換使退出臨界區(qū)，交換使lock=0為止。為止。v3、使用特殊機(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)

24、程的單處理）可用于：含有任意數(shù)量進(jìn)程的單處理機(jī)或共享主存的多處理機(jī)；機(jī)或共享主存的多處理機(jī)；（2）比較簡(jiǎn)單，易于驗(yàn)證；）比較簡(jiǎn)單，易于驗(yàn)證；（3）可支持多個(gè)臨界段，每個(gè)臨界段用各）可支持多個(gè)臨界段，每個(gè)臨界段用各自的變量加以定義。如自的變量加以定義。如lock變量的改變。變量的改變。缺點(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)生死鎖。如：）有可

25、能產(chǎn)生死鎖。如：P1在執(zhí)行在執(zhí)行TS或或SWAP指令時(shí)，擁有更高優(yōu)先級(jí)的進(jìn)程指令時(shí)，擁有更高優(yōu)先級(jí)的進(jìn)程P2中中斷斷P1，并且，并且P2又要使用又要使用P1所占用的資源。所占用的資源。二、利用軟件方法解決進(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； 3.4 互斥實(shí)現(xiàn)方法互斥實(shí)現(xiàn)方法互斥執(zhí)

26、行的程序段用軟件實(shí)現(xiàn)?；コ鈭?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)程的描述如下：述如下：P1P1：whilewhile（1 1） whilewhile（turnturn！1 1） no-opno-op； critical sectioncritical sectionturnturn2 2；

27、P2P2：whilewhile（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對(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)該臨界資源

28、，而界資源，而P1P1又想再次訪問(wèn)該資源，但又想再次訪問(wèn)該資源，但它卻無(wú)法進(jìn)入臨界區(qū)。它卻無(wú)法進(jìn)入臨界區(qū)。算法算法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)

29、程時(shí)，表示進(jìn)程P1P1正在臨界區(qū)正在臨界區(qū)內(nèi)執(zhí)行；若且內(nèi)執(zhí)行；若且flag1= 1flag1= 1時(shí)，表示進(jìn)程時(shí)，表示進(jìn)程P2P2正在臨界區(qū)內(nèi)執(zhí)行。算法正在臨界區(qū)內(nèi)執(zhí)行。算法2 2的描述如的描述如下：下：Int 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

30、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ū)對(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幾乎是在幾乎是在

31、同時(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)則。算法算法3 3（雙標(biāo)志、先修改后檢查算法）（雙標(biāo)志、先修改后檢查算法） 算法算法3 3中仍然使用了數(shù)組中仍然使用了數(shù)組flag flag ，但但flag0=1flag0=1表示進(jìn)程表示進(jìn)程P1P1希望進(jìn)入臨界希望進(jìn)入臨界區(qū)，然后再去查看區(qū)，然后再去查看P2P2的標(biāo)志。若此時(shí)的標(biāo)志。若此時(shí)flag1=1flag1=1，則，則P1P1等待；否則，

32、等待；否則，P1P1進(jìn)入進(jìn)入臨界區(qū)；對(duì)于進(jìn)程臨界區(qū)；對(duì)于進(jìn)程P2P2亦然。亦然。Int 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 section flag1

33、=0 flag1=0； 測(cè)試對(duì)方是測(cè)試對(duì)方是否在臨界區(qū)否在臨界區(qū)對(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ū)。 算法算法4 4（先修改、后檢查、后修改者等待（先修改、后檢查、后修改者等待算法）算法）Int flag2=0Int flag

34、2=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 sectioncritical section Flag1=0 Fla

35、g1=0； 評(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 Flag0=0 Flag0=0； P2P2：whilewhile（1 1） Fla

36、g1=1Flag1=1；turn=1turn=1；While(flag0&turn=1While(flag0&turn=1） no-opno-op； critical sectioncritical section Flag1=0 Flag1=0； 3.5. 3.5. 信號(hào)量和信號(hào)量和PVPV操作操作(semaphore)(semaphore) 由于實(shí)現(xiàn)互斥的軟件方法和硬件方法都存由于實(shí)現(xiàn)互斥的軟件方法和硬件方法都存在缺陷，故需要尋找其他機(jī)制?，F(xiàn)寄希望于在缺陷，故需要尋找其他機(jī)制?，F(xiàn)寄希望于操作系統(tǒng)和程序設(shè)計(jì)提供對(duì)并發(fā)的支持。操作系統(tǒng)和程序設(shè)計(jì)提供對(duì)并發(fā)的支持。（信號(hào)量、管程、消息傳遞）（信號(hào)

37、量、管程、消息傳遞）信號(hào)量機(jī)制是一種卓有成效的解決進(jìn)程同步信號(hào)量機(jī)制是一種卓有成效的解決進(jìn)程同步問(wèn)題的工具。問(wèn)題的工具。一、一、信號(hào)量的定義信號(hào)量的定義信號(hào)量一般由兩個(gè)成員組成。其中一個(gè)信號(hào)量一般由兩個(gè)成員組成。其中一個(gè)成員為整型變量，表示該信號(hào)量的值；成員為整型變量，表示該信號(hào)量的值；另一個(gè)是指向另一個(gè)是指向PCBPCB的指針。的指針。信號(hào)量的信號(hào)量的C C語(yǔ)言描述如下：語(yǔ)言描述如下：struct semaphoreint value;/信號(hào)量的值域信號(hào)量的值域struct PCB *queue; /* *queuequeue為等待進(jìn)程鏈表指針為等待進(jìn)程鏈表指針S;信號(hào)量變量信號(hào)量變量S S

38、的值只能通過(guò)的值只能通過(guò)P P、V V操作來(lái)改變它。操作來(lái)改變它。二、二、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)量做通過(guò)對(duì)信號(hào)量做P P、V V操作來(lái)實(shí)現(xiàn)互斥訪操作來(lái)實(shí)現(xiàn)互斥訪問(wèn)臨界區(qū)。問(wèn)臨界區(qū)。三、三、N N個(gè)進(jìn)程利用信號(hào)量、

39、個(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-; S.value-; if (S.value0) if (S.value0) Block(S.L ) Block(S.L )S.value+;S.value+;if(S.value=0)if(S.value=0,s.value=0,則該進(jìn)程繼續(xù)執(zhí)行；則該進(jìn)程繼續(xù)執(zhí)行；如果如果s.value0,s.value0,s.value

40、0,則該進(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)程繼操作的進(jìn)程繼續(xù)執(zhí)行。續(xù)執(zhí)行。五、五、信號(hào)量機(jī)制物理含義信號(hào)量機(jī)制物理含義1 1、信號(hào)量初值、信號(hào)量初值S.valueS.value表示系統(tǒng)中某種資表示系統(tǒng)中某種資源的數(shù)目，又稱資源信息量。源的數(shù)目，又稱資源信息量。2 2、執(zhí)行一次、執(zhí)行一次P P操作意味

41、著請(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í)行. .3 3、執(zhí)行一次、執(zhí)行一次V V操作意味著釋放一個(gè)單位資源，操作意味著釋放一個(gè)單位資源，因此因此S.valueS.value的值加的值加1 1；若若s.value=0s.value0s.value0時(shí)時(shí), ,表示等待隊(duì)列無(wú)等待該表示等待隊(duì)列無(wú)等待該信

42、號(hào)量的進(jìn)程信號(hào)量的進(jìn)程, ,其值表示還可用的資源數(shù)其值表示還可用的資源數(shù)目目. .做做V V操作的進(jìn)程繼續(xù)執(zhí)行。操作的進(jìn)程繼續(xù)執(zhí)行。六、信號(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操作，并且操作，并且n n個(gè)個(gè)進(jìn)程共享一個(gè)互進(jìn)程共享一個(gè)互斥信號(hào)量斥信號(hào)量S,S,初值為初值為1 1（即只允許一個(gè)進(jìn)程進(jìn)（即只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)）

43、。入臨界區(qū)）。例例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ī)（讀寫(xiě)分配表）（讀寫(xiě)分配表）V(mutex) Pb:P(mutex)釋放打印機(jī)釋放打印機(jī)（讀寫(xiě)分配表）（讀寫(xiě)分配表）V(mutex) 1: mutex.value-; if (mutex.value0) Block(mutex.L

44、);4: mutex.value+; if (mutex.value=0) wakeup(mutex.L);2: mutex.value-; if (mutex.value0) Block(mutex.L );3: mutex.value+; if (mutex.value=1) Ri:=Ri-1; Aj:=Ri;輸出一張票；輸出一張票； else 輸出輸出“票已售完票已售完”； ;/*過(guò)程結(jié)束過(guò)程結(jié)束 cobegin P(1),P(2),P(n) coend例例2. 用用PV操作實(shí)現(xiàn)航空售票系統(tǒng)中訪問(wèn)余票額的同操作實(shí)現(xiàn)航空售票系統(tǒng)中訪問(wèn)余票額的同步與互斥。步與互斥。（該系統(tǒng)中的各進(jìn)程中該系統(tǒng)

45、中的各進(jìn)程中“按旅客要求找到按旅客要求找到Aj”、“輸出一張票輸出一張票”、“輸出票已售完輸出票已售完”的操作語(yǔ)句的操作語(yǔ)句屬于臨界區(qū)。）屬于臨界區(qū)。）u2 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操作操作例例3 3、有有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)

46、量s s，初值為，初值為0 0。）。）P1: S1;V(s);P2: P(s);S2;1: S.value-; if (S.value0) Block(S.L ); 2: S.value+; if (S.value=0) wakeup(S.L); 0: s.value=0,初態(tài)初態(tài)1: s.value=-1,P2阻塞阻塞2: s.value=0,喚醒喚醒P2例例3 3、有有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)程共享信

47、號(hào)量s s，初值為，初值為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=-10而被阻塞。而被阻塞。只有只有P1執(zhí)行完執(zhí)行完S1,發(fā)出發(fā)出V（S）操作使操作使S增增1后，后，P2才能執(zhí)行才能執(zhí)行S2例例4 4：供者：供者L1L1將讀卡機(jī)中的數(shù)據(jù)放入緩將讀卡機(jī)中的數(shù)據(jù)放入緩沖區(qū)，用者沖區(qū)，用者L2L2從緩沖區(qū)中讀取數(shù)據(jù)，用信從緩沖區(qū)中讀取數(shù)據(jù)，用信號(hào)量機(jī)制實(shí)現(xiàn)對(duì)緩沖區(qū)的同步。號(hào)量機(jī)制實(shí)現(xiàn)對(duì)緩沖區(qū)的同步。緩沖區(qū)緩沖區(qū)供者供者L1L1用者用者L2L2解：設(shè)置兩個(gè)信號(hào)量：解：

48、設(shè)置兩個(gè)信號(hào)量：S1S1：表示緩沖區(qū)是否空（：表示緩沖區(qū)是否空（0 0表示不空，表示不空，1 1表表示空）示空）S2S2：表示緩沖區(qū)是否滿（：表示緩沖區(qū)是否滿（0 0表示不滿，表示不滿，1 1表表示滿）示滿）置初值：置初值：S1=1,S2=0S1=1,S2=0緩沖區(qū)緩沖區(qū)供者供者L1,S1=1?L1,S1=1?用者用者L2,S2=1?L2,S2=1?S2=1S2=1S1=1S1=1供者進(jìn)程供者進(jìn)程L1： do P（S1） 讀入數(shù)據(jù)至緩沖區(qū)讀入數(shù)據(jù)至緩沖區(qū) V（s2）; while（1）用者進(jìn)用者進(jìn)L2：Do P（S2）；）； 從緩沖區(qū)取出信息從緩沖區(qū)取出信息 V（S1） 加工并且存盤加工并且存

49、盤 while(1);置初值：置初值：S1=1,S2=0S1=1,S2=01: S1.value-; if (S1.value0) Block(S1.L );2: S2.value-; if (S2.value0) Block(S2.L );0: s1.value=1,s2.value=0,初態(tài)初態(tài) 1: s1.value=0,L1進(jìn)入進(jìn)入 2: s2.value=-1,阻塞阻塞L23:s2.value=0,喚醒喚醒L2進(jìn)入，進(jìn)入，4:s1.value=1,L1進(jìn)入進(jìn)入供者進(jìn)程供者進(jìn)程L1： Do P（S1） 讀入數(shù)據(jù)至緩沖區(qū)讀入數(shù)據(jù)至緩沖區(qū) V（s2）; while（1）用者進(jìn)用者進(jìn)L2：D

50、o P（S2）；）； 從緩沖區(qū)取從緩沖區(qū)取 出信息出信息 V（S1） 加工并且存盤加工并且存盤 while(1);注：虛線箭頭為同步通信注：虛線箭頭為同步通信例例5 5、客車上的司機(jī)和售票員的工作流程、客車上的司機(jī)和售票員的工作流程如下圖所示：為保證旅客安全，司機(jī)與售票如下圖所示：為保證旅客安全，司機(jī)與售票員應(yīng)各司其職，為完成同一個(gè)運(yùn)送乘客的任員應(yīng)各司其職，為完成同一個(gè)運(yùn)送乘客的任務(wù)相互配合。請(qǐng)用務(wù)相互配合。請(qǐng)用P P、V V操作來(lái)實(shí)現(xiàn)司機(jī)與售操作來(lái)實(shí)現(xiàn)司機(jī)與售票員之間的同步。票員之間的同步。正常行車正常行車到站停車到站停車啟動(dòng)汽車啟動(dòng)汽車售票售票開(kāi)車門開(kāi)車門關(guān)車門關(guān)車門司機(jī)進(jìn)程：司機(jī)進(jìn)程：V

51、oid Bus-driver( ) Do P(run);/判斷能否開(kāi)車判斷能否開(kāi)車啟動(dòng)車輛；啟動(dòng)車輛；正常行車；正常行車；到站停車；到站停車； V（Open）;/開(kāi)門信號(hào)增開(kāi)門信號(hào)增1While (1);售票員進(jìn)程：售票員進(jìn)程：Void Conductor( )Do 售票；售票；P（Open）;/判斷能否開(kāi)門判斷能否開(kāi)門開(kāi)啟車門；開(kāi)啟車門；等待旅客陸續(xù)上車；等待旅客陸續(xù)上車；關(guān)閉車門；關(guān)閉車門；V（run）;/開(kāi)車信號(hào)增開(kāi)車信號(hào)增1 while(1);設(shè)兩個(gè)信號(hào)量設(shè)兩個(gè)信號(hào)量open表示開(kāi)門表示開(kāi)門,run表示開(kāi)車表示開(kāi)車;并并設(shè)初值設(shè)初值open=0（關(guān)門）（關(guān)門）;run=1（開(kāi)車），則：

52、（開(kāi)車），則：1: run.value-; if (run.value0) Block(S1.L );2: open.value-; if (open.value=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.signal; csignal(n

53、otfull); 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)程，則喚醒則喚醒Void producer( ) while(1) produce an item in nextp; producer-consumer.put(item); Void consume

54、r( ) while(1) producer-consumer.get(item);Consume the item in nextc; ;Main ( ) Cobegin producer( );consumer( ); . 三、管程與進(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)程是由順序程序執(zhí)行有關(guān)操作，管程主作。進(jìn)程是由順序程序執(zhí)行有

55、關(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è)置的。 （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)工作方式，因此，稱管程樣被調(diào)用而處于被動(dòng)工作方式，因此，稱管程為被動(dòng)成分。與此相對(duì)

56、應(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)程所撤消，只能被進(jìn)程調(diào)用。只能被進(jìn)程調(diào)用。3.5 進(jìn)程通信一、進(jìn)程通信的

57、概念與類型一、進(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ì)用戶不透明。（2 2）高級(jí)通信。指用戶可直接）高級(jí)通信。指用戶可直接通過(guò)操作系統(tǒng)提供的一組通信命令高通過(guò)操作系統(tǒng)提供的一組通信命令高效地傳送大量數(shù)據(jù)的一種通信方式。效地傳送大量數(shù)據(jù)的一種通信方式。特點(diǎn)：特點(diǎn)：一是效率高。一是效率高。二是通信對(duì)用戶透明。二是通信對(duì)

58、用戶透明。 二、高級(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ū)的通信方式2 2、消息傳遞系統(tǒng)、消息傳遞系統(tǒng)在消息傳遞中，進(jìn)程間的數(shù)據(jù)在消息傳遞中，進(jìn)程間的數(shù)據(jù)交換以消息為單位。程序員直接利用交換以消息為單位。程序員直接利用系統(tǒng)提供的通信命令（原語(yǔ)）來(lái)實(shí)現(xiàn)。系統(tǒng)提供的通信命令（原語(yǔ)

59、）來(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ì)列取得消息。列取得消息。Send(B,a) id:BSize:5Text:hello發(fā)發(fā)送送區(qū)區(qū)a aa a進(jìn)程進(jìn)程A AReceive(b) id:ASize:5Text:hello接接收收區(qū)區(qū)bb進(jìn)程進(jìn)程BPCB(B)mq mutexsmSize:5Text: helloNext: 0Sender:A第第1個(gè)消息緩沖區(qū)個(gè)消息緩沖區(qū)圖圖3-22 3-22 消息緩沖通信示

60、意圖消息緩沖通信示意圖（2 2）間接通信方式。）間接通信方式。發(fā)送進(jìn)程將消息發(fā)送到某種中間發(fā)送進(jìn)程將消息發(fā)送到某種中間實(shí)體中，接收進(jìn)程從中取得消息。實(shí)體中，接收進(jìn)程從中取得消息。這種中間實(shí)體一般為信箱，故也稱這種中間實(shí)體一般為信箱，故也稱之為信箱通信方式。之為信箱通信方式。信箱通信示意圖信箱通信示意圖進(jìn)程進(jìn)程 A A信箱頭信箱頭sendsendreceivereceive進(jìn)程進(jìn)程 B Bsendsendreceivereceive圖圖3-23 3-23 信箱通信示意圖信箱通信示意圖3 3、管道通信方式、管道通信方式管道是指用于連接一個(gè)讀進(jìn)程和管道是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫(xiě)進(jìn)程以實(shí)現(xiàn)它們之間