linux的調度演算法

1. linux系統的進程調度

Linux進程調度

1．調度方式

Linux系統的調度方式基本上採用「 搶占式優先順序 」方式，當進程在用戶模式下運行時，不管它是否自願，核心在一定條件下（如該進程的時間片用完或等待I/O）可以暫時中止其運行，而調度其他進程運行。一旦進程切換到內核模式下運行時，就不受以上限制，而一直運行下去，僅在重新回到用戶模式之前才會發生進程調度。

Linux系統中的調度基本上繼承了UNIX系統的 以優先順序為基礎 的調度。也就是說，核心為系統中每個進程計算出一個優先順序，該優先順序反映了一個進程獲得CPU使用權的資格，即高優先順序的進程優先得到運行。核心從進程就緒隊列中挑選一個優先順序最高的進程，為其分配一個CPU時間片，令其投入運行。在運行過程中，當前進程的優先順序隨時間遞減，這樣就實現了「負反饋」作用，即經過一段時間之後，原來級別較低的進程就相對「提升」了級別，從而有機會得到運行。當所有進程的優先順序都變為0（最低）時，就重新計算一次所有進程的優先順序。

2．調度策略

Linux系統針對不同類別的進程提供了3種不同的調度策略，即SCHED_FIFO、SCHED_RR及SCHED_OTHER。其中，SCHED_FIFO適合於 短實時進程 ，它們對時間性要求比較強，而每次運行所需的時間比較短。一旦這種進程被調度且開始運行，就一直運行到自願讓出CPU或被優先順序更高的進程搶占其執行權為止。

SCHED_RR對應「時間片輪轉法」，適合於每次運行需要 較長時間的實時進程 。一個運行進程分配一個時間片（200 ms），當時間片用完後，CPU被另外進程搶占，而該進程被送回相同優先順序隊列的末尾，核心動態調整用戶態進程的優先順序。這樣，一個進程從創建到完成任務後終止，需要經歷多次反饋循環。當進程再次被調度運行時，它就從上次斷點處開始繼續執行。

SCHED_OTHER是傳統的UNIX調度策略，適合於互動式的 分時進程 。這類進程的優先順序取決於兩個因素：一個是進程剩餘時間配額，如果進程用完了配給的時間，則相應優先順序降到0；另一個是進程的優先數nice，這是從UNIX系統沿襲下來的方法，優先數越小，其優先順序越高。nice的取值范圍是-20 19。用戶可以利用nice命令設定進程的nice值。但一般用戶只能設定正值，從而主動降低其優先順序；只有特權用戶才能把nice的值設置為負數。進程的優先順序就是以上二者之和。

後台命令對應後台進程（又稱後台作業）。後台進程的優先順序低於任何交互（前台）進程的優先順序。所以，只有當系統中當前不存在可運行的交互進程時，才調度後台進程運行。後台進程往往按批處理方式調度運行。

3．調度時機

核心進行進程調度的時機有以下5種情況：

（1）當前進程調用系統調用nanosleep( )或者pause( )，使自己進入睡眠狀態，主動讓出一段時間的CPU的使用權。

（2）進程終止，永久地放棄對CPU的使用。

（3）在時鍾中斷處理程序執行過程中，發現當前進程連續運行的時間過長。

（4）當喚醒一個睡眠進程時，發現被喚醒的進程比當前進程更有資格運行。

（5）一個進程通過執行系統調用來改變調度策略或者降低自身的優先順序（如nice命令），從而引起立即調度。

4．調度演算法

進程調度的演算法應該比較簡單，以便減少頻繁調度時的系統開銷。Linux執行進程調度時，首先查找所有在就緒隊列中的進程，從中選出優先順序最高且在內存的一個進程。如果隊列中有實時進程，那麼實時進程將優先運行。如果最需要運行的進程不是當前進程，那麼當前進程就被掛起，並且保存它的現場—— 所涉及的一切機器狀態，包括程序計數器和CPU寄存器等，然後為選中的進程恢復運行現場。

（二）Linux常用調度命令

· nohup命令

nohup命令的功能是以忽略掛起和退出的方式執行指定的命令。其命令格式是：

nohupcommand［arguments］

其中，command是所要執行的命令，arguments是指定命令的參數。

nohup命令告訴系統，command所代表的命令在執行過程中不受任何結束運行的信號（hangup和quit）的影響。例如，

$ nohup find / -name exam.txt -print>f1 &

find命令在後台運行。在用戶注銷後，它會繼續運行：從根目錄開始，查找名字是exam.txt的文件，結果被定向到文件f1中。

如果用戶沒有對輸出進行重定向，則輸出被附加到當前目錄的nohup.out文件中。如果用戶在當前目錄中不具備寫許可權，則輸出被定向到$HOME/nohup.out 中。

· at命令

at命令允許指定命令執行的時間。at命令的常用形式是：

attimecommand

其中，time是指定命令command在將來執行時的時間和日期。時間的指定方法有多種，用戶可以使用絕對時間，也可以用相對時間。該指定命令將以作業形式在後台運行。例如：

$ at 15:00 Oct 20

回車後進入接收方式，接著鍵入以下命令：

mail -s "Happy Birthday!" liuzheny

按下D鍵，屏幕顯示：

job 862960800.a at Wed Oct 20 15:00:00 CST 1999

$

表明建立了一個作業，其作業ID號是862960800.a，運行作業的時間是1999年10月20日下午3:00，給liuzheny發一條標題為「Happy Birthday！」（生日快樂）的空白郵件。

利用 at-l 可以列出當前at隊列中所有的作業。

利用 at-r 可以刪除指定的作業。這些作業以前由at或batch命令調度。例如，

at-r862960797.a

將刪除作業ID號是862960797.a的作業。其一般使用形式是：

at-rjob_id

注意，結尾是.a的作業ID號，表示這個作業是由at命令提交的；結尾是.b的作業ID號，表示這個作業是由batch命令提交的。

· batch命令

batch命令不帶任何參數，它提交的作業的優先順序比at命令提交的作業的優先順序低。batch無法指定作業運行的時間。實際運行時間要看系統中已經提交的作業數量。如果系統中優先順序較高的作業比較多，那麼，batch提交的作業則需要等待；如果系統空閑，則運行batch提交的作業。例如，

$ batch

回車後進入接收方式，接著鍵入命令：

find / -name exam.txt -print

按下D。退出接收方式，屏幕顯示：

job 862961540.b at Thu Nov 18 14:30:00 CST 1999

表示find命令被batch作為一個作業提交給系統，作業ID號是862961540.b。如果系統當前空閑，這個作業被立即執行，其結果同樣作為郵件發送給用戶。

· jobs命令

jobs命令用來顯示當前shell下正在運行哪些作業（即後台作業）。例如：

$ jobs

[2] + Running tar tv3 *&

[1] - Running find / -name README -print > logfile &

$

其中，第一列方括弧中的數字表示作業序號，它是由當前運行的shell分配的，而不是由操作系統統一分配的。在當前shell環境下，第一個後台作業的作業號為1，第二個作業的作業號為2，等等。

第二列中的「 」號表示相應作業的優先順序比「－」號對應作業的優先順序高。

第三列表明作業狀態，是否為運行、中斷、等待輸入或停止等。

最後列出的是創建當前這個作業所對應的命令行。

利用 jobs-l 形式，可以在作業號後顯示出相應進程的PID。如果想只顯示相應進程的PID，不顯示其它信息，則使用 jobs-p 形式。

· fg命令

fg命令把指定的後台作業移到前台。其使用格式是：

fg [job…]

其中，參數job是一個或多個進程的PID，或者是命令名稱或者作業號（前面要帶有一個「%」號）。例如：

$ jobs

[2] + Running tar tv3 *&

[1] - Running find / -name README -print > logfile&

$ fg %find

find / -name README -print > logfile

注意，顯示的命令行末尾沒有「&」符號。下面命令能產生同樣的效果：

$ fg %1

這樣，find命令對應的進程就在前台執行。當後台只有一個作業時，鍵入不帶參數的fg命令，就能使相應進程移到前台。當有兩個或更多的後台作業時，鍵入不帶參數的fg，就把最後進入後台的進程首先移到前台。

· bg命令

bg命令可以把前台進程換到後台執行。其使用格式是：

bg [job…]

其中，job是一個或多個進程的PID、命令名稱或者作業號，在參數前要帶「%」號。例如，在cc（C編譯命令）命令執行過程中，按下Z鍵，使這個作業掛起。然後鍵入以下命令：

$ bg %cc

該掛起的作業在後台重新開始執行。

2. Linux - 進程調度

進程調度演算法也稱 CPU 調度演算法，畢竟進程是由 CPU 調度的。

當 CPU 空閑時，操作系統就選擇內存中的某個「就緒狀態」的進程，並給其分配 CPU。

什麼時候會發生 CPU 調度呢？通常有以下情況：

其中發生在 1 和 4 兩種情況下的調度稱為「非搶占式調度」，2 和 3 兩種情況下發生的調度稱為「搶占式調度」。

非搶占式的意思就是，當進程正在運行時，它就會一直運行，直到該進程完成或發生某個事件而被阻塞時，才會把 CPU 讓給其他進程。

而搶占式調度，顧名思義就是進程正在運行的時候，可以被打斷，使其把 CPU 讓給其他進程。那搶占的原則一般有三種，分別是時間片原則、優先權原則、短作業優先原則。

你可能會好奇為什麼第 3 種情況也會發生 CPU 調度呢？假設有一個進程是處於等待狀態的，但是它的優先順序比較高，如果該進程等待的事件發生了，它就會轉到就緒狀態，一旦它轉到就緒狀態，如果我們的調度演算法是以優先順序來進行調度的，那麼它就會立馬搶占正在運行的進程，所以這個時候就會發生 CPU 調度。

那第 2 種狀態通常是時間片到的情況，因為時間片到了就會發生中斷，於是就會搶占正在運行的進程，從而佔用 CPU。

調度演算法影響的是等待時間（進程在就緒隊列中等待調度的時間總和），而不能影響進程真在使用 CPU 的時間和 I/O 時間。

最簡單的一個調度演算法，就是非搶占式的先來先服務（First Come First Severd, FCFS）演算法了。

顧名思義，先來後到，每次從就緒隊列選擇最先進入隊列的進程，然後一直運行，直到進程退出或被阻塞，才會繼續從隊列中選擇第一個進程接著運行。

這似乎很公平，但是當一個長作業先運行了，那麼後面的短作業等待的時間就會很長，不利於短作業。

FCFS 對長作業有利，適用於 CPU 繁忙型作業的系統，而不適用於 I/O 繁忙型作業的系統。

最短作業優先（Shortest Job First, SJF）調度演算法同樣也是顧名思義，它會優先選擇運行時間最短的進程來運行，這有助於提高系統的吞吐量。

這顯然對長作業不利，很容易造成一種極端現象。

比如，一個長作業在就緒隊列等待運行，而這個就緒隊列有非常多的短作業，那麼就會使得長作業不斷的往後推，周轉時間變長，致使長作業長期不會被運行。

前面的「先來先服務調度演算法」和「最短作業優先調度演算法」都沒有很好的權衡短作業和長作業。

那麼，高響應比優先 （Highest Response Ratio Next, HRRN）調度演算法主要是權衡了短作業和長作業。

每次進行進程調度時，先計算「響應比優先順序」，然後把「響應比優先順序」最高的進程投入運行，「響應比優先順序」的計算公式：

從上面的公式，可以發現：

最古老、最簡單、最公平且使用最廣的演算法就是時間片輪轉（Round Robin, RR）調度演算法。

每個進程被分配一個時間段，稱為時間片（Quantum），即允許該進程在該時間段中運行。

另外，時間片的長度就是一個很關鍵的點：

通常時間片設為 20ms~50ms 通常是一個比較合理的折中值。

前面的「時間片輪轉演算法」做了個假設，即讓所有的進程同等重要，也不偏袒誰，大家的運行時間都一樣。

但是，對於多用戶計算機系統就有不同的看法了，它們希望調度是有優先順序的，即希望調度程序能從就緒隊列中選擇最高優先順序的進程進行運行，這稱為最高優先順序（Highest Priority First，HPF）調度演算法。

進程的優先順序可以分為，靜態優先順序或動態優先順序：

該演算法也有兩種處理優先順序高的方法，非搶占式和搶占式：

但是依然有缺點，可能會導致低優先順序的進程永遠不會運行。

多級反饋隊列（Multilevel Feedback Queue）調度演算法是「時間片輪轉演算法」和「最高優先順序演算法」的綜合和發展。

顧名思義：

工作原理：

設置了多個隊列，賦予每個隊列不同的優先順序，每個隊列優先順序從高到低，同時優先順序越高時間片越短；

新的進程會被放入到第一級隊列的末尾，按先來先服務的原則排隊等待被調度，如果在第一級隊列規定的時間片沒運行完成，則將其轉入到第二級隊列的末尾，以此類推，直至完成；

當較高優先順序的隊列為空，才調度較低優先順序的隊列中的進程運行。如果進程運行時，有新進程進入較高優先順序的隊列，則停止當前運行的進程並將其移入到原隊列末尾，接著讓較高優先順序的進程運行；

可以發現，對於短作業可能可以在第一級隊列很快被處理完。對於長作業，如果在第一級隊列處理不完，可以移入下次隊列等待被執行，雖然等待的時間變長了，但是運行時間也會更長了，所以該演算法很好的兼顧了長短作業，同時有較好的響應時間。

整體架構如下，即調度策略是模塊化設計的，調度器根據不同的進程依次遍歷不同的調度策略，找到進程對應的調度策略，調度的結果即為選出一個可運行的進程指針，並將其加入到進程可運行隊列中。

以一棵紅黑樹管理所有需要調度的進程，
紅黑樹，左邊節點小於右邊節點的值，運行到目前為止vruntime最小的進程，同時考慮了CPU/IO和nice，總是找vruntime最小的線程調度。
vruntime = pruntime/weight × 1024;
vruntime是虛擬運行時間，pruntime是物理運行時間，weight權重由nice值決定(nice越低權重越高)，則運行時間少、nice值低的的線程vruntime小，將得到優先調度。這是一個隨運行而動態變化的過程。

3. linux io調度演算法都有哪些

I/O調度的4種演算法
1)CFQ(完全公平排隊I/O調度程序)
特點:
在最新的內核版本和發行版中,都選擇CFQ做為默認的I/O調度器,對於通用的伺服器也是最好的選擇.
CFQ試圖均勻地分布對I/O帶寬的訪問,避免進程被餓死並實現較低的延遲,是deadline和as調度器的折中.
CFQ對於多媒體應用(video,audio)和桌面系統是最好的選擇.
CFQ賦予I/O請求一個優先順序,而I/O優先順序請求獨立於進程優先順序,高優先順序的進程的讀寫不能自動地繼承高的I/O優先順序.

工作原理:
CFQ為每個進程/線程,單獨創建一個隊列來管理該進程所產生的請求,也就是說每個進程一個隊列,各隊列之間的調度使用時間片來調度,
以此來保證每個進程都能被很好的分配到I/O帶寬.I/O調度器每次執行一個進程的4次請求.

2)NOOP(電梯式調度程序)
特點:
在Linux2.4或更早的版本的調度程序,那時只有這一種I/O調度演算法.
NOOP實現了一個簡單的FIFO隊列,它像電梯的工作主法一樣對I/O請求進行組織,當有一個新的請求到來時,它將請求合並到最近的請求之後,以此來保證請求同一介質.
NOOP傾向餓死讀而利於寫.
NOOP對於快閃記憶體設備,RAM,嵌入式系統是最好的選擇.
電梯演算法餓死讀請求的解釋:
因為寫請求比讀請求更容易.
寫請求通過文件系統cache,不需要等一次寫完成,就可以開始下一次寫操作,寫請求通過合並,堆積到I/O隊列中.
讀請求需要等到它前面所有的讀操作完成,才能進行下一次讀操作.在讀操作之間有幾毫秒時間,而寫請求在這之間就到來,餓死了後面的讀請求.
3)Deadline(截止時間調度程序)
特點:
通過時間以及硬碟區域進行分類,這個分類和合並要求類似於noop的調度程序.
Deadline確保了在一個截止時間內服務請求,這個截止時間是可調整的,而默認讀期限短於寫期限.這樣就防止了寫操作因為不能被讀取而餓死的現象.
Deadline對資料庫環境(ORACLE RAC,MYSQL等)是最好的選擇.

4)AS(預料I/O調度程序)
特點:
本質上與Deadline一樣,但在最後一次讀操作後,要等待6ms,才能繼續進行對其它I/O請求進行調度.
可以從應用程序中預訂一個新的讀請求,改進讀操作的執行,但以一些寫操作為代價.
它會在每個6ms中插入新的I/O操作,而會將一些小寫入流合並成一個大寫入流,用寫入延時換取最大的寫入吞吐量.
AS適合於寫入較多的環境,比如文件伺服器
AS對資料庫環境表現很差.

4. 關於linux的調度演算法

Linux2.6
版本的
Linux
內核使用了新的調度器演算法，它是由
Ingo
Molnar開發的
O（1）調度器演算法。它在高負載的情況下極其出色，並且對處理器調度有很好的擴展。
Linux2.4
版本的標准調度器中，使用時間片重算的演算法。這種演算法要求在所有的進程都用盡時間片以後，重新計算下一次運行的時間片。這樣每次任務調度的花銷不確定，可能因為計算比較復雜，產生較大調度延遲。特別是多處理器系統，可能由於調度的延遲，導致大部分處理器處於空閑
狀態，影響系統性能。
新的調度器採用
O（1）的調度演算法，通過優先順序數組的數據結構來實現。優先順序數組可以使每個優先順序都有相應的任務隊列，還有一個優先順序點陣圖，每個優先順序對應點陣圖中一位，通過點陣圖可快速執行最高優先順序任務。因優先順序個數是固定的，所以查找的時間也固定，不受運行任務數的影響。
新的調度器為每個處理器維護
2
個優先順序數組：有效數組和過期數組。有效數組內任務隊列的進程都還有可以運行的時間片；過期數組內任務隊列的進程都沒有時間片可以執行。當一個進程的時間片用光時，就把它從有效數組移到過期數組，並且時間片也已經重新計算好了。當需要重新調度這些任務的時候，只要在有效數組和過期數組之間切換就好了。這種交換是O（1）演算法的核心。
關於該演算法的更多內容，google
一下！

5. linux環境下的進程調度演算法有哪些

第一部分： 實時調度演算法介紹

對於什麼是實時系統，POSIX 1003.b作了這樣的定義：指系統能夠在限定的響應時間內提供所需水平的服務。而一個由Donald Gillies提出的更加為大家接受的定義是：一個實時系統是指計算的正確性不僅取決於程序的邏輯正確性，也取決於結果產生的時間，如果系統的時間約束條件得不到滿足，將會發生系統出錯。

實時系統根據其對於實時性要求的不同，可以分為軟實時和硬實時兩種類型。硬實時系統指系統要有確保的最壞情況下的服務時間，即對於事件的響應時間的截止期限是無論如何都必須得到滿足。比如航天中的宇宙飛船的控制等就是現實中這樣的系統。其他的所有有實時特性的系統都可以稱之為軟實時系統。如果明確地來說，軟實時系統就是那些從統計的角度來說，一個任務（在下面的論述中，我們將對任務和進程不作區分）能夠得到有確保的處理時間，到達系統的事件也能夠在截止期限到來之前得到處理，但違反截止期限並不會帶來致命的錯誤，像實時多媒體系統就是一種軟實時系統。

一個計算機系統為了提供對於實時性的支持，它的操作系統必須對於CPU和其他資源進行有效的調度和管理。在多任務實時系統中，資源的調度和管理更加復雜。本文下面將先從分類的角度對各種實時任務調度演算法進行討論，然後研究普通的 Linux操作系統的進程調度以及各種實時Linux系統為了支持實時特性對普通Linux系統所做的改進。最後分析了將Linux操作系統應用於實時領域中時所出現的一些問題，並總結了各種實時Linux是如何解決這些問題的。

1. 實時CPU調度演算法分類

各種實時操作系統的實時調度演算法可以分為如下三種類別[Wang99][Gopalan01]：基於優先順序的調度演算法（Priority-driven scheling-PD）、基於CPU使用比例的共享式的調度演算法（Share-driven scheling-SD）、以及基於時間的進程調度演算法（Time-driven scheling-TD），下面對這三種調度演算法逐一進行介紹。

1.1. 基於優先順序的調度演算法

基於優先順序的調度演算法給每個進程分配一個優先順序，在每次進程調度時，調度器總是調度那個具有最高優先順序的任務來執行。根據不同的優先順序分配方法，基於優先順序的調度演算法可以分為如下兩種類型[Krishna01][Wang99]：

靜態優先順序調度演算法：

這種調度演算法給那些系統中得到運行的所有進程都靜態地分配一個優先順序。靜態優先順序的分配可以根據應用的屬性來進行，比如任務的周期，用戶優先順序，或者其它的預先確定的策略。RM（Rate-Monotonic）調度演算法是一種典型的靜態優先順序調度演算法，它根據任務的執行周期的長短來決定調度優先順序，那些具有小的執行周期的任務具有較高的優先順序。

動態優先順序調度演算法：

這種調度演算法根據任務的資源需求來動態地分配任務的優先順序，其目的就是在資源分配和調度時有更大的靈活性。非實時系統中就有很多這種調度演算法，比如短作業優先的調度演算法。在實時調度演算法中， EDF演算法是使用最多的一種動態優先順序調度演算法，該演算法給就緒隊列中的各個任務根據它們的截止期限（Deadline）來分配優先順序，具有最近的截止期限的任務具有最高的優先順序。

1.2. 基於比例共享調度演算法

雖然基於優先順序的調度演算法簡單而有效，但這種調度演算法提供的是一種硬實時的調度，在很多情況下並不適合使用這種調度演算法：比如象實時多媒體會議系統這樣的軟實時應用。對於這種軟實時應用，使用一種比例共享式的資源調度演算法（SD演算法）更為適合。

比例共享調度演算法指基於CPU使用比例的共享式的調度演算法，其基本思想就是按照一定的權重（比例）對一組需要調度的任務進行調度，讓它們的執行時間與它們的權重完全成正比。

我們可以通過兩種方法來實現比例共享調度演算法[Nieh01]：第一種方法是調節各個就緒進程出現在調度隊列隊首的頻率，並調度隊首的進程執行；第二種做法就是逐次調度就緒隊列中的各個進程投入運行，但根據分配的權重調節分配個每個進程的運行時間片。

比例共享調度演算法可以分為以下幾個類別：輪轉法、公平共享、公平隊列、彩票調度法（Lottery）等。

比例共享調度演算法的一個問題就是它沒有定義任何優先順序的概念；所有的任務都根據它們申請的比例共享CPU資源，當系統處於過載狀態時，所有的任務的執行都會按比例地變慢。所以為了保證系統中實時進程能夠獲得一定的CPU處理時間，一般採用一種動態調節進程權重的方法。

1.3. 基於時間的進程調度演算法

對於那些具有穩定、已知輸入的簡單系統，可以使用時間驅動（Time-driven:TD）的調度演算法，它能夠為數據處理提供很好的預測性。這種調度演算法本質上是一種設計時就確定下來的離線的靜態調度方法。在系統的設計階段，在明確系統中所有的處理情況下，對於各個任務的開始、切換、以及結束時間等就事先做出明確的安排和設計。這種調度演算法適合於那些很小的嵌入式系統、自控系統、感測器等應用環境。

這種調度演算法的優點是任務的執行有很好的可預測性，但最大的缺點是缺乏靈活性，並且會出現有任務需要被執行而CPU卻保持空閑的情況。

2. 通用Linux系統中的CPU調度

通用Linux系統支持實時和非實時兩種進程，實時進程相對於普通進程具有絕對的優先順序。對應地，實時進程採用SCHED_FIFO或者SCHED_RR調度策略，普通的進程採用SCHED_OTHER調度策略。

在調度演算法的實現上，Linux中的每個任務有四個與調度相關的參數，它們是rt_priority、policy、priority（nice）、counter。調度程序根據這四個參數進行進程調度。

在SCHED_OTHER 調度策略中，調度器總是選擇那個priority+counter值最大的進程來調度執行。從邏輯上分析，SCHED_OTHER調度策略存在著調度周期（epoch），在每一個調度周期中，一個進程的priority和counter值的大小影響了當前時刻應該調度哪一個進程來執行，其中 priority是一個固定不變的值，在進程創建時就已經確定，它代表了該進程的優先順序，也代表這該進程在每一個調度周期中能夠得到的時間片的多少； counter是一個動態變化的值，它反映了一個進程在當前的調度周期中還剩下的時間片。在每一個調度周期的開始，priority的值被賦給 counter，然後每次該進程被調度執行時，counter值都減少。當counter值為零時，該進程用完自己在本調度周期中的時間片，不再參與本調度周期的進程調度。當所有進程的時間片都用完時，一個調度周期結束，然後周而復始。另外可以看出Linux系統中的調度周期不是靜態的，它是一個動態變化的量，比如處於可運行狀態的進程的多少和它們priority值都可以影響一個epoch的長短。值得注意的一點是，在2.4以上的內核中， priority被nice所取代，但二者作用類似。

可見SCHED_OTHER調度策略本質上是一種比例共享的調度策略，它的這種設計方法能夠保證進程調度時的公平性--一個低優先順序的進程在每一個epoch中也會得到自己應得的那些CPU執行時間，另外它也提供了不同進程的優先順序區分，具有高priority值的進程能夠獲得更多的執行時間。

對於實時進程來說，它們使用的是基於實時優先順序rt_priority的優先順序調度策略，但根據不同的調度策略，同一實時優先順序的進程之間的調度方法有所不同：

SCHED_FIFO：不同的進程根據靜態優先順序進行排隊，然後在同一優先順序的隊列中，誰先准備好運行就先調度誰，並且正在運行的進程不會被終止直到以下情況發生：1.被有更高優先順序的進程所強佔CPU；2.自己因為資源請求而阻塞；3.自己主動放棄CPU（調用sched_yield）；

SCHED_RR：這種調度策略跟上面的SCHED_FIFO一模一樣，除了它給每個進程分配一個時間片，時間片到了正在執行的進程就放棄執行；時間片的長度可以通過sched_rr_get_interval調用得到；

由於Linux系統本身是一個面向桌面的系統，所以將它應用於實時應用中時存在如下的一些問題：

Linux系統中的調度單位為10ms，所以它不能夠提供精確的定時；

當一個進程調用系統調用進入內核態運行時，它是不可被搶占的；

Linux內核實現中使用了大量的封中斷操作會造成中斷的丟失；

由於使用虛擬內存技術，當發生頁出錯時，需要從硬碟中讀取交換數據，但硬碟讀寫由於存儲位置的隨機性會導致隨機的讀寫時間，這在某些情況下會影響一些實時任務的截止期限；

雖然Linux進程調度也支持實時優先順序，但缺乏有效的實時任務的調度機制和調度演算法；它的網路子系統的協議處理和其它設備的中斷處理都沒有與它對應的進程的調度關聯起來，並且它們自身也沒有明確的調度機制；

3. 各種實時Linux系統

3.1. RT-Linux和RTAI

RT -Linux是新墨西哥科技大學（New Mexico Institute of Technology）的研究成果[RTLinuxWeb][Barabanov97]。它的基本思想是，為了在Linux系統中提供對於硬實時的支持，它實現了一個微內核的小的實時操作系統（我們也稱之為RT-Linux的實時子系統），而將普通Linux系統作為一個該操作系統中的一個低優先順序的任務來運行。另外普通Linux系統中的任務可以通過FIFO和實時任務進行通信。RT-Linux的框架如圖 1所示：

圖 1 RT-Linux結構

RT -Linux的關鍵技術是通過軟體來模擬硬體的中斷控制器。當Linux系統要封鎖CPU的中斷時時，RT-Linux中的實時子系統會截取到這個請求，把它記錄下來，而實際上並不真正封鎖硬體中斷，這樣就避免了由於封中斷所造成的系統在一段時間沒有響應的情況，從而提高了實時性。當有硬體中斷到來時， RT-Linux截取該中斷，並判斷是否有實時子系統中的中斷常式來處理還是傳遞給普通的Linux內核進行處理。另外，普通Linux系統中的最小定時精度由系統中的實時時鍾的頻率決定，一般Linux系統將該時鍾設置為每秒來100個時鍾中斷，所以Linux系統中一般的定時精度為 10ms，即時鍾周期是10ms，而RT-Linux通過將系統的實時時鍾設置為單次觸發狀態，可以提供十幾個微秒級的調度粒度。

RT-Linux實時子系統中的任務調度可以採用RM、EDF等優先順序驅動的演算法，也可以採用其他調度演算法。

RT -Linux對於那些在重負荷下工作的專有系統來說，確實是一個不錯的選擇，但他僅僅提供了對於CPU資源的調度；並且實時系統和普通Linux系統關系不是十分密切，這樣的話，開發人員不能充分利用Linux系統中已經實現的功能，如協議棧等。所以RT-Linux適合與工業控制等實時任務功能簡單，並且有硬實時要求的環境中，但如果要應用與多媒體處理中還需要做大量的工作。

義大利的RTAI( Real-Time Application Interface )源於RT-Linux，它在設計思想上和RT-Linux完全相同。它當初設計目的是為了解決RT-Linux難於在不同Linux版本之間難於移植的問題，為此，RTAI在 Linux 上定義了一個實時硬體抽象層，實時任務通過這個抽象層提供的介面和Linux系統進行交互，這樣在給Linux內核中增加實時支持時可以盡可能少地修改 Linux的內核源代碼。

3.2. Kurt-Linux

Kurt -Linux由Kansas大學開發，它可以提供微秒級的實時精度[KurtWeb] [Srinivasan]。不同於RT-Linux單獨實現一個實時內核的做法，Kurt -Linux是在通用Linux系統的基礎上實現的，它也是第一個可以使用普通Linux系統調用的基於Linux的實時系統。

Kurt-Linux將系統分為三種狀態：正常態、實時態和混合態，在正常態時它採用普通的Linux的調度策略，在實時態只運行實時任務，在混合態實時和非實時任務都可以執行；實時態可以用於對於實時性要求比較嚴格的情況。

為了提高Linux系統的實時特性，必須提高系統所支持的時鍾精度。但如果僅僅簡單地提高時鍾頻率，會引起調度負載的增加，從而嚴重降低系統的性能。為了解決這個矛盾， Kurt-Linux採用UTIME所使用的提高Linux系統中的時鍾精度的方法[UTIMEWeb]：它將時鍾晶元設置為單次觸發狀態（One shot mode），即每次給時鍾晶元設置一個超時時間，然後到該超時事件發生時在時鍾中斷處理程序中再次根據需要給時鍾晶元設置一個超時時間。它的基本思想是一個精確的定時意味著我們需要時鍾中斷在我們需要的一個比較精確的時間發生，但並非一定需要系統時鍾頻率達到此精度。它利用CPU的時鍾計數器TSC (Time Stamp Counter)來提供精度可達CPU主頻的時間精度。

對於實時任務的調度，Kurt-Linux採用基於時間（TD）的靜態的實時CPU調度演算法。實時任務在設計階段就需要明確地說明它們實時事件要發生的時間。這種調度演算法對於那些循環執行的任務能夠取得較好的調度效果。

Kurt -Linux相對於RT-Linux的一個優點就是可以使用Linux系統自身的系統調用，它本來被設計用於提供對硬實時的支持，但由於它在實現上只是簡單的將Linux調度器用一個簡單的時間驅動的調度器所取代，所以它的實時進程的調度很容易受到其它非實時任務的影響，從而在有的情況下會發生實時任務的截止期限不能滿足的情況，所以也被稱作嚴格實時系統（Firm Real-time）。目前基於Kurt-Linux的應用有：ARTS（ATM Reference Traffic System）、多媒體播放軟體等。另外Kurt-Linux所採用的這種方法需要頻繁地對時鍾晶元進行編程設置。

3.3. RED-Linux

RED -Linux是加州大學Irvine分校開發的實時Linux系統[REDWeb][ Wang99]，它將對實時調度的支持和Linux很好地實現在同一個操作系統內核中。它同時支持三種類型的調度演算法，即：Time-Driven、 Priority-Dirven、Share-Driven。

為了提高系統的調度粒度，RED-Linux從RT-Linux那兒借鑒了軟體模擬中斷管理器的機制，並且提高了時鍾中斷頻率。當有硬體中斷到來時，RED-Linux的中斷模擬程序僅僅是簡單地將到來的中斷放到一個隊列中進行排隊，並不執行真正的中斷處理程序。

另外為了解決Linux進程在內核態不能被搶占的問題， RED-Linux在Linux內核的很多函數中插入了搶占點原語，使得進程在內核態時，也可以在一定程度上被搶占。通過這種方法提高了內核的實時特性。

RED-Linux的設計目標就是提供一個可以支持各種調度演算法的通用的調度框架，該系統給每個任務增加了如下幾項屬性，並將它們作為進程調度的依據：

Priority：作業的優先順序；

Start-Time：作業的開始時間；

Finish-Time：作業的結束時間；

Budget：作業在運行期間所要使用的資源的多少；

通過調整這些屬性的取值及調度程序按照什麼樣的優先順序來使用這些屬性值，幾乎可以實現所有的調度演算法。這樣的話，可以將三種不同的調度演算法無縫、統一地結合到了一起。

6. linux進程調度的三種策略是什麼

進程調度策略就是調度系統種哪一個進程來CPU運行。這種調度分2層考慮。 第一層，進程狀態這個是最優先考慮的，也就是說優先順序最高的。在linux中只有就緒態的進程才有可能會被調度選中然後佔有CPU，其它狀態的進程不可能佔有的到CPU。下面是linux中進程的狀態TASK_RUNNING:就緒狀態，得到CPU就可以運行。
TASK_INTERRUPTIBLE:淺度睡眠，資源到位或者受到信號就會變成就緒態。
TASK_UNINTERRUPTIBLE:深度睡眠，資源到位就會進入就緒態，不響應信號。
TASK_ZOMBIE：僵死態，進程exit後。
TASK_STOPPED：暫停態，收到SIG_CONT信號進入就緒態。 第二層，其實真正在操作系統中的實現，就是所有就緒態進程鏈接成一個隊列，進程調度時候只會考慮這個隊列中的進程，對其它的進程不考慮，這就實現了第一層中的要求。接下來就是就緒隊列內部各個進程的競爭了。 Linux採用3種不同的調度政策，SCHED_FIFO（下面簡寫成FIFO，先來先服務），SCHED_RR（簡寫成RR，時間片輪流），SCHED_OTHER（下面簡寫成OTHER）。這里大家就能看出一個問題，採用同等調度政策的進程之間自然有可比性，Linux3種調度政策並存，那麼不同調度政策間的進程如何比較呢？可以說他們之間根本就沒有可比性。其實在調度時候，調度只看一個指標，那就是各個進程所具有的權值，權值最大的且在可執行隊列中排在最前面的就會被調度執行。而權值的計算才會設計到各方面因素，其中調度政策可以說在計算權值中，份量是最重的。 為什麼Linux要這么干呢？這是由於事務的多樣性決定的，進程有實時性進程和非實時性的進程2種，FIFO和RR是用來支持實時性進程的調度，我們看一下這3種政策下權值的計算公式就明白了：FIFO和RR計算公式，權值=1000+進程真正的運行時間OTHER計算公式，當時間片為0時，權值=0.當時間片不為0時候，權值=剩餘時間片+20-nice,同時如果是內核線程有+1的小加分，這是因為內核線程無需用戶空間的切換，所以給它加了一分，獎勵他在進程切換時候開銷小的功勞。時間片好理解，那麼nice這個值，用過linux系統的人都知道，這是一個從unix下繼承過來的概念，表示謙讓度，是一個從20～-19的數，可以通過nice和renice指令來設置。從代碼中也能看到值越小就越不會謙讓他人。 從這里我們看出FIFO和RR至少有1000的基數，所以在有FIFO和RR調度政策進程存在時，OTHER進程是沒有機會被調度的到的。從權值計算公式同時也能看出，FIFO先來先服務的調度政策滿足了，但RR這個時間片輪流的調度如果按照這種權值計算是不能滿足時間片輪流這一概念的。這里只是權值的計算，在調度時候對RR政策的進程特殊處理。 以上都是權值計算，下面看看真正的調度過程，首先是對RR政策進程的特殊處理，如果當前進程採用的RR政策，那麼看他的時間片是否用完，用完了就踢到就緒隊列尾部，同時恢復他的時間片。然後是便利整個就緒隊列，找到第一個權值最大的進程來運行。 整體調度效果就是：如果有FIFO和RR政策的進程，就優先調度他們2個，他們之間看已執行時間長短決定勝負，而2種政策內部則遵守各自調度政策。而OTHER只有在前面2種不存在於就緒隊列時候才有可能執行，他們實際也是輪流執行，但他們之間是靠剩餘時間和NICE值來決定勝負。同時就緒隊列中排在最前面的最優先考慮在同樣權值情況下。

7. linux調度演算法的核心思想是什麼

第一部分：實時調度演算法

什麼是實時系統，POSIX 1003.b作了這樣的定義：是指系統可以在有限響應時間內提供所需的服務級別。較可取被定義為由Donald喬利士的的：一個實時系統的程序的邏輯正確性不僅取決於計算的准確度，而且還對結果，如果系統時間的限制不能滿足將是一個系統錯誤發生。

基於實時系統的實時性要求的不同，可分為軟實時和硬實時兩種。硬實時系統是指系統必須確保，在最壞情況下的服務時間，截止日期為事件的響應時間是在任何情況下，必須滿足。如航天飛船的控制是這樣一個系統的現實。所有其他實時系統的特點，可以稱為軟實時系統。如果清除，軟實時系統是那些從統計學的角度來看，一個任務（在下面的討論中，我們將有任務和過程不作出區分），以確保系統的處理時間，可以得到事件可以處理的最後期限到來之前，違反的最後期限，並不會帶來一個致命的錯誤，如實時多媒體系統是一種軟實時系統。

一台電腦系統的CPU和其他資源進行有效的調度和管理，以提供實時操作系統的支持。的多任務的實時系統中，資源的調度和管理更復雜的。下面討論本文將從各種實時任務調度演算法的分類的角度來看，普通的Linux操作系統進程調度和各種實時Linux系統，然後研究，以支持實時特點，普通的Linux系統的改進。實時領域的一些問題，並總結了各種實時Linux的Linux操作系統，歸根到底是如何解決這些問題。

CPU的實時調度演算法的分類

多種實時操作系統的實時調度演算法可以分為以下三類Wang99] [Gopalan01]：基於優先順序調度演算法（優先順序驅動調度PD），基於在共享的CPU使用率調度演算法（分享驅動調度SD）的比例，以及基於時間的進程調度演算法（時間驅動調度TD），下面這三種調度演算法逐一介紹。

1.1

/>基於優先順序的調度演算法，基於優先順序的調度演算法，每個進程被分配一個優先順序，每次的進程調度程序，調度程序總是具有最高的調度優先順序的任務執行。根據不同的優先順序分配方法，基於優先順序的調度演算法可以分為以下兩種類型的Krishna01] [Wang99]：靜態優先順序調度演算法

該演算法得到這些系統中運行的所有進程都靜態分配一個優先順序。靜態優先順序分配的屬性的應用程序，如任務循環中的用戶優先順序，或其他預先確定的政策。 RM（速率單調）的調度演算法是一個典型的靜態優先順序的調度演算法，根據執行的任務的調度優先順序的周期的長度確定，那些具有小的執行周期的任務的優先順序較高。

動態優先順序調度演算法：

該演算法基於任務的資源需求動態地分配任務的優先順序，資源分配和調度的目的更大的靈活性。非實時系統，這種演算法有很多，如短作業優先順序調度演算法。任務的實時調度演算法，EDF演算法是使用最廣泛的動態優先順序調度演算法，該演算法根據他們的截止日期（截止日期）分配優先順序的就緒隊列中的每個任務，最近期限具有最高的優先順序。

1.2

基於優先順序調度演算法的調度演算法是簡單而有效的，但這種演算法的基礎上按比例份額是一個硬實時調度，許多的情況下，不適合使用此演算法：例如，軟實時應用，如實時多媒體會議系統。對於軟實時應用程序，共享資源調度演算法（SD演算法）的比例使用是更合適的。

比例共享調度演算法是指對CPU使用率的比例共享調度演算法，其基本思路是按照一定的權重（比率），需要一組調度安排任務，以使它們的權重成比例的執行時間。

要實現比例共享調度演算法[Nieh01]有兩種方法：第一種方法是調整的准備過程中出現的調度隊列隊第一頻率，並安排一線隊的過程中，執行第二種方法是連續調度進程就緒隊列中投產，但根據調整分配一個進程的運行時間片分配的權重。

比例共享調度演算法可以分為以下類別：循環賽，公平份額，公平排隊，的彩票調度方法，（彩票）。

比例共享調度演算法的一個問題是，它並沒有定義任何優先的概念，所有的任務都根據其應用的CPU資源的比例共享系統過載時，執行的所有任務將較慢比例。因此，為了確保該系統的實時過程中獲得一定量的CPU處理時間，一般採用的是動態權重的調整過程。

1.3。基於時間進程調度演算法的調度演算法

對於那些具有穩定，簡單的系統已知輸入，您可以使用時間驅動（驅動時間時間：TD）數據處理，它可以提供一個良好的預測。這種調度演算法本質上是一個設計定型的離線靜態調度方法。在系統的設計階段，所有處理的情況下，在明確的制度，每個任務切換的開始和結束的時間提前做出了明確的安排和設計。該演算法是適用於小型嵌入式系統，自動化控制系統，感測器和其他應用環境。

該演算法的優勢是良好的可預測性任務的執行，但最大的缺點是缺乏靈活性，而且會有一個任務需要執行，而CPU保持空閑。

一般的Linux系統CPU調度

一般的Linux系統支持實時和非實時兩種進程，實時進程與普通進程方面具有絕對的優先權。相應地，實時進程調度策略SCHED_FIFO或SCHED_RR，普通進程SCHED_OTHER調度策略。

每個任務調度演算法的實現在Linux四種調度參數，它們是rt_priority優先政策（尼斯），計數器。調度進程調度的基礎上，這四個參數。

SCHED_OTHER調度策略，調度程序總是會選擇優先順序+計數器的值進程調度的執行。從邏輯分析存在SCHED_OTHER調度策略調度處理來執行，其特徵在於，所述優先順序是一個固定的調度周期（歷元），在每個調度周期內的過程中的優先順序，計數器的值的大小的影響這一刻已經確定變數值的過程中被創建時，它代表了進程的優先順序，也代表數量的時間片，通過該方法可以得到在每個調度周期內，計數器是一個動態值，它反映了當前調度周期的過程中，剩餘的時間片。在每個調度周期的開始，分配給優先順序值計數器，那麼每一次進程被調度運行計數器的值？減少。當計數器的值是零，這個過程已經運行的時間片調度期內，不再參與調度周期進程調度。當所有的進程都用完了時間片調度期結束，然後一遍又一遍。此外，可以看出在Linux系統中的調度周期是不固定的，它的量是動態變化的，例如，在運行的進程的數目和它們的優先順序值？可以影響一個劃時代的長度。有一點值得注意的是，在2.4內核中，首要任務是不錯的替換兩個類似的作用。

按比例分擔的調度策略調度策略SCHED_OTHER可見的性質，它的這種設計方法，以確保進程調度的公平性 - 一個低優先順序進程，在每個時代也將得到他們的份額那些CPU的執行時間，此外，它也提供了不同的進程的優先順序，進程執行時間可以得到更多的具有高優先順序值。

對於實時的過程中，他們使用基於實時優先順序rt_priority的優先順序調度策略，但相同的實時優先順序的進程調度方法是根據不同的調度策略，

BR /> SCHED_FIFO：不同的進程，根據靜態優先順序排隊，然後在相同的優先順序隊列，先准備好運行的第一誰調度和運行的進程不會被終止，直到發生以下情況：1。高優先順序的進程篡奪了CPU;自己的資源請求受阻;自己主動放棄CPU（呼叫SCHED_YIELD）;

SCHED_RR是這樣的：這個調度策略SCHED_FIFO與上述完全相同，除了時間片分配給每個進程，正在實施的過程中，給執行時間片，時間片的長度可以通過sched_rr_get_interval調用

由於Linux系統本身是一個桌面導向的系統，因此，它是用於在實時應用中的一些問題：/> /> Linux系統調度單位是10ms，所以它不能提供精確的定時中斷; p>當一個進程調用系統調用進入內核模式運行，它不能被搶占;

Linux內核實現大量採用了封閉中斷操作損失;

由於使用虛擬內存技術，當發生頁面錯誤時，從硬碟中讀取的數據交換的需要，但硬碟讀取和寫入的存儲位置的隨機性，將導致隨機讀取和寫入時間，這在某些情況下，會影響實時任務期限;

雖然Linux的進程調度器還支持實時優先順序，但由於缺乏有效的實時任務調度機制和調度演算法;其網路子協議處理和其它設備的中斷處理，調度伴有相應的過程和自己的有沒有明確的調度機制;

各種實時Linux系統
Home>的的

3.1 RT-Linux和RTAI

RT-Linux是新墨西哥大學的研究（新墨西哥州技術學院）[RTLinuxWeb] [Barabanov97。其基本思路是，在Linux系統上的硬實時支持，它實現了一個微內核實時操作系統（也被稱為RT-Linux的實時子系統），而普通的Linux系統作為一個低優先順序任務在操作系統中運行。在正常的Linux系統的另一個任務可以溝通，通過FIFO和實時任務。 RT-Linux的框架如圖1所示：

圖1 RT-Linux的結構

RT-Linux的關鍵技術是軟體模擬硬體中斷控制器。當Linux系統不時阻止CPU中斷，實時定量RT-Linux的子系統的請求攔截，愛不釋手，而事實上並沒有真正阻止硬體中斷，從而避免了由於中斷造成的封由系統在一段時間內沒有響應，從而在改進的實時。當傳遞給Linux內核的RT-Linux的一個硬體中斷到達截取的中斷，並確定是否有一個實時子系統中斷常式來處理或處理。此外，的最小定時的精度在正常的Linux系統是確定系統的實時時鍾的頻率，Linux的系統時鍾被設置到時鍾中斷每秒100，所以在Linux的系統定時的精度10毫秒，即時鍾周期10ms時，RT-Linux的實時時鍾設置為單觸發狀態，可以提供更多的十幾微秒調度粒度。

RT-Linux實時子系統的任務調度優先順序驅動演算法，RM，EDF等，也可用於其他調度演算法。

RT-Linux的專有系統，重型工作，的確是一個不錯的選擇，但他只提供了CPU資源的調度和實時系統和Linux系統的關系不是非常密切，因此開發人員可以充分利用已在Linux系統中，如協議棧實現的功能。 RT-Linux的工業控制等實時任務簡單和硬實時要求的環境，但大量的工作需要做，如果你想應用的多媒體處理。

義大利實時應用程序介面（RTAI）來自RT-Linux的，它是在設計和RT-Linux的思想相同。這是原來的設計中，為了解決問題，RT-Linux的不同版本的Linux之間很難很難移植，RTAI在Linux上定義的實時硬體抽象層，這個抽象層介面提供實時任務Linux系統的相互作用，這可以增加一點可以Linux內核源代碼到Linux內核的實時支持。

3.2。 KURT-Linux的

KURT-Linux的堪薩斯大學開發的，它可以提供實時微秒精度[KurtWeb] [斯里尼瓦桑]。與RT-Linux的單獨實現一個實時內核，KURT-Linux是常用的Linux系統的基礎上實現的，這也是第一個基於Linux的實時系統可以使用普通的Linux系統調用。

KURT-Linux系統分為三種狀態：正常狀態，實時狀態和混合狀態，在正常狀態下，它使用普通的Linux實時運行狀態實時調度策略任務，實時和非實時任務的混合狀態，可以執行實時狀態可以被用來為實時的要求更加嚴格。

為了提高Linux系統的實時特性，有必要提高精度的時鍾系統的支持。但是，如果只是簡單地增加時鍾頻率將導致調度負載的增加，從而嚴重降低系統的性能。為了解決這個矛盾，KURT-Linux中使用的時鍾精度的方法[UTIMEWeb]提高Linux系統UTIME，時鍾晶元設置為單次觸發狀態（單拍模式），也就是每個時鍾晶元設置超時，然後再次超時事件發生時，在時鍾中斷的處理程序所需的時鍾晶元設置一個超時。其基本思想是一個精確的時間意味著我們需要的時鍾中斷發生時，我們需要一個更精確的時間，以達到這樣的精度，但並不一定需要系統時鍾頻率。它採用了CPU時鍾計數器時間戳計數器（TSC）提供准確的CPU頻率精度的時間。

KURT-Linux的實時任務調度，使用靜態CPU的實時調度演算法，基於時間（TD）。實時任務需要實時事件發生在設計階段就必須清楚列明。該演算法可以實現更好的調度任務，對於那些誰周期。

KURT-Linux的相RT-Linux的優勢之一是，你可以使用系統調用的Linux系統，它最初是專為硬實時支持，但因為它是簡單的實現將使用一個簡單的時間驅動調度取代Linux的調度，實時進程調度的影響等非實時任務，在某些情況下會發生實時任務的截止日期是脆弱的不符合的，也被稱為嚴格的實時系統（快地實時）。基於KURT-Linux的應用程序：藝術（ATM參考交通系統），多媒體播放軟體。 KURT-Linux的另一種方法，需要頻繁的時鍾晶元編程。

3.3。 RED-Linux的

RED-Linux是加州大學爾灣，實時Linux系統的發展[REDWeb] [Wang99]，它將支持實時調度和Linux實現相同的操作系統內核。它支持三種類型的調度演算法，即：時間驅動優先Dirven，分享驅動。

為了提高系統的調度粒度，RED-Linux的學習RT-Linux的軟體模擬中斷的管理機制，並增加頻率的時鍾中斷。 RED-Linux的中斷模擬程序只是簡單地中斷會在隊列中排隊一個硬體中斷到來時，並沒有進行實際的中斷處理程序。

另外，為了解決Linux的內核模式的過程中不能被中斷，RED-Linux的插入Linux內核搶占點原語的眾多功能，使這一進程在內核模式下，也在一定程度上被搶占。通過這種方法提高了內核的實時特性。

RED-Linux的設計目標是提供常規調度框架可以支持多種調度演算法，系統為每個任務增加幾個屬性，進程調度的基礎上：

優先順序：作業的優先順序;

開始時間：工作的開始時間;

完成時間：工作的結束時間; BR p>預算：資源的數量在操作過程中要使用的工作;

調整值？這些屬性和調度根據什麼優先使用的這些屬性值幾乎所有的調度演算法。在這種情況下，三種不同的調度演算法無縫地一起耦合到一個統一的。

8. linux進程、線程及調度演算法（三）

調度策略值得是大家都在ready時，並且CPU已經被調度時，決定誰來運行，誰來被調度。

兩者之間有一定矛盾。
響應的優化，意味著高優先順序會搶占優先順序，會花時間在上下文切換，會影響吞吐。
上下文切換的時間是很短的，幾微妙就能搞定。上下文切換本身對吞吐並多大影響， 重要的是，切換後引起的cpu 的 cache miss.
每次切換APP, 數據都要重新load一次。
Linux 會盡可能的在響應與吞吐之間尋找平衡。比如在編譯linux的時候，會讓你選擇 kernal features -> Preemption model.
搶占模型會影響linux的調度演算法。

所以 ARM 的架構都是big+LITTLE， 一個很猛CPU+ 多個 性能較差的 CPU, 那麼可以把I/O型任務的調度 放在 LITTLE CPU上。需要計算的放在big上。

早期2.6 內核將優先順序劃分了 0-139 bit的優先順序。數值越低，優先順序越高。0-99優先順序 都是 RT（即時響應）的 ，100-139都是非RT的，即normal。
調度的時候 看哪個bitmap 中的 優先順序上有任務ready。可能多個任務哦。

在普通優先順序線程調度中，高優先順序並不代表對低優先順序的絕對優勢。會在不同優先順序進行輪轉。
100 就是比101高，101也會比102高，但100 不會堵著101。
眾屌絲進程在輪轉時，優先順序高的：

初始設置nice值為0，linux 會探測 你是喜歡睡眠，還是幹活。越喜歡睡，linux 越獎勵你，優先順序上升（nice值減少）。越喜歡幹活，優先順序下降（nice值增加）。所以一個進程在linux中，干著干著 優先順序越低，睡著睡著 優先順序越高。

後期linux補丁中

紅黑樹，數據結構， 左邊節點小於右邊節點
同時兼顧了 CPU/IO 和 nice。
數值代表著 進程運行到目前為止的virtual runtime 時間。

（pyhsical runtime） / weight * 1024(系數)。
優先調度 節點值（vruntime）最小的線程。權重weight 其實有nice 來控制。

一個線程一旦被調度到，則物理運行時間增加，vruntime增加，往左邊走。
weight的增加，也導致vruntime減小，往右邊走。
總之 CFS讓線程 從左滾到右，從右滾到左。即照顧了I/O(喜歡睡，分子小) 也 照顧了 nice值低（分母高）.所以 由喜歡睡，nice值又低的線程，最容易被調度到。
自動調整，無需向nice一樣做出獎勵懲罰動作，個人理解權重其實相當於nice

但是 此時 來一個 0-99的線程，進行RT調度，都可以瞬間秒殺你！因為人家不是普通的，是RT的!

一個多線程的進程中，每個線程的調度的策略 如 fifo rr normal, 都可以不同。每一個的優先順序都可以不一樣。
實驗舉例, 創建2個線程，同時開2個：

運行2次，創建兩個進程
sudo renice -n -5(nice -5級別) -g(global)， 會明顯看到 一個進程的CPU佔用率是另一個的 3倍。

為什麼cpu都已經達到200%，為什麼系統不覺得卡呢？因為，我們的線程在未設置優先順序時，是normal調度模式，且是 CPU消耗型 調度級別其實不高。

利用chrt工具，可以將進程 調整為 50 從normal的調度策略 升為RT （fifo）級別的調度策略，會出現：

chrt , nice renice 的調度策略 都是以線程為單位的，以上 設置的將進程下的所有線程進行設置nice值
線程是調度單位，進程不是，進程是資源封裝單位！

兩個同樣死循環的normal優先順序線程，其中一個nice值降低，該線程的CPU 利用率就會比另一個CPU的利用率高。