35產(chǎn)生死鎖的原因和必要條件-資料下載頁
2024-09-30 10:31本頁面
【導(dǎo)讀】源，從而提高了資源的利用率。發(fā)生一種隨機(jī)性故障――死鎖。產(chǎn)生死鎖的必要條件。處理死鎖的基本方法。所有進(jìn)程的資源分配工作，都由OS完成。研究資源分配時(shí)，我們必須搞清該資源。正是引起系統(tǒng)死鎖的原因。不可搶占資源—指只有占用者進(jìn)程不再需要使。占有者進(jìn)程使用資源過程中強(qiáng)行搶占。根據(jù)使用期限；永久資源和臨時(shí)性資源。死鎖Deadlock：是計(jì)算機(jī)系統(tǒng)中多道程序并發(fā)。外力作用，這些進(jìn)程將永遠(yuǎn)不能再向前推進(jìn)。陷入死鎖狀態(tài)的進(jìn)程稱為死鎖進(jìn)程，所占用的。請求和釋放資源的順序不當(dāng)，導(dǎo)致進(jìn)程的死鎖。兩個(gè)進(jìn)程并發(fā)執(zhí)行，按下列。求新的資源的同時(shí)，保持對某些資源的占有。使用r1和r2;使用r1和r2. 的信件S1來到后再向P3發(fā)送信件S2；這種做法許多場合行不通。種種死鎖防止辦法施加于資源。采用剝奪式調(diào)度方法可破壞第三個(gè)條。當(dāng)進(jìn)程在申請資源未獲準(zhǔn)許的情況下,去等待，以后再一起向系統(tǒng)提出申請,
【正文】 系統(tǒng)中某個(gè)時(shí)刻 S為死鎖狀態(tài)的充要條件是S時(shí)刻系統(tǒng)的資源分配圖是不可完全簡化的。 在經(jīng)過一系列的簡化后，若能消去圖中的所有邊，使所有的進(jìn)程都成為孤立結(jié)點(diǎn)，則稱該圖是可完全簡化的；反之的是不可完全簡化的。 P1 P2 r1 r2 P1 P2 r1 r2 P1 P2 r1 r2 49 ? 死鎖的恢復(fù) 。 是與檢測死鎖相配套的一種措施 ， 用于將進(jìn)程從死鎖狀態(tài)下解脫出來 。 常用的方法有： ? 1撤消進(jìn)程；最簡單撤消進(jìn)程的方法是使全部死鎖的進(jìn)程夭折掉；另一方法是按照某種順序逐個(gè)地撤消進(jìn)程 ， 直至有足夠的資源可用 ， 死鎖狀態(tài)消除為止 2掛起進(jìn)程（剝奪資源）。使用掛起 /激活機(jī)構(gòu)掛起一些進(jìn)程，剝奪它們的資源以解除死鎖，待條件滿足時(shí)，再激活進(jìn)程。目前掛起法比較受到重視。 50 ? 1． （ 北大 95） 一個(gè) OS有 20個(gè)進(jìn)程 ， 競爭使用 65個(gè)同類資源 ， 申請方式是逐個(gè)進(jìn)行的 ， 一旦某個(gè)進(jìn)程獲得它所需要的全部資源 ， 則立即歸還所有資源 。 每個(gè)進(jìn)程最多使用三個(gè)資源 。 若僅考慮這類資源 ， 該系統(tǒng)有無可能產(chǎn)生死鎖 ， 為什么 ？ ? 2． 死鎖和饑餓的主要差別是什么 ？ 例題 51 ? 1 答：不可能 。 因?yàn)樗梨i產(chǎn)生的原因有兩點(diǎn)：系統(tǒng)資源不足或推進(jìn)順序不當(dāng) ， 在本題中 ， 進(jìn)程所需的最大資源數(shù)為 60， 而系統(tǒng)共有該類資源 65個(gè) ， 其資源數(shù)已足夠系統(tǒng)內(nèi)各進(jìn)程使用 。 ? 2 答：簡言之 ， 死鎖是某進(jìn)程等待一個(gè)不會(huì)發(fā)生的事件的一種現(xiàn)象；而饑餓現(xiàn)象是某進(jìn)程正等待這樣一個(gè)事件 ， 它發(fā)生了但總是受到其它進(jìn)程的影響 ， 以至輪不到 （ 或很難輪到 ） 該進(jìn)程 。 52 銀行家算法的基本思想 (1) ?系統(tǒng)中的所有進(jìn)程進(jìn)入進(jìn)程集合 , ?在安全狀態(tài)下系統(tǒng)收到進(jìn)程的資源請求后 ,先把資源試探性分配給它。 ?系統(tǒng)用剩下的可用資源和進(jìn)程集合中其他進(jìn)程還要的資源數(shù)作比較，在進(jìn)程集合中找到剩余資源能滿足最大需求量的進(jìn)程 ,從而 ,保證這個(gè)進(jìn)程運(yùn)行完畢并歸還全部資源。 53 銀行家算法的基本思想 (2) ? 把這個(gè)進(jìn)程從集合中去掉 , 系統(tǒng)的剩余資源更多了 ,反復(fù)執(zhí)行上述步驟。 ? 最后 ,檢查進(jìn)程集合 ,若為空表明本次申請可行 ,系統(tǒng)處于安全狀態(tài) ,可實(shí)施本次分配 。否則 ,有進(jìn)程執(zhí)行不完，系統(tǒng)處于不安全狀態(tài) ,本次資源分配暫不實(shí)施 ,讓申請進(jìn)程等待。 54 死鎖的檢測與解除 1 資源分配圖和死鎖定理 2 借助于死鎖的安全性測試算法的死鎖檢測 3 warshall傳遞閉包算法的死鎖檢測 55 簡化進(jìn)程 資源分配圖檢測系統(tǒng)是否處于死鎖狀態(tài) (1) (1)如果進(jìn)程 資源分配圖中無環(huán)路，則此時(shí)系統(tǒng)沒有發(fā)生死鎖。 (2)如果進(jìn)程 資源分配圖中有環(huán)路，且每個(gè)資源類中僅有一個(gè)資源，則系統(tǒng)中發(fā)生了死鎖，此時(shí)，環(huán)路是系統(tǒng)發(fā)生死鎖的充要條件，環(huán)路中的進(jìn)程便為死鎖進(jìn)程。 56 簡化進(jìn)程 資源分配圖檢測系統(tǒng)是否處于死鎖狀態(tài) (2) (3)如果進(jìn)程 資源分配圖中有環(huán)路 ， 且涉及的資源類中有多個(gè)資源 ， 則環(huán)路的存在只是產(chǎn)生死鎖的必要條件而不是充分條件 。 57 簡化進(jìn)程 資源分配圖檢測系統(tǒng)是否處于死鎖狀態(tài) (3) ?如果能在進(jìn)程 資源分配圖中消去此進(jìn)程的所有請求邊和分配邊 ， 成為孤立結(jié)點(diǎn) 。 經(jīng)一系列簡化 ， 使所有進(jìn)程成為孤立結(jié)點(diǎn) ， 則該圖是可完全簡化的；否則則稱該圖是不可完全簡化的 。 58 簡化進(jìn)程 資源分配圖檢測系統(tǒng)是否處于死鎖狀態(tài) (4) ?系統(tǒng)為死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)該狀態(tài)的進(jìn)程 資源分配圖是不可完全簡化的 。 該充分條件稱為死鎖定理 。 59 死鎖的 具體 檢測和解除 方法 (1) 借助于死鎖的安全性測試算法來實(shí)現(xiàn)。今定義布爾型向量 possible[k]，k=1,..,n。檢測死鎖算法如下： （ 1） currentavail:=available； （ 2）在 rest中查每一個(gè)進(jìn)程 Pk,如果claim[k,*]alloc[k,*]=0，則possible[k]:=true；否則possible[k]:=false；這里 k=1,..,n。 60 死鎖的 具體 檢測和解除 方法 (2) （ 3） 在 rest中找一個(gè)進(jìn)程 Pk，需滿足條件： possible[k]=falseamp。(request[*]≤ currentavail) 找到這樣的 Pk便轉(zhuǎn)（ 4）；否則轉(zhuǎn)（ 5） ； （ 4） currentavail:=currentavail+allocation；possible[k]:=true； 然后轉(zhuǎn)（ 3） ； (5) 如果對 k=1,..,n若 possible[k]=true不成立，那么，系統(tǒng)出現(xiàn)了死鎖，并且possible[k]=false的 Pk為死鎖進(jìn)程。 61 死鎖的 具體 檢測和解除 方法 (3) 死鎖檢測算法與死鎖避免算法是類似的，不同在于前者考慮了檢查每個(gè)進(jìn)程還需要的所有資源能否滿足要求；而后者則僅要根據(jù)進(jìn)程的當(dāng)前申請資源量來判斷系統(tǒng)是否進(jìn)入了不安全狀態(tài)。 62 (1) ?立即結(jié)束所有進(jìn)程的執(zhí)行 ， 并重新啟動(dòng)操作系統(tǒng) 。 方法簡單 ,但以前工作全部作廢 ,損失可能很大 。 ?撤銷陷于死鎖的所有進(jìn)程 ,解除死鎖繼續(xù)運(yùn)行 。 63 死鎖的解除 (2) ?逐個(gè)撤銷陷于死鎖的進(jìn)程 ,回收其資源 ,直至死鎖解除 。 ?剝奪陷于死鎖的進(jìn)程占用的資源 ，但并不撤銷它 , 直至死鎖解除 。 64 死鎖的解除 (3) ? 根據(jù)系統(tǒng)保存的 checkpoint,讓所有進(jìn)程回退 ,直到解除死鎖 。 ? 當(dāng)檢測到死鎖時(shí) ， 如果存在某些未卷入死鎖的進(jìn)程 ， 而這些進(jìn)程隨著建立一些新的抑制進(jìn)程能執(zhí)行到結(jié)束 ， 則它們可能釋放足夠的資源來解除死鎖 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1