進(jìn)程同步的多種解決辦法

XI'ANTECHNOLOGICALUNIVERSITY實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)課程名稱 操作系統(tǒng)論文名稱進(jìn)程同步的多種解決辦法專業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)： 15060101指導(dǎo)教師 績(jī):2017年11月26日進(jìn)程同步的多種解決辦法摘要：簡(jiǎn)單介紹了進(jìn)程同步的概念，分析了進(jìn)程同步的多種解決辦法，重點(diǎn)討論了讀者寫(xiě)者問(wèn)題，更容易了解解決辦法的具體機(jī)制。關(guān)鍵詞：進(jìn)程同步；多進(jìn)程；讀者-寫(xiě)者0引言Windows應(yīng)用程序中消息有兩種送出途徑，直接和排隊(duì)。Windows或某些運(yùn)行的應(yīng)用程序可直接發(fā)布消息給窗口過(guò)程，或消息可送達(dá)到消息列象連續(xù)不斷地輪詢消息隊(duì)列的OS中當(dāng)前執(zhí)行的每一個(gè)進(jìn)程都不是由事件的順序來(lái)控制的，而是由事件的發(fā)生來(lái)控制的。在傳統(tǒng)的操作系統(tǒng)中，為提高資源利用率和系統(tǒng)吞吐量，通常采用多道程序技術(shù)，將多個(gè)程序同時(shí)裝入內(nèi)存，并使之并發(fā)執(zhí)行。同步在OS中引入進(jìn)程后，一方面使系統(tǒng)中多道程序并發(fā)執(zhí)行，這不僅使資源利用率改善，亦可顯著提高系統(tǒng)吞吐量，但也使系統(tǒng)更為復(fù)雜，致使進(jìn)程對(duì)系統(tǒng)資源的無(wú)序爭(zhēng)奪，每次處理的結(jié)果存在不確定性，顯現(xiàn)不可再現(xiàn)性。因此，在多道程序系統(tǒng)中，必須引入進(jìn)程同步機(jī)制。在本文中將介紹如下幾種進(jìn)程同步機(jī)制——硬件同步機(jī)制，信號(hào)量機(jī)制，管程機(jī)制和Peri網(wǎng)。進(jìn)程同步解決辦法硬件同步機(jī)制目前許多計(jì)算機(jī)已提供特殊的硬件指令，允許對(duì)一個(gè)字中的內(nèi)容進(jìn)行檢測(cè)和改正或?qū)蓚€(gè)字進(jìn)行交換?？衫锰厥庵噶罱鉀Q臨界的問(wèn)題。對(duì)臨界區(qū)管理時(shí)，可將標(biāo)志看作一個(gè)鎖，“鎖開(kāi)”進(jìn)入，“鎖關(guān)”等待，初始狀態(tài)鎖是開(kāi)著的。但當(dāng)臨界資源忙碌時(shí)，其他進(jìn)程處于“忙等”狀態(tài)，不符合“讓權(quán)等待”原則，造成處理機(jī)時(shí)間的浪費(fèi)，同時(shí)很難解決，解決復(fù)雜的進(jìn)程同步問(wèn)題。信號(hào)量機(jī)制信號(hào)量機(jī)制已得到廣泛發(fā)展，由整形信號(hào)量經(jīng)記錄型信號(hào)量，發(fā)展到“信號(hào)量集機(jī)制”，已廣泛應(yīng)用于單處理機(jī)和多處理機(jī)系統(tǒng)以及計(jì)算機(jī)網(wǎng)絡(luò)中。信號(hào)量機(jī)制通常包括整型信號(hào)量，記錄型信號(hào)量，AND型信號(hào)量和信號(hào)量集。整型信號(hào)量除初始化外，僅能通過(guò)兩個(gè)標(biāo)準(zhǔn)的原子操作wait(S)和signal(S)來(lái)訪問(wèn)。很長(zhǎng)時(shí)間以來(lái)，這兩個(gè)操作分別被稱為P、V操作。wait和signal操作可描述如下：wait(S){while(S<=0);/*dono-op*/S--;}Signal(S){S++;}原子操作不可中斷，因此在執(zhí)行時(shí)不可中斷，即是當(dāng)一個(gè)進(jìn)程再修改某信號(hào)量時(shí)，沒(méi)有其他進(jìn)程可同時(shí)對(duì)該信號(hào)量進(jìn)行修改。此外，在wait操作中，對(duì)S值的測(cè)試和做S=S-1操作時(shí)，都不可中斷。在整型信號(hào)量機(jī)制中的wait操作，只要是信號(hào)量S<=0，就不斷測(cè)試，因此，該機(jī)制并未遵循“讓權(quán)等待”的準(zhǔn)則，而是使進(jìn)程處于“忙等”狀態(tài)。記錄型信號(hào)量則不存在“忙等”狀態(tài)。記錄型信號(hào)量采取“讓權(quán)等待”的策略，但會(huì)出現(xiàn)多個(gè)進(jìn)程訪問(wèn)同一臨界資源的情況。為此，在信號(hào)量機(jī)制中除了一個(gè)需要用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個(gè)進(jìn)程鏈表指針list，用于鏈接上述所有的等待進(jìn)程。記錄型信號(hào)量由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名。AND型信號(hào)量AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源，一次性全部地分給進(jìn)程，待進(jìn)程使用完再一起釋放。只要尚有一個(gè)進(jìn)程未能分配給進(jìn)程，其他所有可能為之分配的資源也不分配給它。亦即，對(duì)若干個(gè)臨界資源的分配采取原子操作方式；要么把它所請(qǐng)求的資源全部分配到進(jìn)程。要么一個(gè)也不分配。由死鎖理論可知，這樣就可以避免上述死鎖情況的發(fā)生。為此，在wait操作中增加了一個(gè)“AND”條件，故稱為AND同步，或成為同時(shí)wait操作。信號(hào)量集在上述的記錄型信號(hào)量機(jī)制中，wait(S)或signal(S)操作僅能對(duì)信號(hào)量施加1或減一操作，意味著每次只能對(duì)某類資源進(jìn)行一個(gè)單位的申請(qǐng)或者釋放。當(dāng)一次需要N個(gè)單位時(shí)，便要進(jìn)行N次wait(S)操作，這顯然是低效的，甚至?xí)黾铀梨i的概率。此外，在有些情況下，為確保系統(tǒng)的安全性，當(dāng)所申請(qǐng)的資源數(shù)量低于某一下限值時(shí)，還必須進(jìn)行管制，不予以分配。因此，當(dāng)進(jìn)程中申請(qǐng)某類臨界資源時(shí)，在每次分配之前，都必須測(cè)試資源的數(shù)量，判斷是否大于可分配的下限值，決定是否予以分配?；谏鲜鰞牲c(diǎn)，可以對(duì)AND信號(hào)量機(jī)制加以擴(kuò)充，對(duì)進(jìn)程所申請(qǐng)的所有資源以及每類資源不同的資源需求量，在一次P,V原語(yǔ)操作中完成申請(qǐng)或者釋放。進(jìn)程對(duì)信號(hào)量S1的測(cè)試值不再是一，而是該資源的分配下限值t1,即使要求Si>=ti,否則不予以分配。一旦允許分配，進(jìn)程對(duì)該資源的需求值為di,即表示資源信號(hào)量，進(jìn)行Si=Si-di操作，而不是簡(jiǎn)單的Si=Si-1。由此形成一般化的“信號(hào)量集”機(jī)制。管程機(jī)制系統(tǒng)中的各種硬件資源和軟件資源均可用于數(shù)據(jù)結(jié)構(gòu)抽象地描述其資源特性，即用少量信息和對(duì)該資源所執(zhí)行的操作來(lái)表征該資源，而忽略它們的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)細(xì)節(jié)。因此，可以利用共享資源所執(zhí)行的操作來(lái)表征該資源，而忽略它們的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)細(xì)節(jié)。因此，可以利用共享數(shù)據(jù)結(jié)構(gòu)抽象地表示系統(tǒng)中的共享資源，并且將對(duì)該共享數(shù)據(jù)結(jié)構(gòu)實(shí)施的特定操作定義為一組過(guò)程。進(jìn)程對(duì)共享資源的申請(qǐng)、釋放和其他操作必須通過(guò)這組過(guò)程，間接的對(duì)共享數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)操作。對(duì)于請(qǐng)求訪問(wèn)共享資源的諸多并發(fā)進(jìn)程，可以根據(jù)資源的情況接受或者阻塞，確保每次僅有一個(gè)進(jìn)程進(jìn)入管程。執(zhí)行這組過(guò)程，使用共享資源，選擇對(duì)共享資源所有訪問(wèn)的統(tǒng)一管理，有效實(shí)現(xiàn)進(jìn)程互斥。Petri網(wǎng)Petri網(wǎng)是一種適于描述和分析異步并發(fā)系統(tǒng)的有力工具，Peri網(wǎng)是德國(guó)的C.A.Petri于1962年在他的博士論文中提到的，用以構(gòu)造系統(tǒng)模型及動(dòng)態(tài)特性分析。在計(jì)算機(jī)科學(xué)的許多領(lǐng)域，如并行計(jì)算，分布式數(shù)據(jù)庫(kù)設(shè)計(jì)等，Petri網(wǎng)系統(tǒng)已經(jīng)起到了越來(lái)越重要的作用。Petri網(wǎng)結(jié)構(gòu)元素的物理描述：①位置:描述可能的系統(tǒng)局部狀態(tài)(條件或狀態(tài))。如：隊(duì)列、資源等。②變遷：描述修改系統(tǒng)狀態(tài)的事件。如：信息處理、發(fā)送、資源存取等操作。③?。阂?guī)定局部狀態(tài)和事件之間的關(guān)系，連接位置和變遷。④標(biāo)示或標(biāo)記：活動(dòng)元素，包含在位置集合中。如果一個(gè)位置描述一個(gè)條件,有標(biāo)記表示條件為真，否則條件為假。也可以用于表示處理的信息單元、數(shù)據(jù)資源單元和顧客、用戶等對(duì)象實(shí)體。進(jìn)程同步編程實(shí)例：利用記錄型信號(hào)量解決哲學(xué)家就餐問(wèn)題：為每根筷子設(shè)置一個(gè)信號(hào)量chopstick[i],初值為1。一個(gè)哲學(xué)家通過(guò)在相應(yīng)信號(hào)量上執(zhí)行P操作抓起一支筷子，執(zhí)行V操作放下一支筷子。philosopher:while(true){P(chopstick[i]);P(chopstick[(i+1)%5])；用餐；V(chopstick[i]);V(chopstick[(i+1)%5])；思考；}利用信號(hào)量集機(jī)制解決讀者-寫(xiě)者問(wèn)題:增加限制：最多允許RN個(gè)讀者同時(shí)讀。引入信號(hào)量L,初值為RN。VarRNinteger;L,mx:semaphore：=RN,1;beginparbeginreader:beginrepeatSwait(L,1,1);Swait(mx,1,0);???performreadoperation;???Ssignal(L,1);untilfalse;endwriter:beginrepeatSwait(mx,1,1;L,RN,0);performwriteoperation;Ssignal(mx,1);untilfalse;endparendend3?3利用Petri網(wǎng)描述讀者-寫(xiě)者問(wèn)題：圖1和圖2分別表示了一個(gè)讀進(jìn)程和一個(gè)寫(xiě)進(jìn)程的情況。對(duì)于圖1和圖2中各庫(kù)所和變遷的含義是：Rp1/Wp1:讀者/寫(xiě)者在做其他事；p1p1RT1/WT1：讀者/寫(xiě)者提出資源使用申請(qǐng)；r2/w2:讀者/寫(xiě)者等待應(yīng)答；22rT2/wT2：讀者/寫(xiě)者得到讀/寫(xiě)的應(yīng)答；R3/W3：讀者/寫(xiě)者進(jìn)行讀/寫(xiě)操作；R；3/W；3:讀者/寫(xiě)者歸還資源；R-f|R,T| RRtS RPm RT*o~―~o―_WniWtiWhWitWi.j圖3給出兩個(gè)讀者和一個(gè)寫(xiě)作的Petri網(wǎng)的示意圖。Til0]K1200圖3給出兩個(gè)讀者和一個(gè)寫(xiě)作的Petri網(wǎng)的示意圖。Til0]K1200凰3^11'ni00畑其中：c：限制讀進(jìn)程與寫(xiě)進(jìn)程互斥訪問(wèn)條件C1：標(biāo)志讀者個(gè)數(shù)C1到WT11的約束弧用來(lái)限制只有所有讀者都不讀時(shí)才能寫(xiě)Rpli代表第一個(gè)讀者的狀態(tài)；RT1i代表第一個(gè)讀者的動(dòng)作Rp2i代表第二個(gè)讀者的狀態(tài)；RT2i代表第二個(gè)讀者的動(dòng)作4結(jié)束語(yǔ)本文重點(diǎn)討論了進(jìn)程同步的多種解決辦法這一問(wèn)題，通過(guò)實(shí)現(xiàn)“哲學(xué)家進(jìn)餐問(wèn)題”，“讀者-寫(xiě)者問(wèn)題”這兩個(gè)經(jīng)典的進(jìn)程同步問(wèn)題，比較清晰的反映了進(jìn)程同步的解決辦法。通過(guò)對(duì)解決辦法的總結(jié)，作者也