操作系統(tǒng)ppt課件第3章

單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,*,*,第3章 并發(fā)控制互斥與同步,本章知識點：,3.1 并發(fā)原理,3.2 互斥軟件解決方法,3.3,互斥硬件解決方法,3.4 信號量,3.5 管程,3.6 *消息傳遞,3.7 *讀者/寫者問題,3.8 系統(tǒng)舉例（略）,1,3.1 并發(fā)原理,在單處理機多道程序的系統(tǒng)中，進程的并發(fā)執(zhí)行方式是插入執(zhí)行，表面看起來進程如同是同時執(zhí)行的。在多處理機系統(tǒng)中并發(fā)執(zhí)行方式有插入執(zhí)行和重疊執(zhí)行。,并發(fā)的存在要求操作系統(tǒng)必須能跟蹤大量活躍進程,必須為每一活躍進程分配資源，必須保護每一進程的數(shù)據(jù)和物理資源不被其他進程侵犯，并且進程執(zhí)行的結(jié)果與其他并發(fā)進程執(zhí)行時的相對速度無關(guān)。,2,3.1.1 進程間的相互作用,進程之間常常相互作用，存在某種彼此依賴或相互制約的關(guān)系,：,同步和互斥關(guān)系。,根據(jù)進程意識到其他進程的存在程度不同，可將進程間的相互作用劃分為：,進程互不覺察,、,進程間接覺察,、,進程直接覺察。,3,3.1.2 進程間的相互競爭,并發(fā)進程在競爭使用同一資源時將產(chǎn)生沖突。,進程間的競爭面臨3個控制問題：,互斥,死鎖,饑餓,競爭的控制不可避免地涉及到操作系統(tǒng)，因為是操作系統(tǒng)分配資源，另外，進程自身也必須能以某種方式表達互斥的要求,。,4,3.1.2 進程間的相互競爭,臨界資源,:,在同一時刻只允許一個進程訪問的資源稱為臨界資源。,臨界區(qū),(,段,):,訪問臨界資源的那一部分程序稱為臨界區(qū)（段）。,5,3.1.3 進程間的相互合作,1.通過共享合作,這些進程并不是通過名字察覺到對方，而是通過共享訪問間接察覺。進程間通過共享方式進行合作。除互斥、死鎖和饑餓外，保證數(shù)據(jù)的一致性也是一個潛在的控制問題。,6,3.1.3 進程間的相互合作,2.通過通信合作,進程通信是指進程之間可直接以較高的效率傳遞較多數(shù)據(jù)的信息交換方式。這種方式中采用的是通信機構(gòu)，在進程通信時往往以消息形式傳遞信息。,因為在消息傳遞中不存在共享，所以這種形式的合作不需要互斥，但是還存在死鎖和饑餓問題。,7,3.1.4 互斥的要求,并發(fā)進程的成功完成需要有定義臨界段和實現(xiàn)互斥的能力，這是任何并發(fā)進程方案的基礎(chǔ)。解決互斥問題必須滿足以下要求：,互斥執(zhí)行,執(zhí)行非臨界段的進程不能受到其他進程的干擾,有限的等待,沒有進程相對速度和數(shù)目的假設(shè),進程進入到臨界段中的時間有限,8,3.2 互斥軟件解決方法,軟件方法對并發(fā)進程不提供任何支持，因此，無論是系統(tǒng)程序或應(yīng)用程序，進程都要同其他進程合作以解決互斥，它們從程序設(shè)計語言和操作系統(tǒng)那里得不到任何支持。軟件方法易引起較高的進程附和較多的錯誤，但有利于深刻理解并發(fā)的復(fù)雜性。,9,3.2.1,Dekker,算法,Dekker,算法的優(yōu)點在于它描述了并發(fā)進程發(fā)展過程中遇到的大部分共同問題。任何互斥都必須依賴于一些硬件上的基本約束，其中最基本的約束是任一時刻只能有一個進程訪問內(nèi)存中某一位置。,10,3.2.1,Dekker,算法,1.第1種途徑,這種方法保證了互斥，但它只記住了允許哪個進程進入其臨界段，未記住每個進程的狀態(tài)。,var,turn:0.1;turn,為共享的全局變量,PROCESS 0 PROCESS 1,while,turn0,do,nothing;,while,turn1,do,nothing,；,critical section;critical section;,turn:=1;turn:=0;,11,3.2.1,Dekker,算法,2.第2種途徑,這種解決方法依賴于進程執(zhí)行的相對速度,共享的全局變量是：,var,flag:,array,0.1,of,boolean,;,它被初始化為,false,PROCESS 0 PROCESS 1,while,flag1,do,nothing;,while,flag0,do,nothing;,flag0:=true;flag1:=true;,critical section;critical section;,flag0:=false;flag1:=false;,12,3.2.1,Dekker,算法,3.第3種途徑,這種方法保證了互斥但會導(dǎo)致死鎖問題。,PROCESS 0 PROCESS 1,flag0:=true;flag1:=true;,while,flag1,do,nothing;,while,flag0,do,nothing;,critical section;critical section;,flag0:=false;flag1:=false;,13,3.2.1,Dekker,算法,4.第4種途徑,PROCESS 0 PROCESS 1,flag0:=true;flag1:=true;,while,flag1,do,nothing;,while,flag0,do,nothing;,begin,begin,flag0:=false;flag1:=false;,delay for a short time;delay for a short time;,flag0:=true;flag1:=true;,end,;,end,;,critical section;critical section;,flag0:=false,；,flag1:=false;,14,3.2.1,Dekker,算法,5.一個正確的解決方法,設(shè)計一個“指示”小屋，小屋內(nèi)的黑板標明“,turn”,，當(dāng),P,0,想進入其臨界段時，置自己的,flag,為“,true”,，這時它去查看,P,1,的,flag,，如果是“,false”,，則,P,0,就立即進入自己的臨界段，反之,P,0,去查看“指示”小屋，如果,turn=0,，那么它知道自己應(yīng)該堅持并不時去查看,P,1,的小屋，,P,1,將覺察到它應(yīng)該放棄并在自己的黑板上寫上“,false”,，以允許,P,0,繼續(xù)執(zhí)行。,P,0,執(zhí)行完臨界段后，它將,flag,置為“,false”,以釋放臨界段，并且將,turn,置為,1,，將進入權(quán)交給,P,1,。,15,3.2.2,Peterson,算法,Dekker,算法可以解決互斥問題，但是，其復(fù)雜的程序難于理解，其正確性難于證明。,Peterson,給出了一個簡單的方法。下面是一個兩進程互斥的簡單解決方法，進一步可將,Peterson,算法推廣到多個進程的情況。,16,3.2.2,Peterson,算法,var,flag,:array,0.1,of,boolean,;,flag1:,=true;,turn:0.1;turn:=0;,procedure,P,0,;,while,flag0,and,turn=0,do,nothing;,begin,critical section;,repeat,flag1:=false;,flag0:=true;remainder,turn:=1;,forever,while,flag1,and,turn=1,do,nothing;,end,;,critical section;,begin,flag0:=false;flag0:=false;,remainder flag1:=false;,forever,turn:=1;,end,;,parbegin,procedure,P,1,;P,0,;P,1,begin,parend,repeat end.,17,3.3 互斥硬件解決方法,完全利用軟件方法來解決進程互斥進入臨界區(qū)的問題有一定的難度，且有很大局限性，現(xiàn)在有許多計算機提供了一些可以解決臨界區(qū)問題的特殊的硬件指令。,硬件方法通過特殊的機器指令實現(xiàn)互斥，可以降低開銷。,18,3.3.1 禁止中斷,在單處理機中，禁止進程被中斷即可保證互斥，通過操作系統(tǒng)內(nèi)核定義的禁止和允許中斷的原語就可獲得這種能力。進程執(zhí)行臨界段時不能被中斷。,優(yōu)點：,在單處理機中可保證互斥。,缺點：,代價較高，使執(zhí)行效率顯著降低,在多處理機系統(tǒng)中，禁止中斷不能保證互斥,19,3.3.2 使用機器指令,1,.,特殊的機器指令,在多處理機系統(tǒng)中，多個處理機共享一個共同的主存，這里并沒有主/從關(guān)系，也沒有實現(xiàn)互斥的中斷機制。許多系統(tǒng)都提供了一些特殊的硬件指令，允許我們在一個存儲周期內(nèi)去測試和修改一個字的內(nèi)容（,Test and Set,指令），或者交換兩個字的內(nèi)容（,Exchange,指令）等等。這些特殊指令可以用來解決臨界段問題。,20,3.3.2 使用機器指令,2.,機器指令方法的特性,優(yōu)點：,可用于含有任意數(shù)量進程的單處理機或共享主存的多處理機；,比較簡單，易于驗證；,可支持多個臨界段，每個臨界段用各自的變量加以定義。,缺點：,采用,busy-waiting,技術(shù)，進程等待進入臨界段時耗費處理機時間；,可能產(chǎn)生饑餓；,可能產(chǎn)生死鎖。,21,3.4 信號量,信號量是一個整型變量，除對其初始化外，它可由兩個不可中斷的,P、V,操作存取。,不論是采用一般信號量還是二元信號量，進程都將排隊等候信號量，但這并不意味著進程移出的順序與隊列次序相同。,基本原則：兩個或多個進程可通過單一的信號量展開合作，即進程在某一特定的地方停止執(zhí)行，直到某個特定的信號量到來為止。通過信號量，任何復(fù)雜的合作要求都可被滿足,。,22,3.4 信號量,P,操作,Wait(s):,s.count:=s.count-1,If s.count0,Then begin,將該進程置入,s.queue,阻塞該進程,End;,V,操作,s.count:=s.count+1,If s.count=0,Then begin,將進程 從,s.queue,中移出，置入就緒隊列,End;,23,3.4.1 用信號量解決互斥問題,信號量的互斥算法可以用小屋模型來描述。除了黑板外，小屋中還有一個大冰箱。某進程進入小屋后執(zhí)行,wait,操作將黑板上的數(shù)減,1,，這時，如果黑板上的值非負，它就進入臨界段，反之它就進入冰箱內(nèi)冬眠。這時，就允許另一進程進入小屋。當(dāng)一個進程完成其臨界段后，它進入小屋執(zhí)行,signal,，將黑板上的值加,1,，這時如果黑板上的值為非正數(shù)，它就從冰箱中喚醒一個進程。,24,3.4.2 用信號量解決生產(chǎn)者/消費者問題,問題描述如下：一個或更多的生產(chǎn)者生產(chǎn)出某種類型的數(shù)據(jù),(,記錄、字符,),，并把它們送入緩沖區(qū)，惟一的一個消費者一次從緩沖區(qū)中取走一個數(shù)據(jù)，系統(tǒng)要保證緩沖區(qū)操作不發(fā)生重疊，即在任一時刻只能有一方,(,生產(chǎn)者或消費者,),訪問緩沖區(qū)。,25,3.4.2 用信號量解決生產(chǎn)者/消費者問題,用二元信號量來解決此問題。在任何時候生產(chǎn)者,(P),都可向緩沖區(qū)中添加數(shù)據(jù)，在添加數(shù)據(jù)前，,P,執(zhí)行,waitB,(s),，然后執(zhí)行,signalB,(s),以防止在添加過程中，別的消費者,(C),或,P,訪問緩沖區(qū)。在進入到臨界段時，,P,將增加,n,的值，如果,n=1,則在此次添加數(shù)據(jù)前緩沖區(qū)為空，于是,P,執(zhí)行,signalB,(delay),并將這個情況通知,C,。,C,最初執(zhí)行,waitB,(delay),來等待,P,生產(chǎn)出第一個數(shù)據(jù)，然后取走數(shù)據(jù)并在臨界段中減小,n,的值。如果,P,總保持在,C,前面，那么,C,就不會因為信號量,delay,而阻塞，因為,n,總是正數(shù)，這樣,P,和,C,都能順利地工作。這個方法也存在缺陷有可能導(dǎo)致死鎖。,26,3.4.2 用信號量解決生產(chǎn)者/消費者問題,解決這個問題的一個方法是引入一個附加變量，它在消費者的臨界段中設(shè)置。這樣，就不會出現(xiàn)死鎖了。,使用一般信號量可以得到另一種解決方法，變量,n,是一個信號量，它的值等于緩沖區(qū)中的數(shù)據(jù)項數(shù)。,27,3.4.3,信號量的實現(xiàn),wait,和,signal,操作都必須作為原子操作實現(xiàn)。顯然，用硬件方法或固件方法都可解決這一問題，而且還有其他解決方法。盡管,wait,和,signal,操作執(zhí)行的時間較短，但因包含了忙,-,等，故忙,-,等占用的時間是主要的,。,對單處理機系統(tǒng)而言，可以在,wait,和,s