操作系統四種調度算法

　　操作系統對進程的調度一般上有四種常見的算法。下面由學習啦小編為大家整理了操作系統的四種調度算法的相關知識，希望對大家有幫助!

　　操作系統四重調度算法之一、先來先服務調度算法

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

　　操作系統四重調度算法之二、短作業(yè)(進程)優(yōu)先調度算法

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

　　操作系統四重調度算法之三、高優(yōu)先權優(yōu)先調度算法

　　1.優(yōu)先權調度算法的類型

　　為了照顧緊迫型作業(yè)，使之在進入系統后便獲得優(yōu)先處理，引入了最高優(yōu)先權優(yōu)先(FPF)調度算法。此算法常被用于批處理系統中，作為作業(yè)調度算法，也作為多種操作系統中的進程調度算法，還可用于實時系統中。當把該算法用于作業(yè)調度時，系統將從后備隊列中選擇若干個優(yōu)先權最高的作業(yè)裝入內存。當用于進程調度時，該算法是把處理機分配給就緒隊列中優(yōu)先權最高的進程，這時，又可進一步把該算法分成如下兩種。

　　1) 非搶占式優(yōu)先權算法

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

　　2) 搶占式優(yōu)先權調度算法

　　在這種方式下，系統同樣是把處理機分配給優(yōu)先權最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現了另一個其優(yōu)先權更高的進程，進程調度程序就立即停止當前進程(原優(yōu)先權最高的進程)的執(zhí)行，重新將處理機分配給新到的優(yōu)先權最高的進程。因此，在采用這種調度算法時，是每當系統中出現一個新的就緒進程i 時，就將其優(yōu)先權Pi與正在執(zhí)行的進程j 的優(yōu)先權Pj進行比較。如果Pi≤Pj，原進程Pj便繼續(xù)執(zhí)行;但如果是Pi>Pj，則立即停止Pj的執(zhí)行，做進程切換，使i 進程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權調度算法能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴格的實時系統中，以及對性能要求較高的批處理和分時系統中。

　　操作系統四重調度算法之四、基于時間片的輪轉調度算法

　　1.時間片輪轉法

　　1) 基本原理

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

　　2.多級反饋隊列調度算法

　　前面介紹的各種用作進程調度的算法都有一定的局限性。如短進程優(yōu)先的調度算法，僅照顧了短進程而忽略了長進程，而且如果并未指明進程的長度，則短進程優(yōu)先和基于進程長度的搶占式調度算法都將無法使用。而多級反饋隊列調度算法則不必事先知道各種進程所需的執(zhí)行時間，而且還可以滿足各種類型進程的需要，因而它是目前被公認的一種較好的進程調度算法。在采用多級反饋隊列調度算法的系統中，調度算法的實施過程如下所述。

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

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

　　(3) 僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行;僅當第1～(i-1)隊列均空時，才會調度第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務時，又有新進程進入優(yōu)先權較高的隊列(第1～(i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調度程序把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優(yōu)先權進程。