計算機(jī)操作系統(tǒng)修訂版ppt課件

1、第三章 處理機(jī)調(diào)度與死鎖 第三章第三章 處置機(jī)調(diào)度與死鎖處置機(jī)調(diào)度與死鎖 3.1 3.1 處置機(jī)調(diào)度的根本概念處置機(jī)調(diào)度的根本概念 3.2 3.2 調(diào)度算法調(diào)度算法 3.3 3.3 實時調(diào)度實時調(diào)度 3.4 3.4 多處置機(jī)系統(tǒng)中的調(diào)度多處置機(jī)系統(tǒng)中的調(diào)度 3.5 3.5 產(chǎn)生死鎖的緣由和必要條件產(chǎn)生死鎖的緣由和必要條件 3.6 3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法 3.7 3.7 死鎖的檢測與解除死鎖的檢測與解除 第三章 處理機(jī)調(diào)度與死鎖 3.1 處置機(jī)調(diào)度的根本概念處置機(jī)調(diào)度的根本概念 3.1.1 高級、中級和低級調(diào)度高級、中級和低級調(diào)度 1. 高級調(diào)度高級調(diào)度(High Scheduli

2、ng) 在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決議。 1) 接納多少個作業(yè) 2) 接納哪些作業(yè) 第三章 處理機(jī)調(diào)度與死鎖 2. 低級調(diào)度低級調(diào)度(Low Level Scheduling) 1) 非搶占方式(Non-preemptive Mode) 在采用非搶占調(diào)度方式時，能夠引起進(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)是實現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)的批處置系統(tǒng)環(huán)境。但它難

3、以滿足緊急義務(wù)的要求立刻執(zhí)行，因此能夠呵斥難以預(yù)料的后果。顯然，在要求比較嚴(yán)厲的實時系統(tǒng)中，不宜采用這種調(diào)度方式。 第三章 處理機(jī)調(diào)度與死鎖 2) 搶占方式搶占方式(Preemptive Mode) 搶占的原那么有： 優(yōu)先權(quán)原那么。(2) 短作業(yè)(進(jìn)程)優(yōu)先原那么。 (3) 時間片原那么。 第三章 處理機(jī)調(diào)度與死鎖 3. 中級調(diào)度中級調(diào)度(Intermediate-Level Scheduling) 中級調(diào)度又稱中程調(diào)度(Medium-Term Scheduling)。 引入中級調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。 為此，應(yīng)使那些暫時不能運(yùn)轉(zhuǎn)的進(jìn)程不再占用珍貴的內(nèi)存資源，而將它們

4、調(diào)至外存上去等待，把此時的進(jìn)程形狀稱為就緒駐外存形狀或掛起形狀。當(dāng)這些進(jìn)程重又具備運(yùn)轉(zhuǎn)條件、且內(nèi)存又稍有空閑時，由中級調(diào)度來決議把外存上的哪些又具備運(yùn)轉(zhuǎn)條件的就緒進(jìn)程，重新調(diào)入內(nèi)存，并修正其形狀為就緒形狀，掛在就緒隊列上等待進(jìn)程調(diào)度。 第三章 處理機(jī)調(diào)度與死鎖 3.1.2 調(diào)度隊列模型調(diào)度隊列模型 1. 僅有進(jìn)程調(diào)度的調(diào)度隊列模型僅有進(jìn)程調(diào)度的調(diào)度隊列模型 圖 3 - 1 僅具有進(jìn)程調(diào)度的調(diào)度隊列模型 就 緒隊 列阻 塞隊列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件交互用戶事件出現(xiàn)時間片完第三章 處理機(jī)調(diào)度與死鎖 2. 具有高級和低級調(diào)度的調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型 圖 3-2 具有高、

5、低兩級調(diào)度的調(diào)度隊列模型 就 緒隊列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件1作業(yè)調(diào)度事件1出現(xiàn)時間片完等待事件2事件2出現(xiàn)等待事件n事件n出現(xiàn)后備 隊列第三章 處理機(jī)調(diào)度與死鎖 就緒隊列的方式。 (2) 設(shè)置多個阻塞隊列。 圖 3-2 示出了具有高、低兩級調(diào)度的調(diào)度隊列模型。該模型與上一模型的主要區(qū)別在于如下兩個方面。 第三章 處理機(jī)調(diào)度與死鎖 3. 同時具有三級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型 圖 3-3 具有三級調(diào)度時的調(diào)度隊列模型 就緒隊列進(jìn)程調(diào)度CPU就緒，掛起隊列中級調(diào)度阻塞，掛起隊列阻塞隊列等待事件進(jìn)程完成時間片完作業(yè)調(diào)度交互型作業(yè)后備隊列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)第三章

6、 處理機(jī)調(diào)度與死鎖 3.1.3 選擇調(diào)度方式和調(diào)度算法的假設(shè)干準(zhǔn)那么選擇調(diào)度方式和調(diào)度算法的假設(shè)干準(zhǔn)那么 1. 面向用戶的準(zhǔn)那么面向用戶的準(zhǔn)那么 (1) 周轉(zhuǎn)時間短。周轉(zhuǎn)時間短。 可把平均周轉(zhuǎn)時間描畫為： iiiTnT11niSiiTTnW11作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供效力的時間TS之比，即W=T/TS，稱為帶權(quán)周轉(zhuǎn)時間，而平均帶權(quán)周轉(zhuǎn)時間那么可表示為: 第三章 處理機(jī)調(diào)度與死鎖 (2) 呼應(yīng)時間快。 (3) 截止時間的保證。 (4) 優(yōu)先權(quán)準(zhǔn)那么。 第三章 處理機(jī)調(diào)度與死鎖 2. 面向系統(tǒng)的準(zhǔn)那么面向系統(tǒng)的準(zhǔn)那么 系統(tǒng)吞吐量高。(2) 處置機(jī)利用率好。 (3) 各類資源的平衡利用。 第三

7、章 處理機(jī)調(diào)度與死鎖 3.2 調(diào)調(diào) 度度 算算 法法 3.2.1 先來先效力和短作業(yè)先來先效力和短作業(yè)(進(jìn)程進(jìn)程)優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法 1. 先來先效力調(diào)度算法先來先效力調(diào)度算法 第三章 處理機(jī)調(diào)度與死鎖 圖 3-4 FCFS和SJF調(diào)度算法的性能 第三章 處理機(jī)調(diào)度與死鎖 2. 短作業(yè)短作業(yè)(進(jìn)程進(jìn)程)優(yōu)先調(diào)度算法優(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)度算法，是從后備隊列中選擇一個或假設(shè)干個估計運(yùn)轉(zhuǎn)時間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)轉(zhuǎn)。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法，那么是從就緒

8、隊列中選出一估計運(yùn)轉(zhuǎn)時間最短的進(jìn)程，將處置機(jī)分配給它，使它立刻執(zhí)行并不斷執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處置機(jī)時，再重新調(diào)度。第三章 處理機(jī)調(diào)度與死鎖 SJ(P)F調(diào)度算法也存在不容忽視的缺陷： (1) 該算法對長作業(yè)不利，如作業(yè)C的周轉(zhuǎn)時間由10增至16，其帶權(quán)周轉(zhuǎn)時間由2增至3.1。更嚴(yán)重的是，假設(shè)有一長作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊列(就緒隊列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來的)短作業(yè)(進(jìn)程)，將導(dǎo)致長作業(yè)(進(jìn)程)長期不被調(diào)度。 (2) 該算法完全未思索作業(yè)的緊迫程度，因此不能保證緊迫性作業(yè)(進(jìn)程)會被及時處置。 (3) 由于作業(yè)(進(jìn)程)的長短只是根據(jù)用戶所提供的估計執(zhí)行

9、時間而定的，而用戶又能夠會有意或無意地縮短其作業(yè)的估計運(yùn)轉(zhuǎn)時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。 第三章 處理機(jī)調(diào)度與死鎖 3.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法 1. 優(yōu)先權(quán)調(diào)度算法的類型優(yōu)先權(quán)調(diào)度算法的類型 非搶占式優(yōu)先權(quán)算法 在這種方式下，系一致旦把處置機(jī)分配給就緒隊列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便不斷執(zhí)行下去，直至完成； 或因發(fā)生某事件使該進(jìn)程放棄處置機(jī)時，系統(tǒng)方可再將處置機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處置系統(tǒng)中；也可用于某些對實時性要求不嚴(yán)的實時系統(tǒng)中。 第三章 處理機(jī)調(diào)度與死鎖 2) 搶占式優(yōu)先權(quán)調(diào)度算法 在這種方式下，系統(tǒng)同樣是把

10、處置機(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)度算法時，是每當(dāng)系統(tǒng)中出現(xiàn)一個新的就緒進(jìn)程i時，就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進(jìn)程j的優(yōu)先權(quán)Pj進(jìn)展比較。假設(shè)PiPj，原進(jìn)程Pj便繼續(xù)執(zhí)行；但假設(shè)是PiPj, 那么立刻停頓Pj的執(zhí)行，做進(jìn)程切換，使i進(jìn)程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法，能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)厲的實時系統(tǒng)中， 以及對性能要求較高的批處置和分時系統(tǒng)中。 第三章 處理機(jī)調(diào)度與死鎖 2.

11、 優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型 1) 靜態(tài)優(yōu)先權(quán) 靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時確定的，且在進(jìn)程的整個運(yùn)轉(zhuǎn)期間堅持不變。普通地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如，07或0255中的某一整數(shù)， 又把該整數(shù)稱為優(yōu)先數(shù)。只是詳細(xì)用法各異：有的系統(tǒng)用“0表示最高優(yōu)先權(quán)，當(dāng)數(shù)值愈大時，其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。 第三章 處理機(jī)調(diào)度與死鎖 確定進(jìn)程優(yōu)先權(quán)的根據(jù)有如下三個方面：進(jìn)程類型。 (2) 進(jìn)程對資源的需求。 (3) 用戶要求。 第三章 處理機(jī)調(diào)度與死鎖 2) 動態(tài)優(yōu)先權(quán) 動態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進(jìn)程時所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時間的添加而改動的，以便獲得更好的調(diào)度性能。例

12、如，我們可以規(guī)定，在就緒隊列中的進(jìn)程，隨其等待時間的增長，其優(yōu)先權(quán)以速率a提高。假設(shè)一切的進(jìn)程都具有一樣的優(yōu)先權(quán)初值，那么顯然是最先進(jìn)入就緒隊列的進(jìn)程，將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處置機(jī)，此即FCFS算法。假設(shè)一切的就緒進(jìn)程具有各不一樣的優(yōu)先權(quán)初值，那么，對于優(yōu)先權(quán)初值低的進(jìn)程，在等待了足夠的時間后，其優(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ī)。 第三章 處理機(jī)調(diào)度與死鎖 3. 高呼應(yīng)比優(yōu)先調(diào)度算法高呼應(yīng)比優(yōu)先調(diào)度算法 要求服務(wù)時間要求服務(wù)時間等待時間優(yōu)先權(quán)優(yōu)先權(quán)的變化規(guī)律可描畫為：

13、 由于等待時間與效力時間之和，就是系統(tǒng)對該作業(yè)的呼應(yīng)時間，故該優(yōu)先權(quán)又相當(dāng)于呼應(yīng)比RP。據(jù)此，又可表示為： 要求服務(wù)時間響應(yīng)時間要求服務(wù)時間要求服務(wù)時間等待時間優(yōu)先權(quán)第三章 處理機(jī)調(diào)度與死鎖 (1) 假設(shè)作業(yè)的等待時間一樣，那么要求效力的時間愈短，其優(yōu)先權(quán)愈高，因此該算法有利于短作業(yè)。 (2) 當(dāng)要求效力的時間一樣時，作業(yè)的優(yōu)先權(quán)決議于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因此它實現(xiàn)的是先來先效力。 (3) 對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的添加而提高，當(dāng)其等待時間足夠長時，其優(yōu)先級便可升到很高， 從而也可獲得處置機(jī)。 第三章 處理機(jī)調(diào)度與死鎖 3.2.3 基于時間片的輪轉(zhuǎn)調(diào)度算法基于

14、時間片的輪轉(zhuǎn)調(diào)度算法 1. 時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法 在早期的時間片輪轉(zhuǎn)法中，系統(tǒng)將一切的就緒進(jìn)程按先在早期的時間片輪轉(zhuǎn)法中，系統(tǒng)將一切的就緒進(jìn)程按先來先效力的原那么，排成一個隊列，每次調(diào)度時，把來先效力的原那么，排成一個隊列，每次調(diào)度時，把CPU分配給隊首進(jìn)程，并令其執(zhí)行一個時間片。時間片的大小從分配給隊首進(jìn)程，并令其執(zhí)行一個時間片。時間片的大小從幾幾ms到幾百到幾百ms。當(dāng)執(zhí)行的時間片用完時，由一個計時器發(fā)。當(dāng)執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷懇求，調(diào)度程序便據(jù)此信號來停頓該進(jìn)程的執(zhí)行，出時鐘中斷懇求，調(diào)度程序便據(jù)此信號來停頓該進(jìn)程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處置

15、機(jī)分配給就緒并將它送往就緒隊列的末尾；然后，再把處置機(jī)分配給就緒隊列中新的隊首進(jìn)程，同時也讓它執(zhí)行一個時間片。這樣就隊列中新的隊首進(jìn)程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的一切進(jìn)程，在一給定的時間內(nèi)，均能可以保證就緒隊列中的一切進(jìn)程，在一給定的時間內(nèi)，均能獲得一時間片的處置機(jī)執(zhí)行時間。獲得一時間片的處置機(jī)執(zhí)行時間。第三章 處理機(jī)調(diào)度與死鎖 2. 多級反響隊列調(diào)度算法多級反響隊列調(diào)度算法 (1) 應(yīng)設(shè)置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級。 第一個隊列的優(yōu)先級最高，第二個隊列次之，其他各隊列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊列中進(jìn)程執(zhí)行時間片的大小也各不一樣，在優(yōu)先權(quán)愈高的

16、隊列中，為每個進(jìn)程所規(guī)定的執(zhí)行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。 圖 3-5 是多級反響隊列算法的表示。 第三章 處理機(jī)調(diào)度與死鎖 圖 3-5 多級反響隊列調(diào)度算法 就緒隊列1就緒隊列2就緒隊列3就緒隊列nS1S2S3至CPU至CPU至CPU至CPU(時間片：S1 S2 S3)第三章 處理機(jī)調(diào)度與死鎖 (2) 當(dāng)一個新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊列的末尾，按FCFS原那么排隊等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時，如它能在該時間片內(nèi)完成，便可預(yù)備撤離系統(tǒng)；假設(shè)它在一個時間片終了時髦未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第

17、二隊列的末尾，再同樣地按FCFS原那么等待調(diào)度執(zhí)行；假設(shè)它在第二隊列中運(yùn)轉(zhuǎn)一個時間片后仍未完成，再依次將它放入第三隊列，如此下去，當(dāng)一個長作業(yè)(進(jìn)程)從第一隊列依次降到第n隊列后，在第n隊列中便采取按時間片輪轉(zhuǎn)的方式運(yùn)轉(zhuǎn)。 第三章 處理機(jī)調(diào)度與死鎖 (3) 僅當(dāng)?shù)谝魂犃锌臻e時，調(diào)度程序才調(diào)度第二隊列中的進(jìn)程運(yùn)轉(zhuǎn)； 僅當(dāng)?shù)?(i-1) 隊列均空時，才會調(diào)度第i隊列中的進(jìn)程運(yùn)轉(zhuǎn)。假設(shè)處置機(jī)正在第i隊列中為某進(jìn)程效力時，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊列(第1(i-1)中的任何一個隊列)，那么此時新進(jìn)程將搶占正在運(yùn)轉(zhuǎn)進(jìn)程的處置機(jī)，即由調(diào)度程序把正在運(yùn)轉(zhuǎn)的進(jìn)程放回到第i隊列的末尾，把處置機(jī)分配給新到的高優(yōu)

18、先權(quán)進(jìn)程。 第三章 處理機(jī)調(diào)度與死鎖 3. 多級反響隊列調(diào)度算法的性能多級反響隊列調(diào)度算法的性能 終端型作業(yè)用戶。 (2) 短批處置作業(yè)用戶。 (3) 長批處置作業(yè)用戶。第三章 處理機(jī)調(diào)度與死鎖 3.3 實實 時時 調(diào)調(diào) 度度 3.3.1 實現(xiàn)實時調(diào)度的根本條件實現(xiàn)實時調(diào)度的根本條件 1. 提供必要的信息提供必要的信息 就緒時間。(2) 開場截止時間和完成截止時間。 (3) 處置時間。 (4) 資源要求。 (5) 優(yōu)先級。 第三章 處理機(jī)調(diào)度與死鎖 2. 系統(tǒng)處置才干強(qiáng)系統(tǒng)處置才干強(qiáng) 在實時系統(tǒng)中，通常都有著多個實時義務(wù)。假設(shè)處置機(jī)的處置才干不夠強(qiáng)，那么有能夠因處置機(jī)忙不過來而使某些實時義務(wù)不

19、能得到及時處置， 從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個周期性的硬實時義務(wù)，它們的處置時間可表示為Ci，周期時間表示為Pi，那么在單處置機(jī)情況下，必需滿足下面的限制條件： miiiPC11第三章 處理機(jī)調(diào)度與死鎖 系統(tǒng)才是可調(diào)度的。假設(shè)系統(tǒng)中有6個硬實時義務(wù)，它們的周期時間都是 50 ms，而每次的處置時間為 10 ms，那么不難算出，此時是不能滿足上式的，因此系統(tǒng)是不可調(diào)度的。 處理的方法是提高系統(tǒng)的處置才干，其途徑有二：其一仍是采用單處置機(jī)系統(tǒng)， 但須加強(qiáng)其處置才干， 以顯著地減少對每一個義務(wù)的處置時間；其二是采用多處置機(jī)系統(tǒng)。假定系統(tǒng)中的處置機(jī)數(shù)為N，那么應(yīng)將上述的限制條件改為：

20、miiiNPC1第三章 處理機(jī)調(diào)度與死鎖 3. 采用搶占式調(diào)度機(jī)制采用搶占式調(diào)度機(jī)制 當(dāng)一個優(yōu)先權(quán)更高的義務(wù)到達(dá)時，允許將當(dāng)前義務(wù)暫時掛起，而令高優(yōu)先權(quán)義務(wù)立刻投入運(yùn)轉(zhuǎn)，這樣便可滿足該硬實時義務(wù)對截止時間的要求。但這種調(diào)度機(jī)制比較復(fù)雜。 對于一些小的實時系統(tǒng)，假設(shè)能預(yù)知義務(wù)的開場截止時間，那么對實時義務(wù)的調(diào)度可采用非搶占調(diào)度機(jī)制，以簡化調(diào)度程序和對義務(wù)調(diào)度時所破費(fèi)的系統(tǒng)開銷。但在設(shè)計這種調(diào)度機(jī)制時，應(yīng)使一切的實時義務(wù)都比較小，并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時地將本人阻塞起來，以便釋放出處置機(jī)， 供調(diào)度程序去調(diào)度那種開場截止時間即將到達(dá)的義務(wù)。 第三章 處理機(jī)調(diào)度與死鎖 4. 具有快速切換

21、機(jī)制具有快速切換機(jī)制 該機(jī)制應(yīng)具有如下兩方面的才干： (1) 對外部中斷的快速呼應(yīng)才干。為使在緊迫的外部事件懇求中斷時系統(tǒng)能及時呼應(yīng)，要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使制止中斷的時間間隔盡量短， 以免耽擱時機(jī)(其它緊迫義務(wù))。 (2) 快速的義務(wù)分派才干。在完成義務(wù)調(diào)度后，便應(yīng)進(jìn)展義務(wù)切換。為了提高分派程序進(jìn)展義務(wù)切換時的速度， 應(yīng)使系統(tǒng)中的每個運(yùn)轉(zhuǎn)功能單位適當(dāng)?shù)男?，以減少義務(wù)切換的時間開銷。 第三章 處理機(jī)調(diào)度與死鎖 3.3.2 實時調(diào)度算法的分類實時調(diào)度算法的分類 1. 非搶占式調(diào)度算法非搶占式調(diào)度算法 非搶占式輪轉(zhuǎn)調(diào)度算法。 (2) 非搶占式優(yōu)先調(diào)度算法。 第三章 處理機(jī)調(diào)度與死鎖 2

22、. 搶占式調(diào)度算法搶占式調(diào)度算法 基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法。(2) 立刻搶占(Immediate Preemption)的優(yōu)先權(quán)調(diào)度算法。 (a) 非搶占輪轉(zhuǎn)調(diào)度當(dāng)前進(jìn)程實時進(jìn)程實時進(jìn)程請求調(diào)度實時進(jìn)程槍占當(dāng)前進(jìn)程，并立即執(zhí)行(d) 立即搶占的優(yōu)先權(quán)調(diào)度調(diào)度時間進(jìn)程 1進(jìn)程 2實時進(jìn)程要求調(diào)度進(jìn)程 n實時進(jìn)程調(diào)度實時進(jìn)程運(yùn)行(b) 非搶占優(yōu)先權(quán)調(diào)度當(dāng)前進(jìn)程實時進(jìn)程實時進(jìn)程請求調(diào)度當(dāng)前進(jìn)程運(yùn)行完成調(diào)度時間當(dāng)前進(jìn)程實時進(jìn)程請求調(diào)度時鐘中斷到來時調(diào)度時間(c) 基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度調(diào)度時間實時進(jìn)程圖 3-6 實時進(jìn)程調(diào)度 第三章 處理機(jī)調(diào)度與死鎖 3.3.3 常用的幾種實時調(diào)度

23、算法常用的幾種實時調(diào)度算法 1. 最早截止時間優(yōu)先即最早截止時間優(yōu)先即EDF(Earliest Deadline First)算法算法 圖 3-7 EDF算法用于非搶占調(diào)度方式 1342開始截止時間任務(wù)執(zhí)行任務(wù)到達(dá)12341342t第三章 處理機(jī)調(diào)度與死鎖 2. 最低松弛度優(yōu)先即最低松弛度優(yōu)先即LLF(Least Laxity First)算法算法 該算法是根據(jù)義務(wù)緊急(或松弛)的程度，來確定義務(wù)的優(yōu)先級。義務(wù)的緊急程度愈高，為該義務(wù)所賦予的優(yōu)先級就愈高， 以使之優(yōu)先執(zhí)行。例如，一個義務(wù)在200ms時必需完成，而它本身所需的運(yùn)轉(zhuǎn)時間就有100ms，因此，調(diào)度程序必需在100 ms之前調(diào)度執(zhí)行，

24、該義務(wù)的緊急程度(松弛程度)為100 ms。又如，另一義務(wù)在400 ms時必需完成，它本身需求運(yùn)轉(zhuǎn) 150 ms，那么其松弛程度為 250 ms。在實現(xiàn)該算法時要求系統(tǒng)中有一個按松弛度排序的實時義務(wù)就緒隊列，松弛度最低的義務(wù)排在隊列最前面，調(diào)度程序總是選擇就緒隊列中的隊首義務(wù)執(zhí)行。該算法主要用于可搶占調(diào)度方式中。假設(shè)在一個實時系統(tǒng)中，有兩個周期性實時義務(wù)A和B，義務(wù)A要求每 20 ms執(zhí)行一次，執(zhí)行時間為 10 ms；義務(wù)B只需求每50 ms執(zhí)行一次，執(zhí)行時間為 25 ms。 第三章 處理機(jī)調(diào)度與死鎖 圖 3-8 A和B義務(wù)每次必需完成的時間 A1A2A3A4A5A6A7A8204060801

25、00120140160B1B2B3t0第三章 處理機(jī)調(diào)度與死鎖 在剛開場時(t1=0)，A1必需在20ms時完成，而它本身運(yùn)轉(zhuǎn)又需 10 ms，可算出A1的松弛度為10ms；B1必需在50ms時完成， 而它本身運(yùn)轉(zhuǎn)就需25 ms，可算出B1的松弛度為25 ms，故調(diào)度程序應(yīng)先調(diào)度A1執(zhí)行。在t2=10 ms時，A2的松弛度可按下式算出： A2的松弛度=必需完成時間-其本身的運(yùn)轉(zhuǎn)時間-當(dāng)前時間 =40 ms-10 ms-10 ms=20 ms 第三章 處理機(jī)調(diào)度與死鎖 類似地，可算出B1的松弛度為15ms，故調(diào)度程序應(yīng)選擇B2運(yùn)轉(zhuǎn)。在t3=30 ms時，A2的松弛度已減為0(即40-10-30)

26、，而B1的松弛度為15 ms(即50-5-30)，于是調(diào)度程序應(yīng)搶占B1的處置機(jī)而調(diào)度A2運(yùn)轉(zhuǎn)。在t4=40 ms時，A3的松弛度為10 ms(即60-10-40)，而B1的松弛度僅為5 ms(即50-5-40)，故又應(yīng)重新調(diào)度B1執(zhí)行。在t5=45 ms時，B1執(zhí)行完成，而此時A3的松弛度已減為5 ms(即60-10-45)，而B2的松弛度為30 ms(即100-25-45)，于是又應(yīng)調(diào)度A3執(zhí)行。在t6=55ms時，義務(wù)A尚未進(jìn)入第4周期，而義務(wù)B已進(jìn)入第2周期，故再調(diào)度B2執(zhí)行。在t7=70 ms時，A4的松弛度已減至0 ms(即80-10-70)，而B2的松弛度為20 ms(即100-

27、10-70)，故此時調(diào)度又應(yīng)搶占B2的處置機(jī)而調(diào)度A4執(zhí)行。 第三章 處理機(jī)調(diào)度與死鎖 圖 3-9 利用ELLF算法進(jìn)展調(diào)度的情況 t1A1(10)10203040506080t0t10B1(20)t2t370A2(10)A3(10)A4(10)t4t5t6t7t8B1(5)B2(15)B2(10)第三章 處理機(jī)調(diào)度與死鎖 3.4 多處置機(jī)系統(tǒng)中的調(diào)度多處置機(jī)系統(tǒng)中的調(diào)度 3.4.1 多處置器系統(tǒng)的類型多處置器系統(tǒng)的類型 (1) 嚴(yán)密耦合(Tightly Coupted)MPS。 這通常是經(jīng)過高速總線或高速交叉開關(guān)，來實現(xiàn)多個處置器之間的互連的。它們共享主存儲器系統(tǒng)和I/O設(shè)備，并要求將主存儲

28、器劃分為假設(shè)干個能獨(dú)立訪問的存儲器模塊，以便多個處置機(jī)能同時對主存進(jìn)展訪問。系統(tǒng)中的一切資源和進(jìn)程，都由操作系統(tǒng)實施一致的控制和管理。 第三章 處理機(jī)調(diào)度與死鎖 (2) 松散耦合(Loosely Coupled)MPS。 在松散耦合MPS中，通常是經(jīng)過通道或通訊線路，來實現(xiàn)多臺計算機(jī)之間的互連。每臺計算機(jī)都有本人的存儲器和I/O設(shè)備，并配置了OS來管理本地資源和在本地運(yùn)轉(zhuǎn)的進(jìn)程。因此，每一臺計算機(jī)都能獨(dú)立地任務(wù)， 必要時可經(jīng)過通訊線路與其它計算機(jī)交換信息，以及協(xié)調(diào)它們之間的任務(wù)。 第三章 處理機(jī)調(diào)度與死鎖 2. 對稱多處置器系統(tǒng)和非對稱多處置器系統(tǒng)對稱多處置器系統(tǒng)和非對稱多處置器系統(tǒng) (1)

29、對稱多處置器系統(tǒng)SMPS(Symmetric MultiProcessor System)。 在系統(tǒng)中所包含的各處置器單元，在功能和構(gòu)造上都是一樣的， 當(dāng)前的絕大多數(shù)MPS都屬于SMP系統(tǒng)。例如，IBM公司的SR/6000 Model F50, 便是利用4片Power PC處置器構(gòu)成的。 (2) 非對稱多處置器系統(tǒng)。在系統(tǒng)中有多種類型的處置單元， 它們的功能和構(gòu)造各不一樣，其中只需一個主處置器，有多個從處置器。 第三章 處理機(jī)調(diào)度與死鎖 3.4.2 進(jìn)程分配方式進(jìn)程分配方式 1. 對稱多處置器系統(tǒng)中的進(jìn)程分配方式對稱多處置器系統(tǒng)中的進(jìn)程分配方式 在在SMP系統(tǒng)中，一切的處置器都是一樣的，因此可

30、把一系統(tǒng)中，一切的處置器都是一樣的，因此可把一切的處置器作為一個處置器池切的處置器作為一個處置器池(Processor pool)，由調(diào)度程序，由調(diào)度程序或基于處置器的懇求，或基于處置器的懇求， 將任何一個進(jìn)程分配給池中的任何一將任何一個進(jìn)程分配給池中的任何一個處置器去處置。在進(jìn)展進(jìn)程分配時，可采用以下兩種方式個處置器去處置。在進(jìn)展進(jìn)程分配時，可采用以下兩種方式之一。之一。 1) 靜態(tài)分配靜態(tài)分配(Static Assigenment)方式方式 2) 動態(tài)分配動態(tài)分配(Dynamic Assgement)方式方式 第三章 處理機(jī)調(diào)度與死鎖 2. 非對稱非對稱MPS中的進(jìn)程分配方式中的進(jìn)程分配方

31、式 對于非對稱對于非對稱MPS， 其其OS大多采用主大多采用主從從(Master-Slave)式式OS， 即即OS的中心部分駐留在一臺主機(jī)上的中心部分駐留在一臺主機(jī)上(Master)， 而而從機(jī)從機(jī)(Slave)上只是用戶程序，上只是用戶程序， 進(jìn)程調(diào)度只由主機(jī)執(zhí)行。進(jìn)程調(diào)度只由主機(jī)執(zhí)行。 每每當(dāng)從機(jī)空閑時，當(dāng)從機(jī)空閑時， 便向主機(jī)發(fā)送一索求進(jìn)程的信號，便向主機(jī)發(fā)送一索求進(jìn)程的信號， 然后，然后， 便等待主機(jī)為它分配進(jìn)程。便等待主機(jī)為它分配進(jìn)程。 在主機(jī)中堅持有一個就緒隊列，在主機(jī)中堅持有一個就緒隊列， 只需就緒隊列不空，只需就緒隊列不空， 主機(jī)便從其隊首摘下一進(jìn)程分配給懇主機(jī)便從其隊首摘下一

32、進(jìn)程分配給懇求的從機(jī)。從機(jī)接納到分配的進(jìn)程后便運(yùn)轉(zhuǎn)該進(jìn)程，求的從機(jī)。從機(jī)接納到分配的進(jìn)程后便運(yùn)轉(zhuǎn)該進(jìn)程， 該進(jìn)該進(jìn)程終了后從機(jī)又向主機(jī)發(fā)出懇求。程終了后從機(jī)又向主機(jī)發(fā)出懇求。 第三章 處理機(jī)調(diào)度與死鎖 3.4.3 進(jìn)程進(jìn)程(線程線程)調(diào)度方式調(diào)度方式 1. 自調(diào)度(Self-Scheduling)方式 1) 自調(diào)度機(jī)制 在多處置器系統(tǒng)中，自調(diào)度方式是最簡單的一種調(diào)度方式。它是直接由單處置機(jī)環(huán)境下的調(diào)度方式演化而來的。 在系統(tǒng)中設(shè)置有一個公共的進(jìn)程或線程就緒隊列， 一切的處置器在空閑時，都可本人到該隊列中獲得一進(jìn)程(或線程)來運(yùn)轉(zhuǎn)。在自調(diào)度方式中，可采用在單處置機(jī)環(huán)境下所用的調(diào)度算法，如先來先效

33、力(FCFS)調(diào)度算法、最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法和搶占式最高優(yōu)先權(quán)優(yōu)先調(diào)度算法等。 第三章 處理機(jī)調(diào)度與死鎖 2) 自調(diào)度方式的優(yōu)點(diǎn) 自調(diào)度方式的主要優(yōu)點(diǎn)表現(xiàn)為：首先，系統(tǒng)中的公共就緒隊列可按照單處置機(jī)系統(tǒng)中所采用的各種方式加以組織； 其調(diào)度算法也可沿用單處置機(jī)系統(tǒng)所用的算法，亦即，很容易將單處置機(jī)環(huán)境下的調(diào)度機(jī)制移植到多處置機(jī)系統(tǒng)中， 故它依然是當(dāng)前多處置機(jī)系統(tǒng)中較常用的調(diào)度方式。其次， 只需系統(tǒng)中有義務(wù)，或者說只需公共就緒隊列不空，就不會出現(xiàn)處置機(jī)空閑的情況，也不會發(fā)生處置器忙閑不均的景象，因此有利于提高處置器的利用率。 第三章 處理機(jī)調(diào)度與死鎖 3) 自調(diào)度方式的缺陷瓶頸問題。

34、(2) 低效性。 (3) 線程切換頻繁。 第三章 處理機(jī)調(diào)度與死鎖 2. 成組調(diào)度成組調(diào)度(Gang Scheduling)方式方式 在成組調(diào)度時，如何為運(yùn)用程序分配處置器時間， 1) 面向一切運(yùn)用程序平均分配處置器時間 2) 面向一切線程平均分配處置器時間 圖 3 - 10 兩種分配處置器時間的方法 第三章 處理機(jī)調(diào)度與死鎖 3. 公用途置器分配公用途置器分配(Dedicated Processor Assigement)方式方式 圖 3-11 線程數(shù)對加速比的影響 123456789 10 11 12 13 14 15 16 17 18 19 20 21 22 23 241234567加速

35、比線程數(shù)矩陣相乘FFT0第三章 處理機(jī)調(diào)度與死鎖 3.5 產(chǎn)生死鎖的緣由和必要條件產(chǎn)生死鎖的緣由和必要條件3.5.1 產(chǎn)生死鎖的緣由產(chǎn)生死鎖的緣由 競爭資源。競爭資源。 (2) 進(jìn)程間推進(jìn)順序非法。進(jìn)程間推進(jìn)順序非法。 第三章 處理機(jī)調(diào)度與死鎖 1. 競爭資源引起進(jìn)程死鎖競爭資源引起進(jìn)程死鎖 可剝奪和非剝奪性資源 2) 競爭非剝奪性資源 3) 競爭暫時性資源 第三章 處理機(jī)調(diào)度與死鎖 圖 3-12 I/O設(shè)備共享時的死鎖情況 R1R2P1P2第三章 處理機(jī)調(diào)度與死鎖 圖 3-13 進(jìn)程之間通訊時的死鎖 S2P1S3P3S1P2第三章 處理機(jī)調(diào)度與死鎖 2. 進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程推進(jìn)順序

36、不當(dāng)引起死鎖 1) 進(jìn)程推進(jìn)順序合法 圖 3-14 進(jìn)程推進(jìn)順序?qū)λ梨i的影響 P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)D第三章 處理機(jī)調(diào)度與死鎖 2) 進(jìn)程推進(jìn)順序非法 假設(shè)并發(fā)進(jìn)程P1和P2按曲線所示的順序推進(jìn)，它們將進(jìn)入不平安區(qū)D內(nèi)。此時P1堅持了資源R1, P2堅持了資源R2, 系統(tǒng)處于不平安形狀。由于，這時兩進(jìn)程再向前推進(jìn)，便能夠發(fā)生死鎖。例如，當(dāng)P1運(yùn)轉(zhuǎn)到P1:Request(R2)時，將因R2已被P2占用而阻塞；當(dāng)P2運(yùn)轉(zhuǎn)到P2: Request(R1)時，也將因R1已被P1占用

37、而阻塞，于是發(fā)生了進(jìn)程死鎖。 第三章 處理機(jī)調(diào)度與死鎖 3.5.2 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件 互斥條件 (2) 懇求和堅持條件 (3) 不剝奪條件 (4) 環(huán)路等待條件 第三章 處理機(jī)調(diào)度與死鎖 3.5.3 處置死鎖的根本方法處置死鎖的根本方法預(yù)防死鎖。 (2) 防止死鎖。 (3) 檢測死鎖。 (4) 解除死鎖。 第三章 處理機(jī)調(diào)度與死鎖 3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法 3.6.1 預(yù)防死鎖預(yù)防死鎖 摒棄“懇求和堅持條件 2. 摒棄“不剝奪條件 3. 摒棄“環(huán)路等待條件 第三章 處理機(jī)調(diào)度與死鎖 3.6.2 系統(tǒng)平安形狀系統(tǒng)平安形狀 1. 平安形狀 在防止死鎖的方法中，允許進(jìn)

38、程動態(tài)地懇求資源，但系統(tǒng)在進(jìn)展資源分配之前，應(yīng)先計算此次資源分配的平安性。假設(shè)此次分配不會導(dǎo)致系統(tǒng)進(jìn)入不平安形狀，那么將資源分配給進(jìn)程； 否那么，令進(jìn)程等待。 所謂平安形狀，是指系統(tǒng)能按某種進(jìn)程順序(P1, P2, ，Pn)(稱P1, P2, , Pn序列為平安序列)，來為每個進(jìn)程Pi分配其所需資源，直至滿足每個進(jìn)程對資源的最大需求，使每個進(jìn)程都可順利地完成。假設(shè)系統(tǒng)無法找到這樣一個平安序列，那么稱系統(tǒng)處于不平安形狀。 第三章 處理機(jī)調(diào)度與死鎖 2. 平安形狀之例平安形狀之例 我們經(jīng)過一個例子來闡明平安性。假定系統(tǒng)中有三個我們經(jīng)過一個例子來闡明平安性。假定系統(tǒng)中有三個進(jìn)程進(jìn)程P1、 P2和和P

39、3，共有，共有12臺磁帶機(jī)。進(jìn)程臺磁帶機(jī)。進(jìn)程P1總共要求總共要求10臺臺磁帶機(jī)，磁帶機(jī)，P2和和P3分別要求分別要求4臺和臺和9臺。假設(shè)在臺。假設(shè)在T0時辰，進(jìn)程時辰，進(jìn)程P1、P2和和P3已分別獲得已分別獲得5臺、臺、2臺和臺和2臺磁帶機(jī)，尚有臺磁帶機(jī)，尚有3臺空臺空閑未分配，如下表所示：閑未分配，如下表所示： 進(jìn) 程 最 大 需 求 已 分 配 可 用 P1P2P310495223第三章 處理機(jī)調(diào)度與死鎖 3. 由平安形狀向不平安形狀的轉(zhuǎn)換由平安形狀向不平安形狀的轉(zhuǎn)換 假設(shè)不按照平安序列分配資源，那么系統(tǒng)能夠會由平假設(shè)不按照平安序列分配資源，那么系統(tǒng)能夠會由平安形狀進(jìn)入不平安形狀。例如，

40、在安形狀進(jìn)入不平安形狀。例如，在T0時辰以后，時辰以后，P3又懇求又懇求1臺磁帶機(jī)，假設(shè)此時系統(tǒng)把剩余臺磁帶機(jī)，假設(shè)此時系統(tǒng)把剩余3臺中的臺中的1臺分配給臺分配給P3，那么系統(tǒng)便進(jìn)入不平安形狀。那么系統(tǒng)便進(jìn)入不平安形狀。 由于，此時也無法再找到一由于，此時也無法再找到一個平安序列，個平安序列， 例如，把其他的例如，把其他的2臺分配給臺分配給P2，這樣，在，這樣，在P2完成后只能釋放出完成后只能釋放出4臺，既不能滿足臺，既不能滿足P1尚需尚需5臺的要求，也臺的要求，也不能滿足不能滿足P3尚需尚需6臺的要求，致使它們都無法推進(jìn)到完成，臺的要求，致使它們都無法推進(jìn)到完成，彼此都在等待對方釋放資源，即

41、墮入僵局，結(jié)果導(dǎo)致死鎖。彼此都在等待對方釋放資源，即墮入僵局，結(jié)果導(dǎo)致死鎖。 第三章 處理機(jī)調(diào)度與死鎖 3.6.3 利用銀行家算法防止死鎖利用銀行家算法防止死鎖 1. 銀行家算法中的數(shù)據(jù)構(gòu)造銀行家算法中的數(shù)據(jù)構(gòu)造 (1) 可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改動。假設(shè)Availablej=K，那么表示系統(tǒng)中現(xiàn)有Rj類資源K個。 第三章 處理機(jī)調(diào)度與死鎖 (2) 最大需求矩陣Max。這是一個nm的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資

42、源的最大需求。假設(shè)Maxi,j=K，那么表示進(jìn)程i需求Rj類資源的最大數(shù)目為K。 (3) 分配矩陣Allocation。這也是一個nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。假設(shè)Allocationi,j=K，那么表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。 (4) 需求矩陣Need。這也是一個nm的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)。假設(shè)Needi,j=K，那么表示進(jìn)程i還需求Rj類資源K個，方能完成其義務(wù)。 Needi,j=Maxi,j-Allocationi,j 第三章 處理機(jī)調(diào)度與死鎖 2. 銀行家算法 設(shè)Requesti是進(jìn)程Pi的懇求向量，假設(shè)Reques

43、tij=K，表示進(jìn)程Pi需求K個Rj類型的資源。當(dāng)Pi發(fā)出資源懇求后，系統(tǒng)按下述步驟進(jìn)展檢查： (1) 假設(shè)RequestijNeedi,j，便轉(zhuǎn)向步驟2；否那么以為出錯，由于它所需求的資源數(shù)已超越它所宣布的最大值。 (2) 假設(shè)RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否那么， 表示尚無足夠資源，Pi須等待。 第三章 處理機(jī)調(diào)度與死鎖 (3) 系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修正下面數(shù)據(jù)構(gòu)造中的數(shù)值： Availablej =Availablej-Requestij; Allocationi,j =Allocationi,j+Requestij; Needi,j =Need

44、i,j-Requestij; (4) 系統(tǒng)執(zhí)行平安性算法，檢查此次資源分配后，系統(tǒng)能否處于平安形狀。假設(shè)平安，才正式將資源分配給進(jìn)程Pi，以完本錢次分配；否那么， 將本次的試探分配作廢，恢復(fù)原來的資源分配形狀，讓進(jìn)程Pi等待。 第三章 處理機(jī)調(diào)度與死鎖 3. 平安性算法平安性算法 (1) 設(shè)置兩個向量： 任務(wù)向量Work: 它表示系統(tǒng)可提供應(yīng)進(jìn)程繼續(xù)運(yùn)轉(zhuǎn)所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行平安算法開場時，Work =Available; Finish: 它表示系統(tǒng)能否有足夠的資源分配給進(jìn)程，使之運(yùn)轉(zhuǎn)完成。開場時先做Finishi =false; 當(dāng)有足夠資源分配給進(jìn)程時， 再令Finis

45、hi =true。 第三章 處理機(jī)調(diào)度與死鎖 (2) 從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程： Finishi=false; Needi,jWorkj； 假設(shè)找到， 執(zhí)行步驟(3)， 否那么，執(zhí)行步驟(4)。 (3) 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj =Worki+Allocationi,j; Finishi =true; go to step 2; (4) 假設(shè)一切進(jìn)程的Finishi=true都滿足， 那么表示系統(tǒng)處于平安形狀；否那么，系統(tǒng)處于不平安形狀。 第三章 處理機(jī)調(diào)度與死鎖 4. 銀行家算法之例銀行家算法之例 假定系統(tǒng)中有五個進(jìn)程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時辰的資源分配情況如圖 3-15 所示。 圖 3-15 T0時辰的資源分配表 第三章 處理機(jī)調(diào)度與死鎖 (1) T0時辰的平安性： 圖 3-16 T0時辰的平安序列 第三章 處理機(jī)調(diào)度與死鎖 (2) P1懇求資源：P1發(fā)出懇求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)展檢查： Request1(1, 0, 2)Need1(1, 2,