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

1、W內(nèi) 容l 嵌入式操作系統(tǒng)概述嵌入式操作系統(tǒng)概述l 進程管理進程管理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)用 處理機調(diào)度處理機調(diào)度 一個批處理型作業(yè)，從進入系統(tǒng)并駐留在外存的后備隊列上開始，直至作業(yè)運行完畢，可能要經(jīng)歷的三級調(diào)度:高級調(diào)度 低級調(diào)度 中級調(diào)度高級調(diào)度 又稱作業(yè)調(diào)度、長程調(diào)度 、接納調(diào)度 作用：把外存上處于后備隊列中的作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配資源、排在就緒隊列上，準備執(zhí)行。 分時系統(tǒng)、實時系統(tǒng)

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

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

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

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

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

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

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

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

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

11、2102D3100102202202開始開始+運行運行進程到達時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A0101B11001101C21101102D3100102202完成完成-到達到達進程到達時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A01011B11001101100C21101102100D3100102202199周轉(zhuǎn)周轉(zhuǎn)/ /運行運行進程到達時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A010111/1B11001101100100/100C21101102100100/1100/1D3100102202199199/100進程到達時間運行時間開始時間完成時間周轉(zhuǎn)

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

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

14、 11 14 9帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1 2 2 5.5 3.5 2.8SPF完成時間完成時間4周轉(zhuǎn)時間周轉(zhuǎn)時間4帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間作業(yè)作業(yè)算法算法 進程名進程名A B C D E 平均 到達時間到達時間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 9帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1 2 2 5.5 3.5 2.8SPF完成時間完成時間4 6 周轉(zhuǎn)時間周轉(zhuǎn)時間4 3 帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間作業(yè)作業(yè)算法算法 進程名進程名A B C D E 平均 到達時間到達時間0 1 2 3 4 服務(wù)時間服務(wù)

15、時間4 3 5 2 4FCFS 完成時間完成時間4 7 12 14 18周轉(zhuǎn)時間周轉(zhuǎn)時間4 6 10 11 14 9帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1 2 2 5.5 3.5 2.8SPF完成時間完成時間4 9 6 周轉(zhuǎn)時間周轉(zhuǎn)時間4 8 3 帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間作業(yè)作業(yè)算法算法 進程名進程名A B C D E 平均 到達時間到達時間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 9帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1 2 2 5.5 3.5 2.8SPF完成時間完成時間4 9 6 13 周轉(zhuǎn)時間周轉(zhuǎn)時間4 8

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

17、間周轉(zhuǎn)時間4 6 10 11 14 9帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1 2 2 5.5 3.5 2.8SPF完成時間完成時間4 9 18 6 13 周轉(zhuǎn)時間周轉(zhuǎn)時間4 8 16 3 9 8帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1 2.673.1 1.5 2.25 2.1作業(yè)作業(yè)算法算法 進程名進程名A B C D E 平均 到達時間到達時間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 9帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1 2 2 5.5 3.5 2.8SPF完成時間完成時間4 9 18 6 13 周轉(zhuǎn)時間周轉(zhuǎn)時間4 8 1

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

19、一定能真正做到短作業(yè)優(yōu)先調(diào)度。行時間而定的不一定能真正做到短作業(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)算法 把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程后便一直執(zhí)行下去直至完成；或發(fā)生某事件使該進程放棄處理機時，可再將處理機重新分配給另一優(yōu)先權(quán)最高的進程。 用于批處理系統(tǒng)和某些對實時性要求不嚴的實時系統(tǒng)中。低優(yōu)先級任

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

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

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

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

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

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

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

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

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