第7課作業(yè)調(diào)度算法

1、內(nèi)容回顧：進程和線程間的幾點不同 地址空間地址空間：不同進程的地址空間相互獨立，進程各線程共享一個地址空間。 通信關(guān)系通信關(guān)系：不同進程間使用系統(tǒng)提供的進程通信機制；同一進程各線程直接通過訪問共享的進程地址空間來實現(xiàn)。 調(diào)度切換調(diào)度切換：不同進程間切換要花很大開銷，同一進程的線程切換開銷很少。 PCB數(shù)據(jù)程序用戶棧系統(tǒng)棧寄存器單線程進程模型進程PCB數(shù)據(jù)程序用戶棧系統(tǒng)棧寄存器TCB用戶棧系統(tǒng)棧寄存器TCB用戶棧系統(tǒng)棧寄存器TCB線程1線程2線程3進程多線程進程模型(a)(b)內(nèi)容回顧：用戶與操作系統(tǒng)的程序接口操作系統(tǒng)管理了計算機的軟硬件資源，當(dāng)用戶要使用這些資源時必須通過操作系統(tǒng)來實現(xiàn)，操作系

2、統(tǒng)通過系統(tǒng)調(diào)用命令來響應(yīng)用戶的請求，這就是操作系統(tǒng)提供的程序接口程序接口。 操作系統(tǒng)預(yù)先編寫了很多不同功能的子程序，這子程序完成相應(yīng)資源的具體管理，用戶在自己的程序里通過調(diào)用這些子程序來得到系統(tǒng)提供的相應(yīng)功能服務(wù)。這些子程序就是“系統(tǒng)功系統(tǒng)功能調(diào)用程序能調(diào)用程序”，簡稱“系統(tǒng)調(diào)用系統(tǒng)調(diào)用”。特權(quán)指令與非特權(quán)指令把CPU的指令分為兩類：一類是操作系統(tǒng)和用戶都能使用的指令，稱為“非特權(quán)指令”；一類是只能由操作系統(tǒng)使用的指令，稱為“特權(quán)指令”。 管態(tài)與目態(tài)計算機可以執(zhí)行這些“特權(quán)指令”的狀態(tài)，我們稱之為“管態(tài)管態(tài)”。管態(tài)下可以執(zhí)行包括特權(quán)指令在內(nèi)任何指令。當(dāng)系統(tǒng)處于只能執(zhí)行用戶自己程序而不能執(zhí)行特權(quán)

3、指令的狀態(tài)時，我們稱之為“目態(tài)目態(tài)”。CUP處于“管態(tài)”還是“目態(tài)”由硬件系統(tǒng)自動識別。內(nèi)容回顧內(nèi)容回顧 訪管指令用戶程序在執(zhí)行的過程中，通過系統(tǒng)提供的訪管指令由“目態(tài)”轉(zhuǎn)為“管態(tài)”，從而實現(xiàn)特殊指令的執(zhí)行，而達到實現(xiàn)系統(tǒng)調(diào)用的目的。訪管指令訪管指令是一條非特權(quán)指令，功能是執(zhí)行它就會產(chǎn)生一個軟中斷，促使中央處理機由目態(tài)轉(zhuǎn)為管態(tài)，進入操作系統(tǒng) 。內(nèi)容回顧：作業(yè)內(nèi)容回顧：作業(yè)作業(yè)作業(yè)：指用戶要求計算機系統(tǒng)做的一個計算問題或一次事務(wù)處理的完整過程。從作業(yè)提交給系統(tǒng)，到作業(yè)運行完畢被撤消，是一個作業(yè)的生命期。在這期間，作業(yè)隨著自己的推進及環(huán)境變化，狀態(tài)也在不斷變化。內(nèi)容回顧：作業(yè)的生命期內(nèi)容回顧：作業(yè)

4、的生命期作業(yè)的四個基本狀態(tài)后備作業(yè)內(nèi)容回顧：作業(yè)調(diào)度內(nèi)容回顧：作業(yè)調(diào)度按某種規(guī)則從后備作業(yè)隊列里挑選作業(yè)進入內(nèi)存，參與對處理機的競爭，稱為作業(yè)調(diào)度作業(yè)調(diào)度，它由作業(yè)調(diào)度程序作業(yè)調(diào)度程序完成。所 采用的規(guī)則，稱作業(yè)調(diào)度算法作業(yè)調(diào)度算法。處理機調(diào)度處理機調(diào)度高級調(diào)度（作業(yè)調(diào)度）低級調(diào)度 （進程調(diào)度）今日內(nèi)容 選擇作業(yè)調(diào)度算法要考慮的要素選擇作業(yè)調(diào)度算法要考慮的要素 作業(yè)調(diào)度原則作業(yè)調(diào)度原則 衡量作業(yè)調(diào)度算法優(yōu)劣的指標衡量作業(yè)調(diào)度算法優(yōu)劣的指標 調(diào)度算法的詳細講解調(diào)度算法的詳細講解 先來先服務(wù)作業(yè)調(diào)度算法先來先服務(wù)作業(yè)調(diào)度算法 短作業(yè)優(yōu)先作業(yè)調(diào)度算法短作業(yè)優(yōu)先作業(yè)調(diào)度算法 響應(yīng)比高者優(yōu)先作業(yè)調(diào)度算法

5、響應(yīng)比高者優(yōu)先作業(yè)調(diào)度算法選擇作業(yè)調(diào)度算法要考慮的要素設(shè)計目標 作業(yè)調(diào)度算法要與系統(tǒng)的整體設(shè)計目標一致，如批處理系統(tǒng)應(yīng)考慮的是提高計算機效率和增加系統(tǒng)的吞吐能力；分時系統(tǒng)應(yīng)考慮的是對用戶的請求響應(yīng)時間；實時系統(tǒng)應(yīng)考慮信息的準確性以及保證及時響應(yīng)。選擇作業(yè)調(diào)度算法要考慮的要素 資源利用率 均衡的資源利用率是評價系統(tǒng)性能優(yōu)劣的重要指標。在選擇作業(yè)調(diào)度算法時，在考慮系統(tǒng)設(shè)計目標的前提下，應(yīng)最大限度地發(fā)揮各種資源的效能，注意考慮系統(tǒng)資源的均衡使用，使“I/O繁忙”的作業(yè)與“CPU繁忙”的作業(yè)搭配調(diào)度，例如將科學(xué)計算型（CPU型）作業(yè)和數(shù)據(jù)處理型（輸入輸出型）作業(yè)搭配運行就是一種方法。選擇作業(yè)調(diào)度算法要

6、考慮的要素作業(yè)的周轉(zhuǎn)時間 設(shè)法縮短作業(yè)的周轉(zhuǎn)時間以應(yīng)保證提交的作業(yè)在規(guī)定的截止時間內(nèi)完成，提高衡量調(diào)度性能的指標 大多數(shù)操作系統(tǒng)都采用折中方案，盡量選擇算法比較簡單的調(diào)度算法。作業(yè)調(diào)度原則作業(yè)調(diào)度原則 盡可能使后備作業(yè)隊列中每個作業(yè)都得到公平對待，避免一個作業(yè)無限期地延遲得不到執(zhí)行。 使進入內(nèi)存中的作業(yè)均衡地使用系統(tǒng)各種資源，避免出現(xiàn)有的資源空閑，有的資源被爭搶的局面。 盡可能提高吞吐能力，在單位時間內(nèi)為多個作業(yè)提供服務(wù)。 衡量作業(yè)調(diào)度算法優(yōu)劣的指標衡量作業(yè)調(diào)度算法優(yōu)劣的指標 CPU利用率利用率好的算法應(yīng)盡可能地提高CPU利用率。CPU利用率=CPU有效工作時間/CPU總的運行時間 吞吐量吞吐

7、量指單位時間內(nèi)平均完成的作業(yè)數(shù)量。吞吐量=完成的作業(yè)道數(shù)/完成的時間 作業(yè)周轉(zhuǎn)時間作業(yè)周轉(zhuǎn)時間作業(yè)周轉(zhuǎn)時間是指一個作業(yè)從提交到完成總共花費的時間作業(yè)周轉(zhuǎn)時間=作業(yè)完成時間-作業(yè)提交時間作業(yè)周轉(zhuǎn)時間=作業(yè)運行時間+作業(yè)等待時間 對于一批n個作業(yè)而言，它們的“平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間” T 應(yīng)該是： T=( T1 + T2 + + Tn ) / n先來先服務(wù)作業(yè)調(diào)度算法先來先服務(wù)作業(yè)調(diào)度算法以作業(yè)進入后備隊列中的先后次序作業(yè)選擇作業(yè)的依據(jù)。也就是說哪個作業(yè)在后備隊列中等待的時間最長，它就是下次調(diào)度選中者。但前提是這個作業(yè)的資源需求要得到滿足，否則就要被推遲選中例：有3個作業(yè)，所需CPU時間如下表所

8、示。按1、2、3的順序，同時提交給系統(tǒng)，采用先來先服務(wù)的作業(yè)調(diào)度算法。求每個作業(yè)的周轉(zhuǎn)時間及它們的平均周轉(zhuǎn)時間。作業(yè)作業(yè)所需所需CPU時間時間1232433例：有3個作業(yè)，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統(tǒng)，采用先來先服務(wù)的作業(yè)調(diào)度算法。求每個作業(yè)的周轉(zhuǎn)時間及它們的平均周轉(zhuǎn)時間。作業(yè)作業(yè)所需所需CPU時間時間1232433提交時間提交時間 開始時間開始時間完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間例：有3個作業(yè)，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統(tǒng)，采用先來先服務(wù)的作業(yè)調(diào)度算法。求每個作業(yè)的周轉(zhuǎn)時間及它們的平均周轉(zhuǎn)時間。作業(yè)作業(yè)所需所需CPU時間時間12

9、32433提交時間提交時間 開始時間開始時間000完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間例：有3個作業(yè)，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統(tǒng)，采用先來先服務(wù)的作業(yè)調(diào)度算法。求每個作業(yè)的周轉(zhuǎn)時間及它們的平均周轉(zhuǎn)時間。作業(yè)作業(yè)所需所需CPU時間時間1232433提交時間提交時間 開始時間開始時間0000完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間24例：有3個作業(yè)，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統(tǒng)，采用先來先服務(wù)的作業(yè)調(diào)度算法。求每個作業(yè)的周轉(zhuǎn)時間及它們的平均周轉(zhuǎn)時間。作業(yè)作業(yè)所需所需CPU時間時間1232433提交時間提交時間 開始時間開始時間00002427完

10、成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間242730例：有3個作業(yè)，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統(tǒng)，采用先來先服務(wù)的作業(yè)調(diào)度算法。求每個作業(yè)的周轉(zhuǎn)時間及它們的平均周轉(zhuǎn)時間。作業(yè)作業(yè)所需所需CPU時間時間1232433提交時間提交時間 開始時間開始時間00002427完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間242730242730例：有3個作業(yè)，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統(tǒng)，采用先來先服務(wù)的作業(yè)調(diào)度算法。求每個作業(yè)的周轉(zhuǎn)時間及它們的平均周轉(zhuǎn)時間。作業(yè)作業(yè)所需所需CPU時間時間1232433 開始時間開始時間024完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間2427

11、3024273024這三個作業(yè)的平均周轉(zhuǎn)時間為： T= (T1+T2+T3 ) / 3 = (24+27+30) / 3 = 81 / 3 = 27例：有五個作業(yè)如下表所示，采用先來先服務(wù)調(diào)度算法算出每個例：有五個作業(yè)如下表所示，采用先來先服務(wù)調(diào)度算法算出每個 作業(yè)的周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間作 業(yè)到達時間所需CPU時間18：00628：02238：03748：05358：064例：有五個作業(yè)如下表所示，采用先來先服務(wù)調(diào)度算法算出每個例：有五個作業(yè)如下表所示，采用先來先服務(wù)調(diào)度算法算出每個 作業(yè)的周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間作 業(yè)到達時間所需CPU時間開始時間完成時間周轉(zhuǎn)時間18：00628：02238

12、：03748：05358：064例：有五個作業(yè)如下表所示，采用先來先服務(wù)調(diào)度算法算出每個例：有五個作業(yè)如下表所示，采用先來先服務(wù)調(diào)度算法算出每個 作業(yè)的周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間作 業(yè)到達時間所需CPU時間開始時間完成時間周轉(zhuǎn)時間18：0068：008：0628：02238：03748：05358：064例：有五個作業(yè)如下表所示，采用先來先服務(wù)調(diào)度算法算出每個例：有五個作業(yè)如下表所示，采用先來先服務(wù)調(diào)度算法算出每個 作業(yè)的周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間作 業(yè)到達時間所需CPU時間開始時間完成時間周轉(zhuǎn)時間18：0068：008：0628：0228：068：0838：0378：088：1548：0538：15

13、8：1858：0648：188：22例：有五個作業(yè)如下表所示，采用先來先服務(wù)調(diào)度算法算出每個例：有五個作業(yè)如下表所示，采用先來先服務(wù)調(diào)度算法算出每個 作業(yè)的周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間作 業(yè)到達時間所需CPU時間開始時間完成時間周轉(zhuǎn)時間18：0068：008：06628：0228：068：08638：0378：088：151248：0538：158：181358：0648：188：2216這五個作業(yè)的平均周轉(zhuǎn)時間為：（6+6+12+13+16）/5=10.6。短作業(yè)優(yōu)先作業(yè)調(diào)度算法短作業(yè)優(yōu)先作業(yè)調(diào)度算法基本思想：要求每個用戶對自己作業(yè)所需CPU時間做出估計，填入作業(yè)說明書。作業(yè)調(diào)度程序工作時，是從后

14、備作業(yè)隊列里挑需CPU時間最少、且資源能得到滿足的作業(yè)進入內(nèi)存投入運行。 例：有3個作業(yè)，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統(tǒng)，采用短作業(yè)優(yōu)先的作業(yè)調(diào)度算法。求每個作業(yè)的周轉(zhuǎn)時間及它們的平均周轉(zhuǎn)時間。作業(yè)作業(yè)所需所需CPU時間時間1232433例：有3個作業(yè)，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統(tǒng)，采用短作業(yè)優(yōu)先的作業(yè)調(diào)度算法。求每個作業(yè)的周轉(zhuǎn)時間及它們的平均周轉(zhuǎn)時間。作業(yè)作業(yè)所需所需CPU時間時間1232433提交時間提交時間 開始時間開始時間000完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間作業(yè)作業(yè)所需所需CPU時間時間1232433完成時間完成時間周轉(zhuǎn)時

15、間周轉(zhuǎn)時間例：有3個作業(yè)，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統(tǒng)，采用短作業(yè)優(yōu)先的作業(yè)調(diào)度算法。求每個作業(yè)的周轉(zhuǎn)時間及它們的平均周轉(zhuǎn)時間。作業(yè)作業(yè)所需所需CPU時間時間1232433提交時間提交時間 開始時間開始時間0000完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間33作業(yè)作業(yè)所需所需CPU時間時間1232433完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間例：有3個作業(yè)，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統(tǒng)，采用短作業(yè)優(yōu)先的作業(yè)調(diào)度算法。求每個作業(yè)的周轉(zhuǎn)時間及它們的平均周轉(zhuǎn)時間。作業(yè)作業(yè)所需所需CPU時間時間1232433提交時間提交時間 開始時間開始時間00003完成

16、時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間3636作業(yè)作業(yè)所需所需CPU時間時間1232433完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間例：有3個作業(yè)，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統(tǒng)，采用短作業(yè)優(yōu)先的作業(yè)調(diào)度算法。求每個作業(yè)的周轉(zhuǎn)時間及它們的平均周轉(zhuǎn)時間。作業(yè)作業(yè)所需所需CPU時間時間1232433提交時間提交時間 開始時間開始時間000603完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間30363036作業(yè)作業(yè)所需所需CPU時間時間1232433完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間這三個作業(yè)的平均周轉(zhuǎn)時間為： T= (T1+T2+T3 ) / 3 = (30+3+6) / 3 = 13例：有五個作業(yè)如下

17、表所示，采用短作業(yè)優(yōu)先調(diào)度算法算出每個例：有五個作業(yè)如下表所示，采用短作業(yè)優(yōu)先調(diào)度算法算出每個 作業(yè)的周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間作 業(yè)到達時間所需CPU時間開始時間完成時間周轉(zhuǎn)時間18：00628：02238：03748：05358：064例：有五個作業(yè)如下表所示，采用短作業(yè)優(yōu)先調(diào)度算法算出每個例：有五個作業(yè)如下表所示，采用短作業(yè)優(yōu)先調(diào)度算法算出每個 作業(yè)的周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間作 業(yè)到達時間所需CPU時間開始時間完成時間周轉(zhuǎn)時間18：0068：008：0628：02238：03748：05358：064例：有五個作業(yè)如下表所示，采用短作業(yè)優(yōu)先調(diào)度算法算出每個例：有五個作業(yè)如下表所示，采用短作業(yè)優(yōu)

18、先調(diào)度算法算出每個 作業(yè)的周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間作 業(yè)到達時間所需CPU時間開始時間完成時間周轉(zhuǎn)時間18：0068：008：0628：0228：068：0838：03748：05358：064例：有五個作業(yè)如下表所示，采用短作業(yè)優(yōu)先調(diào)度算法算出每個例：有五個作業(yè)如下表所示，采用短作業(yè)優(yōu)先調(diào)度算法算出每個 作業(yè)的周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間作作 業(yè)業(yè)到達時間到達時間所需所需CPU時間時間開始時間開始時間完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間18：0068：008：0628：0228：068：0838：0378：158：2248：0538：088：1158：0648：118：15例：有五個作業(yè)如下表所示，采用

19、短作業(yè)優(yōu)先調(diào)度算法算出每個例：有五個作業(yè)如下表所示，采用短作業(yè)優(yōu)先調(diào)度算法算出每個 作業(yè)的周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間作作 業(yè)業(yè)到達時間到達時間所需所需CPU時間時間開始時間開始時間完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間18：0068：008：06628：0228：068：08638：0378：158：221948：0538：088：11658：0648：118：159這五個作業(yè)的平均周轉(zhuǎn)時間為：（6+6+19+6+9）/5=9.2。響應(yīng)比高者優(yōu)先作業(yè)調(diào)度算法響應(yīng)比高者優(yōu)先作業(yè)調(diào)度算法基本思想：在進行作業(yè)調(diào)度時，先計算每個作業(yè)當(dāng)時的響應(yīng)比： 響應(yīng)比響應(yīng)比 = ( 已等待時間已等待時間 ) / ( 所需所需

20、CPU時間時間 ) 然后從中挑選出響應(yīng)比最高的作業(yè)作為調(diào)度的對象。作業(yè)到達時間所需時間A8：005B8：023C8：031D8：042例：有四個作業(yè)如下表所示，采用響應(yīng)比高者例：有四個作業(yè)如下表所示，采用響應(yīng)比高者優(yōu)先調(diào)度算法算出作業(yè)的周轉(zhuǎn)時間優(yōu)先調(diào)度算法算出作業(yè)的周轉(zhuǎn)時間 在剛開始時，只有作業(yè)A，因此先運行作業(yè)A。 當(dāng)A于8：05運行完成時，其它三個作業(yè)B、C、D都已到達，按響應(yīng)比高者優(yōu)先算法要求，現(xiàn)在要計算這三個作業(yè)的響應(yīng)比。 此時在8:05時狀態(tài)如下表所示： 作業(yè)到達時間所需時間等待時間響應(yīng)比B8：023C8：031D8：042 此時在8:05時狀態(tài)如下表所示： 作業(yè)到達時間所需時間等待時間響應(yīng)比B8：0233C8：0312D8：0421 此時在8:05時狀態(tài)如下表所示： 作業(yè)到達時間所需時間等待時間響應(yīng)比B8：02331C8：03122D8：04210.5 可以看出，此時作業(yè)C的響應(yīng)比的響應(yīng)比最高，因此把它投入運行，作業(yè)C在8：06完成。現(xiàn)在還有兩個作業(yè)再計算它們此時的響應(yīng)比。作業(yè)在8:06時狀態(tài)作業(yè)到達時間所需時間等待時間響應(yīng)比B8：023D8：042作業(yè)在8:06時狀態(tài)作業(yè)到達時間所需時間等待時間響應(yīng)比B8：0234D8：0422作業(yè)在8:06時狀態(tài)作業(yè)到達時間所需時間等待時間響應(yīng)比B8：02341.3D8：04221 經(jīng)過重新