計(jì)算機(jī)操作系統(tǒng) 第三版 第三章處理機(jī)調(diào)度

第三章處理機(jī)調(diào)度與死鎖處理機(jī)管理的工作是對(duì)CPU資源進(jìn)行合理的分配使用，以提高處理機(jī)利用率，并使各用戶公平地得到處理機(jī)資源。要解決的問(wèn)題WHAT：按什么原則分配CPU

—進(jìn)程調(diào)度算法WHEN：何時(shí)分配CPU

—進(jìn)程調(diào)度的時(shí)機(jī)HOW：如何分配CPU

—CPU調(diào)度過(guò)程（進(jìn)程的上下文切換）作業(yè)是任務(wù)實(shí)體，進(jìn)程是完成任務(wù)的執(zhí)行實(shí)體;沒(méi)有作業(yè)任務(wù)，進(jìn)程無(wú)事可干，沒(méi)有進(jìn)程，作業(yè)任務(wù)沒(méi)法完成。一個(gè)作業(yè)可由多個(gè)進(jìn)程組成，且必須至少有一個(gè)進(jìn)程，但反過(guò)來(lái)不成立。作業(yè)概念更多地用在批處理操作系統(tǒng)，而進(jìn)程則可以用在各種多道程序設(shè)計(jì)系統(tǒng)。作業(yè)是用戶向計(jì)算機(jī)提交任務(wù)的任務(wù)實(shí)體。進(jìn)程是計(jì)算機(jī)為完成用戶任務(wù)而設(shè)置的執(zhí)行實(shí)體，是系統(tǒng)分配資源的基本單位。一個(gè)作業(yè)可由多個(gè)進(jìn)程組成，且必須至少有一個(gè)進(jìn)程，但反過(guò)來(lái)不成立。作業(yè)和進(jìn)程的關(guān)系

處理機(jī)三級(jí)調(diào)度1.高級(jí)(Long-term)調(diào)度——作業(yè)調(diào)度

作業(yè)調(diào)度用于決定把外存井上處于作業(yè)后備隊(duì)列上的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。在批處理系統(tǒng)中，作業(yè)是先駐留在外存的輸入井上的，因此需要有作業(yè)調(diào)度；在分時(shí)系統(tǒng)中，通過(guò)鍵盤(pán)輸入的命令和數(shù)據(jù)直接進(jìn)入內(nèi)存，無(wú)需作業(yè)調(diào)度。2.低級(jí)(Short-term)調(diào)度——進(jìn)程調(diào)度

進(jìn)程調(diào)度決定就緒隊(duì)列中哪個(gè)進(jìn)程將獲得處理機(jī)，然后由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的操作。進(jìn)程調(diào)度是最基本的調(diào)度，任何操作系統(tǒng)都有進(jìn)程調(diào)度。低級(jí)調(diào)度：最基本。各類0S必須具有的功能。中級(jí)調(diào)度：較完善的OS中，引入其來(lái)改善內(nèi)存的利用率和提高作業(yè)的吞吐量。高級(jí)調(diào)度：批處理OS必須配置，純粹的分時(shí)或?qū)崟r(shí)OS中，通常無(wú)須配置。提交狀態(tài)收容狀態(tài)完成狀態(tài)外存內(nèi)存分級(jí)調(diào)度作業(yè)的狀態(tài)及其轉(zhuǎn)換就緒等待就緒等待執(zhí)行輸入管理系統(tǒng)交換調(diào)度線程調(diào)度進(jìn)程調(diào)度作業(yè)調(diào)度提交狀態(tài)：作業(yè)處于從輸入設(shè)備進(jìn)入外存的過(guò)程；收容狀態(tài)：作業(yè)的全部信息被輸入到輸入井，尚未被調(diào)度執(zhí)行；完成狀態(tài)：作業(yè)運(yùn)行完畢，所占資源尚未被收回。作業(yè)狀態(tài)一個(gè)作業(yè)從提交給計(jì)算機(jī)系統(tǒng)到執(zhí)行結(jié)束退出系統(tǒng)，一般都要經(jīng)歷提交、后備、執(zhí)行和完成等4個(gè)狀態(tài)。提交狀態(tài)：一個(gè)作業(yè)在其處于從輸入設(shè)備進(jìn)入外部存儲(chǔ)設(shè)備的過(guò)程稱為提交狀態(tài)。后備狀態(tài)：也稱為收容狀態(tài)。若一個(gè)作業(yè)的全部信息已全部被輸入進(jìn)輸入井，則在它還未被調(diào)度去執(zhí)行之前，該作業(yè)處于后備狀態(tài)。執(zhí)行狀態(tài)：作業(yè)調(diào)度程序從后備作業(yè)中選取若干個(gè)作業(yè)到內(nèi)存投入運(yùn)行。它為被選中作業(yè)建立進(jìn)程并分配必要的資源，這時(shí)，這些被選中的作業(yè)處于執(zhí)行狀態(tài)。完成狀態(tài)：當(dāng)作業(yè)運(yùn)行完畢，但它所占用的資源尚未全部被系統(tǒng)回收時(shí)，該作業(yè)處于完成狀態(tài)。調(diào)度的層次提交狀態(tài)收容狀態(tài)完成狀態(tài)外存內(nèi)存就緒等待就緒等待執(zhí)行輸入管理系統(tǒng)交換調(diào)度線程調(diào)度進(jìn)程調(diào)度作業(yè)調(diào)度第1級(jí)：作業(yè)調(diào)度、宏觀調(diào)度、高級(jí)調(diào)度對(duì)外存輸入井上的大量作業(yè)進(jìn)行選擇，對(duì)選擇的作業(yè)分配資源，建立相應(yīng)進(jìn)程。作業(yè)執(zhí)行完畢時(shí)，回收資源。分級(jí)調(diào)度調(diào)度的層次提交狀態(tài)收容狀態(tài)完成狀態(tài)外存內(nèi)存就緒等待就緒等待執(zhí)行輸入管理系統(tǒng)交換調(diào)度線程調(diào)度進(jìn)程調(diào)度作業(yè)調(diào)度第2級(jí)：交換調(diào)度、中級(jí)調(diào)度將處于外存交換區(qū)中的就緒狀態(tài)或等待狀態(tài)的進(jìn)程調(diào)入內(nèi)存，或把處于內(nèi)存就緒狀態(tài)或內(nèi)存等待狀態(tài)的進(jìn)程交換導(dǎo)外存交換區(qū)。分級(jí)調(diào)度調(diào)度的層次提交狀態(tài)收容狀態(tài)完成狀態(tài)外存內(nèi)存就緒等待就緒等待執(zhí)行輸入管理系統(tǒng)交換調(diào)度線程調(diào)度進(jìn)程調(diào)度作業(yè)調(diào)度第3級(jí)：進(jìn)程調(diào)度、微觀調(diào)度、低級(jí)調(diào)度選取一個(gè)處于就緒狀態(tài)的進(jìn)程占用處理機(jī)，之后，進(jìn)行上下文切換以便建立與占用處理機(jī)進(jìn)程相適應(yīng)的執(zhí)行環(huán)境。分級(jí)調(diào)度調(diào)度的層次提交狀態(tài)收容狀態(tài)完成狀態(tài)外存內(nèi)存就緒等待就緒等待執(zhí)行輸入管理系統(tǒng)交換調(diào)度線程調(diào)度進(jìn)程調(diào)度作業(yè)調(diào)度第4級(jí)：線程調(diào)度選取一個(gè)處于就緒狀態(tài)的線程進(jìn)入執(zhí)行狀態(tài)。分級(jí)調(diào)度3.1.3處理機(jī)調(diào)度模型分時(shí)間片完完成CPU交互型作業(yè)等待事件活動(dòng)就緒隊(duì)列靜止就緒隊(duì)列靜止阻塞隊(duì)列活動(dòng)阻塞隊(duì)列事件發(fā)生作業(yè)調(diào)度后備作業(yè)隊(duì)列批量作業(yè)中級(jí)調(diào)度調(diào)入中級(jí)調(diào)度調(diào)出磁盤(pán)進(jìn)程調(diào)度中級(jí)調(diào)度調(diào)出事件發(fā)生具有三級(jí)級(jí)調(diào)度的調(diào)度隊(duì)列模型作業(yè)后備狀態(tài)執(zhí)行狀態(tài)完成狀態(tài)4.2.1作業(yè)調(diào)度的功能記錄系統(tǒng)中各作業(yè)的狀況系統(tǒng)為每個(gè)作業(yè)建立一個(gè)JCB記錄作業(yè)信息，系統(tǒng)通過(guò)JCB感知作業(yè)的存在。作業(yè)名作業(yè)類型資源要求資源使用情況優(yōu)先級(jí)（數(shù)）當(dāng)前狀態(tài)其它作業(yè)進(jìn)入后備狀態(tài)時(shí)，系統(tǒng)為其建立JCB；作業(yè)進(jìn)入完成狀態(tài)后，系統(tǒng)撤銷其JCB。作業(yè)調(diào)度1作業(yè)調(diào)度的功能記錄系統(tǒng)中各作業(yè)的狀況從后備隊(duì)列中選擇一部分作業(yè)投入運(yùn)行（涉及調(diào)度算法）為被選中的作業(yè)做好執(zhí)行前的準(zhǔn)備（建立進(jìn)程、為進(jìn)程們分配系統(tǒng)資源）作業(yè)執(zhí)行結(jié)束時(shí)的后處理作業(yè)調(diào)度2作業(yè)調(diào)度目標(biāo)目標(biāo)公平性：對(duì)所有作業(yè)應(yīng)該是公平的利用率：應(yīng)使設(shè)備有高的利用率作業(yè)量：每天執(zhí)行盡可能多的作業(yè)響應(yīng)時(shí)間：有快的響應(yīng)時(shí)間作業(yè)調(diào)度3作業(yè)調(diào)度性能衡量面向用戶的調(diào)度性能準(zhǔn)則周轉(zhuǎn)時(shí)間：作業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時(shí)間。周轉(zhuǎn)時(shí)間Ti=作業(yè)完成時(shí)刻(Tei)-作業(yè)提交時(shí)刻(Tsi)=作業(yè)等待時(shí)間(Twi)+作業(yè)執(zhí)行時(shí)間（Tri)平均周轉(zhuǎn)時(shí)間作業(yè)調(diào)度3作業(yè)調(diào)度性能衡量面向用戶的調(diào)度性能準(zhǔn)則帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間Wi=Ti/Tri平均帶權(quán)周轉(zhuǎn)時(shí)間響應(yīng)時(shí)間：用戶輸入一個(gè)請(qǐng)求（如擊鍵）到系統(tǒng)給出首次響應(yīng)（如屏幕顯示）的時(shí)間——分時(shí)系統(tǒng)作業(yè)調(diào)度3作業(yè)調(diào)度性能衡量面向系統(tǒng)的調(diào)度性能準(zhǔn)則吞吐量：?jiǎn)挝粫r(shí)間內(nèi)所完成的作業(yè)數(shù)，跟作業(yè)本身特性和調(diào)度算法都有關(guān)系——批處理系統(tǒng)處理機(jī)利用率：——大中型主機(jī)各種設(shè)備的均衡利用：如CPU繁忙的作業(yè)和I/O繁忙（指次數(shù)多，每次時(shí)間短）的作業(yè)搭配——大中型主機(jī)作業(yè)調(diào)度1先來(lái)先服務(wù)按照作業(yè)到達(dá)后備作業(yè)隊(duì)列（或進(jìn)程進(jìn)入就緒隊(duì)列）的先后次序來(lái)選擇作業(yè)（或進(jìn)程）。

FCFS算法當(dāng)前作業(yè)或進(jìn)程占用CPU，直到執(zhí)行完或阻塞，才出讓CPU（非搶占方式）最簡(jiǎn)單的算法

FCFS特點(diǎn)比較有利于長(zhǎng)作業(yè)，而不利于短作業(yè)有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)調(diào)度算法2短作業(yè)／進(jìn)程優(yōu)先(SJF/SPF)調(diào)度算法

(SJF,ShortestJobFirst)

SJF算法對(duì)預(yù)計(jì)執(zhí)行時(shí)間短的作業(yè)（進(jìn)程）優(yōu)先分派處理機(jī)。通常后來(lái)的短作業(yè)不搶先正在執(zhí)行的作業(yè)

SJF優(yōu)點(diǎn)比FCFS改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，縮短作業(yè)的等待時(shí)間提高系統(tǒng)的吞吐量調(diào)度算法2短作業(yè)優(yōu)先

(SJF,ShortestJobFirst)

SJF缺點(diǎn)對(duì)長(zhǎng)作業(yè)非常不利，可能長(zhǎng)時(shí)間得不到執(zhí)行未能依據(jù)作業(yè)的緊迫程度來(lái)劃分執(zhí)行的優(yōu)先級(jí)難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間，從而影響調(diào)度性能調(diào)度算法先來(lái)先服務(wù)調(diào)度算法和短作業(yè)優(yōu)先調(diào)度算法作業(yè)提交時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間執(zhí)行順序18.002.0028.500.5039.000.1049.500.208.0010.0012110.0010.5022410.5010.6031.61610.6010.8041.36.58.0010.0012110.0010.1021.11110.1010.3030.8410.3010.8042.34.6先來(lái)先服務(wù)算法平均周轉(zhuǎn)時(shí)間t=1.725帶權(quán)平均周轉(zhuǎn)時(shí)間w=6.875短作業(yè)優(yōu)先算法平均周轉(zhuǎn)時(shí)間t=1.55帶權(quán)平均周轉(zhuǎn)時(shí)間w=5.154時(shí)間片輪轉(zhuǎn)算法

(RoundRobin)

說(shuō)明前兩種算法主要用于宏觀調(diào)度，說(shuō)明怎樣選擇一個(gè)進(jìn)程或作業(yè)開(kāi)始運(yùn)行，開(kāi)始運(yùn)行后的作法都相同，即運(yùn)行到結(jié)束或阻塞，阻塞結(jié)束時(shí)等待當(dāng)前進(jìn)程放棄CPU本算法主要用于微觀調(diào)度，說(shuō)明怎樣并發(fā)運(yùn)行，即切換的方式；設(shè)計(jì)目標(biāo)是提高資源利用率其基本思路是通過(guò)時(shí)間片輪轉(zhuǎn)，提高進(jìn)程并發(fā)性和響應(yīng)時(shí)間特性，從而提高資源利用率調(diào)度算法4時(shí)間片輪轉(zhuǎn)算法

(RoundRobin)RoundRobin算法將系統(tǒng)中所有的就緒進(jìn)程按照FCFS原則，排成一個(gè)隊(duì)列當(dāng)執(zhí)行的時(shí)間片用完時(shí)，調(diào)度程序便停止該進(jìn)程的執(zhí)行，并將它送就緒隊(duì)列的末尾，等待分配下一時(shí)間片再執(zhí)行。然后把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)，均能獲得一個(gè)時(shí)間片的處理機(jī)執(zhí)行時(shí)間進(jìn)程可以未使用完一個(gè)時(shí)間片，就出讓CPU（如阻塞）F…DCBACPU阻塞完成超時(shí)調(diào)度算法4時(shí)間片輪轉(zhuǎn)算法

(RoundRobin)

時(shí)間片長(zhǎng)度的確定（時(shí)間片的長(zhǎng)度從幾個(gè)ms到幾百ms）時(shí)間片長(zhǎng)度變化的影響過(guò)長(zhǎng)退化為FCFS算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)都執(zhí)行完，響應(yīng)時(shí)間長(zhǎng)過(guò)短用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，上下文切換次數(shù)增加，響應(yīng)時(shí)間長(zhǎng)調(diào)度算法7多級(jí)反饋隊(duì)列算法(RoundRobinwithMultipleFeedback)多級(jí)反饋隊(duì)列算法（目前公認(rèn)的較好的一種進(jìn)程調(diào)度算法）設(shè)置多個(gè)就緒隊(duì)列，分別賦予不同的優(yōu)先級(jí)，如逐級(jí)降低，隊(duì)列1的優(yōu)先級(jí)最高。每個(gè)隊(duì)列執(zhí)行時(shí)間片的長(zhǎng)度也不同，規(guī)定優(yōu)先級(jí)越低則時(shí)間片越長(zhǎng)。新進(jìn)程進(jìn)入內(nèi)存后，先投入隊(duì)列1的末尾，按FCFS算法調(diào)度；若按隊(duì)列1一個(gè)時(shí)間片未能執(zhí)行完，則降低投入到隊(duì)列2的末尾，同樣按FCFS算法調(diào)度；如此下去，降低到最后的隊(duì)列，則按“時(shí)間片輪轉(zhuǎn)”算法調(diào)度直到完成；僅當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程執(zhí)行。如果有新進(jìn)程進(jìn)入優(yōu)先級(jí)較高的隊(duì)列，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，并把被搶先的進(jìn)程投入原隊(duì)列的末尾。（搶占式調(diào)度方式）調(diào)度算法多級(jí)反饋隊(duì)列

在兩道環(huán)境下有四個(gè)作業(yè),已知它們進(jìn)入系統(tǒng)的時(shí)間、估計(jì)運(yùn)行時(shí)間,系統(tǒng)采用短作業(yè)優(yōu)先作業(yè)調(diào)度算法，作業(yè)被調(diào)度運(yùn)行后不再退出內(nèi)存,當(dāng)一新作業(yè)投入運(yùn)行后，可按照作業(yè)運(yùn)行時(shí)間長(zhǎng)短調(diào)整作業(yè)執(zhí)行的次序（可搶占式調(diào)度占用CPU）請(qǐng)給出這四個(gè)作業(yè)的執(zhí)行時(shí)間序列，并計(jì)算出平均周轉(zhuǎn)時(shí)間及帶權(quán)平均周轉(zhuǎn)時(shí)間調(diào)度算法應(yīng)用舉例最短作業(yè)優(yōu)先算法執(zhí)行結(jié)果最短作業(yè)優(yōu)先算法執(zhí)行分析過(guò)程10：00，JOB1進(jìn)入，只有一作業(yè)，JOB1被調(diào)入執(zhí)行，10：05，JOB2到達(dá)，最多允許兩作業(yè)同時(shí)進(jìn)入，所以JOB2也被調(diào)入內(nèi)存中有兩作業(yè)，哪一個(gè)執(zhí)行？題目規(guī)定當(dāng)一新作業(yè)運(yùn)行后，可按作業(yè)運(yùn)行時(shí)間長(zhǎng)短調(diào)整執(zhí)行次序即基于優(yōu)先數(shù)可搶占式調(diào)度策略，優(yōu)先數(shù)是根據(jù)作業(yè)估計(jì)運(yùn)行時(shí)間大小來(lái)決定的，由于JOB2運(yùn)行時(shí)間（20分）比JOB1少（到10：05，JOB1還需25分鐘），所以JOB2運(yùn)行，而JOB1等待調(diào)度算法應(yīng)用舉例最短作業(yè)優(yōu)先算法執(zhí)行分析過(guò)程10：10，JOB3到達(dá)輸入井，內(nèi)存已有兩作業(yè)，JOB3不能馬上進(jìn)入內(nèi)存；10：20，JOB4也不能進(jìn)入內(nèi)存，10：25，JOB2運(yùn)行結(jié)束，退出，內(nèi)存中剩下JOB1，輸入井中有兩作業(yè)JOB3和JOB4，如何調(diào)度？作業(yè)調(diào)度算法：最短作業(yè)優(yōu)先，因此JOB3進(jìn)入內(nèi)存，比較JOB1和JOB3運(yùn)行時(shí)間，JOB3運(yùn)行時(shí)間短，故JOB3運(yùn)行，同樣，JOB3退出后，下一個(gè)是JOB4，JOB4結(jié)束后，JOB1才能繼續(xù)運(yùn)行。調(diào)度算法應(yīng)用舉例1.死瑣概念死鎖是指多個(gè)并發(fā)執(zhí)行的進(jìn)程因爭(zhēng)奪資源而出現(xiàn)的一種彼此都不能繼續(xù)推進(jìn)的僵持局面。死鎖（Deadlock）產(chǎn)生死鎖的原因和必要條件2.產(chǎn)生死鎖的原因競(jìng)爭(zhēng)資源進(jìn)程間推進(jìn)順序非法2.產(chǎn)生死鎖的原因競(jìng)爭(zhēng)資源資源分為可重用資源和臨時(shí)性資源重用資源又分為可剝奪資源和非剝奪資源。可剝奪資源：CPU，存儲(chǔ)器非剝奪資源：打印機(jī)競(jìng)爭(zhēng)重用資源，且數(shù)量不能滿足進(jìn)程運(yùn)行需要，就會(huì)陷入僵局。又如：200K的可用內(nèi)存，

P1，P2都進(jìn)行到第二步時(shí)，死鎖發(fā)生。P1......Request80Kbytes;Request60Kbytes;P2......Request70Kbytes;Request80Kbytes;產(chǎn)生死鎖的原因和必要條件2.產(chǎn)生死鎖的原因進(jìn)程間推進(jìn)順序非法（進(jìn)程的異步性特征）

進(jìn)程P進(jìn)程QGetA GetB…… ……GetB GetA…… ……ReleaseAReleaseB…… ……ReleaseBReleaseA37正確模式

進(jìn)程P進(jìn)程QGetA GetB…………ReleaseAReleaseB…… ……GetB GetA…… ……ReleaseBReleaseA

進(jìn)程在申請(qǐng)資源時(shí)，用完一個(gè)資源釋放后再申請(qǐng)下一個(gè)資源。3.5產(chǎn)生死鎖的原因和必要條件38正確模式

進(jìn)程P進(jìn)程QGetA GetA…… ……GetB GetB…… ……ReleaseAReleaseA…… ……ReleaseBReleaseB兩個(gè)進(jìn)程按照相同的順序申請(qǐng)使用資源3.5產(chǎn)生死鎖的原因和必要條件39產(chǎn)生死鎖的原因和必要條件3.產(chǎn)生死鎖的必要條件互斥條件Mutualexclusion一段時(shí)間內(nèi)，某資源只能由一個(gè)進(jìn)程占用。是臨界資源本身的固有屬性。請(qǐng)求和保持條件Hold-and-wait保持已經(jīng)獲得資源不放，繼續(xù)提出新的資源需求。不剝奪條件Nopreemption進(jìn)程已獲得資源在未使用完前不能被剝奪。環(huán)路等待條件系統(tǒng)一定有兩個(gè)或兩個(gè)以上的進(jìn)程組成的一條環(huán)路，該環(huán)路中的每個(gè)進(jìn)程都在等待著相鄰進(jìn)程正占用著的資源產(chǎn)生死鎖的原因和必要條件處理死鎖的四種策略預(yù)防死鎖通過(guò)破除死鎖的四個(gè)必要條件之一，來(lái)防止死鎖產(chǎn)生。避免死鎖仔細(xì)地對(duì)資源進(jìn)行動(dòng)態(tài)分配，以避免死鎖發(fā)生。檢測(cè)與解除死鎖檢測(cè)系統(tǒng)中是否出現(xiàn)死鎖，若出現(xiàn)則解除掉。忽略該問(wèn)題允許系統(tǒng)發(fā)生死鎖，然后解除假裝死鎖永不發(fā)生保證系統(tǒng)永遠(yuǎn)不會(huì)發(fā)生死鎖預(yù)防和避免死鎖的方法預(yù)防死鎖如果能夠保證四個(gè)必要條件中至少有一個(gè)不成立，那么死鎖將不會(huì)產(chǎn)生。（Havender，1968）但其中的“互斥”條件不能破除。預(yù)防和避免死鎖的方法摒棄“請(qǐng)求和保持”條件方法規(guī)定進(jìn)程在執(zhí)行前要一次性地申請(qǐng)運(yùn)行所需全部資源。只有資源全部到手，進(jìn)程方可運(yùn)行，否則進(jìn)程等待。優(yōu)點(diǎn)簡(jiǎn)單、易于實(shí)現(xiàn)缺點(diǎn)資源利用率低進(jìn)程運(yùn)行被延遲預(yù)防和避免死鎖的方法摒棄“不剝奪”條件方法保持資源的進(jìn)程申請(qǐng)新資源失敗時(shí)，在轉(zhuǎn)為阻塞狀態(tài)之前，必須釋放其占用的全部資源。而該進(jìn)程自身則必須等到重新獲得原有資源及新資源后，才能重新運(yùn)行。缺點(diǎn)實(shí)現(xiàn)復(fù)雜，代價(jià)大3.6預(yù)防和避免死鎖的方法摒棄“環(huán)路等待”條件方法1保證每個(gè)進(jìn)程在任何時(shí)候只能占用一個(gè)資源。要用第二個(gè)，必須先釋放第一個(gè)。方法2對(duì)資源按類型線性排隊(duì)編號(hào)，進(jìn)程對(duì)資源的請(qǐng)求必須按照資源序號(hào)遞增提出。缺點(diǎn)：1.找不出一種人人滿意的編號(hào)順序。

2.仍存在資源浪費(fèi)。

3.用戶編程受到限制。4.限制新類型設(shè)備增加預(yù)防和避免死鎖的方法避免死鎖思路允許進(jìn)程動(dòng)態(tài)的申請(qǐng)資源將系統(tǒng)狀態(tài)分為安全狀態(tài)：不會(huì)發(fā)生死鎖不安全狀態(tài)：可能發(fā)生死鎖避免系統(tǒng)進(jìn)入不安全狀態(tài)！做法每次進(jìn)行資源分配時(shí)，首先檢測(cè)一下資源分配后系統(tǒng)處于何種狀態(tài)，若處于安全狀態(tài)，則正式實(shí)施本次分配；若處于不安全狀態(tài)，則不予分配，申請(qǐng)資源的進(jìn)程阻塞。46預(yù)防死鎖的方法系統(tǒng)安全狀態(tài)（用于避免死鎖）安全狀態(tài)：系統(tǒng)能按某種進(jìn)程順序(P1,P2,…，Pn)，來(lái)為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。稱(P1,P2,…,Pn)序列為安全序列預(yù)防和避免死鎖的方法例，系統(tǒng)有三個(gè)進(jìn)程P1、P2和P3，共用12臺(tái)磁帶機(jī)。在T0和T1時(shí)刻，系統(tǒng)的資源分配情況分別如下表a和b。進(jìn)程最大需求已分配可用

P11053

P242P392進(jìn)程最大需求已分配可用

P11052

P242P393ab預(yù)防和避免死鎖的方法結(jié)果：T0時(shí)刻系統(tǒng)處于安全狀態(tài)。（安全序列<P2

，P1，P3

>）P1P2P3可用5(5)2(2)2(7)35(5)4(0)2(7)15(5)2(7)510(0)2(7)02(7)109(0)312結(jié)果：T1時(shí)刻系統(tǒng)處于不安全狀態(tài)。P1P2P3可用5(5)2(2)3(6)25(5)4(0)3(6)05(5)3(6)449利用銀行家算法避免死鎖避免死鎖策略1.當(dāng)前狀態(tài)下，某進(jìn)程申請(qǐng)資源；2.系統(tǒng)假設(shè)將資源分給該進(jìn)程，滿足它的需求；3.檢查分配后的系統(tǒng)狀態(tài)是否是安全的，如果是安全，就確認(rèn)本次分配；如果系統(tǒng)是不安全的，就取消本次分配并阻塞該進(jìn)程。（第三步又稱安全算法）避免死鎖策略也稱作銀行家算法。避免死鎖實(shí)質(zhì)：在進(jìn)程資源分配時(shí)，如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。預(yù)防和避免死鎖的方法預(yù)防和避免死鎖的方法利用銀行家算法避免死鎖數(shù)據(jù)結(jié)構(gòu)—n個(gè)進(jìn)程(P1,…,Pn)，m類資源(R1,…,Rm)可利用資源向量Available（m）Available[j]表示Rj

類資源的可用數(shù)目。最大需求矩陣Max（n×m）Max[i,j]表示進(jìn)程Pi

對(duì)Rj

類資源的最大需求量。分配矩陣Allocation（n×m）Allocation[i,j]表示已分配給進(jìn)程Pi

的Rj

類資源的數(shù)目。需求矩陣Need（n×m）Need[i,j]表示進(jìn)程Pi

對(duì)Rj

類資源的剩余需求量Requesti

：進(jìn)程Pi

的請(qǐng)求向量預(yù)防和避免死鎖的方法銀行家算法：進(jìn)程Pi

發(fā)出資源請(qǐng)求RequestiRequestiNeedi?

執(zhí)行安全性算法，檢查分配后的系統(tǒng)狀態(tài)正式分配安全狀態(tài)Requesti

Available?是

試分配：Available:=AvailableRequestiAllocationi:=Allocationi+RequestiNeedi:=Needi

Requesti是將試分配作廢；恢復(fù)原資源分配狀態(tài)；進(jìn)程Pi阻塞。不安全狀態(tài)錯(cuò)誤否否進(jìn)程Pi阻塞3.6預(yù)防和避免死鎖的方法安全性算法Work:=Available;Finish[i]:=false(i=1,2,…,n);找一滿足下列條件的進(jìn)程：Finish[i]=false且Needi

WorkWork:=Work+Allocationi;

Finish[i]:=true;找到

所有進(jìn)程的Finish[i]=true？找不到是系統(tǒng)狀態(tài)安全不是系統(tǒng)狀態(tài)不安全預(yù)防和避免死鎖的方法例：系統(tǒng)中有五個(gè)進(jìn)程{P0,P1,P2,P3,P4}和三類資源{A,B,C}，每類資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如下表。問(wèn)：P1發(fā)出請(qǐng)求向量Request1(1,0,2)，能否分配？ProcessMaxAllocationNeedAvailableABCABCABCABCP0753010743332P1 322200122P2 902302600P3222211011P4433002431ProcessMaxAllocationNeedAvailableP0753010743332P1 322200122P2 902302600P3222211011

P4433002431230020302結(jié)論：可以找到一個(gè)安全序列<p1,p3,p4,p2,p0>，所以安全，可以將P1申請(qǐng)的資源分配給它。Request1(1

,0

,2)試分配（結(jié)果見(jiàn)紅字）安全性算法：Work={230}Finish=

falsefalsefalsefalsefalsetrue532743true745true1047true1057true死鎖的檢測(cè)與解除死鎖的檢測(cè)資源分配圖RAG（ResourceAllo