1、1,第三章 同步、通信與死鎖,2,3.1 進(jìn)程的同步與互斥 在多道程序的環(huán)境中，系統(tǒng)中的多個(gè)進(jìn)程可以并發(fā)執(zhí)行，同時(shí)它們又要共享系統(tǒng)中的資源，由此諸進(jìn)程間會(huì)產(chǎn)生錯(cuò)綜復(fù)雜的相互制約的關(guān)系。 一、進(jìn)程間制約關(guān)系 1.競(jìng)爭(zhēng)關(guān)系 源于資源共享，多個(gè)不存在邏輯關(guān)系的進(jìn)程因共享資源而產(chǎn)生制約關(guān)系。 若一個(gè)進(jìn)程要求使用某一資源，而該資源正被另一個(gè)進(jìn)程使用，并且這一資源不允許兩個(gè)進(jìn)程同時(shí)訪問(wèn)，那么該進(jìn)程只有等待，只有這一資源釋放后才能使用。 2.協(xié)作關(guān)系 源于進(jìn)程間的協(xié)作。 一組進(jìn)程為完成共同任務(wù)分工協(xié)作，各進(jìn)程都獨(dú)立以不可預(yù)知速度推進(jìn)，在執(zhí)行的先后次序就有約束，在一些關(guān)鍵點(diǎn)上協(xié)調(diào)工作。若一個(gè)進(jìn)程運(yùn)行到某關(guān)鍵點(diǎn)

2、時(shí)，在尚未收到另一協(xié)作進(jìn)程發(fā)來(lái)的信息前應(yīng)阻塞自己，等協(xié)作進(jìn)程發(fā)來(lái)消息后方可繼續(xù)執(zhí)行。,進(jìn)程資源進(jìn)程,進(jìn)程進(jìn)程,3,進(jìn)程間這種相互依賴又相互制約，相互協(xié)作又相互競(jìng)爭(zhēng)的關(guān)系，主要表現(xiàn)在進(jìn)程互斥和進(jìn)程同步兩方面 二、進(jìn)程互斥 引例： 宿舍電話的使用 打印機(jī)的使用 1、臨界資源 一次僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源。 引例中的電話和打印機(jī)都屬于臨界資源。還有光盤(pán)刻錄機(jī)、繪圖儀、共享變量、共享的數(shù)據(jù)結(jié)構(gòu)等等也是臨界資源。 2、臨界區(qū)： 每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段程序段稱為臨界區(qū)。（臨界段）,4,例：統(tǒng)計(jì)兩個(gè)進(jìn)程P1和P2對(duì)共享變量count的訪問(wèn)計(jì)數(shù)。 P1： . P2: . R1=count;

3、R2=count; R1=R1+1; R2=R2+1; count=R1; count=R2; . . 兩進(jìn)程并發(fā)執(zhí)行，可能的執(zhí)行順序?yàn)椋?P1: R1=count; R1=R1+1; P2: R2=count; R2=R2+1; count=R2; P1: count=R1; 雖然兩個(gè)進(jìn)程各自都執(zhí)行了對(duì)count加1的操作，但結(jié)果為何count只增加1？ count是臨界資源，P1、P2訪問(wèn)count的兩個(gè)程序段就是臨界區(qū)，兩個(gè)進(jìn)程必須互斥的進(jìn)入臨界區(qū),否則就可能出與時(shí)間有關(guān)的錯(cuò)誤.,5,、進(jìn)程互斥 進(jìn)程應(yīng)互斥訪問(wèn)同一臨界資源，即進(jìn)程應(yīng)互斥的進(jìn)入臨界區(qū)。當(dāng)一進(jìn)程正在訪問(wèn)某臨界區(qū)時(shí)，就不允許其

4、它進(jìn)程進(jìn)入，試圖進(jìn)入臨界區(qū)的另一進(jìn)程必須等待。進(jìn)程之間的這種相互制約的關(guān)系稱為進(jìn)程互斥。,4、進(jìn)入臨界區(qū)的準(zhǔn)則： 每次至多有一個(gè)進(jìn)程進(jìn)入臨界區(qū)內(nèi)執(zhí)行； 若已有進(jìn)程在臨界區(qū)中，試圖進(jìn)入此臨界區(qū)的其他進(jìn)程應(yīng)等待； 進(jìn)入臨界區(qū)的進(jìn)程應(yīng)在有限時(shí)間內(nèi)退出，以便讓等待隊(duì)列中的一個(gè)進(jìn)程進(jìn)入。,6,三、進(jìn)程同步,引例：兩位同學(xué)約好星期天去玩，早上8:00在校門(mén)口，不見(jiàn)不散。當(dāng)一個(gè)同學(xué)先來(lái)到校門(mén)口，要等另一個(gè)同學(xué)，到齊后一起去玩。,互斥的概念來(lái)自于諸進(jìn)程對(duì)臨界資源的競(jìng)爭(zhēng)，同步來(lái)源于多個(gè)進(jìn)程的協(xié)作。在人類社會(huì)中競(jìng)爭(zhēng)與協(xié)作是永恒的。 進(jìn)程同步：幾個(gè)進(jìn)程相互協(xié)作，一個(gè)進(jìn)程到達(dá)某點(diǎn)后，若另一進(jìn)程尚未完成某些操作，就必須

5、停下來(lái)等待，只有等另一進(jìn)程的這些操作完成了才能繼續(xù)執(zhí)行。協(xié)作進(jìn)程間需要在某些關(guān)鍵點(diǎn)上排定執(zhí)行先后次序而等待、傳遞信號(hào)或消息所產(chǎn)生的協(xié)作關(guān)系稱為進(jìn)程同步。,7,例：計(jì)算fun1(X)*fun2(y) 兩進(jìn)程合作完成任務(wù) 進(jìn)程1：計(jì)算fun1(X)。 進(jìn)程2：計(jì)算fun2(X)；與進(jìn)程1結(jié)果相乘。 進(jìn)程1和進(jìn)程2并發(fā)執(zhí)行。,8,3.2 進(jìn)程互斥的實(shí)現(xiàn),一、實(shí)現(xiàn)進(jìn)程互斥的軟件算法 現(xiàn)在很少用軟件方法解決互斥，但通過(guò)學(xué)習(xí)軟件解法能使讀者了解到，在早期進(jìn)程互斥問(wèn)題的解決并不是一件很簡(jiǎn)單的事。,9,嘗試 (1),bool inside1=false; /P1不在其臨界區(qū)內(nèi) bool inside2=fal

6、se; /P2不在其臨界區(qū)內(nèi) cobegin process P1( ) process P2( ) while(inside2); while(inside1); inside1=true; inside2=true; 臨界區(qū); 臨界區(qū); inside1=false; inside2=false; coend P1和P2可能同時(shí)進(jìn)入臨界區(qū),10,嘗試 (2),bool inside1=false; /P1不在其臨界區(qū)內(nèi) bool inside2=false; /P2不在其臨界區(qū)內(nèi) cobegin process P1( ) process P2( ) inside1=true; inside

7、2=true; while(inside2); while(inside1); 臨界區(qū); 臨界區(qū); inside1=false; inside2=false; coend P1和P2可能永遠(yuǎn)等待。,11,process P0( ) inside0=true; turn=1; while(inside1 ,process P1( ) inside1=true; turn=0; while(inside0 ,cobegin,coend,bool inside2; inside0=false; inside1=false; enum 0,1 turn;,Peterson算法,12,為每一進(jìn)程設(shè)標(biāo)志位

8、insidei，當(dāng)insidei=true時(shí)，表示進(jìn)程pi要求進(jìn)入，或正在臨界區(qū)中執(zhí)行。此外再設(shè)一個(gè)變量turn，用于指示允許進(jìn)入的進(jìn)程編號(hào)。 進(jìn)程0為了進(jìn)入先置inside0=true，并置turn為1，表示應(yīng)輪到p1進(jìn)入。接著再判斷inside1 cobegin process Pi( ) /i=1,2,.,n while(!TS(s); /上鎖 臨界區(qū); s=true; /開(kāi)鎖 coend,變量s代表了臨界資源的狀態(tài)，可把它看成一把鎖。S初值設(shè)為true，表示沒(méi)有進(jìn)程在臨界區(qū)，資源可用。進(jìn)入臨界區(qū)前，首先用TS指令測(cè)試s，若沒(méi)有進(jìn)程在臨界區(qū)，則可進(jìn)入，否則循環(huán)測(cè)試直至s的值為true；當(dāng)

9、進(jìn)程退出臨界區(qū)時(shí)，把s的值置為true。,18,3.swap指令實(shí)現(xiàn)進(jìn)程互斥,swap指令 又稱交換指令，在Intel x86中稱為XCHG。 功能是交換兩個(gè)字的內(nèi)容。,void SWAP(bool ,19,利用swap實(shí)現(xiàn)進(jìn)程互斥 為每一臨界資源設(shè)置一個(gè)全局布爾變量lock，其初值為false，表示無(wú)進(jìn)程在臨界區(qū)內(nèi)。在每個(gè)進(jìn)程中有局部布爾變量keyi。,bool lock=false; cobegin Process Pi( ) /i=1,2,.,n bool keyi=true; do SWAP(keyi,lock); while(keyi); /上鎖 臨界區(qū); SWAP(keyi,loc

10、k); /開(kāi)鎖 coend,20,實(shí)現(xiàn)進(jìn)程互斥的軟件算法太過(guò)復(fù)雜，效率低下； 實(shí)現(xiàn)進(jìn)程互斥的硬件方法雖簡(jiǎn)單有效，但采用忙式等待，白白浪費(fèi)cpu時(shí)間；將測(cè)試能否進(jìn)入臨界區(qū)的責(zé)任推卸給各進(jìn)程，會(huì)削弱系統(tǒng)的可靠性，加重用戶的編程負(fù)擔(dān)；且這些方案只能解決進(jìn)程互斥問(wèn)題，卻不能解決進(jìn)程同步問(wèn)題。,21,3.3 信號(hào)量與PV操作,一、信號(hào)量的概念 信號(hào)量的概念是由荷蘭科學(xué)家Dijkstra于1965年提出的。,管理和控制鐵路和公路交通的重要工具是信號(hào)燈，利用信號(hào)燈的顏色控制各種車(chē)輛的正常通行。在操作系統(tǒng)中引入了信號(hào)燈（信號(hào)量）的概念，讓多個(gè)進(jìn)程通過(guò)信號(hào)量展開(kāi)交互。,22,1.信號(hào)量的定義 是一個(gè)結(jié)構(gòu)型數(shù)據(jù)結(jié)

11、構(gòu)，定義如下： struct semaphore int value; /信號(hào)量的值 struct pcb *list; /信號(hào)量隊(duì)列的頭指針 信號(hào)量說(shuō)明： semaphore s; 信號(hào)量必須置一次且只能置一次初值，初值不能為負(fù)數(shù)。 對(duì)信號(hào)量只能執(zhí)行P、V操作,23,2.P、V操作 對(duì)信號(hào)量?jī)H能執(zhí)行P、V操作。 對(duì)信號(hào)量的P操作記為：P(S)，P操作是一個(gè)原子操作。 對(duì)信號(hào)量的V操作記為：V(S), V操作是一個(gè)原子操作。 在實(shí)際系統(tǒng)中，一般情況下是由機(jī)器硬件提供P、V操作的指令，當(dāng)然是原子操作，若機(jī)器不提供P、V操作的指令，則操作系統(tǒng)提供P、V操作原語(yǔ)。,24,P(s)： s.value-

12、； 若s.value0，則執(zhí)行P(s)的進(jìn)程繼續(xù)執(zhí)行； 若s.value0，則執(zhí)行P(s)的進(jìn)程被阻塞，并把它插入到等待信號(hào)量s的阻塞隊(duì)列中。,V(s)： s.value+； 若s.value0 ，則執(zhí)行V(s)的進(jìn)程繼續(xù)執(zhí)行； 若s.value0，則執(zhí)行V(s)的進(jìn)程從等待信號(hào)量s的阻塞隊(duì)列中喚醒頭一個(gè)進(jìn)程，然后自己繼續(xù)執(zhí)行。,操作系統(tǒng)正是利用信號(hào)量的狀態(tài)對(duì)進(jìn)程和資源進(jìn)行管理。從物理意義上理解，P操作相當(dāng)于申請(qǐng)資源；V操作相當(dāng)于釋放資源。,25,二、用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥,1. 兩個(gè)進(jìn)程間的互斥 semaphore S； S =1； cobegin Process P1( ) Process

13、P2( ) P（S） P（S） V（S） V（S） coend,臨界區(qū),臨界區(qū),26,對(duì)于兩個(gè)并發(fā)進(jìn)程，互斥信號(hào)量的值僅取1、0和-1三個(gè)值 若S1表示沒(méi)有進(jìn)程進(jìn)入臨界區(qū) 若S0表示有一個(gè)進(jìn)程進(jìn)入臨界區(qū) 若S-1表示一個(gè)進(jìn)程進(jìn)入臨界區(qū)，另一個(gè)進(jìn)程等待進(jìn)入。,27,例：有一個(gè)售票廳只能容納300人，當(dāng)少于300人時(shí)，可以進(jìn)入購(gòu)票；否則在外等待。若將每一個(gè)購(gòu)票者看作一個(gè)進(jìn)程，請(qǐng)用P、V操作編程實(shí)現(xiàn)。,semaphore S； S=300； Process Pi()（i=1，2，3，） P(S)； 進(jìn)入購(gòu)票廳； 購(gòu)票； 離開(kāi)購(gòu)票廳； V(S)； ,28,思考： 對(duì)于n個(gè)并發(fā)進(jìn)程，如何實(shí)現(xiàn)互斥； 信號(hào)

14、量的取值范圍是什么，有什么含義。,設(shè)置互斥信號(hào)量 S=m（m為某種臨界資源可用數(shù)量） cobegin process P1 process P2 process pn P（S） P（S） P（S） V（S） V（S） V（S） coend,臨界區(qū),臨界區(qū),臨界區(qū),互斥信號(hào)量聯(lián)系一組并發(fā)進(jìn)程，各進(jìn)程對(duì)此信號(hào)量執(zhí)行P、V操作，因此又稱為公用信號(hào)量。,29,信號(hào)量取值范圍：mm-n 信號(hào)量的含義： S0表示有S個(gè)資源可用 S=0表示無(wú)資源可用 S0則| S |表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù),30,三、用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步,1.進(jìn)程同步模型 進(jìn)程P1到達(dá)L1這一點(diǎn)時(shí)，若進(jìn)程P2還未執(zhí)行到L2點(diǎn)，進(jìn)程P1

15、就必須停下來(lái)等待，等到進(jìn)程P2到達(dá)L2這一點(diǎn)時(shí)，P1才能繼續(xù)運(yùn)行。也就是進(jìn)程P1在L1這一點(diǎn)要與進(jìn)程P2同步。 （P1等待P2） semaphore s； S=0 Cobegin process P1（） process P2（） L1:P(s) L2:V(s) coend,總結(jié)： P1在L1點(diǎn)等待P2進(jìn)程執(zhí)行到L2點(diǎn)才能繼續(xù)執(zhí)行。 設(shè)置信號(hào)量s=0 P1進(jìn)程L1點(diǎn)：P(S) P2進(jìn)程L2點(diǎn)：V(S),31,在操作系統(tǒng)中，同步有各種各樣，歸納起來(lái)有兩類： 保證一組合作進(jìn)程按確定的次序執(zhí)行 保證共享緩沖區(qū)的合作進(jìn)程的同步。,2.合作進(jìn)程的執(zhí)行次序 若干個(gè)進(jìn)程為了完成一個(gè)共同任務(wù)而并發(fā)執(zhí)行，在這些

16、進(jìn)程中，有些進(jìn)程之間有次序的要求，有些進(jìn)程之間沒(méi)有次序的要求。 為了描述方便，可以用一個(gè)圖來(lái)描述諸進(jìn)程合作完成某一任務(wù)的次序。進(jìn)程流圖,32,33,進(jìn)程流圖是實(shí)際例子抽象出來(lái)的。 例：(a+b)*(c+d)+c*f,34,例：試用信號(hào)量實(shí)現(xiàn)這三個(gè)并發(fā)進(jìn)程按確定的次序執(zhí)行。 a、分析進(jìn)程的同步關(guān)系 進(jìn)程P1、P2可并發(fā)執(zhí)行，P3的執(zhí)行必須等待P1、P2都完成后才能開(kāi)始執(zhí)行。 b、設(shè)置信號(hào)量，說(shuō)明含義、初值。 s13 = 0 表示進(jìn)程P1尚未執(zhí)行完成； s23 = 0 表示進(jìn)程P2尚未執(zhí)行完成； c、寫(xiě)出程序描述,35,36,例：試用信號(hào)量實(shí)現(xiàn)這三個(gè)進(jìn)程的同步。 Semaphore SB，SC；

17、SB=0； SC=0； cobegin Pa（） Pb（） Pc（） P(SB); P(SC)； V(SB); V(SC); coend,37,3.共享緩沖區(qū)的合作進(jìn)程的同步 設(shè)有一個(gè)緩沖區(qū)buffer，大小為一個(gè)字節(jié)，某計(jì)算進(jìn)程和打印進(jìn)程共用，CP進(jìn)程不斷產(chǎn)生字符，送buffer，IOP進(jìn)程從buffer中取出字符打印。 如不加控制，會(huì)有多種打印結(jié)果，這取決于這兩個(gè)進(jìn)程運(yùn)行的相對(duì)速度。在這眾多的打印結(jié)果中，只有CP、IOP進(jìn)程的運(yùn)行剛好匹配的一種是對(duì)的，其它均為錯(cuò)誤，并且不能重現(xiàn)。,38,要保證打印結(jié)果的正確，CP、IOP必須遵循以下同步規(guī)則： (1)當(dāng)CP把結(jié)果送入buffer后，IOP才

18、能從buffer中取，否則IOP必須等待； (2)當(dāng)IOP從buffer中取走數(shù)據(jù)后，CP才能將新產(chǎn)生數(shù)據(jù)送buffer，否則也必須等待。,解決這個(gè)問(wèn)題的步驟： (1)分析問(wèn)題，弄清楚同步關(guān)系，如上分析； (2)設(shè)置信號(hào)量，說(shuō)明含義、初值； (3)寫(xiě)出程序描述。,39,40,四、互斥和同步對(duì)信號(hào)量操作方法的差異,互斥和同步都是通過(guò)對(duì)信號(hào)量的P、V操作來(lái)實(shí)現(xiàn)的，但這兩種控制機(jī)制對(duì)信號(hào)量的操作策略是不同的。 互斥的實(shí)現(xiàn)： 是不同進(jìn)程對(duì)同一信號(hào)量進(jìn)行P、V操作。進(jìn)入臨界區(qū)之前執(zhí)行P操作，退出臨界區(qū)后執(zhí)行V操作。 同步的實(shí)現(xiàn)： Pa進(jìn)程要同步等待Pb需設(shè)置一信號(hào)量，Pa進(jìn)程中實(shí)行P操作，Pb進(jìn)程實(shí)行V

19、操作。 若進(jìn)程Pb也要同步等待Pa，則要設(shè)置另一個(gè)信號(hào)量。 P.V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作 當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程 當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn),41,五、經(jīng)典的進(jìn)程同步、互斥問(wèn)題,1.生產(chǎn)者消費(fèi)者問(wèn)題,問(wèn)題描述： 有m個(gè)生產(chǎn)者和n個(gè)消費(fèi)者，它們共享可存放k件產(chǎn)品的緩沖區(qū)。 只要緩沖區(qū)未滿，生產(chǎn)者就可以把產(chǎn)品送入緩沖區(qū); 只要緩沖區(qū)未空，消費(fèi)者就可以從緩沖區(qū)中取走物品。,42,著名的生產(chǎn)者-消費(fèi)者問(wèn)題是計(jì)算機(jī)操作系統(tǒng)中并發(fā)進(jìn)程內(nèi)在關(guān)系的一種抽象，是典型的進(jìn)程同步問(wèn)題。 在操作系統(tǒng)中，生產(chǎn)者進(jìn)程可以是計(jì)算進(jìn)程、發(fā)送進(jìn)程；而消費(fèi)者進(jìn)程可以是打印進(jìn)程、接收

20、進(jìn)程等等。 解決好生產(chǎn)者-消費(fèi)者問(wèn)題就解決好了一類并發(fā)進(jìn)程的同步問(wèn)題。,43,問(wèn)題分析,對(duì)于生產(chǎn)者進(jìn)程：生產(chǎn)一個(gè)產(chǎn)品，當(dāng)要送入緩沖區(qū)時(shí)，要檢查是否有空緩沖區(qū)，若有，則可將產(chǎn)品送入緩沖區(qū)，并通知消費(fèi)者進(jìn)程；否則，等待； 對(duì)于消費(fèi)者進(jìn)程：當(dāng)它去取產(chǎn)品時(shí)，要看緩沖區(qū)中是否有產(chǎn)品可取，若有則取走一個(gè)產(chǎn)品，并通知生產(chǎn)者進(jìn)程，否則，等待。 這種相互等待，并互通信息就是典型的進(jìn)程同步。 因此應(yīng)該設(shè)兩個(gè)同步信號(hào)量： empty：表示可用的空緩沖區(qū)的數(shù)目，初值為k full：表示可以使用產(chǎn)品的數(shù)目，初值為。 緩沖區(qū)是一個(gè)臨界資源，必須互斥使用，所以另外還需要設(shè)置一個(gè)互斥信號(hào)量mutex，其初值為。,44,問(wèn)題的

21、解,item Bk; semaphore empty;empty=k; /可以使用的空緩沖區(qū)數(shù) semaphore full; full=0; /緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù) semaphore mutex;mutex=1; /互斥信號(hào)量 int in=0; /放入緩沖區(qū)指針 int out=0; /取出緩沖區(qū)指針,cobegin process producer_i ( ) process consumer_j ( ) while(true) while(true) produce( ); P(full); P(empty); P(mutex); P(mutex); take( ) from B

22、out; append to Bin; out=(out+1)%k; in=(in+1)%k; V(mutex); V(mutex); V(empty); V(full); consume( ); coend,45,討論： 若將生產(chǎn)者進(jìn)程中兩個(gè)P操作交換次序，那么當(dāng)緩沖區(qū)存滿k件產(chǎn)品（empty=0，mutex=1，full=k）時(shí)，生產(chǎn)者又生產(chǎn)一件產(chǎn)品，將在P(empty)上等待，此時(shí)mutex=0。消費(fèi)者進(jìn)程將在P(mutex)上等待。這就導(dǎo)致兩進(jìn)程都處于無(wú)休止的等待狀態(tài)，造成了死鎖。 若將消費(fèi)者進(jìn)程中兩P操作交換次序，則當(dāng)緩沖區(qū)為空時(shí)，也會(huì)出項(xiàng)上述類似問(wèn)題。,46,總結(jié)： P.V操作必須

23、成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作。 當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程。 當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)。 如果兩個(gè)P操作在一起，那么P操作的順序至關(guān)重要。 一個(gè)同步P操作與一個(gè)互斥P操作在一起時(shí)，同步P操作在互斥P操作前。 而兩個(gè)V操作在一起時(shí)順序無(wú)關(guān)緊要。,47,2. 讀者/寫(xiě)者問(wèn)題,問(wèn)題描述 有兩組并發(fā)進(jìn)程: 讀者和寫(xiě)者,共享一個(gè)文件F 要求： 允許多個(gè)讀者同時(shí)執(zhí)行讀操作 只允許一個(gè)寫(xiě)者執(zhí)行寫(xiě)操作 任一寫(xiě)者在完成寫(xiě)操作之前不允許其它讀者或?qū)懻吖ぷ?寫(xiě)者執(zhí)行寫(xiě)操作前，應(yīng)讓已有的寫(xiě)者和讀者全部退出,48,問(wèn)題分析,讀者和寫(xiě)者互斥，寫(xiě)者和寫(xiě)者互斥訪問(wèn)文件 設(shè)信號(hào)量writeblo

24、ck，用于實(shí)現(xiàn)讀寫(xiě)互斥、寫(xiě)寫(xiě)互斥地訪問(wèn)文件。 另設(shè)一個(gè)全局變量readcount，記錄正在讀的讀者數(shù)目。 設(shè)置信號(hào)量mutex，用于使讀者互斥地訪問(wèn)共享變量readcount 。,49,int readcount=0; /讀進(jìn)程計(jì)數(shù) semaphore writeblock,mutex; writeblock=1; mutex=1; cobegin process reader_i( ) process writer_j( ) P(mutex); P(writeblock); readcount+; 寫(xiě)文件; if(readcount=1) V(writeblock); P(writebloc

25、k); V(mutex); 讀文件; P(mutex); readcount-; if(readcount=0) V(writeblock); V(mutex); Coend,50,3.哲學(xué)家就餐問(wèn)題,問(wèn)題描述,有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤(pán)通心面，每人面前有一只空盤(pán)于，每?jī)扇酥g放一把叉子。每個(gè)哲學(xué)家思考、饑餓、然后吃通心面。為了吃面，每個(gè)哲學(xué)家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子。,51,問(wèn)題分析,每把叉子都必須互斥使用，因此為每把叉子設(shè)置互斥信號(hào)量forki(i=0,1,2,3,4),初值均為1； 當(dāng)哲學(xué)家吃面前必須執(zhí)行兩個(gè)P操作，獲得自己左邊和右邊的兩把叉

26、子；吃完后必須執(zhí)行兩次V操作，放下兩把叉子。,52,semaphore fork5; for (int i=0;i5;i+) forki=1; cobegin process philosopher_i( ) /i= 0,1,2,3,4 while(true) think( ); P(forki); P(fork(i+1)%5); eat( ); V(forki); V(fork(i+1)%5); coend,53,上述解法可能出現(xiàn)永遠(yuǎn)等待，有若干種辦法可避免死鎖： （1）至多允許四個(gè)哲學(xué)家同時(shí)吃； （2）奇數(shù)號(hào)先取左手邊的叉子，偶數(shù)號(hào)先 取右手邊的叉子； （3）每個(gè)哲學(xué)家取到手邊的兩把叉子才

27、吃，否則一把叉子也不取。,54,3.4 進(jìn)程通信,進(jìn)程通信(Interprocess Communication,IPC)是指進(jìn)程之間的信息交換。 信號(hào)量及P.V操作實(shí)現(xiàn)的是進(jìn)程之間的低級(jí)通訊，所以P.V為低級(jí)通訊原語(yǔ)。它只能傳遞簡(jiǎn)單的信號(hào)，不能傳遞交換大量信息。 本節(jié)介紹高級(jí)進(jìn)程通信，是指進(jìn)程間高效的傳送大量數(shù)據(jù)的通信方式。,55,進(jìn)程間通信的方式,信號(hào)(signal)通信機(jī)制 管道(pipeline)通信機(jī)制 消息傳遞(message passing)通信機(jī)制 信號(hào)量(semaphore)通信機(jī)制 共享主存(shared memory)通信機(jī)制 前兩種是UNIX最早的版本就提供的進(jìn)程通信機(jī)

28、制。信號(hào)通信機(jī)制只能發(fā)送單個(gè)信號(hào)而不能傳遞數(shù)據(jù)；管道通信雖能傳送數(shù)據(jù)，卻只能在進(jìn)程家族內(nèi)使用，應(yīng)用范圍有限。,56,進(jìn)程通信方式發(fā)展,UNIX發(fā)展歷史中，AT&T的Bell與加大伯克利的BSD是兩大主力。 Bell致力于改進(jìn)傳統(tǒng)的進(jìn)程IPC，形成了SYSTEM IPC機(jī)制（上述后三種通信機(jī)制）。 BSD在改進(jìn)IPC的同時(shí)，把網(wǎng)絡(luò)通信規(guī)程(TCP/IP)實(shí)現(xiàn)到UNIX內(nèi)核中，考慮把同一計(jì)算機(jī)上的進(jìn)程通信納入更廣的網(wǎng)絡(luò)范圍的進(jìn)程間通信，這種努力結(jié)果出現(xiàn)了socket網(wǎng)絡(luò)通信機(jī)制。,57,一、管道通信機(jī)制,管道通信是UNIX的傳統(tǒng)進(jìn)程通信方式，也是UNIX發(fā)展最有意義的貢獻(xiàn)之一。 所謂管道，是指用于

29、連接一個(gè)讀進(jìn)程和一個(gè)寫(xiě)進(jìn)程的特殊文件，稱pipe文件。 發(fā)送進(jìn)程以字符流形式把大量數(shù)據(jù)送入管道，接收進(jìn)程從管道中接收數(shù)據(jù)，所以叫管道通信。,58,管道的實(shí)質(zhì)是一個(gè)共享文件，基本上可借助于文件系統(tǒng)的機(jī)制實(shí)現(xiàn)，包括（管道）文件的創(chuàng)建、打開(kāi)、關(guān)閉和讀寫(xiě)。 但寫(xiě)進(jìn)程和讀進(jìn)程間的相互協(xié)調(diào)單靠文件系統(tǒng)機(jī)制解決不了，讀寫(xiě)進(jìn)程相互同步，必須做到以下幾點(diǎn)： （1）互斥，即一個(gè)進(jìn)程正在使用某個(gè)管道寫(xiě)入或讀出數(shù)據(jù)時(shí)，另一個(gè)進(jìn)程就必須等待； （2）發(fā)送者和接收者雙方必須能夠知道對(duì)方是否存在，如果對(duì)方已經(jīng)不存在，就沒(méi)有必要再發(fā)送信息。 （3）同步，指當(dāng)寫(xiě)進(jìn)程把一定量的數(shù)據(jù)發(fā)送后，便睡眠等待，直到讀進(jìn)程把管道中數(shù)據(jù)取走后，在把它喚醒。反之當(dāng)讀進(jìn)程讀空管道時(shí)，也被阻塞，直到寫(xiě)進(jìn)程將數(shù)據(jù)寫(xiě)入管道后，才將它喚醒。,59,二、共享主存通信機(jī)制,在主存中開(kāi)辟一個(gè)公用存儲(chǔ)區(qū)，要通信的進(jìn)程把自己的虛地址空