進程同步第三章

第三章進程的同步與通信3.1進程的同步3.2進程通信3.1進程的同步3.1.1臨界區(qū)3.1.2利用硬件的方法解決進程互斥問題—互斥的加鎖實現(xiàn)3.1.3信號量機制進程同步的主要任務(wù)：使并發(fā)執(zhí)行的諸進程之間能有效地共享資源和相互合作，從而使程序的并發(fā)執(zhí)行具有可再現(xiàn)性。3.1.1臨界區(qū)一、臨界區(qū)1.臨界資源：2.臨界區(qū)：3.1進程的同步一次僅允許一個進程訪問的資源例：進程PA、PB共享內(nèi)存MS。其中MS分為三個領(lǐng)域，即系統(tǒng)區(qū)、進程工作區(qū)和數(shù)據(jù)區(qū)。數(shù)據(jù)區(qū)被劃分為大小相等的塊，每個塊中既可能被放有數(shù)據(jù)，也可能未放有數(shù)據(jù)。系統(tǒng)區(qū)中主要是堆棧S，其中存放那些空數(shù)據(jù)塊的地址。分析其中的臨界資源、臨界區(qū)。訪問臨界資源的代碼段，不允許多個并發(fā)進程交叉執(zhí)行的一段程序二、進程間的制約關(guān)系

1.間接制約關(guān)系(互斥)：2.直接制約關(guān)系(同步)：3.1.1臨界區(qū)由于共享資源引起由于相互合作引起3.1進程的同步受間接制約的各進程在執(zhí)行順序上是任意的;一組在異步環(huán)境下的并發(fā)進程,各自的執(zhí)行結(jié)果互為對方的執(zhí)行條件,從而限制各進程的執(zhí)行速度的過程,稱為并發(fā)進程間的直接制約。三、臨界區(qū)的進入：

3.1.1臨界區(qū)臨界區(qū)必須互斥訪問2.同步機制應(yīng)遵循的準則1.訪問過程3.1進程的同步臨界區(qū)(1)檢查臨界資源是否被訪問，未被訪問，轉(zhuǎn)(2)，否則轉(zhuǎn)(1)。(2)進入臨界區(qū)，并設(shè)訪問標志恢復(fù)訪問標志，允許其它進程進入空閑讓進忙則等待有限等待讓權(quán)等待進入?yún)^(qū)退出區(qū)3.1.2利用硬件的方法解決進程互斥問題—互斥的加鎖實現(xiàn)

可以利用某些硬件指令－－其讀寫操作由一條指令完成，因而保證讀操作與寫操作不被打斷；這些指令允許對一個字的內(nèi)容進行檢測和修正，或交換兩個字的內(nèi)容。一、利用Test-and-Set指令實現(xiàn)互斥二、利用Swap指令實現(xiàn)進程互斥3.1進程的同步3.1.2利用硬件的方法解決進程互斥問題—互斥的加鎖實現(xiàn)一、利用Test-and-Set指令實現(xiàn)互斥1.Test-and-Set指令該指令讀出標志后設(shè)置為TRUEbooleanTS(boolean*lock){booleanold;old=*lock;*lock=TRUE;returnold;}lock表示資源的兩種狀態(tài)：TRUE表示臨界區(qū)正被占用（忙），F(xiàn)ALSE表示空閑。3.1進程的同步3.1.2利用硬件的方法解決進程互斥問題—互斥的加鎖實現(xiàn)一、利用Test-and-Set指令實現(xiàn)互斥2.利用TS指令實現(xiàn)進程互斥利用TS實現(xiàn)進程互斥：每個臨界資源設(shè)置一個公共布爾變量lock，初值為FALSE在“進入?yún)^(qū)”利用TS進行檢查：若有進程在臨界區(qū)時，重復(fù)檢查；直到其它進程退出時，檢查通過；3.1進程的同步3.1.2利用硬件的方法解決進程互斥問題—互斥的加鎖實現(xiàn)二、利用Swap指令實現(xiàn)進程互斥1.Swap指令交換兩個字（字節(jié)）的內(nèi)容voidSWAP(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}3.1進程的同步3.1.2利用硬件的方法解決進程互斥問題—互斥的加鎖實現(xiàn)二、利用Swap指令實現(xiàn)進程互斥2.利用Swap實現(xiàn)進程互斥每個臨界資源設(shè)置一個公共布爾變量lock，初值為FALSE。每個進程設(shè)置一個私有布爾變量key3.1進程的同步3.1.2利用硬件的方法解決進程互斥問題—互斥的加鎖實現(xiàn)3.1進程的同步硬件方法的優(yōu)點適用于任意數(shù)目的進程，在單處理器或多處理器上簡單，容易驗證其正確性可以支持進程內(nèi)存在多個臨界區(qū)，只需為每個臨界區(qū)設(shè)立一個布爾變量硬件方法的缺點循環(huán)測試鎖狀態(tài),損耗CPU時間?？赡堋梆囸I”：從等待進程中隨機選擇一個進入臨界區(qū)，有的進程可能一直選不上(不公平現(xiàn)象)3.1進程的同步3.1.3信號量機制一、信號量

是對系統(tǒng)中資源及其組織情況的抽象。它由一個記錄型數(shù)據(jù)表示。包含兩個數(shù)據(jù)項:typesemaphore=recordvalue:integer;L:listofprocess;end

其中:value的值表示可用資源的數(shù)目;L:為等待此類資源的進程PCB表鏈。3.1進程的同步3.1.3信號量機制二、P—V操作1.P操作：wait(s)功能：請求系統(tǒng)分配一個單位的資源參數(shù)：信號量S流程：3.1進程的同步3.1.3信號量機制二、P—V操作2.V操作：signal(s)功能：釋放一個單位的資源參數(shù)：信號量S流程：3.1進程的同步3.1.3信號量機制三、信號量的應(yīng)用1.實現(xiàn)進程互斥

進程間由于共享資源而引起的間接制約關(guān)系

例如：PA、PB共享一臨界資源設(shè)互斥信號量S，初值為1，表示沒有并發(fā)進程使用臨界區(qū)設(shè)信號量賦初值：實現(xiàn)：3.1進程的同步3.1.3信號量機制三、信號量的應(yīng)用1.實現(xiàn)進程互斥為臨界資源設(shè)置一個互斥信號量S，其初值為1；在每個進程中將臨界區(qū)代碼置于P(S)和V(S)原語之間必須成對使用P和V原語：遺漏P原語則不能保證互斥訪問，遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進程）；P、V原語不能次序錯誤、重復(fù)或遺漏3.1進程的同步3.1.3信號量機制三、信號量的應(yīng)用1.實現(xiàn)進程互斥

問(1)該例中S.value的取值范圍(2)PA在臨界區(qū)訪問,PB等待,某時刻PA執(zhí)行完臨界區(qū)代碼,執(zhí)行V(S)后,問PB的狀態(tài)變化?(3)若有n個進程共享一臨界資源，則信號量的取值范圍?3.1進程的同步3.1.3信號量機制三、信號量的應(yīng)用2.實現(xiàn)進程同步

進程間由于相互合作而引起的直接制約關(guān)系

例如：計算進程和打印進程共享一緩沖區(qū),緩沖區(qū)最多放一個數(shù),計算進程反復(fù)把每次計算結(jié)果放入緩沖區(qū)中,而打印進程則把計算進程每次放入緩沖區(qū)中的數(shù)據(jù)通過打印機打印輸出。設(shè)信號量賦初值：分析：實現(xiàn)：3.1進程的同步3.1.3信號量機制三、信號量的應(yīng)用

問(1)在該問題中需要考慮互斥嗎?為什么?(2)若為緩沖池,池中有多個緩沖塊,可放多個產(chǎn)品（數(shù)），考慮互斥嗎?為什么?----生產(chǎn)者、消費者問題2.實現(xiàn)進程同步結(jié)論：若臨界區(qū)有一個可用資源單位，同步便實現(xiàn)了互斥。若臨界區(qū)有多個可用資源，必須考慮互斥。3.1進程的同步3.1.3信號量機制三、信號量的應(yīng)用2.實現(xiàn)進程同步例如：設(shè)在公共汽車上，司機和售票員的活動分別是：司機：售票員：啟動車輛上乘客正常行車關(guān)車門到站停車售票開車門下乘客一方面只有售票員關(guān)好車門后司機才能啟動車輛，另一方面只有司機到站停車后售票員才能開車門。請分析司機和售票員之間的同步關(guān)系，并用信號量的P、V操作來實現(xiàn)。3.1進程的同步3.1.3信號量機制三、信號量的應(yīng)用2.實現(xiàn)進程同步答：兩個同步：關(guān)車門----〉啟動車輛run=0;到站停車----〉開車門stop=0;司機：售票員：上乘客p(run)關(guān)車門啟動車輛v(run)正常行車售票到站停車p(stop)v(stop)開車門下乘客3.描述前趨圖本題是典型的同步問題。即進程A執(zhí)行完后才可執(zhí)行進程B，只需在兩進程間設(shè)置信號量，當(dāng)進程A執(zhí)行結(jié)束后執(zhí)行V操作，通知進程B可以開始，而進程B在開始之前先執(zhí)行P操作，直到得到進程A的消息。信號量機制三、信號量的應(yīng)用同步關(guān)系如下：begins12=0;s13=0;s24=0;s36=0;s46=0;s45=0;s57=0;s67=0Parbeginbegins1;v(s12);v(s13);end;beginp(s12);s2;v(s24);end;beginp(s13);s3;v(s36);end;beginp(s24);s4;v(s45);v(s46);end;beginp(s45);s5;v(s57);end;beginp(s46);p(s36);s6;v(s67);end;beginp(s57);p(s67);s7;end;parend;end信號量機制三、信號量的應(yīng)用3.描述前趨圖4.解決生產(chǎn)者—消費者問題問題描述：有一群生產(chǎn)者進程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費者進程去消費。為使生產(chǎn)者進程與消費者進程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個具有n個緩沖區(qū)的緩沖池，生產(chǎn)者進程將它所生產(chǎn)的產(chǎn)品放入一個緩沖區(qū)中；消費者進程可從一個緩沖區(qū)中取走產(chǎn)品去消費。盡管所有的生產(chǎn)者進程和消費者進程都是以異步方式運行的，但它們之間必須保持同步，即不允許消費者進程到一個空緩沖區(qū)去取產(chǎn)品；也不允許生產(chǎn)者進程向一個已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品。三、信號量的應(yīng)用信號量機制信號量機制三、信號量的應(yīng)用4.解決生產(chǎn)者—消費者問題設(shè)信號量賦初值：分析：實現(xiàn)：注意：在每個程序中的多個p操作順序不能顛倒。應(yīng)先執(zhí)行對資源信號量的p操作，然后再執(zhí)行對互斥信號量的p操作，否則可能引起進程死鎖。三、信號量的應(yīng)用

三個進程P0、P1、P2和三個緩沖區(qū)B0、B1、B2。進程間借助于相鄰緩沖區(qū)傳遞消息：Pi每次從Bi中取一條消息，經(jīng)加工送入B（i+1）mod3中，B0、B1、B2分別可存放3、2、2個消息。初始時，僅B0有一個消息。1．分析三個進程間的同步、互斥關(guān)系。2．用P、V操作寫出P0、P1、P2的同步及互斥流程。例1:信號量機制三、信號量的應(yīng)用

三個進程P0、P1、P2和三個緩沖區(qū)B0、B1、B2。進程間借助于相鄰緩沖區(qū)傳遞消息：Pi每次從Bi中取一條消息，經(jīng)加工送入B（i+1）mod3中，B0、B1、B2分別可存放3、2、1個消息。初始時，僅B0有一個消息。1．分析三個進程間的同步、互斥關(guān)系。2．用P、V操作寫出P0、P1、P2的同步及互斥流程。例2:信號量機制三、信號量的應(yīng)用一組生產(chǎn)者進程和一組消費者進程共享10個緩沖區(qū)，每個緩沖區(qū)可以存放一個整數(shù)；生產(chǎn)者進