資源描述：
《linux處理機(jī)調(diào)度與死鎖2.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、7.3死鎖的概念7.3.1死鎖的定義可重用資源(reusableresource):各個進(jìn)程可以輪流使用，如處理機(jī)、內(nèi)存、I/0外設(shè)、文件等都是可重用資源，在使用可重用資源時可能出現(xiàn)的死鎖（Deadlock）。通常是由于各進(jìn)程巳擁有部分資源，同時請求其他進(jìn)程已占有的資源，從而造成永遠(yuǎn)等待?？上馁Y源(consumableresource):是指可以動態(tài)生成和動態(tài)消耗的資源，一般不限制數(shù)量，如中斷、信號量、消息、緩沖區(qū)等都是可消耗資源。由于可消耗資源的生成和消耗存在依賴關(guān)系，因此他們的使用也可能因為雙方都等待對方生成資源而形成死
2、鎖。1圖7-1進(jìn)程之間通信時的死鎖2死鎖的定義:死鎖是一組并發(fā)進(jìn)程,它們共享系統(tǒng)的某些資源,該組進(jìn)程中每個進(jìn)程都已經(jīng)占有了部分資源,但都在不釋放自己占有資源的情況下要求獲得被其它進(jìn)程已經(jīng)占有的資源,從而造成它們相互等待,永遠(yuǎn)不能繼續(xù)推進(jìn)的狀態(tài).說明：①參與死鎖的進(jìn)程最少是兩個（兩個以上進(jìn)程才會出現(xiàn)死鎖）。②參與死鎖的進(jìn)程至少有兩個已經(jīng)占有資源。③參與死鎖的所有進(jìn)程都在等待事件。④參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集。37.3.2資源分配圖(2)凡屬于E中的一個邊e∈E，都連接著P中的一個結(jié)點和R中的一個結(jié)點，e={pi,r
3、j}是資源請求邊，由進(jìn)程pi指向資源rj，它表示進(jìn)程pi請求一個單位的rj資源。e={rj,pi}是資源分配邊，由資源rj指向進(jìn)程pi,它表示把一個單位的資源rj分配給進(jìn)程pi。該圖是由一組結(jié)點V和一組邊E所組成的：G=（V，E），具有以下形式的定義和限制：（1）V被分為兩個互斥的子集，一組進(jìn)程結(jié)點P={p1,p2,…,pn},一組資源結(jié)點R={r1,r2,…rn},47.3.3產(chǎn)生死鎖的原因產(chǎn)生死鎖的根本原因是:⒈資源不足，引起資源競爭⒉進(jìn)程推進(jìn)順序不合理5例:設(shè)有兩個進(jìn)程Pa和Pb,它們都需要使用系統(tǒng)內(nèi)的打印機(jī)和輸入機(jī).它
4、們的算法設(shè)計如下:設(shè)信號量s1代表輸入機(jī)資源可用數(shù)量,s1=1設(shè)信號量s2代表打印機(jī)資源可用數(shù)量,s2=1Pa:P(s2)…P(s1)…V(s2)…V(s1)Pb:P(s1)…P(s2)…V(s1)…V(s2)67.3.4死鎖產(chǎn)生的必要條件⑴互斥條件。進(jìn)程要求對所分配的資源進(jìn)行排他性使用，即在一段時間內(nèi)某資源僅為一個進(jìn)程所占用。⑵不剝奪條件。進(jìn)程所獲得的資源在未使用完畢之前，不能被其他進(jìn)程強(qiáng)行奪走，即只能由獲得該資源的進(jìn)程自己來釋放。⑶請求和保持條件。進(jìn)程每次申請所需要的一部分資源，在等待新資源的同時，進(jìn)程繼續(xù)占有已分配到的資
5、源。⑷循環(huán)等待條件。存在進(jìn)程資源的循環(huán)等待鏈，鏈中的每一個進(jìn)程已獲得資源，同時被鏈中的下一個進(jìn)程所請求。77.4預(yù)防死鎖解決死鎖問題的基本方法有：預(yù)防死鎖、避免死鎖、檢測死鎖和解除死鎖。除此之外還有鴕鳥算法和綜合措施。預(yù)防死鎖是指通過某種策略來限制并發(fā)進(jìn)程對資源的請求，使系統(tǒng)在任何時刻都不滿足死鎖的必要條件。就是在設(shè)計操作系統(tǒng)時，通過設(shè)置某些限制條件，去破壞死鎖四個必要條件中的一個或多個，來防止死鎖，使系統(tǒng)能預(yù)先排除死鎖的可能性。87.4.1摒棄請求和保持條件采用設(shè)備的靜態(tài)預(yù)先分配辦法,具體作法:作業(yè)調(diào)度程序在選擇作業(yè)時,只選
6、擇那些系統(tǒng)能滿足其運(yùn)行時所需的全部資源的作業(yè)投入運(yùn)行,并且在作業(yè)運(yùn)行前,將其所需的全部資源一次性地分配給該作業(yè).該方法的優(yōu)點和缺點如下：①簡單、安全、易于實現(xiàn)。②程序在運(yùn)行之前很難提出將要使用的全部設(shè)備。③直到所有資源滿足才能運(yùn)行，實際上某些資源可能要到運(yùn)行后期才會用到。④一個進(jìn)程運(yùn)行期間，對某些設(shè)備的使用時間很短，甚至不會用到。⑤作業(yè)的周轉(zhuǎn)時間被加長,系統(tǒng)資源的使用率被降低97.4.2摒棄不剝奪條件為了破壞不可剝奪條件，我們采用這樣的策略，一個已擁有資源的進(jìn)程，若它再提出新資源要求而不能立即得到滿足時，它必須釋放已經(jīng)擁有的所
7、有資源，以后需要時再重新申請。擁有資源的進(jìn)程在運(yùn)行過程中其資源可能被剝奪，從而破壞了不可剝奪條件。該方法實現(xiàn)復(fù)雜，被剝奪資源的進(jìn)程前期工作失效，重復(fù)申請和釋放資源給系統(tǒng)增加了開銷，系統(tǒng)要付出很大的代價。107.4.3摒棄環(huán)路等待條件為了破壞環(huán)路等待條件，采用有序資源分配策略。對申請資源的進(jìn)程規(guī)定：同類資源需一次申請，在獲得資源后，只能申請較高級號的資源，無權(quán)申請低級號資源和同類資源。對于低級號資源和同類資源申請，必須先釋放所有高級號的資源，然后再申請，否則不予分配。優(yōu)點：同前兩法相比，其資源利用率和系統(tǒng)吞吐量有較明顯的改善。缺
8、點：進(jìn)程實際需要資源的順序不一定與資源的編號一致，因此仍會造成資源浪費(fèi)，系統(tǒng)增加新設(shè)備較困難。117.4.4摒棄互斥條件互斥條件是由于設(shè)備本身特性所決定的,不能簡單的把其打破;只有通過改造設(shè)備特性實現(xiàn).具體辦法采用Spooling技術(shù),把獨(dú)占設(shè)備改造成共享設(shè)備來實現(xiàn).127.
