摘要：搶占式優(yōu)先權調度算法在這種方式下，系統(tǒng)同樣是把處理機分配給優(yōu)先權最高的進程，使之執(zhí)行。多級反饋隊列調度算法應設置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級。

一 優(yōu)先調度算法 1.先來先服務調度算法（FCFS）

當在作業(yè)調度中采用該算法時，每次調度都是從后備作業(yè)隊列中選擇一個或多個最先進入該隊 列的作業(yè)，將它們調入內存，為它們分配資源、創(chuàng)建進程，然后放入就緒隊列。在進程調度中采 用 FCFS 算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機， 使之投入運行。該進程一直運行到完成或發(fā)生某事件而阻塞后才放棄處理機，特點是：算法比較 簡單，可以實現(xiàn)基本上的公平。

短作業(yè)優(yōu)先(SJF)的調度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們 調入內存運行。而短進程優(yōu)先(SPF)調度算法則是從就緒隊列中選出一個估計運行時間最短的進程， 將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時再重 新調度。該算法未照顧緊迫型作業(yè)。

為了照顧緊迫型作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權優(yōu)先(FPF)調度 算法。當把該算法用于作業(yè)調度時，系統(tǒng)將從后備隊列中選擇若干個優(yōu)先權最高的作業(yè)裝入內存。 當用于進程調度時，該算法是把處理機分配給就緒隊列中優(yōu)先權最高的進程。

在這種方式下，系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權最高的進程后，該進程便一直執(zhí)行下 去，直至完成；或因發(fā)生某事件使該進程放棄處理機時。這種調度算法主要用于批處理系統(tǒng)中； 也可用于某些對實時性要求不嚴的實時系統(tǒng)中。

在這種方式下，系統(tǒng)同樣是把處理機分配給優(yōu)先權最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只 要又出現(xiàn)了另一個其優(yōu)先權更高的進程，進程調度程序就立即停止當前進程(原優(yōu)先權最高的進程) 的執(zhí)行，重新將處理機分配給新到的優(yōu)先權最高的進程。顯然，這種搶占式的優(yōu)先權調度算法能 更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴格的實時系統(tǒng)中，以及對性能要求較高的批 處理和分時系統(tǒng)中。

在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長作業(yè)的運行 得不到保證。如果我們能為每個作業(yè)引入前面所述的動態(tài)優(yōu)先權，并使作業(yè)的優(yōu)先級隨著等待時 間的增加而以速率 a 提高，則長作業(yè)在等待一定的時間后，必然有機會分配到處理機。該優(yōu)先權的 變化規(guī)律可描述為：

(1) 如果作業(yè)的等待時間相同，則要求服務的時間愈短，其優(yōu)先權愈高，因而該算法有利于短作業(yè)。

(2) 當要求服務的時間相同時，作業(yè)的優(yōu)先權決定于其等待時間，等待時間愈長，其優(yōu)先權愈高，因而它實現(xiàn)的是先來先服務。

(3) 對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高，當其等待時間足夠長時，其優(yōu)先級便可升到很高，從而也可獲得處理機。簡言之，該算法既照顧了短作業(yè)，又考慮了作業(yè)到達的先后次序，不會使長作業(yè)長期得不到服務。因此，該算法實現(xiàn)了一種較好的折衷。當然，在 利用該算法時，每要進行調度之前，都須先做響應比的計算，這會增加系統(tǒng)開銷。

在早期的時間片輪轉法中，系統(tǒng)將所有的就緒進程按先來先服務的原則排成一個隊列，每次調度 時，把 CPU 分配給隊首進程，并令其執(zhí)行一個時間片。時間片的大小從幾 ms 到幾百 ms。當執(zhí)行 的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調度程序便據(jù)此信號來停止該進程的執(zhí)行， 并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執(zhí) 行一個時間片。這樣就可以保證就緒隊列中的所有進程在一給定的時間內均能獲得一時間片的處 理機執(zhí)行時間。

(1) 應設置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級。第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先權逐個降低。該算法賦予各個隊列中進程執(zhí)行時間片的大小也各不相同，在優(yōu)先權愈高的隊列中，為每個進程所規(guī)定的執(zhí)行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，……，第 i+1 個隊列的時間片要比第 i 個隊列的時間片長一倍。

(2) 當一個新進程進入內存后，首先將它放入第一隊列的末尾，按 FCFS 原則排隊等待調度。當輪到該進程執(zhí)行時，如它能在該時間片內完成，便可準備撤離系統(tǒng)；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第二隊列的末尾，再同樣地按 FCFS 原則等待調度執(zhí)行；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，……，如此下去，當一個長作業(yè)(進程)從第一隊列依次降到第 n 隊列后，在第 n 隊列便采取按時間片輪轉的方式運行。

(3) 僅當?shù)谝魂犃锌臻e時，調度程序才調度第二隊列中的進程運行；僅當?shù)?1～(i-1)隊列均空時，才會調度第 i隊列中的進程運行。如果處理機正在第 i 隊列中為某進程服務時，又有新進程進入優(yōu)先權較高的隊列(第 1～(i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調度程序把正在運行的進程放回到第 i 隊列的末尾，把處理機分配給新到的高優(yōu)先權進程。在多級反饋隊列調度算法中，如果規(guī)定第一個隊列的時間片略大于多數(shù)人機交互所需之處理時間時，便能夠較好的滿足各種類型用戶的需要。