第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、信號(hào)量和、信號(hào)量和P P、V V操作操作ANDAND信號(hào)量信號(hào)量2.52.5、經(jīng)典進(jìn)程同步與互斥問(wèn)題、經(jīng)典進(jìn)程同步與互斥問(wè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í)行時(shí)，由于資源共享和進(jìn)程合作，使同處于一個(gè)系統(tǒng)中的諸進(jìn)程之間可能存在著以下兩種形式的制約關(guān)系：第二章進(jìn) 程 管 理 互斥：互斥： 互斥是并發(fā)執(zhí)行的多個(gè)進(jìn)程由于競(jìng)爭(zhēng)同一資源而產(chǎn)生的相互排斥的關(guān)系。同步：同步： 同步是進(jìn)程間共同完成一項(xiàng)任務(wù)時(shí)直接發(fā)生相互作用的關(guān)系。 進(jìn)程的兩大關(guān)系進(jìn)程的兩大關(guān)系第二章進(jìn) 程 管 理 同步進(jìn)程間具有合作關(guān)系 在執(zhí)行時(shí)間上必須按一定的順序協(xié)調(diào)進(jìn)行。 臨界資源：一次僅允許一個(gè)進(jìn)程使用的共享資源。 如：打印機(jī)、磁帶機(jī)、表格。第二章進(jìn) 程 管 理 2、臨界資源3、臨界區(qū)在每個(gè)

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

4、的標(biāo)志。 剩余區(qū)：剩余區(qū)：進(jìn)程中除上述進(jìn)入?yún)^(qū)、臨界區(qū)及退出區(qū)之外的其它部分的代碼，在這里都稱(chēng)為剩余區(qū)。第二章進(jìn) 程 管 理 這樣，可把一個(gè)訪問(wè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)無(wú)進(jìn)程處于臨界區(qū)時(shí)，表明臨界資源處于空閑狀態(tài)臨界資源處于空閑狀態(tài)，應(yīng)允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。(2) 忙則等待忙則等待當(dāng)已有進(jìn)程進(jìn)入臨

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

6、進(jìn) 程 管 理 禁止中斷（中斷屏蔽方法）禁止中斷（中斷屏蔽方法） 當(dāng)一個(gè)進(jìn)程正在使用處理機(jī)執(zhí)行它的臨界區(qū)代碼時(shí)，要防止其他進(jìn)程再進(jìn)入其臨界區(qū)訪問(wèn)的最簡(jiǎn)單方法是禁止一切中斷發(fā)生，或稱(chēng)之為屏蔽中斷、關(guān)中斷。其典型模式為：.關(guān)中斷;臨界區(qū);開(kāi)中斷;/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時(shí)，表示資源空閑時(shí)，表示資源空閑; ;當(dāng)當(dāng)lock=truelock=true時(shí)，表示資源正在被使用。時(shí)，表

7、示資源正在被使用。缺點(diǎn)：沒(méi)有做到：缺點(diǎn)：沒(méi)有做到：“讓權(quán)等待讓權(quán)等待”( (當(dāng)進(jìn)程不能進(jìn)入自不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”狀態(tài)。 ) )/TS指令的使用while TS (&lock);臨界區(qū);lock=false;剩余區(qū)；TS（Test and Set）指令互斥實(shí)現(xiàn)的軟件方法互斥實(shí)現(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)程編號(hào)i(i=0,1)。使P0、P1輪流訪問(wèn)臨界資源。缺點(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í)設(shè)每個(gè)元素為false,表示所有進(jìn)程都未進(jìn)入臨界區(qū)。若flagi=true,表示進(jìn)程進(jìn)入臨界區(qū)執(zhí)行。在每個(gè)進(jìn)程進(jìn)入臨界區(qū)時(shí)，先查看臨界資源是否被使用，若正在使用，該進(jìn)程等待，否則才可進(jìn)入。解決了

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

10、軟件方法解決互斥問(wèn)題/進(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ū);先修改、后檢查、后修改算法先修改、后檢查、后修改算法用軟件方法解決互斥問(wèn)題用軟件方法解決互斥問(wèn)題第二章進(jìn) 程 管 理 2.4.3 2.4.3 信號(hào)量機(jī)制信號(hào)量機(jī)制信號(hào)量和信號(hào)量和P P、V V操作操作中心街

11、道 樓宇 1小區(qū)A小區(qū) B城市公路進(jìn)程第二章進(jìn) 程 管 理 信號(hào)量l信號(hào)量是一種數(shù)據(jù)結(jié)構(gòu)l信號(hào)量的值與相應(yīng)資源的使用情況有關(guān)l 信號(hào)量的值僅由P、V操作改變第二章進(jìn) 程 管 理 1、整型信號(hào)量 整型數(shù)SP操作（wait）原語(yǔ)V操作（signal）原語(yǔ)第二章進(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ù)目，是個(gè)整型量。第二章進(jìn) 程 管 理 waitwait（s s）和）和signalsignal（S S）是原子操作。是原子操作。 只要信號(hào)量

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

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

14、要先獲得兩個(gè)或更多的共享資源后方能執(zhí)行其任務(wù)。假定現(xiàn)有兩個(gè)進(jìn)程A和B，他們都要求訪問(wèn)共享數(shù)據(jù)D和E。當(dāng)然，共享數(shù)據(jù)都應(yīng)作為臨界資源。為此，可為這兩個(gè)數(shù)據(jù)分別設(shè)置用于互斥的信號(hào)量Dmutex和Emutex，并令它們的初值都是1。相應(yīng)地，在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)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)。在無(wú)外力作用下，兩者都將無(wú)法從僵持狀態(tài)中解脫出來(lái)。我們稱(chēng)此時(shí)的進(jìn)程A和B已進(jìn)入死鎖狀態(tài)。顯然，當(dāng)進(jìn)程同時(shí)要求的共享資源愈多時(shí)，發(fā)生進(jìn)程死鎖的可能性也就愈大。 第二章進(jìn) 程 管 理 3、AND型信號(hào)量基本思想：將進(jìn)程在整個(gè)運(yùn)行中需要的所基本思想：將進(jìn)程在整個(gè)運(yùn)行中需要的所有資源，一次性全部分配給進(jìn)程，待進(jìn)程有資源，一次性全部分配給進(jìn)程，待進(jìn)程使用完后一起釋放。使用完后一起釋放。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。第二章進(jìn) 程 管 理 在在wait中加入中加入AND條件，又稱(chēng)條件，又稱(chēng)AND同步或同同步或同時(shí)時(shí)wait操作。操作。 Swait(Simultaneous wait) Swait(S1，S2，Sn)While(TRUE) if (S11 &Sn1)for(i=1;i