操作系統(tǒng)原理(處理機(jī)調(diào)度)

操作系統(tǒng)原理張德海

E-mail:dhzhang@2009年4月7日云南大學(xué)軟件學(xué)院2003年9月28日1第四章處理機(jī)調(diào)度4.1分級(jí)調(diào)度4.2作業(yè)調(diào)度4.3進(jìn)程調(diào)度4.4調(diào)度算法4.5算法評(píng)價(jià)4.6實(shí)時(shí)系統(tǒng)調(diào)度方法2003年9月28日2第四章處理機(jī)調(diào)度處理機(jī)調(diào)度問(wèn)題實(shí)際上就是處理機(jī)的分配與管理。處理機(jī)管理的工作是對(duì)CPU資源進(jìn)行合理的分配使用，以提高處理機(jī)利用率，并使各用戶(hù)公平地得到處理機(jī)資源。這里的主要問(wèn)題是處理機(jī)調(diào)度算法和調(diào)度算法特征分析。2003年9月28日3并發(fā)所帶來(lái)的效率提升多道程序設(shè)計(jì)2003年9月28日4并發(fā)所帶來(lái)的效率提升順序執(zhí)行模式下的系統(tǒng)工作效率系統(tǒng)總運(yùn)行時(shí)間：80CPU使用效率：CPU占用時(shí)間/總時(shí)間＝40/80=50%DEV1使用效率：15/80＝18.75%DEV2使用效率：25/80=31.25%并發(fā)執(zhí)行模式下的系統(tǒng)工作效率系統(tǒng)總運(yùn)行時(shí)間：45CPU使用效率：40/45=89%DEV1使用效率：15/45=33%DEV2使用效率：25/45＝55.6%多道程序設(shè)計(jì)2003年9月28日5衡量調(diào)度策略的常用指標(biāo)我們可從不同的角度來(lái)判斷處理機(jī)調(diào)度算法的性能，如用戶(hù)的角度、處理機(jī)的角度和算法實(shí)現(xiàn)的角度。實(shí)際的處理機(jī)調(diào)度算法選擇是一個(gè)綜合的判斷結(jié)果。2003年9月28日61.面向用戶(hù)的性能指標(biāo)周轉(zhuǎn)時(shí)間：從作業(yè)提交給系統(tǒng)到返回結(jié)果所需時(shí)間；平均周轉(zhuǎn)時(shí)間T平均帶權(quán)周轉(zhuǎn)時(shí)間（帶權(quán)周轉(zhuǎn)時(shí)間W是T(周轉(zhuǎn))/T(CPU執(zhí)行)〕響應(yīng)時(shí)間：用戶(hù)輸入一個(gè)請(qǐng)求（如擊鍵）到系統(tǒng)給出首次響應(yīng)（如屏幕顯示）的時(shí)間－－分時(shí)系統(tǒng)截止時(shí)間：開(kāi)始截止時(shí)間和完成截止時(shí)間－－實(shí)時(shí)系統(tǒng)，與周轉(zhuǎn)時(shí)間有些相似。公平性：不因作業(yè)或進(jìn)程本身的特性而使上述指標(biāo)過(guò)分惡化。如長(zhǎng)作業(yè)等待很長(zhǎng)時(shí)間。優(yōu)先級(jí)：可以使關(guān)鍵任務(wù)達(dá)到更好的指標(biāo)。2003年9月28日72.面向系統(tǒng)的性能指標(biāo)吞吐率：在給定時(shí)間內(nèi)，一個(gè)計(jì)算機(jī)系統(tǒng)所完成的總工作量；響應(yīng)時(shí)間：用戶(hù)向計(jì)算機(jī)發(fā)出一個(gè)命令到計(jì)算機(jī)將結(jié)果返回給用戶(hù)所需的時(shí)間；設(shè)備利用率：指I/O設(shè)備的使用情況。2003年9月28日83.面向算法的性能指標(biāo)實(shí)現(xiàn)難度：實(shí)現(xiàn)該算法是否容易執(zhí)行開(kāi)銷(xiāo)比：該算法是否消耗太多系統(tǒng)資源2003年9月28日94.1分級(jí)調(diào)度(Scheduling)作業(yè)調(diào)度-高級(jí)調(diào)度交換調(diào)度-中級(jí)調(diào)度進(jìn)程調(diào)度-低級(jí)調(diào)度線程調(diào)度2003年9月28日104.1分級(jí)調(diào)度-作業(yè)調(diào)度高級(jí)(Long-term)調(diào)度――作業(yè)調(diào)度作業(yè)調(diào)度用于決定把外存輸入井上處于作業(yè)后備隊(duì)列上的那些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。在批處理系統(tǒng)中，作業(yè)是先駐留在外存的輸入井上的，因此需要有作業(yè)調(diào)度。然而在分時(shí)系統(tǒng)中，通過(guò)鍵盤(pán)輸入的命令和數(shù)據(jù)直接進(jìn)入內(nèi)存，無(wú)需作業(yè)調(diào)度。2003年9月28日11中級(jí)(Medium-term)調(diào)度——交換調(diào)度引入中級(jí)調(diào)度的目的是為了提高主存利用率和系統(tǒng)吞吐量。由于在進(jìn)程并發(fā)執(zhí)行過(guò)程中，為了充分發(fā)揮內(nèi)存的效能，需將那些暫時(shí)不能運(yùn)行的進(jìn)程從內(nèi)存調(diào)到外存盤(pán)交換區(qū)去等待，而將那些在盤(pán)交換區(qū)的等待事件已經(jīng)發(fā)生急需調(diào)度運(yùn)行的進(jìn)程從盤(pán)交換區(qū)調(diào)入內(nèi)存。在UNIX系統(tǒng)中中級(jí)調(diào)度就是存儲(chǔ)管理中的交換，采用虛擬存儲(chǔ)技術(shù)的分時(shí)系統(tǒng)往往設(shè)立中級(jí)調(diào)度。4.1分級(jí)調(diào)度-交換調(diào)度2003年9月28日124.1分級(jí)調(diào)度-進(jìn)程調(diào)度低級(jí)(Short-term)調(diào)度――進(jìn)程調(diào)度進(jìn)程調(diào)度決定就緒隊(duì)列中哪個(gè)進(jìn)程將獲得處理機(jī)，然后由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的操作。在確定了占用處理機(jī)的進(jìn)程之后，系統(tǒng)必須進(jìn)行進(jìn)程上下文切換以建立與占用處理機(jī)進(jìn)程相適應(yīng)的執(zhí)行環(huán)境。進(jìn)程調(diào)度是最基本的調(diào)度，任何操作系統(tǒng)都有進(jìn)程調(diào)度。2003年9月28日13線程調(diào)度在多線程系統(tǒng)中，按照一定的策略和方法選取一個(gè)處于就緒隊(duì)列中的線程占有處理機(jī)。4.1分級(jí)調(diào)度-線程調(diào)度2003年9月28日14圖：處理機(jī)四級(jí)調(diào)度

作業(yè)運(yùn)行狀態(tài)

外存

外存(盤(pán))交換區(qū)作業(yè)收容狀態(tài)作業(yè)提交狀態(tài)作業(yè)完成狀態(tài)終止作業(yè)就緒態(tài)阻塞態(tài)內(nèi)存

進(jìn)程調(diào)度執(zhí)行態(tài)就緒態(tài)阻塞態(tài)線程調(diào)度交換調(diào)度作業(yè)調(diào)度2003年9月28日154.1.3作業(yè)與進(jìn)程的關(guān)系作業(yè)可被看作是用戶(hù)向計(jì)算機(jī)提交任務(wù)的實(shí)體。如一次計(jì)算，一個(gè)控制過(guò)程等。進(jìn)程則是計(jì)算機(jī)為了完成用戶(hù)任務(wù)實(shí)體而設(shè)置的執(zhí)行實(shí)體，是系統(tǒng)分配資源的基本單位。一個(gè)作業(yè)可以由一個(gè)或多個(gè)進(jìn)程組成。而一個(gè)進(jìn)程不可能對(duì)應(yīng)多個(gè)作業(yè)。2003年9月28日164.2作業(yè)調(diào)度作業(yè)的組成作業(yè)由程序、數(shù)據(jù)、作業(yè)說(shuō)明書(shū)三部分組成程序是問(wèn)題求解的算法描述數(shù)據(jù)是程序加工的對(duì)象，但有些程序未必使用數(shù)據(jù)；作業(yè)說(shuō)明書(shū)是告訴操作系統(tǒng)本作業(yè)的程序和數(shù)據(jù)按什么樣的控制要求使之執(zhí)行。作業(yè)步一個(gè)作業(yè)的一次活動(dòng)中若干相對(duì)獨(dú)立的加工步驟編譯原程序連接裝配程序運(yùn)行程序2003年9月28日174.2作業(yè)調(diào)度2003年9月28日184.2作業(yè)調(diào)度作業(yè)的狀態(tài)作業(yè)從進(jìn)入到運(yùn)行結(jié)束，一般需要經(jīng)歷“提交”、“后備”、“運(yùn)行”和“完成”四個(gè)階段。2003年9月28日19作業(yè)的狀態(tài)1提交狀態(tài)作業(yè)從輸入設(shè)備進(jìn)入外存儲(chǔ)器時(shí)的狀態(tài)2后備狀態(tài)作業(yè)的全部信息調(diào)入外存后,系統(tǒng)將其加入后備作業(yè)隊(duì)列時(shí)的狀態(tài)系統(tǒng)將為每個(gè)作業(yè)建立一個(gè)作業(yè)控制表(JCT)3運(yùn)行狀態(tài)作業(yè)被調(diào)度程序選中,并分配到它所需要的資源時(shí)調(diào)入內(nèi)存運(yùn)行時(shí)的狀態(tài)4完成狀態(tài)作業(yè)正常運(yùn)行結(jié)束或因發(fā)生錯(cuò)誤而終止時(shí),釋放占有的所有資源,準(zhǔn)備離開(kāi)系統(tǒng)時(shí)的狀態(tài)2003年9月28日20作業(yè)的狀態(tài)轉(zhuǎn)換執(zhí)行等待就緒運(yùn)行后備提交完成進(jìn)程調(diào)度程序作業(yè)注冊(cè)程序作業(yè)調(diào)度程序作業(yè)終止程序2003年9月28日21作業(yè)控制塊JCB作業(yè)名作業(yè)類(lèi)型資源要求資源使用情況

優(yōu)先級(jí)當(dāng)前狀態(tài)其它2003年9月28日224.2.1作業(yè)調(diào)度及其功能作業(yè)調(diào)度是按照某種調(diào)度算法從后備作業(yè)隊(duì)列中選擇作業(yè)裝入內(nèi)存運(yùn)行，并當(dāng)作業(yè)運(yùn)行結(jié)束后做后續(xù)處理。選擇作業(yè)分配資源：分配內(nèi)存和外設(shè)資源建立作業(yè)的進(jìn)程建立其它相關(guān)表格作業(yè)后續(xù)處理(收回資源/撤消PCB和JCB)作業(yè)調(diào)度又稱(chēng)為宏觀調(diào)度在實(shí)時(shí)系統(tǒng)和分時(shí)系統(tǒng)中通常不配置作業(yè)調(diào)度2003年9月28日234.2.2作業(yè)調(diào)度目標(biāo)與性能衡量作業(yè)調(diào)度目標(biāo)：對(duì)所有作業(yè)應(yīng)該是公平合理的應(yīng)使設(shè)備有高的利用率每天執(zhí)行盡可能多的作業(yè)有快的響應(yīng)時(shí)間作業(yè)調(diào)度性能衡量平均周轉(zhuǎn)時(shí)間帶權(quán)平均周轉(zhuǎn)時(shí)間2003年9月28日24周轉(zhuǎn)時(shí)間：從作業(yè)提交到作業(yè)完成的時(shí)間間隔。

Ti=tci–tsi平均周轉(zhuǎn)時(shí)間:n個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間T為:帶權(quán)周轉(zhuǎn)時(shí)間：為周轉(zhuǎn)時(shí)間T和運(yùn)行時(shí)間R之比。W=T/R平均帶權(quán)周轉(zhuǎn)時(shí)間：平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間2003年9月28日25平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間圖示三個(gè)作業(yè)的執(zhí)行順序：算出各作業(yè)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間：作業(yè)到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間10240242412132427268.673232730289.33平均周轉(zhuǎn)時(shí)間T=26,平均帶權(quán)周轉(zhuǎn)時(shí)間

W=6.332003年9月28日264.3進(jìn)程調(diào)度進(jìn)程調(diào)度的功能：記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況

進(jìn)程管理模塊在各進(jìn)程的PCB表中記錄系統(tǒng)各進(jìn)程的執(zhí)行情況和狀態(tài)特征，并將各PCB表根據(jù)進(jìn)程狀態(tài)特征和資源要求排成相應(yīng)的隊(duì)列，并進(jìn)行動(dòng)態(tài)隊(duì)列轉(zhuǎn)換。選擇占有處理機(jī)進(jìn)程

進(jìn)程調(diào)度的主要功能是按照一定的策略（由它決定的調(diào)度算法），選擇一個(gè)處于就緒態(tài)的進(jìn)程，使其獲得處理機(jī)執(zhí)行。進(jìn)行進(jìn)程上下文切換

進(jìn)程上下文實(shí)際上是進(jìn)程執(zhí)行活動(dòng)全過(guò)程的靜態(tài)描述，一個(gè)進(jìn)程的執(zhí)行是在進(jìn)程上下文中執(zhí)行。當(dāng)正在執(zhí)行的進(jìn)程由于某種原因要讓出處理機(jī)時(shí)，系統(tǒng)要做上下文切換，以使另一個(gè)進(jìn)程得以執(zhí)行。2003年9月28日274.3.2進(jìn)程調(diào)度的時(shí)機(jī)引起進(jìn)程調(diào)度的原因有：1.正在執(zhí)行的進(jìn)程執(zhí)行完畢；2.執(zhí)行中的進(jìn)程調(diào)用阻塞原語(yǔ)將自己阻塞起來(lái)進(jìn)入睡眠狀態(tài)；3.執(zhí)行中的進(jìn)程調(diào)用了P原語(yǔ)操作，從而因資源不足而被阻塞；或調(diào)用了V原語(yǔ)激活了等待資源的進(jìn)程隊(duì)列；4.執(zhí)行中的進(jìn)程提出I/O請(qǐng)求后被阻塞；5.執(zhí)行中的進(jìn)程在分時(shí)系統(tǒng)中的時(shí)間片已用完；6.系統(tǒng)程序返回用戶(hù)進(jìn)程時(shí)，可認(rèn)為系統(tǒng)進(jìn)程執(zhí)行完畢，從而可調(diào)度選擇一個(gè)新的用戶(hù)進(jìn)程執(zhí)行；7.在剝奪方式下，就緒隊(duì)列中的進(jìn)程優(yōu)先級(jí)高于執(zhí)行中的進(jìn)程，執(zhí)行進(jìn)程被剝奪處理機(jī)資源。2003年9月28日28進(jìn)程調(diào)度的方式非剝奪（非搶占Nonpreemptivemode）方式：采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給某進(jìn)程后，便讓進(jìn)程一直執(zhí)行，直到該進(jìn)程完成或發(fā)生某事件而被阻塞時(shí)，才把處理機(jī)分配給其它進(jìn)程，決不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)。這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單、系統(tǒng)開(kāi)銷(xiāo)小，適用于大多數(shù)批處理系統(tǒng)環(huán)境。缺點(diǎn)是難以滿(mǎn)足緊急任務(wù)的要求，不適用于實(shí)時(shí)、分時(shí)系統(tǒng)要求。2003年9月28日29進(jìn)程調(diào)度的方式剝奪（搶占）方式（Preemptivemode）這種調(diào)度方式，允許進(jìn)程調(diào)度程序根據(jù)某個(gè)原則，去停止某個(gè)正在執(zhí)行的進(jìn)程，將已分配給進(jìn)程的處理機(jī)，重新分配給另一個(gè)進(jìn)程。搶占的原則有：時(shí)間片原則。各進(jìn)程按時(shí)間片運(yùn)行，當(dāng)一個(gè)時(shí)間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這個(gè)原則適用于分時(shí)系統(tǒng)。優(yōu)先權(quán)原則。通常是對(duì)一些重要的和緊急的進(jìn)程賦予較高的優(yōu)先權(quán)。當(dāng)這種進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，例如由阻塞態(tài)轉(zhuǎn)換為就緒態(tài)，或從靜止就緒態(tài)轉(zhuǎn)為活動(dòng)就緒態(tài)時(shí)，或新創(chuàng)建進(jìn)入就緒態(tài)的進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，如果其優(yōu)先權(quán)比正在執(zhí)行的進(jìn)程優(yōu)先權(quán)高，便停止正在執(zhí)行的進(jìn)程，將處理機(jī)分配給優(yōu)先權(quán)高的進(jìn)程，使之執(zhí)行。2003年9月28日304.3.3進(jìn)程上下文切換進(jìn)程上下文由正文段、數(shù)據(jù)段、硬件寄存器的內(nèi)容和有關(guān)數(shù)據(jù)結(jié)構(gòu)等組成。進(jìn)程上下文切換包括4個(gè)步驟：1.決定是否作上下文切換以及是否允許做上下文切換。包括對(duì)進(jìn)程調(diào)度原因的檢查分析，以及當(dāng)前執(zhí)行進(jìn)程的資格和CPU執(zhí)行方式的檢查等；2.保存當(dāng)前執(zhí)行進(jìn)程的上下文。2003年9月28日314.3.3進(jìn)程上下文切換（續(xù)）進(jìn)程上下文切換的步驟(續(xù))：3.按照某個(gè)進(jìn)程調(diào)度算法，選擇一個(gè)處于就緒狀態(tài)的進(jìn)程。4.恢復(fù)或裝配所選進(jìn)程的上下文，將CPU控制權(quán)交給所選進(jìn)程。2003年9月28日324.3.4進(jìn)程調(diào)度性能評(píng)價(jià)進(jìn)程調(diào)度性能的衡量是操作系統(tǒng)設(shè)計(jì)的一個(gè)重要指標(biāo)。進(jìn)程調(diào)度性能的定性衡量：可靠性：如進(jìn)程調(diào)度是否會(huì)破壞數(shù)據(jù)結(jié)構(gòu)。簡(jiǎn)潔性：調(diào)度程序不會(huì)太繁瑣和復(fù)雜進(jìn)程調(diào)度性能的定量衡量：CPU利用率進(jìn)程等待-執(zhí)行時(shí)間比響應(yīng)時(shí)間2003年9月28日334.4進(jìn)程調(diào)度算法先來(lái)先服務(wù)(FCFS)最短作業(yè)優(yōu)先(shortestjobfirst)時(shí)間片輪轉(zhuǎn)法(Roundrobin)多級(jí)反饋輪轉(zhuǎn)法(roundrobinwithmultiplefeedback)優(yōu)先級(jí)法(PriorityScheduling)最高響應(yīng)比優(yōu)先(highestresponse_rationext)2003年9月28日34本小節(jié)學(xué)習(xí)目標(biāo)理解各調(diào)度算法的原理學(xué)會(huì)分析比較各種算法的優(yōu)缺點(diǎn)能運(yùn)用所學(xué)知識(shí)對(duì)實(shí)例進(jìn)行分析是本章的重點(diǎn)和難點(diǎn)2003年9月28日35回顧：評(píng)價(jià)算法的各種指標(biāo)周轉(zhuǎn)時(shí)間：從作業(yè)提交給系統(tǒng)到返回結(jié)果所需時(shí)間；平均周轉(zhuǎn)時(shí)間T平均帶權(quán)周轉(zhuǎn)時(shí)間（帶權(quán)周轉(zhuǎn)時(shí)間W=

T周轉(zhuǎn)時(shí)間/E執(zhí)行時(shí)間）響應(yīng)時(shí)間：用戶(hù)輸入一個(gè)請(qǐng)求（如擊鍵）到系統(tǒng)給出首次響應(yīng)（如屏幕顯示）的時(shí)間－－分時(shí)系統(tǒng)截止時(shí)間：開(kāi)始截止時(shí)間和完成截止時(shí)間－－實(shí)時(shí)系統(tǒng)，與周轉(zhuǎn)時(shí)間有些相似。公平性：不因作業(yè)或進(jìn)程本身的特性而使上述指標(biāo)過(guò)分惡化。如長(zhǎng)作業(yè)等待很長(zhǎng)時(shí)間。(《論語(yǔ)季氏》:“不患寡而患不均”

)優(yōu)先級(jí)(效率)：可以使關(guān)鍵任務(wù)達(dá)到更好的指標(biāo)(鄧小平：讓一部分人先富起來(lái))。吞吐率：在給定時(shí)間內(nèi)，一個(gè)計(jì)算機(jī)系統(tǒng)所完成的總工作量；設(shè)備利用率：指I/O設(shè)備的使用情況。實(shí)現(xiàn)難度：實(shí)現(xiàn)該算法是否容易執(zhí)行開(kāi)銷(xiāo)比：該算法是否消耗太多系統(tǒng)資源2003年9月28日364.4.1先來(lái)先服務(wù)(FCFS)按照作業(yè)提交或進(jìn)程變?yōu)榫途w狀態(tài)的先后次序，分派CPU；當(dāng)前進(jìn)程占用CPU，直到執(zhí)行完或阻塞，才出讓CPU（非搶占方式）。在進(jìn)程喚醒后（如I/O完成），并不立即恢復(fù)執(zhí)行，通常等到當(dāng)前作業(yè)或進(jìn)程出讓CPU。好比我們?cè)谑程门抨?duì)打飯！2003年9月28日37FCFS調(diào)度例子假設(shè)：用戶(hù)區(qū)內(nèi)存空間只有100KB，內(nèi)存連續(xù)分配且運(yùn)行中不能移動(dòng)。作業(yè)名作業(yè)到達(dá)的時(shí)間需計(jì)算的時(shí)間（分）需要內(nèi)存量（KB）A8:064215B8:183060C8:302450D8:362410E8:421220調(diào)度順序？2003年9月28日38作業(yè)需時(shí)需內(nèi)存A4215B3060C2450D2410E1220作業(yè)名到達(dá)時(shí)間作業(yè)調(diào)度時(shí)間進(jìn)程開(kāi)始時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A8:068:06B8:188:18C8:309:18D8:368:36E8:429:188:068:484242/429:189:426666/249:4210:069696/2410:0610:189696/12T=(42+60+66+96+96)/5=72(min)W=(1+2+2.75+4+8)/5=3.55內(nèi)存容量100K8:489:186060/30調(diào)度順序：A->B->D->C->EFCFS調(diào)度例子返回SJF2003年9月28日394.4.1先來(lái)先服務(wù)(FCFS)特點(diǎn)：最簡(jiǎn)單的算法，表面上很公平；比較有利于長(zhǎng)作業(yè)，而不利于短作業(yè)。有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。影響：可能會(huì)降低吞吐率增加平均周轉(zhuǎn)時(shí)間2003年9月28日404.4.2最短作業(yè)優(yōu)先

(SJF,ShortestJobFirst)又稱(chēng)為“短進(jìn)程優(yōu)先”SPN(ShortestProcessNext)；這是對(duì)FCFS算法的改進(jìn)，其目標(biāo)是提高吞吐率，減少平均周轉(zhuǎn)時(shí)間。對(duì)預(yù)計(jì)執(zhí)行時(shí)間短的作業(yè)（進(jìn)程）優(yōu)先分派處理機(jī)。通常后來(lái)的短作業(yè)不搶先正在執(zhí)行的作業(yè)。(非剝奪)2003年9月28日41短作業(yè)優(yōu)先調(diào)度例子作業(yè)名到達(dá)時(shí)間作業(yè)調(diào)度時(shí)進(jìn)程開(kāi)始時(shí)結(jié)束時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A8:068:06B8:188:18C8:309:42D8:368:36E8:429:12T=(42+84+108+36+72)/5=68.4(min)W=(1+2.8+4.5+1.5+6)/5=3.16作業(yè)需時(shí)需內(nèi)存A4215B3060C2450D2410E12208:068:484242/42=18:489:123636/24=1.59:5410:18108108/24=4.59:429:547272/12=69:129:428484/30=2.8調(diào)度順序：A->D->B->E->CBE5KE5KE5KC查看FCFS2003年9月28日42非搶占式SJF調(diào)度例子

ExampleofNon-PreemptiveSJF

Process

ArrivalTime

UseTime P1 0.0 7 P22.0 4 P3 4.0 1 P4 5.0 4SJF(non-preemptive非搶占)

平均周轉(zhuǎn)時(shí)間T=(7+10+4+11)/4=8

平均帶權(quán)周轉(zhuǎn)時(shí)間W=(1+10/4+4+11/4)/4=2.56P1P3P273160P48122003年9月28日43搶占式SJF調(diào)度例子

ExampleofPreemptiveSJF

Process

ArrivalTime

UseTime P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4SJF(preemptive搶占)平均周轉(zhuǎn)時(shí)間=(16+5+1+6)/4=7平均帶權(quán)周轉(zhuǎn)時(shí)間T=(16/7+5/4+1+6/4)/4=1.51P1P3P242110P457P2P1162003年9月28日44

SJF算法的特點(diǎn)優(yōu)點(diǎn)：比FCFS改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，縮短作業(yè)的等待時(shí)間；提高系統(tǒng)的吞吐量；缺點(diǎn)：對(duì)長(zhǎng)作業(yè)非常不利，可能長(zhǎng)時(shí)間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來(lái)劃分執(zhí)行的優(yōu)先級(jí)；難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間，從而影響調(diào)度性能。2003年9月28日454.4.3輪轉(zhuǎn)法(RoundRobin)將系統(tǒng)中所有的就緒進(jìn)程按照FCFS原則，排成一個(gè)隊(duì)列。每次調(diào)度時(shí)將CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的長(zhǎng)度從幾個(gè)ms到幾百ms。在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷。調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，并通過(guò)上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程。進(jìn)程可以未使用完一個(gè)時(shí)間片，就出讓CPU（如阻塞）。2003年9月28日464.4.3輪轉(zhuǎn)法(RoundRobin)輪轉(zhuǎn)法調(diào)度：FCBACPU完成如何確定時(shí)間片？2003年9月28日474.4.3輪轉(zhuǎn)法(RoundRobin)

--時(shí)間片長(zhǎng)度的確定時(shí)間片長(zhǎng)度變化的影響過(guò)長(zhǎng)－>退化為FCFS算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)都執(zhí)行完，響應(yīng)時(shí)間長(zhǎng)。過(guò)短－>用戶(hù)的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，上下文切換次數(shù)增加，響應(yīng)時(shí)間長(zhǎng)。對(duì)響應(yīng)時(shí)間的要求：q(時(shí)間片)=R(響應(yīng)時(shí)間)/Nmax(進(jìn)程數(shù)目)時(shí)間片長(zhǎng)度的影響因素：就緒進(jìn)程的數(shù)目：數(shù)目越多，時(shí)間片越?。ó?dāng)響應(yīng)時(shí)間一定時(shí)）系統(tǒng)的處理能力：應(yīng)當(dāng)使用戶(hù)輸入通常在一個(gè)時(shí)間片內(nèi)能處理完，否則使響應(yīng)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間延長(zhǎng)。2003年9月28日48時(shí)間片輪轉(zhuǎn)法(q=1)進(jìn)程名到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A012026262.17B05117173.4C03211113.67D06320203.33周轉(zhuǎn)時(shí)間T=18.5,平均帶權(quán)周轉(zhuǎn)時(shí)間W=3.14262003年9月28日49時(shí)間片輪轉(zhuǎn)法(q=4)進(jìn)程名到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A012026262.17B05420204C03811113.67D061122223.67周轉(zhuǎn)時(shí)間T=19.75,平均帶權(quán)周轉(zhuǎn)時(shí)間W=3.38這個(gè)例子的最佳時(shí)間片是多少？2003年9月28日50進(jìn)程名到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A012026262.17B05317173.4C036993D06920203.33周轉(zhuǎn)時(shí)間T=18,平均帶權(quán)周轉(zhuǎn)時(shí)間W=2.98時(shí)間片輪轉(zhuǎn)法(q=3)2003年9月28日51進(jìn)程名到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A012026262.17B05510102C031013134.33D061524244周轉(zhuǎn)時(shí)間T=18.25,平均帶權(quán)周轉(zhuǎn)時(shí)間W=3.12時(shí)間片輪轉(zhuǎn)法(q=5)2003年9月28日524.4.4多級(jí)反饋輪轉(zhuǎn)法把就緒隊(duì)列按照進(jìn)程到達(dá)就緒隊(duì)列的類(lèi)型和進(jìn)程被阻塞時(shí)的原因分成不同的就緒隊(duì)列；每個(gè)隊(duì)列按FCFS方式排列，各隊(duì)列之間的進(jìn)程享有不同的優(yōu)先級(jí)，但同一隊(duì)列內(nèi)優(yōu)先級(jí)相同；當(dāng)一個(gè)進(jìn)程在執(zhí)行完它的時(shí)間片后，或從睡眠中被喚醒以及被創(chuàng)建之后，將進(jìn)入不同的就緒隊(duì)列。2003年9月28日53多級(jí)反饋隊(duì)列：就緒隊(duì)列2時(shí)間片S2>S1就緒隊(duì)列1時(shí)間片S1時(shí)間片完時(shí)間片完運(yùn)行運(yùn)行運(yùn)行就緒隊(duì)列n時(shí)間片Sn>Sn-1完成完成完成時(shí)間片完阻塞隊(duì)列i阻塞阻塞阻塞事件發(fā)生2003年9月28日54多級(jí)反饋輪轉(zhuǎn)法的特點(diǎn)：多級(jí)反饋輪轉(zhuǎn)法不必事先知道各種進(jìn)程所需的執(zhí)行時(shí)間，仍能基本滿(mǎn)足短進(jìn)程優(yōu)先和I/O頻繁的進(jìn)程優(yōu)先的需要，因而是目前公認(rèn)的較好的一種進(jìn)程調(diào)度算法。在UNIX系統(tǒng)、WindowsNT、OS/2中都采用了類(lèi)似的調(diào)度算法。2003年9月28日55本段小結(jié)先來(lái)先服務(wù)(FCFS)最短作業(yè)優(yōu)先(shortestjobfirst)時(shí)間片輪轉(zhuǎn)法(Roundrobin)多級(jí)反饋輪轉(zhuǎn)法(roundrobinwithmultiplefeedback)優(yōu)先級(jí)法(PriorityScheduling)最高響應(yīng)比優(yōu)先(highestresponse_rationext)2003年9月28日564.4.5優(yōu)先級(jí)法(PriorityScheduling)按照進(jìn)程的優(yōu)先權(quán)大小來(lái)調(diào)度，使高優(yōu)先權(quán)進(jìn)程得到優(yōu)先處理的調(diào)度策略稱(chēng)為優(yōu)先權(quán)調(diào)度算法。進(jìn)程的優(yōu)先權(quán)的設(shè)置可以是靜態(tài)的，也可以是動(dòng)態(tài)的。2003年9月28日57靜態(tài)優(yōu)先級(jí)靜態(tài)優(yōu)先權(quán)在進(jìn)程創(chuàng)建時(shí)確定，且的在整個(gè)生命期中保持不變。確定進(jìn)程優(yōu)先權(quán)的依據(jù)有：進(jìn)程類(lèi)型，通常系統(tǒng)進(jìn)程（例如對(duì)換進(jìn)程）的優(yōu)先權(quán)高于一般用戶(hù)態(tài)進(jìn)程的優(yōu)先權(quán)；進(jìn)程對(duì)資源的需求，如進(jìn)程執(zhí)行時(shí)間及內(nèi)存需要省的進(jìn)程應(yīng)賦予較高的優(yōu)先權(quán)；根據(jù)用戶(hù)要求，由用戶(hù)的緊迫程度及用戶(hù)所付費(fèi)用的多少來(lái)確定進(jìn)程的優(yōu)先權(quán)。2003年9月28日58動(dòng)態(tài)優(yōu)先級(jí)動(dòng)態(tài)優(yōu)先權(quán)是指在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，可以隨進(jìn)程的推進(jìn)而改變，以便獲得更好的調(diào)度性能。改變優(yōu)先權(quán)的因數(shù)，隨系統(tǒng)不同而不同，最常考慮的因素是進(jìn)程的等待時(shí)間，已使用處理機(jī)的時(shí)間，或者資源使用情況等。思考：等待時(shí)間長(zhǎng)的進(jìn)程優(yōu)先級(jí)應(yīng)該提高還是降低？2003年9月28日59確定動(dòng)態(tài)優(yōu)先級(jí)的原則在就緒隊(duì)列中，等待時(shí)間延長(zhǎng)則優(yōu)先級(jí)提高，從而使優(yōu)先級(jí)較低的進(jìn)程在等待足夠的時(shí)間后，其優(yōu)先級(jí)提高到可被調(diào)度執(zhí)行；進(jìn)程每執(zhí)行一個(gè)時(shí)間片，就降低其優(yōu)先級(jí)，從而一個(gè)進(jìn)程持續(xù)執(zhí)行時(shí)，其優(yōu)先級(jí)降低到出讓CPU。2003年9月28日60例：線性?xún)?yōu)先級(jí)調(diào)度算法

（SRR,SelfishRoundRobin）本算法是優(yōu)先級(jí)算法的一個(gè)實(shí)例，它通過(guò)進(jìn)程優(yōu)先級(jí)的遞增來(lái)改進(jìn)長(zhǎng)執(zhí)行時(shí)間進(jìn)程的周轉(zhuǎn)時(shí)間特征。就緒進(jìn)程隊(duì)列分成兩個(gè)：新創(chuàng)建進(jìn)程隊(duì)列：按FCFS方式排成；進(jìn)程優(yōu)先級(jí)按速率a增加；享受服務(wù)隊(duì)列：已得到過(guò)時(shí)間片服務(wù)的進(jìn)程按FCFS方式排成；進(jìn)程優(yōu)先級(jí)按速率b增加；新創(chuàng)建進(jìn)程等待時(shí)間的確定：當(dāng)新創(chuàng)建進(jìn)程優(yōu)先級(jí)與享受服務(wù)隊(duì)列中最后一個(gè)進(jìn)程優(yōu)先級(jí)相同時(shí)，轉(zhuǎn)入享受服務(wù)隊(duì)列；2003年9月28日61線性?xún)?yōu)先級(jí)調(diào)度算法（SRR）FCBACPU完成享受服務(wù)進(jìn)程隊(duì)列新創(chuàng)建進(jìn)程隊(duì)列2003年9月28日62

SRR算法的優(yōu)先級(jí)變化當(dāng)b>a>0時(shí)，享受服務(wù)隊(duì)列中永遠(yuǎn)只有一個(gè)進(jìn)程；SRR算法退化成FCFS算法；當(dāng)a>b=0時(shí)，SRR算法就是時(shí)間片輪轉(zhuǎn)算法；2003年9月28日63優(yōu)先級(jí)法調(diào)度示例例如：假定在單CPU條件下有下列要執(zhí)行的作業(yè)：各作業(yè)依次到達(dá)，相差一個(gè)時(shí)間單位。①用執(zhí)行時(shí)間圖描述非搶占優(yōu)先級(jí)調(diào)度算法執(zhí)行這些作業(yè)的情況；②算出各作業(yè)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。作業(yè)運(yùn)行時(shí)間優(yōu)先級(jí)11032143224115532003年9月28日64用執(zhí)行時(shí)間圖描述非搶占優(yōu)先級(jí)調(diào)度算法執(zhí)行這些作業(yè)的情況優(yōu)先級(jí)法調(diào)度示例(cont.)2003年9月28日65算出各作業(yè)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間作業(yè)到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間1010010101.021118191818.03221113115.5431101188.05451318142.8平均周轉(zhuǎn)時(shí)間T=12.2

平均帶權(quán)周轉(zhuǎn)時(shí)間W=7.06優(yōu)先級(jí)法調(diào)度示例(cont.)2003年9月28日664.4.6最高響應(yīng)比優(yōu)先HighestResponseRatioNext(HRRN)法按照高響應(yīng)比優(yōu)先的原則，在每次選擇作業(yè)投入運(yùn)行時(shí)，先計(jì)算此時(shí)后備作業(yè)隊(duì)列中每個(gè)作業(yè)的響應(yīng)比R然后選擇其值最大的作業(yè)投入運(yùn)行。

R值定義為：

R＝（已等待時(shí)間＋要求運(yùn)行時(shí)間）／要求運(yùn)行時(shí)間＝1＋已等待時(shí)間／要求運(yùn)行時(shí)間。

HRN算法實(shí)際上是FCFS算法和SJF算法的折衷。

優(yōu)點(diǎn)？缺點(diǎn)？2003年9月28日674.4.6最高響應(yīng)比優(yōu)先(HRRN)法FCFS與SJF是片面的調(diào)度算法。FCFS只考慮作業(yè)等候時(shí)間而忽視了作業(yè)的計(jì)算時(shí)問(wèn)，SJF只考慮用戶(hù)估計(jì)的作業(yè)計(jì)算時(shí)間而忽視了作業(yè)等待時(shí)間。HRRF是介乎這兩者之間的折衷算法，既考慮作業(yè)等待時(shí)間，又考慮作業(yè)的運(yùn)行時(shí)間，既照顧短作業(yè)又不使長(zhǎng)作業(yè)的等待時(shí)間過(guò)長(zhǎng)，改進(jìn)了調(diào)度性能。2003年9月28日684.4.6最高響應(yīng)比優(yōu)先(HRRN)法HRRF算法特點(diǎn)：短作業(yè)容易得到較高響應(yīng)比長(zhǎng)作業(yè)等待時(shí)間足夠長(zhǎng)后，也將獲得足夠高的響應(yīng)比饑餓現(xiàn)象不會(huì)發(fā)生。2003年9月28日69三、HRRF---算法舉例(1)例如，以下四個(gè)作業(yè)先后到達(dá)系統(tǒng)進(jìn)入調(diào)度：作業(yè)名到達(dá)時(shí)間所需CPU時(shí)間作業(yè)10 20

作業(yè)25 15

作業(yè)3105

作業(yè)415 102003年9月28日70三、HRRF---算法舉例(2)

假設(shè)實(shí)施SJFSJF的作業(yè)調(diào)度順序?yàn)樽鳂I(yè)1、3、4、2平均作業(yè)周轉(zhuǎn)時(shí)間T=

(20+(25-19)+(35-15)+(50-5))／４＝(20+15+20+45)／4=25

平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=(20/20+15/5+25/10+45/15)／4=2.252003年9月28日71三、HRRF---算法舉例(3)

假設(shè)實(shí)施FCFS如果對(duì)它們施行FCFS調(diào)度算法

平均作業(yè)周轉(zhuǎn)時(shí)間

T=(20+30+30+35)／4=28.75

平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=(20/20+30/15+30/5+35/10)／4=3.132003年9月28日72三、HRRF---算法舉例(4)

對(duì)作業(yè)流執(zhí)行HRRF調(diào)度算法?開(kāi)始只有作業(yè)1，被選中執(zhí)行時(shí)間20ms；?作業(yè)1執(zhí)行完畢，響應(yīng)比依次為1+15/15、1+10/5、1+5/10，作業(yè)3被選中，執(zhí)行時(shí)間5ms；?作業(yè)3執(zhí)行完畢，響應(yīng)比依次為1+20/15、1+10/10，作業(yè)2被選中，執(zhí)行時(shí)間15ms；?作業(yè)2執(zhí)行完畢，作業(yè)4被選中，執(zhí)行時(shí)間10ms；

平均作業(yè)周轉(zhuǎn)時(shí)間T=(20+15+35+35)/4=26.25

平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=(20/20+15/5+35/15+35/10)/4=2.46作業(yè)1