先來(lái)先服務(wù) （FCFS，first come first served）

在所有調(diào)度算法中，最簡(jiǎn)單的是非搶占式的FCFS算法。
算法原理：進(jìn)程按照它們請(qǐng)求CPU的順序使用CPU.就像你買東西去排隊(duì)，誰(shuí)第一個(gè)排，誰(shuí)就先被執(zhí)行，在它執(zhí)行的過(guò)程中，不會(huì)中斷它。當(dāng)其他人也想進(jìn)入內(nèi)存被執(zhí)行，就要排隊(duì)等著，如果在執(zhí)行過(guò)程中出現(xiàn)一些事，他現(xiàn)在不想排隊(duì)了，下一個(gè)排隊(duì)的就補(bǔ)上。此時(shí)如果他又想排隊(duì)了，只能站到隊(duì)尾去。
算法優(yōu)點(diǎn)：易于理解且實(shí)現(xiàn)簡(jiǎn)單，只需要一個(gè)隊(duì)列(FIFO)，且相當(dāng)公平
算法缺點(diǎn)：比較有利于長(zhǎng)進(jìn)程，而不利于短進(jìn)程，有利于CPU 繁忙的進(jìn)程，而不利于I/O 繁忙的進(jìn)程

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

短作業(yè)優(yōu)先（SJF, Shortest Job First）又稱為“短進(jìn)程優(yōu)先”SPN(Shortest Process Next)；這是對(duì)FCFS算法的改進(jìn)，其目標(biāo)是減少平均周轉(zhuǎn)時(shí)間。
算法原理：對(duì)預(yù)計(jì)執(zhí)行時(shí)間短的進(jìn)程優(yōu)先分派處理機(jī)。通常后來(lái)的短進(jìn)程不搶先正在執(zhí)行的進(jìn)程。
算法優(yōu)點(diǎn)：相比FCFS 算法，該算法可改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，縮短進(jìn)程的等待時(shí)間，提高系統(tǒng)的吞吐量。
算法缺點(diǎn)：對(duì)長(zhǎng)進(jìn)程非常不利，可能長(zhǎng)時(shí)間得不到執(zhí)行，且未能依據(jù)進(jìn)程的緊迫程度來(lái)劃分執(zhí)行的優(yōu)先級(jí)，以及難以準(zhǔn)確估計(jì)進(jìn)程的執(zhí)行時(shí)間，從而影響調(diào)度性能。

最高響應(yīng)比優(yōu)先法(HRRN，Highest Response Ratio Next)

最高響應(yīng)比優(yōu)先法(HRRN，Highest Response Ratio Next)是對(duì)FCFS方式和SJF方式的一種綜合平衡。FCFS方式只考慮每個(gè)作業(yè)的等待時(shí)間而未考慮執(zhí)行時(shí)間的長(zhǎng)短，而SJF方式只考慮執(zhí)行時(shí)間而未考慮等待時(shí)間的長(zhǎng)短。因此，這兩種調(diào)度算法在某些極端情況下會(huì)帶來(lái)某些不便。HRN調(diào)度策略同時(shí)考慮每個(gè)作業(yè)的等待時(shí)間長(zhǎng)短和估計(jì)需要的執(zhí)行時(shí)間長(zhǎng)短，從中選出響應(yīng)比最高的作業(yè)投入執(zhí)行。這樣，即使是長(zhǎng)作業(yè)，隨著它等待時(shí)間的增加，W / T也就隨著增加，也就有機(jī)會(huì)獲得調(diào)度執(zhí)行。這種算法是介于FCFS和SJF之間的一種折中算法。
算法原理：響應(yīng)比R定義如下： R =(W+T)/T = 1+W/T
其中T為該作業(yè)估計(jì)需要的執(zhí)行時(shí)間，W為作業(yè)在后備狀態(tài)隊(duì)列中的等待時(shí)間。每當(dāng)要進(jìn)行作業(yè)調(diào)度時(shí)，系統(tǒng)計(jì)算每個(gè)作業(yè)的響應(yīng)比，選擇其中R最大者投入執(zhí)行。
算法優(yōu)點(diǎn)：由于長(zhǎng)作業(yè)也有機(jī)會(huì)投入運(yùn)行，在同一時(shí)間內(nèi)處理的作業(yè)數(shù)顯然要少于SJF法，從而采用HRRN方式時(shí)其吞吐量將小于采用SJF 法時(shí)的吞吐量。
算法缺點(diǎn)：由于每次調(diào)度前要計(jì)算響應(yīng)比，系統(tǒng)開銷也要相應(yīng)增加。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個(gè)人覺(jué)得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)? ??

時(shí)間片輪轉(zhuǎn)算法（RR，Round-Robin）

該算法采用剝奪策略。時(shí)間片輪轉(zhuǎn)調(diào)度是一種最古老，最簡(jiǎn)單，最公平且使用最廣的算法，又稱RR調(diào)度。每個(gè)進(jìn)程被分配一個(gè)時(shí)間段，稱作它的時(shí)間片，即該進(jìn)程允許運(yùn)行的時(shí)間。
算法原理：讓就緒進(jìn)程以FCFS 的方式按時(shí)間片輪流使用CPU 的調(diào)度方式，即將系統(tǒng)中所有的就緒進(jìn)程按照FCFS 原則，排成一個(gè)隊(duì)列，每次調(diào)度時(shí)將CPU 分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片，時(shí)間片的長(zhǎng)度從幾個(gè)ms 到幾百ms。在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷，調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，并通過(guò)上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程，進(jìn)程可以未使用完一個(gè)時(shí)間片，就出讓CPU（如阻塞）。
算法優(yōu)點(diǎn)：時(shí)間片輪轉(zhuǎn)調(diào)度算法的特點(diǎn)是簡(jiǎn)單易行、平均響應(yīng)時(shí)間短。
算法缺點(diǎn)：不利于處理緊急作業(yè)。在時(shí)間片輪轉(zhuǎn)算法中，時(shí)間片的大小對(duì)系統(tǒng)性能的影響很大，因此時(shí)間片的大小應(yīng)選擇恰當(dāng)
怎樣確定時(shí)間片的大?。?/p>

時(shí)間片大小的確定

1.系統(tǒng)對(duì)響應(yīng)時(shí)間的要求
2.就緒隊(duì)列中進(jìn)程的數(shù)目
3.系統(tǒng)的處理能力

多級(jí)反饋隊(duì)列(Multilevel Feedback Queue)

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

原文作者：ShawnLeex