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

操作系統(tǒng)第7課作業(yè)調(diào)度算法內(nèi)容回顧：進(jìn)程和線程間的幾點(diǎn)不同地址空間：不同進(jìn)程的地址空間相互獨(dú)立，進(jìn)程各線程共享一個(gè)地址空間。通信關(guān)系：不同進(jìn)程間使用系統(tǒng)提供的進(jìn)程通信機(jī)制；同一進(jìn)程各線程直接通過(guò)訪問(wèn)共享的進(jìn)程地址空間來(lái)實(shí)現(xiàn)。調(diào)度切換：不同進(jìn)程間切換要花很大開(kāi)銷(xiāo)，同一進(jìn)程的線程切換開(kāi)銷(xiāo)很少。PCB數(shù)據(jù)程序用戶(hù)棧系統(tǒng)棧寄存器單線程進(jìn)程模型進(jìn)程PCB數(shù)據(jù)程序用戶(hù)棧系統(tǒng)棧寄存器TCB用戶(hù)棧系統(tǒng)棧寄存器TCB用戶(hù)棧系統(tǒng)棧寄存器TCB線程1線程2線程3進(jìn)程多線程進(jìn)程模型(a)(b)內(nèi)容回顧：用戶(hù)與操作系統(tǒng)的程序接口操作系統(tǒng)管理了計(jì)算機(jī)的軟硬件資源，當(dāng)用戶(hù)要使用這些資源時(shí)必須通過(guò)操作系統(tǒng)來(lái)實(shí)現(xiàn)，操作系統(tǒng)通過(guò)系統(tǒng)調(diào)用命令來(lái)響應(yīng)用戶(hù)的請(qǐng)求，這就是操作系統(tǒng)提供的程序接口。操作系統(tǒng)預(yù)先編寫(xiě)了很多不同功能的子程序，這子程序完成相應(yīng)資源的具體管理，用戶(hù)在自己的程序里通過(guò)調(diào)用這些子程序來(lái)得到系統(tǒng)提供的相應(yīng)功能服務(wù)。這些子程序就是“系統(tǒng)功能調(diào)用程序”，簡(jiǎn)稱(chēng)“系統(tǒng)調(diào)用”。特權(quán)指令與非特權(quán)指令把CPU的指令分為兩類(lèi)：一類(lèi)是操作系統(tǒng)和用戶(hù)都能使用的指令，稱(chēng)為“非特權(quán)指令”；一類(lèi)是只能由操作系統(tǒng)使用的指令，稱(chēng)為“特權(quán)指令”。管態(tài)與目態(tài)計(jì)算機(jī)可以執(zhí)行這些“特權(quán)指令”的狀態(tài)，我們稱(chēng)之為“管態(tài)”。管態(tài)下可以執(zhí)行包括特權(quán)指令在內(nèi)任何指令。當(dāng)系統(tǒng)處于只能執(zhí)行用戶(hù)自己程序而不能執(zhí)行特權(quán)指令的狀態(tài)時(shí)，我們稱(chēng)之為“目態(tài)”。CUP處于“管態(tài)”還是“目態(tài)”由硬件系統(tǒng)自動(dòng)識(shí)別。內(nèi)容回顧內(nèi)容回顧訪管指令用戶(hù)程序在執(zhí)行的過(guò)程中，通過(guò)系統(tǒng)提供的訪管指令由“目態(tài)”轉(zhuǎn)為“管態(tài)”，從而實(shí)現(xiàn)特殊指令的執(zhí)行，而達(dá)到實(shí)現(xiàn)系統(tǒng)調(diào)用的目的。訪管指令是一條非特權(quán)指令，功能是執(zhí)行它就會(huì)產(chǎn)生一個(gè)軟中斷，促使中央處理機(jī)由目態(tài)轉(zhuǎn)為管態(tài)，進(jìn)入操作系統(tǒng)。內(nèi)容回顧：作業(yè)作業(yè)：指用戶(hù)要求計(jì)算機(jī)系統(tǒng)做的一個(gè)計(jì)算問(wèn)題或一次事務(wù)處理的完整過(guò)程。從作業(yè)提交給系統(tǒng)，到作業(yè)運(yùn)行完畢被撤消，是一個(gè)作業(yè)的生命期。在這期間，作業(yè)隨著自己的推進(jìn)及環(huán)境變化，狀態(tài)也在不斷變化。內(nèi)容回顧：作業(yè)的生命期作業(yè)的四個(gè)基本狀態(tài)后備作業(yè)內(nèi)容回顧：作業(yè)調(diào)度按某種規(guī)則從后備作業(yè)隊(duì)列里挑選作業(yè)進(jìn)入內(nèi)存，參與對(duì)處理機(jī)的競(jìng)爭(zhēng)，稱(chēng)為作業(yè)調(diào)度，它由作業(yè)調(diào)度程序完成。所采用的規(guī)則，稱(chēng)作業(yè)調(diào)度算法。處理機(jī)調(diào)度高級(jí)調(diào)度（作業(yè)調(diào)度）低級(jí)調(diào)度（進(jìn)程調(diào)度）今日內(nèi)容選擇作業(yè)調(diào)度算法要考慮的要素作業(yè)調(diào)度原則衡量作業(yè)調(diào)度算法優(yōu)劣的指標(biāo)調(diào)度算法的詳細(xì)講解先來(lái)先服務(wù)作業(yè)調(diào)度算法短作業(yè)優(yōu)先作業(yè)調(diào)度算法響應(yīng)比高者優(yōu)先作業(yè)調(diào)度算法選擇作業(yè)調(diào)度算法要考慮的要素設(shè)計(jì)目標(biāo)作業(yè)調(diào)度算法要與系統(tǒng)的整體設(shè)計(jì)目標(biāo)一致，如批處理系統(tǒng)應(yīng)考慮的是提高計(jì)算機(jī)效率和增加系統(tǒng)的吞吐能力；分時(shí)系統(tǒng)應(yīng)考慮的是對(duì)用戶(hù)的請(qǐng)求響應(yīng)時(shí)間；實(shí)時(shí)系統(tǒng)應(yīng)考慮信息的準(zhǔn)確性以及保證及時(shí)響應(yīng)。選擇作業(yè)調(diào)度算法要考慮的要素

資源利用率均衡的資源利用率是評(píng)價(jià)系統(tǒng)性能優(yōu)劣的重要指標(biāo)。在選擇作業(yè)調(diào)度算法時(shí)，在考慮系統(tǒng)設(shè)計(jì)目標(biāo)的前提下，應(yīng)最大限度地發(fā)揮各種資源的效能，注意考慮系統(tǒng)資源的均衡使用，使“I/O繁忙”的作業(yè)與“CPU繁忙”的作業(yè)搭配調(diào)度，例如將科學(xué)計(jì)算型（CPU型）作業(yè)和數(shù)據(jù)處理型（輸入輸出型）作業(yè)搭配運(yùn)行就是一種方法。選擇作業(yè)調(diào)度算法要考慮的要素作業(yè)的周轉(zhuǎn)時(shí)間設(shè)法縮短作業(yè)的周轉(zhuǎn)時(shí)間以應(yīng)保證提交的作業(yè)在規(guī)定的截止時(shí)間內(nèi)完成，提高衡量調(diào)度性能的指標(biāo)大多數(shù)操作系統(tǒng)都采用折中方案，盡量選擇算法比較簡(jiǎn)單的調(diào)度算法。作業(yè)調(diào)度原則盡可能使后備作業(yè)隊(duì)列中每個(gè)作業(yè)都得到公平對(duì)待，避免一個(gè)作業(yè)無(wú)限期地延遲得不到執(zhí)行。使進(jìn)入內(nèi)存中的作業(yè)均衡地使用系統(tǒng)各種資源，避免出現(xiàn)有的資源空閑，有的資源被爭(zhēng)搶的局面。盡可能提高吞吐能力，在單位時(shí)間內(nèi)為多個(gè)作業(yè)提供服務(wù)。

衡量作業(yè)調(diào)度算法優(yōu)劣的指標(biāo)CPU利用率好的算法應(yīng)盡可能地提高CPU利用率。CPU利用率=CPU有效工作時(shí)間/CPU總的運(yùn)行時(shí)間吞吐量指單位時(shí)間內(nèi)平均完成的作業(yè)數(shù)量。吞吐量=完成的作業(yè)道數(shù)/完成的時(shí)間作業(yè)周轉(zhuǎn)時(shí)間作業(yè)周轉(zhuǎn)時(shí)間是指一個(gè)作業(yè)從提交到完成總共花費(fèi)的時(shí)間作業(yè)周轉(zhuǎn)時(shí)間=作業(yè)完成時(shí)間-作業(yè)提交時(shí)間作業(yè)周轉(zhuǎn)時(shí)間=作業(yè)運(yùn)行時(shí)間+作業(yè)等待時(shí)間對(duì)于一批n個(gè)作業(yè)而言，它們的“平均周轉(zhuǎn)時(shí)間”T應(yīng)該是：

T=(T1+T2+…+Tn)/n先來(lái)先服務(wù)作業(yè)調(diào)度算法以作業(yè)進(jìn)入后備隊(duì)列中的先后次序作業(yè)選擇作業(yè)的依據(jù)。也就是說(shuō)哪個(gè)作業(yè)在后備隊(duì)列中等待的時(shí)間最長(zhǎng)，它就是下次調(diào)度選中者。但前提是這個(gè)作業(yè)的資源需求要得到滿(mǎn)足，否則就要被推遲選中例：有3個(gè)作業(yè)，所需CPU時(shí)間如下表所示。按1、2、3的順序，同時(shí)提交給系統(tǒng)，采用先來(lái)先服務(wù)的作業(yè)調(diào)度算法。求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間及它們的平均周轉(zhuǎn)時(shí)間。作業(yè)所需CPU時(shí)間1232433例：有3個(gè)作業(yè)，所需CPU時(shí)間如下表所示。按1、2、3的順序，同時(shí)提交給系統(tǒng)，采用先來(lái)先服務(wù)的作業(yè)調(diào)度算法。求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間及它們的平均周轉(zhuǎn)時(shí)間。作業(yè)所需CPU時(shí)間1232433提交時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間例：有3個(gè)作業(yè)，所需CPU時(shí)間如下表所示。按1、2、3的順序，同時(shí)提交給系統(tǒng)，采用先來(lái)先服務(wù)的作業(yè)調(diào)度算法。求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間及它們的平均周轉(zhuǎn)時(shí)間。作業(yè)所需CPU時(shí)間1232433提交時(shí)間開(kāi)始時(shí)間000完成時(shí)間周轉(zhuǎn)時(shí)間例：有3個(gè)作業(yè)，所需CPU時(shí)間如下表所示。按1、2、3的順序，同時(shí)提交給系統(tǒng)，采用先來(lái)先服務(wù)的作業(yè)調(diào)度算法。求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間及它們的平均周轉(zhuǎn)時(shí)間。作業(yè)所需CPU時(shí)間1232433提交時(shí)間開(kāi)始時(shí)間0000完成時(shí)間周轉(zhuǎn)時(shí)間24例：有3個(gè)作業(yè)，所需CPU時(shí)間如下表所示。按1、2、3的順序，同時(shí)提交給系統(tǒng)，采用先來(lái)先服務(wù)的作業(yè)調(diào)度算法。求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間及它們的平均周轉(zhuǎn)時(shí)間。作業(yè)所需CPU時(shí)間1232433提交時(shí)間開(kāi)始時(shí)間00002427完成時(shí)間周轉(zhuǎn)時(shí)間242730例：有3個(gè)作業(yè)，所需CPU時(shí)間如下表所示。按1、2、3的順序，同時(shí)提交給系統(tǒng)，采用先來(lái)先服務(wù)的作業(yè)調(diào)度算法。求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間及它們的平均周轉(zhuǎn)時(shí)間。作業(yè)所需CPU時(shí)間1232433提交時(shí)間開(kāi)始時(shí)間00002427完成時(shí)間周轉(zhuǎn)時(shí)間242730242730例：有3個(gè)作業(yè)，所需CPU時(shí)間如下表所示。按1、2、3的順序，同時(shí)提交給系統(tǒng)，采用先來(lái)先服務(wù)的作業(yè)調(diào)度算法。求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間及它們的平均周轉(zhuǎn)時(shí)間。作業(yè)所需CPU時(shí)間1232433開(kāi)始時(shí)間024完成時(shí)間周轉(zhuǎn)時(shí)間24273024273024這三個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間為：

T=(T1+T2+T3)/3=(24+27+30)/3=81/3=27例：有五個(gè)作業(yè)如下表所示，采用先來(lái)先服務(wù)調(diào)度算法算出每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)到達(dá)時(shí)間所需CPU時(shí)間18：00628：02238：03748：05358：064例：有五個(gè)作業(yè)如下表所示，采用先來(lái)先服務(wù)調(diào)度算法算出每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)到達(dá)時(shí)間所需CPU時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間18：00628：02238：03748：05358：064例：有五個(gè)作業(yè)如下表所示，采用先來(lái)先服務(wù)調(diào)度算法算出每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)到達(dá)時(shí)間所需CPU時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間18：0068：008：0628：02238：03748：05358：064例：有五個(gè)作業(yè)如下表所示，采用先來(lái)先服務(wù)調(diào)度算法算出每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)到達(dá)時(shí)間所需CPU時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間18：0068：008：0628：0228：068：0838：0378：088：1548：0538：158：1858：0648：188：22例：有五個(gè)作業(yè)如下表所示，采用先來(lái)先服務(wù)調(diào)度算法算出每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)到達(dá)時(shí)間所需CPU時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間18：0068：008：06628：0228：068：08638：0378：088：151248：0538：158：181358：0648：188：2216這五個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間為：（6+6+12+13+16）/5=10.6。短作業(yè)優(yōu)先作業(yè)調(diào)度算法基本思想：要求每個(gè)用戶(hù)對(duì)自己作業(yè)所需CPU時(shí)間做出估計(jì)，填入作業(yè)說(shuō)明書(shū)。作業(yè)調(diào)度程序工作時(shí)，是從后備作業(yè)隊(duì)列里挑需CPU時(shí)間最少、且資源能得到滿(mǎn)足的作業(yè)進(jìn)入內(nèi)存投入運(yùn)行。例：有3個(gè)作業(yè)，所需CPU時(shí)間如下表所示。按1、2、3的順序，同時(shí)提交給系統(tǒng)，采用短作業(yè)優(yōu)先的作業(yè)調(diào)度算法。求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間及它們的平均周轉(zhuǎn)時(shí)間。作業(yè)所需CPU時(shí)間1232433例：有3個(gè)作業(yè)，所需CPU時(shí)間如下表所示。按1、2、3的順序，同時(shí)提交給系統(tǒng)，采用短作業(yè)優(yōu)先的作業(yè)調(diào)度算法。求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間及它們的平均周轉(zhuǎn)時(shí)間。作業(yè)所需CPU時(shí)間1232433提交時(shí)間開(kāi)始時(shí)間000完成時(shí)間周轉(zhuǎn)時(shí)間作業(yè)所需CPU時(shí)間1232433完成時(shí)間周轉(zhuǎn)時(shí)間例：有3個(gè)作業(yè)，所需CPU時(shí)間如下表所示。按1、2、3的順序，同時(shí)提交給系統(tǒng)，采用短作業(yè)優(yōu)先的作業(yè)調(diào)度算法。求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間及它們的平均周轉(zhuǎn)時(shí)間。作業(yè)所需CPU時(shí)間1232433提交時(shí)間開(kāi)始時(shí)間0000完成時(shí)間周轉(zhuǎn)時(shí)間33作業(yè)所需CPU時(shí)間1232433完成時(shí)間周轉(zhuǎn)時(shí)間例：有3個(gè)作業(yè)，所需CPU時(shí)間如下表所示。按1、2、3的順序，同時(shí)提交給系統(tǒng)，采用短作業(yè)優(yōu)先的作業(yè)調(diào)度算法。求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間及它們的平均周轉(zhuǎn)時(shí)間。作業(yè)所需CPU時(shí)間1232433提交時(shí)間開(kāi)始時(shí)間00003完成時(shí)間周轉(zhuǎn)時(shí)間3636作業(yè)所需CPU時(shí)間1232433完成時(shí)間周轉(zhuǎn)時(shí)間例：有3個(gè)作業(yè)，所需CPU時(shí)間如下表所示。按1、2、3的順序，同時(shí)提交給系統(tǒng)，采用短作業(yè)優(yōu)先的作業(yè)調(diào)度算法。求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間及它們的平均周轉(zhuǎn)時(shí)間。作業(yè)所需CPU時(shí)間1232433提交時(shí)間開(kāi)始時(shí)間000603完成時(shí)間周轉(zhuǎn)時(shí)間30363036作業(yè)所需CPU時(shí)間1232433完成時(shí)間周轉(zhuǎn)時(shí)間這三個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間為：

T=(T1+T2+T3)/3=(30+3+6)/3=13例：有五個(gè)作業(yè)如下表所示，采用短作業(yè)優(yōu)先調(diào)度算法算出每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)到達(dá)時(shí)間所需CPU時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間18：00628：02238：03748：05358：064例：有五個(gè)作業(yè)如下表所示，采用短作業(yè)優(yōu)先調(diào)度算法算出每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)到達(dá)時(shí)間所需CPU時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間18：0068：008：0628：02238：03748：05358：064例：有五個(gè)作業(yè)如下表所示，采用短作業(yè)優(yōu)先調(diào)度算法算出每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)到達(dá)時(shí)間所需CPU時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間18：0068：008：0628：0228：068：0838：03748：05358：064例：有五個(gè)作業(yè)如下表所示，采用短作業(yè)優(yōu)先調(diào)度算法算出每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)到達(dá)時(shí)間所需CPU時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間18：0068：008：0628：0228：068：0838：0378：158：2248：0538：088：1158：0648：118：15例：有五個(gè)作業(yè)如下表所示，采用短作業(yè)優(yōu)先調(diào)度算法算出每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)到達(dá)時(shí)間所需CPU時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間18：0068：008：06628：0228：068：08638：0378：158：221948：0538：088：11658：0648：118：159這五個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間為：（6+6+19+6+9）/5=9.2。響應(yīng)比高者優(yōu)先作業(yè)調(diào)度算法基本思想：在進(jìn)行作業(yè)調(diào)度時(shí)，先計(jì)算每個(gè)作業(yè)當(dāng)時(shí)的響應(yīng)比：響應(yīng)比=(已等待時(shí)間)/(所需CPU時(shí)間)

然后從中挑選出響應(yīng)比最高的作業(yè)作為調(diào)度的對(duì)象。作業(yè)到達(dá)時(shí)間所需時(shí)間A8：005B8：023C8：031D8：042例：有四個(gè)作業(yè)如下表所示，采用響應(yīng)比高者優(yōu)先調(diào)度算法算出作業(yè)的周轉(zhuǎn)時(shí)間在剛開(kāi)始時(shí)，只有作業(yè)A，因此先運(yùn)行作業(yè)A。當(dāng)A于8：05運(yùn)行完成時(shí)，其它三個(gè)作業(yè)B、C、D都已到達(dá)，按響應(yīng)比高者優(yōu)先算法要求，現(xiàn)在要計(jì)算這三個(gè)作業(yè)的響應(yīng)比。此時(shí)在8:05時(shí)狀態(tài)如下表所示：作業(yè)到達(dá)時(shí)間所需時(shí)間等待時(shí)間響應(yīng)比B8：023C8：031D8：042此時(shí)在8:05時(shí)狀態(tài)如下表所示：作業(yè)到達(dá)時(shí)間所需時(shí)間等待時(shí)間響應(yīng)比B8：0233C8：0312D8：0421此時(shí)在8:05時(shí)狀態(tài)如下表所示：作業(yè)到達(dá)時(shí)間所需時(shí)間等待時(shí)間響應(yīng)比B8：02331C8：03122D