在了解Linux操作系統下的調度算法前，先來談談什麼是進程調度以及基本的進程調度算法。
▲進程調度：無論是在批處理系統還是分時系統中，用戶進程數一般都多於處理機數、這將導致它們互相爭奪處理機。另外，系統進程也同樣需要使用處理機。這就要求進程調度程序按一定的策略，動態地把處理機分配給處於就緒隊列中的某一個進程，以使之執行。▲進程調度具有四條基本屬性和三個基本狀態：
基本屬性------>1、多態性 從誕生、運行，直至消滅；2、多個不同的進程可以包括相同的程序；3、三種基本狀態 它們之間可進行轉換；4、並發性並發執行的進程輪流占用處理器。 基本狀態------>1、等待態：等待某個事件的完成； 2、就緒態：等待系統分配處理器以便運行；3、運行態：占有處理器正在運行。
搶占式（剝奪式）和非搶占式（非剝奪式）：非搶占式/非剝奪式：分派程序一旦把處理機分配給某進程後便讓它一直運行下去，直到進程完成或發生。
搶占式/剝奪式：當一個進程正在運行時，系統可以基於某種原則，剝奪已分配給它的處理機，將之分配給其它進程。剝奪原則有：優先權原則、短進程優先原則、時間片原則。
衡量進程調度性能的指標有：周轉時間、響應時間、CPU-I/O執行期。操作系統中基本的調度算法大致可分為六類：
⑴先到先服務算法（FCFS：firstcome first service）：如果早就緒的進程排在就緒隊列的前面，遲就緒的進程排在就緒隊列的後面，那麼該算法總是把當前處於就緒隊列之首的那個進程調度到運行狀態。也就說，它只考慮進程進入就緒隊列的先後，而不考慮它的下一個CPU周期的長短及其他因素。FCFS算法簡單易行，是一種非搶占式策略，但性能卻不大好。因為對於進程越長時越有利，且對於頻繁調用CPU的進程有利，而對於頻繁調用I/O接口的進程不利。
⑵短進程優先算法（SJF：Shortest Job First或SPN：ShortestProcess Next)：對預計執行時間短的進程優先分派處理機。通常後來的短進程不搶先正在執行的進程。其目標是減少平均周轉時間。該算法的優點在於比FCFS改善平均周轉時間和平均帶權周轉時間，縮短作業的等待時間；提高系統的吞吐量；但依然存在對長作業非常不利，可能長時間得不到執行；未能依據作業的緊迫程度來劃分執行的優先級；難以准確估計作業（進程）的執行時間，從而影響調度性能的缺點。
⑶時間片輪轉算法（RR：Round Robin）：該算法的特性是讓每個進程在就緒隊列中的等待時間與享受服務的時間成正比例。其過程：①將系統中所有的就緒進程按照FCFS原則，排成一個隊列；②每次調度時將CPU分派給隊首進程，讓其執行一個時間片。時間片的長度從幾個ms到幾百ms；③在一個時間片結束時，發生時鐘中斷；④調度程序據此暫停當前進程的執行，將其送到就緒隊列的末尾，並通過上下文切換執行當前的隊首進程；⑤進程可以未使用完一個時間片，就讓出CPU（如阻塞）。⑷多級反饋隊列算法(Round Robin with Multiple Feedback)：該算法是輪轉算法和優先級算法的綜合和發展。其過程：①設置多個就緒隊列，分別賦予不同的優先級，如逐級降低，隊列1的優先級最高。每個隊列執行時間片的長度也不同，規定優先級越低則時間片越長，如逐級加倍；②新進程進入內存後，先投入隊列1的末尾，按FCFS算法調度；若按隊列1一個時間片未能執行完，則降低投入到隊列2的末尾，同樣按FCFS算法調度；如此下去，降低到最後的隊列，則按“時間片輪轉”算法調度直到完成；③僅當較高優先級的隊列為空，才調度較低優先級的隊列中的進程執行。如果進程執行時有新進程進入較高優先級的隊列，則搶先執行新進程，並把被搶先的進程投入原隊列的末尾。該算法擁有①為提高系統吞吐量和縮短平均周轉時間而照顧短進程；②獲得較好的I/O設備利用率和縮短響應時間而照顧I/O型進程；③不必估計進程的執行時間，動態調節的優點。
⑸優先級算法（Priority Scheduling）：該算法是多級隊列算法的改進，平衡各進程對響應時間的要求。適用於作業調度和進程調度，可分成搶先式和非搶先式。該算法分為靜態優先級和動態優先級。⑹最高響應比優先法(HRN，Highest Response_ratio Next)：該算法是對FCFS方式和SJF方式的一種綜合平衡。FCFS方式只考慮每個作業的等待時間而未考慮執行時間的長短，而SJF方式只考慮執行時間而未考慮等待時間的長短。因此，這兩種調度算法在某些極端情況下會帶來某些不便。HRN調度策略同時考慮每個作業的等待時間長短和估計需要的執行時間長短，從中選出響應比最高的作業投入執行。
響應比R定義如下： R =(W+T)/T = 1+W/T其中T為該作業估計需要的執行時間，W為作業在後備狀態隊列中的等待時間。每當要進行作業調度時，系統計算每個作業的響應比，選擇其中R最大者投入執行。這樣，即使是長作業，隨著它等待時間的增加，W / T也就隨著增加，也就有機會獲得調度執行。這種算法是介於FCFS和SJF之間的一種折中算法。由於長作業也有機會投入運行，在同一時間內處理的作業數顯然要少於SJF法，從而采用HRN方式時其吞吐量將小於采用SJF
法時的吞吐量。另外，由於每次調度前要計算響應比，系統開銷也要相應增加。
⑴policy是進程的調度策略，用來區分實時進程和普通進程，實時進程優先於普通進程運行；
⑵priority是進程(包括實時和普通)的靜態優先級；
⑶counter是進程剩余的時間片，它的起始值就是priority的值；由於counter在後面計算一個處於可運行狀態的進程值得運行的程度goodness時起重要作用，因此，counter也可以看作是進程的動態優先。
⑷rt_priority是實時進程特有的，用於實時進程間的選擇。
Linux系統中的進程調度策略主要分為三種：1、SCHED_OTHER 分時調度策略；
2、SCHED_FIFO實時調度策略，先到先服務；3、SCHED_RR實時調度策略，時間片輪轉。
實時進程將得到優先調用，實時進程根據實時優先級決定調度權值，分時進程則通過nice和counter值決定權值，nice越小，counter越大，被調度的概率越大，也就是曾經使用了cpu最少的進程將會得到優先調度。
SHCED_RR和SCHED_FIFO的不同：當采用SHCED_RR策略的進程的時間片用完，系統將重新分配時間片，並置於就緒隊列尾。放在隊列尾保證了所有具有相同優先級的RR任務的調度公平。SCHED_FIFO一旦占用cpu則一直運行。一直運行直到有更高優先級任務到達或自己放棄。
如果有相同優先級的實時進程（根據優先級計算的調度權值是一樣的）已經准備好，FIFO時必須等待該進程主動放棄後才可以運行這個優先級相同的任務。而RR可以讓每個任務都執行一段時間。
