Linux進程調(diào)度策略

linux內(nèi)核的三種主要調(diào)度策略：

1，SCHED_OTHER 分時調(diào)度策略，

2，SCHED_FIFO實時調(diào)度策略，先到先服務(wù)

3，SCHED_RR實時調(diào)度策略，時間片輪轉(zhuǎn)

實時進程將得到優(yōu)先調(diào)用，實時進程根據(jù)實時優(yōu)先級決定調(diào)度權(quán)值。分時進程則通過nice和counter值決定權(quán)值，nice越小，counter越大，被調(diào)度的概率越大，也就是曾經(jīng)使用了cpu最少的進程將會得到優(yōu)先調(diào)度。

SHCED_RR和SCHED_FIFO的不同：

當采用SHCED_RR策略的進程的時間片用完，系統(tǒng)將重新分配時間片，并置于就緒隊列尾。放在隊列尾保證了所有具有相同優(yōu)先級的RR任務(wù)的調(diào)度公平。

SCHED_FIFO一旦占用cpu則一直運行。一直運行直到有更高優(yōu)先級任務(wù)到達或自己放棄。

如果有相同優(yōu)先級的實時進程(根據(jù)優(yōu)先級計算的調(diào)度權(quán)值是一樣的)已經(jīng)準備好，F(xiàn)IFO時必須等待該進程主動放棄后才可以運行這個優(yōu)先級相同的任務(wù)。而RR可以讓每個任務(wù)都執(zhí)行一段時間。

相同點：

RR和FIFO都只用于實時任務(wù)。

創(chuàng)建時優(yōu)先級大于0(1-99)。

按照可搶占優(yōu)先級調(diào)度算法進行。

就緒態(tài)的實時任務(wù)立即搶占非實時任務(wù)。

所有任務(wù)都采用linux分時調(diào)度策略時：

1，創(chuàng)建任務(wù)指定采用分時調(diào)度策略，并指定優(yōu)先級nice值(-20~19)。

2，將根據(jù)每個任務(wù)的nice值確定在cpu上的執(zhí)行時間(counter)。

3，如果沒有等待資源，則將該任務(wù)加入到就緒隊列中。

4，調(diào)度程序遍歷就緒隊列中的任務(wù)，通過對每個任務(wù)動態(tài)優(yōu)先級的計算權(quán)值(counter+20-nice)結(jié)果，選擇計算結(jié)果最大的一個去運行，當這個時間片用完后(counter減至0)或者主動放棄cpu時，該任務(wù)將被放在就緒隊列末尾(時間片用完)或等待隊列(因等待資源而放棄cpu)中。

5，此時調(diào)度程序重復(fù)上面計算過程，轉(zhuǎn)到第4步。

6，當調(diào)度程序發(fā)現(xiàn)所有就緒任務(wù)計算所得的權(quán)值都為不大于0時，重復(fù)第2步。

所有任務(wù)都采用FIFO時：

1，創(chuàng)建進程時指定采用FIFO，并設(shè)置實時優(yōu)先級rt_priority(1-99)。

2，如果沒有等待資源，則將該任務(wù)加入到就緒隊列中。

3，調(diào)度程序遍歷就緒隊列，根據(jù)實時優(yōu)先級計算調(diào)度權(quán)值(1000+rt_priority),選擇權(quán)值最高的任務(wù)使用cpu，該FIFO任務(wù)將一直占有cpu直到有優(yōu)先級更高的任務(wù)就緒(即使優(yōu)先級相同也不行)或者主動放棄(等待資源)。

4，調(diào)度程序發(fā)現(xiàn)有優(yōu)先級更高的任務(wù)到達(高優(yōu)先級任務(wù)可能被中斷或定時器任務(wù)喚醒，再或被當前運行的任務(wù)喚醒，等等)，則調(diào)度程序立即在當前任務(wù)堆棧中保存當前cpu寄存器的所有數(shù)據(jù)，重新從高優(yōu)先級任務(wù)的堆棧中加載寄存器數(shù)據(jù)到cpu，此時高優(yōu)先級的任務(wù)開始運行。重復(fù)第3步。

5，如果當前任務(wù)因等待資源而主動放棄cpu使用權(quán)，則該任務(wù)將從就緒隊列中刪除，加入等待隊列，此時重復(fù)第3步。

所有任務(wù)都采用RR調(diào)度策略時：

1，創(chuàng)建任務(wù)時指定調(diào)度參數(shù)為RR，并設(shè)置任務(wù)的實時優(yōu)先級和nice值(nice值將會轉(zhuǎn)換為該任務(wù)的時間片的長度)。

2，如果沒有等待資源，則將該任務(wù)加入到就緒隊列中。

3，調(diào)度程序遍歷就緒隊列，根據(jù)實時優(yōu)先級計算調(diào)度權(quán)值(1000+rt_priority),選擇權(quán)值最高的任務(wù)使用cpu。

4，如果就緒隊列中的RR任務(wù)時間片為0，則會根據(jù)nice值設(shè)置該任務(wù)的時間片，同時將該任務(wù)放入就緒隊列的末尾。重復(fù)步驟3。

5，當前任務(wù)由于等待資源而主動退出cpu，則其加入等待隊列中。重復(fù)步驟3。

系統(tǒng)中既有分時調(diào)度，又有時間片輪轉(zhuǎn)調(diào)度和先進先出調(diào)度：

1，RR調(diào)度和FIFO調(diào)度的進程屬于實時進程，以分時調(diào)度的進程是非實時進程。

2，當實時進程準備就緒后，如果當前cpu正在運行非實時進程，則實時進程立即搶占非實時進程。

3，RR進程和FIFO進程都采用實時優(yōu)先級做為調(diào)度的權(quán)值標準，RR是FIFO的一個延伸。FIFO時，如果兩個進程的優(yōu)先級一樣，則這兩個優(yōu)先級一樣的進程具體執(zhí)行哪一個是由其在隊列中的未知決定的，這樣導致一些不公正性(優(yōu)先級是一樣的，為什么要讓你一直運行?),如果將兩個優(yōu)先級一樣的任務(wù)的調(diào)度策略都設(shè)為RR,則保證了這兩個任務(wù)可以循環(huán)執(zhí)行，保證了公平。

Ingo Molnar-實時補丁

為了能并入主流內(nèi)核，Ingo Molnar的實時補丁也采用了非常靈活的策略，它支持四種搶占模式：

1.No Forced Preemption (Server)，這種模式等同于沒有使能搶占選項的標準內(nèi)核，主要適用于科學計算等服務(wù)器環(huán)境。

2.Voluntary Kernel Preemption (Desktop)，這種模式使能了自愿搶占，但仍然失效搶占內(nèi)核選項，它通過增加搶占點縮減了搶占延遲，因此適用于一些需要較好的響應(yīng)性的環(huán)境，如桌面環(huán)境，當然這種好的響應(yīng)性是以犧牲一些吞吐率為代價的。

3.Preemptible Kernel (Low-Latency Desktop)，這種模式既包含了自愿搶占，又使能了可搶占內(nèi)核選項，因此有很好的響應(yīng)延遲，實際上在一定程度上已經(jīng)達到了軟實時性。它主要適用于桌面和一些嵌入式系統(tǒng)，但是吞吐率比模式2更低。

4.Complete Preemption (Real-Time)，這種模式使能了所有實時功能，因此完全能夠滿足軟實時需求，它適用于延遲要求為100微秒或稍低的實時系統(tǒng)。

實現(xiàn)實時是以犧牲系統(tǒng)的吞吐率為代價的，因此實時性越好，系統(tǒng)吞吐率就越低。