1、第三章處理機(jī)調(diào)度與死鎖 3.1處理機(jī)調(diào)度3.1.1處理機(jī)的三級調(diào)度3.1.2調(diào)度的基本原則3.1.3調(diào)度隊列模型3.1.4常見調(diào)度算法第三章處理機(jī)調(diào)度與死鎖 第三章處理機(jī)調(diào)度與死鎖 3.1處理器的三級調(diào)度1 1、高級調(diào)度（作業(yè)調(diào)度）、高級調(diào)度（作業(yè)調(diào)度）(1) 作業(yè)作業(yè)(Job)。作業(yè)是一個比程序更為廣泛的概念，它不僅包含了通常的程序和數(shù)據(jù)程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說明書作業(yè)說明書，系統(tǒng)根據(jù)該說明書來對程序的運(yùn)行進(jìn)行控制。在批處理系統(tǒng)在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。 第三章處理機(jī)調(diào)度與死鎖 （2 2）作業(yè)控制塊）作業(yè)控制塊JCB

2、(Job Control Block)JCB(Job Control Block)是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。 在JCB中所包含的內(nèi)容因系統(tǒng)而異，通常應(yīng)包含的內(nèi)容有包含的內(nèi)容有：作業(yè)標(biāo)識、用戶名稱、用戶帳戶、作業(yè)類型作業(yè)類型(CPU 繁忙型、繁忙型、I/O 繁忙型繁忙型、批量型、終端型)、作業(yè)狀態(tài)、調(diào)度信息(優(yōu)先級、作業(yè)已運(yùn)行時間)、資源需求(預(yù)計運(yùn)行時間、要求內(nèi)存大小、要求I/O設(shè)備的類型和數(shù)量等)、進(jìn)入系統(tǒng)時間、開始處理時間、作業(yè)完成時間、作業(yè)退出時間、資源使用情況等。 第三章處理機(jī)調(diào)度與死鎖 （3 3）作業(yè)調(diào)度）作業(yè)調(diào)度 根據(jù)作業(yè)控制塊中的

3、信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求， 按照一定的算法，從外存的后備隊列中選取某些作業(yè)調(diào)入外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存內(nèi)存， 為作業(yè)創(chuàng)建進(jìn)程、分配必要的資源。 然后再將新創(chuàng)建的進(jìn)程插入就緒隊列，準(zhǔn)備執(zhí)行。 作業(yè)調(diào)度的運(yùn)行頻率較低，通常為幾分鐘一次。 作業(yè)的平均周轉(zhuǎn)時間盡可能少，有利于提高CPU 的利用率和系統(tǒng)的吞吐量作業(yè)調(diào)度，需要解決兩個問題：作業(yè)調(diào)度，需要解決兩個問題：1) 決定接納多少個作業(yè)決定接納多少個作業(yè)作業(yè)調(diào)度每次要接納多少個作業(yè)進(jìn)入內(nèi)存，取決于多道程序度。2) 2) 決定接納哪些作業(yè)決定接納哪些作業(yè)應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存，這將取決于所采用的調(diào)度算法。 先來先服務(wù)調(diào)度

4、算法； 短作業(yè)優(yōu)先調(diào)度算法； 基于作業(yè)優(yōu)先級的調(diào)度算法第三章處理機(jī)調(diào)度與死鎖 2 2、 低級調(diào)度（進(jìn)程調(diào)度）低級調(diào)度（進(jìn)程調(diào)度）它所調(diào)度的對象是進(jìn)程進(jìn)程( (或內(nèi)核級線程或內(nèi)核級線程) )。進(jìn)程調(diào)度是最基本的一種調(diào)度，在多道批處理、分時和實(shí)時三種類型的OS中，都必須配置這級調(diào)度。（1 1）低級調(diào)度的功能）低級調(diào)度的功能低級調(diào)度用于決定就緒隊列中的哪個進(jìn)程就緒隊列中的哪個進(jìn)程(或內(nèi)核級線程，為敘述方便，以后只寫進(jìn)程)應(yīng)獲得處理機(jī)應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。進(jìn)程調(diào)度的運(yùn)行頻率很高，一般隔幾十毫秒要運(yùn)行一次。第三章處理機(jī)調(diào)度與死鎖 （2 2）進(jìn)程調(diào)度方式）進(jìn)程調(diào)

5、度方式 非搶占方式非搶占方式( (NonpreemptiveNonpreemptive Mode) Mode)在采用這種調(diào)度方式時，一旦把處理機(jī)分配給某進(jìn)程后，在采用這種調(diào)度方式時，一旦把處理機(jī)分配給某進(jìn)程后，不管它要運(yùn)行多長時間，都一直讓它運(yùn)行下去，不管它要運(yùn)行多長時間，都一直讓它運(yùn)行下去，決不會因為時鐘中斷等原因而搶占正在運(yùn)行進(jìn)程的處理機(jī)，也不允許其它進(jìn)程搶占已經(jīng)分配給它的處理機(jī)。直至該進(jìn)程完成，自愿釋放處理機(jī)，或發(fā)生某事件而被阻塞時，才再把處理機(jī)分配給其他進(jìn)程。 第三章處理機(jī)調(diào)度與死鎖 在采用非搶占調(diào)度方式非搶占調(diào)度方式時，可能引起進(jìn)程調(diào)度的因素引起進(jìn)程調(diào)度的因素可歸結(jié)為如下幾個：(1)

6、 正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；(2) 執(zhí)行中的進(jìn)程因提出I/O請求而暫停執(zhí)行；(3) 在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)難以滿足緊急任務(wù)的要求立即執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格的實(shí)時系統(tǒng)中，不宜采用這種調(diào)度方式。 第三章處理機(jī)調(diào)度與死鎖 搶占方式搶占方式(Preemptive Mode)(Preemptive Mode)這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則去暫停某個正允許調(diào)度程序根據(jù)

7、某種原則去暫停某個正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。進(jìn)程。搶占方式的優(yōu)點(diǎn)是，可以防止一個長進(jìn)程長時間占用處理機(jī)，能為大多數(shù)進(jìn)程提供更公平的服務(wù)，特別是能滿足對響應(yīng)時間有著較嚴(yán)格要求的實(shí)時任務(wù)的需求。但搶占方式比非搶占方式調(diào)度所需付出的開銷較大。搶占調(diào)度方式是基于一定原則的，主要有如下幾條： 第三章處理機(jī)調(diào)度與死鎖 (1) 優(yōu)先權(quán)原則優(yōu)先權(quán)原則。通常是對一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。當(dāng)這種作業(yè)到達(dá)時，如果其優(yōu)先權(quán)比正在執(zhí)行進(jìn)程的優(yōu)先權(quán)高，便停止正在執(zhí)行(當(dāng)前)的進(jìn)程，將處理機(jī)分配給優(yōu)先權(quán)高的新到的進(jìn)程，使之執(zhí)

8、行；或者說，允許優(yōu)先權(quán)高的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)。(2) 短作業(yè)短作業(yè)(進(jìn)程進(jìn)程)優(yōu)先原則優(yōu)先原則。當(dāng)新到達(dá)的作業(yè)(進(jìn)程)比正在執(zhí)行的作業(yè)(進(jìn)程)明顯的短時，將暫停當(dāng)前長作業(yè)(進(jìn)程)的執(zhí)行，將處理機(jī)分配給新到的短作業(yè)(進(jìn)程)，使之優(yōu)先執(zhí)行； 或者說，短作業(yè)(進(jìn)程)可以搶占當(dāng)前較長作業(yè)(進(jìn)程)的處理機(jī)。(3) 時間片原則時間片原則。各進(jìn)程按時間片輪流運(yùn)行，當(dāng)一個時間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這種原則適用于分時系統(tǒng)、大多數(shù)的實(shí)時系統(tǒng)，以及要求較高的批處理系統(tǒng)。 3 3、 中級調(diào)度中級調(diào)度中級調(diào)度又稱中程調(diào)度。 目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量目的是為了提高內(nèi)存利用率和系

9、統(tǒng)吞吐量。 將處于外存對換區(qū)中的具備運(yùn)行條件的進(jìn)程調(diào)入內(nèi)存，或?qū)⑻幱趦?nèi)存中的暫時不能運(yùn)行的進(jìn)程交換到外存對換區(qū)。 在存儲器管理中詳細(xì)介紹外存內(nèi)存掛起第三章處理機(jī)調(diào)度與死鎖 掛起和激活第三章處理機(jī)調(diào)度與死鎖 在上述三種調(diào)度中， 進(jìn)程調(diào)度進(jìn)程調(diào)度的運(yùn)行頻率最高，在分時系統(tǒng)中通常是10100 ms便進(jìn)行一次進(jìn)程調(diào)度，因此把它稱為短程調(diào)度短程調(diào)度。為避免進(jìn)程調(diào)度占用太多的CPU時間，進(jìn)程調(diào)度算法不宜太復(fù)雜。 作業(yè)調(diào)度作業(yè)調(diào)度往往是發(fā)生在一個(批)作業(yè)運(yùn)行完畢，退出系統(tǒng)，而需要重新調(diào)入一個(批)作業(yè)進(jìn)入內(nèi)存時，故作業(yè)調(diào)度的周期較長，大約幾分鐘一次，因此把它稱為長程調(diào)度長程調(diào)度。由于其運(yùn)行頻率較低，故允許

10、作業(yè)調(diào)度算法花費(fèi)較多的時間。 中級調(diào)度中級調(diào)度的運(yùn)行頻率基本上介于上述兩種調(diào)度之間，因此把它稱為中程調(diào)度。 第三章處理機(jī)調(diào)度與死鎖 作業(yè)調(diào)度與進(jìn)程調(diào)度區(qū)別：作業(yè)調(diào)度與進(jìn)程調(diào)度區(qū)別：（1）作業(yè)調(diào)度的結(jié)果：是為作業(yè)創(chuàng)建進(jìn)程進(jìn)程調(diào)度的結(jié)果：是進(jìn)程被執(zhí)行（2）作業(yè)調(diào)度次數(shù)少，進(jìn)程調(diào)度頻度高（3）作業(yè)調(diào)度一般只在批處理系統(tǒng)，但所有系統(tǒng)進(jìn)程調(diào)度必須有。第三章處理機(jī)調(diào)度與死鎖 3.1.2 調(diào)度的基本原則調(diào)度的基本原則 為了衡量調(diào)度算法的性能，人們提出了一些評價標(biāo)準(zhǔn)：1、CPU利用率2、系統(tǒng)吞吐量3、響應(yīng)時間4、周轉(zhuǎn)時間（1）周轉(zhuǎn)時間、平均周轉(zhuǎn)時間（2）帶權(quán)周轉(zhuǎn)時間、平均帶權(quán)周轉(zhuǎn)時間第三章處理機(jī)調(diào)度與死鎖 吞

11、吐量吞吐量吞吐量指單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。評價批處理系統(tǒng)性能的重要指標(biāo) 。與作業(yè)的平均長度有關(guān)。對于大型作業(yè)，一般吞吐量約為每小時一道作業(yè)，對于中、小型作業(yè)，其吞吐量則可達(dá)到數(shù)十道作業(yè)。第三章處理機(jī)調(diào)度與死鎖 響應(yīng)時間響應(yīng)時間 響應(yīng)時間是從用戶通過鍵盤提交一個請求開始直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時間間隔。它包括三部分時間：從鍵盤輸入的請求信息傳送到處理機(jī)的時間；處理機(jī)對請求信息進(jìn)行處理的時間；將響應(yīng)信息回送到終端顯示器的時間。l 是分時系統(tǒng)中的重要原則。第三章處理機(jī)調(diào)度與死鎖 周轉(zhuǎn)時間周轉(zhuǎn)時間 從從作業(yè)被提交給系統(tǒng)作業(yè)被提交給系統(tǒng)開始，到開始，到作業(yè)完成作業(yè)完成為止的這段時間為止的這段時間

12、間隔稱為間隔稱為作業(yè)周轉(zhuǎn)時間作業(yè)周轉(zhuǎn)時間。包括四部分時間：。包括四部分時間：l 在外存后備隊列上等待調(diào)度的時間在外存后備隊列上等待調(diào)度的時間l 進(jìn)程在就緒隊列上等待調(diào)度的時間進(jìn)程在就緒隊列上等待調(diào)度的時間l 進(jìn)程在進(jìn)程在CPU上執(zhí)行的時間上執(zhí)行的時間l 進(jìn)程等待進(jìn)程等待I/O操作完成的時間操作完成的時間 周轉(zhuǎn)時間定義實(shí)際服務(wù)時間實(shí)際服務(wù)時間等待時間實(shí)際服務(wù)時間周轉(zhuǎn)時間siiTTWinisiinTTW11周轉(zhuǎn)時間Ti平均周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 平均帶權(quán)周轉(zhuǎn)時間 niinTT11Ti：作業(yè)的周轉(zhuǎn)時間；：作業(yè)的周轉(zhuǎn)時間；Tsi：系統(tǒng)為提供為它提系統(tǒng)為提供為它提 供服務(wù)的時間（真正供服務(wù)的時間（真正 運(yùn)

13、行時間）。運(yùn)行時間）。第三章處理機(jī)調(diào)度與死鎖 例例:有如下三道作業(yè)。系統(tǒng)為它們服務(wù)的順序有如下三道作業(yè)。系統(tǒng)為它們服務(wù)的順序 是：是：1、2、3。求平均周轉(zhuǎn)時間和平均。求平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。帶權(quán)周轉(zhuǎn)時間。第三章處理機(jī)調(diào)度與死鎖 解：解：第三章處理機(jī)調(diào)度與死鎖 第三章處理機(jī)調(diào)度與死鎖 平均周轉(zhuǎn)時間：平均周轉(zhuǎn)時間：T=(2+2.9+3)/3=2.63hT=(2+2.9+3)/3=2.63h平均帶權(quán)周轉(zhuǎn)時間：平均帶權(quán)周轉(zhuǎn)時間：W=(2+2.9+12)/3=5.3hW=(2+2.9+12)/3=5.3h。第三章處理機(jī)調(diào)度與死鎖 截止時間截止時間 是指某任務(wù)必須開始執(zhí)行的最遲時間，或必須完成

14、的最遲時間。 對于嚴(yán)格的實(shí)時系統(tǒng)，其調(diào)度方式和調(diào)度算法必須能保證這一點(diǎn) 。選擇調(diào)度方式和調(diào)度算法的準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的準(zhǔn)則 面向用戶的準(zhǔn)則 面向系統(tǒng)的準(zhǔn)則周轉(zhuǎn)時間短響應(yīng)時間快 截止時間的保證 優(yōu)先權(quán)準(zhǔn)則 系統(tǒng)吞吐量高處理機(jī)利用率好 資源的平衡利用 第三章處理機(jī)調(diào)度與死鎖 (1)(1)僅有進(jìn)程調(diào)度的調(diào)度隊列模型僅有進(jìn)程調(diào)度的調(diào)度隊列模型 (2)(2)有高級和低級調(diào)度的調(diào)度隊列模型有高級和低級調(diào)度的調(diào)度隊列模型(3)(3)同時有三級調(diào)度的調(diào)度隊列模型同時有三級調(diào)度的調(diào)度隊列模型3.1.3 調(diào)度隊列模型調(diào)度隊列模型第三章處理機(jī)調(diào)度與死鎖 通常，把就緒進(jìn)程組織成FIFO隊列，每當(dāng)創(chuàng)建新進(jìn)程時排

15、在就緒隊列的末尾，按時間片輪轉(zhuǎn)方式運(yùn)行。進(jìn)程在執(zhí)行時，出現(xiàn)三種情況：1 任務(wù)在時間片內(nèi)完成，進(jìn)程便在釋放處理機(jī)后進(jìn)入完成狀態(tài)；2 任務(wù)在時間片內(nèi)未完成，OS便將該任務(wù)再放入就緒隊列的末尾；3 在執(zhí)行期間，進(jìn)程因為某事件而被阻塞后，被OS放入阻塞隊列。(1)(1)僅有進(jìn)程調(diào)度的調(diào)度隊列模型僅有進(jìn)程調(diào)度的調(diào)度隊列模型第三章處理機(jī)調(diào)度與死鎖 就緒隊列就緒隊列阻塞隊列阻塞隊列cpu進(jìn)程調(diào)度進(jìn)程調(diào)度等待事件等待事件時間片完時間片完進(jìn)程完成進(jìn)程完成用戶用戶事件出現(xiàn)事件出現(xiàn)23第三章處理機(jī)調(diào)度與死鎖 (2)(2)有高級和低級調(diào)度的調(diào)度隊列模型有高級和低級調(diào)度的調(diào)度隊列模型 與前一模型的差別：（1）就緒隊列的

16、形式。批處理系統(tǒng)中最常用的是優(yōu)先權(quán)隊列。也可采用無序鏈表方式。（2）設(shè)置多個阻塞隊列。就緒隊列就緒隊列阻塞隊列阻塞隊列cpu進(jìn)程調(diào)度進(jìn)程調(diào)度等待事件等待事件時間片完時間片完進(jìn)程完成進(jìn)程完成作業(yè)作業(yè)調(diào)度調(diào)度后備隊列后備隊列第三章處理機(jī)調(diào)度與死鎖 （3）有三級調(diào)度的調(diào)度隊列模型）有三級調(diào)度的調(diào)度隊列模型 調(diào)出時，可使進(jìn)程狀態(tài)由內(nèi)存就緒轉(zhuǎn)變?yōu)橥獯婢途w，由內(nèi)存阻塞轉(zhuǎn)變?yōu)橥獯孀枞?在中級調(diào)度使外存就緒轉(zhuǎn)變?yōu)閮?nèi)存就緒。3.1.4調(diào)度算法調(diào)度算法v調(diào)度算法是指：根據(jù)系統(tǒng)的調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略資源分配策略所規(guī)定的所規(guī)定的資資源分配算法源分配算法 。v不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算

17、法不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法 。第二章進(jìn) 程 管 理 補(bǔ)：進(jìn)程的三種基本狀態(tài)轉(zhuǎn)換補(bǔ)：進(jìn)程的三種基本狀態(tài)轉(zhuǎn)換 就緒就緒阻塞阻塞執(zhí)行執(zhí)行I/O請求I/O完成時間片完進(jìn)程調(diào)度第二章進(jìn) 程 管 理 掛起操作和進(jìn)程狀態(tài)的轉(zhuǎn)換掛起操作和進(jìn)程狀態(tài)的轉(zhuǎn)換1.掛起操作的引入掛起操作的引入（1）終端用戶請求）終端用戶請求（2）父進(jìn)程請求）父進(jìn)程請求（3）負(fù)荷調(diào)節(jié)需要）負(fù)荷調(diào)節(jié)需要（4）操作系統(tǒng)的需要）操作系統(tǒng)的需要第二章進(jìn) 程 管 理 掛起引起的狀態(tài)轉(zhuǎn)換掛起引起的狀態(tài)轉(zhuǎn)換靜止?fàn)顟B(tài)靜止?fàn)顟B(tài)活動狀態(tài)活動狀態(tài)掛起狀態(tài)掛起狀態(tài)非掛起狀態(tài)非掛起狀態(tài)第二章進(jìn) 程 管 理 有掛起狀態(tài)的進(jìn)程狀態(tài)圖有掛起狀態(tài)的進(jìn)

18、程狀態(tài)圖靜止靜止就緒就緒活動活動阻塞阻塞執(zhí)行執(zhí)行I/O請求活動活動就緒就緒靜止靜止阻塞阻塞掛起掛起激活掛起激活調(diào)度釋放釋放1、先來先服務(wù)調(diào)度、先來先服務(wù)調(diào)度算法（算法（FCFS）（）（作業(yè)調(diào)度、進(jìn)程調(diào)度作業(yè)調(diào)度、進(jìn)程調(diào)度） 2、短作業(yè)（進(jìn)程）優(yōu)先法（、短作業(yè)（進(jìn)程）優(yōu)先法（作業(yè)調(diào)度、進(jìn)程調(diào)度作業(yè)調(diào)度、進(jìn)程調(diào)度） 3 3、高優(yōu)先權(quán)優(yōu)先調(diào)度、高優(yōu)先權(quán)優(yōu)先調(diào)度算法（算法（作業(yè)調(diào)度作業(yè)調(diào)度、進(jìn)程調(diào)度、進(jìn)程調(diào)度） 優(yōu)先權(quán)調(diào)度算法的類型 非搶占式優(yōu)先權(quán)算法 搶占式優(yōu)先權(quán)算法高高響應(yīng)比優(yōu)先調(diào)度算法（響應(yīng)比優(yōu)先調(diào)度算法（作業(yè)調(diào)度作業(yè)調(diào)度） 4 4、時間片輪轉(zhuǎn)法（、時間片輪轉(zhuǎn)法（進(jìn)程調(diào)度進(jìn)程調(diào)度）5 5、多級反

19、饋隊列調(diào)度多級反饋隊列調(diào)度算法（算法（進(jìn)程調(diào)度進(jìn)程調(diào)度）1 1、先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法（FCFSFCFS）可用于作業(yè)調(diào)度和進(jìn)程調(diào)度中。可用于作業(yè)調(diào)度和進(jìn)程調(diào)度中。l 作業(yè)調(diào)度中每次從后備作業(yè)隊列中，選擇作業(yè)調(diào)度中每次從后備作業(yè)隊列中，選擇一個或多一個或多個最先進(jìn)入該隊列的個最先進(jìn)入該隊列的作業(yè)調(diào)入內(nèi)存，為它們分配資作業(yè)調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊列。源、創(chuàng)建進(jìn)程，然后放入就緒隊列。l 進(jìn)程調(diào)度時每次從就緒隊列中，選擇一個最先進(jìn)入進(jìn)程調(diào)度時每次從就緒隊列中，選擇一個最先進(jìn)入該隊列的進(jìn)程分配處理機(jī)使之運(yùn)行。直到完成或阻該隊列的進(jìn)程分配處理機(jī)使之運(yùn)行。直到完成或阻

20、塞后，才放棄處理機(jī)。塞后，才放棄處理機(jī)。1、先來先服務(wù)調(diào)度算法、先來先服務(wù)調(diào)度算法l 是一種最簡單的調(diào)度算法既可用于作業(yè)調(diào)度也可用是一種最簡單的調(diào)度算法既可用于作業(yè)調(diào)度也可用于進(jìn)程調(diào)度。于進(jìn)程調(diào)度。l FCFS( first come first serve)FCFS( first come first serve)算法算法l 有利長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。有利長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。 l 有利有利CPUCPU繁忙型作業(yè)，而不利于繁忙型作業(yè)，而不利于I/OI/O繁忙型作業(yè)。繁忙型作業(yè)。開始開始+運(yùn)行運(yùn)行決定服務(wù)順序決定服務(wù)順序1 11011011021022022

21、02開始開始+運(yùn)行運(yùn)行完成完成-到達(dá)到達(dá)周轉(zhuǎn)周轉(zhuǎn)/ /運(yùn)行運(yùn)行100/1100/1100/1100/12、短、短作業(yè)（進(jìn)程）作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法 短作業(yè)優(yōu)先（SJF）法：從后備隊列中選擇一個或若干個估計運(yùn)行時間最短估計運(yùn)行時間最短的作業(yè)調(diào)入內(nèi)存運(yùn)行。短進(jìn)程優(yōu)先（SPF）調(diào)度算法：從就緒隊列中選出一估計運(yùn)行時間最短的進(jìn)程，分配處理機(jī)使它立即執(zhí)行直到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時，再重新調(diào)度。可用于作業(yè)調(diào)度和進(jìn)程調(diào)度中可用于作業(yè)調(diào)度和進(jìn)程調(diào)度中 進(jìn)程名進(jìn)程名 到達(dá)時間到達(dá)時間 服務(wù)時間服務(wù)時間FCFS 完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間SJF完成時間完

22、成時間周轉(zhuǎn)時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E 到達(dá)時間到達(dá)時間0 1 2 3 4 服務(wù)時間服務(wù)時間4 3 5 2 4FCFS 完成時間完成時間4 7 12 14 18周轉(zhuǎn)時間周轉(zhuǎn)時間4 6 10 11 14帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間1 2 2 5.5 3.5SJF完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E 到達(dá)時間到達(dá)時間0 1 2 3 4 服務(wù)時間服務(wù)時間4 3 5 2 4FCFS 完成時間完成時間4 7 12 14 18周轉(zhuǎn)時間周轉(zhuǎn)時間4 6 10 11 14帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間

23、間1 2 2 5.5 3.5SJF完成時間完成時間4周轉(zhuǎn)時間周轉(zhuǎn)時間4帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E 到達(dá)時間到達(dá)時間0 1 2 3 4 服務(wù)時間服務(wù)時間4 3 5 2 4FCFS 完成時間完成時間4 7 12 14 18周轉(zhuǎn)時間周轉(zhuǎn)時間4 6 10 11 14帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間1 2 2 5.5 3.5SJF完成時間完成時間4 6周轉(zhuǎn)時間周轉(zhuǎn)時間4 3帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E 到達(dá)時間到達(dá)時間0 1 2 3 4 服務(wù)時間服務(wù)時間4 3 5 2 4FCFS 完成時間完成時間4 7 12 14 18周

24、轉(zhuǎn)時間周轉(zhuǎn)時間4 6 10 11 14帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間1 2 2 5.5 3.5SJF完成時間完成時間4 9 6周轉(zhuǎn)時間周轉(zhuǎn)時間4 8 3帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E 到達(dá)時間到達(dá)時間0 1 2 3 4 服務(wù)時間服務(wù)時間4 3 5 2 4FCFS 完成時間完成時間4 7 12 14 18周轉(zhuǎn)時間周轉(zhuǎn)時間4 6 10 11 14帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間1 2 2 5.5 3.5SJF完成時間完成時間4 9 6 13周轉(zhuǎn)時間周轉(zhuǎn)時間4 8 3 9帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E 到達(dá)時間到達(dá)時間0 1 2

25、3 4 服務(wù)時間服務(wù)時間4 3 5 2 4FCFS 完成時間完成時間4 7 12 14 18周轉(zhuǎn)時間周轉(zhuǎn)時間4 6 10 11 14帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間1 2 2 5.5 3.5SJF完成時間完成時間4 9 18 6 13周轉(zhuǎn)時間周轉(zhuǎn)時間4 8 16 3 9帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E平均 到達(dá)時間到達(dá)時間0 1 2 3 4 服務(wù)時間服務(wù)時間4 3 5 2 4FCFS 完成時間完成時間4 7 12 14 18周轉(zhuǎn)時間周轉(zhuǎn)時間4 6 10 11 14帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間1 2 2 5.5 3.5SJF完成時間完成時間4 9 18 6 13周轉(zhuǎn)時

26、間周轉(zhuǎn)時間4 8 16 3 9帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間1 2.673.1 1.5 2.25作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E 到達(dá)時間到達(dá)時間0 1 2 3 4 服務(wù)時間服務(wù)時間4 3 5 2 4FCFS 完成時間完成時間4 7 12 14 18周轉(zhuǎn)時間周轉(zhuǎn)時間4 6 10 11 14帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間1 2 2 5.5 3.5SJF完成時間完成時間4 9 18 6 13周轉(zhuǎn)時間周轉(zhuǎn)時間4 8 16 3 9帶權(quán)周轉(zhuǎn)時帶權(quán)周轉(zhuǎn)時間間1 2.673.1 1.5 2.25作業(yè)作業(yè)算法算法SJ （P）F法缺點(diǎn)法缺點(diǎn)（1 1）對長作業(yè)不利對長作業(yè)不利。如果有一長作業(yè)進(jìn)入系統(tǒng)的后。如果

27、有一長作業(yè)進(jìn)入系統(tǒng)的后備隊列，由于總是優(yōu)先調(diào)度那些短作業(yè)（進(jìn)程），備隊列，由于總是優(yōu)先調(diào)度那些短作業(yè)（進(jìn)程），將導(dǎo)致長作業(yè)長期不被調(diào)度。將導(dǎo)致長作業(yè)長期不被調(diào)度。（2 2）完全）完全未考慮未考慮作業(yè)的作業(yè)的緊迫程度緊迫程度，不能保證緊迫性，不能保證緊迫性作業(yè)（進(jìn)程）會被及時處理。作業(yè)（進(jìn)程）會被及時處理。（3 3）作業(yè)（進(jìn)程）的長短根據(jù)）作業(yè)（進(jìn)程）的長短根據(jù)用戶所提供的估計用戶所提供的估計執(zhí)執(zhí)行時間而定的，不一定能真正做到短作業(yè)優(yōu)先調(diào)行時間而定的，不一定能真正做到短作業(yè)優(yōu)先調(diào)度。度。3 3、 高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法（1）優(yōu)先權(quán)調(diào)度算法類型（2 2）優(yōu)先權(quán)的類型）優(yōu)先權(quán)的類型

28、（3 3）高響應(yīng)比優(yōu)先調(diào)度算法）高響應(yīng)比優(yōu)先調(diào)度算法可用于作業(yè)調(diào)度和進(jìn)程調(diào)度中可用于作業(yè)調(diào)度和進(jìn)程調(diào)度中（1 1）優(yōu)先權(quán)）優(yōu)先權(quán)調(diào)度算法類型調(diào)度算法類型 非搶占式非搶占式優(yōu)先權(quán)算法優(yōu)先權(quán)算法 把處理機(jī)分配給就緒隊列中把處理機(jī)分配給就緒隊列中優(yōu)先權(quán)最高優(yōu)先權(quán)最高的進(jìn)程后便一直執(zhí)的進(jìn)程后便一直執(zhí)行下去直至完成；或發(fā)生某事件使該進(jìn)程放棄處理機(jī)時，行下去直至完成；或發(fā)生某事件使該進(jìn)程放棄處理機(jī)時，可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程?？稍賹⑻幚頇C(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。 用于用于批處理系統(tǒng)批處理系統(tǒng)和某些和某些對實(shí)時性要求不嚴(yán)對實(shí)時性要求不嚴(yán)的實(shí)時系統(tǒng)中。的實(shí)時系統(tǒng)中。 搶占式搶占式優(yōu)先

29、權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法 把處理機(jī)分配給把處理機(jī)分配給優(yōu)先權(quán)最高優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。在執(zhí)行期的進(jìn)程，使之執(zhí)行。在執(zhí)行期間，只要又出現(xiàn)優(yōu)先權(quán)間，只要又出現(xiàn)優(yōu)先權(quán)更高更高的進(jìn)程，就的進(jìn)程，就重新重新將處理機(jī)分配將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。給新到的優(yōu)先權(quán)最高的進(jìn)程。 能更好地滿足緊迫作業(yè)的要求，常用于能更好地滿足緊迫作業(yè)的要求，常用于要求比較嚴(yán)格的要求比較嚴(yán)格的實(shí)實(shí)時系統(tǒng)時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。中，以及對性能要求較高的批處理和分時系統(tǒng)中。書p94 靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán) 動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)書p94 靜態(tài)優(yōu)先權(quán)：靜態(tài)優(yōu)先權(quán)： 在創(chuàng)建進(jìn)程時確定在創(chuàng)建進(jìn)程時確定

30、 在進(jìn)程的整個運(yùn)行期間保持不變。在進(jìn)程的整個運(yùn)行期間保持不變。 一般地，用某一范圍內(nèi)的一個整數(shù)來表示的，例如，一般地，用某一范圍內(nèi)的一個整數(shù)來表示的，例如，0707或或02550255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。確定優(yōu)先權(quán)依據(jù)：確定優(yōu)先權(quán)依據(jù)：（1 1）進(jìn)程類型：系統(tǒng)進(jìn)程）進(jìn)程類型：系統(tǒng)進(jìn)程高于高于用戶進(jìn)程用戶進(jìn)程（2 2）進(jìn)程對資源的要求：要求少的進(jìn)程應(yīng)賦予較）進(jìn)程對資源的要求：要求少的進(jìn)程應(yīng)賦予較高高優(yōu)先權(quán)。優(yōu)先權(quán)。（3 3）用戶要求。這是由用戶進(jìn)程的）用戶要求。這是由用戶進(jìn)程的緊迫程度緊迫程度及所付費(fèi)多少來確定。及所付費(fèi)多少來確定。靜態(tài)優(yōu)先權(quán)法

31、優(yōu)缺點(diǎn)：靜態(tài)優(yōu)先權(quán)法優(yōu)缺點(diǎn)：l簡單，系統(tǒng)開銷小l不精確，僅在要求不高的系統(tǒng)中使用（2 2）優(yōu)先權(quán)的類型）優(yōu)先權(quán)的類型 動態(tài)動態(tài)優(yōu)先權(quán)優(yōu)先權(quán)優(yōu)先權(quán)隨優(yōu)先權(quán)隨進(jìn)程推進(jìn)進(jìn)程推進(jìn)或隨其或隨其等待時間等待時間的增加而改變的，的增加而改變的，以便獲得更好的調(diào)度性能。以便獲得更好的調(diào)度性能。 (3)(3)高高響應(yīng)比優(yōu)先調(diào)度響應(yīng)比優(yōu)先調(diào)度算法（作業(yè)調(diào)度）算法（作業(yè)調(diào)度） 引入動態(tài)優(yōu)先權(quán)，并使作業(yè)優(yōu)先級隨著等待時間的增引入動態(tài)優(yōu)先權(quán)，并使作業(yè)優(yōu)先級隨著等待時間的增加而以速率加而以速率a a提高。提高。該優(yōu)先權(quán)的變化規(guī)律為：該優(yōu)先權(quán)的變化規(guī)律為：優(yōu)先權(quán)優(yōu)先權(quán) = =（等待時間（等待時間+ +要求服務(wù)時間）要求服務(wù)

32、時間） / /要求服務(wù)時間要求服務(wù)時間優(yōu)先權(quán)優(yōu)先權(quán) = = R RP P = =響應(yīng)時間響應(yīng)時間/ /要求服務(wù)時間要求服務(wù)時間R RP P ：響應(yīng)比：響應(yīng)比分析作業(yè)等待時間相同，則有利于作業(yè)等待時間相同，則有利于短作業(yè)短作業(yè)。要求服務(wù)時間相同，實(shí)現(xiàn)的是要求服務(wù)時間相同，實(shí)現(xiàn)的是先來先服務(wù)先來先服務(wù)。長作業(yè)也可獲得處理機(jī)。長作業(yè)也可獲得處理機(jī)。優(yōu)點(diǎn)：兼顧長短作業(yè)。優(yōu)點(diǎn)：兼顧長短作業(yè)。缺點(diǎn)：由于做響應(yīng)比計算，故增加了系缺點(diǎn)：由于做響應(yīng)比計算，故增加了系 統(tǒng)開銷統(tǒng)開銷優(yōu)先權(quán)優(yōu)先權(quán) =(=(等待時間等待時間/ /要求服務(wù)時間要求服務(wù)時間)+1)+1 4 4、基于、基于時間片的輪轉(zhuǎn)調(diào)度算法時間片的輪轉(zhuǎn)調(diào)度算法分時系統(tǒng)中，多采用時間片輪轉(zhuǎn)法分時系統(tǒng)中，多采用時間片輪轉(zhuǎn)法 把就緒進(jìn)程組織成把就緒進(jìn)程組織成FIFOFIFO隊列；隊列； 把