進(jìn)程同步第三章

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

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

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

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

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

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

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

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

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

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

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

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

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

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