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

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

2、任務(wù)分別是在各自的物理處理機上分別運行。自的物理處理機上分別運行。 程序并發(fā)執(zhí)行的特征程序并發(fā)執(zhí)行的特征3 3：程序執(zhí)行：程序執(zhí)行結(jié)果的不可再現(xiàn)性。結(jié)果的不可再現(xiàn)性。計算結(jié)果與執(zhí)行的速度有關(guān)，從而失去了可再計算結(jié)果與執(zhí)行的速度有關(guān)，從而失去了可再現(xiàn)性。如對共享變量的使用。例，有現(xiàn)性。如對共享變量的使用。例，有2 2個循環(huán)程個循環(huán)程序序A A和和B B，它們共享一個變量，它們共享一個變量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以不同的速度運行，以不同的速度運行，（假定變量（假定變量n n的初值為的初值為100)100)。OSOS選擇執(zhí)行程序選擇執(zhí)行程序A A完成后再執(zhí)行程序完成后再執(zhí)行程序B BA A：n+n+； B B：coutncoutn； B B：n=0n=0；此時得到的此時得到的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+;此時得到的此時得到的n n值分別為值分別為100, 0, 1100, 0, 1 OSOS選擇先

4、執(zhí)行程序選擇先執(zhí)行程序B B的一個語句后，的一個語句后，再執(zhí)行程序再執(zhí)行程序A A的一個語句，最后執(zhí)行程序的一個語句，最后執(zhí)行程序B B的第二個語句。的第二個語句。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í)行時，結(jié)果是正確的。按的序列執(zhí)行時，結(jié)果是正確的。按(b)的序列執(zhí)行情況，則兩個旅客可的序列執(zhí)行情況，則兩個旅客可能各自都買到一張同天同次航班的機票，可是，能各自都買到一張同天同次航班的機票，可是，Aj的值實際上只減去了的值實際上只減去了1,造造成余票數(shù)的不正確。成余票數(shù)的不正確。設(shè)設(shè)Aj=50則則x1=50此時此時x2=50此時此時x1=49此時此時x2=

6、49此時此時Aj=49此時此時Aj=49特別是，當某次航班只有一張余票時，就可能把特別是，當某次航班只有一張余票時，就可能把這一張票同時售給了兩位旅客，顯然這是不能允許的。這一張票同時售給了兩位旅客，顯然這是不能允許的。設(shè)設(shè)Aj=1則則x1=1此時此時x2=1此時此時x1=0此時此時x2=0此時此時Aj=0此時此時Aj=0出錯原因是什么？出錯原因是什么？余票額是共享變量！沒有建立對共享變量余票額是共享變量！沒有建立對共享變量的使用與保護機制。的使用與保護機制。 由以上的例子說明什么？由以上的例子說明什么？ 要想實現(xiàn)多道程序并發(fā)執(zhí)行，必須設(shè)法對要想實現(xiàn)多道程序并發(fā)執(zhí)行，必須設(shè)法對共享變量（資源）

7、加入一定的管理機制和共享變量（資源）加入一定的管理機制和一定的保護措施，保證共享資源的一定的保護措施，保證共享資源的協(xié)調(diào)使協(xié)調(diào)使用用，以避免出現(xiàn)與時間有關(guān)的錯誤，以保，以避免出現(xiàn)與時間有關(guān)的錯誤，以保持并發(fā)程序的可再現(xiàn)性。持并發(fā)程序的可再現(xiàn)性。思考：對共享變量（資源）如何加思考：對共享變量（資源）如何加上這種規(guī)則（機制）呢？上這種規(guī)則（機制）呢？這是這是現(xiàn)代操作系統(tǒng)必須解決的核心問題！現(xiàn)代操作系統(tǒng)必須解決的核心問題！ 同步機制：信號傳遞？同步機制：信號傳遞？ 互斥機制：加鎖？互斥機制：加鎖？同步關(guān)系同步關(guān)系（亦稱直接制約關(guān)系）（亦稱直接制約關(guān)系）: : 指完成同一任務(wù)的伙伴進程間，因需指完成同

8、一任務(wù)的伙伴進程間，因需要在某些位置上協(xié)調(diào)它們的工作而相互等要在某些位置上協(xié)調(diào)它們的工作而相互等待、相互交換信息所產(chǎn)生的制約關(guān)系。待、相互交換信息所產(chǎn)生的制約關(guān)系。如：如：接力跑比賽中，運動員之間要配合接力跑比賽中，運動員之間要配合默契。一棒一棒接著跑。默契。一棒一棒接著跑。3.2 進程的同步與互斥例例 ：在計算機系統(tǒng)中對同一緩沖：在計算機系統(tǒng)中對同一緩沖區(qū)的數(shù)據(jù)的輸入與輸出操作。緩沖區(qū)區(qū)的數(shù)據(jù)的輸入與輸出操作。緩沖區(qū)滿才能輸出，緩沖區(qū)空才能輸入。滿才能輸出，緩沖區(qū)空才能輸入。 緩沖區(qū)緩沖區(qū)輸入輸入進程進程輸出輸出進程進程已存滿，可取已存滿，可取已取空，可存已取空，可存互斥關(guān)系互斥關(guān)系（亦稱間

9、接制約關(guān)系）（亦稱間接制約關(guān)系）: : 即進程間因相互競爭使用獨占型資即進程間因相互競爭使用獨占型資源（互斥資源）所產(chǎn)生的制約關(guān)系。源（互斥資源）所產(chǎn)生的制約關(guān)系。例（例（1 1）：上例中）：上例中ECHOECHO程序中的變量程序中的變量OUTOUT和和ININ，例（例（2 2）：飛機訂票系統(tǒng)中的余票額）：飛機訂票系統(tǒng)中的余票額AjAj必必須互斥使用。須互斥使用。例（例（3 3）：多個用戶進程同用一臺打印機）：多個用戶進程同用一臺打印機時。時。 既同步又要互斥的例子：既同步又要互斥的例子： 1 1、客車上的司機和售票員各司其職、客車上的司機和售票員各司其職為完成同一個運送乘客的任務(wù)相互配為完成

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

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

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

13、M; ;Coend;如下例對共享變量如下例對共享變量countcount的互斥訪問。的互斥訪問?；コ鈭?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三、進程互斥進入臨界區(qū)的一般結(jié)構(gòu)三、進程互斥

14、進入臨界區(qū)的一般結(jié)構(gòu) 進入臨界段之前要申請，獲得批進入臨界段之前要申請，獲得批準方可進入；準方可進入； 退出臨界段之后要聲明，以便其退出臨界段之后要聲明，以便其他進程進入。他進程進入。While( 1 ) 進入?yún)^(qū)進入?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;例如上例對共享變量例如上例對共享變量countcount的互斥訪問。的互斥訪問。臨界區(qū)臨界區(qū)臨界區(qū)臨界區(qū)Entry code(Ent

15、ry code(請求獨占請求獨占) )exit code(exit code(釋放釋放) )Entry code(Entry code(請求獨占請求獨占) )exit code(exit code(釋放釋放) )例如：對打印機（臨界資源）的互斥使用例如：對打印機（臨界資源）的互斥使用Entry code(Entry code(請求獨占請求獨占) )exit code(exit code(釋放釋放) )使用打印機的程序段使用打印機的程序段P1P1：臨界區(qū)臨界區(qū)Entry code(Entry code(請求獨占請求獨占) )exit code(exit code(釋放釋放) )使用打印機的程序段

16、使用打印機的程序段P2P2：臨界區(qū)臨界區(qū)臨界資源臨界資源四、臨界區(qū)進入準則（同步機制）四、臨界區(qū)進入準則（同步機制）準則準則1 1：空閑讓進。若無進程進入空閑空閑讓進。若無進程進入空閑的臨界區(qū)，一次僅允許一個進程進入。的臨界區(qū)，一次僅允許一個進程進入。準則準則2 2：忙則等待。任何時候，處于臨忙則等待。任何時候，處于臨界區(qū)內(nèi)的進程不可多于一個，如果已有界區(qū)內(nèi)的進程不可多于一個，如果已有進程進入自己的臨界區(qū)，則其他進程必進程進入自己的臨界區(qū)，則其他進程必須等待。須等待。準則準則3 3：有限等待。進入臨界區(qū)的進程有限等待。進入臨界區(qū)的進程要在有限時間內(nèi)退出，以便其他進程及要在有限時間內(nèi)退出，以便其

17、他進程及時進入自己的臨界區(qū)。時進入自己的臨界區(qū)。準則準則4 4：讓權(quán)等待。如果進程不能進入讓權(quán)等待。如果進程不能進入自己的臨界區(qū)，則應(yīng)讓出自己的臨界區(qū)，則應(yīng)讓出CPUCPU，避免進程，避免進程出現(xiàn)出現(xiàn)“忙等忙等”現(xiàn)象?，F(xiàn)象。四、臨界區(qū)進入準則（同步機制）四、臨界區(qū)進入準則（同步機制）Cobegin void A( ) N=count; N=N+100; count=N; ; void B( ) M=count; M=M+200; count=M; ;Coend;例如上例對共享變量例如上例對共享變量countcount的互斥訪問。的互斥訪問。臨界區(qū)臨界區(qū)臨界區(qū)臨界區(qū)Entry code(Entr

18、y code(請求獨占請求獨占) )exit code(exit code(釋放釋放) )Entry code(Entry code(請求獨占請求獨占) )exit code(exit code(釋放釋放) )3.4 互斥實現(xiàn)方法互斥實現(xiàn)方法2 2、專用機器指令、專用機器指令（1 1）“Test and SetTest and Set”指令指令管理思想：加鎖機制。開始鎖打開即未鎖上。先到的管理思想：加鎖機制。開始鎖打開即未鎖上。先到的進程拿到鎖并進入臨界區(qū)然后反鎖，直到從臨界區(qū)退進程拿到鎖并進入臨界區(qū)然后反鎖，直到從臨界區(qū)退出，開鎖交還。出，開鎖交還。該指令功能描述為：該指令功能描述為：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ù)作為一個原語執(zhí)行（即不存在中斷）。函數(shù)作為一個原語執(zhí)行（即不存在中斷）。locklock有兩種狀態(tài)：當有兩種狀態(tài)：當lock=0lock=0時，表示該資源空閑；時，表示該資源空閑；當當lock=1lock=1時，表示該資源正在被使用。時，表示該資源正在被使用。3.4 互斥實現(xiàn)方法互斥實現(xiàn)方法 例例1：利用：利用testset指令實現(xiàn)指令實現(xiàn)互斥的循環(huán)進程描述

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

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

22、，可為臨界資源設(shè)置一個全局變量進程互斥時，可為臨界資源設(shè)置一個全局變量locklock，其，其初值為初值為0 0，在每個進程中再利用一個局部變量，在每個進程中再利用一個局部變量keykey。然后。然后通過通過swapswap指令實現(xiàn)互斥。指令實現(xiàn)互斥。3.4 互斥實現(xiàn)方法互斥實現(xiàn)方法2 2、專用機器指令、專用機器指令例例2：利用：利用swap指令實現(xiàn)互斥的描述指令實現(xiàn)互斥的描述/*I為進程號，如為為進程號，如為P（2） 為進程為進程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過程，過程，則此時則此時lock=1,Key2=0,P(2)進進入臨界區(qū)。當入臨界區(qū)。當P(2)正正在臨界區(qū)時，若有另在臨界區(qū)時，若有另一進程又想進入臨界一進程又想進入臨界區(qū)，執(zhí)行區(qū)，執(zhí)行P(1)，此時，此時key1=1,lock=1,兩者交兩者交換還是換還是1，故，故P(1)只能只能循環(huán)等待。直至循環(huán)等待。直至P(2)退出臨界區(qū)，交換使退出臨界區(qū)，交換使lock=0為止。為止。v3、使用特殊機器指令實現(xiàn)互斥的優(yōu)缺點、使用特殊機器指令實現(xiàn)互斥的優(yōu)缺點優(yōu)點：優(yōu)點：（1）可用于：含有任意數(shù)量進

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

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

26、行的程序段用軟件實現(xiàn)。互斥執(zhí)行的程序段用軟件實現(xiàn)。算法算法1 1（單標志算法）（單標志算法）我們設(shè)置一個公用整型變量我們設(shè)置一個公用整型變量turnturn，用于指示被允許進入臨界區(qū)的進程的用于指示被允許進入臨界區(qū)的進程的編號，即若編號，即若turn=1turn=1，表示允許進程，表示允許進程P1P1進入臨界區(qū)。算法進入臨界區(qū)。算法1 1對對P1P1、P2P2進程的描進程的描述如下：述如下：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； 測試自己能測試自己能否進入臨界否進入臨界區(qū)區(qū)把臨界區(qū)使把臨界區(qū)使用權(quán)交給用權(quán)交給P2P2對算法一的評價：對算法一的評價：該算法可確保每次只允許一個進程進該算法可確保每次只允許一個進程進入臨界區(qū)。入臨界區(qū)。2 2個進程是輪流地進入臨界區(qū)。個進程是輪流地進入臨界區(qū)。不能保證實現(xiàn)不能保證實現(xiàn)“空閑讓進空閑讓進”的準則。的準則。 如當進程如當進程P2P2暫時并未要求訪問該臨暫時并未要求訪問該臨界資源

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

29、程時，表示進程P1P1正在臨界區(qū)正在臨界區(qū)內(nèi)執(zhí)行；若且內(nèi)執(zhí)行；若且flag1= 1flag1= 1時，表示進程時，表示進程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； 測試對方是測試對方是否在臨界區(qū)，否在臨界區(qū)，如果在，在如果在，在此循環(huán)等待此循環(huán)等待如果對方不如果對方不在臨界區(qū)，在臨界區(qū)，自己進入臨自己進入臨界區(qū)界區(qū)對算法對算法2 2的評價：的評價：算法算法2 2解決了有空讓進的問題。解決了有空讓進的問題。違背了違背了“忙則等待忙則等待”的準則。即的準則。即當當P1P1和和P2P2都未進入臨界區(qū)時，它們各自都未進入臨界區(qū)時，它們各自的訪問標志都為的訪問標志都為0.0.如果如果P1P1和和P2P2幾乎是在幾乎是在

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

32、等待；否則，P1P1進入進入臨界區(qū)；對于進程臨界區(qū)；對于進程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； 測試對方是測試對方是否在臨界區(qū)否在臨界區(qū)對算法對算法3 3的評價：的評價：算法算法3 3又會造成最終誰都不能進入臨又會造成最終誰都不能進入臨界區(qū)的后果。因而它既違背了界區(qū)的后果。因而它既違背了“有空讓進有空讓進”的準則的準則1 1，又違背了，又違背了“有限等待有限等待”的準則的準則3 3。例如，當例如，當P1P1和和P2P2幾乎在同時要進入臨界區(qū)，幾乎在同時要進入臨界區(qū)，雙方都在雙方都在“謙讓謙讓”，結(jié)果誰也進不了臨界，結(jié)果誰也進不了臨界區(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； 評價：該算法是組合了算法評價：該算法是組合了算法1 1和算法和算法3 3中的中的關(guān)鍵概念而形成的，保證了關(guān)鍵概念而形成的，保證了“忙則等待忙則等待”，又實現(xiàn)了又實現(xià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. 信號量和信號量和PVPV操作操作(semaphore)(semaphore) 由于實現(xiàn)互斥的軟件方法和硬件方法都存由于實現(xiàn)互斥的軟件方法和硬件方法都存在缺陷，故需要尋找其他機制?，F(xiàn)寄希望于在缺陷，故需要尋找其他機制?，F(xiàn)寄希望于操作系統(tǒng)和程序設(shè)計提供對并發(fā)的支持。操作系統(tǒng)和程序設(shè)計提供對并發(fā)的支持。（信號量、管程、消息傳遞）（信號

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

38、的值只能通過的值只能通過P P、V V操作來改變它。操作來改變它。二、二、P P和和V V操作原語的偽代碼形式如下：操作原語的偽代碼形式如下：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); 通過對信號量做通過對信號量做P P、V V操作來實現(xiàn)互斥訪操作來實現(xiàn)互斥訪問臨界區(qū)。問臨界區(qū)。三、三、N N個進程利用信號量、

39、個進程利用信號量、PVPV操作互操作互斥使用臨界段的一般結(jié)構(gòu)：斥使用臨界段的一般結(jié)構(gòu)：設(shè)互斥信號量設(shè)互斥信號量S S的初值為的初值為1 1 P(S)P(S)V(S)V(S)臨界區(qū)臨界區(qū)非臨界段非臨界段Do while(1)臨界資源臨界資源如打印機如打印機 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,則該進程繼續(xù)執(zhí)行；則該進程繼續(xù)執(zhí)行；如果如果s.value0,s.value0,s.value

40、0,則該進程繼續(xù)執(zhí)則該進程繼續(xù)執(zhí)行；（行；（S0S0說明等待隊列說明等待隊列queuequeue中無等待的中無等待的進程）進程） 如果如果s.value=0,s.value=0,則釋放信號量則釋放信號量隊列隊列L L上的第一個上的第一個PCBPCB所對應(yīng)的進程（把阻所對應(yīng)的進程（把阻塞態(tài)改為就緒態(tài)），執(zhí)行塞態(tài)改為就緒態(tài)），執(zhí)行V V操作的進程繼操作的進程繼續(xù)執(zhí)行。續(xù)執(zhí)行。五、五、信號量機制物理含義信號量機制物理含義1 1、信號量初值、信號量初值S.valueS.value表示系統(tǒng)中某種資表示系統(tǒng)中某種資源的數(shù)目，又稱資源信息量。源的數(shù)目，又稱資源信息量。2 2、執(zhí)行一次、執(zhí)行一次P P操作意味

41、著請求分配一個單操作意味著請求分配一個單位資源，因此位資源，因此S.valueS.value的值減的值減1 1；當當S.value0S.value0S.value0時時, ,表示等待隊列無等待該表示等待隊列無等待該信號量的進程信號量的進程, ,其值表示還可用的資源數(shù)其值表示還可用的資源數(shù)目目. .做做P P操作的進程繼續(xù)執(zhí)行操作的進程繼續(xù)執(zhí)行. .3 3、執(zhí)行一次、執(zhí)行一次V V操作意味著釋放一個單位資源，操作意味著釋放一個單位資源，因此因此S.valueS.value的值加的值加1 1；若若s.value=0s.value0s.value0時時, ,表示等待隊列無等待該表示等待隊列無等待該信

42、號量的進程信號量的進程, ,其值表示還可用的資源數(shù)其值表示還可用的資源數(shù)目目. .做做V V操作的進程繼續(xù)執(zhí)行。操作的進程繼續(xù)執(zhí)行。六、信號量的一般應(yīng)用u1 1、用信號量實現(xiàn)進程互斥、用信號量實現(xiàn)進程互斥要使要使N N個進程互斥使用某臨界資源（如打個進程互斥使用某臨界資源（如打印機），只要在每個進程的使用臨界資源印機），只要在每個進程的使用臨界資源的臨界區(qū)（即程序段）前加的臨界區(qū)（即程序段）前加P P操作，退出臨操作，退出臨界區(qū)前加界區(qū)前加V V操作，并且操作，并且n n個個進程共享一個互進程共享一個互斥信號量斥信號量S,S,初值為初值為1 1（即只允許一個進程進（即只允許一個進程進入臨界區(qū)）

43、。入臨界區(qū)）。例例1：進程：進程Pa（分配進程）和（分配進程）和Pb（釋放進程）（釋放進程）對某一打印機分配表的互斥使用情況，可用信對某一打印機分配表的互斥使用情況，可用信號量實現(xiàn)。設(shè)互斥信號量號量實現(xiàn)。設(shè)互斥信號量mutex，其初值為，其初值為1。則則Pa和和Pb的臨界區(qū)代碼可按下述方式組織：的臨界區(qū)代碼可按下述方式組織：Pa:P(mutex)分配打印機分配打印機（讀寫分配表）（讀寫分配表）V(mutex) Pb:P(mutex)釋放打印機釋放打印機（讀寫分配表）（讀寫分配表）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 輸出輸出“票已售完票已售完”； ;/*過程結(jié)束過程結(jié)束 cobegin P(1),P(2),P(n) coend例例2. 用用PV操作實現(xiàn)航空售票系統(tǒng)中訪問余票額的同操作實現(xiàn)航空售票系統(tǒng)中訪問余票額的同步與互斥。步與互斥。（該系統(tǒng)中的各進程中該系統(tǒng)

45、中的各進程中“按旅客要求找到按旅客要求找到Aj”、“輸出一張票輸出一張票”、“輸出票已售完輸出票已售完”的操作語句的操作語句屬于臨界區(qū)。）屬于臨界區(qū)。）u2 2、用信號量實現(xiàn)進程同步、用信號量實現(xiàn)進程同步u根據(jù)信號量的初值，在某個進根據(jù)信號量的初值，在某個進程的程序段程的程序段前前加加P P操作，在另一個操作，在另一個的程序段的程序段后后加加V V操作操作例例3 3、有有P1,P2 P1,P2 兩進程，必須在兩進程，必須在P P1 1執(zhí)行完執(zhí)行完S1S1語句后，語句后，P2P2才能執(zhí)行才能執(zhí)行S2S2。請用。請用PVPV操作實現(xiàn)同步操作實現(xiàn)同步（需同步的兩進程共享信號量（需同步的兩進程共享信號

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 兩進程，必須在兩進程，必須在P P1 1執(zhí)行完執(zhí)行完S1S1語句后，語句后，P2P2才能執(zhí)行才能執(zhí)行S2S2。請用。請用PVPV操作實現(xiàn)同步操作實現(xiàn)同步（需同步的兩進程共享信號量（需同步的兩進程共享信

47、號量s s，初值為，初值為0 0。）。）P2: P1: S1;V(s); P(s);S2;信號量初值為信號量初值為0，則，則P2不可能不可能先執(zhí)行，因為執(zhí)行先執(zhí)行，因為執(zhí)行P（s）操作）操作時，時，S=-10而被阻塞。而被阻塞。只有只有P1執(zhí)行完執(zhí)行完S1,發(fā)出發(fā)出V（S）操作使操作使S增增1后，后，P2才能執(zhí)行才能執(zhí)行S2例例4 4：供者：供者L1L1將讀卡機中的數(shù)據(jù)放入緩將讀卡機中的數(shù)據(jù)放入緩沖區(qū)，用者沖區(qū)，用者L2L2從緩沖區(qū)中讀取數(shù)據(jù)，用信從緩沖區(qū)中讀取數(shù)據(jù)，用信號量機制實現(xiàn)對緩沖區(qū)的同步。號量機制實現(xiàn)對緩沖區(qū)的同步。緩沖區(qū)緩沖區(qū)供者供者L1L1用者用者L2L2解：設(shè)置兩個信號量：解：

48、設(shè)置兩個信號量：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供者進程供者進程L1： do P（S1） 讀入數(shù)據(jù)至緩沖區(qū)讀入數(shù)據(jù)至緩沖區(qū) V（s2）; while（1）用者進用者進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進入進入 2: s2.value=-1,阻塞阻塞L23:s2.value=0,喚醒喚醒L2進入，進入，4:s1.value=1,L1進入進入供者進程供者進程L1： Do P（S1） 讀入數(shù)據(jù)至緩沖區(qū)讀入數(shù)據(jù)至緩沖區(qū) V（s2）; while（1）用者進用者進L2：D

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

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

52、（開車），則：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;共享變量共享變量說明說明放產(chǎn)品放產(chǎn)品過程過程取產(chǎn)品過取產(chǎn)品過程程局部變量置局部變量置初值初值如果緩如果緩沖池已沖池已滿，放滿，放產(chǎn)品過產(chǎn)品過程入等程入等待隊列待隊列如果等如果等待取的待取的隊列中隊列中有進程，有進程，則喚醒則喚醒如無產(chǎn)品如無產(chǎ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( ); . 三、管程與進程的異同三、管程與進程的異同(1)二者都定義了數(shù)據(jù)結(jié)構(gòu)。進程定義的是私有二者都定義了數(shù)據(jù)結(jié)構(gòu)。進程定義的是私有數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)PCB,管程定義的是公共數(shù)據(jù)結(jié)構(gòu)，如管程定義的是公共數(shù)據(jù)結(jié)構(gòu)，如消息隊列。消息隊列。 (2)二者都在各自的數(shù)據(jù)結(jié)構(gòu)上進行有意義的操二者都在各自的數(shù)據(jù)結(jié)構(gòu)上進行有意義的操作。進程是由順序程序執(zhí)行有關(guān)操作，管程主作。進程是由順序程序執(zhí)行有

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

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

57、概念與類型一、進程通信的概念與類型1 1、概念、概念進程通信指進程之間的信息交換。進程通信指進程之間的信息交換。2 2、類型。依據(jù)交換信息量的多少。、類型。依據(jù)交換信息量的多少。（1 1）低級通信。如進程的同步與）低級通信。如進程的同步與互斥的信號量機制。特點：互斥的信號量機制。特點：一是效率低一是效率低二是通信對用戶不透明。二是通信對用戶不透明。（2 2）高級通信。指用戶可直接）高級通信。指用戶可直接通過操作系統(tǒng)提供的一組通信命令高通過操作系統(tǒng)提供的一組通信命令高效地傳送大量數(shù)據(jù)的一種通信方式。效地傳送大量數(shù)據(jù)的一種通信方式。特點：特點：一是效率高。一是效率高。二是通信對用戶透明。二是通信對

58、用戶透明。 二、高級通信機制的類型1 1、共享存儲器系統(tǒng)、共享存儲器系統(tǒng)通信的進程共享某些數(shù)據(jù)結(jié)構(gòu)或通信的進程共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲區(qū)，進程之間能夠通過它們共享存儲區(qū)，進程之間能夠通過它們進行通信。進行通信。（1 1）基于共享數(shù)據(jù)結(jié)構(gòu)的通信方）基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式式進程間同步處理由程序員解決。進程間同步處理由程序員解決。（2 2）基于共享存儲區(qū)的通信方式）基于共享存儲區(qū)的通信方式2 2、消息傳遞系統(tǒng)、消息傳遞系統(tǒng)在消息傳遞中，進程間的數(shù)據(jù)在消息傳遞中，進程間的數(shù)據(jù)交換以消息為單位。程序員直接利用交換以消息為單位。程序員直接利用系統(tǒng)提供的通信命令（原語）來實現(xiàn)。系統(tǒng)提供的通信命令（原語

59、）來實現(xiàn)。（1 1）直接通信方式。）直接通信方式。發(fā)送進程直接將消息發(fā)送給接收發(fā)送進程直接將消息發(fā)送給接收進程并將它掛在接收進程的消息緩進程并將它掛在接收進程的消息緩沖隊列上，接收進程從消息緩沖隊沖隊列上，接收進程從消息緩沖隊列取得消息。列取得消息。Send(B,a) id:BSize:5Text:hello發(fā)發(fā)送送區(qū)區(qū)a aa a進程進程A AReceive(b) id:ASize:5Text:hello接接收收區(qū)區(qū)bb進程進程BPCB(B)mq mutexsmSize:5Text: helloNext: 0Sender:A第第1個消息緩沖區(qū)個消息緩沖區(qū)圖圖3-22 3-22 消息緩沖通信示

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