基本介紹
- 中文名：進程調度
- 基本屬性：多態性
- 基本狀態：等待態、運行態、就緒態
- 處理：高級
- 領域：作業系統
基本屬性,基本狀態,處理機,方式,非剝奪方式,剝奪方式,算法,先進先出算法,短進程優先,輪轉法,多級反饋佇列,實現,功能,時機,上下切換,性能評價,實時系統,綜述,優先權,比例共享,時間,Linux 原理,依據,調度方法,策略,主要函式,
基本屬性
1.多態性 從誕生、運行，直至消滅。
2.多個不同的進程可以包括相同的程式
進程調度
進程調度3.三種基本狀態 它們之間可進行轉換
基本狀態
1.等待態：等待某個事件的完成；
2.就緒態：等待系統分配處理器以便運行；
3.運行態：占有處理器正在運行。
運行態→等待態 往往是由於等待外設，等待主存等資源分配或等待人工干預而引起的。
等待態→就緒態 則是等待的條件已滿足，只需分配到處理器後就能運行。
運行態→就緒態 不是由於自身原因，而是由外界原因使運行狀態的進程讓出處理器，這時候就變成就緒態。例如時間片用完，或有更高優先權的進程來搶占處理器等。
就緒態→運行態 系統按某種策略選中就緒佇列中的一個進程占用處理器，此時就變成了運行態
處理機
高級、中級和低級調度作業從提交開始直到完成，往往要經歷下述三級調度：
方式
非剝奪方式
分派程式一旦把處理機分配給某進程後便讓它一直運行下去，直到進程完成或發生某事件而阻塞時，才把處理機分配給另一個進程。
進程調度
進程調度剝奪方式
例如，有三個進程P1、P2、P3先後到達，它們分別需要20、4和2個單位時間運行完畢。
26個單位時間，平均周轉時間是23.33個時間單位。
假如用時間片原則的剝奪調度方式，可得到：
可見：P1、P2、P3的周轉時間分別為26、10、6個單位時間(假設時間片為2個單位時間)，平均周轉時間為14個單位時間。
衡量進程調度性能的指標有：周轉時間、回響時間、CPU-I/O執行期。
算法
先進先出算法
算法總是把處理機分配給最先進入就緒佇列的進程，一個進程一旦分得處理機，便一直執行下去，直到該進程完成或阻塞時，才釋放處理機。
例如，有三個進程P1、P2和P3先後進入就緒佇列，它們的執行期分別是21、6和3個單位時間，
執行情況如下圖：
對於P1、P2、P3的周轉時間為21、27、30，平均周轉時間為26。
可見，FIFO算法服務質量不佳，容易引起作業用戶不滿，常作為一種輔助調度算法。
短進程優先
最短CPU運行期優先調度算法(SCBF--Shortest CPU Burst First)
例如，在就緒佇列中有四個進程P1、P2、P3和P4，它們的下一個執行期分別是16、12、4和3個單位時間，執行情況如下圖：
進程調度
進程調度P1、P2、P3和P4的周轉時間分別為35、19、7、3，平均周轉時間為16。
該算法雖可獲得較好的調度性能，但難以準確地知道下一個CPU執行期，而只能根據每一個進程的執行歷史來預測。
輪轉法
多級佇列方法：將系統中所有進程分成若干類，每類為一級。
多級反饋佇列
多級反饋佇列方式是在系統中設定多個就緒佇列，並賦予各佇列以不同的優先權。
實現
引起原因
正在執行的進程執行完畢或因發生某事件而不能再繼續執行；
執行中的進程因提出I/O請求而暫停執行；
在進程通信或同步過程中執行了某種原語操作如P操作、阻塞、掛起原語等；
在可剝奪式調度中，有比當前進程優先權更高的進程進入就緒佇列；
在時間片輪轉法中，時間片完；
功能
記錄系統中所有進程的執行情況
進程調度的具體功能可總結為如下幾點：作為進程調度的準備，進程管理模組必須將系統中各進程的執行情況和狀態特徵記錄在各進程的PCB表中。並且，根據各進程的狀態特徵和資源需求等、進程管理模組還將各進程的PCB表排成相應的佇列並進行動態佇列轉接。進程調度模組通過PCB變化來掌握系統中存在的所有進程的執行情況和狀態特徵，並在適當的時機從就緒佇列中選擇出一個進程占據處理機。
進程調度
進程調度選擇占有處理機的進程
進程調度的主要功能是按照一定的策略選擇—個處於就緒狀態的進程，使其獲得處理機執行。根據不同的系統設計目的，有各種各樣的選擇策略，例如系統開銷較少的靜態優先數調度法，適合於分時系統的輪轉法(Round RoLin)和多級互饋輪轉法(Round Robin with Multip1e feedback)等。這些選擇策略決定了調度算法的性能。
進行進程上下文切換
時機
引起進程調度的原因有以下幾類
進程調度發生在什麼時機呢？這與引起進程調度的原因以及進程調度的方式有關。
(1)正在執行的進程執行完畢。這時，如果不選擇新的就緒進程執行，將浪費處理機資源。
(2)執行中進程自己調用阻塞原語將自己阻塞起來進入睡眠等狀態。
(4)執行中進程提出I/O請求後被阻塞。
(5)在分時系統中時間片已經用完。
(6)在執行完系統調用等系統程式後返回用戶進程時，這時可看作系統進程執行完畢，從而可調度選擇一新的用戶進程執行。
以上都是在可剝奪方式下的引起進程調度的原因。在CPU執行方式是可剝奪時．還有
(7)就緒佇列中的某進程的優先權變得高於當前執行進程的優先權，從而也將引發進程調度。
兩種占用CPU的方式
不可剝奪式 (不可搶占式non_preemptive)：即使在就緒佇列存在有優先權高於當前執行進程時，當前進程仍將占用處理機直到該進程自己因調用原語操作或等待I/O而進入阻塞、睡眠狀態，或時間片用完時才重新發生調度讓出處理機。
上下切換
進程上下文由正文段、數據段、硬體暫存器的內容以及有關數據結構等組成。硬體暫存器主要包括存放CPU將要執行的下條指令虛擬地址的程式計數器PC，指出機器與進程相關聯的硬體狀態的處理機狀態暫存器PS，存放過程調用(或系統調用)時所傳遞參數的通用暫存器R以及堆疊指針暫存器S等。數據結構則包括PCB等在內的所有與執行該進程有關的管理和控制用表格、數組、鏈等。在發生進程調度時系統要做進程上下文切換。
在進程（上下文）中切換的步驟
n用新狀態和其它相關信息更新正在運行進程的PCB
n把原來的進程移至合適的佇列-就緒、阻塞
n選擇另一個要執行的進程
n更新被選中進程的PCB
n從被選中進程中重裝入
CPU 上下文
性能評價
進程調度的定量評價包括CPU的利用率評價、進程在就緒佇列中的等待時間與執行時間之比等。實際上由於進程進入就緒佇列的隨機模型很難確定，而且進程上下文切換等也將影響進程的執行效率，LL而對進程調度進行解析是很困難的。一般情況下，大多利用模擬或測試系統回響時間的方法來評價進程調度的性能。
實時系統
綜述
實時系統與其他作業系統不同在於計算機要能及時回響外部事件的請求，在規定的嚴格時間內完成對該事件的處理，並控制所有實時設備和實時任務協調一致地工作，對於對時間要求嚴格性的不同，實時系統又分為硬實時系統和軟實時系統，其中硬實時系統是指這種時限的要求是絕對的，任何一個實時任務都能夠在時限之前完成；而軟實時系統的要求就沒有這么嚴格，允許偶爾有實時任務不滿足時限的要求.實時系統一般用於嵌入式的系統中，分為實時過程控制和實時通信處理，其中實時過程控制主要用於工業控制，軍事控制領域；時事通信用於電信，銀行，飛機訂票等領域，正是由於在這些特殊領域的運用使得實時作業系統設計時主要追求的是：對外部請求在嚴格時間範圍內做出反應，有高可靠性和完備性.為達到時間要求，進程的調度策略就顯得尤為重要.
優先權
最簡單最直觀的進程調度策略是基於優先權的調度，多數實時系統採用基於優先權的調度，每個進程根據它重要程度的不同被賦予不同的優先權，調度器在每次調度時，總選擇優先權最高的進程開始執行.
首先要考慮的問題是如何分配優先權，對於進程優先權的分配可以採用靜態和動態兩種方式，靜態優先權調度算法：這種調度算法給那些系統中得到運行的所有進程都靜態地分配一個優先權.靜態優先權的分配可以根據套用的屬性來進行，比如進程的周期，用戶優先權，或者其它的預先確定的策略.單調率算法(RM)調度算法是一種典型的靜態優先權調度算法，它根據進程的執行周期的長短來決定調度優先權，那些具有小的執行周期的進程具有較高的優先權.動態優先權調度算法：這種調度算法根據進程的資源需求來動態地分配進程的優先權，其目的就是在資源分配和調度時有更大的靈活性.在實時系統中，最早期限優先算法(EDF)算法是使用最多的一種動態優先權調度算法，該算法給就緒佇列中的各個進程根據它們的截止期限(Deadline)來分配優先權，具有最近的截止期限的進程具有最高的優先權.
不可搶占式核心要求每個進程自我放棄CPU的所有權，各個進程彼此合作共享一個CPU.異步事件還是由中斷服務來處理.中斷服務可以使一個高優先權的進程由掛起狀態變為就緒狀態.但中斷服務以後控制權還是回到原來被中斷了的那個進程，直到該進程主動放棄CPU的使用權時，那個高優先權的進程才能獲得CPU的使用權.這就出現了回響時間的問題，高優先權的進程已經進入了就緒狀態但不能執行，這樣進程的回響時間變得不再確定這與實時系統的要求不符，因此一般的實時作業系統都要求是可搶占式的核心，當一個運行著的進程使一個比它優先權高的進程進入了就緒態，當前進程的CPU使用權就被剝奪了，或者說被掛起了，那個高優先權的進程立刻得到了CPU的控制權，如果是中斷服務子程式使一個高優先權的進程進入就緒態，中斷完成時，中斷了的進程被掛起，優先權高的那個進程開始運行.在這種核心設定下，多個進程可能處於並發的狀態，這就出現了多個進程共享資源的情況，因此我們需要設定信號量來保證臨界資源的正確使用，任何一個想使用臨界資源的進程在進入臨界區之前必須擁有使用臨界資源的信號量，否則不可以執行臨界區代碼.
這樣基於優先權的可搶占式進程調度策略就基本架構完成，但此時仍然有系統崩潰的危險，假設系統中有3個進程，分別為p1，p2和p3. p1的優先權高於p2，而p2的優先權高於p3.恰在此時p1和p2 因某種原因被阻塞，這時候系統調度p3執行.p3執行一段時間後，p1被喚醒.由於採取的是PBP的調度策略，因此p1搶占 p3的CPU， p1執行.p1執行一段時間後要進入臨界區，但此時p3占有此臨界資源的信號量.因此p1被阻塞，處於等待狀態，等待p3 釋放此信號量.經過這么一段時間後，p2此時此刻處於就緒狀態.因此系統調度p2執行.如果p3在p2的執行期間一直沒有能夠被調度執行的話，那p1和p3將一直等到p2執行完後才能執行，p1更要等到p3釋放它所把持的信號量才能執行；而這段時間完全有可能超出p1的Deadline，使得p1崩潰.我們看到在這個過程中，由於臨界資源的使用問題使得優先權低的進程先於優先權高的進程先執行，這就出現了優先權反轉的問題，從而造成了系統崩潰，對於這個問題可以採用優先權繼承的辦法來進行解決.在優先權繼承方案中，當高優先權進程在等待低優先權的進程占有的信號量時，讓低優先權進程繼承高優先權進程的優先權，即把低優先權進程的優先權提高到高優先權進程的優先權；當低優先權進程釋放高優先權進程等待的信號量時，立即把其優先權降低到原來的優先權.採用這種方法可以有效地解決上面所述的優先權反轉的問題.當高優先權進程p1想要進入臨界區時，由於低優先權進程p3占有這個臨界資源的信號量，導致p1被阻塞.這時候，系統把p3的優先權升到p1的優先權，此時優先權處於p1和p3之間的進程p2，即使處於就緒狀態也不可以被調度執行，因為此時p3的優先權已經高於p2，所以p3此時被調度執行.當p3釋放p1需要的信號量時，系統立即把p3的優先權降到原來的高度，來保證p1和p2正常有序執行，有許多實時系統是採用這種方法來防止優先權反轉的，如VXWORKS.
比例共享
雖然基於優先權的調度簡單而且易於實現，是目前使用最廣泛的實時系統的進程調度策略，但對於一些軟實時系統而言這種方法不再適用，比如實時多媒體會議，在這種情況下我們可以選擇基於共享的進程調度算法，其基本思想就是按照一定的權重(比例)對一組需要調度的進程進行調度，讓它們的執行時間與它們的權重完全成正比.我們可以通過兩種方法來實現比例共享調度算法：第一種方法是調節各個就緒進程出現在調度佇列隊首的頻率，並調度隊首的進程執行；第二種做法就是逐次調度就緒佇列中的各個進程投入運行，但根據分配的權重調節分配個每個進程的運行時間片.比例共享調度算法的一個問題就是它沒有定義任何優先權的概念；所有的進程都根據它們申請的比例共享CPU資源，當系統處於過載狀態時，所有的進程的執行都會按比例地變慢.所以為了保證系統中實時進程能夠獲得一定的CPU處理時間，一般採用一種動態調節進程權重的方法.
時間
對於那些具有穩定，已知輸入的簡單系統，可以使用時間驅動的調度算法，它能夠為數據處理提供很好的預測性.這種調度算法本質上是一種設計時就確定下來的離線的靜態調度方法.在系統的設計階段，在明確係統中所有的處理情況下，對於各個進程的開始，切換，以及結束時間等就事先做出明確的安排和設計.這種調度算法適合於那些很小的嵌入式系統，自控系統，感測器等套用環境.這種調度算法的優點是進程的執行有很好的可預測性，但最大的缺點是缺乏靈活性，並且會出現有進程需要被執行而 CPU 卻保持空閒的情況.
對於不同要求下的實時系統可以採用不同的進程調度策略來進行設計，也可以將這些方法進行綜合之後得到更適合的調度策略.
Linux 原理
依據
調度程式運行時，要在所有可運行狀態的進程中選擇最值得運行的進程投入運行。選擇進程的依據是什麼呢？在每個進程的task_struct結構中有以下四項：policy、priority、counter、rt_priority。這四項是選擇進程的依據。其中，policy是進程的調度策略，用來區分實時進程和普通進程，實時進程優先於普通進程運行；priority是進程(包括實時和普通)的靜態優先權；counter是進程剩餘的時間片，它的起始值就是priority的值；由於counter在後面計算一個處於可運行狀態的進程值得運行的程度goodness時起重要作用，因此，counter也可以看作是進程的動態優先權。rt_priority是實時進程特有的，用於實時進程間的選擇。
調度方法
1，SCHED_OTHER 分時調度策略，
2，SCHED_FIFO實時調度策略，先到先服務
3，SCHED_RR實時調度策略，時間片輪轉
實時進程將得到優先調用，實時進程根據實時優先權決定調度權值，分時進程則通過nice和counter值決定權值，nice越小，counter越大，被調度的機率越大，也就是曾經使用了cpu最少的進程將會得到優先調度。
SHCED_RR和SCHED_FIFO的不同：
SCHED_FIFO一旦占用cpu則一直運行。一直運行直到有更高優先權任務到達或自己放棄。
如果有相同優先權的實時進程（根據優先權計算的調度權值是一樣的）已經準備好，FIFO時必須等待該進程主動放棄後才可以運行這個優先權相同的任務。而RR可以讓每個任務都執行一段時間。
相同點：
RR和FIFO都只用於實時任務。
創建時優先權大於0(1-99)。
按照可搶占優先權調度算法進行。
就緒態的實時任務立即搶占非實時任務。
所有任務都採用linux分時調度策略時。
1，創建任務指定採用分時調度策略，並指定優先權nice值(-20~19)。
2，將根據每個任務的nice值確定在cpu上的執行時間(counter)。
3，如果沒有等待資源，則將該任務加入到就緒佇列中。
4，調度程式遍歷就緒佇列中的任務，通過對每個任務動態優先權的計算(counter+20-nice)結果，選擇計算結果最大的一個去運行，當這個時間片用完後(counter減至0)或者主動放棄cpu時，該任務將被放在就緒佇列末尾(時間片用完)或等待佇列(因等待資源而放棄cpu)中。
5，此時調度程式重複上面計算過程，轉到第4步。
6，當調度程式發現所有就緒任務計算所得的權值都為不大於0時，重複第2步。
所有任務都採用FIFO時，
1，創建進程時指定採用FIFO，並設定實時優先權rt_priority(1-99)。
2，如果沒有等待資源，則將該任務加入到就緒佇列中。
3，調度程式遍歷就緒佇列，根據實時優先權計算調度權值(1000+rt_priority)，選擇權值最高的任務使用cpu，該FIFO任務將一直占有cpu直到有優先權更高的任務就緒(即使優先權相同也不行)或者主動放棄(等待資源)。
4，調度程式發現有優先權更高的任務到達(高優先權任務可能被中斷或定時器任務喚醒，再或被當前運行的任務喚醒，等等)，則調度程式立即在當前任務堆疊中保存當前cpu暫存器的所有數據，重新從高優先權任務的堆疊中載入暫存器數據到cpu，此時高優先權的任務開始運行。重複第3步。
5，如果當前任務因等待資源而主動放棄cpu使用權，則該任務將從就緒佇列中刪除，加入等待佇列，此時重複第3步。
所有任務都採用RR調度策略時
1，創建任務時指定調度參數為RR，並設定任務的實時優先權和nice值(nice值將會轉換為該任務的時間片的長度)。
2，如果沒有等待資源，則將該任務加入到就緒佇列中。
3，調度程式遍歷就緒佇列，根據實時優先權計算調度權值(1000+rt_priority)，選擇權值最高的任務使用cpu。
4，如果就緒佇列中的RR任務時間片為0，則會根據nice值設定該任務的時間片，同時將該任務放入就緒佇列的末尾。重複步驟3。
5，當前任務由於等待資源而主動退出cpu，則其加入等待佇列中。重複步驟3。
系統中既有分時調度，又有時間片輪轉調度和先進先出調度
1，RR調度和FIFO調度的進程屬於實時進程，以分時調度的進程是非實時進程。
2，當實時進程準備就緒後，如果當前cpu正在運行非實時進程，則實時進程立即搶占非實時進程。
3，RR進程和FIFO進程都採用實時優先權做為調度的權值標準，RR是FIFO的一個延伸。FIFO時，如果兩個進程的優先權一樣，則這兩個優先權一樣的進程具體執行哪一個是由其在佇列中的未知決定的，這樣導致一些不公正性(優先權是一樣的，為什麼要讓你一直運行？)，如果將兩個優先權一樣的任務的調度策略都設為RR，則保證了這兩個任務可以循環執行，保證了公平。
策略
調度程式運行時，要在所有處於可運行狀態的進程之中選擇最值得運行的進程投入運行。選擇進程的依據是什麼呢？在每個進程的task_struct 結構中有這么四項：
policy， priority ， counter， rt_priority
這四項就是調度程式選擇進程的依據.其中，policy是進程的調度策略，用來區分兩種進程-實時和普通；priority是進程(實時和普通)的優先權；counter 是進程剩餘的時間片，它的大小完全由priority決定；rt_priority是實時優先權，這是實時進程所特有的，用於實時進程間的選擇。
首先，Linux 根據policy從整體上區分實時進程和普通進程，因為實時進程和普通進程度調度是不同的，它們兩者之間，實時進程應該先於普通進程而運行，然後，對於同一類型的不同進程，採用不同的標準來選擇進程：
對於普通進程，Linux採用動態優先調度，選擇進程的依據就是進程counter的大小。進程創建時，優先權priority被賦一個初值，一般為0～70之間的數字，這個數字同時也是計數器counter的初值，就是說進程創建時兩者是相等的。字面上看，priority是“優先權”、counter是“計數器”的意思，然而實際上，它們表達的是同一個意思-進程的“時間片”。Priority代表分配給該進程的時間片，counter表示該進程剩餘的時間片。在進程運行過程中，counter不斷減少，而priority保持不變，以便在counter變為0的時候（該進程用完了所分配的時間片）對counter重新賦值。當一個普通進程的時間片用完以後，並不馬上用priority對counter進行賦值，只有所有處於可運行狀態的普通進程的時間片(p->；；counter==0)都用完了以後，才用priority對counter重新賦值，這個普通進程才有了再次被調度的機會。這說明，普通進程運行過程中，counter的減小給了其它進程得以運行的機會，直至counter減為0時才完全放棄對CPU的使用，這就相對於優先權在動態變化，所以稱之為動態優先調度。至於時間片這個概念，和其他不同作業系統一樣的，Linux的時間單位也是“時鐘滴答”，只是不同作業系統對一個時鐘滴答的定義不同而已（Linux為10ms）。進程的時間片就是指多少個時鐘滴答，比如，若priority為20，則分配給該進程的時間片就為20個時鐘滴答，也就是20*10ms=200ms。Linux中某個進程的調度策略(policy)、優先權(priority)等可以作為參數由用戶自己決定，具有相當的靈活性。核心創建新進程時分配給進程的時間片預設為200ms(更準確的，應為210ms)，用戶可以通過系統調用改變它。
對於實時進程，Linux採用了兩種調度策略，即FIFO(先來先服務調度)和RR（時間片輪轉調度）。因為實時進程具有一定程度的緊迫性，所以衡量一個實時進程是否應該運行，Linux採用了一個比較固定的標準。實時進程的counter只是用來表示該進程的剩餘時間片，並不作為衡量它是否值得運行的標準，這和普通進程是有區別的。上面已經看到，每個進程有兩個優先權，實時優先權就是用來衡量實時進程是否值得運行的。
這一切看來比較麻煩，但實際上Linux中的實現相當簡單。Linux用函式goodness()來衡量一個處於可運行狀態的進程值得運行的程度。該函式綜合了上面提到的各個方面，給每個處於可運行狀態的進程賦予一個權值(weight)，調度程式以這個權值作為選擇進程的唯一依據。
Linux根據policy的值將進程總體上分為實時進程和普通進程，提供了三種調度算法：一種傳統的Unix調度程式和兩個由POSIX.1b(原名為POSIX.4)作業系統標準所規定的“實時”調度程式。但這種實時只是軟實時，不滿足諸如中斷等待時間等硬實時要求，只是保證了當實時進程需要時一定只把CPU分配給實時進程。
非實時進程有兩種優先權，一種是靜態優先權，另一種是動態優先權。實時進程又增加了第三種優先權，實時優先權。優先權是一些簡單的整數，為了決定應該允許哪一個進程使用CPU的資源，用優先權代表相對權值-優先權越高，它得到CPU時間的機會也就越大。
？ 靜態優先權(priority)-不隨時間而改變，只能由用戶進行修改。它指明了在被迫和其他進程競爭CPU之前，該進程所應該被允許的時間片的最大值（但很可能的，在該時間片耗盡之前，進程就被迫交出了CPU）。
？ 動態優先權(counter)-只要進程擁有CPU，它就隨著時間不斷減小；當它小於0時，標記進程重新調度。它指明了在這個時間片中所剩餘的時間量。
？ 實時優先權(rt_priority)-指明這個進程自動把CPU交給哪一個其他進程；較高權值的進程總是優先於較低權值的進程。如果一個進程不是實時進程，其優先權就是0，所以實時進程總是優先於非實時進程的（但實際上，實時進程也會主動放棄CPU）。
當policy分別為以下值時：
1) SCHED_OTHER：這是普通的用戶進程，進程的預設類型，採用動態優先調度策略，選擇進程的依據主要是根據進程goodness值的大小。這種進程在運行時，可以被高goodness值的進程搶先。
2) SCHED_FIFO：這是一種實時進程，遵守POSIX1.b標準的FIFO(先入先出)調度規則。它會一直運行，直到有一個進程因I/O阻塞，或者主動釋放CPU，或者是CPU被另一個具有更高rt_priority的實時進程搶先。在Linux實現中，SCHED_FIFO進程仍然擁有時間片-只有當時間片用完時它們才被迫釋放CPU。因此，如同POSIX1.b一樣，這樣的進程就象沒有時間片(不是採用分時)一樣運行。Linux中進程仍然保持對其時間片的記錄（不修改counter）主要是為了實現的方便，同時避免在調度代碼的關鍵路徑上出現條件判斷語句 if (！(current->；；policy&；；SCHED_FIFO)){...}-要知道，其他大量非FIFO進程都需要記錄時間片，這種多餘的檢測只會浪費CPU資源。（一種最佳化措施，不該將執行時間占10%的代碼的運行時間減少到50%；而是將執行時間占90%的代碼的運行時間減少到95%。0.9+0.1*0.5=0.95>；；0.1+0.9*0.9=0.91）
3) SCHED_RR：這也是一種實時進程，遵守POSIX1.b標準的RR(循環round-robin)調度規則。除了時間片有些不同外，這種策略與SCHED_FIFO類似。當SCHED_RR進程的時間片用完後，就被放到SCHED_FIFO和SCHED_RR佇列的末尾。
只要系統中有一個實時進程在運行，則任何SCHED_OTHER進程都不能在任何CPU運行。每個實時進程有一個rt_priority，因此，可以按照rt_priority在所有SCHED_RR進程之間分配CPU。其作用與SCHED_OTHER進程的priority作用一樣。只有root用戶能夠用系統調用sched_setscheduler，來改變當前進程的類型(sys_nice，sys_setpriority)。
此外，核心還定義了SCHED_YIELD，這並不是一種調度策略，而是截取調度策略的一個附加位。如同前面說明的一樣，如果有其他進程需要CPU，它就提示調度程式釋放CPU。特別要注意的就是這甚至會引起實時進程把CPU釋放給非實時進程。
主要函式
真正執行調度的函式是schedule(void)，它選擇一個最合適的進程執行，並且真正進行上下文切換，使得選中的進程得以執行。而reschedule_idle(struct task_struct *p)的作用是為進程選擇一個合適的CPU來執行，如果它選中了某個CPU，則將該CPU上當前運行進程的need_resched標誌置為1，然後向它發出一個重新調度的處理機間中斷，使得選中的CPU能夠在中斷處理返回時執行schedule函式，真正調度進程p在CPU上執行。在schedule()和reschedule_idle()中調用了goodness()函式。goodness()函式用來衡量一個處於可運行狀態的進程值得運行的程度。此外，在schedule()函式中還調用了schedule_tail()函式；在reschedule_idle()函式中還調用了reschedule_idle_slow()。這些函式的實現對理解SMP的調度非常重要，下面一一分析這些函式。先給出每個函式的主要流程圖，然後給出原始碼，並加注釋。
goodness()函式分析
goodness()函式計算一個處於可運行狀態的進程值得運行的程度。一個任務的goodness是以下因素的函式：正在運行的任務、想要運行的任務、當前的CPU。goodness返回下面兩類值中的一個：1000以下或者1000以上。1000或者1000以上的值只能賦給“實時”進程，從0到999的值只能賦給普通進程。實際上，在單處理器情況下，普通進程的goodness值只使用這個範圍底部的一部分，從0到41。在SMP情況下，SMP模式會優先照顧等待同一個處理器的進程。不過，不管是UP還是SMP，實時進程的goodness值的範圍是從1001到1099。
goodness()函式其實是不會返回-1000的，也不會返回其他負值。由於idle進程的counter值為負，所以如果使用idle進程作為參數調用goodness，就會返回負值，但這是不會發生的。
goodness()是個簡單的函式，但是它是linux調度程式不可缺少的部分。運行佇列中的每個進程每次執行schedule時都要調度它，因此它的執行速度必須很快。
//在/kernel/sched.c中
static inline int goodness(struct task_struct * p， int this_cpu， struct mm_struct *this_mm)
{ int weight；
if (p->；；policy ！= SCHED_OTHER) {/*如果是實時進程，則*/
weight = 1000 + p->；；rt_priority；
goto out；
}
/* 將counter的值賦給weight，這就給了進程一個大概的權值，counter中的值表示進程在一個時間片內，剩下要運行的時間.*/
weight = p->；；counter；
if (！weight) /* weight==0，表示該進程的時間片已經用完，則直接轉到標號out*/
goto out；
#ifdef __SMP__
/*在SMP情況下，如果進程將要運行的CPU與進程上次運行的CPU是一樣的，則最有利，因此，假如進程上次運行的CPU與當前CPU一致的話，權值加上PROC_CHANGE_PENALTY，這個宏定義為20。*/
if (p->；；processor == this_cpu)
weight += PROC_CHANGE_PENALTY；
#endif
weight += 1；
weight += p->；；priority； /* 權值加上進程的優先權*/
out：
return weight； /* 返回值作為進程調度的唯一依據，誰的權值大，就調度誰運行*/
}
schedule()函式分析
schedule()函式的作用是，選擇一個合適的進程在CPU上執行，它僅僅根據'goodness'來工作。對於SMP情況，除了計算每個進程的加權平均運行時間外，其他與SMP相關的部分主要由goodness()函式來體現。
流程：
①將prev和next設定為schedule最感興趣的兩個進程：其中一個是在調用schedule時正在運行的進程(prev)，另外一個應該是接著就給予CPU的進程（next）。注意：prev和next可能是相同的-schedule可以重新調度已經獲得cpu的進程.
②中斷處理程式運行“下半部分”.
③核心實時系統部分的實現，循環調度程式（SCHED_RR）通過移動“耗盡的”RR進程-已經用完其時間片的進程-到佇列末尾，這樣具有相同優先權的其他RR進程就可以獲得CPU了。同時，這補充了耗盡進程的時間片。
④由於代碼的其他部分已經決定了進程必須被移進或移出TASK_RUNNING狀態，所以會經常使用schedule，例如，如果進程正在等待的硬體條件已經發生，所以如果必要，這個switch會改變進程的狀態。如果進程已經處於TASK_RUNNING狀態，它就無需處理了。如果它是可以中斷的（等待信號），並且信號已經到達了進程，就返回TASK_RUNNING狀態。在所以其他情況下（例如，進程已經處於TASK_UNINTERRUPTIBLE狀態了），應該從運行佇列中將進程移走。
⑤將p初始化為運行佇列的第一個任務；p會遍歷佇列中的所有任務。
⑥c記錄了運行佇列中所有進程最好的“goodness”-具有最好“goodness”的進程是最易獲得CPU的進程。goodness的值越高越好。
⑦遍歷執行任務鍊表，跟蹤具有最好goodness的進程。
⑧這個循環中只考慮了唯一一個可以調度的進程。在SMP模式下，只有任務不在cpu上運行時，即can_schedule宏返回為真時，才會考慮該任務。在UP情況下，can_schedule宏返回恆為真.
⑨如果循環結束後，得到c的值為0。說明運行佇列中的所有進程的goodness值都為0。goodness的值為0，意味著進程已經用完它的時間片，或者它已經明確說明要釋放CPU。在這種情況下，schedule要重新計算進程的counter；新counter的值是原來值的一半加上進程的靜態優先權（priortiy），除非進程已經釋放CPU，否則原來counter的值為0。因此，schedule通常只是把counter初始化為靜態優先權。（中斷處理程式和由另一個處理器引起的分支在schedule搜尋goodness最大值時都將增加此循環中的計數器，因此由於這個原因計數器可能不會為0。顯然，這很罕見。）在counter的值計算完成後，重新開始執行這個循環，找具有最大goodness的任務。
⑩如果schedule已經選擇了一個不同於前面正在執行的進程來調度，那么就必須掛起原來的進程並允許新的進程運行。這時調用switch_to來進行切換。
