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

1、第三章第三章 處理機(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 實(shí)時調(diào)度實(shí)時調(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 死鎖的檢測與解除死鎖的檢測與解除 3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 3.1.1 高級、中級和低級調(diào)度高級、中級和低級調(diào)度 1. 高級調(diào)度高級調(diào)度(high scheduling) 在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定。

2、 1) 接納多少個作業(yè) 2) 接納哪些作業(yè) 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)是實(shí)現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)的要求立即執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格

3、的實(shí)時系統(tǒng)中，不宜采用這種調(diào)度方式。 2) 搶占方式搶占方式(preemptive mode) 搶占的原則有： 優(yōu)先權(quán)原則。(2) 短作業(yè)(進(jìn)程)優(yōu)先原則。 (3) 時間片原則。 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)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待，把此時的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件、且內(nèi)存又稍有空閑時，由中級調(diào)度來決定把外存上的

4、哪些又具備運(yùn)行條件的就緒進(jìn)程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。 3.1.2 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型 1. 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 圖 3 - 1 僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 就 緒隊(duì) 列阻 塞隊(duì)列進(jìn)程調(diào)度cpu進(jìn)程完成等待事件交互用戶事件出現(xiàn)時間片完2. 具有高級和低級調(diào)度的調(diào)度隊(duì)列模型具有高級和低級調(diào)度的調(diào)度隊(duì)列模型 圖 3-2 具有高、低兩級調(diào)度的調(diào)度隊(duì)列模型 就 緒隊(duì)列進(jìn)程調(diào)度cpu進(jìn)程完成等待事件1作業(yè)調(diào)度事件1出現(xiàn)時間片完等待事件2事件2出現(xiàn)等待事件n事件n出現(xiàn)后備 隊(duì)列就緒隊(duì)列的形式。 (2) 設(shè)置多個阻塞隊(duì)列。

5、圖 3-2 示出了具有高、低兩級調(diào)度的調(diào)度隊(duì)列模型。該模型與上一模型的主要區(qū)別在于如下兩個方面。 3. 同時具有三級調(diào)度的調(diào)度隊(duì)列模型同時具有三級調(diào)度的調(diào)度隊(duì)列模型 圖 3-3 具有三級調(diào)度時的調(diào)度隊(duì)列模型 就緒隊(duì)列進(jìn)程調(diào)度cpu就緒，掛起隊(duì)列中級調(diào)度阻塞，掛起隊(duì)列阻塞隊(duì)列等待事件進(jìn)程完成時間片完作業(yè)調(diào)度交互型作業(yè)后備隊(duì)列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)3.1.3 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 1. 面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 (1) 周轉(zhuǎn)時間短。周轉(zhuǎn)時間短。 可把平均周轉(zhuǎn)時間描述為： iiitnt11nisiittnw11作業(yè)的周轉(zhuǎn)時間t與系統(tǒng)為它提供服務(wù)的

6、時間ts之比，即w=t/ts，稱為帶權(quán)周轉(zhuǎn)時間，而平均帶權(quán)周轉(zhuǎn)時間則可表示為: (2) 響應(yīng)時間快。 (3) 截止時間的保證。 (4) 優(yōu)先權(quán)準(zhǔn)則。 2. 面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則 系統(tǒng)吞吐量高。(2) 處理機(jī)利用率好。 (3) 各類資源的平衡利用。 3.2 調(diào)調(diào) 度度 算算 法法 3.2.1 先來先服務(wù)和短作業(yè)先來先服務(wù)和短作業(yè)(進(jìn)程進(jìn)程)優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法 1. 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法 圖 3-4 fcfs和sjf調(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)度的算法。它們可

7、以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(sjf)的調(diào)度算法，是從后備隊(duì)列中選擇一個或若干個估計(jì)運(yùn)行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先(spf)調(diào)度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時，再重新調(diào)度。 sj(p)f調(diào)度算法也存在不容忽視的缺點(diǎn)： (1) 該算法對長作業(yè)不利，如作業(yè)c的周轉(zhuǎn)時間由10增至16，其帶權(quán)周轉(zhuǎn)時間由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)程)長期不

8、被調(diào)度。 (2) 該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會被及時處理。 (3) 由于作業(yè)(進(jìn)程)的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(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)算法 在這種方式下，系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(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)

9、中；也可用于某些對實(shí)時性要求不嚴(yán)的實(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)度算法時，是每當(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)行比較。如果pipj，原進(jìn)程pj便繼續(xù)執(zhí)行；但如果是pipj, 則立即停止pj的執(zhí)行，做進(jìn)程切換，使i進(jìn)程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法，能更好地滿足緊迫作業(yè)的要求，故而常用于

10、要求比較嚴(yán)格的實(shí)時系統(tǒng)中， 以及對性能要求較高的批處理和分時系統(tǒng)中。 2. 優(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)行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如，07或0255中的某一整數(shù)， 又把該整數(shù)稱為優(yōu)先數(shù)。只是具體用法各異：有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，當(dāng)數(shù)值愈大時，其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。 確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個方面：進(jìn)程類型。 (2) 進(jìn)程對資源的需求。 (1) (3) 用戶要求。 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)或隨其等待時間的增加而改

11、變的，以便獲得更好的調(diào)度性能。例如，我們可以規(guī)定，在就緒隊(duì)列中的進(jìn)程，隨其等待時間的增長，其優(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)程，在等待了足夠的時間后，其優(yōu)先權(quán)便可能升為最高，從而可以獲得處理機(jī)。當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時，如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機(jī)。 3. 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 要求服務(wù)時間要求服務(wù)時間等待時間優(yōu)先權(quán)優(yōu)先權(quán)的變化規(guī)律可描述為：

12、由于等待時間與服務(wù)時間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比rp。據(jù)此，又可表示為： 要求服務(wù)時間響應(yīng)時間要求服務(wù)時間要求服務(wù)時間等待時間優(yōu)先權(quán) (1) 如果作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。 (2) 當(dāng)要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)。 (3) 對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高，當(dāng)其等待時間足夠長時，其優(yōu)先級便可升到很高， 從而也可獲得處理機(jī)。 3.2.3 基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法 1. 時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法

13、在早期的時間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則，排成一個隊(duì)列，每次調(diào)度時，把cpu分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個時間片。時間片的大小從幾ms到幾百ms。當(dāng)執(zhí)行的時間片用完時，由一個計(jì)時器發(fā)出時鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時間內(nèi)，均能獲得一時間片的處理機(jī)執(zhí)行時間。2. 多級反饋隊(duì)列調(diào)度算法多級反饋隊(duì)列調(diào)度算法 (1) 應(yīng)設(shè)置多個就緒隊(duì)列，并為各個隊(duì)列賦予不同的優(yōu)先級。 第一個隊(duì)列的優(yōu)先級最高，第二個隊(duì)列次之，其余各隊(duì)

14、列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊(duì)列中進(jìn)程執(zhí)行時間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊(duì)列中，為每個進(jìn)程所規(guī)定的執(zhí)行時間片就愈小。例如，第二個隊(duì)列的時間片要比第一個隊(duì)列的時間片長一倍，第i+1個隊(duì)列的時間片要比第i個隊(duì)列的時間片長一倍。 圖 3-5 是多級反饋隊(duì)列算法的示意。 圖 3-5 多級反饋隊(duì)列調(diào)度算法 就緒隊(duì)列1就緒隊(duì)列2就緒隊(duì)列3就緒隊(duì)列ns1s2s3至cpu至cpu至cpu至cpu(時間片：s1 s2 s3) (2) 當(dāng)一個新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按fcfs原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時，如它能在該時間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個時間片結(jié)束時

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

16、高優(yōu)先權(quán)進(jìn)程。 3. 多級反饋隊(duì)列調(diào)度算法的性能多級反饋隊(duì)列調(diào)度算法的性能 終端型作業(yè)用戶。 (2) 短批處理作業(yè)用戶。 (3) 長批處理作業(yè)用戶。3.3 實(shí)實(shí) 時時 調(diào)調(diào) 度度 3.3.1 實(shí)現(xiàn)實(shí)時調(diào)度的基本條件實(shí)現(xiàn)實(shí)時調(diào)度的基本條件 1. 提供必要的信息提供必要的信息 就緒時間。(2) 開始截止時間和完成截止時間。 (3) 處理時間。 (4) 資源要求。 (5) 優(yōu)先級。 2. 系統(tǒng)處理能力強(qiáng)系統(tǒng)處理能力強(qiáng) 在實(shí)時系統(tǒng)中，通常都有著多個實(shí)時任務(wù)。若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過來而使某些實(shí)時任務(wù)不能得到及時處理， 從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個周期性的硬實(shí)時任

17、務(wù)，它們的處理時間可表示為ci，周期時間表示為pi，則在單處理機(jī)情況下，必須滿足下面的限制條件： miiipc11 系統(tǒng)才是可調(diào)度的。假如系統(tǒng)中有6個硬實(shí)時任務(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)將上述的限制條件改為： miiinpc13. 采用搶占式調(diào)度機(jī)制采用搶占式調(diào)度機(jī)制 當(dāng)一個優(yōu)先權(quán)更高的任務(wù)到達(dá)時，允許將當(dāng)前任務(wù)暫時

18、掛起，而令高優(yōu)先權(quán)任務(wù)立即投入運(yùn)行，這樣便可滿足該硬實(shí)時任務(wù)對截止時間的要求。但這種調(diào)度機(jī)制比較復(fù)雜。 對于一些小的實(shí)時系統(tǒng)，如果能預(yù)知任務(wù)的開始截止時間，則對實(shí)時任務(wù)的調(diào)度可采用非搶占調(diào)度機(jī)制，以簡化調(diào)度程序和對任務(wù)調(diào)度時所花費(fèi)的系統(tǒng)開銷。但在設(shè)計(jì)這種調(diào)度機(jī)制時，應(yīng)使所有的實(shí)時任務(wù)都比較小，并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時地將自己阻塞起來，以便釋放出處理機(jī)， 供調(diào)度程序去調(diào)度那種開始截止時間即將到達(dá)的任務(wù)。 4. 具有快速切換機(jī)制具有快速切換機(jī)制 該機(jī)制應(yīng)具有如下兩方面的能力： (1) 對外部中斷的快速響應(yīng)能力。為使在緊迫的外部事件請求中斷時系統(tǒng)能及時響應(yīng)，要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)

19、，還應(yīng)使禁止中斷的時間間隔盡量短， 以免耽誤時機(jī)(其它緊迫任務(wù))。 (2) 快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)切換時的速度， 應(yīng)使系統(tǒng)中的每個運(yùn)行功能單位適當(dāng)?shù)男。詼p少任務(wù)切換的時間開銷。 3.3.2 實(shí)時調(diào)度算法的分類實(shí)時調(diào)度算法的分類 1. 非搶占式調(diào)度算法非搶占式調(diào)度算法 非搶占式輪轉(zhuǎn)調(diào)度算法。 (2) 非搶占式優(yōu)先調(diào)度算法。 2. 搶占式調(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)程實(shí)時進(jìn)程實(shí)時進(jìn)程請求調(diào)度實(shí)時進(jìn)程槍

20、占當(dāng)前進(jìn)程，并立即執(zhí)行(d) 立即搶占的優(yōu)先權(quán)調(diào)度調(diào)度時間進(jìn)程 1進(jìn)程 2實(shí)時進(jìn)程要求調(diào)度進(jìn)程 n實(shí)時進(jìn)程調(diào)度實(shí)時進(jìn)程運(yùn)行(b) 非搶占優(yōu)先權(quán)調(diào)度當(dāng)前進(jìn)程實(shí)時進(jìn)程實(shí)時進(jìn)程請求調(diào)度當(dāng)前進(jìn)程運(yùn)行完成調(diào)度時間當(dāng)前進(jìn)程實(shí)時進(jìn)程請求調(diào)度時鐘中斷到來時調(diào)度時間(c) 基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度調(diào)度時間實(shí)時進(jìn)程圖 3-6 實(shí)時進(jìn)程調(diào)度 3.3.3 常用的幾種實(shí)時調(diào)度算法常用的幾種實(shí)時調(diào)度算法 1. 最早截止時間優(yōu)先即最早截止時間優(yōu)先即edf(earliest deadline first)算法算法 圖 3-7 edf算法用于非搶占調(diào)度方式 1342開始截止時間任務(wù)執(zhí)行任務(wù)到達(dá)12341342t2. 最

21、低松弛度優(yōu)先即最低松弛度優(yōu)先即llf(least laxity first)算法算法 該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級就愈高， 以使之優(yōu)先執(zhí)行。例如，一個任務(wù)在200ms時必須完成，而它本身所需的運(yùn)行時間就有100ms，因此，調(diào)度程序必須在100 ms之前調(diào)度執(zhí)行，該任務(wù)的緊急程度(松弛程度)為100 ms。又如，另一任務(wù)在400 ms時必須完成，它本身需要運(yùn)行 150 ms，則其松弛程度為 250 ms。在實(shí)現(xiàn)該算法時要求系統(tǒng)中有一個按松弛度排序的實(shí)時任務(wù)就緒隊(duì)列，松弛度最低的任務(wù)排在隊(duì)列最前面，調(diào)度程序總是選擇就緒隊(duì)列中的

22、隊(duì)首任務(wù)執(zhí)行。該算法主要用于可搶占調(diào)度方式中。假如在一個實(shí)時系統(tǒng)中，有兩個周期性實(shí)時任務(wù)a和b，任務(wù)a要求每 20 ms執(zhí)行一次，執(zhí)行時間為 10 ms；任務(wù)b只要求每50 ms執(zhí)行一次，執(zhí)行時間為 25 ms。 圖 3-8 a和b任務(wù)每次必須完成的時間 a1a2a3a4a5a6a7a820406080100120140160b1b2b3t0 在剛開始時(t1=0)，a1必須在20ms時完成，而它本身運(yùn)行又需 10 ms，可算出a1的松弛度為10ms；b1必須在50ms時完成， 而它本身運(yùn)行就需25 ms，可算出b1的松弛度為25 ms，故調(diào)度程序應(yīng)先調(diào)度a1執(zhí)行。在t2=10 ms時，a2的

23、松弛度可按下式算出： a2的松弛度=必須完成時間-其本身的運(yùn)行時間-當(dāng)前時間 =40 ms-10 ms-10 ms=20 ms 類似地，可算出b1的松弛度為15ms，故調(diào)度程序應(yīng)選擇b2運(yùn)行。在t3=30 ms時，a2的松弛度已減為0(即40-10-30)，而b1的松弛度為15 ms(即50-5-30)，于是調(diào)度程序應(yīng)搶占b1的處理機(jī)而調(diào)度a2運(yù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的松弛度

24、為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-10-70)，故此時調(diào)度又應(yīng)搶占b2的處理機(jī)而調(diào)度a4執(zhí)行。 圖 3-9 利用ellf算法進(jìn)行調(diào)度的情況 t1a1(10)10203040506080t0t10b1(20)t2t370a2(10)a3(10)a4(10)t4t5t6t7t8b1(5)b2(15)b2(10)3.4 多處理機(jī)系統(tǒng)中的調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度 3.4.1 多處理器

25、系統(tǒng)的類型多處理器系統(tǒng)的類型 (1) 緊密耦合(tightly coupted)mps。 這通常是通過高速總線或高速交叉開關(guān)，來實(shí)現(xiàn)多個處理器之間的互連的。它們共享主存儲器系統(tǒng)和i/o設(shè)備，并要求將主存儲器劃分為若干個能獨(dú)立訪問的存儲器模塊，以便多個處理機(jī)能同時對主存進(jìn)行訪問。系統(tǒng)中的所有資源和進(jìn)程，都由操作系統(tǒng)實(shí)施統(tǒng)一的控制和管理。 (2) 松散耦合(loosely coupled)mps。 在松散耦合mps中，通常是通過通道或通信線路，來實(shí)現(xiàn)多臺計(jì)算機(jī)之間的互連。每臺計(jì)算機(jī)都有自己的存儲器和i/o設(shè)備，并配置了os來管理本地資源和在本地運(yùn)行的進(jìn)程。因此，每一臺計(jì)算機(jī)都能獨(dú)立地工作， 必要時

26、可通過通信線路與其它計(jì)算機(jī)交換信息，以及協(xié)調(diào)它們之間的工作。 2. 對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng)對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng) (1) 對稱多處理器系統(tǒng)smps(symmetric multiprocessor system)。 在系統(tǒng)中所包含的各處理器單元，在功能和結(jié)構(gòu)上都是相同的， 當(dāng)前的絕大多數(shù)mps都屬于smp系統(tǒng)。例如，ibm公司的sr/6000 model f50, 便是利用4片power pc處理器構(gòu)成的。 (2) 非對稱多處理器系統(tǒng)。在系統(tǒng)中有多種類型的處理單元， 它們的功能和結(jié)構(gòu)各不相同，其中只有一個主處理器，有多個從處理器。 3.4.2 進(jìn)程分配方式進(jìn)程分配方

27、式 1. 對稱多處理器系統(tǒng)中的進(jìn)程分配方式對稱多處理器系統(tǒng)中的進(jìn)程分配方式 在smp系統(tǒng)中，所有的處理器都是相同的，因而可把所有的處理器作為一個處理器池(processor pool)，由調(diào)度程序或基于處理器的請求， 將任何一個進(jìn)程分配給池中的任何一個處理器去處理。在進(jìn)行進(jìn)程分配時，可采用以下兩種方式之一。 1) 靜態(tài)分配(static assigenment)方式 2) 動態(tài)分配(dynamic assgement)方式 2. 非對稱非對稱mps中的進(jìn)程分配方式中的進(jìn)程分配方式 對于非對稱mps， 其os大多采用主從(master-slave)式os， 即os的核心部分駐留在一臺主機(jī)上(ma

28、ster)， 而從機(jī)(slave)上只是用戶程序， 進(jìn)程調(diào)度只由主機(jī)執(zhí)行。 每當(dāng)從機(jī)空閑時， 便向主機(jī)發(fā)送一索求進(jìn)程的信號， 然后， 便等待主機(jī)為它分配進(jìn)程。 在主機(jī)中保持有一個就緒隊(duì)列， 只要就緒隊(duì)列不空， 主機(jī)便從其隊(duì)首摘下一進(jìn)程分配給請求的從機(jī)。從機(jī)接收到分配的進(jìn)程后便運(yùn)行該進(jìn)程， 該進(jìn)程結(jié)束后從機(jī)又向主機(jī)發(fā)出請求。 3.4.3 進(jìn)程進(jìn)程(線程線程)調(diào)度方式調(diào)度方式 1. 自調(diào)度自調(diào)度(self-scheduling)方式方式 1) 自調(diào)度機(jī)制 在多處理器系統(tǒng)中，自調(diào)度方式是最簡單的一種調(diào)度方式。它是直接由單處理機(jī)環(huán)境下的調(diào)度方式演變而來的。 在系統(tǒng)中設(shè)置有一個公共的進(jìn)程或線程就緒隊(duì)列，

29、 所有的處理器在空閑時，都可自己到該隊(duì)列中取得一進(jìn)程(或線程)來運(yùn)行。在自調(diào)度方式中，可采用在單處理機(jī)環(huán)境下所用的調(diào)度算法，如先來先服務(wù)(fcfs)調(diào)度算法、最高優(yōu)先權(quán)優(yōu)先(fpf)調(diào)度算法和搶占式最高優(yōu)先權(quán)優(yōu)先調(diào)度算法等。 2) 自調(diào)度方式的優(yōu)點(diǎn) 自調(diào)度方式的主要優(yōu)點(diǎn)表現(xiàn)為：首先，系統(tǒng)中的公共就緒隊(duì)列可按照單處理機(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ù)，或者說只要公共就緒隊(duì)列不空，就不會出現(xiàn)處理機(jī)空閑的情況，也不會發(fā)生處理器

30、忙閑不均的現(xiàn)象，因而有利于提高處理器的利用率。 3) 自調(diào)度方式的缺點(diǎn)瓶頸問題。 (2) 低效性。 (3) 線程切換頻繁。 2. 成組調(diào)度成組調(diào)度(gang scheduling)方式方式 在成組調(diào)度時，如何為應(yīng)用程序分配處理器時間， 1) 面向所有應(yīng)用程序平均分配處理器時間 2) 面向所有線程平均分配處理器時間 圖 3 - 10 兩種分配處理器時間的方法 3. 專用處理器分配專用處理器分配(dedicated processor assigement)方式方式 圖 3-11 線程數(shù)對加速比的影響 123456789 10 11 12 13 14 15 16 17 18 19 20 21 22

31、 23 241234567加速比線程數(shù)矩陣相乘fft03.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件3.5.1 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 競爭資源。競爭資源。 (2) 進(jìn)程間推進(jìn)順序非法。進(jìn)程間推進(jìn)順序非法。 1. 競爭資源引起進(jìn)程死鎖競爭資源引起進(jìn)程死鎖 可剝奪和非剝奪性資源 2) 競爭非剝奪性資源 3) 競爭臨時性資源 圖 3-12 i/o設(shè)備共享時的死鎖情況 r1r2p1p2圖 3-13 進(jìn)程之間通信時的死鎖 s2p1s3p3s1p22. 進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程推進(jìn)順序不當(dāng)引起死鎖 1) 進(jìn)程推進(jìn)順序合法 圖 3-14 進(jìn)程推進(jìn)順序?qū)λ梨i的影響 p2rel(r1)p2

32、rel(r2)p2req(r1)p2req(r2)p1req(r1)p1req(r2)p1rel(r1)p1rel(r2)d 2) 進(jìn)程推進(jìn)順序非法 若并發(fā)進(jìn)程p1和p2按曲線所示的順序推進(jìn)，它們將進(jìn)入不安全區(qū)d內(nèi)。此時p1保持了資源r1, p2保持了資源r2, 系統(tǒng)處于不安全狀態(tài)。因?yàn)椋@時兩進(jìn)程再向前推進(jìn)，便可能發(fā)生死鎖。例如，當(dāng)p1運(yùn)行到p1:request(r2)時，將因r2已被p2占用而阻塞；當(dāng)p2運(yùn)行到p2: request(r1)時，也將因r1已被p1占用而阻塞，于是發(fā)生了進(jìn)程死鎖。 3.5.2 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件 互斥條件 (2) 請求和保持條件 (3) 不剝

33、奪條件 (4) 環(huán)路等待條件 3.5.3 處理死鎖的基本方法處理死鎖的基本方法預(yù)防死鎖。 (2) 避免死鎖。 (3) 檢測死鎖。 (4) 解除死鎖。 3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法 3.6.1 預(yù)防死鎖預(yù)防死鎖 摒棄“請求和保持”條件 2. 摒棄“不剝奪”條件 3. 摒棄“環(huán)路等待”條件 3.6.2 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài) 1. 安全狀態(tài)安全狀態(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

34、)(稱p1, p2, , pn序列為安全序列)，來為每個進(jìn)程pi分配其所需資源，直至滿足每個進(jìn)程對資源的最大需求，使每個進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。 2. 安全狀態(tài)之例安全狀態(tài)之例 我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進(jìn)程p1、 p2和p3，共有12臺磁帶機(jī)。進(jìn)程p1總共要求10臺磁帶機(jī)，p2和p3分別要求4臺和9臺。假設(shè)在t0時刻，進(jìn)程p1、p2和p3已分別獲得5臺、2臺和2臺磁帶機(jī)，尚有3臺空閑未分配，如下表所示： 進(jìn) 程 最 大 需 求 已 分 配 可 用 p1p2p310495223 3. 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀

35、態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在t0時刻以后，p3又請求1臺磁帶機(jī)，若此時系統(tǒng)把剩余3臺中的1臺分配給p3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。 因?yàn)?，此時也無法再找到一個安全序列， 例如，把其余的2臺分配給p2，這樣，在p2完成后只能釋放出4臺，既不能滿足p1尚需5臺的要求，也不能滿足p3尚需6臺的要求，致使它們都無法推進(jìn)到完成，彼此都在等待對方釋放資源，即陷入僵局，結(jié)果導(dǎo)致死鎖。 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖 1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量available。這是一個

36、含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果availablej=k，則表示系統(tǒng)中現(xiàn)有rj類資源k個。 (2) 最大需求矩陣max。這是一個nm的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果maxi,j=k，則表示進(jìn)程i需要rj類資源的最大數(shù)目為k。 (3) 分配矩陣allocation。這也是一個nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果allocationi,j=k，則表示進(jìn)程i當(dāng)前已分得rj類資源的數(shù)目為k。 (4) 需求矩陣

37、need。這也是一個nm的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)。如果needi,j=k，則表示進(jìn)程i還需要rj類資源k個，方能完成其任務(wù)。 needi,j=maxi,j-allocationi,j 2. 銀行家算法銀行家算法 設(shè)requesti是進(jìn)程pi的請求向量，如果requestij=k，表示進(jìn)程pi需要k個rj類型的資源。當(dāng)pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查： (1) 如果requestijneedi,j，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。 (2) 如果requestijavailablej，便轉(zhuǎn)向步驟(3)；否則， 表示尚無足夠資源，p

38、i須等待。 (3) 系統(tǒng)試探著把資源分配給進(jìn)程pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： availablej =availablej-requestij; allocationi,j =allocationi,j+requestij; needi,j =needi,j-requestij; (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ù)目

39、，它含有m個元素，在執(zhí)行安全算法開始時，work =available; finish: 它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時先做finishi =false; 當(dāng)有足夠資源分配給進(jìn)程時， 再令finishi =true。 (2) 從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程： finishi=false; needi,jworkj； 若找到， 執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。 (3) 當(dāng)進(jìn)程pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： workj =worki+allocationi,j; finishi =true; go to ste

40、p 2; (4) 如果所有進(jìn)程的finishi=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時刻的資源分配情況如圖 3-15 所示。 圖 3-15 t0時刻的資源分配表 (1) t0時刻的安全性： 圖 3-16 t0時刻的安全序列 (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分配資源，并修改