進程的調(diào)度算法

2018-03-14 14:33:51 csdn　點擊量：評論 (0)

今天我們來說一說操作系統(tǒng)中進程的調(diào)度算法。 1 先來先服務（FCFS，first come first served）在所有調(diào)度算法中，最簡單的是非搶占式

今天我們來說一說操作系統(tǒng)中進程的調(diào)度算法。

1.先來先服務（FCFS，first come first served）

在所有調(diào)度算法中，最簡單的是非搶占式的FCFS算法。

算法原理：進程按照它們請求CPU的順序使用CPU.就像你買東西去排隊，誰第一個排，誰就先被執(zhí)行，在它執(zhí)行的過程中，不會中斷它。當其他人也想進入內(nèi)存被執(zhí)行，就要排隊等著，如果在執(zhí)行過程中出現(xiàn)一些事，他現(xiàn)在不想排隊了，下一個排隊的就補上。此時如果他又想排隊了，只能站到隊尾去。
算法優(yōu)點：易于理解且實現(xiàn)簡單，只需要一個隊列(FIFO)，且相當公平
算法缺點：比較有利于長進程，而不利于短進程，有利于CPU 繁忙的進程，而不利于I/O 繁忙的進程。

2.最短作業(yè)優(yōu)先（SJF, Shortest Job First）

短作業(yè)優(yōu)先（SJF, Shortest Job First）又稱為“短進程優(yōu)先”SPN(Shortest Process Next)；這是對FCFS算法的改進，其目標是減少平均周轉時間。

算法原理：對預計執(zhí)行時間短的進程優(yōu)先分派處理機。通常后來的短進程不搶先正在執(zhí)行的進程。

算法優(yōu)點：相比FCFS 算法，該算法可改善平均周轉時間和平均帶權周轉時間，縮短進程的等待時間，提高系統(tǒng)的吞吐量。

算法缺點：對長進程非常不利，可能長時間得不到執(zhí)行，且未能依據(jù)進程的緊迫程度來劃分執(zhí)行的優(yōu)先級，以及難以準確估計進程的執(zhí)行時間，從而影響調(diào)度性能。

最高響應比優(yōu)先法(HRRN，Highest Response Ratio Next)是對FCFS方式和SJF方式的一種綜合平衡。

算法原理：響應比R定義如下： R =(W+T)/T = 1+W/T

其中T為該作業(yè)估計需要的執(zhí)行時間，W為作業(yè)在后備狀態(tài)隊列中的等待時間。每當要進行作業(yè)調(diào)度時，系統(tǒng)計算每個作業(yè)的響應比，選擇其中R最大者投入執(zhí)行。

算法優(yōu)點：由于長作業(yè)也有機會投入運行，在同一時間內(nèi)處理的作業(yè)數(shù)顯然要少于SJF法，從而采用HRRN方式時其吞吐量將小于采用SJF 法時的吞吐量。

算法缺點

時間片輪轉算法（RR，Round-Robin）

該算法采用剝奪策略。時間片輪轉調(diào)度是一種最古老，最簡單，最公平且使用最廣的算法，又稱RR調(diào)度。每個進程被分配一個時間段，稱作它的時間片，即該進程允許運行的時間。

算法原理：讓就緒進程以FCFS 的方式按時間片輪流使用CPU 的調(diào)度方式，即將系統(tǒng)中所有的就緒進程按照FCFS 原則，排成一個隊列，每次調(diào)度時將CPU 分派給隊首進程，讓其執(zhí)行一個時間片，時間片的長度從幾個ms 到幾百ms。在一個時間片結束時，發(fā)生時鐘中斷，調(diào)度程序據(jù)此暫停當前進程的執(zhí)行，將其送到就緒隊列的末尾，并通過上下文切換執(zhí)行當前的隊首進程，進程可以未使用完一個時間片，就出讓CPU（如阻塞）。

算法優(yōu)點：時間片輪轉調(diào)度算法的特點是簡單易行、平均響應時間短。

算法缺點：不利于處理緊急作業(yè)。在時間片輪轉算法中，時間片的大小對系統(tǒng)性能的影響很大，因此時間片的大小應選擇恰當
怎樣確定時間片的大小：

        時間片大小的確定
        1.系統(tǒng)對響應時間的要求
        2.就緒隊列中進程的數(shù)目

3.系統(tǒng)的處理能力

5.多級反饋隊列(Multilevel Feedback Queue)

多級反饋隊列調(diào)度算法是一種CPU處理機調(diào)度算法，UNIX操作系統(tǒng)采取的便是這種調(diào)度算法。

多級反饋隊列調(diào)度算法描述：

　　 1、進程在進入待調(diào)度的隊列等待時，首先進入優(yōu)先級最高的Q1等待。
　　 2、首先調(diào)度優(yōu)先級高的隊列中的進程。若高優(yōu)先級中隊列中已沒有調(diào)度的進程，則調(diào)度次優(yōu)先級隊列中的進程。例如：Q1,Q2,Q3三個隊列，只有在Q1中沒有進程等待時才去調(diào)度Q2，同理，只有Q1,Q2都為空時才會去調(diào)度Q3。
　　 3、對于同一個隊列中的各個進程，按照時間片輪轉法調(diào)度。比如Q1隊列的時間片為N，那么Q1中的作業(yè)在經(jīng)歷了N個時間片后若還沒有完成，則進入Q2隊列等待，若Q2的時間片用完后作業(yè)還不能完成，一直進入下一級隊列，直至完成。
　　 4、在低優(yōu)先級的隊列中的進程在運行時，又有新到達的作業(yè)，那么在運行完這個時間片后，CPU馬上分配給新到達的作業(yè)（搶占式）。
　　在多級反饋隊列調(diào)度算法中，如果規(guī)定第一個隊列的時間片略大于多數(shù)人機交互所需之處理時間時，便能夠較好的滿足各種類型用戶的需要。