進程調度

1.多態性 從誕生、運行，直至消滅。

2.多個不同的進程可以包括相同的程序

3.三種基本狀態 它們之間可進行轉換

4.併發性併發執行的進程輪流佔用處理器

1.等待態：等待某個事件的完成；

2.就緒態：等待系統分配處理器以便運行；

3.運行態：佔有處理器正在運行。

運行態→等待態 往往是由於等待外設，等待主存等資源分配或等待人工干預而引起的。

等待態→就緒態 則是等待的條件已滿足，只需分配到處理器後就能運行。

運行態→就緒態 不是由於自身原因，而是由外界原因使運行狀態的進程讓出處理器，這時候就變成就緒態。例如時間片用完，或有更高優先級的進程來搶佔處理器等。

就緒態→運行態 系統按某種策略選中就緒隊列中的一個進程佔用處理器，此時就變成了運行態

高級調度：(High-Level Scheduling)又稱為作業調度，它決定把後備作業調入內存運行；

低級調度：(Low-Level Scheduling)又稱為進程調度，它決定把就緒隊列的某進程獲得CPU；

中級調度：(Intermediate-Level Scheduling)又稱為在虛擬存儲器中引入，在內、外存對換區進行進程對換。

分派程序一旦把處理機分配給某進程後便讓它一直運行下去，直到進程完成或發生某事件而阻塞時，才把處理機分配給另一個進程。

當一個進程正在運行時，系統可以基於某種原則，剝奪已分配給它的處理機，將之分配給其它進程。剝奪原則有：優先權原則、短進程優先原則、時間片原則。

例如，有三個進程P1、P2、P3先後到達，它們分別需要20、4和2個單位時間運行完畢。

假如它們就按P1、P2、P3的順序執行，且不可剝奪，則三進程各自的週轉時間分別為20、24、

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)

該算法從就緒隊列中選出下一個“CPU執行期最短”的進程，為之分配處理機。

例如，在就緒隊列中有四個進程P1、P2、P3和P4，它們的下一個執行期分別是16、12、4和3個單位時間，執行情況如下圖：

P1、P2、P3和P4的週轉時間分別為35、19、7、3，平均週轉時間為16。

該算法雖可獲得較好的調度性能，但難以準確地知道下一個CPU執行期，而只能根據每一個進程的執行歷史來預測。

前幾種算法主要用於批處理系統中，不能作為分時系統中的主調度算法，在分時系統中，都採用時間片輪轉法。

簡單輪轉法：系統將所有就緒進程按FIFO規則排隊，按一定的時間間隔把處理機分配給隊列中的進程。這樣，就緒隊列中所有進程均可獲得一個時間片的處理機而運行。

多級隊列方法：將系統中所有進程分成若干類，每類為一級。

多級反饋隊列方式是在系統中設置多個就緒隊列，並賦予各隊列以不同的優先權。

引起原因

正在執行的進程執行完畢或因發生某事件而不能再繼續執行；

執行中的進程因提出I/O請求而暫停執行；

在進程通信或同步過程中執行了某種原語操作如P操作、阻塞、掛起原語等；

在可剝奪式調度中，有比當前進程優先權更高的進程進入就緒隊列；

在時間片輪轉法中，時間片完；

△通常系統是按先來先服務或優先權形式來組織調度隊列。

其中，RQ為就緒隊列指針，EP為運行隊列指針。

進程調度的具體功能可總結為如下幾點：作為進程調度的準備，進程管理模塊必須將系統中各進程的執行情況和狀態特徵記錄在各進程的PCB表中。並且，根據各進程的狀態特徵和資源需求等、進程管理模塊還將各進程的PCB表排成相應的隊列並進行動態隊列轉接。進程調度模塊通過PCB變化來掌握系統中存在的所有進程的執行情況和狀態特徵，並在適當的時機從就緒隊列中選擇出一個進程佔據處理機。

進程調度的主要功能是按照一定的策略選擇—個處於就緒狀態的進程，使其獲得處理機執行。根據不同的系統設計目的，有各種各樣的選擇策略，例如系統開銷較少的靜態優先數調度法，適合於分時系統的輪轉法(Round RoLin)和多級互饋輪轉法(Round Robin with Multip1e feedback)等。這些選擇策略決定了調度算法的性能。

—個進程的上下文(context)包括進程的狀態、有關變量和數據結構的值、機器寄存器的值和PCB以及有關程序、數據等。一個進程的執行是在進程的上下文中執行。當正在執行的進程由於某種原因要讓出處理機時，系統要做進程上下文切換，以使另一個進程得以執行。當進行上下文切換時點統要首先檢查是否允許做上下文切換(在有些情況下，上下文切換是不允許的，例如系統正在執行某個不允許中斷的原語時)。然後，系統要保留有關被切換進程的足夠信息，以便以後切換回該進程時，順利恢復該進程的執行。在系統保留了CPU現場之後，調度程序選擇一個新的處於就緒狀態的進程、並裝配該進程的上下文，使CPU的控制權掌握在被選中進程手中。

引起進程調度的原因有以下幾類

進程調度發生在什麼時機呢？這與引起進程調度的原因以及進程調度的方式有關。

(1)正在執行的進程執行完畢。這時，如果不選擇新的就緒進程執行，將浪費處理機資源。

(2)執行中進程自己調用阻塞原語將自己阻塞起來進入睡眠等狀態。

(3)執行中進程調用了P原語操作，從而因資源不足而被阻塞；或調用了v原語操作激活了等待資源的進程隊列。

(4)執行中進程提出I/O請求後被阻塞。

(5)在分時系統中時間片已經用完。

(6)在執行完系統調用等系統程序後返回用户進程時，這時可看作系統進程執行完畢，從而可調度選擇一新的用户進程執行。

以上都是在可剝奪方式下的引起進程調度的原因。在CPU執行方式是可剝奪時．還有

(7)就緒隊列中的某進程的優先級變得高於當前執行進程的優先級，從而也將引發進程調度。

兩種佔用CPU的方式

可剝奪式 (可搶佔式preemptive)：就緒隊列中一旦有優先級高於當前執行進程優先級的進程存在時，便立即發生進程調度，轉讓處理機。

不可剝奪式 (不可搶佔式non_preemptive)：即使在就緒隊列存在有優先級高於當前執行進程時，當前進程仍將佔用處理機直到該進程自己因調用原語操作或等待I/O而進入阻塞、睡眠狀態，或時間片用完時才重新發生調度讓出處理機。

進程上下文由正文段、數據段、硬件寄存器的內容以及有關數據結構等組成。硬件寄存器主要包括存放CPU將要執行的下條指令虛擬地址的程序計數器PC，指出機器與進程相關聯的硬件狀態的處理機狀態寄存器PS，存放過程調用(或系統調用)時所傳遞參數的通用寄存器R以及堆棧指針寄存器S等。數據結構則包括PCB等在內的所有與執行該進程有關的管理和控制用表格、數組、鏈等。在發生進程調度時系統要做進程上下文切換。

n保存處理器的上下文，包括程序計數器和其它寄存器

n用新狀態和其它相關信息更新正在運行進程的PCB

n把原來的進程移至合適的隊列-就緒、阻塞

n選擇另一個要執行的進程

n更新被選中進程的PCB

n從被選中進程中重裝入

CPU 上下文

進程調度雖然是在系統內部的低級調度，但進程調度的優劣直接影響作業調度的性能。那麼，怎樣評價進程調度的優劣呢？反映作業調度優劣的週轉時間和平均週轉時間只在某種程度上反映了進程調度的性能，例如，其執行時間部分中實際上包含有進程等待(包括就緒狀態時的等待)時間，而進程等待時間的多少是要依靠進程調度策略和等待事件何時發生等來決定的。因此，進程調度性能的商量是操作系統設計的一個重要指標。

我們説進程調度性能的衡量方法可分為定形和定量兩種。在定形衡量方面，首先是調度的可靠性。包括一次進程調度是否可能引起數據結構的破壞等。這要求我們對調度時機的選擇和保存CPU現場十分謹慎。另外，簡潔性也是衡量進程調度的一個重要指標，由於調度程序的執行涉及到多個進程和必須進行上下文切換，如果調度程序過於繁瑣和複雜，將會耗去較大的系統開銷。這在用户進程調用系統調用較多的情況下，將會造成響應時間大幅度增加。

進程調度的定量評價包括CPU的利用率評價、進程在就緒隊列中的等待時間與執行時間之比等。實際上由於進程進入就緒隊列的隨機模型很難確定，而且進程上下文切換等也將影響進程的執行效率，LL而對進程調度進行解析是很困難的。一般情況下，大多利用模擬或測試系統響應時間的方法來評價進程調度的性能。

實時系統與其他操作系統不同在於計算機要能及時響應外部事件的請求，在規定的嚴格時間內完成對該事件的處理，並控制所有實時設備和實時任務協調一致地工作，對於對時間要求嚴格性的不同，實時系統又分為硬實時系統和軟實時系統，其中硬實時系統是指這種時限的要求是絕對的，任何一個實時任務都能夠在時限之前完成；而軟實時系統的要求就沒有這麼嚴格，允許偶爾有實時任務不滿足時限的要求.實時系統一般用於嵌入式的系統中，分為實時過程控制和實時通信處理，其中實時過程控制主要用於工業控制，軍事控制領域；時事通信用於電信，銀行，飛機訂票等領域，正是由於在這些特殊領域的運用使得實時操作系統設計時主要追求的是：對外部請求在嚴格時間範圍內做出反應，有高可靠性和完備性.為達到時間要求，進程的調度策略就顯得尤為重要.

最簡單最直觀的進程調度策略是基於優先級的調度，多數實時系統採用基於優先級的調度，每個進程根據它重要程度的不同被賦予不同的優先級，調度器在每次調度時，總選擇優先級最高的進程開始執行.

首先要考慮的問題是如何分配優先級，對於進程優先級的分配可以採用靜態和動態兩種方式，靜態優先級調度算法：這種調度算法給那些系統中得到運行的所有進程都靜態地分配一個優先級.靜態優先級的分配可以根據應用的屬性來進行，比如進程的週期，用户優先級，或者其它的預先確定的策略.單調率算法(RM)調度算法是一種典型的靜態優先級調度算法，它根據進程的執行週期的長短來決定調度優先級，那些具有小的執行週期的進程具有較高的優先級.動態優先級調度算法：這種調度算法根據進程的資源需求來動態地分配進程的優先級，其目的就是在資源分配和調度時有更大的靈活性.在實時系統中，最早期限優先算法(EDF)算法是使用最多的一種動態優先級調度算法，該算法給就緒隊列中的各個進程根據它們的截止期限(Deadline)來分配優先級，具有最近的截止期限的進程具有最高的優先級.

分配好優先級之後下一個要考慮的問題是何時讓高優先級進程掌握CPU的使用權，這取決於操作系統的內核，有不可搶佔式和可搶佔式兩種.

不可搶佔式內核要求每個進程自我放棄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 卻保持空閒的情況.

對於不同要求下的實時系統可以採用不同的進程調度策略來進行設計，也可以將這些方法進行綜合之後得到更適合的調度策略.

調度程序運行時，要在所有可運行狀態的進程中選擇最值得運行的進程投入運行。選擇進程的依據是什麼呢？在每個進程的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的不同：

當採用SHCED_RR策略的進程的時間片用完，系統將重新分配時間片，並置於就緒隊列尾。放在隊列尾保證了所有具有相同優先級的RR任務的調度公平。

SCHED_FIFO一旦佔用cpu則一直運行。一直運行直到有更高優先級任務到達或自己放棄。

如果有相同優先級的實時進程（根據優先級計算的調度權值是一樣的）已經準備好，FIFO時必須等待該進程主動放棄後才可以運行這個優先級相同的任務。而RR可以讓每個任務都執行一段時間。

RR和FIFO都只用於實時任務。

創建時優先級大於0(1-99)。

按照可搶佔優先級調度算法進行。

就緒態的實時任務立即搶佔非實時任務。

1，創建任務指定採用分時調度策略，並指定優先級nice值(-20~19)。

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

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

4，調度程序遍歷就緒隊列中的任務，通過對每個任務動態優先級的計算(counter+20-nice)結果，選擇計算結果最大的一個去運行，當這個時間片用完後(counter減至0)或者主動放棄cpu時，該任務將被放在就緒隊列末尾(時間片用完)或等待隊列(因等待資源而放棄cpu)中。

5，此時調度程序重複上面計算過程，轉到第4步。

6，當調度程序發現所有就緒任務計算所得的權值都為不大於0時，重複第2步。

1，創建進程時指定採用FIFO，並設置實時優先級rt_priority(1-99)。

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

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

4，調度程序發現有優先級更高的任務到達(高優先級任務可能被中斷或定時器任務喚醒，再或被當前運行的任務喚醒，等等)，則調度程序立即在當前任務堆棧中保存當前cpu寄存器的所有數據，重新從高優先級任務的堆棧中加載寄存器數據到cpu，此時高優先級的任務開始運行。重複第3步。

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

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）。

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是以下因素的函數：正在運行的任務、想要運行的任務、當前的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

if (p->；；mm == this_mm) /*進程p與當前運行進程，是同一個進程的不同線程，或者是共享地址空間的不同進程，優先選擇，權值加1*/

weight += 1；

weight += p->；；priority； /* 權值加上進程的優先級*/

out：

return weight； /* 返回值作為進程調度的唯一依據，誰的權值大，就調度誰運行*/

}

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來進行切換。