第2章進程同步與通信-1

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

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

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

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

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

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

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

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

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

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

11、道 樓宇 1小區(qū)A小區(qū) B城市公路進程第二章進 程 管 理 信號量l信號量是一種數據結構l信號量的值與相應資源的使用情況有關l 信號量的值僅由P、V操作改變第二章進 程 管 理 1、整型信號量 整型數SP操作（wait）原語V操作（signal）原語第二章進 程 管 理 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表示資源數目，是個整型量。第二章進 程 管 理 waitwait（s s）和）和signalsignal（S S）是原子操作。是原子操作。 只要信號量

12、只要信號量S0S0就不斷測就不斷測試，不滿足讓權等待。試，不滿足讓權等待。第二章進 程 管 理 2、記錄型信號量、記錄型信號量 記錄型結構，包含兩個數據項： 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、二章進 程 管 理 lS.value為資源信號量，其初值為某類資源為資源信號量，其初值為某類資源的數目。的數目。lS.value0S.value0：表示系統中可用的資源數量：表示系統中可用的資源數量lS.value0S.value0：其絕對值表示已阻塞的進程數：其絕對值表示已阻塞的進程數量。（等待使用資源的進程個數）量。（等待使用資源的進程個數）lS.valueS.value初值為初值為1 1時：只允許一個進程訪問時：只允許一個進程訪問臨界資源，是互斥信號量。臨界資源，是互斥信號量。第二章進 程 管 理 上述的進程互斥問題，是針對各進程之間只共享一個臨界資源而言的。在有些應用場合，是一個進程需

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