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