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

1、W內(nèi) 容l 嵌入式操作系統(tǒng)概述嵌入式操作系統(tǒng)概述l 進程管理進程管理l 同步與互斥同步與互斥l 調(diào)度調(diào)度lSmall RTOSSmall RTOS任務管理和調(diào)度任務管理和調(diào)度lSmallSmall RTOS RTOS同步與互斥同步與互斥lSmall RTOSSmall RTOS應用應用 處理機調(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)先權原則。優(yōu)先權高的進程搶占處理機。 （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)建新進程時就排在就緒隊列的末尾，按時間片輪轉方式運行進程在執(zhí)行時，出現(xiàn)三種情況：（1）任務在時間片內(nèi)完成，進程在釋放處理機后進入完成狀態(tài)；（2）任務在時間片內(nèi)未完成，OS便將該任務放入就緒隊列的末尾；（3）在執(zhí)行期間，進程因為某事件而被阻塞，被OS放入阻塞隊列。就緒隊列就緒隊列阻塞隊列阻塞隊列cpu進程調(diào)度進程調(diào)度等待事件等待事件時間片完時間片完進程完成進程完成用戶用戶事件出現(xiàn)事件出現(xiàn)有高級和低級調(diào)度的調(diào)度隊列模型 與前一模型的差別：（1）就緒隊列的形式。批處理系統(tǒng)中最常用的是優(yōu)先權隊列。也可采用無序鏈表方式。（2）設置多個

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)存就緒轉變?yōu)橥獯婢途w，由內(nèi)存阻塞轉變?yōu)橥獯孀枞?在中級調(diào)度使外存就緒轉變?yōu)閮?nèi)存就緒。選擇調(diào)度方式和選擇調(diào)度方式和調(diào)度算法的準則調(diào)度算法的準則 面向用戶的準則面向用戶的準則 面向系統(tǒng)的準則面向系統(tǒng)的準則周轉時間短周轉時間短響應時間快響應時間快 截止時間的保證截止時間的保證 優(yōu)先權準則優(yōu)先權準則 系統(tǒng)吞吐量高系統(tǒng)吞吐量高處理機利用率好處理機利用率好 資源的平衡利用資源的平衡利用 周

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

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

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

9、有關。對于大型作業(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)度算法算法 先來先服務調(diào)度算法先來先服務調(diào)度算法l作業(yè)調(diào)度中每次從后備作業(yè)隊列中，選擇一個或多個最先進入該隊列的作業(yè)調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放入就緒隊列。l進程調(diào)度時每次從就緒隊列中，選擇一個最先進入該隊列的進程分配處理機使之運行。直到完成或阻塞后，才放棄處理機。先來先服務調(diào)度算

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

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

12、時間帶權周轉時間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 服務時間服務時間4 3 5 2 4FCFS 完成時間完成時間周轉時間周轉時間帶權周轉時間帶權周轉時間SPF

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

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

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

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

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

18、6 3 9 8帶權周轉時間帶權周轉時間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è)（進程），將導致長作業(yè)長期不被調(dià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)先權優(yōu)先調(diào)度算法高優(yōu)先權優(yōu)先調(diào)度算法1 1優(yōu)先權調(diào)度算法的類型優(yōu)先權調(diào)度算法的類型2 2優(yōu)先權的類型優(yōu)先權的類型3. 3. 高響應比優(yōu)先調(diào)度算法高響應比優(yōu)先調(diào)度算法優(yōu)先權調(diào)度算法類型優(yōu)先權調(diào)度算法類型1 1）非搶占式優(yōu)先權算法）非搶占式優(yōu)先權算法2 2）搶占式優(yōu)先權調(diào)度算法）搶占式優(yōu)先權調(diào)度算法非搶占式優(yōu)先權算法 把處理機分配給就緒隊列中優(yōu)先權最高的進程后便一直執(zhí)行下去直至完成；或發(fā)生某事件使該進程放棄處理機時，可再將處理機重新分配給另一優(yōu)先權最高的進程。 用于批處理系統(tǒng)和某些對實時性要求不嚴的實時系統(tǒng)中。低優(yōu)先級任

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

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

22、3 3運行結束運行結束任務任務2 2運行結束運行結束 任務任務1 1被具有更高優(yōu)先級的任務被具有更高優(yōu)先級的任務2 2所搶占，然后任務所搶占，然后任務2 2又被任務又被任務3 3搶占。當搶占。當任務任務3 3完成運行后，任務完成運行后，任務2 2繼續(xù)執(zhí)行。當任務繼續(xù)執(zhí)行。當任務2 2完成運行后，任務完成運行后，任務1 1才又得才又得以繼續(xù)執(zhí)行。以繼續(xù)執(zhí)行。 優(yōu)先權的類型優(yōu)先權的類型 靜態(tài)優(yōu)先權靜態(tài)優(yōu)先權 動態(tài)優(yōu)先權動態(tài)優(yōu)先權靜態(tài)優(yōu)先權靜態(tài)優(yōu)先權在創(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)先權依據(jù)：（1）進程類型：系統(tǒng)進程高于用戶進程（2）進程對資源的要求：要求少的進程應賦予較高優(yōu)先權。（3）用戶要求。這是由用戶進程的緊迫程度及所付費多少來確定。靜態(tài)優(yōu)先權法優(yōu)缺點l簡單，系統(tǒng)開銷小l不精確，僅在要求不高的系統(tǒng)中使用動態(tài)優(yōu)先權動態(tài)優(yōu)先權 優(yōu)先權隨進程推進或隨其等待時間的增加而改變的，以便獲得更好的調(diào)度性能。 高響應比優(yōu)先調(diào)度算法高響應比優(yōu)先調(diào)度算法 引入動態(tài)優(yōu)先權，并使作業(yè)優(yōu)先級隨著等待時間的增加而以某個速率a提高。該優(yōu)先權的變化規(guī)律為：優(yōu)先

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

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

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

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

28、小，只要使作業(yè)（進程）在第一隊列所規(guī)定的時間片內(nèi)完成，便可令用戶滿意。（2）短批處理作業(yè)用戶。其周轉時間短。（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）非搶占式輪轉調(diào)度算法 （2）非搶占式優(yōu)先調(diào)度算法 非搶占式輪轉調(diào)度算法v用于工業(yè)群控系統(tǒng)中v由一臺計算機控制若干個相同的（或類似的）對象，為每一個被控對象建立一個實時任務，并將它們排成一個輪轉隊列。v調(diào)度程序每次選擇隊列中的第一個任務運行。完成后，便把它掛在輪轉隊列的末尾，等待下次調(diào)度運行，調(diào)度程序再選擇下一個（隊首）任務運行。v可獲得數(shù)秒至數(shù)十秒的響應時間 非搶占式優(yōu)先調(diào)度算法 針對有一定要求的系統(tǒng) 為實時要求高的任務賦予較高的優(yōu)先