操作系統(tǒng)死鎖同步互斥CH6c5

1、進(jìn)程間的制約關(guān)系進(jìn)程間的制約關(guān)系第第 6 6 章章 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 柴忠良柴忠良 2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)6.1 進(jìn)程間的制約關(guān)系16.3 死鎖、高級(jí)進(jìn)程通信3本章講述內(nèi)容本章講述內(nèi)容6.2 信號(hào)量與P、V操作12013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 本章將引入操作系統(tǒng)中的重要概念：信號(hào)本章將引入操作系統(tǒng)中的重要概念：信號(hào)量以及在信號(hào)量上的量以及在信號(hào)量上的P P、V V操作。利用信號(hào)量以操作。利用信號(hào)量以及在信號(hào)量上的及在信號(hào)量上的P P、V V操作，可以很好地解決進(jìn)操作，可以很好地解決進(jìn)程間的互斥與同步關(guān)系，保證進(jìn)程程序的正確程間的互斥與同步關(guān)系，保證進(jìn)程程序的正確執(zhí)

2、行。執(zhí)行。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 本章著重講述四個(gè)方面的內(nèi)容：本章著重講述四個(gè)方面的內(nèi)容：v（1 1）進(jìn)程間的兩種制約關(guān)系）進(jìn)程間的兩種制約關(guān)系互斥與同步?；コ馀c同步。v（2 2）正確處理互斥與同步的方法）正確處理互斥與同步的方法信號(hào)量信號(hào)量 以及在信號(hào)量上的以及在信號(hào)量上的P P、V V操作。操作。v（3 3）死鎖以及解決死鎖的途徑。）死鎖以及解決死鎖的途徑。v（4 4）進(jìn)程間的高級(jí)通信。）進(jìn)程間的高級(jí)通信。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)進(jìn)程的順序性進(jìn)程的順序性馮諾依曼結(jié)構(gòu)的基本特性是處理器順序執(zhí)行命令。當(dāng)一個(gè)進(jìn)程獨(dú)占CPU時(shí)具有以下特性：v順序性：處理機(jī)的操作嚴(yán)格

3、按照程序所規(guī)定的順序執(zhí)行。v封閉性：進(jìn)程執(zhí)行的結(jié)果取決于進(jìn)程本身，不受外界影響。v可再現(xiàn)性：當(dāng)進(jìn)程再次重復(fù)執(zhí)行時(shí)，必定獲得相同的結(jié)果。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)進(jìn)程的并發(fā)性進(jìn)程的并發(fā)性如果系統(tǒng)中存在一組可同時(shí)執(zhí)行的進(jìn)程。并發(fā)進(jìn)程之間可能是無(wú)關(guān)的，也可能是有關(guān)的相互依賴(lài)。當(dāng)多個(gè)進(jìn)程共享CPU時(shí)具有以下特性：v間斷性：不再是一口氣運(yùn)行下去，出現(xiàn)走走停?，F(xiàn)象，停的次數(shù)和地方不再相同。v封閉性被打破：不同的時(shí)間運(yùn)行的進(jìn)程個(gè)數(shù)、是誰(shuí)以及它們的執(zhí)行時(shí)間不同，受外界影響。v不可再現(xiàn)性：當(dāng)進(jìn)程再次重復(fù)執(zhí)行時(shí)，運(yùn)行的過(guò)程和運(yùn)行的結(jié)果不一定相同。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)6.1 進(jìn)程間的制

4、約關(guān)系v6.1.1 6.1.1 與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤v 在相同的前提條件下，兩次執(zhí)行的結(jié)果有在相同的前提條件下，兩次執(zhí)行的結(jié)果有可能不相同。在操作系統(tǒng)里，把這種由于時(shí)間可能不相同。在操作系統(tǒng)里，把這種由于時(shí)間因素的影響而產(chǎn)生的錯(cuò)誤，稱(chēng)為因素的影響而產(chǎn)生的錯(cuò)誤，稱(chēng)為“與時(shí)間有關(guān)與時(shí)間有關(guān)的錯(cuò)誤的錯(cuò)誤”。 2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)例：游樂(lè)場(chǎng)自動(dòng)計(jì)數(shù)系統(tǒng)。例：游樂(lè)場(chǎng)自動(dòng)計(jì)數(shù)系統(tǒng)。BeginCount:integer;Count:=0;CobeginCoend;End;Process PINR1:integer;BeginR1:=count;R1:=R1+1;count:=R

5、1;End;Process POUTR2:integer;BeginR2:=count;R2:=R2-1;count:=R2;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)例：飛機(jī)航班售票系統(tǒng)。例：飛機(jī)航班售票系統(tǒng)。Aj:j次航班余票數(shù)j=1,2,3mPi:i航班處理進(jìn)程i=1,2,3nRi:各進(jìn)程工作單元售票處1售票處5售票處4售票處3售票處22013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)例：飛機(jī)航班售票系統(tǒng)。例：飛機(jī)航班售票系統(tǒng)。Process Pi(i=1,2,3n)Ri:integer;Begin按旅客要求找到Aj;Ri:=Aj;if Ri=1 thenelse 輸出“票已售完”End;Beg

6、inRi:=Ri-1;Aj:=Ri;輸出一張票End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 圖圖6-1 6-1 對(duì)輸出井文件目錄的管理對(duì)輸出井文件目錄的管理2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 圖圖6-2 6-2 通過(guò)雙緩沖區(qū)復(fù)制文件通過(guò)雙緩沖區(qū)復(fù)制文件2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 圖圖6-3 GETPUTCOPY6-3 GETPUTCOPY導(dǎo)致錯(cuò)誤導(dǎo)致錯(cuò)誤2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v6.1.2 6.1.2 競(jìng)爭(zhēng)資源競(jìng)爭(zhēng)資源互斥互斥v 在操作系統(tǒng)中，凡是牽扯到數(shù)據(jù)、隊(duì)列、在操作系統(tǒng)中，凡是牽扯到數(shù)據(jù)、隊(duì)列、緩沖區(qū)、表格和變量等任何形式的共享資源時(shí)，緩沖區(qū)、表格和變量等

7、任何形式的共享資源時(shí)，都很容易出現(xiàn)類(lèi)似的這種都很容易出現(xiàn)類(lèi)似的這種“與時(shí)間有關(guān)的錯(cuò)與時(shí)間有關(guān)的錯(cuò)誤誤”。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 為了避免錯(cuò)誤的發(fā)生，關(guān)鍵是要找到一種為了避免錯(cuò)誤的發(fā)生，關(guān)鍵是要找到一種途徑，來(lái)阻止多于一個(gè)進(jìn)程同時(shí)使用它們。也途徑，來(lái)阻止多于一個(gè)進(jìn)程同時(shí)使用它們。也就是說(shuō)，保證對(duì)它們的使用是互斥進(jìn)行的。就是說(shuō)，保證對(duì)它們的使用是互斥進(jìn)行的。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 與一個(gè)共享變量（或臨界資源）交往的多與一個(gè)共享變量（或臨界資源）交往的多個(gè)進(jìn)程，為了保證它們各自運(yùn)行結(jié)果的正確性，個(gè)進(jìn)程，為了保證它們各自運(yùn)行結(jié)果的正確性，當(dāng)其中的一個(gè)進(jìn)程正在對(duì)該變量

8、（或臨界資源）當(dāng)其中的一個(gè)進(jìn)程正在對(duì)該變量（或臨界資源）進(jìn)行操作時(shí)，就不允許其他進(jìn)程同時(shí)對(duì)它進(jìn)行進(jìn)行操作時(shí)，就不允許其他進(jìn)程同時(shí)對(duì)它進(jìn)行操作。進(jìn)程間的這種制約關(guān)系被稱(chēng)為操作。進(jìn)程間的這種制約關(guān)系被稱(chēng)為“互斥互斥”。 2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 進(jìn)程A 進(jìn)程B共享變量COUNT2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)對(duì)具有互斥關(guān)系的進(jìn)程，要注意以下四點(diǎn)：v（1 1）只有涉及共享變量的那一部分程序，才）只有涉及共享變量的那一部分程序，才真正需要保證互斥地執(zhí)行。通常，把進(jìn)程程序真正需要保證互斥地執(zhí)行。通常，把進(jìn)程程序中中“真正需要保證互斥執(zhí)行真正需要保證互斥執(zhí)行”的那一段程序，的那一段程

9、序，稱(chēng)為該進(jìn)程的稱(chēng)為該進(jìn)程的“臨界區(qū)（或臨界段）臨界區(qū)（或臨界段）”。 2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 進(jìn)程A 進(jìn)程B共享變量COUNT2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)例：游樂(lè)場(chǎng)自動(dòng)計(jì)數(shù)系統(tǒng)。例：游樂(lè)場(chǎng)自動(dòng)計(jì)數(shù)系統(tǒng)。BeginCount:integer;Count:=0;CobeginCoend;End;Process PINR1:integer;BeginR1:=count;R1:=R1+1;count:=R1;End;Process POUTR2:integer;BeginR2:=count;R2:=R2-1;count:=R2;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)

10、業(yè)v（2 2）具有互斥關(guān)系的進(jìn)程，并不關(guān)心對(duì)方的）具有互斥關(guān)系的進(jìn)程，并不關(guān)心對(duì)方的存在性。即使對(duì)方不存在，自己也能夠正確的存在性。即使對(duì)方不存在，自己也能夠正確的運(yùn)行，不會(huì)受到它存在與否的影響。運(yùn)行，不會(huì)受到它存在與否的影響。v（3 3）具有互斥關(guān)系進(jìn)程的臨界區(qū)，雖然都是）具有互斥關(guān)系進(jìn)程的臨界區(qū)，雖然都是針對(duì)同一個(gè)共享變量的程序段，但在其上的操針對(duì)同一個(gè)共享變量的程序段，但在其上的操作可以相同也可以不相同。作可以相同也可以不相同。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)相關(guān)臨界區(qū)相關(guān)臨界區(qū)v（4 4）進(jìn)程的臨界區(qū)是相對(duì)于某個(gè)共享變量而）進(jìn)程的臨界區(qū)是相對(duì)于某個(gè)共享變量而言的，不同共享變量的臨

11、界區(qū)之間，不存在互言的，不同共享變量的臨界區(qū)之間，不存在互斥關(guān)系。斥關(guān)系。XY2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)相關(guān)臨界區(qū)執(zhí)行時(shí)必須遵循以下準(zhǔn)則：v（1）每次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)每次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)。v（2）一個(gè)進(jìn)程在臨界區(qū)內(nèi)逗留有限時(shí)間后，）一個(gè)進(jìn)程在臨界區(qū)內(nèi)逗留有限時(shí)間后，就應(yīng)該退出，以便給其他進(jìn)程創(chuàng)造進(jìn)入臨界區(qū)就應(yīng)該退出，以便給其他進(jìn)程創(chuàng)造進(jìn)入臨界區(qū)的機(jī)會(huì)。的機(jī)會(huì)。v（3）不能強(qiáng)迫一個(gè)進(jìn)程在臨界區(qū)外無(wú)限期逗）不能強(qiáng)迫一個(gè)進(jìn)程在臨界區(qū)外無(wú)限期逗留。留。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)相關(guān)臨界區(qū)三原則 有限時(shí)間進(jìn)有限時(shí)間進(jìn) 一次一個(gè)一次一個(gè) 有限時(shí)間出有限時(shí)間出1201

12、3 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v6.1.3 6.1.3 協(xié)同工作協(xié)同工作同步同步這里所描述的進(jìn)程間的關(guān)系有如下特點(diǎn)：這里所描述的進(jìn)程間的關(guān)系有如下特點(diǎn)：v（1 1）具有這種關(guān)系的進(jìn)程，需要在某些點(diǎn)上）具有這種關(guān)系的進(jìn)程，需要在某些點(diǎn)上協(xié)調(diào)相互的動(dòng)作，誰(shuí)先到達(dá)誰(shuí)后到達(dá)是有順序協(xié)調(diào)相互的動(dòng)作，誰(shuí)先到達(dá)誰(shuí)后到達(dá)是有順序要求的。要求的。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 圖圖6-4 GET6-4 GET和和COPYCOPY協(xié)調(diào)一致地工作協(xié)調(diào)一致地工作2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v（2 2）這些進(jìn)程都應(yīng)該了解對(duì)方的工作，對(duì)方）這些進(jìn)程都應(yīng)該了解對(duì)方的工作，對(duì)方不存在，或任何一方單獨(dú)運(yùn)行，

13、就會(huì)出現(xiàn)差錯(cuò)。不存在，或任何一方單獨(dú)運(yùn)行，就會(huì)出現(xiàn)差錯(cuò)。v（3 3）一方或雙方的運(yùn)行會(huì)直接地依賴(lài)于對(duì)方）一方或雙方的運(yùn)行會(huì)直接地依賴(lài)于對(duì)方所產(chǎn)生的信息或發(fā)出的消息。所產(chǎn)生的信息或發(fā)出的消息。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)，除非合作進(jìn)程已一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)，除非合作進(jìn)程已經(jīng)完成了某種操作或發(fā)來(lái)了信息，否則就必須經(jīng)完成了某種操作或發(fā)來(lái)了信息，否則就必須暫時(shí)等待那些操作的完成或信息的到來(lái)。暫時(shí)等待那些操作的完成或信息的到來(lái)。握手和均值2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 進(jìn)程間的這種關(guān)系被稱(chēng)為進(jìn)程間的這種關(guān)系被稱(chēng)為“同步同步”。暫停等。暫停等待以取得同步的那

14、一點(diǎn)，稱(chēng)為待以取得同步的那一點(diǎn)，稱(chēng)為“同步點(diǎn)同步點(diǎn)”，需，需要等待一個(gè)進(jìn)程完成的操作或發(fā)送的信息，稱(chēng)要等待一個(gè)進(jìn)程完成的操作或發(fā)送的信息，稱(chēng)為為“同步條件同步條件”。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)6.2 信號(hào)量與P、V操作v 通過(guò)信號(hào)量取不同的初值以及在其上做通過(guò)信號(hào)量取不同的初值以及在其上做P P、V V操作，就能夠?qū)崿F(xiàn)進(jìn)程間的互斥、同步，甚操作，就能夠?qū)崿F(xiàn)進(jìn)程間的互斥、同步，甚至用來(lái)管理資源的分配。至用來(lái)管理資源的分配。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v6.2.1 6.2.1 信號(hào)量與信號(hào)量與P P、V V操作的定義操作的定義v 所謂所謂“信號(hào)量信號(hào)量”，是一個(gè)具有非負(fù)初值的

15、，是一個(gè)具有非負(fù)初值的整型變量，并且有一個(gè)隊(duì)列與它關(guān)聯(lián)。整型變量，并且有一個(gè)隊(duì)列與它關(guān)聯(lián)。 2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 在一個(gè)信號(hào)量在一個(gè)信號(hào)量S S上，只能做規(guī)定的兩種操上，只能做規(guī)定的兩種操作：作：P P操作，記為操作，記為P P（S S）；和）；和V V操作，記為操作，記為V V（S S）。）。P P、V V操作的具體定義如下。操作的具體定義如下。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v（1 1）信號(hào)量）信號(hào)量S S上的上的P P操作定義操作定義: :v當(dāng)一個(gè)進(jìn)程調(diào)用當(dāng)一個(gè)進(jìn)程調(diào)用P P（S S）時(shí)，應(yīng)該順序做下面不）時(shí)，應(yīng)該順序做下面不可分割的兩個(gè)動(dòng)作?？煞指畹膬蓚€(gè)動(dòng)作。

16、vVs = VsVs = Vs 1 1，即把當(dāng)前信號(hào)量，即把當(dāng)前信號(hào)量S S的取值減的取值減1 1。v若若Vs = 0Vs = 0，則調(diào)用進(jìn)程繼續(xù)運(yùn)行；若，則調(diào)用進(jìn)程繼續(xù)運(yùn)行；若Vs0Vs0，則調(diào)用進(jìn)程由運(yùn)行狀態(tài)變?yōu)樽枞麪顟B(tài)，到與該則調(diào)用進(jìn)程由運(yùn)行狀態(tài)變?yōu)樽枞麪顟B(tài)，到與該信號(hào)量有關(guān)的隊(duì)列信號(hào)量有關(guān)的隊(duì)列VqVq上排隊(duì)等待，直到其他進(jìn)上排隊(duì)等待，直到其他進(jìn)程在程在S S上執(zhí)行上執(zhí)行V V操作將其釋放為止。操作將其釋放為止。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)P(S) V(S)Procedure P(Var S:semaphore)BeginS:=S-1;if S0 then W(S)End;

17、PProcedure V(Var S:semaphore)BeginS:=S+1;if S 0Vs 0，則調(diào)用進(jìn)程繼續(xù)運(yùn)行；若，則調(diào)用進(jìn)程繼續(xù)運(yùn)行；若Vs=Vs=1 thenelse 輸出“票已售完”End;BeginRi:=Ri-1;Aj:=Ri;V(S);輸出一張票End;BeginS:semaphore;S:=1;CobeginCoend;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)例：飛機(jī)航班售票系統(tǒng)。例：飛機(jī)航班售票系統(tǒng)。Process Pi(i=1,2,3n)Ri:integer;Begin按旅客要求找到Aj;P(S)；Ri:=Aj;if Ri=1 thenelse 輸出“票已售

18、完”End;BeginRi:=Ri-1;Aj:=Ri;V(S);輸出一張票End;BeginS:semaphore;S:=1;CobeginCoend;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)例：飛機(jī)航班售票系統(tǒng)。例：飛機(jī)航班售票系統(tǒng)。Process Pi(i=1,2,3n)Ri:integer;Begin按旅客要求找到Aj;P(S)；Ri:=Aj;if Ri=1 thenelse begin V(S); 輸出“票已售完” end;End;BeginRi:=Ri-1;Aj:=Ri;V(S);輸出一張票End;BeginS:semaphore;S:=1;CobeginCoend;End;2

19、013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)序調(diào)用進(jìn)程PV操作臨界區(qū)內(nèi)被S阻塞S的值112AP(S)A03AV(S)14BP(S)B05CP(S)BC-16DP(S)BC D-27EP(S)BC D E-38BV(S)DC E-29FP(S)DC E F-310DV(S)EC F-211非A-FEC F-212EV(S)FC-113FV(S)C014CV(S)12013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 圖圖6-5 P6-5 P、V V操作用于進(jìn)程互斥操作用于進(jìn)程互斥2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 設(shè)置一個(gè)初值為設(shè)置一個(gè)初值為1 1的信號(hào)量的信號(hào)量S S，在進(jìn)程，在進(jìn)程A A和和B B的進(jìn)入點(diǎn)處

20、安排關(guān)于信號(hào)量的進(jìn)入點(diǎn)處安排關(guān)于信號(hào)量S S的的P P操作，在進(jìn)程操作，在進(jìn)程A A和和B B的退出點(diǎn)處安排關(guān)于信號(hào)量的退出點(diǎn)處安排關(guān)于信號(hào)量S S的的V V操作。這操作。這樣，就能夠確保樣，就能夠確保CSaCSa和和CSbCSb互斥地執(zhí)行?；コ獾貓?zhí)行。 2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 例例6-1 6-1 在第在第2 2章的圖章的圖2-22-2中，給出了一個(gè)中，給出了一個(gè)“觀察者觀察者- -報(bào)告者報(bào)告者”的例子。試用信號(hào)量上的的例子。試用信號(hào)量上的P P、V V操作來(lái)保證它們正確地配合工作。操作來(lái)保證它們正確地配合工作。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)圖圖6-6 “觀察者觀察者

21、-報(bào)告者報(bào)告者”問(wèn)題的問(wèn)題的P、V操作解法操作解法2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v6.2.3 6.2.3 用用P P、V V操作實(shí)現(xiàn)同步操作實(shí)現(xiàn)同步互斥是特殊的同步：空間限制互斥是特殊的同步：空間限制 協(xié)調(diào)同步：時(shí)間限制協(xié)調(diào)同步：時(shí)間限制記錄和均值2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 圖圖6-7 P6-7 P、V V操作用于進(jìn)程同步操作用于進(jìn)程同步2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 為了保證做到這一點(diǎn)，設(shè)置一個(gè)初值為為了保證做到這一點(diǎn)，設(shè)置一個(gè)初值為0 0的信號(hào)量的信號(hào)量S S，在進(jìn)程，在進(jìn)程A A的的X X點(diǎn)處（即同步點(diǎn)），點(diǎn)處（即同步點(diǎn)），安排一個(gè)關(guān)于信號(hào)量安排一個(gè)關(guān)于信號(hào)

22、量S S的的P P操作，在進(jìn)程操作，在進(jìn)程B B的的Y Y點(diǎn)點(diǎn)處安排關(guān)于信號(hào)量處安排關(guān)于信號(hào)量S S的的V V操作。操作。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 這樣，就能夠確保進(jìn)程這樣，就能夠確保進(jìn)程A A在在X X點(diǎn)處與進(jìn)程點(diǎn)處與進(jìn)程B B取得同步了。取得同步了。 2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 例例6-2 6-2 試用信號(hào)量上的試用信號(hào)量上的P P、V V操作，來(lái)保操作，來(lái)保證如圖證如圖6-46-4所示的所示的GETGET和和COPYCOPY兩者之間協(xié)調(diào)地工兩者之間協(xié)調(diào)地工作。作。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 圖圖6-8 6-8 用用P P、V V操作保證操作保證G

23、ETGET和和COPYCOPY間的協(xié)作關(guān)系間的協(xié)作關(guān)系2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v6.2.4 6.2.4 用用P P、V V操作實(shí)現(xiàn)資源分配操作實(shí)現(xiàn)資源分配v 如果把信號(hào)量的初始值，比如如果把信號(hào)量的初始值，比如n n，理解為，理解為是系統(tǒng)中某種資源的數(shù)目，那么，在它的上面是系統(tǒng)中某種資源的數(shù)目，那么，在它的上面做做P P操作，即是申請(qǐng)一個(gè)資源；在它的上面做操作，即是申請(qǐng)一個(gè)資源；在它的上面做V V操作，即是釋放一個(gè)用完的資源。操作，即是釋放一個(gè)用完的資源。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 與該信號(hào)量有關(guān)的隊(duì)列，是資源等待隊(duì)列。與該信號(hào)量有關(guān)的隊(duì)列，是資源等待隊(duì)列。 201

24、3 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 在用在用P P、V V操作實(shí)現(xiàn)資源分配時(shí)，把所設(shè)置操作實(shí)現(xiàn)資源分配時(shí)，把所設(shè)置的信號(hào)量初值設(shè)為資源的個(gè)數(shù)的信號(hào)量初值設(shè)為資源的個(gè)數(shù)n n。在進(jìn)行資源。在進(jìn)行資源分配的進(jìn)程中對(duì)信號(hào)量做分配的進(jìn)程中對(duì)信號(hào)量做P P操作。每做一次操作。每做一次P P操操作，就分配一個(gè)資源。作，就分配一個(gè)資源。 2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 在進(jìn)行資源回收的進(jìn)程里對(duì)信號(hào)量做在進(jìn)行資源回收的進(jìn)程里對(duì)信號(hào)量做V V操操作。每做一次作。每做一次V V操作，就收回一個(gè)資源。操作，就收回一個(gè)資源。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 由于資源初啟時(shí)共有由于資源初啟時(shí)共有n n

25、個(gè)，如果對(duì)資源進(jìn)個(gè)，如果對(duì)資源進(jìn)行連續(xù)行連續(xù)n n次申請(qǐng)，都能夠立即得到滿足。但第次申請(qǐng)，都能夠立即得到滿足。但第n n+1+1個(gè)提出申請(qǐng)的進(jìn)程就不得不在資源等待隊(duì)個(gè)提出申請(qǐng)的進(jìn)程就不得不在資源等待隊(duì)列中等待了。列中等待了。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 例例 “ “生產(chǎn)者生產(chǎn)者- -消費(fèi)者消費(fèi)者”問(wèn)題）假定有問(wèn)題）假定有m m個(gè)個(gè)生產(chǎn)者和生產(chǎn)者和r r個(gè)消費(fèi)者，他們共享個(gè)消費(fèi)者，他們共享n n個(gè)緩沖區(qū)。個(gè)緩沖區(qū)。 生產(chǎn)者生產(chǎn)者 容器容器 消費(fèi)者消費(fèi)者v 1 : 1 : 11 : 1 : 1v 1 : n : 1 1 : n : 1v m : n : r m : n : r2013

26、計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 生產(chǎn)者生產(chǎn)者 容器容器 消費(fèi)者消費(fèi)者v 1 : 1 : 11 : 1 : 112013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)Beginbuffer:integer;SP,SG:semaphore;SP:=1;SG:=0;Cobegin生產(chǎn)者、消費(fèi)者進(jìn)程Coend;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)生產(chǎn)者、消費(fèi)者進(jìn)程生產(chǎn)者、消費(fèi)者進(jìn)程Process producerBeginL1: produce a product; P(SP); buffer:=product; V(SG);goto L1;End;Process consumerBeginL2: P(SG)

27、;take a product; V(SP);consume;goto L1;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 例例6-3 6-3 （簡(jiǎn)單的（簡(jiǎn)單的“生產(chǎn)者生產(chǎn)者- -消費(fèi)者消費(fèi)者”問(wèn)題）問(wèn)題）假定有一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者，他們共享假定有一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者，他們共享1010個(gè)緩沖區(qū)。生產(chǎn)者不斷地生產(chǎn)物品，將每個(gè)物個(gè)緩沖區(qū)。生產(chǎn)者不斷地生產(chǎn)物品，將每個(gè)物品依次放入緩沖區(qū)中（一個(gè)緩沖區(qū)正好放一個(gè)品依次放入緩沖區(qū)中（一個(gè)緩沖區(qū)正好放一個(gè)物品）。物品）。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 消費(fèi)者依次從緩沖區(qū)中取出物品進(jìn)行消費(fèi)。消費(fèi)者依次從緩沖區(qū)中取出物品進(jìn)行消費(fèi)。只有在緩沖區(qū)

28、中有空位時(shí)，生產(chǎn)者生產(chǎn)出來(lái)的只有在緩沖區(qū)中有空位時(shí)，生產(chǎn)者生產(chǎn)出來(lái)的物品才能往里面放；只有在緩沖區(qū)有物品時(shí)，物品才能往里面放；只有在緩沖區(qū)有物品時(shí)，消費(fèi)者才能從它的里面取出物品。試用消費(fèi)者才能從它的里面取出物品。試用P P、V V操操作來(lái)協(xié)調(diào)生產(chǎn)者和消費(fèi)者之間的工作。作來(lái)協(xié)調(diào)生產(chǎn)者和消費(fèi)者之間的工作。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 圖圖6-9 P6-9 P、V V操作用于操作用于“簡(jiǎn)單生產(chǎn)者簡(jiǎn)單生產(chǎn)者- -消費(fèi)者消費(fèi)者”問(wèn)題問(wèn)題2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 生產(chǎn)者生產(chǎn)者 容器容器 消費(fèi)者消費(fèi)者 1 : n : 11 : n : 1k kt tB0B1BtBkBn-12013

29、計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)BeginB:array0(n-1) of integer;k,t:integer; k:=0;t:=0;SP,SG:semaphore;SP:=n;SG:=0;Cobegin生產(chǎn)者、消費(fèi)者進(jìn)程Coend;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)生產(chǎn)者、消費(fèi)者進(jìn)程生產(chǎn)者、消費(fèi)者進(jìn)程Process producerBeginL1: produce a product; P(SP); B(k):=product;k:=k+1; V(SG);goto L1;End;Process consumerBeginL2: P(SG);take a product from

30、B(t); t:=t+1; V(SP);consume;goto L1;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)生產(chǎn)者、消費(fèi)者進(jìn)程生產(chǎn)者、消費(fèi)者進(jìn)程Process producerBeginL1: produce a product; P(SP); B(k):=product;k:=(k+1) mod n; V(SG);goto L1;End;Process consumerBeginL2: P(SG);take a product from B(t); t:=(t+1) mod n; V(SP);consume;goto L1;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v6.2.5

31、 6.2.5 互斥互斥/ /同步的樣例分析同步的樣例分析2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 例例6-4 6-4 （“生產(chǎn)者生產(chǎn)者- -消費(fèi)者消費(fèi)者”問(wèn)題）假定問(wèn)題）假定有有i i個(gè)生產(chǎn)者和個(gè)生產(chǎn)者和j j個(gè)消費(fèi)者，他們共享個(gè)消費(fèi)者，他們共享k k個(gè)緩沖個(gè)緩沖區(qū)。生產(chǎn)者不斷地生產(chǎn)物品，將每個(gè)物品依次區(qū)。生產(chǎn)者不斷地生產(chǎn)物品，將每個(gè)物品依次放入緩沖區(qū)中（一個(gè)緩沖區(qū)正好放一個(gè)物品）。放入緩沖區(qū)中（一個(gè)緩沖區(qū)正好放一個(gè)物品）。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 消費(fèi)者依次從緩沖區(qū)中取出物品進(jìn)行消費(fèi)。消費(fèi)者依次從緩沖區(qū)中取出物品進(jìn)行消費(fèi)。只有在緩沖區(qū)中有空位時(shí)，生產(chǎn)者生產(chǎn)出來(lái)的只有在緩沖區(qū)中

32、有空位時(shí)，生產(chǎn)者生產(chǎn)出來(lái)的物品才能往里面放；只有在緩沖區(qū)有物品時(shí)，物品才能往里面放；只有在緩沖區(qū)有物品時(shí)，消費(fèi)者才能從它的里面取出物品。試用消費(fèi)者才能從它的里面取出物品。試用P P、V V操操作來(lái)協(xié)調(diào)生產(chǎn)者和消費(fèi)者之間的工作。作來(lái)協(xié)調(diào)生產(chǎn)者和消費(fèi)者之間的工作。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 圖圖6-10 P6-10 P、V V操作用于操作用于“生產(chǎn)者生產(chǎn)者- -消費(fèi)者消費(fèi)者”問(wèn)題問(wèn)題2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 生產(chǎn)者生產(chǎn)者 容器容器 消費(fèi)者消費(fèi)者 m : n : rm : n : rk kt tS1S1 S2 S2B0B1BtBkBn-12013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)

33、業(yè)BeginB:array0(n-1) of integer;k,t:integer; k:=0;t:=0;S1,S2,SP,SG:semaphore;S1=1;S2:=1;SP:=n;SG:=0;Cobegin生產(chǎn)者、消費(fèi)者進(jìn)程Coend;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)生產(chǎn)者、消費(fèi)者進(jìn)程生產(chǎn)者、消費(fèi)者進(jìn)程Process producer i(i=1,2m)BeginL1: produce a product; P(SP);P(S1); B(k):=product;k:=(k+1) mod n; V(S1); V(SG);goto L1;End;Process consumer

34、 j(j=1,2r)BeginL2: P(SG);P(S2);take a product from B(t); t:= :=(t+1) mod n; V(S2); V(SP); consume;goto L1;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 互斥、資源分配，只是同步的不同表現(xiàn)形式互斥、資源分配，只是同步的不同表現(xiàn)形式罷了。罷了?；コ馐翘厥獾耐剑嚎臻g限制互斥是特殊的同步：空間限制 協(xié)調(diào)同步：時(shí)間限制協(xié)調(diào)同步：時(shí)間限制2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 例例6-5 6-5 （“讀者讀者- -寫(xiě)者寫(xiě)者”問(wèn)題）若一批數(shù)問(wèn)題）若一批數(shù)據(jù)被多個(gè)并發(fā)進(jìn)程共享使用。其中一些進(jìn)程只據(jù)

35、被多個(gè)并發(fā)進(jìn)程共享使用。其中一些進(jìn)程只要求讀數(shù)據(jù)，稱(chēng)為要求讀數(shù)據(jù)，稱(chēng)為“讀者讀者”；另一些會(huì)對(duì)數(shù)據(jù)；另一些會(huì)對(duì)數(shù)據(jù)進(jìn)行修改，稱(chēng)為進(jìn)行修改，稱(chēng)為“寫(xiě)者寫(xiě)者”。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 多個(gè)讀者同時(shí)工作時(shí)，訪問(wèn)不會(huì)有問(wèn)題。但多個(gè)讀者同時(shí)工作時(shí)，訪問(wèn)不會(huì)有問(wèn)題。但是讀者和寫(xiě)者或?qū)懻吆蛯?xiě)者同時(shí)工作時(shí)，就可是讀者和寫(xiě)者或?qū)懻吆蛯?xiě)者同時(shí)工作時(shí)，就可能導(dǎo)致錯(cuò)誤的訪問(wèn)結(jié)果。能導(dǎo)致錯(cuò)誤的訪問(wèn)結(jié)果。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 假定在有讀者訪問(wèn)時(shí)，又來(lái)寫(xiě)者要求訪問(wèn)，假定在有讀者訪問(wèn)時(shí)，又來(lái)寫(xiě)者要求訪問(wèn)，那么寫(xiě)者只能等待，而后續(xù)到來(lái)的讀者則可以那么寫(xiě)者只能等待，而后續(xù)到來(lái)的讀者則可以進(jìn)行

36、訪問(wèn)（這就是隱含讀者比寫(xiě)者有更高的訪進(jìn)行訪問(wèn)（這就是隱含讀者比寫(xiě)者有更高的訪問(wèn)權(quán)）。試用問(wèn)權(quán)）。試用P P、V V操作來(lái)協(xié)調(diào)讀者和寫(xiě)者之間操作來(lái)協(xié)調(diào)讀者和寫(xiě)者之間的工作。的工作。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) P(MUTEX) P(MUTEX) P(MUTEX) V(MUTEX) V(WRT) V(WRT) P(WRT) P(WRT) 圖圖6-11 P6-11 P、V V操作用于操作用于“讀者讀者- -寫(xiě)者寫(xiě)者”問(wèn)題問(wèn)題2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)過(guò)鐵橋、過(guò)隧道過(guò)鐵橋、過(guò)隧道BeginE,W,Flag:Semaphore;E=1;W:=1;Flag:=1;CE,CW: int

37、eger;CE:=0; CW:=0;Cobegin過(guò)鐵橋 或 過(guò)隧道進(jìn)程Coend;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)過(guò)鐵橋、過(guò)隧道進(jìn)程過(guò)鐵橋、過(guò)隧道進(jìn)程Process EastBegin L1 : P(E);if CE=0 Then P(Flag);CE:=CE+1;V(E); 過(guò)橋 或 過(guò)隧道；P(E);if CE=1 Then V(Flag);CE:=CE-1;V(E);goto L1;End;Process WestBegin L2: P(W);if CW=0 Then P(Flag);CW:=CW+1;V(W); 過(guò)橋 或 過(guò)隧道；P(W);if CW=1 Then V(

38、Flag);CW:=CW-1;V(W);goto L2;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)過(guò)鐵橋、過(guò)隧道進(jìn)程過(guò)鐵橋、過(guò)隧道進(jìn)程Process EastBegin P(E);if CE=0 Then P(Flag);CE:=CE+1;V(E); 過(guò)橋 或 過(guò)隧道；P(E);if CE=1 Then V(Flag);CE:=CE-1;V(E);End;Process WestBegin P(W);if CW=0 Then P(Flag);CW:=CW+1;V(W); 過(guò)橋 或 過(guò)隧道；P(W);if CW=1 Then V(Flag);CW:=CW-1;V(W);End;2013 計(jì)算

39、機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)過(guò)鐵橋、過(guò)隧道進(jìn)程過(guò)鐵橋、過(guò)隧道進(jìn)程Process EastBegin P(E);CE:=CE+1;if CE=1 Then P(Flag);V(E); 過(guò)橋 或 過(guò)隧道；P(E);CE:=CE-1;if CE=0 Then V(Flag);V(E);End;Process WestBegin P(W);if CW=0 Then P(Flag);CW:=CW+1;V(W); 過(guò)橋 或 過(guò)隧道；P(W);if CW=1 Then V(Flag);CW:=CW-1;V(W);End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 圖圖6-12 6-12 不正確的解法不正確的解法20

40、13 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 圖圖6-13 6-13 又一個(gè)不正確的解法又一個(gè)不正確的解法2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)補(bǔ)充：水果問(wèn)題補(bǔ)充：水果問(wèn)題v看似2:1:2v 父 兒v 母 女盤(pán)子2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)BeginS,SP,SO:semaphore;S:=1;SP:=0;SO:=0;Cobegin生產(chǎn)者父母、消費(fèi)者兒女進(jìn)程Coend;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)Process fatherBeginL1: have an apple; P(S);put an apple into plate;V(SP);goto L1;End;Proces

41、s motherBeginL2: have an orange; P(S);put an orange into plate;V(SO);goto L2;End;Process sonBeginL3: P(SO); get an orange from plate;V(S);eat an orange;goto L3;End;Process daughtBeginL4: P(SP); get an apple; V(S); eat the apple from plate;goto L4;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)作業(yè)：分奇偶數(shù)作業(yè)：分奇偶數(shù)v W1 R W2v 緩沖區(qū)B輸

42、入設(shè)備輸出設(shè)備輸出設(shè)備2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)BeginB:integer;S,SE,SO:semaphore;S:=1;SE:=0;SO:=0;Cobegin一輸入二輸出進(jìn)程Coend;End;Process Rx:integer;BeginL1: 讀數(shù)；X:=所讀的數(shù)；P(S)；B:=x;if B=奇數(shù) then V(SO); else V(SE);goto L1;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)Process W1y:integer;BeginL2: P(SO)；y:=B;V(S); 輸出y;goto L2;End;Process W2z:integer;Be

43、ginL3: P(SE)；z:=B;V(S); 輸出z;goto L3;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)司機(jī)與票員的同步進(jìn)程司機(jī)與票員的同步進(jìn)程Process Bus-DriverBegin L1 : P(Run); 啟動(dòng)車(chē)輛; 正常行駛; 到站停車(chē)； V(Open); goto L1;End;Process CondctorBegin L2 :售票； P(Open);開(kāi)啟車(chē)門(mén);服務(wù)乘客上車(chē);關(guān)閉車(chē)門(mén)；V(Run);goto L2;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)請(qǐng)用請(qǐng)用PV操作來(lái)實(shí)現(xiàn)司機(jī)與票員的同步操作來(lái)實(shí)現(xiàn)司機(jī)與票員的同步BeginOpen,Run:Semaph

44、ore;Open=0;Run:=1;Cobegin司機(jī)、售票員進(jìn)程Coend;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)司機(jī)與票員的同步進(jìn)程司機(jī)與票員的同步進(jìn)程Process Bus-DriverBegin L1 : P(Run); 啟動(dòng)車(chē)輛; 正常行駛; 到站停車(chē)； V(Open); goto L1;End;Process CondctorBegin L2 :售票； P(Open);開(kāi)啟車(chē)門(mén);服務(wù)乘客上車(chē);關(guān)閉車(chē)門(mén)；V(Run);goto L2;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)6.3 死鎖、高級(jí)進(jìn)程通信v6.3.1 6.3.1 死鎖與產(chǎn)生死鎖的必要條件死鎖與產(chǎn)生死鎖的必要條

45、件v 常用方框代表資源，圓圈代表進(jìn)程，如果常用方框代表資源，圓圈代表進(jìn)程，如果畫(huà)一條由資源到進(jìn)程的有向邊，則表示把該資畫(huà)一條由資源到進(jìn)程的有向邊，則表示把該資源分配給了這個(gè)進(jìn)程。源分配給了這個(gè)進(jìn)程。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 如果畫(huà)一條由進(jìn)程到資源的有向邊，則表如果畫(huà)一條由進(jìn)程到資源的有向邊，則表示該進(jìn)程申請(qǐng)這個(gè)資源，這樣的圖就是所謂的示該進(jìn)程申請(qǐng)這個(gè)資源，這樣的圖就是所謂的“資源分配圖資源分配圖”。 2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) R S T U R A B D C A (a) (b) (c) 圖例： 資源 進(jìn)程 圖圖6-14 6-14 資源分配圖資源分配圖2013 計(jì)

46、算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 例例6-6 6-6 現(xiàn)在有進(jìn)程現(xiàn)在有進(jìn)程A A對(duì)資源的需求序列是對(duì)資源的需求序列是申請(qǐng)申請(qǐng)R R，申請(qǐng)，申請(qǐng)S S，釋放，釋放R R，釋放，釋放S S；進(jìn)程；進(jìn)程B B對(duì)資源對(duì)資源的需求序列是申請(qǐng)的需求序列是申請(qǐng)S S，申請(qǐng)，申請(qǐng)T T，釋放，釋放S S，釋放，釋放T T；進(jìn)程進(jìn)程C C對(duì)資源的需求序列是申請(qǐng)對(duì)資源的需求序列是申請(qǐng)T T，申請(qǐng)，申請(qǐng)R R，釋?zhuān)尫欧臫 T，釋放，釋放R R。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 請(qǐng)對(duì)序列：（請(qǐng)對(duì)序列：（1 1）“A A申請(qǐng)申請(qǐng)R R、B B申請(qǐng)申請(qǐng)S S、C C申申請(qǐng)請(qǐng)T T、A A申請(qǐng)申請(qǐng)S S、B B申請(qǐng)申

47、請(qǐng)T T、C C申請(qǐng)申請(qǐng)R”R”；（；（2 2）“A A申請(qǐng)申請(qǐng)R R、C C申請(qǐng)申請(qǐng)T T、A A申請(qǐng)申請(qǐng)S S、C C申請(qǐng)申請(qǐng)R R、A A釋放釋放R R、A A釋放釋放S”S”分別畫(huà)出對(duì)應(yīng)的資源分配圖，說(shuō)明誰(shuí)分別畫(huà)出對(duì)應(yīng)的資源分配圖，說(shuō)明誰(shuí)能夠運(yùn)行，誰(shuí)無(wú)法運(yùn)行。能夠運(yùn)行，誰(shuí)無(wú)法運(yùn)行。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) R S T R S T R S T R S T R S T R S T A B C A B C A B C A B C A B C A B C 1.A 申請(qǐng) R, 2.B 申請(qǐng) S, 3.C 申請(qǐng) T, 4.A 申請(qǐng) S, 5.B 申請(qǐng) T, 6.C 申請(qǐng) R (a)

48、(b) (c) (d) (e) (f) 圖圖6-15 6-15 第第1 1個(gè)序列的資源分配圖個(gè)序列的資源分配圖2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) R S T R S T R S T R S T R S T S T 3.A 申請(qǐng) S, 1.A 申請(qǐng) R, 2.C 申請(qǐng) T, 4.C 申請(qǐng) R, 5.A 釋放 R, 6.A 釋放 S A B C A B C A B C A B C A B C A B C R (a) (b) (c) (d) (e) (f) 圖圖6-16 6-16 第第2 2個(gè)序列的資源分配圖個(gè)序列的資源分配圖2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 所謂所謂“死鎖死鎖”，即指系

49、統(tǒng)中若存在一組（至，即指系統(tǒng)中若存在一組（至少兩個(gè)或以上）進(jìn)程，它們中的每一個(gè)都占用少兩個(gè)或以上）進(jìn)程，它們中的每一個(gè)都占用了某種資源而又都在等待其中另一個(gè)所占用的了某種資源而又都在等待其中另一個(gè)所占用的資源，這種等待永遠(yuǎn)不會(huì)結(jié)束，這就是資源，這種等待永遠(yuǎn)不會(huì)結(jié)束，這就是“死死鎖鎖”，或說(shuō)這一組進(jìn)程處于，或說(shuō)這一組進(jìn)程處于“死鎖死鎖”狀態(tài)。狀態(tài)。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 一個(gè)系統(tǒng)出現(xiàn)死鎖，會(huì)存在四個(gè)必要條件：一個(gè)系統(tǒng)出現(xiàn)死鎖，會(huì)存在四個(gè)必要條件：v（1 1）互斥條件）互斥條件 v（2 2）部分分配（占用并等待）條件）部分分配（占用并等待）條件 v（3 3）非剝奪條件）非剝奪條件

50、 v（4 4）循環(huán)等待條件）循環(huán)等待條件 2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 死機(jī)不一定死鎖死機(jī)不一定死鎖v 出現(xiàn)環(huán)路也不一定死鎖出現(xiàn)環(huán)路也不一定死鎖 R1R1 R2 R2 P1P4P3P22013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 解決系統(tǒng)中的死鎖問(wèn)題，有下面幾種對(duì)策：解決系統(tǒng)中的死鎖問(wèn)題，有下面幾種對(duì)策：v（1 1）忽略死鎖）忽略死鎖 v（2 2）預(yù)防死鎖）預(yù)防死鎖 v（3 3）避免死鎖）避免死鎖 v（4 4）檢測(cè)死鎖并恢復(fù)（解除）檢測(cè)死鎖并恢復(fù)（解除） 2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v6.3.2 6.3.2 死鎖的預(yù)防死鎖的預(yù)防v 所謂所謂“死鎖的預(yù)防死鎖的預(yù)防”，是指破壞產(chǎn)

51、生死鎖，是指破壞產(chǎn)生死鎖四個(gè)必要條件中的一條或幾條，以使系統(tǒng)不會(huì)四個(gè)必要條件中的一條或幾條，以使系統(tǒng)不會(huì)產(chǎn)生死鎖。產(chǎn)生死鎖。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v（1 1）破壞）破壞“互斥條件互斥條件”。 v（2 2）破壞）破壞“部分分配（占用并等待）條件部分分配（占用并等待）條件”。 v（3 3）破壞）破壞“非剝奪條件非剝奪條件”。 v（4 4）破壞）破壞“循環(huán)等待條件循環(huán)等待條件”。 2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) i i j A A B (a) (b) (c) j B 1輸入機(jī) 2打印機(jī) 3繪圖儀 4磁帶機(jī) 5CD-ROM 圖圖6-17 6-17 用順序編號(hào)破壞用順序編號(hào)破壞“

52、循環(huán)等待條件循環(huán)等待條件”2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)哲學(xué)家吃面哲學(xué)家吃面BeginS1,S2,S3,S4,S5:semaphore;S1:=1; S2:=1; S3:=1; S4:=1; S5:=1;Cobegin進(jìn)程Coend;End;f1f4f5f3f2人1人3人2人4人52013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)Process P1BeginL1:思考; P(S1); 取F1; P(S2); 取F2;吃面； 放下F1和F2;V(S2);V(S1);goto L1;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)Process P2BeginL2:思考; P(S2); 取F2; P(

53、S3); 取F3;吃面； 放下F2和F3;V(S3);V(S2);goto L2;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)Process P3BeginL3:思考; P(S3); 取F3; P(S4); 取F4;吃面； 放下F3和F4;V(S4);V(S3);goto L3;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)Process P4BeginL4:思考; P(S4); 取F4; P(S5); 取F5;吃面； 放下F4和F5;V(S5);V(S4);goto L4;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)Process P5BeginL5:思考; P(S5); 取F5; P(

54、S1); 取F1;吃面； 放下F1和F5;V(S1);V(S5);goto L5;End;2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)Process P5BeginL5:思考; P(S1); 取F1; P(S5); 取F5;吃面； 放下F1和F5;V(S5);V(S1);goto L5;End;按序分配按序分配2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v6.3.3 6.3.3 死鎖的避免死鎖的避免v死鎖的防止是在運(yùn)行前采取的措施，相當(dāng)于小死鎖的防止是在運(yùn)行前采取的措施，相當(dāng)于小孩打防疫針，不會(huì)死鎖。但這些措施會(huì)大大影孩打防疫針，不會(huì)死鎖。但這些措施會(huì)大大影響系統(tǒng)的速度。響系統(tǒng)的速度。v死鎖的避免就是如果

55、能夠找到一個(gè)執(zhí)行次序，死鎖的避免就是如果能夠找到一個(gè)執(zhí)行次序，那么也不會(huì)死鎖。那么也不會(huì)死鎖。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v死鎖的避免是指雖然系統(tǒng)中存在有產(chǎn)生死鎖的死鎖的避免是指雖然系統(tǒng)中存在有產(chǎn)生死鎖的條件，但小心對(duì)待進(jìn)程提出的每一個(gè)資源請(qǐng)求。條件，但小心對(duì)待進(jìn)程提出的每一個(gè)資源請(qǐng)求。 v在接到一個(gè)資源請(qǐng)求時(shí)，不是立即進(jìn)行分配，在接到一個(gè)資源請(qǐng)求時(shí)，不是立即進(jìn)行分配，而是根據(jù)當(dāng)時(shí)資源的使用情況，按照一定的算而是根據(jù)當(dāng)時(shí)資源的使用情況，按照一定的算法去模擬分配，探測(cè)出模擬分配的結(jié)果。法去模擬分配，探測(cè)出模擬分配的結(jié)果。2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)共共12個(gè)資源，剩余個(gè)資源，

56、剩余3個(gè)個(gè)v 只有在探測(cè)結(jié)果表明絕對(duì)不會(huì)出現(xiàn)死鎖時(shí)，才真正接只有在探測(cè)結(jié)果表明絕對(duì)不會(huì)出現(xiàn)死鎖時(shí)，才真正接受這次資源請(qǐng)求。受這次資源請(qǐng)求。進(jìn)程最大需求數(shù)已占資源尚缺資源P1P2P391042527522013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)共共12個(gè)資源，剩余個(gè)資源，剩余2個(gè)個(gè)進(jìn)程最大需求數(shù)已占資源尚缺資源P1P2P391042+1=3526522013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 如果能在有限的時(shí)間內(nèi)，保證所有進(jìn)程得如果能在有限的時(shí)間內(nèi)，保證所有進(jìn)程得到自己需要的全部資源，那么稱(chēng)系統(tǒng)處于到自己需要的全部資源，那么稱(chēng)系統(tǒng)處于“安安全狀態(tài)全狀態(tài)”；否則稱(chēng)系統(tǒng)處于；否則稱(chēng)系統(tǒng)處于“不安全狀態(tài)不安

57、全狀態(tài)”。 安全安全狀態(tài)狀態(tài)不安全不安全狀態(tài)狀態(tài)死鎖2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)銀行家算法的基本思想v當(dāng)一個(gè)用戶對(duì)資金的最大需求量不超過(guò)銀行家當(dāng)一個(gè)用戶對(duì)資金的最大需求量不超過(guò)銀行家現(xiàn)有的資金時(shí)就接納該用戶。現(xiàn)有的資金時(shí)就接納該用戶。v用戶可以分期貸款，但貸款總數(shù)不能超過(guò)最大用戶可以分期貸款，但貸款總數(shù)不能超過(guò)最大需求量。需求量。v當(dāng)銀行家現(xiàn)有資金不夠時(shí)可推遲支付，但時(shí)間當(dāng)銀行家現(xiàn)有資金不夠時(shí)可推遲支付，但時(shí)間有限。有限。v當(dāng)用戶得到全部貸款后，必須按時(shí)歸還所有貸當(dāng)用戶得到全部貸款后，必須按時(shí)歸還所有貸款?？睢?013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè) 圖圖6-18 6-18 銀行家算法

58、的基本思想銀行家算法的基本思想2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)銀行家算法之例銀行家算法之例 假定系統(tǒng)中有五個(gè)進(jìn)程P0, P1, P2, P3, P4和三類(lèi)資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖 3-15 所示。 圖 3-15 T0時(shí)刻的資源分配表 2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)(1) T0時(shí)刻的安全性： 圖 3-16 T0時(shí)刻的安全序列 2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)Max最大A B C10 5 7Allacation已分A B CNeed尚需A B CWork工作區(qū)A B C3 3 2Sort執(zhí)行次序Finish完成p07 5

59、 40 1 07 4 410 5 75Tp13 2 22 0 01 2 21 2 21Tp29 0 23 0 26 0 010 4 7 4Tp32 2 22 1 10 1 17 4 32Tp44 3 30 0 24 3 17 4 53TT0時(shí)刻存在安全序列p1,p3,p4,p2,p0，因此不會(huì)死鎖2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)Max最大A B C10 5 7Allacation已分A B C2 2 1Need尚需A B CWork工作區(qū)A B C1 1 1Sort執(zhí)行次序Finish完成p07 5 40 1 02 3 17 4 45 2 3Fp13 2 22 0 01 2 25 2 2

60、2Tp29 0 23 0 26 0 0Fp32 2 22 1 10 1 13 2 21Tp44 3 30 0 24 3 1FT1時(shí)刻找不到安全序列，在不安全狀態(tài)，系統(tǒng)不分配2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)圖圖6-19 6-19 一個(gè)導(dǎo)致安全狀態(tài)的請(qǐng)求一個(gè)導(dǎo)致安全狀態(tài)的請(qǐng)求2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)圖圖6-20 6-20 一個(gè)導(dǎo)致不安全狀態(tài)的請(qǐng)求一個(gè)導(dǎo)致不安全狀態(tài)的請(qǐng)求2013 計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)v 銀行家算法可以推廣用于處理多種資源。銀行家算法可以推廣用于處理多種資源。此時(shí)，系統(tǒng)要為算法設(shè)置兩張表，一張記錄已此時(shí)，系統(tǒng)要為算法設(shè)置兩張表，一張記錄已分配給各進(jìn)程的資源