進(jìn)程同步與互斥的關(guān)系

進(jìn)程同步與互斥的關(guān)系

在多道程序環(huán)境中，當(dāng)程序同時(shí)運(yùn)行時(shí)，由于資源共享和進(jìn)程合作，同一系統(tǒng)中的進(jìn)程之間可能存在相互干擾和直接制約的關(guān)系。信號(hào)機(jī)制是調(diào)整操作系統(tǒng)進(jìn)步同步的常用工具，用于協(xié)調(diào)進(jìn)程。1進(jìn)程間的互斥進(jìn)程的同步是指在異步環(huán)境下的并發(fā)進(jìn)程因直接制約而互相發(fā)送消息,進(jìn)行相互合作、相互等待,使得各進(jìn)程按一定的速度執(zhí)行的過(guò)程;而進(jìn)程的互斥是由并發(fā)進(jìn)程同時(shí)共享公用資源而造成的對(duì)并發(fā)進(jìn)程執(zhí)行速度的間接制約.無(wú)論是同步還是互斥,都是在執(zhí)行的時(shí)間順序上對(duì)并發(fā)進(jìn)程的操作加以某種限制.對(duì)于互斥的進(jìn)程,它們各自單獨(dú)執(zhí)行時(shí)都是正確的;同步的進(jìn)程,它們各自單獨(dú)執(zhí)行會(huì)產(chǎn)生錯(cuò)誤,必須互相配合共同推進(jìn),也就是說(shuō),同步條件高.同步一方面要互斥進(jìn)入臨界區(qū)使用臨界資源,另一方面進(jìn)入臨界區(qū)有先后順序.2pv操作一個(gè)信號(hào)量的建立必須經(jīng)過(guò)說(shuō)明,即應(yīng)該準(zhǔn)確說(shuō)明s的意義和初值,信號(hào)量的值僅能由PV原語(yǔ)來(lái)改變.P操作是申請(qǐng)資源,它使信號(hào)量值減1,若結(jié)果非負(fù),該進(jìn)程繼續(xù),否則該進(jìn)程被封鎖;V操作是釋放資源,它使信號(hào)量值增1,若結(jié)果大于零,該進(jìn)程繼續(xù),否則從該信號(hào)量的等待隊(duì)列中移出一個(gè)進(jìn)程,解除它的等待狀態(tài).2.1售票廳社會(huì)資源用于互斥的信號(hào)量mutex與所有的并發(fā)進(jìn)程有關(guān),稱之為公有信號(hào)量,公有信號(hào)量的值反映了可用該公有資源的數(shù)量.要實(shí)現(xiàn)進(jìn)程互斥,只需用P(mutex)、V(mutex)框住臨界區(qū)CS.程序如下:例1某車站售票廳,任何時(shí)刻最多可容納20名購(gòu)票者進(jìn)入,當(dāng)售票廳中少于20名購(gòu)票者時(shí),廳外的購(gòu)票者可立即進(jìn)入,否則需要在外面等待.每個(gè)購(gòu)票者可看成一個(gè)進(jìn)程.分析:首先確定進(jìn)程間的關(guān)系,售票廳是各進(jìn)程共享的公有資源,當(dāng)售票廳中多于20名購(gòu)票者時(shí),廳外的購(gòu)票者需要在外面等待,所以進(jìn)程間是互斥的關(guān)系;然后確定信號(hào)量及其值,只有一個(gè)公有資源:售票廳,所以設(shè)置一個(gè)信號(hào)量mutex.售票廳最多容納20個(gè)進(jìn)程,即可用該資源實(shí)體數(shù)為20,mutex的初值就設(shè)為20.程序如下:REPEATP(mutex);進(jìn)入售票廳;購(gòu)票;退出;V(mutex);UNTILfalse;由此可知,互斥信號(hào)量的初值可大于等于1(當(dāng)售票廳內(nèi)至多容納1名購(gòu)票者時(shí),初值為1),初值取什么,關(guān)鍵是可用資源數(shù).2.2基于pv原語(yǔ)的進(jìn)程同步與進(jìn)程互斥不同,進(jìn)程同步時(shí)的信號(hào)量只與制約進(jìn)程及被制約進(jìn)程有關(guān)而不是與整組并發(fā)進(jìn)程有關(guān),所以稱該信號(hào)量為私有信號(hào)量.利用PV原語(yǔ)實(shí)現(xiàn)進(jìn)程同步的方法是:首先判斷進(jìn)程間的關(guān)系為同步的,且為各并發(fā)進(jìn)程設(shè)置私有信號(hào)量;然后為私有信號(hào)量賦初值.進(jìn)程通過(guò)調(diào)用P操作來(lái)測(cè)定自己需要的消息是否到達(dá),通過(guò)調(diào)用V操作把其它進(jìn)程需要的消息發(fā)送出去.2.2.1行完后才執(zhí)行程序首先找出所有的前趨關(guān)系,然后對(duì)每一種前趨關(guān)系(如Si→Sj)專門設(shè)置一初值為0的信號(hào)量,并在Si結(jié)束之后執(zhí)行對(duì)該信號(hào)量的V操作,而在Sj開始之前執(zhí)行對(duì)該信號(hào)量的P操作,這樣便可保證程序段Si執(zhí)行完后才執(zhí)行程序段Sj.例如圖1有5個(gè)前趨關(guān)系,故設(shè)5個(gè)信號(hào)量S12、S13、S24、S25、S36、S46、S56,初值均為零,Sij表示第i個(gè)進(jìn)程是否完成,第j個(gè)進(jìn)程能否開始.上述方法考慮的是有向邊的個(gè)數(shù),我們也可以根據(jù)結(jié)點(diǎn)來(lái)設(shè)置信號(hào)量.在前趨圖中,有幾個(gè)有后繼的結(jié)點(diǎn),就設(shè)幾個(gè)信號(hào)量,且初值為零,表示該結(jié)點(diǎn)表示的進(jìn)程是否完成,此時(shí),一個(gè)結(jié)點(diǎn)有幾個(gè)后繼,要做幾次V操作.圖1中,有5個(gè)結(jié)點(diǎn)有后繼,故設(shè)5個(gè)信號(hào)量a、b、c、d、e初值均為零,分別表示P1、P2、P3、P4、P5是否執(zhí)行完成,程序如下:注意:進(jìn)程P1、P2分別有2個(gè)V(a)、V(b)操作,因?yàn)樗鼈兎謩e有2個(gè)后繼.2.2.2規(guī)范開車行為,釋放信號(hào)量例2在公共汽車上,司機(jī)和售票員各司其職.司機(jī):正常行車、到站停車、啟動(dòng)開車;售票員:售票、開車門、關(guān)車門.司機(jī)和售票員之間應(yīng)該密切配合,協(xié)調(diào)一致,以確保行車安全.請(qǐng)用PV操作實(shí)現(xiàn)司機(jī)和售票員之間的同步.分析:司機(jī)和售票員在到站、開門、關(guān)門、啟動(dòng)開車幾件事情上存在有同步關(guān)系:到站后才能開門,關(guān)門后才能開車.用2個(gè)私有信號(hào)量stop、run分別表示可以開門和可以開車.由于初始狀態(tài)是汽車行車和售票員售票,所以初值應(yīng)該都為0,到站后才會(huì)有司機(jī)發(fā)消息讓開門.程序如下:如果司機(jī)和售票員的工作流程如下,司機(jī):啟動(dòng)開車、正常行車、到站停車;售票員:開車門、關(guān)車門、售票.此時(shí),由于初始狀態(tài)為停車而還沒(méi)開門狀態(tài),設(shè)stop=1、run=0,2個(gè)程序?yàn)?需要注意的是2個(gè)進(jìn)程同步時(shí),程序編制和信號(hào)量初值有關(guān).若S1=1,S2=0,則進(jìn)程1為:P(S1)……V(S2),進(jìn)程2為P(S2)……V(S1),即申請(qǐng)自己的信號(hào)量,釋放對(duì)方的信號(hào)量;若S1=0,S2=0,則進(jìn)程1為:……V(S2),P(S1),進(jìn)程2為P(S2)……V(s1),即其中一個(gè)進(jìn)程先執(zhí)行,然后釋放對(duì)方的信號(hào)量,再申請(qǐng)自己的信號(hào)量.3同步信號(hào)量與互斥信息有了上面的分析后,下面來(lái)考慮進(jìn)程同步與互斥的混合問(wèn)題.例3有一個(gè)倉(cāng)庫(kù),可以存放A和B2種產(chǎn)品.要求:1)每次只能存入一種產(chǎn)品(A或B);2)-N<A產(chǎn)品數(shù)量-B產(chǎn)品數(shù)量<M.試用PV操作描述產(chǎn)品A與產(chǎn)品B的入庫(kù)過(guò)程.分析:將放A產(chǎn)品看成一個(gè)進(jìn)程,放B產(chǎn)品看成另一個(gè)進(jìn)程,這2個(gè)進(jìn)程單獨(dú)執(zhí)行會(huì)產(chǎn)生錯(cuò)誤:產(chǎn)品數(shù)量不符合條件2),故2個(gè)進(jìn)程是同步的.由條件2)知,B產(chǎn)品的數(shù)量不能比A產(chǎn)品的數(shù)量多N個(gè)以上,A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量多M個(gè)以上.即每次放A產(chǎn)品時(shí)先檢查A產(chǎn)品的數(shù)量是否比B產(chǎn)品的數(shù)量多M個(gè)以上,若是,不允許放,放B產(chǎn)品時(shí)也做檢查.因此設(shè)2個(gè)同步信號(hào)量,分別表示A產(chǎn)品比產(chǎn)品多入庫(kù)的數(shù)量和B產(chǎn)品比A產(chǎn)品多入庫(kù)的數(shù)量,由條件可知,初值分別為M-1和N-1.給出的條件1)是臨界資源的訪問(wèn)控制,設(shè)一個(gè)互斥信號(hào)量來(lái)解決.需要說(shuō)明的是,A進(jìn)程中同步的P(sa)、V(sb)在外,互斥的P(mutex)、V(mutex)在內(nèi),B進(jìn)程也如此.用PV操作實(shí)現(xiàn)進(jìn)程同步與互斥時(shí),應(yīng)注意:1)對(duì)每一個(gè)共享資源(含變量)都要設(shè)立信號(hào)量,互斥時(shí)對(duì)一個(gè)共享資源設(shè)一個(gè)信號(hào)量,同步時(shí)對(duì)一個(gè)共享資源可能要設(shè)兩個(gè)或多個(gè)信號(hào)量,視有幾個(gè)進(jìn)程來(lái)使用該共享變量而定;2)互斥時(shí)信號(hào)量的初值可大