進程的同步課件

1、2.1 2.1 進程的概念進程的概念2.2 2.2 進程控制進程控制2.3 2.3 進程同步進程同步2.4 2.4 進程通信進程通信2.5 2.5 線程線程第2章 進程管理進程的同步PPT課件2.3進程的同步進程的同步進程的引入雖然改善了系統(tǒng)的資源利用率和提高了系統(tǒng)的吞吐量，但是進程的異步性，特別是它們在爭用臨界資源時，會給系統(tǒng)造成一定的混亂。為了解決這個問題，提出了進程同步的概念。程序（間）并發(fā)執(zhí)行的特征： 程序運行時獨占資源進程的同步 進程同步問題的提出進程異步推進可能造成混亂混亂可能導(dǎo)致不可再現(xiàn) 進程同步目標(biāo) 進程間的兩種主要關(guān)系進程間的關(guān)系與進程間的獨立性進程間的關(guān)系是在進程間相對獨立

2、的前提下發(fā)展的獨立獲得資源獨立調(diào)度進程間的同步關(guān)系（一）進程間的同步關(guān)系（二）進程間的同步關(guān)系（三）進程間的同步關(guān)系兩種形式的制約關(guān)系 間接相互制約關(guān)系 -源于資源共享,產(chǎn)生互斥問題 直接相互制約關(guān)系 -源于進程間合作,產(chǎn)生同步問題同步實現(xiàn)初探（二）同步實現(xiàn)初探（三）進程間的同步關(guān)系 進程同步時面臨的兩種主要關(guān)系司機與售票員司機與售票員多個打印者多個打印者計算者與打印者計算者與打印者2.3.1同步的概念同步的概念總結(jié)：兩種制約關(guān)系1資源共享資源共享(進程互斥、進程間的間接相互制約）進程互斥、進程間的間接相互制約）2相互協(xié)作（進程同步、直接相互制約）相互協(xié)作（進程同步、直接相互制約）進程同步的任

3、務(wù)進程同步的任務(wù)保證各進程能互斥地訪問這些資源（有效地共享資源）。保證協(xié)作進程或線程的順序執(zhí)行，使它們不會出現(xiàn)與時間有關(guān)的差錯，對數(shù)據(jù)的一致性進行維護（有效地相互合作）。臨界資源臨界資源 臨界資源：臨界資源：在一段時間內(nèi)只允許一在一段時間內(nèi)只允許一個進程訪問的資源個進程訪問的資源 對臨界資源的訪問必須采用互斥的對臨界資源的訪問必須采用互斥的方式進行，以實現(xiàn)對資源的共享。方式進行，以實現(xiàn)對資源的共享。程 序 段1程 序 段2程 序 段n共 享 變量 怎樣才能保證并發(fā)執(zhí)行結(jié)果的正確性呢？ 如果我們把兩個進程中使用公共變量有關(guān)的語句，各自都抽象為一個順序的執(zhí)行單位，也就是說，保證任何一個進程即使運行

4、到其中這些語句時被打斷，在它下一次被調(diào)度到而繼續(xù)執(zhí)行直到退出這些語句之前，另一個進程不允許進入使用公共變量的語句執(zhí)行，也就一定能保證那些語句總能被順序地執(zhí)行，顯然其執(zhí)行結(jié)果也一定是正確的2.3.1.3臨界區(qū)問題臨界區(qū)問題 臨界區(qū)的概念：將多個進程訪問臨界資源的那一段程序代碼稱為臨界區(qū)。在臨界區(qū)中，進程能改變變量的值，更新數(shù)據(jù)表或?qū)懳募取Ｏ到y(tǒng)只允許一個進程在臨界區(qū)執(zhí)行，而不允許其它進程進入臨界區(qū)。解決臨界區(qū)問題必須遵循的原則：1.當(dāng)某一時刻沒有進程處于臨界區(qū)內(nèi)時，相應(yīng)的臨界資源處于空閑狀態(tài)。因而可允許一個請求進入臨界區(qū)進程立即進入臨界區(qū)，以有效地利用臨界資源。2.如果此時已有進程進入臨界區(qū)，則

5、其它試圖進入臨界區(qū)的進程必須等待，以保證各進程互斥地訪問臨界資源。3.當(dāng)某個進程申請進入臨界區(qū)時，它應(yīng)在有限時間內(nèi)獲得系統(tǒng)的響應(yīng)，而能夠進入臨界區(qū)，以免進程陷入無限等待狀態(tài)。4.當(dāng)進程不能進入臨界區(qū)時，應(yīng)立即釋放處理機，以免進程陷入忙等待狀態(tài)。 1 空閑讓進；2 忙則等待；3 讓權(quán)等待；4 有限等待；臨界區(qū)臨界區(qū)2.3.2同步的實現(xiàn)同步的實現(xiàn)解決臨界區(qū)問題可以用軟件或硬件實現(xiàn)。使用硬件實現(xiàn)進程的同步，可以使用戶的編程任務(wù)更容易且系統(tǒng)的效率更高。1關(guān)中斷關(guān)中斷使用關(guān)中斷解決單處理器環(huán)境下臨界區(qū)的問題。使用關(guān)中斷不能解決多處理器環(huán)境下臨界區(qū)的問題。關(guān)閉中斷將延誤處理器的處理時間，使系統(tǒng)性能下降。鎖

6、機制 臨界資源鎖機制例：商場的試衣間是互斥資源是臨界資源是共享資源每個顧客必須遵循以下過程使用試衣間：鎖機制 臨界資源鎖機制鎖機制實現(xiàn) 一種簡單的鎖操作實現(xiàn)鎖機制實現(xiàn)鎖操作模型 鎖操作的一般模型出了問題的鎖鎖機制實現(xiàn) 關(guān)鎖操作不可被打斷用原語實現(xiàn)關(guān)鎖操作關(guān)鎖操作在一個指令周期內(nèi)完成 鎖操作的特點：實現(xiàn)了進程互斥訪問臨界資源。不遵循讓權(quán)等待原則。忙等信號量機制 信號量機制：由Dijkstra提出的一種解決進程的同步與互斥的工具： 信號量信號量用于表示用于表示資源數(shù)目資源數(shù)目或或請求使用請求使用某一資源的進程個數(shù)某一資源的進程個數(shù)的整型量的整型量. S是與臨界區(qū)內(nèi)所使用的共享資源有關(guān)的信是與臨界區(qū)

7、內(nèi)所使用的共享資源有關(guān)的信號量。號量。 S0 可供并發(fā)進程使用的資源數(shù)可供并發(fā)進程使用的資源數(shù) S0 正在等待使用臨界區(qū)的進程數(shù)正在等待使用臨界區(qū)的進程數(shù)P原語操作和V原語操作 P原語操作的主要動作S1如果S1以后仍大于等于零，則進程繼續(xù)進行如果S1以后小于零，則將該進程阻塞以后插入阻塞隊列，然后轉(zhuǎn)進程調(diào)度 V原語操作的主要動作S1如果相加后結(jié)果大于零，則繼續(xù)進行相加后結(jié)果小于等于零，則從該信號的等待隊列中喚醒一個等待進程，然后返回原進程繼續(xù)執(zhí)行或者轉(zhuǎn)進程調(diào)度。入口s=s-1s0調(diào)度進程入等待隊列轉(zhuǎn)進程調(diào)度入口s=s1s0喚醒等待隊列中的一個進程返回或轉(zhuǎn)進程調(diào)度返回返回s.否value=0)繼

8、續(xù)執(zhí)行；else阻塞并進入等待隊列；V操作V（S）S=S+1;if(S0)繼續(xù)運行；else喚醒等待隊列中的一個進程，并繼續(xù)運行；信號量：PV操作記錄型的信號量機制 是一個記錄型的數(shù)據(jù)結(jié)構(gòu)，包含兩個數(shù)據(jù)項，一是計數(shù)值域，另一是等待該信號量的進程隊列首指針域。描述如下： typedef struct semaphore int value; PCB *p; semaphore；記錄型信號量的P，V操作P(s)和V(s)操作原語voidP(s)structsemaphores;s.value=s.value-1;if(s.value0)block(s.p);2.3.2 信號量機制 AND型信號量（

9、只需了解）引入原因:一個進程需要先獲得兩個或更多的資源后,方能執(zhí)行其任務(wù). 基本思想將對多個信號量的逐個申請改為一次，用一個原子操作完成進程要么一次獲得所有的資源，要么一個也申請不到不會存在互相等待的局面信號量集（了解） 引入原因:在記錄型信號量中每次對僅能施以加或減操作，即每次只能獲得或釋放一個單位的臨界資源 一次需要個某類臨界資源時 資源數(shù)量低于某一下限值時，便不予分配 可對信號量機制加以擴充，形成一般化的“信號量集”機制公用與私用信號量2.3.3 信號量的應(yīng)用 .利用信號量實現(xiàn)進程互斥例1：n個并發(fā)進程共用一個公用變量Q，寫出信號量實現(xiàn)n個進程互斥時的程序描述，并說明信號量的取值范圍。

10、2.利用信號量實現(xiàn)前驅(qū)關(guān)系設(shè)有個并發(fā)執(zhí)行的進程：P1: s1 ; P2: s2為了實現(xiàn)前驅(qū)關(guān)系S1 S2 ，可使他們共享一個公用信號量，初值為 P1 : S1; V(s) ; P2: P(s) ; S2 ;利用信號量解決前驅(qū)圖問題 例如：PA、PB、PC為一組合作的進程，其流程如圖所示，使用信號量實現(xiàn)三個進程的同步。ACB 例如：PA、PB、PC為一組合作的進程，其流程如圖所示，使用信號量實現(xiàn)三個進程的同步。 設(shè)兩個同步信號燈SB、SC分別表示進程和能夠開始 執(zhí)行，其初值均為0（ SB=0 ，SC=0）。ACBSB =0;SC =0;BeginPA : Begin V(SB) V(SC ) E

11、nd;EndProgram;利用信號量來描述前趨圖關(guān)系S1S3S2S4S5S6S7S8具有具有8個結(jié)點的前趨圖。圖中的前趨圖個結(jié)點的前趨圖。圖中的前趨圖中共有有向邊中共有有向邊10條，可設(shè)條，可設(shè)10個信號量，個信號量，初值均為初值均為0；有；有8個結(jié)點，可設(shè)計成個結(jié)點，可設(shè)計成8個個并發(fā)進程，具體描述如下：并發(fā)進程，具體描述如下：S1S3S2S4S5S6S7S8agefbcdhijStruct smaphore a,b,c,d,e,f,g,h,I,j=0,0,0,0,0,0,0,0,0,0cobegin S1;V(a);V(b);V(c); P(a);S2;V(d); P(b);S3;V(e

12、);V(f); P(c);S4;V(g); P(d);P(e);S5;V(h); P(f);P(g);S6;V(i) P(h);P(i);S7;V(j); P(j);S8;coendS1S3S2S4S5S6S7S8agefbcdhij用信號量解題的關(guān)鍵 步驟： 信號量的設(shè)置； 給信號量賦初值（常用的互斥和同步信號量值的大?。?； P、V操作安排的位置（其中，P的順序不能顛倒）練習(xí)ACBDE3.利用信號量實現(xiàn)進程同步： 例例2：已知一個求值公式（：已知一個求值公式（A2+3B）/(B+5A),若若A,B已賦值，試畫出該公式求已賦值，試畫出該公式求值過程的前趨圖。值過程的前趨圖。 解：在該公式的求值過程中，有些運算解：在該公式的求值過程中，有些運算分量的執(zhí)行是可以并發(fā)執(zhí)行的。為了描分量的執(zhí)行是可以并發(fā)執(zhí)行的。為了描述方便，可設(shè)置一些中間變量保存中間述方便，可設(shè)置一