第2章進(jìn)程同步與通信-1

1、第二章進(jìn) 程 管 理 第二章進(jìn)程的描述與控制 2.4 2.4 進(jìn)程同步與互斥進(jìn)程同步與互斥1 1、進(jìn)程同步與互斥、進(jìn)程同步與互斥 2 2、信號量和、信號量和P P、V V操作操作ANDAND信號量信號量2.52.5、經(jīng)典進(jìn)程同步與互斥問題、經(jīng)典進(jìn)程同步與互斥問題2.62.6、 進(jìn)程通信進(jìn)程通信 第二章進(jìn) 程 管 理 2.4.1 進(jìn)程同步的基本概念進(jìn)程同步的基本概念 間接制約間接制約: :進(jìn)程間由于共享某種系統(tǒng)資源，而形成的相進(jìn)程間由于共享某種系統(tǒng)資源，而形成的相互制約?；ブ萍s。 直接制約：直接制約： 進(jìn)程間由于合作進(jìn)程間由于合作而形成的相互制約而形成的相互制約。進(jìn)程進(jìn)程B B 資源資源進(jìn)程進(jìn)程

2、A進(jìn)程進(jìn)程A進(jìn)程進(jìn)程B B1、進(jìn)程的兩種制約關(guān)系、進(jìn)程的兩種制約關(guān)系 在多道程序環(huán)境下，當(dāng)程序并發(fā)執(zhí)行時，由于資源共享和進(jìn)程合作，使同處于一個系統(tǒng)中的諸進(jìn)程之間可能存在著以下兩種形式的制約關(guān)系：第二章進(jìn) 程 管 理 互斥：互斥： 互斥是并發(fā)執(zhí)行的多個進(jìn)程由于競爭同一資源而產(chǎn)生的相互排斥的關(guān)系。同步：同步： 同步是進(jìn)程間共同完成一項任務(wù)時直接發(fā)生相互作用的關(guān)系。 進(jìn)程的兩大關(guān)系進(jìn)程的兩大關(guān)系第二章進(jìn) 程 管 理 同步進(jìn)程間具有合作關(guān)系 在執(zhí)行時間上必須按一定的順序協(xié)調(diào)進(jìn)行。 臨界資源：一次僅允許一個進(jìn)程使用的共享資源。 如：打印機(jī)、磁帶機(jī)、表格。第二章進(jìn) 程 管 理 2、臨界資源3、臨界區(qū)在每個

3、進(jìn)程中訪問臨界資源的那段程序。 進(jìn)程必須互斥進(jìn)入臨界區(qū)第二章進(jìn) 程 管 理 訪問臨界區(qū)的循環(huán)進(jìn)程描述訪問臨界區(qū)的循環(huán)進(jìn)程描述repeat進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)臨界區(qū)臨界區(qū)退出區(qū)退出區(qū)剩余區(qū)剩余區(qū)檢查臨界資源是否能訪問將臨界區(qū)標(biāo)志設(shè)為未訪問 until false;第二章進(jìn) 程 管 理 進(jìn)入?yún)^(qū)：進(jìn)入?yún)^(qū)：每個進(jìn)程在進(jìn)入臨界區(qū)之前，應(yīng)先對欲訪問的臨界資源進(jìn)行檢查，看它是否正被訪問。如果此刻該臨界資源未被訪問，進(jìn)程便可進(jìn)入臨界區(qū)對該資源進(jìn)行訪問，并設(shè)置它正被訪問的標(biāo)志它正被訪問的標(biāo)志； 退出區(qū)：退出區(qū)：在臨界區(qū)后面也要加上一段稱為退出區(qū)(exit section)的代碼，用于將臨界區(qū)正被訪問的標(biāo)志恢復(fù)為未被訪問

4、的標(biāo)志。 剩余區(qū)：剩余區(qū)：進(jìn)程中除上述進(jìn)入?yún)^(qū)、臨界區(qū)及退出區(qū)之外的其它部分的代碼，在這里都稱為剩余區(qū)。第二章進(jìn) 程 管 理 這樣，可把一個訪問臨界資源的循環(huán)進(jìn)程描述如下：repeatentry sectioncritical section；exit sectionremainder section；until false； 第二章進(jìn) 程 管 理 4、同步機(jī)制遵循的原則、同步機(jī)制遵循的原則 (1) 空閑讓進(jìn)空閑讓進(jìn)當(dāng)無進(jìn)程處于臨界區(qū)時，表明臨界資源處于空閑狀態(tài)臨界資源處于空閑狀態(tài)，應(yīng)允許一個請求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。(2) 忙則等待忙則等待當(dāng)已有進(jìn)程進(jìn)入臨

5、界區(qū)時已有進(jìn)程進(jìn)入臨界區(qū)時，表明臨界資源正在被訪問，因而其它其它試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待進(jìn)程必須等待，以保證對臨界資源的互斥訪問。 第二章進(jìn) 程 管 理 (3) 有限等待有限等待對要求訪問臨界資源的進(jìn)程，應(yīng)保證在有限時間內(nèi)能進(jìn)入自己有限時間內(nèi)能進(jìn)入自己的臨界區(qū)的臨界區(qū)，以免陷入“死等”狀態(tài)。(4) 讓權(quán)等待讓權(quán)等待當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時，應(yīng)立即釋放處理機(jī)不能進(jìn)入自己的臨界區(qū)時，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”狀態(tài)。 互斥的實現(xiàn)方法互斥的實現(xiàn)方法禁止中斷專用機(jī)器指令TS（Test and Set）指令 Swap指令（1）硬件方法）硬件方法2.4.2 硬件同步機(jī)制硬件同步機(jī)制第二章

6、進(jìn) 程 管 理 禁止中斷（中斷屏蔽方法）禁止中斷（中斷屏蔽方法） 當(dāng)一個進(jìn)程正在使用處理機(jī)執(zhí)行它的臨界區(qū)代碼時，要防止其他進(jìn)程再進(jìn)入其臨界區(qū)訪問的最簡單方法是禁止一切中斷發(fā)生，或稱之為屏蔽中斷、關(guān)中斷。其典型模式為：.關(guān)中斷;臨界區(qū);開中斷;/TS指令：boolean TS(boolean *lock) boolean temp; temp = *lock; *lock=true; return temp;LockLock有兩種狀態(tài)有兩種狀態(tài)：當(dāng)當(dāng)lock=falselock=false時，表示資源空閑時，表示資源空閑; ;當(dāng)當(dāng)lock=truelock=true時，表示資源正在被使用。時，表

7、示資源正在被使用。缺點(diǎn)：沒有做到：缺點(diǎn)：沒有做到：“讓權(quán)等待讓權(quán)等待”( (當(dāng)進(jìn)程不能進(jìn)入自不能進(jìn)入自己的臨界區(qū)時，應(yīng)立即釋放處理機(jī)己的臨界區(qū)時，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”狀態(tài)。 ) )/TS指令的使用while TS (&lock);臨界區(qū);lock=false;剩余區(qū)；TS（Test and Set）指令互斥實現(xiàn)的軟件方法互斥實現(xiàn)的軟件方法/進(jìn)程進(jìn)程0while (turn!=0) /什么都不做;臨界區(qū);turn = 1;剩余區(qū); /進(jìn)程進(jìn)程1while (turn!=1) do/什么都不做;臨界區(qū);turn = 0;剩余區(qū);設(shè)置公共整型變量turn，用于指示進(jìn)入臨界區(qū)

8、的進(jìn)程編號i(i=0,1)。使P0、P1輪流訪問臨界資源。缺點(diǎn)：強(qiáng)制性輪流進(jìn)入臨界區(qū)，不能保證“空閑讓進(jìn)空閑讓進(jìn)”。1、單標(biāo)志算單標(biāo)志算法法/進(jìn)程進(jìn)程0 while (flag1)/什么都不做 ;flag0=true;臨界區(qū);flag0 =false;剩余區(qū);/進(jìn)程進(jìn)程1while ( flag0) /什么都不做 ;flag1=true;臨界區(qū);flag1 =false;剩余區(qū);設(shè)置數(shù)組flag，初始時設(shè)每個元素為false,表示所有進(jìn)程都未進(jìn)入臨界區(qū)。若flagi=true,表示進(jìn)程進(jìn)入臨界區(qū)執(zhí)行。在每個進(jìn)程進(jìn)入臨界區(qū)時，先查看臨界資源是否被使用，若正在使用，該進(jìn)程等待，否則才可進(jìn)入。解決了

9、“空閑讓進(jìn)”問題。缺點(diǎn)：可能同時進(jìn)入臨界區(qū)，不能保證“忙則等忙則等待待”。用軟件方法解決互斥問題用軟件方法解決互斥問題2、雙標(biāo)志、先檢查雙標(biāo)志、先檢查算法算法/進(jìn)程進(jìn)程0flag0=true;while (flag1)/什么也不做;臨界區(qū);flag0 =false;剩余區(qū);兩進(jìn)程先后同時作flagi=true;缺點(diǎn)：保證了不同時進(jìn)入臨界區(qū)，但又又可能都進(jìn)不去可能都進(jìn)不去。不能保證“有空讓進(jìn)有空讓進(jìn)”。/進(jìn)程進(jìn)程1flag1=true;while (flag0)/什么也不做;臨界區(qū);flag1 =false ; 剩余區(qū);3、雙標(biāo)志、先修改后檢查雙標(biāo)志、先修改后檢查算法算法用軟件方法解決互斥問題用

10、軟件方法解決互斥問題/進(jìn)程進(jìn)程0flag0=true;turn=1;while (flag1) & (turn=1)/什么也不做;臨界區(qū);flag0 =false ;剩余區(qū);保證了“有空讓進(jìn)有空讓進(jìn)”和“忙則等忙則等待待”。/進(jìn)程進(jìn)程1flag1=true;turn=0;while (flag0) & (turn=0)/什么也不做;臨界區(qū);flag1 =false ;剩余區(qū);先修改、后檢查、后修改算法先修改、后檢查、后修改算法用軟件方法解決互斥問題用軟件方法解決互斥問題第二章進(jìn) 程 管 理 2.4.3 2.4.3 信號量機(jī)制信號量機(jī)制信號量和信號量和P P、V V操作操作中心街

11、道 樓宇 1小區(qū)A小區(qū) B城市公路進(jìn)程第二章進(jìn) 程 管 理 信號量l信號量是一種數(shù)據(jù)結(jié)構(gòu)l信號量的值與相應(yīng)資源的使用情況有關(guān)l 信號量的值僅由P、V操作改變第二章進(jìn) 程 管 理 1、整型信號量 整型數(shù)SP操作（wait）原語V操作（signal）原語第二章進(jìn) 程 管 理 l Wait（S）: while （S00）；）；/ do no-op/ do no-op S:=S-1; S:=S-1;l Signal（S）: S:=S+1;S:=S+1;S表示資源數(shù)目，是個整型量。第二章進(jìn) 程 管 理 waitwait（s s）和）和signalsignal（S S）是原子操作。是原子操作。 只要信號量

12、只要信號量S0S0就不斷測就不斷測試，不滿足讓權(quán)等待。試，不滿足讓權(quán)等待。第二章進(jìn) 程 管 理 2、記錄型信號量、記錄型信號量 記錄型結(jié)構(gòu)，包含兩個數(shù)據(jù)項： typedef structint value;Struct process_control_block *list;semaphore;ValueLSwait操作：申請一個單位資源操作：申請一個單位資源 wait(semaphore *S)S-value-;if(S-valuelist);signal操作：釋放一個單位資源操作：釋放一個單位資源signal(semaphore *S)S-value+；if(S-valuelist); 第

13、二章進(jìn) 程 管 理 lS.value為資源信號量，其初值為某類資源為資源信號量，其初值為某類資源的數(shù)目。的數(shù)目。lS.value0S.value0：表示系統(tǒng)中可用的資源數(shù)量：表示系統(tǒng)中可用的資源數(shù)量lS.value0S.value0：其絕對值表示已阻塞的進(jìn)程數(shù)：其絕對值表示已阻塞的進(jìn)程數(shù)量。（等待使用資源的進(jìn)程個數(shù)）量。（等待使用資源的進(jìn)程個數(shù)）lS.valueS.value初值為初值為1 1時：只允許一個進(jìn)程訪問時：只允許一個進(jìn)程訪問臨界資源，是互斥信號量。臨界資源，是互斥信號量。第二章進(jìn) 程 管 理 上述的進(jìn)程互斥問題，是針對各進(jìn)程之間只共享一個臨界資源而言的。在有些應(yīng)用場合，是一個進(jìn)程需

14、要先獲得兩個或更多的共享資源后方能執(zhí)行其任務(wù)。假定現(xiàn)有兩個進(jìn)程A和B，他們都要求訪問共享數(shù)據(jù)D和E。當(dāng)然，共享數(shù)據(jù)都應(yīng)作為臨界資源。為此，可為這兩個數(shù)據(jù)分別設(shè)置用于互斥的信號量Dmutex和Emutex，并令它們的初值都是1。相應(yīng)地，在兩個進(jìn)程中都要包含兩個對Dmutex和Emutex的操作，即 process A:process B:wait(Dmutex)；wait(Emutex)；wait(Emutex)；wait(Dmutex)； 第二章進(jìn) 程 管 理 若進(jìn)程A和B按下述次序交替執(zhí)行wait操作：process A: wait(Dmutex)； 于是Dmutex=0process B:

15、 wait(Emutex)； 于是Emutex=0process A: wait(Emutex)； 于是Emutex=-1 A阻塞process B: wait(Dmutex)； 于是Dmutex=-1 B阻塞 最后，進(jìn)程A和B處于僵持狀態(tài)。在無外力作用下，兩者都將無法從僵持狀態(tài)中解脫出來。我們稱此時的進(jìn)程A和B已進(jìn)入死鎖狀態(tài)。顯然，當(dāng)進(jìn)程同時要求的共享資源愈多時，發(fā)生進(jìn)程死鎖的可能性也就愈大。 第二章進(jìn) 程 管 理 3、AND型信號量基本思想：將進(jìn)程在整個運(yùn)行中需要的所基本思想：將進(jìn)程在整個運(yùn)行中需要的所有資源，一次性全部分配給進(jìn)程，待進(jìn)程有資源，一次性全部分配給進(jìn)程，待進(jìn)程使用完后一起釋放。使用完后一起釋放。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。第二章進(jìn) 程 管 理 在在wait中加入中加入AND條件，又稱條件，又稱AND同步或同同步或同時時wait操作。操作。 Swait(Simultaneous wait) Swait(S1，S2，Sn)While(TRUE) if (S11 &Sn1)for(i=1;i