1、進程同步與互斥習(xí)題課,河北工業(yè)大學(xué) 計算機學(xué)院 李建偉,利用信號量實現(xiàn)進程間的互斥,由于各進程要求共享資源，而有些資源需要互斥使用，因此各進程間競爭使用這些資源，進程的這種關(guān)系為進程的互斥 臨界資源：critical resource 系統(tǒng)中某些資源一次只允許一個進程使用，稱這樣的資源為臨界資源或互斥資源或共享變量,臨界區(qū)（互斥區(qū)）：critical section 一個程序片段的集合，這些程序片段分散在不同的進程中，對某個共享的數(shù)據(jù)結(jié)構(gòu)（共享資源）進行操作 在進程中涉及到臨界資源的程序段叫臨界區(qū),a := a -1 print (a),a := a +1 print (a),進程的互斥 （間

2、接作用）,互斥例題1 設(shè)一民航航班售票系統(tǒng)有n個售票處。每個售票處通過終端訪問系統(tǒng)中的公用數(shù)據(jù)區(qū)，假定公共數(shù)據(jù)區(qū)中一些單元xk(k=1, 2, )分別存放月日次航班的現(xiàn)存票數(shù)。設(shè)P1，P2， ，Pn表示各售票處的處理進程，R1, R2, , Rn表示各進程執(zhí)行時所用的工作單元。 用信號量實現(xiàn)進程間互斥的程序如下：,begin S: Semaphore; S=1 cobegin,Process Pi(i=1, 2, , n) begin 按旅客訂票要求找到xk; P(S) Ri=xk; if Ri1 then begin Ri=Ri-1; xk=R1; V(S) 輸出一張票 end else b

3、egin V(S); 輸出“票已售完” end end; coend; end;,互斥例題2,2. 利用信號量實現(xiàn)進程間的同步 一般來說， 信號量初值為 0， 兩個進程之間的同步模型如下：,進程P1 進程P2 L1：P(S) L2：V(S),例 1 用信號量實現(xiàn)司機和售票員的同步。 設(shè)S1和S2分別為司機和售票員的私用信號量，初值均為0，則司機和售票員的同步過程描述如下：,例 2 設(shè)進程A、B是兩個相互合作的進程，共用一個緩沖區(qū)。進程A負責(zé)從卡片輸入機讀入卡片送到緩沖區(qū)， 進程B取走緩沖區(qū)中的卡片信息進行加工處理。進程A在完成將卡片送入緩沖區(qū)后，給進程B發(fā)一信號。進程B收到信號后，取走卡片信息

4、進行加工處理。反之，進程B取走卡片信息后，給進程A發(fā)一信號，進程A再將卡片信息讀入緩沖區(qū)。為此，我們利用兩個私用信號量S1和S2， 其初值均為 0，信號量S1表示緩沖區(qū)是否有卡片信息，信號量S2表示緩沖區(qū)信息是否被取走。利用P、V操作實施進程A、B的同步過程如下：,讀者-寫者模型是現(xiàn)代操作系統(tǒng)中典型的進程同步互斥問題，以客戶服務(wù)器模式為代表的多進(線)程通信系統(tǒng)應(yīng)用都可以抽象為該模型的不同形式。因此,該模型的算法在這些領(lǐng)域具有重要的應(yīng)用價值。,典型同步互斥問題之一： 讀者與寫者問題(ReaderWriter Problems),多個進程共享一個文件,其中只讀文件進程稱為讀者,只寫文件進程稱為寫

5、者.多個讀者和多個寫者在某個時間段內(nèi)對該文件資源異步進行讀寫.為避免文件數(shù)據(jù)出現(xiàn)丟失修改和讀臟數(shù)據(jù)的情況,對讀者和寫者的讀寫操作限制如下. (1)寫-寫互斥,即不允許多個寫者同時對文件 進行寫操作. (2)讀-寫互斥,即不允許讀者和寫者同時對文 件分別進行讀寫操作. (3)讀-讀允許,即允許多個讀者同時對文件進 行讀操作.,讀者優(yōu)先方案,設(shè)計思想:讀者優(yōu)先意味著以下兩條要求. (i)除非有寫者正在寫文件,否則讀者不需要等待; (ii)僅當(dāng)無讀者時才允許寫者使用文件.,讀者優(yōu)先算法實現(xiàn): PReader(讀者進程) P(mutexReaderCount) ReaderCount+ If(Read

6、erCount=1) P(mutexShareFile) V(mutexReaderCount) 從文件讀信息 P(mutexReaderCount) ReaderCount- If(ReaderCount=0) V(mutexShareFile) V(mutexReaderCount),PWriter(寫者進程) P(mutexShareFile) 向文件寫信息 V(mutexShareFile) 算法分析:限制條件(1)(3)均可以得到滿足,是徹底解決讀者-寫者問題的最基本方案.但讀者的高優(yōu)先級可能造成某個暫時得不到文件的寫者由于被隨后而來的源源不斷的讀者插隊而長時間掛起,直到全部讀者進程

7、運行完畢后,才可以使用文件.,讀者-寫者公平競爭方案,設(shè)計思想:讀者-寫者公平競爭的要求讀者-寫者完全按照先來先服務(wù)的原則使用文件資源，一旦有寫者到達，后續(xù)的讀者都必須等待。不允許出現(xiàn)后來者超越先來的等待資源者插隊的現(xiàn)象。,PReader(讀者進程) P(mutexRegister) P(mutexReaderCount) ReaderCount+ If(ReaderCount= P(mutexShareF V(mutexReaderCount) V(mutexRegister) 從文件讀信息 P(mutexReaderCount ReaderCount- If(ReaderCount=0)

8、V(mutexShareFile) V(mutexReaderCount),PWriter(寫者進程) P(mutexRegister) P(mutexShareFile) 向文件寫信息 V(mutexShareFile) V(mutexRegister),算法分析,限制條件(1)(3)均可以得到滿足,新的互斥信號量mutexRegister的引入使得在有寫者處于等待狀態(tài)的情況下,后來的讀者進程會由于同寫者進程對注冊標(biāo)記的競爭嘗試失敗而不得不掛起,從而實現(xiàn)了讀者-寫者間的先來先服務(wù)的公平競爭方案.,寫者優(yōu)先方案,設(shè)計思想:寫者優(yōu)先有以下兩條要求. (i)僅當(dāng)無寫者時才允許讀者使用文件; (ii

9、)喚醒時優(yōu)先考慮寫者.,算法實現(xiàn):,PReader(讀者進程) P(mutexEnhance) P(mutexRegister) P(mutexReaderCount) ReaderCount+ If(ReaderCount=1) P(mutexShareFile) V(mutexReaderCount) V(mutexRegister) V(mutexEnhance) 從文件讀信息 P(mutexReaderCount) ReaderCount- If(ReaderCount=0) V(mutexShareFile) V(mutexReaderCount),PWriter(寫者進程) P(m

10、utexWriterCount) WriterCount+ If(WriterCount=1) P(mutexRegister) V(mutexWriterCount) P(mutexShareFile) 向文件寫信息 V(mutexShareFile) P(mutexWriterCount) WriterCount- If(WriterCount=0) V(mutexRegister) V(mutexWriterCount),算法分析,在滿足限制條件(1)(3)的前提下,以寫者進程為優(yōu)先考慮對象,如果有寫請求發(fā)出,則它會在被允許的最快時間內(nèi)得到響應(yīng).其好處是在一個由很多客戶端以讀權(quán)限訪問的服

11、務(wù)器(如一般的公眾服務(wù)器)上,如果管理員對服務(wù)器的某些內(nèi)容或配置進行修改的話,那么它的及時性可以得到滿足。,總結(jié),可由一類進程多次訪問,而不同類的進程必須 互斥訪問資源的控制,是進程控制中常見的一類問 題. 讀者-寫者模型正是這類問題中的一個典型, 它給出了對于這類資源的控制方法,即采用一個資 源計數(shù)變量進行控制,把對于該資源的訪問控制變 成對變量的訪問.同時,資源計數(shù)變量作為新的臨界資源,也需要用新的信號量對其進行互斥訪問控制.,練習(xí)題1,桌子有一空盤，允許存放一個水果。爸爸可向盤中放蘋果，也可以向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時一次只能放一只水果供吃者取

12、用，請用P、V原語實現(xiàn)爸爸、兒子、女兒3個并發(fā)進程的同步。,練習(xí)題2,設(shè)有三個進程A、B、C，其中A與B構(gòu)成一對生產(chǎn)者與消費者(A為生產(chǎn)者，B為消費者)，共享一個由n個緩沖塊組成的緩沖池，B與C也構(gòu)成一對生產(chǎn)者與消費者（此時B為生產(chǎn)者，C為消費者），共享另一個由m個緩沖塊組成的緩沖池。用P、V操作描述它們之間的關(guān)系。,練習(xí)題3,把學(xué)生和監(jiān)考老師都看作進程，學(xué)生有N人，教師1人?？紙鲩T口每次只能進出一個人，進考場原則是先來先進。當(dāng)N個學(xué)生都進入考場后，教師才能發(fā)卷子。學(xué)生交卷后可以離開考場。教師要等收上來全部卷子后才能離開考場。 問共需設(shè)置幾個進程？ 設(shè)置合適的信號量及初值，試用P、V操作解決上述