操作系統(tǒng)原理課件-(3)[123頁]

1、第3章 進(jìn)程同步與通信 多個并發(fā)執(zhí)行的進(jìn)程在運(yùn)行過程中共享系統(tǒng)中的CPU、內(nèi)存、I/O設(shè)備和文件等資源，系統(tǒng)資源的共享使得一個進(jìn)程的執(zhí)行可能會受到來自其他進(jìn)程直接或間接的制約。 為了協(xié)調(diào)進(jìn)程之間的制約關(guān)系，達(dá)到資源共享和進(jìn)程合作，就需要實(shí)現(xiàn)進(jìn)程的互斥與同步。 協(xié)調(diào)進(jìn)程之間的關(guān)系是通過進(jìn)程之間的通信機(jī)制來實(shí)現(xiàn)的，低級通信主要是通過控制進(jìn)程的執(zhí)行速度來保證進(jìn)程之間的互斥與同步，高級通信則要在進(jìn)程之間傳送大量的數(shù)據(jù)。 此外，進(jìn)程的并發(fā)執(zhí)行還會帶來一個嚴(yán)重問題死鎖。第3章 進(jìn)程同步與通信3.1 進(jìn)程同步的基本概念3.2 進(jìn)程互斥方法3.3 信號量機(jī)制3.4 經(jīng)典互斥與同步問題3.5 經(jīng)典互斥與同步問題

2、的應(yīng)用3.6 管程機(jī)制3.7 進(jìn)程通信3.8 死鎖 3.1.1 并發(fā)進(jìn)程的關(guān)系 經(jīng)過大量的實(shí)踐和分析后發(fā)現(xiàn)，多個并發(fā)執(zhí)行的進(jìn)程存在兩種類型的關(guān)系：無關(guān)和相關(guān)。無關(guān)的進(jìn)程之間在并發(fā)執(zhí)行后，可以保證程序的可再現(xiàn)性，只有相關(guān)的進(jìn)程之間并發(fā)執(zhí)行后，才可能破壞程序的可再現(xiàn)性，對于相關(guān)的并發(fā)進(jìn)程，則存在著以下兩種相互制約的關(guān)系 （1）間接制約關(guān)系。一組（兩個或多個）進(jìn)程共享一種資源，且 該資源一次僅允許一個進(jìn)程使用；當(dāng)一個進(jìn)程正在訪問或使用該 資源時，就制約其他進(jìn)程對該資源的訪問或使用，否則就可能 造成執(zhí)行結(jié)果的錯誤。 像打印機(jī)這種在一段時間內(nèi)只能由一個進(jìn)程使用的資源稱為獨(dú)占資源或互斥資源。多個并發(fā)進(jìn)程對

3、互斥資源的共享導(dǎo)致進(jìn)程之間出現(xiàn)了間接制約關(guān)系。間接制約的存在使得多個并發(fā)進(jìn)程不能同時訪問互斥資源，只有其他進(jìn)程沒有占用該互斥資源時，當(dāng)前運(yùn)行的進(jìn)程才能訪問它。也就是說，一個進(jìn)程通過共享互斥資源來暫時限制（間接制約）其他進(jìn)程的運(yùn)行。 3.1 進(jìn)程同步的基本概念 （2）直接制約關(guān)系。是由任務(wù)協(xié)作引起的，幾個進(jìn)程相互協(xié)作完成 一項(xiàng)任務(wù)，這些進(jìn)程因任務(wù)性質(zhì)的要求必須按事先規(guī)定好的順 序依次執(zhí)行，否則就可能造成錯誤的結(jié)果。 在包裹自動分揀計算機(jī)系統(tǒng)中，分揀筐一次只能存放一個包裹，揀入進(jìn)程選擇包裹放入分揀筐，揀出進(jìn)程則從分揀筐中取出包裹，揀入進(jìn)程和揀出進(jìn)程相互協(xié)作完成包裹的分揀任務(wù)。正常情況下分揀系統(tǒng)將有

4、條不紊地工作，但可能會出現(xiàn)在分揀筐中包裹未取走之前揀入進(jìn)程又將包裹放入分揀筐中；也可能會出現(xiàn)分揀筐中無包裹時，揀出進(jìn)程要從分揀筐中取走包裹。因此，必須事先規(guī)定好揀入進(jìn)程和揀出進(jìn)程的執(zhí)行順序，在揀出進(jìn)程未取走分揀筐中存放的包裹之前，不允許執(zhí)行揀入進(jìn)程；當(dāng)分揀筐為空且揀入進(jìn)程未將包裹放入分揀筐之前，不允許執(zhí)行揀出進(jìn)程。使得揀入進(jìn)程和揀出進(jìn)程彼此直接制約對方的運(yùn)行，相互協(xié)調(diào)的完成既定任務(wù)。3.1 進(jìn)程同步的基本概念 3.1.2 進(jìn)程的互斥與同步 （1）進(jìn)程同步。進(jìn)程間的同步是指某些進(jìn)程之間在邏輯上的相互制約關(guān)系。也就是說，若干進(jìn)程為完成一個共同的任務(wù)而相互合作，由于合作的每一個進(jìn)程都是以各自獨(dú)立的、

5、不可預(yù)知的速度向前推進(jìn)，這就需要相互合作的進(jìn)程在某些協(xié)調(diào)點(diǎn)處來協(xié)調(diào)它們的工作。當(dāng)一個合作進(jìn)程到達(dá)此協(xié)調(diào)點(diǎn)后，在未得到其他合作進(jìn)程發(fā)來的消息之前則阻塞自己，直到其他合作進(jìn)程給出協(xié)調(diào)信號后，才被喚醒再繼續(xù)執(zhí)行。進(jìn)程之間這種相互合作等待對方消息的協(xié)調(diào)關(guān)系就稱為進(jìn)程同步。 （2）進(jìn)程互斥。進(jìn)程互斥是指某一資源同一時間只允許一個進(jìn)程對其進(jìn)行訪問，這種訪問具有唯一性和排它性。進(jìn)程互斥通常是進(jìn)程之間爭奪互斥資源而引起的，在這種情況下，任何時刻都不允許兩個及兩個以上的并發(fā)進(jìn)程同時執(zhí)行那段訪問該互斥資源的程序代碼。3.1 進(jìn)程同步的基本概念 互斥的實(shí)現(xiàn)還會產(chǎn)生兩個額外的控制問題：饑餓和死鎖。 （1）饑餓。一個進(jìn)

6、程所申請的資源總是被優(yōu)先于自己的其他進(jìn)程所占有，而長時間處于不能被調(diào)度執(zhí)行的狀態(tài)（長時間處于就緒或阻塞狀態(tài)），將這種現(xiàn)象稱為“饑餓”。 例如，系統(tǒng)中有三個周期性執(zhí)行的進(jìn)程：P1、P2和P3，其中P1正在占用CPU執(zhí)行，而P2和P3處于就緒狀態(tài)。如果三個進(jìn)程對CPU競爭的結(jié)果是P1釋放CPU后，將其分配給P2運(yùn)行，而P2釋放CPU后又將其分配給P1再次運(yùn)行，如此循環(huán)往復(fù)，這就使得處于就緒狀態(tài)的進(jìn)程P3長時間不能被調(diào)度執(zhí)行，這就是饑餓狀態(tài)。3.1 進(jìn)程同步的基本概念 （2）死鎖。一個進(jìn)程集合中已經(jīng)占有部分資源的兩個或兩個以上進(jìn)程，還需要獲得已被其他進(jìn)程占有的資源才能夠繼續(xù)執(zhí)行，有可能出現(xiàn)某些進(jìn)程相

7、互之間都在等待對方占有的資源而無法運(yùn)行的局面，即在進(jìn)程集合中的這些進(jìn)程處于永遠(yuǎn)的阻塞狀態(tài)，這就是“死鎖”。 例如，有兩個進(jìn)程P1和P2在執(zhí)行過程中都需要使用互斥資源R1和R2，且資源R1和R2均只有一個。假設(shè)在某時刻P1占用了R1又要申請使用R2，而P2占用了R2又要申請使用R1，這時P1因申請已被P2占用的R2而阻塞，P2則因?yàn)樯暾堃驯籔1占用的R1而阻塞，從而出現(xiàn)P1和P2因相互等待對方資源而始終無法運(yùn)行的死鎖狀態(tài)。3.1 進(jìn)程同步的基本概念 進(jìn)程同步與進(jìn)程互斥的區(qū)別 進(jìn)程互斥是由互斥資源引起的，即各進(jìn)程之間共享互斥資源的使用權(quán)。這種競爭沒有確定的必然聯(lián)系，哪個進(jìn)程競爭到互斥資源的使用權(quán)，

8、則該資源就歸哪個進(jìn)程使用，直到它不再需要該資源時才放棄該資源的使用權(quán)，而那些未申請到互斥資源的進(jìn)程則不能執(zhí)行。也即，進(jìn)程互斥是通過互斥資源來制約各進(jìn)程執(zhí)行的，這種互斥無法事先指定進(jìn)程對資源的訪問順序，故訪問是無序的。 進(jìn)程同步則是指相互協(xié)作的并發(fā)進(jìn)程之間存在著必然的聯(lián)系，若當(dāng)前運(yùn)行進(jìn)程執(zhí)行過程中需要進(jìn)行同步時，在沒有得到協(xié)同工作的其他合作進(jìn)程發(fā)來的同步消息之前，當(dāng)前運(yùn)行進(jìn)程則不能繼續(xù)向前推進(jìn)（運(yùn)行）。在進(jìn)程同步中，雖然互斥資源仍然制約著進(jìn)程的執(zhí)行，但協(xié)調(diào)各進(jìn)程向前推進(jìn)的只能是進(jìn)程同步，即使用進(jìn)程同步來協(xié)調(diào)和制約各合作進(jìn)程的執(zhí)行，通過對資源的有序訪問去完成一個共同的任務(wù)。3.1 進(jìn)程同步的基本概

9、念例：下面活動中，每個活動分屬于同步與互斥關(guān)系的哪一種，并說明其理由。（1）若干同學(xué)去圖書館借書；（2）兩隊(duì)舉行籃球比賽；（3）流水線生產(chǎn)的各道工序；（4）商品生產(chǎn)和社會消費(fèi)。 同步與互斥的比較3.1.3 臨界資源與臨界區(qū)臨界資源某段時間內(nèi)只能允許一個進(jìn)程使用的資源（即互斥資源）。臨界區(qū)進(jìn)程中訪問臨界資源的代碼段。例：進(jìn)程P1和進(jìn)程P2共享一個公用變量S，假設(shè)進(jìn)程P1需要對變量S進(jìn)行加1操作，而進(jìn)程P2需要對變量S進(jìn)行減1操作。假設(shè)s的當(dāng)前值是1，（1）先執(zhí)行語句 、，再執(zhí)行語句 、，則s；（2）先執(zhí)行語句 、，再執(zhí)行語句 、，則s；（3）執(zhí)行語句的次序?yàn)?、，則s0；3.1 進(jìn)程同步的基本概

10、念 進(jìn)程P1： register1=s; register1=register1+1; s=register1; 進(jìn)程P2： register2=s; register2=register2-1; s=register2;解決辦法：把公用變量s作為臨界資源處理，進(jìn)程P1和進(jìn)程地P2互斥地訪問公用變量s。同步機(jī)制應(yīng)遵循的準(zhǔn)則（1）空閑讓進(jìn)。無進(jìn)程處于臨界區(qū)時意味著臨界資源處于空閑狀態(tài)，這時若有進(jìn)程要求進(jìn)入臨界區(qū)應(yīng)立即允許進(jìn)入。（2）忙則等待。當(dāng)已有進(jìn)程進(jìn)入其臨界區(qū)時則意味著某臨界資源正在使用，所有其他欲訪問該臨界資源的進(jìn)程試圖進(jìn)入各自臨界區(qū)時必須等待，以保證各進(jìn)程互斥地進(jìn)入訪問相同臨界資源的臨界

11、區(qū)。（3）有限等待。若干進(jìn)程要求進(jìn)入訪問同一臨界資源的臨界區(qū)時，應(yīng)在有限時間內(nèi)使一進(jìn)程進(jìn)入臨界區(qū)，即不應(yīng)出現(xiàn)各進(jìn)程相互等待而都無法進(jìn)入臨界區(qū)的情況。（4）讓權(quán)等待。當(dāng)進(jìn)程不能進(jìn)入其臨界區(qū)時應(yīng)立即釋放所占有的CPU，以免陷入“忙等”（進(jìn)程在占有CPU的同時又一直等待），保證其他可執(zhí)行的進(jìn)程獲得CPU運(yùn)行。3.2.1 實(shí)現(xiàn)進(jìn)程互斥的硬件方法 通過計算機(jī)提供的一些機(jī)器指令來實(shí)現(xiàn)進(jìn)程的互斥。 機(jī)器指令是指在一個指令周期內(nèi)執(zhí)行完成的指令，而專用機(jī)器指令的執(zhí)行則不會被中斷。專用機(jī)器指令有3個： 1.開關(guān)中斷指令： 進(jìn)程在進(jìn)入臨界區(qū)之前先執(zhí)行“關(guān)中斷”指令來屏蔽掉所有中斷；進(jìn)程完成臨界區(qū)的任務(wù)后，再執(zhí)行“開

12、中斷”指令將中斷打開。程序結(jié)構(gòu)如下： cobegin /偽代碼cobegin和coend表示其間的進(jìn)程可以并發(fā)執(zhí)行 process Pi() / i=1, 2, 3, , n /與臨界資源無關(guān)的代碼 lock out interrupts; /關(guān)中斷 臨界區(qū); unlock interrupts; /開中斷 /與臨界資源無關(guān)的剩余代碼 coend3.2 進(jìn)程互斥方法2. 測試與設(shè)置指令TS（Test and Set）： 要為每個臨界資源設(shè)置一個整型變量s，可以將它看成一把鎖。若s的值為0（開鎖狀態(tài)），則表示沒有進(jìn)程訪問該鎖對應(yīng)的臨界資源。若s的值為1（關(guān)鎖狀態(tài)），則表示該鎖對應(yīng)的臨界資源已被某

13、個進(jìn)程占用。3.2 進(jìn)程互斥方法 TS指令的函數(shù)描述： int TS(int s) if(s) return 1; else s=1; return 0; 應(yīng)用： int s=0; cobegin process Pi() /i=1,2,3,n /與臨界資源無關(guān)的代碼 while(TS(s); /進(jìn)入?yún)^(qū) 臨界區(qū)； s=0; /退出區(qū) /與臨界資源無關(guān)的剩余代碼 coend3. 交換指令（Swap）：要為每個臨界資源設(shè)置一個整型的全局變量s；若s的值為0則表示沒有進(jìn)程在臨界區(qū)，若s的值為1則表示有進(jìn)程在臨界區(qū)（即訪問臨界資源）。此外，還要為每個進(jìn)程設(shè)置一個整型局部變量key。只有當(dāng)s的值為0并且

14、key的值為1時，本進(jìn)程才能進(jìn)入臨界區(qū)。進(jìn)入臨界區(qū)后，s的值為1且key的值為0；退出臨界區(qū)時，應(yīng)將s的值置為0。3.2 進(jìn)程互斥方法 交換指令的函數(shù)描述： void Swap(int *a,int *b) int temp=*a; *a=*b; *b=temp; int s=0; /s為全局變量 cobegin process Pi() /i=1,2,3,n /與臨界資源無關(guān)的代碼 int key=1; /key為局部變量 do /進(jìn)入?yún)^(qū) Swap(&s,&key); while(key); 臨界區(qū)； s=0; /退出區(qū) /與臨界資源無關(guān)的剩余代碼 coend3.2.2實(shí)現(xiàn)進(jìn)程互斥的軟件方法

15、1. 兩標(biāo)志進(jìn)程互斥算法基本思想：為希望訪問臨界資源的兩個并發(fā)進(jìn)程設(shè)置的兩個標(biāo)志T1和T2來表示某個進(jìn)程是否在臨界區(qū)；若Ti（i=1, 2）等于0則表示進(jìn)程Pi（i=1, 2）沒有在臨界區(qū)，若Ti（i=1, 2）等于1則表示進(jìn)程Pi（i=1, 2）在臨界區(qū)。每個進(jìn)程在進(jìn)入臨界區(qū)之前，先判斷臨界區(qū)是否已被另一進(jìn)程訪問，若是則本進(jìn)程等待，否則本進(jìn)程進(jìn)入臨界區(qū)。3.2 進(jìn)程互斥方法 1.兩標(biāo)志進(jìn)程互斥算法算法描述如下： 進(jìn)程P1：while(T2); /檢查P2是否在臨界區(qū)T1=1; /設(shè)置P1在臨界區(qū)標(biāo)志臨界區(qū);T1=0; /設(shè)置P1不在臨界區(qū)標(biāo)志 進(jìn)程P2：while(T1); /檢查P1是否在

16、臨界區(qū)T2=1; /設(shè)置P2在臨界區(qū)標(biāo)志臨界區(qū);T2=0; /設(shè)置P2不在臨界區(qū)標(biāo)志改進(jìn)算法描述如下： 進(jìn)程P1：T1=1; /設(shè)置P1在臨界區(qū)標(biāo)志while(T2); /檢查P2是否在臨界區(qū)臨界區(qū);T1=0; /設(shè)置P1不在臨界區(qū)標(biāo)志 進(jìn)程P2：T2=1; /設(shè)置P2在臨界區(qū)標(biāo)志while(T1); /檢查P1是否在臨界區(qū)臨界區(qū);T2=0; /設(shè)置P2不在臨界區(qū)標(biāo)志2. 三標(biāo)志進(jìn)程互斥算法基本思想：設(shè)置3個標(biāo)志T1、T2和T，其中T1和T2的作用與兩標(biāo)志進(jìn)程互斥算法相同，而T是一個公共標(biāo)志，用來表示允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)號；若進(jìn)程希望進(jìn)入臨界區(qū)，則先設(shè)置自己的標(biāo)志Ti（i=1, 2），然后再

17、檢測公共標(biāo)志T，若T等于i（i=1, 2），則表示允許進(jìn)程Pi（i=1, 2）進(jìn)入臨界區(qū)。3.2 進(jìn)程互斥方法 進(jìn)程P1：T1=1; /設(shè)置P1在臨界區(qū)標(biāo)志T=2; /允許P2進(jìn)入臨界區(qū)while(T2=1&T=2);臨界區(qū);T1=0; /設(shè)置P1不在臨界區(qū)標(biāo)志 進(jìn)程P2：T2=1; /設(shè)置P2在臨界區(qū)標(biāo)志T=1; /允許P1進(jìn)入臨界區(qū)while(T1=1&T=1);臨界區(qū);T2=0; /設(shè)置P2不在臨界區(qū)標(biāo)志3.3.1 信號量 在操作系統(tǒng)中，信號量代表了一類物理資源，它是相應(yīng)物理資源的抽象。具體實(shí)現(xiàn)時，信號量被定義成具有某種類型的變量。 信號量可分為整型信號量和結(jié)構(gòu)體信號量。 1.整型信號量

18、 若信號量為S，則P操作原語和V操作原語可以分別描述如下： int S; P(S): while(S=0); S=S-1; V(S): S=S+1;3.3 信號量機(jī)制2. 結(jié)構(gòu)體型信號量 結(jié)構(gòu)體型信號量中的一個分量成員是一個整型變量，它代表當(dāng)前相應(yīng)資源的可用數(shù)量，或用于進(jìn)程同步與互斥控制的信號量；另一個分量成員是一個隊(duì)列指針，指向因等待同類資源的進(jìn)程阻塞隊(duì)列，或同步與互斥控制中該信號量的進(jìn)程阻塞隊(duì)列。結(jié)構(gòu)體型信號量描述如下： typedef struct int value; struct PCB *L; /struct PCB為PCB對應(yīng)的結(jié)構(gòu)體類型 /L為指向進(jìn)程阻塞隊(duì)列的指針 Semap

19、hore; Semaphore S;3.3 信號量機(jī)制 當(dāng)結(jié)構(gòu)體型信號量作為資源信號量時，指針S.L指向因等待同類資源的進(jìn)程阻塞隊(duì)列（由各進(jìn)程的PCB組成）的隊(duì)首。S.value的初值是一個非負(fù)整數(shù)，它代表著系統(tǒng)中某類資源的數(shù)量。隨著該類資源不斷地被分配，S.value的值也隨之發(fā)生變化，會出現(xiàn)以下三種情況。 （1）當(dāng)S.value0時，S.value表示該類資源當(dāng)前的可用數(shù)量。 （2）當(dāng)S.value = 0時，S.value表示該類資源為空。 （3）當(dāng)S.value0時，S.value的絕對值表示因等待該類資源而阻塞的進(jìn)程個數(shù)。 當(dāng)結(jié)構(gòu)體型信號量作為控制信號量時（包括對臨界區(qū)和共享變量的互

20、斥控制），S.value的值用來控制是否允許進(jìn)程繼續(xù)執(zhí)行。當(dāng)S.value0時，當(dāng)前運(yùn)行進(jìn)程繼續(xù)執(zhí)行；當(dāng)S.value0時，當(dāng)前運(yùn)行進(jìn)程被阻塞而放棄執(zhí)行，此時S.value的絕對值表示被阻塞于S信號量的進(jìn)程個數(shù)。指針S.L用來指向進(jìn)程在S信號量的進(jìn)程阻塞隊(duì)列。3.3 信號量機(jī)制 P(S)原語void P(Semaphore S) lock out interrupts; /關(guān)中斷 S.value=S.value-1; if(S.value0) /S.value0時阻塞當(dāng)前運(yùn)行進(jìn)程i的運(yùn)行 i.status=block; /置運(yùn)行進(jìn)程i的狀態(tài)為“阻塞” Insert(BlockQueue,i);

21、 /將進(jìn)程i插入到進(jìn)程阻塞隊(duì)列S.L中 unlock interrupts; /開中斷 Scheduler(); /執(zhí)行進(jìn)程調(diào)度程序調(diào)度另一就緒進(jìn)程運(yùn)行 else if(S是資源信號量) GetResouce(i_PCB,一個S資源); /將資源S分配給進(jìn)程i unlock interrupts; /開中斷 P(S)操作的物理含義 （1）在申請和釋放諸如打印機(jī)這類互斥資源的操作中，執(zhí)行一次P(S)操作相當(dāng)于申請一個資源S。若S.value值大于0，則意味著系統(tǒng)中有資源S。此時S.value減1表示將一個資源S分配給當(dāng)前運(yùn)行進(jìn)程，即資源S的可用數(shù)量減少了一個，而當(dāng)前運(yùn)行進(jìn)程請求資源S得到滿足后則

22、繼續(xù)執(zhí)行。若S.value減1后其值小于0時，表示已經(jīng)沒有資源S可用，立即將當(dāng)前運(yùn)行進(jìn)程阻塞起來（放棄CPU）并插入到指針S.L所指的進(jìn)程阻塞隊(duì)列中，然后由進(jìn)程調(diào)度程序調(diào)度另一就緒進(jìn)程運(yùn)行，此時S.value減1后的絕對值表示等待資源S的阻塞進(jìn)程又多了一個。 （2） 在進(jìn)程同步與互斥操作中，S代表同步與互斥的信號量。若S.value減1后其值大于或等于0，則表示當(dāng)前運(yùn)行進(jìn)程不需同步或互斥而繼續(xù)執(zhí)行；若S.value減1后其值小于0，則當(dāng)前運(yùn)行進(jìn)程必需同步或互斥，即被阻塞于信號量S而放棄執(zhí)行，然后由進(jìn)程調(diào)度程序調(diào)度另一就緒進(jìn)程運(yùn)行。顯然，結(jié)構(gòu)體型信號量機(jī)制采用了“讓權(quán)等待”策略。 V(S) 原語

23、 void V(Semaphore S) lock out interrupts; /關(guān)中斷 S.value=S.value+1; if(S是資源信號量) free(資源S) /將資源S從當(dāng)前運(yùn)行進(jìn)程回收到系統(tǒng) if(S.value=0) /進(jìn)程阻塞隊(duì)列中有阻塞進(jìn)程 Remove(i); /從S.L所指的進(jìn)程阻塞隊(duì)列中移出隊(duì)首進(jìn)程i if(S是資源信號量) GetResouce(i_PCB,一個S資源); /將資源S分配給進(jìn)程i i.status=ready; /置進(jìn)程i的狀態(tài)為“就緒” Insert(ReadyQueue,i); /將進(jìn)程i插入到進(jìn)程就緒隊(duì)列中 unlock interrup

24、ts; /開中斷 V(S)操作的物理含義 （1）在申請和釋互斥資源的操作中，執(zhí)行一次V(S)操作相當(dāng)于釋放一個資源S，于是執(zhí)行S.value加1的操作（系統(tǒng)回收一個資源S）。若S.value加1后其值仍然小于或等于0，則表明仍然有處于阻塞狀態(tài)的進(jìn)程在等待資源S，于是將S.L所指進(jìn)程阻塞隊(duì)列上的第一個阻塞進(jìn)程喚醒并將剛回收的資源S分配給它，然后將其移入到進(jìn)程就緒隊(duì)列中。 （2）在進(jìn)程同步與互斥操作中，若S.value加1后其值仍然小于或等于0，則表明有處于阻塞狀態(tài)的進(jìn)程在等待信號量S的喚醒，此時將S.L所指進(jìn)程阻塞隊(duì)列上的第一個阻塞進(jìn)程喚醒，并移入到進(jìn)程就緒隊(duì)列中。 注意：S作為同步與互斥信號量

25、時不涉及資源的分配與回收。 3.3.2 使用信號量實(shí)現(xiàn)進(jìn)程互斥方法：為要進(jìn)入的臨界區(qū)設(shè)置一個互斥信號量mutex，將mutex.value初值設(shè)置為1，然后將各進(jìn)程的臨界區(qū)（訪問臨界資源的那段代碼）置于P(mutex) 和V(mutex) 之間。程序模型如下：Semaphore mutex;mutex.value=1;cobegin process Pi() / i=1, 2, 3, , n /與臨界資源無關(guān)的代碼 P(mutex); 臨界區(qū)； V(mutex); /與臨界資源無關(guān)的剩余代碼 coend3.3 信號量機(jī)制 互斥信號量 當(dāng)兩個或多個進(jìn)程使用初值為1的信號量（稱為互斥信號量）時，可

26、以保證任何時刻只能有一個進(jìn)程進(jìn)入臨界區(qū)。如果每個進(jìn)程在進(jìn)入臨界區(qū)前都對信號量執(zhí)行一個P操作，而在退出臨界區(qū)時對該信號量執(zhí)行一個V操作，就能實(shí)現(xiàn)多個進(jìn)程互斥的進(jìn)入各自的臨界區(qū)（訪問臨界資源的那段程序代碼）。3.3 信號量機(jī)制例如，有兩個進(jìn)程P1和P2要訪問某一臨界資源，它們各自的臨界區(qū)為L1和L2?？稍O(shè)S為這兩個進(jìn)程的互斥信號量，其S.value的初值為1。這時，只需把臨界區(qū)置于P(S) 和V(S) 之間即可實(shí)現(xiàn)兩進(jìn)程的互斥。3.3 信號量機(jī)制進(jìn)程P1： P(S); L1; V(S); 進(jìn)程P2： P(S); L2; V(S); 3.3.3 使用信號量實(shí)現(xiàn)進(jìn)程同步 若干進(jìn)程為完成一個共同的任務(wù)而

27、相互合作，這就需要相互合作的進(jìn)程在某些協(xié)調(diào)點(diǎn)處（即需要同步的地方）插入對信號量的P操作或操作，以便協(xié)調(diào)它們的工作（實(shí)現(xiàn)進(jìn)程間的同步）。 例：在公共汽車上，司機(jī)和售票員各行其職獨(dú)立工作。司機(jī)只有等售票員關(guān)好車門后才能啟動汽車，售票員只有等司機(jī)停好車后才能開車門，即兩者必須密切配合、協(xié)調(diào)一致。 進(jìn)程的同步是采用信號應(yīng)答方式來進(jìn)行的。 3.3 信號量機(jī)制 使用信號量實(shí)現(xiàn)進(jìn)程同步示例程序模型如下：Semaphore Start,Open;Start.value=0,Open.value=0;cobegin process 司機(jī)() while(1) P(Start); 啟動汽車; 正常行駛; 到站停車

28、; V(Open); process 售票員() while(1) 關(guān)車門; V(Start); 售票; P(Open); 開車門; coend使用信號量實(shí)現(xiàn)進(jìn)程同步示例例：進(jìn)程P1P4存在如右圖所示的運(yùn)行次序： 并發(fā)執(zhí)行的程序描述如下：Semaphore a,b,c,d;a.value=0,b.value=0,c.value=0,d.value=0;cobegin process P1() P1;V(a);V(b); process P2() P(a);P2;V(c); process P3() P(b); P3;V(d); process P4() P(c);P(d);P4; coend

29、有向邊上的字母代表信號量，有向邊的起始端進(jìn)程在執(zhí)行結(jié)束時，要對該信號量實(shí)施V操作，而有向邊的結(jié)束端進(jìn)程在執(zhí)行之前則要對該信號量實(shí)施P操作，這樣就確保了多個合作進(jìn)程按事先約定的順序執(zhí)行。 3.4.1 生產(chǎn)者-消費(fèi)者問題 1965年，E.W.Dijkstra在他著名的論文協(xié)同順序進(jìn)程中用生產(chǎn)者-消費(fèi)者問題對并發(fā)程序設(shè)計中進(jìn)程同步的最基本問題，即對多進(jìn)程提供（或釋放）以及使用計算機(jī)系統(tǒng)中軟硬件資源（如數(shù)據(jù)、I/O設(shè)備等）進(jìn)行了抽象的描述，并使用信號燈（信號量）的概念解決了這一問題。 在生產(chǎn)者-消費(fèi)者問題中，所謂消費(fèi)者是指使用某一軟硬件資源的進(jìn)程，而生產(chǎn)者是指提供（或釋放）某一軟硬件資源的進(jìn)程。 現(xiàn)在

30、，生產(chǎn)者-消費(fèi)者問題已經(jīng)抽象為一組生產(chǎn)者向一組消費(fèi)者提供產(chǎn)品，生產(chǎn)者與消費(fèi)者共享一個有界緩沖池，生產(chǎn)者向其中投放產(chǎn)品，消費(fèi)者從中取出產(chǎn)品消費(fèi)。生產(chǎn)者-消費(fèi)者問題是一個著名的進(jìn)程同步問題，是許多相互合作進(jìn)程的一種抽象。如在輸入時，輸入進(jìn)程是生產(chǎn)者，計算進(jìn)程是消費(fèi)者；在輸出時，計算進(jìn)程是生產(chǎn)者，打印進(jìn)程是消費(fèi)者。3.4 經(jīng)典互斥與同步問題例：把一個長度為n的緩沖池（n0，n為緩沖池中緩沖區(qū)的個數(shù)）與一群生產(chǎn)者進(jìn)程P1、P2、Pm和一群消費(fèi)者進(jìn)程C1、C2、Ck聯(lián)系起來，如圖3-6所示。只要緩沖池未滿，生產(chǎn)者就可以把產(chǎn)品送入空緩沖區(qū)；只要緩沖池未空，消費(fèi)者就可以從滿緩沖區(qū)中取出產(chǎn)品進(jìn)行消費(fèi)。生產(chǎn)者和

31、消費(fèi)者的同步關(guān)系將禁止生產(chǎn)者向一滿緩沖區(qū)中投放產(chǎn)品，也禁止消費(fèi)者從一空緩沖區(qū)中取出產(chǎn)品。 用一個具有n個數(shù)組元素的一維數(shù)組B來構(gòu)成循環(huán)隊(duì)列，并用該數(shù)組模擬緩沖池，即每個數(shù)組元素代表一個緩沖區(qū)。 解決方法：首先考慮生產(chǎn)者，只有空緩沖區(qū)存在時才能將產(chǎn)品放入空緩沖區(qū)，即需設(shè)置空緩沖區(qū)個數(shù)的信號量empty，且empty.value的初值為n（初始時有n個空緩沖區(qū)）；其次考慮消費(fèi)者，只有存在放入產(chǎn)品的滿緩沖區(qū)時才能從滿緩沖區(qū)中取出產(chǎn)品，即需設(shè)置放入產(chǎn)品的滿緩沖區(qū)個數(shù)信號量full，且full.value的初值為0（初始時沒有放入產(chǎn)品的滿緩沖區(qū)）。 生產(chǎn)者-消費(fèi)者問題實(shí)現(xiàn)程序item Bn; /數(shù)組B用

32、來模擬n個緩沖區(qū)Semaphore mutex,empty,full;mutex.value=1,empty.value=n,full.value=0;int in=0; /in指針指向一個空緩沖區(qū)int out=0; /out指針指向一個滿緩沖區(qū)item product; /product代表一個產(chǎn)品cobegin process Producer_i() /i=1,2,3,m while(1) product=produce();/生產(chǎn)一個產(chǎn)品 P(empty); /請求空緩沖區(qū) P(mutex); /請求獨(dú)占緩沖池 Bin=product; /產(chǎn)品放到空緩沖區(qū) in=(in+1)%n;

33、/in移至下一個空緩沖區(qū) V(mutex); /釋放緩沖池的使用權(quán) V(full); /滿緩沖區(qū)個數(shù)增一 /若有阻塞的消費(fèi)者進(jìn)程則喚醒之 process Consumer_j() /j=1,2,3,k while(1) P(full); /請求消費(fèi)滿緩沖區(qū)中的產(chǎn)品 P(mutex); /請求獨(dú)占緩沖池使用權(quán) product=Bout; /從滿緩沖區(qū)中取出產(chǎn)品 out=(out+1)%n; /out移至下一個滿緩沖區(qū) V(mutex); /釋放對緩沖池的使用權(quán) V(empty); /空緩沖區(qū)個數(shù)增一 /若有阻塞的生產(chǎn)者進(jìn)程則喚醒之 consume(); /進(jìn)行產(chǎn)品消費(fèi) coend 3.4.2 哲

34、學(xué)家進(jìn)餐問題問題描述：5個哲學(xué)家同坐在一張圓桌旁，每個人的面前擺放著一碗面條，碗的兩旁各擺放著一只筷子。假設(shè)哲學(xué)家的生活除了吃飯就是思考問題（這是一種抽象，即對該問題而言其他活動都無關(guān)緊要），而吃飯的時候需要左手拿一只筷子，右手拿一只筷子，然后開始進(jìn)餐（如下圖）。吃完后又將筷子放回原處，繼續(xù)思考問題。3.4 經(jīng)典互斥與同步問題一個哲學(xué)家的活動進(jìn)程可表示為：（1）思考問題；（2）餓了停止思考，左手拿一只筷子（如果左側(cè)哲學(xué)家已持有它，則需要等待）；（3）右手拿一只筷子（如果右側(cè)哲學(xué)家已持有它，則需要等待）；（4）進(jìn)餐；（5）放右手筷子；（6）放左手筷子；（7）重新回到思考問題狀態(tài)（1）。 ？如何協(xié)

35、調(diào)5個哲學(xué)家的活動進(jìn)程，使得每一個哲學(xué)家最終都可以進(jìn)餐?？紤]下面的兩種情況：（1）按哲學(xué)家的活動進(jìn)程，當(dāng)所有的哲學(xué)家都同時拿起左手筷子時，則所有的哲學(xué)家都將拿不到右手的筷子，并處于等待狀態(tài)，那么哲學(xué)家都將無法進(jìn)餐，最終餓死。（2）將哲學(xué)家的活動進(jìn)程修改一下，變?yōu)楫?dāng)右手的筷子拿不到時，就放下左手的筷子，這種情況不一定沒有問題，因?yàn)榭赡茉谝粋€瞬間，所有的哲學(xué)家都同時拿起左手的筷子，則自然拿不到右手的筷子，于是都同時放下左手的筷子；等一會，又同時拿起左手的筷子，如此這樣永遠(yuǎn)重復(fù)下去，則所有的哲學(xué)家都將無法進(jìn)餐。 以上兩個方面的問題，反映的是程序并發(fā)執(zhí)行時進(jìn)程同步的兩個問題，一個是死鎖，另一個是饑餓。

36、 在哲學(xué)家就餐問題中，筷子應(yīng)作為臨界資源使用，因此需為每支筷子設(shè)置一個互斥信號量，其初值均為1。每個哲學(xué)家在進(jìn)餐之前，必須借助互斥信號量的P原語進(jìn)行以下兩個操作：取左邊的筷子和取右邊的筷子。進(jìn)餐完畢后，必須借助互斥信號量的V原語放下手上的兩支筷子。 哲學(xué)家進(jìn)餐問題解決方法Semaphore chopstick5;for(int i=0;i5;i+)chopsticki.value=1;cobegin process Philosopher_i() / i=0, 1, 2, 3, 4 while(1) think(); /思考 P(chopsticki); /拿起左手的筷子 P(chopstic

37、k(i+1)%5); /拿起右手的筷子 eat(); /進(jìn)餐 V(chopsticki); /放回左手的筷子 V(chopstick(i+1)%5); /放回右手的筷子 coend可能引起死鎖！ 哲學(xué)家進(jìn)餐問題解決方法（1）最多允許4位哲學(xué)家同時拿起左手（或右手）的筷子。程序如下：Semaphore mutex,chopstick5;mutex.value=4;for(int i=0;i5;i+)chopsticki.value=1;cobegin process Philosopher_i( ) / i=0, 1, 2, 3, 4 while(1) think(); /思考 P(mutex)

38、; /最多允許4個哲學(xué)家申請筷子 P(chopsticki); /拿起左手的筷子 P(chopstick(i+1)%5); /拿起右手的筷子 V(mutex); /已拿到兩個筷子，解除申請 eat(); /進(jìn)餐 V(chopsticki); /放回左手的筷子 V(chopstick(i+1)%5); /放回右手的筷子 coend可預(yù)防死鎖出現(xiàn) 哲學(xué)家進(jìn)餐問題解決方法（2）僅當(dāng)哲學(xué)家的左、右兩支筷子均可用時，才允許他同時拿起左、右手的兩支筷子，否則一支筷子也不拿。程序如下：Semaphore chopstick5;for(int i=0;i5;i+)chopsticki.value=1;cobe

39、gin process Philosopher_i() / i=0, 1, 2, 3, 4 while(1) think(); /思考 SP(chopsticki,chopstick(i+1)%5); /同時拿起左、右手的兩只筷子 eat(); /進(jìn)餐 SV(chopsticki,chopstick(i+1)%5); /同時放回左、右手的兩只筷子 coend可預(yù)防死鎖出現(xiàn) 哲學(xué)家進(jìn)餐問題解決方法（3）奇數(shù)號哲學(xué)家先取左手的筷子，然后再取右手的筷子；而偶數(shù)哲學(xué)家先取右手的筷子，然后再取左手的筷子。程序如下： Semaphore chopstick5; for(int i=0;in+1) /顧客已

40、無椅子可坐 rc-; /該顧客需離開理發(fā)廳 V(mutex); else /顧客不是第一個到達(dá)但有空椅子可坐 坐在空椅子上; V(mutex); P(wait); /阻塞自己等待理發(fā)師喚醒 離開理發(fā)廳; process Barber() P(wakeup); /無理發(fā)的顧客則理發(fā)師睡眠 while(1) P(mutex); if(rc!=0) /有等待理發(fā)的顧客 V(wait); /喚醒wait隊(duì)列上第一個顧客 讓被喚醒的顧客坐在理發(fā)椅上理發(fā); rc-; /等待理發(fā)顧客人數(shù)減1 V(mutex); else V(mutex); P(wakeup); /無理發(fā)顧客則理發(fā)師睡眠 coend3.5.

41、1 緩沖區(qū)數(shù)據(jù)傳送問題問題描述：設(shè)有進(jìn)程A、B和C，分別調(diào)用函數(shù)get、copy和put對緩沖區(qū)S和T進(jìn)行操作。其中，get負(fù)責(zé)把數(shù)據(jù)塊輸入到緩沖區(qū)S中，copy負(fù)責(zé)從緩沖區(qū)S中取出數(shù)據(jù)塊并復(fù)制到緩沖區(qū)T中，put負(fù)責(zé)從緩沖區(qū)T中取出數(shù)據(jù)輸出打印，試描述進(jìn)程A、B和C的實(shí)現(xiàn)算法。3.5 經(jīng)典互斥與同步問題的應(yīng)用 三進(jìn)程之間制約關(guān)系的前趨圖見右圖：緩沖區(qū)數(shù)據(jù)傳送示意 緩沖區(qū)數(shù)據(jù)傳送問題實(shí)現(xiàn)程序Semaphore empty1,empty2,full1,full2;empty1.value=1,empty2.value=1;full1.value=0,full2.value=0;cobegin p

42、rocess A() while(1) P(empty1); /測試緩沖區(qū)S是否非空 /非空則阻塞進(jìn)程A get(); /將數(shù)據(jù)塊輸入到緩沖區(qū)S V(full1); /通知進(jìn)程B可取出S中數(shù)據(jù)塊 /若進(jìn)程B阻塞則喚醒它 process B() while(1) P(full1); /S是否有數(shù)據(jù)，無則阻塞進(jìn)程B P(empty2); /測試緩沖區(qū)T是否非空 /非空則阻塞進(jìn)程B copy(); /從S中取出數(shù)據(jù)復(fù)制到緩沖區(qū)T V(empty1); /通知進(jìn)程A緩沖區(qū)S為空 /若進(jìn)程A阻塞則喚醒它 V(full2); /通知C可取出緩沖區(qū)T中數(shù)據(jù)打印 /若進(jìn)程C阻塞則喚醒它 process C()

43、 while(1) P(full2); /T是否有數(shù)據(jù)，無則阻塞進(jìn)程C put(); /取出緩沖區(qū)T中數(shù)據(jù)打印 V(empty2); /通知進(jìn)程B緩沖區(qū)T為空 /如進(jìn)程B阻塞則喚醒它 coend3.5.2 吃水果問題問題描述：桌上有一個盤子，可以放入一個水果。父親總是放蘋果到盤子中，而母親則總是放香蕉到盤子中，一個兒子專等吃盤中的香蕉，而一個女兒專等吃盤中的蘋果。3.5 經(jīng)典互斥與同步問題的應(yīng)用父親、母親、女兒和兒子4個進(jìn)程的同步示意如下： 吃水果問題實(shí)現(xiàn)程序Semaphore apple,banana,mutex;apple.value=0,banana.value=0,mutex.valu

44、e=1;cobegin process father() while(1) P(mutex); /請求盤子使用權(quán) V(apple); /通知女兒可取盤中的蘋果 /若女兒被阻塞則喚醒她 process mother() while(1) P(mutex); /請求盤子使用權(quán) V(banana); /通知兒子可取盤中的香蕉 /若兒子被阻塞則喚醒他 process daughter() while(1) P(apple); /測試是否盤子有蘋果 /若無則阻塞自己 V(mutex); /釋放盤子使用權(quán) /若父母有阻塞者則喚醒之 process son() while(1) P(banana); /測試

45、是否盤子有香蕉 /若無則阻塞自己 V(mutex); /釋放盤子使用權(quán) /若父母有阻塞者則喚醒之 coend3.5.3 汽車過橋問題問題描述：見下圖，橋上不允許兩車交會，但允許同方向多輛車依次通行（即橋上可以有多個同方向的車）。用P、V操作實(shí)現(xiàn)交通管理以防止橋上堵車。3.5 經(jīng)典互斥與同步問題的應(yīng)用解決方法：（1）如果某一方向的車先到，則讓該方向的車過橋。但可能會出現(xiàn)該方向的車源源不斷的到達(dá)、過橋，使得另一方向的車處于“饑餓”狀態(tài)。（2）參考讀者-寫者問題中的寫者優(yōu)先算法，即橋上允許同一方向的多輛車依次過橋，如果此時對方有車提出過橋，則阻塞本方還未上橋的后續(xù)車輛，待橋上本方的車輛過完后，對方的

46、車輛開始過橋。 汽車過橋問題實(shí)現(xiàn)程序Semaphore mutex1,mutex2,wait;mutex1.value=1,mutex2.value=1,wait.value=1;int count1=0,count2=0;cobegin process N_i() /i=1,2,3,m P(wait); /對方車輛過橋時阻止本方車輛上橋 P(mutex1); /申請對count1的訪問權(quán) /如果對方車輛已上橋則阻塞自己 if(count1=0) P(mutex2); /己方第一個上橋車輛則阻塞對方車輛上橋 count1+; /己方過橋車輛加1 V(mutex1); /釋放對count1的訪問

47、權(quán) V(wait); /允許后續(xù)車輛申請過橋; P(mutex1); /申請對count1的訪問權(quán) count1-; /己方過橋車輛減1 if(count1=0) V(mutex2); /己方最后一個車輛過橋后允許對方車輛上橋 /如有被阻塞的對方車輛則喚醒其過橋 V(mutex1); /釋放對count1的訪問權(quán) process S_j() /j=1,2,3,n P(wait); /對方車輛申請過橋時阻止本方車輛上橋 P(mutex2); /申請對count2的訪問權(quán) /如果對方車輛已上橋則阻塞自己 if(count2=0) P(mutex1); /己方第一個上橋車輛則阻塞對方車輛上橋 cou

48、nt2+; /己方過橋車輛加1 V(mutex2); /釋放對count2的訪問權(quán) V(wait); /允許后續(xù)到達(dá)的車輛請求過橋; P(mutex2); /申請對count2的訪問權(quán) count2-; /己方過橋車輛減1 if(count2=0) V(mutex1); /己方最后一個車輛過橋后允許對方車輛上橋 /如有被阻塞的對方車輛則喚醒其過橋 V(mutex2); /釋放對count2的訪問權(quán) coend 為了解決信號量機(jī)制帶來的不便而引入了管程同步機(jī)制。 管程（Monitor）是一種新的進(jìn)程互斥與同步機(jī)制，它能夠提供與信號量同等的功能。使用管程機(jī)制可以將分散在各進(jìn)程中的同步操作集中起來統(tǒng)

49、一控制和管理，更方便地實(shí)現(xiàn)進(jìn)程的互斥與同步，同時也可以減少錯誤的發(fā)生。3.6 管程機(jī)制3.6.1 條件變量與管程結(jié)構(gòu)1. 條件變量 為了避免多個進(jìn)程在管程中出現(xiàn)“忙等”現(xiàn)象，管程提供了條件變量機(jī)制，讓暫時不能進(jìn)入管程的進(jìn)程阻塞或掛起等待。條件變量（Condition Variable）是管程提供的一種進(jìn)程同步機(jī)制，它能夠在多個進(jìn)程之間傳遞信號并解決管程內(nèi)進(jìn)程可能出現(xiàn)的“忙等”問題。 條件變量是封裝在管程內(nèi)的一種數(shù)據(jù)結(jié)構(gòu)，它對應(yīng)一個進(jìn)程阻塞隊(duì)列并只能被管程中的過程（函數(shù)）訪問，且是管程內(nèi)的所有過程（函數(shù)）的全局變量。條件變量只能通過wait和signal兩個原語進(jìn)行控制，而wait和signal

50、原語總是在某個條件變量（如X）上執(zhí)行，表示為X.wait或X.signal。X.wait操作的作用是使本進(jìn)程阻塞在條件變量X上，X.signal操作的作用是若有進(jìn)程的被阻塞在條件變量X上，則將第一個阻塞進(jìn)程喚醒。3.6 管程機(jī)制條件變量與信號量的區(qū)別：（1）與信號量具有值的概念不同，條件變量沒有關(guān)聯(lián)的值；（2）在管程中執(zhí)行signal操作時，如果相應(yīng)的阻塞隊(duì)列中沒有阻塞進(jìn)程則本次操作為空操作，即什么也不做；（3）在信號量中則不會出現(xiàn)這種情況，V操作在阻塞隊(duì)列中沒有阻塞進(jìn)程時也必須對信號量進(jìn)行加1操作（資源個數(shù)增1）。3.6 管程機(jī)制2. 管程結(jié)構(gòu)管程的性質(zhì)：（1）管程中不僅有數(shù)據(jù)而且有對數(shù)據(jù)的

51、操作，即管程是一種擴(kuò)展了的抽象數(shù)據(jù)類型。（2）管程這種擴(kuò)展了的抽象數(shù)據(jù)類型的描述對象是互斥資源，因此，管程實(shí)際上是互斥資源的管理模塊。（3）作為一個軟件模塊，管程應(yīng)符合模塊化的要求，即管程應(yīng)是一個基本程序單位，并可以被單獨(dú)編譯。（4）管程中的數(shù)據(jù)結(jié)構(gòu)只能被管程中的過程（函數(shù)）使用，管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)和過程（函數(shù)）的具體實(shí)現(xiàn)在外部是不可見的。（5）為了實(shí)現(xiàn)對互斥資源的共享，管程應(yīng)有互斥與同步機(jī)制。3.6 管程機(jī)制管程的定義：一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和在該數(shù)據(jù)結(jié)構(gòu)上執(zhí)行的一組過程（函數(shù)），這組過程（函數(shù)）能夠同步進(jìn)程和改變管程中的局部數(shù)據(jù)。管程的組成： （1）局部于管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)； （2）管程內(nèi)

52、共享數(shù)據(jù)的初始化語句； （3）一組對管程內(nèi)數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪問的調(diào)用過程（函數(shù)）。3.6 管程機(jī)制使用管程實(shí)現(xiàn)進(jìn)程同步的特點(diǎn)：（1）管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)只能由管程定義的過程（函數(shù)）訪問，任何外部過程（函數(shù)）都不能訪問它們。（2）任何時刻只能有一個進(jìn)程在管程中執(zhí)行，其他申請進(jìn)入管程的進(jìn)程必須阻塞等待。（3）一個外部過程（函數(shù)）只有通過調(diào)用管程內(nèi)的一個過程（函數(shù)）才能進(jìn)入管程。3.6 管程機(jī)制管程描述如下： monitor 管程名 公用變量說明; 條件變量說明; 初始化語句; define 管程內(nèi)定義的，管程外可以調(diào)用的過程或函數(shù)名列表; use 管程外定義的，管程內(nèi)將要調(diào)用的過程或函數(shù)名列表; 過程或函

53、數(shù)1定義; 過程或函數(shù)2定義;過程或函數(shù)k定義; 3.6 管程機(jī)制例題：一餐廳有50個座位可供用餐者就餐，超過50人時只能排隊(duì)等侯，待空出座位方可就餐，試用管程實(shí)現(xiàn)之。 管程在進(jìn)程同步中的應(yīng)用 就餐問題管程實(shí)現(xiàn)程序monitor Restaurant int count=0; /就餐者計數(shù) condition notfull; /定義條件變量 define eating; /函數(shù)eating在管程內(nèi)定義,在管程外也可調(diào)用 void eating() if(count=50) /就餐者已有50人 notfull.wait; /超過50人時被阻塞 count+; /未超過50人時計數(shù)加1 進(jìn)入餐廳

54、; 就餐; 走出餐廳; count-; /就餐者計數(shù)減1 if(count=49) /有一個空座位時 notfull.signal; /喚醒等候就餐隊(duì)列上的第一人(如果有的話) 管程解決就餐問題的方法如下： cobegin process eat_i() / i=1,2,3,m Restaurant. eating(); coend 吃水果問題的管程實(shí)現(xiàn)程序monitor Eat_fruit int flag=0; /0:無水果,1:有蘋果,2:有香蕉 condition notfull,notempty2; define put,get; void put(int k) /將水果放入盤中 i

55、f(flag0) /盤中已有水果 notfull.wait; /將進(jìn)程掛到阻塞隊(duì)列 flag=k; /盤中無水果時記錄水果編號 放入k號水果到盤中; /放入水果 notemptyk-1.signal; /有等待k號水果進(jìn)程被阻塞則喚醒之 void get(int k) /從盤中取出水果 if(flag!=k) /無水果或與所取水果不符 notemptyk-1.wait /阻塞當(dāng)前執(zhí)行進(jìn)程并掛到阻塞隊(duì)列 從盤中取出k號水果; /相符則取出水果 flag=0; /置盤為空標(biāo)志 notfull.signal; /若有阻塞進(jìn)程則喚醒之 使用管程解決吃水果問題的方法如下： cobegin process

56、 father() 拿一個蘋果; Eat_fruit.put(1); /管程實(shí)現(xiàn)將蘋果放入盤中 process mother() 拿一個香蕉; Eat_fruit.put(2); /管程實(shí)現(xiàn)將香蕉放入盤中 process daughter () Eat_fruit.get(1); /管程實(shí)現(xiàn)從盤中取蘋果吃蘋果 process son () Eat_fruit.get(2); /管程實(shí)現(xiàn)從盤中取香蕉吃香蕉 coend 注意：條件變量notempty設(shè)為數(shù)組形式，實(shí)為兩個條件變量，即女兒或兒子進(jìn)程阻塞時將分別掛到notempty0.wait或notempty1.wait阻塞隊(duì)列上，因此當(dāng)放入水果到

57、盤中后，喚醒的總是需要盤中水果的兒子進(jìn)程或女兒進(jìn)程，這樣就保證喚醒的兒子進(jìn)程或女兒進(jìn)程能夠及時取出盤中的水果。 如果只使用一個條件變量notempty，則可能出現(xiàn)這種情況：初始時盤為空，然后依次執(zhí)行兒子進(jìn)程和女兒進(jìn)程，因盤為空，則兒子進(jìn)程和女兒進(jìn)程就依次掛到notempty.wait阻塞隊(duì)列上，這時若執(zhí)行父親進(jìn)程將蘋果放入盤中，此時喚醒notempty.wait阻塞隊(duì)列上掛著的第一個進(jìn)程即兒子進(jìn)程，但兒子進(jìn)程執(zhí)行時，則因?yàn)楸P中水果與所取水果不符而再次阻塞在notempty.wait隊(duì)列上，這時無論執(zhí)行父親進(jìn)程還是母親進(jìn)程，都因盤中已有水果而無法再放入水果，而被阻塞在notfull.wait隊(duì)列

58、上，即造成了所有進(jìn)程都被阻塞，而無法執(zhí)行的死鎖局面出現(xiàn)。 吃水果問題條件變量設(shè)置說明3.6.2 生產(chǎn)者-消費(fèi)者問題的管程解決方法 在生產(chǎn)者-消費(fèi)者問題中，生產(chǎn)者進(jìn)程生產(chǎn)完一個產(chǎn)品后，如果緩沖池中所有的緩沖區(qū)都裝滿產(chǎn)品，則生產(chǎn)者進(jìn)程被阻塞；同樣，消費(fèi)者進(jìn)程需要消費(fèi)一個產(chǎn)品時，如果此時緩沖池中所有的緩沖區(qū)都為空，則消費(fèi)者進(jìn)程被阻塞。需要設(shè)置兩個不同的阻塞隊(duì)列，即引入兩個條件變量：notfull和notempty來分別對應(yīng)這兩種不同的阻塞條件。 管程在進(jìn)程同步中的應(yīng)用實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者進(jìn)程同步的管程Producer_consumer描述如下：monitor Producer_consumer ite

59、m Bn; /模擬緩沖池 int in=0,out=0,count=0; condition notfull,notempty; /定義兩個條件變量 define put,get; /函數(shù)put和get在管程內(nèi)定義，在管程外也可調(diào)用 void put(item x) /將產(chǎn)品投放到緩沖池中 if(count=n) notfull.wait; /若緩沖池滿則阻塞自己并掛到notfull阻塞隊(duì)列上 Bin=x; /將產(chǎn)品投放到in指向的空緩沖區(qū)中 in=(in+1)%n; /指針in指向下一個空緩沖區(qū) count+; /滿緩沖區(qū)個數(shù)加1 notempty.signal; /喚醒notempty阻塞

60、隊(duì)列上第一個消費(fèi)者進(jìn)程（如果有的話） 3.6 管程機(jī)制void get(item *x) /從緩沖池中取出一個產(chǎn)品放到x所指的地址中 if(count=0) notempty.wait; /若緩沖池空則阻塞自己并掛到notempty阻塞隊(duì)列上 *x=Bout; /由out指向的滿緩沖區(qū)中取出產(chǎn)品賦給*x out=(out+1)%n; /指針out指向下一個滿緩沖區(qū) count-; /滿緩沖區(qū)個數(shù)減1 notfull.signal; /喚醒notfull阻塞隊(duì)列上第一個生產(chǎn)者進(jìn)程（如果有的話） 3.6 管程機(jī)制生產(chǎn)者-消費(fèi)者進(jìn)程同步的管程Producer_consumermonitor Prod