第3章處理機(jī)調(diào)度與死鎖

1、第三章 處理機(jī)調(diào)度與死鎖 第三章第三章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖 3.1 3.1 處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)3.2 3.2 作業(yè)與作業(yè)調(diào)度作業(yè)與作業(yè)調(diào)度3.3 3.3 進(jìn)程調(diào)度進(jìn)程調(diào)度 3.4 3.4 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 3.5 3.5 死鎖概述死鎖概述3.6 3.6 預(yù)防死鎖預(yù)防死鎖3.7 3.7 避免死鎖避免死鎖3.8 3.8 死鎖的檢測與解除死鎖的檢測與解除 第三章 處理機(jī)調(diào)度與死鎖 3.1 處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)3.1.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次 1. 高級調(diào)度高級調(diào)度(High Sched

2、uling) 也稱為也稱為作業(yè)調(diào)度作業(yè)調(diào)度或宏觀調(diào)度。用于決定把后備隊(duì)列中的哪或宏觀調(diào)度。用于決定把后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，為它們分配必要的資源，并創(chuàng)建進(jìn)程。些作業(yè)調(diào)入內(nèi)存，為它們分配必要的資源，并創(chuàng)建進(jìn)程。 高級調(diào)度的高級調(diào)度的運(yùn)行頻率比較低運(yùn)行頻率比較低，時(shí)間尺度通常是分鐘、小時(shí)，時(shí)間尺度通常是分鐘、小時(shí)或天。常用于或天。常用于批處理系統(tǒng)。批處理系統(tǒng)。 在每次執(zhí)行作業(yè)調(diào)度時(shí)，都須做出以下兩個(gè)決定在每次執(zhí)行作業(yè)調(diào)度時(shí)，都須做出以下兩個(gè)決定： 1 1） 接納多少個(gè)作業(yè)接納多少個(gè)作業(yè) 2 2） 接納哪些作業(yè)接納哪些作業(yè) 第三章 處理機(jī)調(diào)度與死鎖 2. 低級調(diào)度低級調(diào)度(Low Level

3、Scheduling) (搶占式和非搶占式搶占式和非搶占式) 也稱也稱微觀調(diào)度、進(jìn)程調(diào)度微觀調(diào)度、進(jìn)程調(diào)度/ /線程調(diào)度線程調(diào)度或短程調(diào)或短程調(diào)度。度。指根據(jù)某種原則從就緒隊(duì)列中選擇一個(gè)進(jìn)程指根據(jù)某種原則從就緒隊(duì)列中選擇一個(gè)進(jìn)程( (線程線程) )并把處理機(jī)分配給該進(jìn)程并把處理機(jī)分配給該進(jìn)程(線程線程)的具體操作。的具體操作。一般類型的操作系統(tǒng)中都一般類型的操作系統(tǒng)中都必須有低級調(diào)度。必須有低級調(diào)度。 低級調(diào)度的低級調(diào)度的運(yùn)行頻率很高運(yùn)行頻率很高，時(shí)間尺度通常是，時(shí)間尺度通常是毫秒級的，幾十毫秒（毫秒級的，幾十毫秒（10100ms10100ms）便進(jìn)行一次。）便進(jìn)行一次。思考：思考：低級調(diào)度是

4、否存在調(diào)幾個(gè)、調(diào)哪幾個(gè)的問題？低級調(diào)度是否存在調(diào)幾個(gè)、調(diào)哪幾個(gè)的問題？ 第三章 處理機(jī)調(diào)度與死鎖 3. 中級調(diào)度中級調(diào)度(Intermediate-Level Scheduling) 概念：概念：中級調(diào)度又稱中級調(diào)度又稱中程調(diào)度中程調(diào)度，是指在內(nèi)存使用情況，是指在內(nèi)存使用情況緊張時(shí)，將一些暫時(shí)不能運(yùn)行的講程（就緒緊張時(shí)，將一些暫時(shí)不能運(yùn)行的講程（就緒/ /阻塞）從內(nèi)存阻塞）從內(nèi)存對換到外存上（掛起）等待。當(dāng)以后內(nèi)存有足夠的空閑空對換到外存上（掛起）等待。當(dāng)以后內(nèi)存有足夠的空閑空間時(shí)，間時(shí)，中級調(diào)度中級調(diào)度再決定將合適的進(jìn)程（就緒）重新調(diào)入內(nèi)再決定將合適的進(jìn)程（就緒）重新調(diào)入內(nèi)存（激活），并修改

5、其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上存（激活），并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。等待進(jìn)程調(diào)度。 思考：引人中級調(diào)度的主要目的是什么？思考：引人中級調(diào)度的主要目的是什么？ 為了提高內(nèi)存的利用率和系統(tǒng)吞吐量。常用在為了提高內(nèi)存的利用率和系統(tǒng)吞吐量。常用在分時(shí)系分時(shí)系統(tǒng)及具有虛擬存儲器的系統(tǒng)統(tǒng)及具有虛擬存儲器的系統(tǒng)中。中。 它的它的運(yùn)行頻率介于高級調(diào)度和低級調(diào)度之間運(yùn)行頻率介于高級調(diào)度和低級調(diào)度之間。 第三章 處理機(jī)調(diào)度與死鎖 3.1.2 處理機(jī)調(diào)度算法的目標(biāo)處理機(jī)調(diào)度算法的目標(biāo) 1. 處理機(jī)調(diào)度算法的共同目標(biāo)處理機(jī)調(diào)度算法的共同目標(biāo) (1) 資源利用率資源利用率 (2) 公平性。公

6、平性是指應(yīng)使諸進(jìn)程都獲得合理的公平性。公平性是指應(yīng)使諸進(jìn)程都獲得合理的CPU 時(shí)間，不會發(fā)生進(jìn)程饑餓現(xiàn)象。時(shí)間，不會發(fā)生進(jìn)程饑餓現(xiàn)象。 (3) 平衡性。盡可能保持系統(tǒng)資源使用的平衡性。平衡性。盡可能保持系統(tǒng)資源使用的平衡性。 (4) 策略強(qiáng)制執(zhí)行策略強(qiáng)制執(zhí)行第三章 處理機(jī)調(diào)度與死鎖 帶權(quán)周轉(zhuǎn)時(shí)間：帶權(quán)周轉(zhuǎn)時(shí)間：作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)的周轉(zhuǎn)時(shí)間T T與系統(tǒng)為它提供服務(wù)的時(shí)間與系統(tǒng)為它提供服務(wù)的時(shí)間T TS S之比，即之比，即W W= =T/TT/TS S=(=(運(yùn)行時(shí)間運(yùn)行時(shí)間 + + 等待時(shí)間等待時(shí)間)/)/運(yùn)行時(shí)間運(yùn)行時(shí)間 =1 + =1 + 等待時(shí)間等待時(shí)間/ /運(yùn)行時(shí)間運(yùn)行時(shí)間 平均帶權(quán)周轉(zhuǎn)

7、時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間: : (1) 平均周轉(zhuǎn)時(shí)間短。平均周轉(zhuǎn)時(shí)間短。平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間描述為：描述為： iiiTnT11niSiiTTnW11周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間: :從作業(yè)提交到系統(tǒng)開始到完成為止的時(shí)間間隔。從作業(yè)提交到系統(tǒng)開始到完成為止的時(shí)間間隔。 即，運(yùn)行時(shí)間即，運(yùn)行時(shí)間+ +等待時(shí)間。等待時(shí)間。2. 批處理系統(tǒng)的目標(biāo)批處理系統(tǒng)的目標(biāo)第三章 處理機(jī)調(diào)度與死鎖 （2 2）系統(tǒng)吞吐量高。）系統(tǒng)吞吐量高。（3 3）處理機(jī)利用率高。）處理機(jī)利用率高。3.3.分時(shí)系統(tǒng)的目標(biāo)分時(shí)系統(tǒng)的目標(biāo)（1 1）響應(yīng)時(shí)間快。（2）均衡性。系統(tǒng)響應(yīng)時(shí)間的快慢應(yīng)與用戶所請求服務(wù)的復(fù)雜性相適應(yīng)。4.4.實(shí)時(shí)系統(tǒng)的目標(biāo)

8、實(shí)時(shí)系統(tǒng)的目標(biāo)（1）截止時(shí)間的保證。（2）可預(yù)測性。第三章 處理機(jī)調(diào)度與死鎖 3. 2 作業(yè)與作業(yè)調(diào)度作業(yè)與作業(yè)調(diào)度作業(yè)和作業(yè)步(1) 作業(yè)(Job)。程序、數(shù)據(jù)、作業(yè)說明書(2) 作業(yè)步(Job Step)。作業(yè)的每一個(gè)加工步驟2. 作業(yè)控制塊(Job Control Block，JCB) 它是作業(yè)在系統(tǒng)中存在的標(biāo)志存在的標(biāo)志，其中保存了系統(tǒng)對作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。在JCB中包含的內(nèi)容有：作業(yè)標(biāo)識、用戶名稱、用戶賬號、作業(yè)類型(CPU 繁忙型、I/O 繁忙型、批量型、終端型)、作業(yè)狀態(tài)、調(diào)度信息(優(yōu)先級、作業(yè)運(yùn)行時(shí)間)、資源需求(預(yù)計(jì)運(yùn)行時(shí)間、要求內(nèi)存大小等)、資源使用情況等。第

9、三章 處理機(jī)調(diào)度與死鎖 3. 作業(yè)運(yùn)行的三個(gè)階段和三種狀態(tài) 作業(yè)從進(jìn)入系統(tǒng)到運(yùn)行結(jié)束，通常需要經(jīng)歷收容、運(yùn)行和完成三個(gè)階段。相應(yīng)的作業(yè)也就有“后備狀態(tài)”、“運(yùn)行狀態(tài)”和“完成狀態(tài)”。(1) 收容階段。(2) 運(yùn)行階段。(3) 完成階段。第三章 處理機(jī)調(diào)度與死鎖 5.調(diào)度算法調(diào)度算法（1 1） 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法 該算法總是把處理機(jī)分配給最先進(jìn)入就緒隊(duì)列的該算法總是把處理機(jī)分配給最先進(jìn)入就緒隊(duì)列的進(jìn)程，一個(gè)進(jìn)程一旦分得處理機(jī)，便執(zhí)行下去，直到進(jìn)程，一個(gè)進(jìn)程一旦分得處理機(jī)，便執(zhí)行下去，直到該進(jìn)程完成或阻塞時(shí)，才釋放處理機(jī)。該進(jìn)程完成或阻塞時(shí)，才釋放處理機(jī)。用于作業(yè)調(diào)度用于作業(yè)調(diào)度

10、或進(jìn)程調(diào)度?；蜻M(jìn)程調(diào)度。 看一個(gè)例子：看一個(gè)例子：4.作業(yè)調(diào)度的主要任務(wù)作業(yè)調(diào)度的主要任務(wù) 根據(jù)JCB中的信息，檢查系統(tǒng)中的資源能否滿足作業(yè)對資源的需求，以及按照一定的調(diào)度算法，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源。然后再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上等待調(diào)度。第三章 處理機(jī)調(diào)度與死鎖 TST帶權(quán)周轉(zhuǎn)時(shí)間，帶權(quán)周轉(zhuǎn)時(shí)間， W=T/TS優(yōu)點(diǎn)優(yōu)點(diǎn): :實(shí)現(xiàn)簡單實(shí)現(xiàn)簡單. . 缺點(diǎn)缺點(diǎn): :沒考慮作業(yè)（進(jìn)程）的優(yōu)先級。利于長作業(yè)（進(jìn)程），沒考慮作業(yè)（進(jìn)程）的優(yōu)先級。利于長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。而不利于短作業(yè)（進(jìn)程）。算法的衡量算法的衡量平均周轉(zhuǎn)時(shí)間平

11、均周轉(zhuǎn)時(shí)間/平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間 第三章 處理機(jī)調(diào)度與死鎖 （2 2） 短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法 短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法SJ(P)FSJ(P)F，是指對短作業(yè)，是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度作業(yè)調(diào)度和進(jìn)程調(diào)度。和進(jìn)程調(diào)度。 短作業(yè)優(yōu)先短作業(yè)優(yōu)先(SJF)(SJF)的調(diào)度算法的調(diào)度算法：是：是從后備隊(duì)列中選擇從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間（一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間（CPUCPU執(zhí)行期）最短的作業(yè)，執(zhí)行期）最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。將它

12、們調(diào)入內(nèi)存運(yùn)行。 短進(jìn)程優(yōu)先短進(jìn)程優(yōu)先(SPF)(SPF)調(diào)度算法調(diào)度算法：則：則是從就緒隊(duì)列中選出是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度。棄處理機(jī)時(shí)，再重新調(diào)度。第三章 處理機(jī)調(diào)度與死鎖 圖圖 3-4 FCFS3-4 FCFS和和SJFSJF調(diào)度算法的性能調(diào)度算法的性能 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法第三章 處理機(jī)調(diào)度與死鎖 SJ(P)F SJ

13、(P)F調(diào)度算法也存在不容忽視的缺點(diǎn)調(diào)度算法也存在不容忽視的缺點(diǎn)： (1) (1) 該算法對長作業(yè)不利該算法對長作業(yè)不利 (2) (2) 該算法該算法完全未考慮作業(yè)的緊迫程度完全未考慮作業(yè)的緊迫程度，因而不能保證，因而不能保證緊迫性作業(yè)緊迫性作業(yè)( (進(jìn)程進(jìn)程) )會被及時(shí)處理。會被及時(shí)處理。 (3) (3) 由于由于作業(yè)作業(yè)( (進(jìn)程進(jìn)程) )的長短難以準(zhǔn)確地知道的長短難以準(zhǔn)確地知道，只是根據(jù)，只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的。用戶所提供的估計(jì)執(zhí)行時(shí)間而定的。第三章 處理機(jī)調(diào)度與死鎖 （3 3） 優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法 1）優(yōu)先級調(diào)度算

14、法）優(yōu)先級調(diào)度算法(基于作業(yè)的緊迫程度基于作業(yè)的緊迫程度) 該算法總是把處理機(jī)分配給就緒隊(duì)列中具有最該算法總是把處理機(jī)分配給就緒隊(duì)列中具有最高優(yōu)先級的作業(yè)（進(jìn)程）?？捎糜诟邇?yōu)先級的作業(yè)（進(jìn)程）?？捎糜谧鳂I(yè)調(diào)度或進(jìn)程作業(yè)調(diào)度或進(jìn)程調(diào)度。調(diào)度。2）高響應(yīng)比優(yōu)先調(diào)度算法）高響應(yīng)比優(yōu)先調(diào)度算法 要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán)優(yōu)先權(quán)的變化規(guī)律可描述為：優(yōu)先權(quán)的變化規(guī)律可描述為： 第三章 處理機(jī)調(diào)度與死鎖 由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對該作業(yè)的由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待

15、時(shí)間優(yōu)先權(quán)=1 +等待時(shí)間要求服務(wù)的時(shí)間 (1) (1) 如果等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈如果等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。高，因而該算法有利于短作業(yè)。 (2) (2) 當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)。間，等待時(shí)間愈長，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)。 (3) (3) 對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時(shí)間的增加而提高，對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長時(shí)，其優(yōu)先級

16、便可升到很高，當(dāng)其等待時(shí)間足夠長時(shí)，其優(yōu)先級便可升到很高， 從而也可獲得處從而也可獲得處理機(jī)。理機(jī)。 第三章 處理機(jī)調(diào)度與死鎖 作業(yè)作業(yè) 到達(dá)時(shí)間到達(dá)時(shí)間 運(yùn)行時(shí)間運(yùn)行時(shí)間 1 101 10：00 200 2小時(shí)小時(shí) 2 102 10：10 110 1小時(shí)小時(shí) 3 103 10：25 2525 25分鐘分鐘一個(gè)例子第三章 處理機(jī)調(diào)度與死鎖 3.3 進(jìn)程調(diào)度進(jìn)程調(diào)度 3.3.1 進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式 1. 進(jìn)程調(diào)度的任務(wù)(1) 保存處理機(jī)的現(xiàn)場信息。(2) 按某種算法選取進(jìn)程。(3) 把處理器分配給進(jìn)程。 第三章 處理機(jī)調(diào)度與死鎖 2. 進(jìn)程調(diào)度機(jī)制為了實(shí)現(xiàn)進(jìn)程調(diào)度，在進(jìn)程調(diào)度機(jī)制中，應(yīng)具

17、有如下三個(gè)基本部分，如圖3-1所示。(1) 排隊(duì)器。 (2) 分派器。 (3) 上下文切換器。 第三章 處理機(jī)調(diào)度與死鎖 3. 進(jìn)程調(diào)度方式（1）搶占式（2）非搶占式第三章 處理機(jī)調(diào)度與死鎖 3.3.2 輪轉(zhuǎn)調(diào)度算法輪轉(zhuǎn)調(diào)度算法 1. 1. 時(shí)間片輪轉(zhuǎn)法（早期）時(shí)間片輪轉(zhuǎn)法（早期）（1 1）所有的就緒進(jìn)程按）所有的就緒進(jìn)程按先來先服務(wù)先來先服務(wù)的原則，排成一個(gè)隊(duì)列的原則，排成一個(gè)隊(duì)列（2 2）每次調(diào)度時(shí)，把）每次調(diào)度時(shí)，把CPUCPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。（3 3）當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請求）當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由

18、一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請求, ,調(diào)度程調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；若時(shí)序便據(jù)此信號來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；若時(shí)間片沒有用完就執(zhí)行結(jié)束了，則立即激活調(diào)度程序，啟動新的時(shí)間片。間片沒有用完就執(zhí)行結(jié)束了，則立即激活調(diào)度程序，啟動新的時(shí)間片。（4 4）重復(fù)（）重復(fù)（2 2） （5 5） 思考：時(shí)間片小了好還是大了好？思考：時(shí)間片小了好還是大了好？ 若很小若很?。豪诙套鳂I(yè)，但中斷及切換頻繁，增加系統(tǒng)開銷。：利于短作業(yè)，但中斷及切換頻繁，增加系統(tǒng)開銷。 若很大若很大：退化為：退化為FCFSFCFS算法，無法滿足交互式用戶的需求。算法，無法滿足交互

19、式用戶的需求。第三章 處理機(jī)調(diào)度與死鎖 例子（q=1、4）第三章 處理機(jī)調(diào)度與死鎖 3.3.4 多隊(duì)列調(diào)度算法多隊(duì)列調(diào)度算法 將一個(gè)就緒隊(duì)列拆成若干個(gè) 不同類型或不同性質(zhì)的進(jìn)程固定在不同的就緒隊(duì)列 不同的就緒隊(duì)列用不同的調(diào)度算法 設(shè)置不同的優(yōu)先級第三章 處理機(jī)調(diào)度與死鎖 3.3.5多級反饋隊(duì)列調(diào)度算法多級反饋隊(duì)列調(diào)度算法 1.調(diào)度機(jī)制調(diào)度機(jī)制 (1) 應(yīng)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)應(yīng)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級和時(shí)間片。先級和時(shí)間片。 第一個(gè)隊(duì)列的優(yōu)先級最高，第一個(gè)隊(duì)列的優(yōu)先級最高，第二個(gè)隊(duì)列次之，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。其余各隊(duì)列的優(yōu)先權(quán)逐

20、個(gè)降低。 優(yōu)先權(quán)愈高的隊(duì)列中，執(zhí)行時(shí)間片就愈小。優(yōu)先權(quán)愈高的隊(duì)列中，執(zhí)行時(shí)間片就愈小。第三章 處理機(jī)調(diào)度與死鎖 圖圖 3-5 多級反饋隊(duì)列調(diào)度算法多級反饋隊(duì)列調(diào)度算法 最高優(yōu)先權(quán)次高優(yōu)先權(quán)最低優(yōu)先權(quán)第三章 處理機(jī)調(diào)度與死鎖 (2) 當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按尾，按FCFS原則排隊(duì)等待調(diào)度。原則排隊(duì)等待調(diào)度。(3) 僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)诔踢\(yùn)行；僅當(dāng)?shù)?(i-1) 隊(duì)列均空時(shí)，才會調(diào)度第隊(duì)列均空時(shí)，才會調(diào)度第i隊(duì)列中的隊(duì)列中的進(jìn)程運(yùn)行

21、進(jìn)程運(yùn)行思考：思考：（1）當(dāng)正在執(zhí)行）當(dāng)正在執(zhí)行i隊(duì)列的進(jìn)程時(shí)，高優(yōu)先級的隊(duì)列來隊(duì)列的進(jìn)程時(shí)，高優(yōu)先級的隊(duì)列來了新進(jìn)程，該如何處理？了新進(jìn)程，該如何處理？（2）被中斷的進(jìn)程進(jìn)入哪個(gè)就緒隊(duì)列？）被中斷的進(jìn)程進(jìn)入哪個(gè)就緒隊(duì)列？第三章 處理機(jī)調(diào)度與死鎖 2. 多級反饋隊(duì)列調(diào)度算法的性能多級反饋隊(duì)列調(diào)度算法的性能 終端型作業(yè)用戶終端型作業(yè)用戶。大多屬于交互型的小作業(yè)。大多屬于交互型的小作業(yè) ，系統(tǒng)，系統(tǒng)能使它們在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成。能使它們在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成。(2)(2)短批處理作業(yè)用戶短批處理作業(yè)用戶。很短的批處理作業(yè)像終端型作。很短的批處理作業(yè)像終端型作業(yè)一樣在第一隊(duì)列即可完

22、成，對于稍長的作業(yè)，也業(yè)一樣在第一隊(duì)列即可完成，對于稍長的作業(yè)，也只需在第二隊(duì)列和第三隊(duì)列各執(zhí)行一個(gè)時(shí)間片就可只需在第二隊(duì)列和第三隊(duì)列各執(zhí)行一個(gè)時(shí)間片就可完成。完成。 (3)(3)長批處理作業(yè)用戶長批處理作業(yè)用戶。它將依次在第。它將依次在第1 1，2 2，n n個(gè)隊(duì)個(gè)隊(duì)列中運(yùn)行，最后按輪轉(zhuǎn)方式運(yùn)行。列中運(yùn)行，最后按輪轉(zhuǎn)方式運(yùn)行。能滿足各種類型用戶的需要：能滿足各種類型用戶的需要：第三章 處理機(jī)調(diào)度與死鎖 3.3.6 基于公平原則的調(diào)度算法基于公平原則的調(diào)度算法 1. 保證調(diào)度算法保證調(diào)度算法是另外一種類型的調(diào)度算法，它向用戶所做出的保證并不是優(yōu)先運(yùn)行，而是明確的性能保證，該算法可以做到調(diào)度的公

23、平性。一種比較容易實(shí)現(xiàn)的性能保證是處理機(jī)分配的公平性。保證每個(gè)進(jìn)程獲得相同的處理機(jī)時(shí)間。 第三章 處理機(jī)調(diào)度與死鎖 在實(shí)施公平調(diào)度算法時(shí)系統(tǒng)中必須具有這樣一些功能：(1) 跟蹤計(jì)算每個(gè)進(jìn)程自創(chuàng)建以來已經(jīng)執(zhí)行的處理時(shí)間。(2) 計(jì)算每個(gè)進(jìn)程應(yīng)獲得的處理機(jī)時(shí)間，即自創(chuàng)建以來的時(shí)間除以n。(3) 計(jì)算進(jìn)程獲得處理機(jī)時(shí)間的比率，即進(jìn)程實(shí)際執(zhí)行的處理時(shí)間和應(yīng)獲得的處理機(jī)時(shí)間之比。(4) 比較各進(jìn)程獲得處理機(jī)時(shí)間的比率。(5) 調(diào)度程序應(yīng)選擇比率最小的進(jìn)程將處理機(jī)分配給它，并讓該進(jìn)程一直運(yùn)行，直到超過最接近它的進(jìn)程比率為止。第三章 處理機(jī)調(diào)度與死鎖 2. 公平分享調(diào)度算法分配給每個(gè)進(jìn)程相同的處理機(jī)時(shí)間，顯

24、然，這對諸進(jìn)程而言，是體現(xiàn)了一定程度的公平，但如果各個(gè)用戶所擁有的進(jìn)程數(shù)不同，就會發(fā)生對用戶的不公平問題。 用戶A：啟動4個(gè)進(jìn)程用戶B：啟動1個(gè)進(jìn)程每個(gè)進(jìn)程獲得一個(gè)時(shí)間，對進(jìn)程而言很公平，但對用戶來說，A（80%）、B（20%）很不公平第三章 處理機(jī)調(diào)度與死鎖 3.4 實(shí)實(shí) 時(shí)時(shí) 調(diào)調(diào) 度度 3.4.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件 1. 提供必要的信息提供必要的信息 就緒時(shí)間。就緒時(shí)間。(2) 開始截止時(shí)間和完成截止時(shí)間。開始截止時(shí)間和完成截止時(shí)間。 (3) 處理時(shí)間。處理時(shí)間。 (4) 資源要求。資源要求。 (5) 優(yōu)先級。優(yōu)先級。 第三章 處理機(jī)調(diào)度與死鎖 2. 系統(tǒng)處理

25、能力強(qiáng)系統(tǒng)處理能力強(qiáng) 假定系統(tǒng)中有假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間可表示為間可表示為Ci，周期時(shí)間表示為，周期時(shí)間表示為Pi，則在單處理機(jī)情況下，則在單處理機(jī)情況下，必須滿足下面的限制條件系統(tǒng)才是可調(diào)度的：必須滿足下面的限制條件系統(tǒng)才是可調(diào)度的： miiiPC11即保證每個(gè)實(shí)時(shí)任務(wù)在一個(gè)周期時(shí)間內(nèi)得到及時(shí)處理即保證每個(gè)實(shí)時(shí)任務(wù)在一個(gè)周期時(shí)間內(nèi)得到及時(shí)處理第三章 處理機(jī)調(diào)度與死鎖 例如例如: :系統(tǒng)中有系統(tǒng)中有6個(gè)硬實(shí)時(shí)任務(wù)，它們的周期時(shí)間都是個(gè)硬實(shí)時(shí)任務(wù)，它們的周期時(shí)間都是 50 ms，而每次的處理時(shí)間為而每次的處理時(shí)間為 10 ms，則不難

26、算出，此時(shí)是不能滿足上式，則不難算出，此時(shí)是不能滿足上式的，的，(10/50)*6 = 1.21，因而系統(tǒng)是，因而系統(tǒng)是不可調(diào)度的不可調(diào)度的。 再如再如:一個(gè)實(shí)時(shí)系統(tǒng)要處理一個(gè)實(shí)時(shí)系統(tǒng)要處理3 3個(gè)事件，其出現(xiàn)周期分別為個(gè)事件，其出現(xiàn)周期分別為100ms100ms、200ms200ms和和500ms500ms，事件的處理時(shí)間分別為，事件的處理時(shí)間分別為50ms50ms、30ms30ms和和100ms100ms，則這個(gè)系統(tǒng)是任務(wù)，則這個(gè)系統(tǒng)是任務(wù)可調(diào)度的可調(diào)度的，因?yàn)椋?，因?yàn)椋?0/100 + 30/200 50/100 + 30/200 + 100/500 =0.85 1 + 100/500

27、=0.85 1 當(dāng)然隱含的條件是進(jìn)程切換的時(shí)間足夠短，可以忽略不計(jì)。當(dāng)然隱含的條件是進(jìn)程切換的時(shí)間足夠短，可以忽略不計(jì)。第三章 處理機(jī)調(diào)度與死鎖 系統(tǒng)不可調(diào)度時(shí)解決的方法是系統(tǒng)不可調(diào)度時(shí)解決的方法是提高系統(tǒng)的處理提高系統(tǒng)的處理能力，其途徑有二：能力，其途徑有二： 其一其一仍是采用單處理機(jī)系統(tǒng)，仍是采用單處理機(jī)系統(tǒng)， 但須但須增強(qiáng)其處增強(qiáng)其處理能力理能力， 以顯著地以顯著地減少對每一個(gè)任務(wù)的處理時(shí)間減少對每一個(gè)任務(wù)的處理時(shí)間； 其二其二是采用是采用多處理機(jī)系統(tǒng)。多處理機(jī)系統(tǒng)。假定系統(tǒng)中的假定系統(tǒng)中的處理處理機(jī)數(shù)為機(jī)數(shù)為N N，則應(yīng)將上述的限制條件改為：，則應(yīng)將上述的限制條件改為：miiiNPC1

28、第三章 處理機(jī)調(diào)度與死鎖 3. 采用搶占式調(diào)度機(jī)制采用搶占式調(diào)度機(jī)制 4. 具有快速切換機(jī)制具有快速切換機(jī)制 (1) 對外部中斷的快速響應(yīng)能力對外部中斷的快速響應(yīng)能力。要求系統(tǒng)具有快速。要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔盡量短盡量短。 (2) 快速的任務(wù)分派能力快速的任務(wù)分派能力。第三章 處理機(jī)調(diào)度與死鎖 3.4.2 實(shí)時(shí)調(diào)度算法的分類實(shí)時(shí)調(diào)度算法的分類 1. 1. 非搶占式調(diào)度算法非搶占式調(diào)度算法 非搶占式輪轉(zhuǎn)調(diào)度算法。（如下頁圖（非搶占式輪轉(zhuǎn)調(diào)度算法。（如下頁圖（a a） (2) (2) 非搶占式優(yōu)先調(diào)度算法。非搶占式優(yōu)先調(diào)度算法。

29、（如下頁圖（如下頁圖（b） 可按不同的方式加以分類，如根據(jù)任務(wù)性質(zhì)的不可按不同的方式加以分類，如根據(jù)任務(wù)性質(zhì)的不同、調(diào)度方式的不同、調(diào)度程序調(diào)度時(shí)間的不同和多同、調(diào)度方式的不同、調(diào)度程序調(diào)度時(shí)間的不同和多處理機(jī)環(huán)境下的調(diào)度等分類。處理機(jī)環(huán)境下的調(diào)度等分類。下面僅按調(diào)度方式的不下面僅按調(diào)度方式的不同對調(diào)度算法進(jìn)行分類：同對調(diào)度算法進(jìn)行分類： 簡單、易實(shí)現(xiàn)。簡單、易實(shí)現(xiàn)。第三章 處理機(jī)調(diào)度與死鎖 (a) 非搶占輪轉(zhuǎn)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程請求調(diào)度實(shí)時(shí)進(jìn)程槍占當(dāng)前進(jìn)程，并立即執(zhí)行(d) 立即搶占的優(yōu)先權(quán)調(diào)度調(diào)度時(shí)間進(jìn)程 1進(jìn)程 2實(shí)時(shí)進(jìn)程要求調(diào)度進(jìn)程 n實(shí)時(shí)進(jìn)程調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行(b) 非搶占優(yōu)先

30、權(quán)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程請求調(diào)度當(dāng)前進(jìn)程運(yùn)行完成調(diào)度時(shí)間當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程請求調(diào)度時(shí)鐘中斷到來時(shí)調(diào)度時(shí)間(c) 基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度調(diào)度時(shí)間實(shí)時(shí)進(jìn)程2. 搶占式調(diào)度算法搶占式調(diào)度算法 基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法?；跁r(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法。( (如下圖如下圖c)c)(2) (2) 立即搶占的優(yōu)先權(quán)調(diào)度算法。立即搶占的優(yōu)先權(quán)調(diào)度算法。( (如下圖如下圖d) d) 圖 3-6 實(shí)時(shí)進(jìn)程調(diào)度 .第三章 處理機(jī)調(diào)度與死鎖 3.4.3最早截止時(shí)間優(yōu)先即最早截止時(shí)間優(yōu)先即EDF算法算法(開始截至?xí)r間開始截至?xí)r間) 圖圖 3-7 EDF3-7 EDF算法用于非搶占調(diào)度方式算法

31、用于非搶占調(diào)度方式 任務(wù)任務(wù)1 1的開始截至?xí)r間的開始截至?xí)r間1342時(shí)間時(shí)間t t時(shí)間 該算法依據(jù)截止時(shí)間確定任務(wù)的優(yōu)先級，截止時(shí)間越早，優(yōu)先級越高。（1）非搶占式調(diào)度方式用于非周期性實(shí)時(shí)任務(wù)第三章 處理機(jī)調(diào)度與死鎖 （1）搶占式調(diào)度方式用于周期性實(shí)時(shí)任務(wù)A：周期20ms 處理時(shí)間：10msB：周期50ms 處理時(shí)間：25ms思考：這兩個(gè)實(shí)時(shí)任務(wù)的處理軌跡第三章 處理機(jī)調(diào)度與死鎖 第三章 處理機(jī)調(diào)度與死鎖 2. 2. 最低松弛度優(yōu)先即最低松弛度優(yōu)先即LLF(Least Laxity First)LLF(Least Laxity First)算法算法 該算法是根據(jù)任務(wù)緊急該算法是根據(jù)任務(wù)緊急(

32、 (或松弛或松弛) )的程度，來確定任務(wù)的優(yōu)先級。的程度，來確定任務(wù)的優(yōu)先級。 任務(wù)的松弛度任務(wù)的松弛度= =任務(wù)必須完成時(shí)間任務(wù)必須完成時(shí)間- -其本身的運(yùn)行時(shí)間其本身的運(yùn)行時(shí)間- -當(dāng)前時(shí)間當(dāng)前時(shí)間 該算法主要用于可搶占調(diào)度方式中。該算法主要用于可搶占調(diào)度方式中。 如上例：如上例：A A和和B B兩個(gè)周期性任務(wù)，它們的周期和處理時(shí)間為兩個(gè)周期性任務(wù)，它們的周期和處理時(shí)間為A A（20,1020,10）、）、B B（50,2550,25）A1A2A3A4A5A6A7A820406080100120140160B1B2B3t01070554530第三章 處理機(jī)調(diào)度與死鎖 執(zhí)行過程（板書）：執(zhí)行

33、過程（板書）：t1A1(10)10203040506080t0t1 0B1(20)t2t370A2(10)A3(10)A4(10)t4t5t6t7t8B1(5)B2(15)B2(10)第三章 處理機(jī)調(diào)度與死鎖 3.4.5 優(yōu)先級倒置(priority inversion problem) 1. 優(yōu)先級倒置的形成當(dāng)前OS廣泛采用優(yōu)先級調(diào)度算法和搶占方式，然而在系統(tǒng)中存在著影響進(jìn)程運(yùn)行的資源而可能產(chǎn)生“優(yōu)先級倒置”的現(xiàn)象，即高優(yōu)先級進(jìn)程(或線程)被低優(yōu)先級進(jìn)程(或線程)延遲或阻塞。我們通過一個(gè)例子來說明該問題。 P1:P(mutex);CS-1;V(mutex); 優(yōu)先級最高P2:program2

34、; 優(yōu)先級其次P3: :P(mutex);CS-3;V(mutex); 優(yōu)先級最底第三章 處理機(jī)調(diào)度與死鎖 假如P3最先執(zhí)行，在執(zhí)行了P(mutex)操作后，進(jìn)入到臨界區(qū)CS-3。在時(shí)刻a，P2就緒，因?yàn)樗萈3的優(yōu)先級高，P2搶占了P3的處理機(jī)而運(yùn)行，如圖3-10所示。 第三章 處理機(jī)調(diào)度與死鎖 2. 優(yōu)先級倒置的解決方法（1）規(guī)定：假如進(jìn)程P3在進(jìn)入臨界區(qū)后P3所占用的處理機(jī)就不允許被搶占。 （2）采用動態(tài)優(yōu)先級繼承方法。第三章 處理機(jī)調(diào)度與死鎖 作業(yè) 四個(gè)作業(yè)進(jìn)入系統(tǒng)，分別計(jì)算在FCFS，SJF和HRRF算法下的平均周轉(zhuǎn)時(shí)間與帶權(quán)周轉(zhuǎn)時(shí)間（時(shí)間用十進(jìn)制表示，單位：小時(shí)）第三章 處理機(jī)調(diào)度

35、與死鎖 3.53.5 死鎖概述死鎖概述 指指多個(gè)多個(gè)進(jìn)程因進(jìn)程因競爭共享資源競爭共享資源而造成的一種而造成的一種僵僵局局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。在這些進(jìn)程中，每個(gè)進(jìn)程都無限等向前推進(jìn)。在這些進(jìn)程中，每個(gè)進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到的資源，這種現(xiàn)象稱為永遠(yuǎn)無法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖進(jìn)程死鎖，這一組進(jìn)程就稱為這一組進(jìn)程就稱為死鎖進(jìn)程死鎖進(jìn)程。3.5.1 3.5.1 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 第三章 處理機(jī)調(diào)度與死鎖 1. 1. 競爭資源引起進(jìn)程死鎖

36、競爭資源引起進(jìn)程死鎖 資源的分類資源的分類：可搶占性資源、不：可搶占性資源、不可搶占性可搶占性資源；可資源；可重用性（永久性）資源和可消耗性（臨時(shí)性）資源。重用性（永久性）資源和可消耗性（臨時(shí)性）資源。2) 2) 競爭不可搶占性資源競爭不可搶占性資源 3.5.1 3.5.1 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 R1R2P1P2進(jìn)程進(jìn)程磁帶機(jī)磁帶機(jī)打印機(jī)打印機(jī)圖圖 3-12 I/O3-12 I/O設(shè)備共享時(shí)的死鎖情況設(shè)備共享時(shí)的死鎖情況 第三章 處理機(jī)調(diào)度與死鎖 圖圖 3-13 3-13 進(jìn)程之間通信時(shí)的死鎖進(jìn)程之間通信時(shí)的死鎖 3) 3) 競爭可競爭可消耗性消耗性資源資源( (臨時(shí)性資源臨時(shí)性資源)

37、 )S2P1S3P3S1P2消息消息消息消息消息消息 例如例如：三進(jìn)程通信，各進(jìn)程先接收對方的消息，：三進(jìn)程通信，各進(jìn)程先接收對方的消息，再釋放自己產(chǎn)生的消息，則可能發(fā)生死鎖，如下圖：再釋放自己產(chǎn)生的消息，則可能發(fā)生死鎖，如下圖：第三章 處理機(jī)調(diào)度與死鎖 2. 進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程推進(jìn)順序不當(dāng)引起死鎖 圖圖 3-14 3-14 進(jìn)程推進(jìn)順序?qū)λ梨i的影響進(jìn)程推進(jìn)順序?qū)λ梨i的影響 第三章 處理機(jī)調(diào)度與死鎖 思考總結(jié)：死鎖的一些結(jié)論思考總結(jié)：死鎖的一些結(jié)論 參與死鎖的進(jìn)程最少是幾個(gè)？參與死鎖的進(jìn)程最少是幾個(gè)？ 兩個(gè)兩個(gè) 參與死鎖的進(jìn)程至少有幾個(gè)已經(jīng)占有資源？參與死鎖的進(jìn)程至少有幾個(gè)已經(jīng)占有資

38、源？ 兩個(gè)兩個(gè) 參與死鎖進(jìn)程有幾個(gè)在等待資源？參與死鎖進(jìn)程有幾個(gè)在等待資源？ 所有死鎖進(jìn)程所有死鎖進(jìn)程 參與死鎖的進(jìn)程構(gòu)成的集合與是當(dāng)前系統(tǒng)中所有進(jìn)參與死鎖的進(jìn)程構(gòu)成的集合與是當(dāng)前系統(tǒng)中所有進(jìn)程構(gòu)成的集合什么關(guān)系？程構(gòu)成的集合什么關(guān)系？ 子集子集第三章 處理機(jī)調(diào)度與死鎖 3.5.2 3.5.2 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件 （1 1）互斥條件）互斥條件 （2 2）請求和保持條件）請求和保持條件 （3 3）不剝奪條件）不剝奪條件 （4 4）環(huán)路等待條件）環(huán)路等待條件 第三章 處理機(jī)調(diào)度與死鎖 3.5.3 3.5.3 處理死鎖的基本方法處理死鎖的基本方法 預(yù)防死鎖。預(yù)防死鎖。 (2) (2

39、) 避免死鎖。避免死鎖。 (3) (3) 檢測死鎖。檢測死鎖。 (4) (4) 解除死鎖。解除死鎖。 第三章 處理機(jī)調(diào)度與死鎖 3.6 3.6 預(yù)防死鎖預(yù)防死鎖 破壞破壞“請求和保持請求和保持”條件。條件。所有進(jìn)程開始運(yùn)行之前，一次性申請其在整個(gè)運(yùn)所有進(jìn)程開始運(yùn)行之前，一次性申請其在整個(gè)運(yùn)行過程中所需要的全部資源。行過程中所需要的全部資源。缺點(diǎn)缺點(diǎn)資源浪費(fèi)、饑餓資源浪費(fèi)、饑餓允許一個(gè)進(jìn)程只獲得運(yùn)行初期所需要的資源后便允許一個(gè)進(jìn)程只獲得運(yùn)行初期所需要的資源后便開始運(yùn)行，運(yùn)行過程中，逐步釋放已分配給自己、開始運(yùn)行，運(yùn)行過程中，逐步釋放已分配給自己、且已經(jīng)使用完畢的全部資源，然后再請求新的所且已經(jīng)使

40、用完畢的全部資源，然后再請求新的所需資源。需資源。 在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死鎖。具體的做法是發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個(gè)破壞產(chǎn)生死鎖的四個(gè)必要條件之一。必要條件之一。第三章 處理機(jī)調(diào)度與死鎖 3.3.破壞破壞“循環(huán)等待循環(huán)等待”條件條件。將所有的資源按照類型進(jìn)行線性排隊(duì)，并賦予將所有的資源按照類型進(jìn)行線性排隊(duì)，并賦予不同的序號，規(guī)定申請資源時(shí)要按照序號遞增不同的序號，規(guī)定申請資源時(shí)要按照序號遞增的次序申請資源。的次序申請資源。缺點(diǎn)：限制新設(shè)備的增加、資源浪費(fèi)、限制用缺點(diǎn)：限制新設(shè)備的增加、資源浪費(fèi)、限制用戶簡單、自主地編程。戶簡

41、單、自主地編程。2.2.破壞破壞“不可搶占不可搶占”條件條件 。當(dāng)某進(jìn)程新的資源未滿足時(shí)，釋放已占有的所當(dāng)某進(jìn)程新的資源未滿足時(shí)，釋放已占有的所有資源。有資源。缺點(diǎn)：前段工作丟失、很難保證連續(xù)、執(zhí)行被缺點(diǎn)：前段工作丟失、很難保證連續(xù)、執(zhí)行被無限推遲）無限推遲）第三章 處理機(jī)調(diào)度與死鎖 1. 1. 安全狀態(tài)安全狀態(tài) 所謂所謂安全狀態(tài)安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序，是指系統(tǒng)能按某種進(jìn)程順序(P(P1 1, P, P2 2, , ，P Pn n)()(稱稱P P1 1, P, P2 2, , P, , Pn n序列為序列為安全序列安全序列) )，來為每個(gè)進(jìn)程，來為每個(gè)進(jìn)程P Pi i分配其所需資

42、源，直至滿足每個(gè)進(jìn)程對資源的最大需求，分配其所需資源，直至滿足每個(gè)進(jìn)程對資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。使每個(gè)進(jìn)程都可順利地完成。 如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不不安全狀態(tài)安全狀態(tài)。 當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)后，當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)后，可能可能進(jìn)入死鎖狀態(tài)。但只要進(jìn)入死鎖狀態(tài)。但只要系統(tǒng)處于安全狀態(tài)，就一定不會進(jìn)入死鎖狀態(tài)。系統(tǒng)處于安全狀態(tài)，就一定不會進(jìn)入死鎖狀態(tài)。3.7 3.7 死鎖避免死鎖避免3.7.1 3.7.1 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)第三章 處理機(jī)調(diào)度與死鎖 2. 2. 安全狀態(tài)之例安全狀態(tài)之例 假定系統(tǒng)中有三個(gè)進(jìn)

43、程假定系統(tǒng)中有三個(gè)進(jìn)程P P1 1、 P P2 2和和P P3 3，共有，共有1212臺磁帶機(jī)。臺磁帶機(jī)。進(jìn)程進(jìn)程P P1 1總共要求總共要求1010臺磁帶機(jī)，臺磁帶機(jī)，P P2 2和和P P3 3分別要求分別要求4 4臺和臺和9 9臺。假臺。假設(shè)在設(shè)在T T0 0時(shí)刻，進(jìn)程時(shí)刻，進(jìn)程P P1 1、P P2 2和和P P3 3已分別獲得已分別獲得5 5臺、臺、2 2臺和臺和2 2臺磁臺磁帶機(jī)，尚有帶機(jī)，尚有3 3臺空閑未分配，如下表所示：臺空閑未分配，如下表所示： 經(jīng)分析經(jīng)分析T0時(shí)刻系統(tǒng)是安全的，此時(shí)存在安全序列時(shí)刻系統(tǒng)是安全的，此時(shí)存在安全序列P2P3。第三章 處理機(jī)調(diào)度與死鎖 3. 3.

44、 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果不按照安全序列分配資源，則系統(tǒng)可能會由安全如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進(jìn)入不安全狀態(tài)狀態(tài)進(jìn)入不安全狀態(tài)。 例如例如，在，在T T0 0時(shí)刻以后，時(shí)刻以后，P P3 3又請求又請求1 1臺磁帶機(jī)，若此時(shí)系臺磁帶機(jī)，若此時(shí)系統(tǒng)把剩余統(tǒng)把剩余3 3臺中的臺中的1 1臺分配給臺分配給P P3 3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。，則系統(tǒng)便進(jìn)入不安全狀態(tài)。 因?yàn)?，因?yàn)?，此時(shí)也無法再找到一個(gè)安全序列此時(shí)也無法再找到一個(gè)安全序列第三章 處理機(jī)調(diào)度與死鎖 3.7.2 3.7.2 利用銀行家算法避免死鎖利用銀行家算法避免死鎖 1. 1

45、. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) (1) 可利用資源向量可利用資源向量AvailableAvailable。 這是一個(gè)含有這是一個(gè)含有m m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，一類可利用的資源數(shù)目，其初始值其初始值是系統(tǒng)中所配置的該類是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。動態(tài)地改變。 如果如果Availablej=K，則表示系統(tǒng)中現(xiàn)有，則表示系統(tǒng)中現(xiàn)有R Rj j類資源類資源K K個(gè)。個(gè)。 第三章 處理機(jī)調(diào)度與死鎖 (2)

46、(2) 最大需求矩陣最大需求矩陣MaxMax。這是一個(gè)。這是一個(gè)n nm m的矩陣，它定義了的矩陣，它定義了系統(tǒng)中系統(tǒng)中n n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對個(gè)進(jìn)程中的每一個(gè)進(jìn)程對m m類資源的最大需求。類資源的最大需求。如果如果Maxi,j=K, ,則表示進(jìn)程則表示進(jìn)程i i需要需要R Rj j類資源的最大數(shù)目為類資源的最大數(shù)目為K.K. (3) (3) 分配矩陣分配矩陣AllocationAllocation。這也是一個(gè)。這也是一個(gè)n nm m的矩陣，它的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如如果果Allocationi,j

47、=K，則表示進(jìn)程，則表示進(jìn)程i i當(dāng)前已分得當(dāng)前已分得R Rj j類資源的數(shù)類資源的數(shù)目為目為K K。 (4) (4) 需求矩陣需求矩陣NeedNeed。這也是一個(gè)。這也是一個(gè)n nm m的矩陣，用以表示每的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。一個(gè)進(jìn)程尚需的各類資源數(shù)。如果如果Needi,j=K，則表示進(jìn)，則表示進(jìn)程程i i還需要還需要R Rj j類資源類資源K K個(gè)，方能完成其任務(wù)。個(gè)，方能完成其任務(wù)。 可得：可得：Needi,j= Maxi,j- Allocationi,j 第三章 處理機(jī)調(diào)度與死鎖 2. 2. 銀行家算法銀行家算法 設(shè)設(shè)RequestRequesti i是進(jìn)程是進(jìn)程

48、P Pi i的請求向量，的請求向量，如果如果Requestij=K，表示進(jìn)程，表示進(jìn)程P Pi i當(dāng)前時(shí)刻請求當(dāng)前時(shí)刻請求K K個(gè)個(gè)R Rj j類型的資源類型的資源。當(dāng)。當(dāng)P Pi i發(fā)出發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查： (1) (1) 如果如果RequestijNeedi,j，便轉(zhuǎn)向步驟便轉(zhuǎn)向步驟2 2；否則認(rèn)為出錯(cuò)。否則認(rèn)為出錯(cuò)。 (2) (2) 如果如果RequestijAvailablej，便轉(zhuǎn)向步驟便轉(zhuǎn)向步驟(3)(3)；否則，；否則， 表示尚無足夠資源，表示尚無足夠資源，P Pi i須等待。須等待。 第三章 處理機(jī)調(diào)度與死鎖 (3) (3

49、) 系統(tǒng)試探著把資源分配給進(jìn)程系統(tǒng)試探著把資源分配給進(jìn)程P Pi i，并修改下面數(shù)據(jù)，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：結(jié)構(gòu)中的數(shù)值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij; (4) (4) 系統(tǒng)執(zhí)行安全性算法系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程若安全，才正式將資源分配給進(jìn)程P Pi i，以完成本次分配；以完成本次分配；否則，將本次的試探分配作廢

50、否則，將本次的試探分配作廢，恢復(fù)原來，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程的資源分配狀態(tài)，讓進(jìn)程P Pi i等待。等待。 第三章 處理機(jī)調(diào)度與死鎖 3. 3. 安全性算法安全性算法 (1) (1) 設(shè)置兩個(gè)向量：設(shè)置兩個(gè)向量： 工作向量工作向量Work:Work: 它表示系統(tǒng)可提供給進(jìn)程繼續(xù)它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有運(yùn)行所需的各類資源數(shù)目，它含有m m個(gè)元素，在執(zhí)行安個(gè)元素，在執(zhí)行安全算法全算法開始時(shí)，開始時(shí)，Work=Available; ; Finish Finish: : 它表示系統(tǒng)是否有足夠的資源分配給它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先

51、做進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finishi=false; ; 當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finishi=true。 第三章 處理機(jī)調(diào)度與死鎖 (2) (2) 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi= =false; Needi,jWorkj； 若找到，執(zhí)行步驟若找到，執(zhí)行步驟(3)(3)，否則，執(zhí)行步驟，否則，執(zhí)行步驟(4)(4)。 (3) (3) 當(dāng)進(jìn)程當(dāng)進(jìn)程P Pi i獲得資源后，可順利執(zhí)行，直至完成，并獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，釋放出分配給它的資源，故應(yīng)執(zhí)行：

52、故應(yīng)執(zhí)行： Workj=Workj+ Allocationi,j; Finishi=true; go to step 2; (4) (4) 如果所有進(jìn)程的如果所有進(jìn)程的FinishFinishi i=true=true都滿足，都滿足， 則表則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 第三章 處理機(jī)調(diào)度與死鎖 4. 4. 銀行家算法之例銀行家算法之例 假定系統(tǒng)中有五個(gè)進(jìn)程假定系統(tǒng)中有五個(gè)進(jìn)程P P0 0, P, P1 1, P, P2 2, P, P3 3, P, P4 4和三類資源和三類資源A, B, CA, B, C，各種資源的數(shù)量分別為

53、，各種資源的數(shù)量分別為1010、5 5、7 7，在，在T T0 0時(shí)刻的時(shí)刻的資源分配情況如圖資源分配情況如圖 3-15 3-15 所示。所示。T T0 0時(shí)刻系統(tǒng)安全嗎？時(shí)刻系統(tǒng)安全嗎？ 圖圖 3-15 3-15 T T0 0時(shí)刻的資源分配表時(shí)刻的資源分配表 所以所以T T0 0時(shí)刻系統(tǒng)是安時(shí)刻系統(tǒng)是安全的，存在安全序列全的，存在安全序列P1,P3,P4,P0,P2P1,P3,P4,P0,P2第三章 處理機(jī)調(diào)度與死鎖 (1) T0時(shí)刻的安全性時(shí)刻的安全性 圖圖 3-16 3-16 T T0 0時(shí)刻的安全序列時(shí)刻的安全序列 第三章 處理機(jī)調(diào)度與死鎖 (2) P(2) P1 1請求資源請求資源

54、P P1 1發(fā)出請求向量發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算，系統(tǒng)按銀行家算法進(jìn)行檢查：法進(jìn)行檢查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系統(tǒng)先假定可為系統(tǒng)先假定可為P P1 1分配資源，并修改分配資源，并修改Available, Allocation1和和Need1向量，由此形成的資源變化情況如圖向量，由此形成的資源變化情況如圖 3-15 3-15 中的圓括號所示。中的圓括號所示。 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。 第三章 處

55、理機(jī)調(diào)度與死鎖 P1 P1發(fā)出請求向量發(fā)出請求向量Request1(1Request1(1，0 0，2)2)，并進(jìn)行試，并進(jìn)行試分配后分配后形成的資源變化情況如下圖中的圓括號所示：形成的資源變化情況如下圖中的圓括號所示：經(jīng)過安全性算法檢查，存在安經(jīng)過安全性算法檢查，存在安全序列全序列P1,P3,P4,P2,P0, P1,P3,P4,P2,P0, 因因此系統(tǒng)是安全的，正式分配此系統(tǒng)是安全的，正式分配第三章 處理機(jī)調(diào)度與死鎖 圖圖 3-17 P3-17 P1 1申請資源時(shí)的安全性檢查申請資源時(shí)的安全性檢查 4. 4. 銀行家算法之例銀行家算法之例 第三章 處理機(jī)調(diào)度與死鎖 (3) P(3) P4

56、4請求資源請求資源：P P4 4發(fā)出請求向量發(fā)出請求向量Request4(3，3，0)，系統(tǒng)，系統(tǒng)按銀行家算法進(jìn)行檢查：按銀行家算法進(jìn)行檢查： Request4(3, 3, 0) Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)，讓讓P P4 4等待等待。(4) P(4) P0 0請求資源請求資源：P P0 0發(fā)出請求向量發(fā)出請求向量Requst0(0，2，0)，系統(tǒng)，系統(tǒng)按銀行家算法進(jìn)行檢查：按銀行家算法進(jìn)行檢查： Request0(0, 2, 0)Needt0 (7, 4, 3); Request0(0, 2, 0)Available

57、(2, 3, 0); 系統(tǒng)暫時(shí)先假定可為系統(tǒng)暫時(shí)先假定可為P P0 0分配資源，并修改有關(guān)數(shù)據(jù)，分配資源，并修改有關(guān)數(shù)據(jù)，如圖如圖 3-18 3-18 所示。所示。 第三章 處理機(jī)調(diào)度與死鎖 圖圖 3-18 3-18 為為P P0 0分配資源后的有關(guān)資源數(shù)據(jù)分配資源后的有關(guān)資源數(shù)據(jù) (5)(5)進(jìn)行安全性檢查：進(jìn)行安全性檢查：可用資源可用資源Available(2.1.0)已不能滿足任何進(jìn)已不能滿足任何進(jìn)程的需要，故程的需要，故系統(tǒng)該進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源系統(tǒng)該進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源。4. 4. 銀行家算法之例銀行家算法之例 第三章 處理機(jī)調(diào)度與死鎖 （1 1）操作系統(tǒng)

58、要定時(shí)運(yùn)行）操作系統(tǒng)要定時(shí)運(yùn)行“死鎖檢測死鎖檢測”程序程序（2 2）解除死鎖并以最小的代價(jià)恢復(fù)操作系統(tǒng)運(yùn)行解除死鎖并以最小的代價(jià)恢復(fù)操作系統(tǒng)運(yùn)行。 思考：死鎖檢測的思考：死鎖檢測的難點(diǎn)在哪？難點(diǎn)在哪？3.8 3.8 死鎖的檢測與解除死鎖的檢測與解除 何時(shí)運(yùn)行死鎖檢測程序？何時(shí)運(yùn)行死鎖檢測程序？ 1. 1. 當(dāng)進(jìn)程等待時(shí)檢測死鎖。當(dāng)進(jìn)程等待時(shí)檢測死鎖。 ( (其缺點(diǎn)是系統(tǒng)的開銷大）其缺點(diǎn)是系統(tǒng)的開銷大） 2. 2. 定時(shí)檢測。定時(shí)檢測。 3. 3. 系統(tǒng)資源利用率下降時(shí)檢測死鎖。系統(tǒng)資源利用率下降時(shí)檢測死鎖。第三章 處理機(jī)調(diào)度與死鎖 3.8.1 死鎖的檢測死鎖的檢測 1. 資源分配圖資源分配圖(Resource Allocation Graph) 圖圖 3-19 3-19 每類資源有多個(gè)時(shí)的情況每類資源有多個(gè)時(shí)的情況 P1P2r1r2 用用有向圖有向圖描述進(jìn)程的死鎖比較準(zhǔn)確、形象。描述進(jìn)程的死鎖比較準(zhǔn)確、形象。 系統(tǒng)由若干類資源構(gòu)成，一類資源稱為一個(gè)系統(tǒng)由若干類資源構(gòu)成，一類資源稱為一個(gè)資源類資源類；每個(gè)資源類中包含若干