第4章調(diào)度-wax

1、W內(nèi) 容l 嵌入式操作系統(tǒng)概述嵌入式操作系統(tǒng)概述l 進(jìn)程管理進(jìn)程管理l 同步與互斥同步與互斥l 調(diào)度調(diào)度lSmall RTOSSmall RTOS任務(wù)管理和調(diào)度任務(wù)管理和調(diào)度lSmallSmall RTOS RTOS同步與互斥同步與互斥lSmall RTOSSmall RTOS應(yīng)用應(yīng)用 處理機(jī)調(diào)度處理機(jī)調(diào)度 一個(gè)批處理型作業(yè)，從進(jìn)入系統(tǒng)并駐留在外存的后備隊(duì)列上開(kāi)始，直至作業(yè)運(yùn)行完畢，可能要經(jīng)歷的三級(jí)調(diào)度:高級(jí)調(diào)度 低級(jí)調(diào)度 中級(jí)調(diào)度高級(jí)調(diào)度 又稱作業(yè)調(diào)度、長(zhǎng)程調(diào)度 、接納調(diào)度 作用：把外存上處于后備隊(duì)列中的作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配資源、排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。 分時(shí)系統(tǒng)、實(shí)時(shí)系統(tǒng)

2、，通常不需要作業(yè)調(diào)度。 低級(jí)調(diào)度 也稱為進(jìn)程調(diào)度、短程調(diào)度 。作用：決定就緒隊(duì)列中的哪個(gè)進(jìn)程能夠獲得處理機(jī)，然后由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。在OS中都必須配置。進(jìn)程調(diào)度的兩種調(diào)度方式進(jìn)程調(diào)度的兩種調(diào)度方式 非搶占方式非搶占方式 搶占方式搶占方式 非搶占方式非搶占方式 一旦把處理機(jī)分配給某進(jìn)程后，便讓該進(jìn)程一直執(zhí)行，直至該進(jìn)程完成或阻塞時(shí)，才再把處理機(jī)分配給其他進(jìn)程。（1）程序執(zhí)行完畢，或因發(fā)生某事件而不能在繼續(xù)執(zhí)行；（2）執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行；（3）在進(jìn)程通信或同步過(guò)程中執(zhí)行了某種原語(yǔ)操作。 非搶占方式引起進(jìn)程調(diào)度的因素非搶占方式引起進(jìn)程調(diào)度的因素 搶占方式

3、搶占方式 允許暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。 搶占原則搶占原則 （1）優(yōu)先權(quán)原則。優(yōu)先權(quán)高的進(jìn)程搶占處理機(jī)。 （2）短作業(yè)優(yōu)先原則。短作業(yè)（進(jìn)程）搶占當(dāng)前較長(zhǎng)作業(yè)（進(jìn)程）的處理機(jī)。 （3）時(shí)間片原則。各進(jìn)程按時(shí)間片運(yùn)行，當(dāng)一個(gè)時(shí)間片用完后重新調(diào)度。 中級(jí)調(diào)度 又稱中程調(diào)度 。目的 ：提高內(nèi)存利用率和系統(tǒng)吞吐率 作用：使暫時(shí)不能運(yùn)行的進(jìn)程從內(nèi)存調(diào)至外存，進(jìn)入就緒駐外存狀態(tài)或掛起狀態(tài)。把外存上又具備運(yùn)行條件的就緒進(jìn)程，重新調(diào)入內(nèi)存，并修改為就緒狀態(tài)，掛在就緒隊(duì)列上。又稱對(duì)換 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型同

4、時(shí)有三級(jí)調(diào)度的調(diào)度隊(duì)列模型 通常，把就緒進(jìn)程組織成FIFO隊(duì)列，每當(dāng)創(chuàng)建新進(jìn)程時(shí)就排在就緒隊(duì)列的末尾，按時(shí)間片輪轉(zhuǎn)方式運(yùn)行進(jìn)程在執(zhí)行時(shí)，出現(xiàn)三種情況：（1）任務(wù)在時(shí)間片內(nèi)完成，進(jìn)程在釋放處理機(jī)后進(jìn)入完成狀態(tài)；（2）任務(wù)在時(shí)間片內(nèi)未完成，OS便將該任務(wù)放入就緒隊(duì)列的末尾；（3）在執(zhí)行期間，進(jìn)程因?yàn)槟呈录蛔枞?，被OS放入阻塞隊(duì)列。就緒隊(duì)列就緒隊(duì)列阻塞隊(duì)列阻塞隊(duì)列cpu進(jìn)程調(diào)度進(jìn)程調(diào)度等待事件等待事件時(shí)間片完時(shí)間片完進(jìn)程完成進(jìn)程完成用戶用戶事件出現(xiàn)事件出現(xiàn)有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型 與前一模型的差別：（1）就緒隊(duì)列的形式。批處理系統(tǒng)中最常用的是優(yōu)先權(quán)隊(duì)列。也可采用無(wú)序鏈表方式。（2）設(shè)置多個(gè)

5、阻塞隊(duì)列。就緒隊(duì)列就緒隊(duì)列阻塞隊(duì)列阻塞隊(duì)列cpu進(jìn)程調(diào)度進(jìn)程調(diào)度等待事件等待事件時(shí)間片完時(shí)間片完進(jìn)程完成進(jìn)程完成作業(yè)作業(yè)調(diào)度調(diào)度后備隊(duì)列后備隊(duì)列有三級(jí)調(diào)度的調(diào)度隊(duì)列模型有三級(jí)調(diào)度的調(diào)度隊(duì)列模型 調(diào)出時(shí)，可使進(jìn)程狀態(tài)由內(nèi)存就緒轉(zhuǎn)變?yōu)橥獯婢途w，由內(nèi)存阻塞轉(zhuǎn)變?yōu)橥獯孀枞?在中級(jí)調(diào)度使外存就緒轉(zhuǎn)變?yōu)閮?nèi)存就緒。選擇調(diào)度方式和選擇調(diào)度方式和調(diào)度算法的準(zhǔn)則調(diào)度算法的準(zhǔn)則 面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則周轉(zhuǎn)時(shí)間短周轉(zhuǎn)時(shí)間短響應(yīng)時(shí)間快響應(yīng)時(shí)間快 截止時(shí)間的保證截止時(shí)間的保證 優(yōu)先權(quán)準(zhǔn)則優(yōu)先權(quán)準(zhǔn)則 系統(tǒng)吞吐量高系統(tǒng)吞吐量高處理機(jī)利用率好處理機(jī)利用率好 資源的平衡利用資源的平衡利用 周

6、轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 從從作業(yè)被提交給系統(tǒng)作業(yè)被提交給系統(tǒng)開(kāi)始，到開(kāi)始，到作業(yè)完成作業(yè)完成為止的這段時(shí)為止的這段時(shí)間間隔稱為作業(yè)周轉(zhuǎn)時(shí)間。包括四部分：間間隔稱為作業(yè)周轉(zhuǎn)時(shí)間。包括四部分：在外存后備隊(duì)列上等待調(diào)度的時(shí)間在外存后備隊(duì)列上等待調(diào)度的時(shí)間進(jìn)程在就緒隊(duì)列上等待調(diào)度的時(shí)間進(jìn)程在就緒隊(duì)列上等待調(diào)度的時(shí)間進(jìn)程在進(jìn)程在CPU上執(zhí)行的時(shí)間上執(zhí)行的時(shí)間進(jìn)程等待進(jìn)程等待I/O操作完成的時(shí)間操作完成的時(shí)間 平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間： T=1/n Tii=1n n帶權(quán)周轉(zhuǎn)時(shí)間: W=T/TsT：作業(yè)的周轉(zhuǎn)時(shí)間Ts：系統(tǒng)為它提供服務(wù)的時(shí)間提供服務(wù)的時(shí)間（真正運(yùn)行時(shí)間）平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間 ：W=1/n

7、 Ti/Tsi i=1n作業(yè)提交時(shí)間/時(shí)運(yùn)行時(shí)間/h110.002210.101310.250.25例例:有三道作業(yè)。系統(tǒng)為它們服務(wù)的順序是：有三道作業(yè)。系統(tǒng)為它們服務(wù)的順序是：1、2、3。求平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。求平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。作業(yè)提交時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間110.002210.101310.250.25解：解：服務(wù)的順序是：服務(wù)的順序是：1、2、3作業(yè)提交時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間110.0021012.0022/2210.1011213.002.92.9/1310.250.251313.2533/0.25解：解：

8、服務(wù)的順序是：服務(wù)的順序是：1、2、3平均周轉(zhuǎn)時(shí)間：T=(2+2.9+3)/3=2.63（h）平均帶權(quán)周轉(zhuǎn)時(shí)間：W=(1+2.9+12)/3=5.3（h）響應(yīng)時(shí)間 響應(yīng)時(shí)間是從用戶通過(guò)鍵盤(pán)提交一個(gè)請(qǐng)求開(kāi)始直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間間隔。包括三部分時(shí)間：從鍵盤(pán)輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間將響應(yīng)信息回送到終端顯示器的時(shí)間。分時(shí)系統(tǒng)中的重要原則。 截止時(shí)間是指某任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。 對(duì)于嚴(yán)格的實(shí)時(shí)系統(tǒng)，其調(diào)度方式和調(diào)度算法必須能保證這一點(diǎn) 。吞吐量吞吐量指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。評(píng)價(jià)批處理系統(tǒng)性能的重要指標(biāo) 。與作業(yè)的平均長(zhǎng)度

9、有關(guān)。對(duì)于大型作業(yè)，一般吞吐量約為每小時(shí)一道作業(yè)；對(duì)于中、小型作業(yè)，其吞吐量則可達(dá)到幾十道作業(yè)。調(diào)度算法 v調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法定的資源分配算法 。v不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法算法 先來(lái)先服務(wù)調(diào)度算法先來(lái)先服務(wù)調(diào)度算法l作業(yè)調(diào)度中每次從后備作業(yè)隊(duì)列中，選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。l進(jìn)程調(diào)度時(shí)每次從就緒隊(duì)列中，選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程分配處理機(jī)使之運(yùn)行。直到完成或阻塞后，才放棄處理機(jī)。先來(lái)先服務(wù)調(diào)度算

10、法先來(lái)先服務(wù)調(diào)度算法l是一種最簡(jiǎn)單的調(diào)度算法既可用于作業(yè)調(diào)度也可用于進(jìn)程調(diào)度。lFCFS( first come first serve)算法l有利長(zhǎng)作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。 l有利CPU繁忙型作業(yè)，而不利于I/O繁忙型作業(yè)。進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A010B11001C21101D3100102決定服務(wù)順序決定服務(wù)順序進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A010B11001C21101D3100102開(kāi)始開(kāi)始+運(yùn)行運(yùn)行進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A0101 1B11001101101C2110110

11、2102D3100102202202開(kāi)始開(kāi)始+運(yùn)行運(yùn)行進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A0101B11001101C21101102D3100102202完成完成-到達(dá)到達(dá)進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A01011B11001101100C21101102100D3100102202199周轉(zhuǎn)周轉(zhuǎn)/ /運(yùn)行運(yùn)行進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A010111/1B11001101100100/100C21101102100100/1100/1D3100102202199199/100進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)

12、時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A010111/1B11001101100100/100C21101102100100/1100/1D3100102202199199/100短作業(yè)（進(jìn)程）優(yōu)先法 短作業(yè)優(yōu)先（SJF）法：從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)調(diào)入內(nèi)存運(yùn)行。短進(jìn)程優(yōu)先（SPF）調(diào)度算法：從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，分配處理機(jī)使它立即執(zhí)行直到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度。 進(jìn)程名進(jìn)程名A B C D E 平均 到達(dá)時(shí)間到達(dá)時(shí)間0 1 2 3 4 服務(wù)時(shí)間服務(wù)時(shí)間4 3 5 2 4FCFS 完成時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間SPF

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

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

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

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

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

18、6 3 9 8帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間1 2.673.1 1.5 2.25 2.1作業(yè)作業(yè)算法算法SJ （P）F法缺點(diǎn)（1 1）對(duì)長(zhǎng)作業(yè)不利。如果有一長(zhǎng)作業(yè)進(jìn)入系統(tǒng)的后）對(duì)長(zhǎng)作業(yè)不利。如果有一長(zhǎng)作業(yè)進(jìn)入系統(tǒng)的后備隊(duì)列，由于總是優(yōu)先調(diào)度那些短作業(yè)（進(jìn)程），備隊(duì)列，由于總是優(yōu)先調(diào)度那些短作業(yè)（進(jìn)程），將導(dǎo)致長(zhǎng)作業(yè)長(zhǎng)期不被調(diào)度。將導(dǎo)致長(zhǎng)作業(yè)長(zhǎng)期不被調(diào)度。（2 2）完全未考慮作業(yè)的緊迫程度，不能保證緊迫性）完全未考慮作業(yè)的緊迫程度，不能保證緊迫性作業(yè)（進(jìn)程）會(huì)被及時(shí)處理。作業(yè)（進(jìn)程）會(huì)被及時(shí)處理。（3 3）作業(yè)（進(jìn)程）的長(zhǎng)短根據(jù)用戶所提供的估計(jì)執(zhí)）作業(yè)（進(jìn)程）的長(zhǎng)短根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的不

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

20、務(wù)低優(yōu)先級(jí)任務(wù)內(nèi)核服務(wù)內(nèi)核服務(wù)ISRISR高優(yōu)先級(jí)任務(wù)高優(yōu)先級(jí)任務(wù)時(shí)時(shí)間間(1)(1)(2)(2)(3)(3)(4)(4)(5)(5)不可搶占內(nèi)核（允許中斷）不可搶占內(nèi)核（允許中斷）(1)(1)低優(yōu)先級(jí)任務(wù)調(diào)用內(nèi)核服務(wù)低優(yōu)先級(jí)任務(wù)調(diào)用內(nèi)核服務(wù)(2)(2)內(nèi)核服務(wù)過(guò)程中，系統(tǒng)發(fā)生中斷，在允許中斷的情況下，進(jìn)入中斷服務(wù)程內(nèi)核服務(wù)過(guò)程中，系統(tǒng)發(fā)生中斷，在允許中斷的情況下，進(jìn)入中斷服務(wù)程序（序（ISRISR）(3)(3)中斷服務(wù)程序完成后，回到內(nèi)核服務(wù)中中斷服務(wù)程序完成后，回到內(nèi)核服務(wù)中(4)(4)內(nèi)核服務(wù)完成，進(jìn)行任務(wù)調(diào)度，切換到新就緒的高優(yōu)先級(jí)任務(wù)內(nèi)核服務(wù)完成，進(jìn)行任務(wù)調(diào)度，切換到新就緒的高優(yōu)先級(jí)

21、任務(wù)(5)(5)高優(yōu)先級(jí)任務(wù)運(yùn)行完成或者因?yàn)槠渌蜃枞瑑?nèi)核調(diào)度低優(yōu)先級(jí)任務(wù)，高優(yōu)先級(jí)任務(wù)運(yùn)行完成或者因?yàn)槠渌蜃枞?，?nèi)核調(diào)度低優(yōu)先級(jí)任務(wù)，低優(yōu)先級(jí)任務(wù)恢復(fù)執(zhí)行低優(yōu)先級(jí)任務(wù)恢復(fù)執(zhí)行搶占式優(yōu)先權(quán)調(diào)度算法 把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。在執(zhí)行期間，只要又出現(xiàn)優(yōu)先權(quán)更高的進(jìn)程，就重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。 能更好地滿足緊迫作業(yè)的要求，常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。任務(wù)任務(wù)1 1任務(wù)任務(wù)2 2任務(wù)任務(wù)3 3優(yōu)先級(jí)優(yōu)先級(jí)高高低低時(shí)間時(shí)間任務(wù)任務(wù)2 2就緒就緒任務(wù)任務(wù)3 3就緒就緒任務(wù)任務(wù)2 2任務(wù)任務(wù)1 1搶占搶占搶占搶占任務(wù)任務(wù)

22、3 3運(yùn)行結(jié)束運(yùn)行結(jié)束任務(wù)任務(wù)2 2運(yùn)行結(jié)束運(yùn)行結(jié)束 任務(wù)任務(wù)1 1被具有更高優(yōu)先級(jí)的任務(wù)被具有更高優(yōu)先級(jí)的任務(wù)2 2所搶占，然后任務(wù)所搶占，然后任務(wù)2 2又被任務(wù)又被任務(wù)3 3搶占。當(dāng)搶占。當(dāng)任務(wù)任務(wù)3 3完成運(yùn)行后，任務(wù)完成運(yùn)行后，任務(wù)2 2繼續(xù)執(zhí)行。當(dāng)任務(wù)繼續(xù)執(zhí)行。當(dāng)任務(wù)2 2完成運(yùn)行后，任務(wù)完成運(yùn)行后，任務(wù)1 1才又得才又得以繼續(xù)執(zhí)行。以繼續(xù)執(zhí)行。 優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型 靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán) 動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)確定在創(chuàng)建進(jìn)程時(shí)確定在進(jìn)程的整個(gè)運(yùn)行期間保持不變。在進(jìn)程的整個(gè)運(yùn)行期間保持不變。一般地，用某一范圍內(nèi)的一個(gè)整數(shù)來(lái)表示的，例一般地，用某一范圍

23、內(nèi)的一個(gè)整數(shù)來(lái)表示的，例如，如，0707或或02550255中的某一整數(shù)，又把該整數(shù)稱為中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。優(yōu)先數(shù)。 確定優(yōu)先權(quán)依據(jù)：（1）進(jìn)程類型：系統(tǒng)進(jìn)程高于用戶進(jìn)程（2）進(jìn)程對(duì)資源的要求：要求少的進(jìn)程應(yīng)賦予較高優(yōu)先權(quán)。（3）用戶要求。這是由用戶進(jìn)程的緊迫程度及所付費(fèi)多少來(lái)確定。靜態(tài)優(yōu)先權(quán)法優(yōu)缺點(diǎn)l簡(jiǎn)單，系統(tǒng)開(kāi)銷小l不精確，僅在要求不高的系統(tǒng)中使用動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán) 優(yōu)先權(quán)隨進(jìn)程推進(jìn)或隨其等待時(shí)間的增加而改變的，以便獲得更好的調(diào)度性能。 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 引入動(dòng)態(tài)優(yōu)先權(quán)，并使作業(yè)優(yōu)先級(jí)隨著等待時(shí)間的增加而以某個(gè)速率a提高。該優(yōu)先權(quán)的變化規(guī)律為：優(yōu)先

24、權(quán) =（等待時(shí)間+要求服務(wù)時(shí)間）/要求服務(wù)時(shí)間即：優(yōu)先權(quán) = RP =響應(yīng)時(shí)間/要求服務(wù)時(shí)間 RP ：響應(yīng)比分析作業(yè)等待時(shí)間相同，則有利于作業(yè)等待時(shí)間相同，則有利于短作業(yè)短作業(yè)。要求服務(wù)時(shí)間相同，實(shí)現(xiàn)的是要求服務(wù)時(shí)間相同，實(shí)現(xiàn)的是先來(lái)先服務(wù)先來(lái)先服務(wù)。長(zhǎng)作業(yè)也可獲得處理機(jī)。長(zhǎng)作業(yè)也可獲得處理機(jī)。優(yōu)點(diǎn)：兼顧長(zhǎng)短作業(yè)。優(yōu)點(diǎn)：兼顧長(zhǎng)短作業(yè)。缺點(diǎn)：由于經(jīng)常做響應(yīng)比計(jì)算，所以增加了系缺點(diǎn)：由于經(jīng)常做響應(yīng)比計(jì)算，所以增加了系 統(tǒng)開(kāi)銷統(tǒng)開(kāi)銷時(shí)間片輪轉(zhuǎn)法 分時(shí)系統(tǒng)中多采用分時(shí)系統(tǒng)中多采用時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法 把就緒進(jìn)程組織成FIFO隊(duì)列， 把CPU分配給隊(duì)首進(jìn)程， 規(guī)定它執(zhí)行一個(gè)時(shí)間片。 時(shí)間片完時(shí)排在就

25、緒隊(duì)列的末尾，重新把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，也執(zhí)行一個(gè)時(shí)間片。 就緒隊(duì)列中的所有進(jìn)程在一定時(shí)間范圍內(nèi)，均可獲得一個(gè)時(shí)間片的CPU時(shí)間.任務(wù)任務(wù)1 1任務(wù)任務(wù)2 2任務(wù)任務(wù)3 3優(yōu)先級(jí)優(yōu)先級(jí)高高低低時(shí)間時(shí)間任務(wù)任務(wù)3 3就緒就緒任務(wù)任務(wù)3 3運(yùn)行結(jié)束運(yùn)行結(jié)束任務(wù)任務(wù)1 1任務(wù)任務(wù)2 2任務(wù)任務(wù)1 1任務(wù)任務(wù)2 2任務(wù)任務(wù)1 1和任務(wù)和任務(wù)2 2具有相同的優(yōu)先級(jí)，按照時(shí)間片輪轉(zhuǎn)的方式輪流執(zhí)行。具有相同的優(yōu)先級(jí)，按照時(shí)間片輪轉(zhuǎn)的方式輪流執(zhí)行。當(dāng)高優(yōu)先級(jí)任務(wù)當(dāng)高優(yōu)先級(jí)任務(wù)3 3就緒后，正在執(zhí)行的任務(wù)就緒后，正在執(zhí)行的任務(wù)2 2被搶占，高優(yōu)先級(jí)任務(wù)被搶占，高優(yōu)先級(jí)任務(wù)3 3得得到執(zhí)行。到執(zhí)行

26、。當(dāng)任務(wù)當(dāng)任務(wù)3 3完成運(yùn)行后，任務(wù)完成運(yùn)行后，任務(wù)2 2才重新在未完成的時(shí)間片內(nèi)繼續(xù)執(zhí)行。才重新在未完成的時(shí)間片內(nèi)繼續(xù)執(zhí)行。隨后任務(wù)隨后任務(wù)1 1和任務(wù)和任務(wù)2 2又按照時(shí)間片輪轉(zhuǎn)的方式執(zhí)行。又按照時(shí)間片輪轉(zhuǎn)的方式執(zhí)行。 多級(jí)反饋隊(duì)列調(diào)度算法 （1）為多個(gè)就緒隊(duì)列賦不同的優(yōu)先級(jí)。）為多個(gè)就緒隊(duì)列賦不同的優(yōu)先級(jí)。 第一個(gè)隊(duì)列的優(yōu)先級(jí)最高其余逐個(gè)降低。第一個(gè)隊(duì)列的優(yōu)先級(jí)最高其余逐個(gè)降低。 各隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的也不同，優(yōu)先權(quán)各隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的也不同，優(yōu)先權(quán)愈高的隊(duì)列中時(shí)間片愈愈高的隊(duì)列中時(shí)間片愈小小。多級(jí)反饋隊(duì)列調(diào)度算法 （2）新進(jìn)程進(jìn)入內(nèi)存后，首先放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)

27、等待調(diào)度。到該進(jìn)程執(zhí)行時(shí)，如果能在該時(shí)間片內(nèi)完成，便準(zhǔn)備撤離系統(tǒng)；如果未完成，轉(zhuǎn)入第二隊(duì)列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如此下去，當(dāng)一個(gè)長(zhǎng)作業(yè)從第一隊(duì)列依次降到第N隊(duì)列后，在第N隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。（3）僅當(dāng)?shù)?（i1）隊(duì)列均空時(shí)，才會(huì)調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列，則新進(jìn)程將搶占處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i隊(duì)列的末尾，把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。例如：Linux中采取active,expired隊(duì)列多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法的性能 （1）終端型作業(yè)用戶。作業(yè)較

28、小，只要使作業(yè)（進(jìn)程）在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成，便可令用戶滿意。（2）短批處理作業(yè)用戶。其周轉(zhuǎn)時(shí)間短。（3）長(zhǎng)批處理作業(yè)用戶。不必?fù)?dān)心作業(yè)長(zhǎng)期得不到處理。實(shí)時(shí)調(diào)度算法又是怎樣的呢實(shí)時(shí)調(diào)度算法又是怎樣的呢 實(shí)時(shí)調(diào)度算法分類實(shí)時(shí)調(diào)度算法分類 硬實(shí)時(shí)調(diào)度算法 軟實(shí)時(shí)調(diào)度算法 實(shí)時(shí)調(diào)度算法分類實(shí)時(shí)調(diào)度算法分類 非搶占調(diào)度算法非搶占調(diào)度算法 搶占調(diào)度算法搶占調(diào)度算法 實(shí)時(shí)調(diào)度算法分類實(shí)時(shí)調(diào)度算法分類 靜態(tài)調(diào)度算法靜態(tài)調(diào)度算法 動(dòng)態(tài)調(diào)度算法動(dòng)態(tài)調(diào)度算法 非搶占式調(diào)度算法v算法簡(jiǎn)單，用在小型實(shí)時(shí)系統(tǒng)或要求不嚴(yán)的實(shí)時(shí)控制系統(tǒng)中。v分兩種： （1）非搶占式輪轉(zhuǎn)調(diào)度算法 （2）非搶占式優(yōu)先調(diào)度算法 非搶占式輪轉(zhuǎn)調(diào)度算法v用于工業(yè)群控系統(tǒng)中v由一臺(tái)計(jì)算機(jī)控制若干個(gè)相同的（或類似的）對(duì)象，為每一個(gè)被控對(duì)象建立一個(gè)實(shí)時(shí)任務(wù)，并將它們排成一個(gè)輪轉(zhuǎn)隊(duì)列。v調(diào)度程序每次選擇隊(duì)列中的第一個(gè)任務(wù)運(yùn)行。完成后，便把它掛在輪轉(zhuǎn)隊(duì)列的末尾，等待下次調(diào)度運(yùn)行，調(diào)度程序再選擇下一個(gè)（隊(duì)首）任務(wù)運(yùn)行。v可獲得數(shù)秒至數(shù)十秒的響應(yīng)時(shí)間 非搶占式優(yōu)先調(diào)度算法 針對(duì)有一定要求的系統(tǒng) 為實(shí)時(shí)要求高的任務(wù)賦予較高的優(yōu)先級(jí)。優(yōu)先