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

上傳人:hjk****65 文檔編號(hào):248184814 上傳時(shí)間:2024-10-22 格式:PPT 頁數(shù):49 大?。?38.50KB
收藏 版權(quán)申訴 舉報(bào) 下載
操作系統(tǒng)ppt課件第3章_第1頁
第1頁 / 共49頁
操作系統(tǒng)ppt課件第3章_第2頁
第2頁 / 共49頁
操作系統(tǒng)ppt課件第3章_第3頁
第3頁 / 共49頁

下載文檔到電腦,查找使用更方便

15 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《操作系統(tǒng)ppt課件第3章》由會(huì)員分享,可在線閱讀,更多相關(guān)《操作系統(tǒng)ppt課件第3章(49頁珍藏版)》請(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 *讀者/寫者問題,3.8 系統(tǒng)舉例(略),1,3.1 并發(fā)原理,在單處理機(jī)多道程序的系統(tǒng)中,進(jìn)程的并發(fā)執(zhí)行方式是插入執(zhí)行,表面看起來進(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ì)速度無關(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)程間的相互競爭,并發(fā)進(jìn)程在競爭使用同一資源時(shí)將產(chǎn)生沖突。,進(jìn)程間的競爭面臨3個(gè)控制問題:,互斥,死鎖,饑餓,競爭的控制不可避免地涉及到操作系統(tǒng),因?yàn)槭遣僮飨到y(tǒng)分配資源,另外,進(jìn)程自身也必須能以某種方式表達(dá)互斥的要求,。,4,3.1.2 進(jìn)程間的相互競爭,臨界資源,:,在同一時(shí)刻只允許一個(gè)進(jìn)程訪問的

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

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

5、須依賴于一些硬件上的基本約束,其中最基本的約束是任一時(shí)刻只能有一個(gè)進(jì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)致死鎖問題。,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,算法可以解決互斥問題,但是,其復(fù)雜的程序難于理解,其正確性難于證明。,Peterson,給出了一個(gè)簡單的方法。下面是一個(gè)兩進(jì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 互斥硬件解決方法,完全利用軟件方法來解決進(jìn)程互斥進(jìn)入臨界區(qū)的問題有一定的難度,且有很大局限性,現(xiàn)在有許多計(jì)算機(jī)提供了一些可以解決臨界區(qū)問題的特殊的硬件指令。,硬件方法通過特殊的機(jī)器指令實(shí)現(xiàn)互斥,可以降低開銷。,18,3.3.1 禁止中斷,在單處理機(jī)中,禁止進(jìn)程被中斷即可保證互斥,通過操作系統(tǒng)內(nèi)核定義的禁止和允許中斷的原語就可獲得這種能力。進(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)都提供了一些特殊的硬件指令,允許我們在一個(gè)存儲(chǔ)周期內(nèi)去測試和修改一個(gè)字的內(nèi)容(,Test and Set,指令),或者交換兩個(gè)字的內(nèi)容(,Exchange,指令)等等。這些特殊指令可以用來解決臨界段問題。,20,3.3.2 使用機(jī)器指令,2.,機(jī)器指令方法的特性,優(yōu)點(diǎn):,可用于含有任意數(shù)量進(jìn)程的單處理機(jī)或共享主存的多處理機(jī);,比較簡單,易于驗(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)程可通過單一的信號(hào)量展開合作,即進(jìn)程在某一特定的地方停止執(zhí)行,直到某個(gè)特定的信號(hào)量到來為止。通過信號(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)量解決互斥問題,信號(hào)量的互斥算法可以用小屋模型來描述。除了黑板外,小屋中還有一個(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)者問題,問題描述如下:一個(gè)或更多的生產(chǎn)者生產(chǎn)出某種類型的數(shù)據(jù),(,記錄、字符,),,并把它們送入緩沖區(qū),惟一的一個(gè)消費(fèi)者一次從緩沖區(qū)中取走一個(gè)數(shù)據(jù),系統(tǒng)要保證緩沖區(qū)操作不發(fā)生重疊,即在任一時(shí)刻只能有一方,(,生產(chǎn)者或消費(fèi)者,),訪問緩沖區(qū)。,25,3.4.2 用信號(hào)量解決生產(chǎn)者/消費(fèi)者問題,用二元信號(hào)量來解決此問題。在任何時(shí)候生產(chǎn)者,(P),都可向緩沖區(qū)中添加數(shù)據(jù),在添加數(shù)據(jù)前,,P,執(zhí)行,waitB,(s),,然后執(zhí)行,signalB,(s),以防止在添加過程中,別的消費(fèi)者,(C),或,P,

16、訪問緩沖區(qū)。在進(jìn)入到臨界段時(shí),,P,將增加,n,的值,如果,n=1,則在此次添加數(shù)據(jù)前緩沖區(qū)為空,于是,P,執(zhí)行,signalB,(delay),并將這個(gè)情況通知,C,。,C,最初執(zhí)行,waitB,(delay),來等待,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)者問題,解決這個(gè)問題的一個(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)。顯然,用硬件方法或固件方法都可解決這一問題,而且還有其他解決方法。盡管,wait,和,signal,操作執(zhí)行的時(shí)間較短,但因包含了忙,-,等,故忙,-,等占用的時(shí)間是主要的,。,對(duì)單處理機(jī)系統(tǒng)而言,可以在,wait,和,s

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔

相關(guān)搜索

關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!