計(jì)算機(jī)操作系統(tǒng)第三版第3章

第三章處理機(jī)調(diào)度與死鎖3.1處理機(jī)調(diào)度的層次3.2調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則3.3調(diào)度算法3.4實(shí)時(shí)調(diào)度

3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除

3.1處理機(jī)調(diào)度的層次3.1.1高級、中級和低級調(diào)度1.高級調(diào)度(HighScheduling)在每次執(zhí)行作業(yè)調(diào)度時(shí)，都須做出以下兩個決定。

1)接納多少個作業(yè)

2)接納哪些作業(yè)2.低級調(diào)度(LowLevelScheduling)1)非搶占方式(Non-preemptiveMode)

在采用非搶占調(diào)度方式時(shí)，可能引起進(jìn)程調(diào)度的因素可歸結(jié)為這樣幾個：①正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；②執(zhí)行中的進(jìn)程因提出I/O請求而暫停執(zhí)行；③在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)的要求——立即執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，不宜采用這種調(diào)度方式。2)搶占方式(PreemptiveMode)搶占的原則有：優(yōu)先權(quán)原則。(2)短作業(yè)(進(jìn)程)優(yōu)先原則。(3)時(shí)間片原則。3.中級調(diào)度(Intermediate-LevelScheduling)中級調(diào)度又稱中程調(diào)度(Medium-TermScheduling)。引入中級調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。為此，應(yīng)使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待，把此時(shí)的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件、且內(nèi)存又稍有空閑時(shí)，由中級調(diào)度來決定把外存上的哪些又具備運(yùn)行條件的就緒進(jìn)程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。3.2調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則3.2.1調(diào)度隊(duì)列模型1.僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型圖3-1僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型2.具有高級和低級調(diào)度的調(diào)度隊(duì)列模型圖3-2具有高、低兩級調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列的形式。

(2)設(shè)置多個阻塞隊(duì)列。圖3-2示出了具有高、低兩級調(diào)度的調(diào)度隊(duì)列模型。該模型與上一模型的主要區(qū)別在于如下兩個方面。3同時(shí)具有三級調(diào)度的調(diào)度隊(duì)列模型圖3-3具有三級調(diào)度時(shí)的調(diào)度隊(duì)列模型3.2.2選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶的準(zhǔn)則(1)周轉(zhuǎn)時(shí)間短。

可把平均周轉(zhuǎn)時(shí)間描述為：作業(yè)的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間TS之比，即W=T/TS，稱為帶權(quán)周轉(zhuǎn)時(shí)間，而平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為:(2)響應(yīng)時(shí)間快。(3)截止時(shí)間的保證。(4)優(yōu)先權(quán)準(zhǔn)則。2.面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高。(2)處理機(jī)利用率好。(3)各類資源的平衡利用。3.3調(diào)度算法3.3.1先來先服務(wù)和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法1.先來先服務(wù)調(diào)度算法圖3-4FCFS和SJF調(diào)度算法的性能2.短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F，是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊(duì)列中選擇一個或若干個估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度。

SJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn)：(1)該算法對長作業(yè)不利，如作業(yè)C的周轉(zhuǎn)時(shí)間由10增至16，其帶權(quán)周轉(zhuǎn)時(shí)間由2增至3.1。更嚴(yán)重的是，如果有一長作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來的)短作業(yè)(進(jìn)程)，將導(dǎo)致長作業(yè)(進(jìn)程)長期不被調(diào)度。(2)該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會被及時(shí)處理。(3)由于作業(yè)(進(jìn)程)的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。3.3.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法1.優(yōu)先權(quán)調(diào)度算法的類型非搶占式優(yōu)先權(quán)算法在這種方式下，系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。2)搶占式優(yōu)先權(quán)調(diào)度算法在這種方式下，系統(tǒng)同樣是把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程(原優(yōu)先權(quán)最高的進(jìn)程)的執(zhí)行，重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。因此，在采用這種調(diào)度算法時(shí)，是每當(dāng)系統(tǒng)中出現(xiàn)一個新的就緒進(jìn)程i時(shí)，就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進(jìn)程j的優(yōu)先權(quán)Pj進(jìn)行比較。如果Pi≤Pj，原進(jìn)程Pj便繼續(xù)執(zhí)行；但如果是Pi＞Pj,則立即停止Pj的執(zhí)行，做進(jìn)程切換，使i進(jìn)程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法，能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對性能要求較高的批處理和分時(shí)系統(tǒng)中。2.優(yōu)先權(quán)的類型1)靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個運(yùn)行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如，0~7或0~255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。只是具體用法各異：有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，當(dāng)數(shù)值愈大時(shí)，其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個方面：進(jìn)程類型。(2)進(jìn)程對資源的需求。(3)用戶要求。2)動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的，以便獲得更好的調(diào)度性能。例如，我們可以規(guī)定，在就緒隊(duì)列中的進(jìn)程，隨其等待時(shí)間的增長，其優(yōu)先權(quán)以速率a提高。若所有的進(jìn)程都具有相同的優(yōu)先權(quán)初值，則顯然是最先進(jìn)入就緒隊(duì)列的進(jìn)程，將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機(jī)，此即FCFS算法。若所有的就緒進(jìn)程具有各不相同的優(yōu)先權(quán)初值，那么，對于優(yōu)先權(quán)初值低的進(jìn)程，在等待了足夠的時(shí)間后，其優(yōu)先權(quán)便可能升為最高，從而可以獲得處理機(jī)。當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí)，如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機(jī)。3.高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先權(quán)的變化規(guī)律可描述為：由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為：(1)如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。(2)當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)。(3)對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長時(shí)，其優(yōu)先級便可升到很高，從而也可獲得處理機(jī)。3.3.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法

1.時(shí)間片輪轉(zhuǎn)法在早期的時(shí)間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則，排成一個隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個時(shí)間片。時(shí)間片的大小從幾ms到幾百ms。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個計(jì)時(shí)器發(fā)出時(shí)鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。2.多級反饋隊(duì)列調(diào)度算法(1)應(yīng)設(shè)置多個就緒隊(duì)列，并為各個隊(duì)列賦予不同的優(yōu)先級。第一個隊(duì)列的優(yōu)先級最高，第二個隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊(duì)列中，為每個進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小。例如，第二個隊(duì)列的時(shí)間片要比第一個隊(duì)列的時(shí)間片長一倍，……，第i+1個隊(duì)列的時(shí)間片要比第i個隊(duì)列的時(shí)間片長一倍。圖3-5是多級反饋隊(duì)列算法的示意。圖3-5多級反饋隊(duì)列調(diào)度算法(2)當(dāng)一個新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊(duì)列中運(yùn)行一個時(shí)間片后仍未完成，再依次將它放入第三隊(duì)列，……，如此下去，當(dāng)一個長作業(yè)(進(jìn)程)從第一隊(duì)列依次降到第n隊(duì)列后，在第n隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。(3)僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?~(i-1)隊(duì)列均空時(shí)，才會調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列(第1~(i-1)中的任何一個隊(duì)列)，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i隊(duì)列的末尾，把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。3.多級反饋隊(duì)列調(diào)度算法的性能終端型作業(yè)用戶：較小、短時(shí)完成。(2)短批處理作業(yè)用戶：在前幾個隊(duì)列完成，周轉(zhuǎn)快。(3)長批處理作業(yè)用戶：長作業(yè)得到處理。3.4實(shí)時(shí)調(diào)度3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件1.提供必要的信息就緒時(shí)間。(2)開始截止時(shí)間和完成截止時(shí)間。(3)處理時(shí)間。(4)資源要求。(5)優(yōu)先級。2.系統(tǒng)處理能力強(qiáng)在實(shí)時(shí)系統(tǒng)中，通常都有著多個實(shí)時(shí)任務(wù)。若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過來而使某些實(shí)時(shí)任務(wù)不能得到及時(shí)處理，從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間可表示為Ci，周期時(shí)間表示為Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件：系統(tǒng)才是可調(diào)度的。假如系統(tǒng)中有6個硬實(shí)時(shí)任務(wù)，它們的周期時(shí)間都是50ms，而每次的處理時(shí)間為10ms，則不難算出，此時(shí)是不能滿足上式的，因而系統(tǒng)是不可調(diào)度的。解決的方法是提高系統(tǒng)的處理能力，其途徑有二：其一仍是采用單處理機(jī)系統(tǒng)，但須增強(qiáng)其處理能力，以顯著地減少對每一個任務(wù)的處理時(shí)間；其二是采用多處理機(jī)系統(tǒng)。假定系統(tǒng)中的處理機(jī)數(shù)為N，則應(yīng)將上述的限制條件改為：3.采用搶占式調(diào)度機(jī)制當(dāng)一個優(yōu)先權(quán)更高的任務(wù)到達(dá)時(shí)，允許將當(dāng)前任務(wù)暫時(shí)掛起，而令高優(yōu)先權(quán)任務(wù)立即投入運(yùn)行，這樣便可滿足該硬實(shí)時(shí)任務(wù)對截止時(shí)間的要求。但這種調(diào)度機(jī)制比較復(fù)雜。對于一些小的實(shí)時(shí)系統(tǒng)，如果能預(yù)知任務(wù)的開始截止時(shí)間，則對實(shí)時(shí)任務(wù)的調(diào)度可采用非搶占調(diào)度機(jī)制，以簡化調(diào)度程序和對任務(wù)調(diào)度時(shí)所花費(fèi)的系統(tǒng)開銷。但在設(shè)計(jì)這種調(diào)度機(jī)制時(shí)，應(yīng)使所有的實(shí)時(shí)任務(wù)都比較小，并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時(shí)地將自己阻塞起來，以便釋放出處理機(jī)，供調(diào)度程序去調(diào)度那種開始截止時(shí)間即將到達(dá)的任務(wù)。4.具有快速切換機(jī)制該機(jī)制應(yīng)具有如下兩方面的能力：(1)對外部中斷的快速響應(yīng)能力。為使在緊迫的外部事件請求中斷時(shí)系統(tǒng)能及時(shí)響應(yīng)，要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔盡量短，以免耽誤時(shí)機(jī)(其它緊迫任務(wù))。(2)快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)切換時(shí)的速度，應(yīng)使系統(tǒng)中的每個運(yùn)行功能單位適當(dāng)?shù)男?，以減少任務(wù)切換的時(shí)間開銷。3.4.2實(shí)時(shí)調(diào)度算法的分類1.非搶占式調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法。(2)非搶占式優(yōu)先調(diào)度算法。2.搶占式調(diào)度算法基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法。(2)立即搶占(ImmediatePreemption)的優(yōu)先權(quán)調(diào)度算法。圖3-6實(shí)時(shí)進(jìn)程調(diào)度3.4.3常用的幾種實(shí)時(shí)調(diào)度算法1.最早截止時(shí)間優(yōu)先即EDF(EarliestDeadlineFirst)算法圖3-7EDF算法用于非搶占調(diào)度方式2.最低松弛度優(yōu)先即LLF(LeastLaxityFirst)算法該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級就愈高，以使之優(yōu)先執(zhí)行。例如，一個任務(wù)在200ms時(shí)必須完成，而它本身所需的運(yùn)行時(shí)間就有100ms，因此，調(diào)度程序必須在100ms之前調(diào)度執(zhí)行，該任務(wù)的緊急程度(松弛程度)為100ms。又如，另一任務(wù)在400ms時(shí)必須完成，它本身需要運(yùn)行150ms，則其松弛程度為250ms。在實(shí)現(xiàn)該算法時(shí)要求系統(tǒng)中有一個按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列，松弛度最低的任務(wù)排在隊(duì)列最前面，調(diào)度程序總是選擇就緒隊(duì)列中的隊(duì)首任務(wù)執(zhí)行。該算法主要用于可搶占調(diào)度方式中。假如在一個實(shí)時(shí)系統(tǒng)中，有兩個周期性實(shí)時(shí)任務(wù)A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時(shí)間為10ms；任務(wù)B只要求每50ms執(zhí)行一次，執(zhí)行時(shí)間為25ms。圖3-8A和B任務(wù)每次必須完成的時(shí)間在剛開始時(shí)(t1=0)，A1必須在20ms時(shí)完成，而它本身運(yùn)行又需10ms，可算出A1的松弛度為10ms；B1必須在50ms時(shí)完成，而它本身運(yùn)行就需25ms，可算出B1的松弛度為25ms，故調(diào)度程序應(yīng)先調(diào)度A1執(zhí)行。在t2=10ms時(shí)，A2的松弛度可按下式算出：A2的松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間=40ms-10ms-10ms=20ms類似地，可算出B1的松弛度為15ms，故調(diào)度程序應(yīng)選擇B2運(yùn)行。在t3=30ms時(shí)，A2的松弛度已減為0(即40-10-30)，而B1的松弛度為15ms(即50-5-30)，于是調(diào)度程序應(yīng)搶占B1的處理機(jī)而調(diào)度A2運(yùn)行。在t4=40ms時(shí)，A3的松弛度為10ms(即60-10-40)，而B1的松弛度僅為5ms(即50-5-40)，故又應(yīng)重新調(diào)度B1執(zhí)行。在t5=45ms時(shí)，B1執(zhí)行完成，而此時(shí)A3的松弛度已減為5ms(即60-10-45)，而B2的松弛度為30ms(即100-25-45)，于是又應(yīng)調(diào)度A3執(zhí)行。在t6=55ms時(shí)，任務(wù)A尚未進(jìn)入第4周期，而任務(wù)B已進(jìn)入第2周期，故再調(diào)度B2執(zhí)行。在t7=70ms時(shí)，A4的松弛度已減至0ms(即80-10-70)，而B2的松弛度為20ms(即100-10-70)，故此時(shí)調(diào)度又應(yīng)搶占B2的處理機(jī)而調(diào)度A4執(zhí)行。圖3-9利用ELLF算法進(jìn)行調(diào)度的情況3.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因競爭資源。(2)進(jìn)程間推進(jìn)順序非法。1.競爭資源引起進(jìn)程死鎖可剝奪和非剝奪性資源：內(nèi)存VS打印機(jī)2)競爭非剝奪性資源：3)競爭臨時(shí)性資源：消息、緩沖區(qū)等圖3-12I/O設(shè)備共享時(shí)的死鎖情況圖3-13進(jìn)程之間通信時(shí)的死鎖2.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖1)進(jìn)程推進(jìn)順序合法圖3-14進(jìn)程推進(jìn)順序?qū)λ梨i的影響2)進(jìn)程推進(jìn)順序非法若并發(fā)進(jìn)程P1和P2按曲線④所示的順序推進(jìn)，它們將進(jìn)入不安全區(qū)D內(nèi)。此時(shí)P1保持了資源R1,P2保持了資源R2,系統(tǒng)處于不安全狀態(tài)。因?yàn)?，這時(shí)兩進(jìn)程再向前推進(jìn)，便可能發(fā)生死鎖。例如，當(dāng)P1運(yùn)行到P1:Request(R2)時(shí)，將因R2已被P2占用而阻塞；當(dāng)P2運(yùn)行到P2:Request(R1)時(shí)，也將因R1已被P1占用而阻塞，于是發(fā)生了進(jìn)程死鎖。3.5.2產(chǎn)生死鎖的必要條件互斥條件(2)請求和保持條件(3)不剝奪條件(4)環(huán)路等待條件3.5.3處理死鎖的基本方法預(yù)防死鎖。(2)避免死鎖。(3)檢測死鎖。(4)解除死鎖。3.6預(yù)防死鎖的方法3.6.1預(yù)防死鎖摒棄“請求和保持”條件：一次性分配2.摒棄“不剝奪”條件：產(chǎn)生副作用，如打印機(jī)3.摒棄“環(huán)路等待”條件:資源編號，順序申請3.6.2系統(tǒng)安全狀態(tài)

1.安全狀態(tài)在避免死鎖的方法中，允許進(jìn)程動態(tài)地申請資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)算此次資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程；否則，令進(jìn)程等待。所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序(P1,P2,…，Pn)(稱〈P1,P2,…,Pn〉序列為安全序列)，來為每個進(jìn)程Pi分配其所需資源，直至滿足每個進(jìn)程對資源的最大需求，使每個進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。2.安全狀態(tài)之例我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進(jìn)程P1、P2和P3，共有12臺磁帶機(jī)。進(jìn)程P1總共要求10臺磁帶機(jī)，P2和P3分別要求4臺和9臺。假設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機(jī)，尚有3臺空閑未分配，如下表所示：進(jìn)程最大需求已分配可用P1P2P3104952233.由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在T0時(shí)刻以后，P3又請求1臺磁帶機(jī)，若此時(shí)系統(tǒng)把剩余3臺中的1臺分配給P3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。因?yàn)?，此時(shí)也無法再找到一個安全序列，例如，把其余的2臺分配給P2，這樣，在P2完成后只能釋放出4臺，既不能滿足P1尚需5臺的要求，也不能滿足P3尚需6臺的要求，致使它們都無法推進(jìn)到完成，彼此都在等待對方釋放資源，即陷入僵局，結(jié)果導(dǎo)致死鎖。3.6.3利用銀行家算法避免死鎖1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu)(1)可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Available［j］=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。(2)最大需求矩陣Max。這是一個n×m的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果Max［i,j］=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。(3)分配矩陣Allocation。這也是一個n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation［i,j］=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。(4)需求矩陣Need。這也是一個n×m的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)。如果Need［i,j］=K，則表示進(jìn)程i還需要Rj類資源K個，方能完成其任務(wù)。Need［i,j］=Max［i,j］-Allocation［i,j］

2.銀行家算法設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requesti［j］=K，表示進(jìn)程Pi需要K個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：(1)如果Requesti［j］≤Need［i,j］，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。(2)如果Requesti［j］≤Available［j］，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。(3)系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：

Available［j］∶=Available［j］-Requesti［j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。3.安全性算法(1)設(shè)置兩個向量：①工作向量Work:它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時(shí)，Work∶=Available;②Finish:它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finish［i］∶=false;當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finish［i］∶=true。(2)從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程：①Finish［i］=false;②Need［i,j］≤Work［j］；若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。(3)當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：

Work［j］∶=Work［i］+Allocation［i,j］;Finish［i］∶=true;gotostep2;(4)如果所有進(jìn)程的Finish［i］=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。4.銀行家算法之例假定系統(tǒng)中有五個進(jìn)程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖3-15所示。圖3-15T0時(shí)刻的資源分配表(1)T0時(shí)刻的安全性：圖3-16T0時(shí)刻的安全序列(2)P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available1(3,3,2)③系統(tǒng)先假定可為P1分配資源，并修改Available,Allocation1和Need1向量，由此形成的資源變化情況如圖3-15中的圓括號所示。④再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。圖3-17P1申請資源時(shí)的安全性檢查(3)P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request4(3,3,0)≤Need4(4,3,1);②Request4(3,3,0)<Available(2,3,0)，讓P4等待。(4)P0請求資源：P0發(fā)出請求向量Requst0(0，2，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request0(0,2,0)≤Need0(7,4,3);②Reque