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

《操作系統(tǒng)ppt課件第3章》由會(huì)員分享，可在線閱讀，更多相關(guān)《操作系統(tǒng)ppt課件第3章（49頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,*,*,第3章 并發(fā)控制互斥與同步,本章知識(shí)點(diǎn)：,3.1 并發(fā)原理,3.2 互斥軟件解決方法,3.3,互斥硬件解決方法,3.4 信號(hào)量,3.5 管程,3.6 *消息傳遞,3.7 *讀者/寫者問(wèn)題,3.8 系統(tǒng)舉例（略）,1,3.1 并發(fā)原理,在單處理機(jī)多道程序的系統(tǒng)中，進(jìn)程的并發(fā)執(zhí)行方式是插入執(zhí)行，表面看起來(lái)進(jìn)程如同是同時(shí)執(zhí)行的。在多處理機(jī)系統(tǒng)中并發(fā)執(zhí)行方式有插入執(zhí)行和重疊執(zhí)行。,并發(fā)的存在要求操作系統(tǒng)必須能跟蹤大量活躍進(jìn)程,必須為每一活躍進(jìn)程分配資源，必須保護(hù)每一進(jìn)程的數(shù)據(jù)和物理資源不被其他進(jìn)程侵犯，并且

2、進(jìn)程執(zhí)行的結(jié)果與其他并發(fā)進(jìn)程執(zhí)行時(shí)的相對(duì)速度無(wú)關(guān)。,2,3.1.1 進(jìn)程間的相互作用,進(jìn)程之間常常相互作用，存在某種彼此依賴或相互制約的關(guān)系,：,同步和互斥關(guān)系。,根據(jù)進(jìn)程意識(shí)到其他進(jìn)程的存在程度不同，可將進(jìn)程間的相互作用劃分為：,進(jìn)程互不覺察,、,進(jìn)程間接覺察,、,進(jìn)程直接覺察。,3,3.1.2 進(jìn)程間的相互競(jìng)爭(zhēng),并發(fā)進(jìn)程在競(jìng)爭(zhēng)使用同一資源時(shí)將產(chǎn)生沖突。,進(jìn)程間的競(jìng)爭(zhēng)面臨3個(gè)控制問(wèn)題：,互斥,死鎖,饑餓,競(jìng)爭(zhēng)的控制不可避免地涉及到操作系統(tǒng)，因?yàn)槭遣僮飨到y(tǒng)分配資源，另外，進(jìn)程自身也必須能以某種方式表達(dá)互斥的要求,。,4,3.1.2 進(jìn)程間的相互競(jìng)爭(zhēng),臨界資源,:,在同一時(shí)刻只允許一個(gè)進(jìn)程訪問(wèn)的

3、資源稱為臨界資源。,臨界區(qū),(,段,):,訪問(wèn)臨界資源的那一部分程序稱為臨界區(qū)（段）。,5,3.1.3 進(jìn)程間的相互合作,1.通過(guò)共享合作,這些進(jìn)程并不是通過(guò)名字察覺到對(duì)方，而是通過(guò)共享訪問(wèn)間接察覺。進(jìn)程間通過(guò)共享方式進(jìn)行合作。除互斥、死鎖和饑餓外，保證數(shù)據(jù)的一致性也是一個(gè)潛在的控制問(wèn)題。,6,3.1.3 進(jìn)程間的相互合作,2.通過(guò)通信合作,進(jìn)程通信是指進(jìn)程之間可直接以較高的效率傳遞較多數(shù)據(jù)的信息交換方式。這種方式中采用的是通信機(jī)構(gòu)，在進(jìn)程通信時(shí)往往以消息形式傳遞信息。,因?yàn)樵谙鬟f中不存在共享，所以這種形式的合作不需要互斥，但是還存在死鎖和饑餓問(wèn)題。,7,3.1.4 互斥的要求,并發(fā)進(jìn)程的

4、成功完成需要有定義臨界段和實(shí)現(xiàn)互斥的能力，這是任何并發(fā)進(jìn)程方案的基礎(chǔ)。解決互斥問(wèn)題必須滿足以下要求：,互斥執(zhí)行,執(zhí)行非臨界段的進(jìn)程不能受到其他進(jìn)程的干擾,有限的等待,沒有進(jìn)程相對(duì)速度和數(shù)目的假設(shè),進(jìn)程進(jìn)入到臨界段中的時(shí)間有限,8,3.2 互斥軟件解決方法,軟件方法對(duì)并發(fā)進(jìn)程不提供任何支持，因此，無(wú)論是系統(tǒng)程序或應(yīng)用程序，進(jìn)程都要同其他進(jìn)程合作以解決互斥，它們從程序設(shè)計(jì)語(yǔ)言和操作系統(tǒng)那里得不到任何支持。軟件方法易引起較高的進(jìn)程附和較多的錯(cuò)誤，但有利于深刻理解并發(fā)的復(fù)雜性。,9,3.2.1,Dekker,算法,Dekker,算法的優(yōu)點(diǎn)在于它描述了并發(fā)進(jìn)程發(fā)展過(guò)程中遇到的大部分共同問(wèn)題。任何互斥都必

5、須依賴于一些硬件上的基本約束，其中最基本的約束是任一時(shí)刻只能有一個(gè)進(jìn)程訪問(wèn)內(nèi)存中某一位置。,10,3.2.1,Dekker,算法,1.第1種途徑,這種方法保證了互斥，但它只記住了允許哪個(gè)進(jìn)程進(jìn)入其臨界段，未記住每個(gè)進(jìn)程的狀態(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種途徑,這種解決方法依賴于進(jìn)程

6、執(zhí)行的相對(duì)速度,共享的全局變量是：,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種途徑,這種方法保證了互斥但會(huì)導(dǎo)致死鎖問(wèn)題。,PROCESS 0 PROCESS 1,flag0:=true;fla

7、g1:=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 tim

8、e;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.一個(gè)正確的解決方法,設(shè)計(jì)一個(gè)“指示”小屋，小屋內(nèi)的黑板標(biāo)明“,turn”,，當(dāng),P,0,想進(jìn)入其臨界段時(shí)，置自己的,flag,為“,true”,，這時(shí)它去查看,P,1,的,flag,，如果是“,false”,，則,P,0,就立即進(jìn)入自己的臨界段，反之,P,0,去查看“指示”小屋，如果,turn=0,，那

9、么它知道自己應(yīng)該堅(jiān)持并不時(shí)去查看,P,1,的小屋，,P,1,將覺察到它應(yīng)該放棄并在自己的黑板上寫上“,false”,，以允許,P,0,繼續(xù)執(zhí)行。,P,0,執(zhí)行完臨界段后，它將,flag,置為“,false”,以釋放臨界段，并且將,turn,置為,1,，將進(jìn)入權(quán)交給,P,1,。,15,3.2.2,Peterson,算法,Dekker,算法可以解決互斥問(wèn)題，但是，其復(fù)雜的程序難于理解，其正確性難于證明。,Peterson,給出了一個(gè)簡(jiǎn)單的方法。下面是一個(gè)兩進(jìn)程互斥的簡(jiǎn)單解決方法，進(jìn)一步可將,Peterson,算法推廣到多個(gè)進(jìn)程的情況。,16,3.2.2,Peterson,算法,var,flag,:

10、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:=f

11、alse;,forever,turn:=1;,end,;,parbegin,procedure,P,1,;P,0,;P,1,begin,parend,repeat end.,17,3.3 互斥硬件解決方法,完全利用軟件方法來(lái)解決進(jìn)程互斥進(jìn)入臨界區(qū)的問(wèn)題有一定的難度，且有很大局限性，現(xiàn)在有許多計(jì)算機(jī)提供了一些可以解決臨界區(qū)問(wèn)題的特殊的硬件指令。,硬件方法通過(guò)特殊的機(jī)器指令實(shí)現(xiàn)互斥，可以降低開銷。,18,3.3.1 禁止中斷,在單處理機(jī)中，禁止進(jìn)程被中斷即可保證互斥，通過(guò)操作系統(tǒng)內(nèi)核定義的禁止和允許中斷的原語(yǔ)就可獲得這種能力。進(jìn)程執(zhí)行臨界段時(shí)不能被中斷。,優(yōu)點(diǎn)：,在單處理機(jī)中可保證互斥。,缺點(diǎn)：,

12、代價(jià)較高，使執(zhí)行效率顯著降低,在多處理機(jī)系統(tǒng)中，禁止中斷不能保證互斥,19,3.3.2 使用機(jī)器指令,1,.,特殊的機(jī)器指令,在多處理機(jī)系統(tǒng)中，多個(gè)處理機(jī)共享一個(gè)共同的主存，這里并沒有主/從關(guān)系，也沒有實(shí)現(xiàn)互斥的中斷機(jī)制。許多系統(tǒng)都提供了一些特殊的硬件指令，允許我們?cè)谝粋€(gè)存儲(chǔ)周期內(nèi)去測(cè)試和修改一個(gè)字的內(nèi)容（,Test and Set,指令），或者交換兩個(gè)字的內(nèi)容（,Exchange,指令）等等。這些特殊指令可以用來(lái)解決臨界段問(wèn)題。,20,3.3.2 使用機(jī)器指令,2.,機(jī)器指令方法的特性,優(yōu)點(diǎn)：,可用于含有任意數(shù)量進(jìn)程的單處理機(jī)或共享主存的多處理機(jī)；,比較簡(jiǎn)單，易于驗(yàn)證；,可支持多個(gè)臨界段，每

13、個(gè)臨界段用各自的變量加以定義。,缺點(diǎn)：,采用,busy-waiting,技術(shù)，進(jìn)程等待進(jìn)入臨界段時(shí)耗費(fèi)處理機(jī)時(shí)間；,可能產(chǎn)生饑餓；,可能產(chǎn)生死鎖。,21,3.4 信號(hào)量,信號(hào)量是一個(gè)整型變量，除對(duì)其初始化外，它可由兩個(gè)不可中斷的,P、V,操作存取。,不論是采用一般信號(hào)量還是二元信號(hào)量，進(jìn)程都將排隊(duì)等候信號(hào)量，但這并不意味著進(jìn)程移出的順序與隊(duì)列次序相同。,基本原則：兩個(gè)或多個(gè)進(jìn)程可通過(guò)單一的信號(hào)量展開合作，即進(jìn)程在某一特定的地方停止執(zhí)行，直到某個(gè)特定的信號(hào)量到來(lái)為止。通過(guò)信號(hào)量，任何復(fù)雜的合作要求都可被滿足,。,22,3.4 信號(hào)量,P,操作,Wait(s):,s.count:=s.count-

14、1,If s.count0,Then begin,將該進(jìn)程置入,s.queue,阻塞該進(jìn)程,End;,V,操作,s.count:=s.count+1,If s.count=0,Then begin,將進(jìn)程 從,s.queue,中移出，置入就緒隊(duì)列,End;,23,3.4.1 用信號(hào)量解決互斥問(wèn)題,信號(hào)量的互斥算法可以用小屋模型來(lái)描述。除了黑板外，小屋中還有一個(gè)大冰箱。某進(jìn)程進(jìn)入小屋后執(zhí)行,wait,操作將黑板上的數(shù)減,1,，這時(shí)，如果黑板上的值非負(fù)，它就進(jìn)入臨界段，反之它就進(jìn)入冰箱內(nèi)冬眠。這時(shí)，就允許另一進(jìn)程進(jìn)入小屋。當(dāng)一個(gè)進(jìn)程完成其臨界段后，它進(jìn)入小屋執(zhí)行,signal,，將黑板上的值加,1

15、,，這時(shí)如果黑板上的值為非正數(shù)，它就從冰箱中喚醒一個(gè)進(jìn)程。,24,3.4.2 用信號(hào)量解決生產(chǎn)者/消費(fèi)者問(wèn)題,問(wèn)題描述如下：一個(gè)或更多的生產(chǎn)者生產(chǎn)出某種類型的數(shù)據(jù),(,記錄、字符,),，并把它們送入緩沖區(qū)，惟一的一個(gè)消費(fèi)者一次從緩沖區(qū)中取走一個(gè)數(shù)據(jù)，系統(tǒng)要保證緩沖區(qū)操作不發(fā)生重疊，即在任一時(shí)刻只能有一方,(,生產(chǎn)者或消費(fèi)者,),訪問(wèn)緩沖區(qū)。,25,3.4.2 用信號(hào)量解決生產(chǎn)者/消費(fèi)者問(wèn)題,用二元信號(hào)量來(lái)解決此問(wèn)題。在任何時(shí)候生產(chǎn)者,(P),都可向緩沖區(qū)中添加數(shù)據(jù)，在添加數(shù)據(jù)前，,P,執(zhí)行,waitB,(s),，然后執(zhí)行,signalB,(s),以防止在添加過(guò)程中，別的消費(fèi)者,(C),或,P,

16、訪問(wèn)緩沖區(qū)。在進(jìn)入到臨界段時(shí)，,P,將增加,n,的值，如果,n=1,則在此次添加數(shù)據(jù)前緩沖區(qū)為空，于是,P,執(zhí)行,signalB,(delay),并將這個(gè)情況通知,C,。,C,最初執(zhí)行,waitB,(delay),來(lái)等待,P,生產(chǎn)出第一個(gè)數(shù)據(jù)，然后取走數(shù)據(jù)并在臨界段中減小,n,的值。如果,P,總保持在,C,前面，那么,C,就不會(huì)因?yàn)樾盘?hào)量,delay,而阻塞，因?yàn)?n,總是正數(shù)，這樣,P,和,C,都能順利地工作。這個(gè)方法也存在缺陷有可能導(dǎo)致死鎖。,26,3.4.2 用信號(hào)量解決生產(chǎn)者/消費(fèi)者問(wèn)題,解決這個(gè)問(wèn)題的一個(gè)方法是引入一個(gè)附加變量，它在消費(fèi)者的臨界段中設(shè)置。這樣，就不會(huì)出現(xiàn)死鎖了。,使用一般信號(hào)量可以得到另一種解決方法，變量,n,是一個(gè)信號(hào)量，它的值等于緩沖區(qū)中的數(shù)據(jù)項(xiàng)數(shù)。,27,3.4.3,信號(hào)量的實(shí)現(xiàn),wait,和,signal,操作都必須作為原子操作實(shí)現(xiàn)。顯然，用硬件方法或固件方法都可解決這一問(wèn)題，而且還有其他解決方法。盡管,wait,和,signal,操作執(zhí)行的時(shí)間較短，但因包含了忙,-,等，故忙,-,等占用的時(shí)間是主要的,。,對(duì)單處理機(jī)系統(tǒng)而言，可以在,wait,和,s