linux進程調度的隊列

『壹』 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：作業在運行期間所要使用的資源的多少；

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

『貳』 linux 內核中關於進程調度的內容在哪個目錄下schele函數在哪裡

linux進程調度中最基本的數據結構是struct runqueue；有關於此結構的隊列在kernel/sched.c，此隊列包含了處理器的所有可執行進程的信息。
每個運行隊列都有兩個優先順序數組，一個活躍的和一個過期的，此數組也是在kernel/sched.c中含有。
schele函數定義也是在kernel/sched.c中。

『叄』 linux 內核中，工作隊列和線程有什麼區別

一句話概括：根本就是兩個不同的概念，差別很大。
簡單的說：
一般來說，線程是windows上的概念，windows區分進程和線程。而在linux上，統一叫進程，進程是完成某項任務所需資源的集合，同時也是linux基本的執行單元。
工作隊列是一個等待被執行的任務鏈表，由專有的線程來調度、執行。很多linux驅動的中斷下半部的實現，都是採用工作隊列的方式。

作者：陳彬
鏈接：
來源：知乎
著作權歸作者所有，轉載請聯系作者獲得授權。

『肆』 linux進程調度的三種策略是什麼

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可以讓每個任務都執行一段時間。

相同點：
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,則保證了這兩個任務可以循環執行，保證了公平。

Ingo Molnar-實時補丁
為了能並入主流內核，Ingo Molnar的實時補丁也採用了非常靈活的策略，它支持四種搶占模式：
1．No Forced Preemption (Server)，這種模式等同於沒有使能搶占選項的標准內核，主要適用於科學計算等伺服器環境。
2．Voluntary Kernel Preemption (Desktop)，這種模式使能了自願搶占，但仍然失效搶占內核選項，它通過增加搶占點縮減了搶占延遲，因此適用於一些需要較好的響應性的環境，如桌面環境，當然這種好的響應性是以犧牲一些吞吐率為代價的。
3．Preemptible Kernel (Low-Latency Desktop)，這種模式既包含了自願搶占，又使能了可搶占內核選項，因此有很好的響應延遲，實際上在一定程度上已經達到了軟實時性。它主要適用於桌面和一些嵌入式系統，但是吞吐率比模式2更低。
4．Complete Preemption (Real-Time)，這種模式使能了所有實時功能，因此完全能夠滿足軟實時需求，它適用於延遲要求為100微秒或稍低的實時系統。
實現實時是以犧牲系統的吞吐率為代價的，因此實時性越好，系統吞吐率就越低。

『伍』 linux內核怎麼調度系統

1.調度器的概述

多任務操作系統分為非搶占式多任務和搶占式多任務。與大多數現代操作系統一樣，Linux採用的是搶占式多任務模式。這表示對CPU的佔用時間由操作系統決定的，具體為操作系統中的調度器。調度器決定了什麼時候停止一個進程以便讓其他進程有機會運行，同時挑選出一個其他的進程開始運行。

2.調度策略

在Linux上調度策略決定了調度器是如何選擇一個新進程的時間。調度策略與進程的類型有關，內核現有的調度策略如下：

#define SCHED_NORMAL 0#define SCHED_FIFO 1#define SCHED_RR 2#define SCHED_BATCH 3/* SCHED_ISO: reserved but not implemented yet */#define SCHED_IDLE 5

0: 默認的調度策略，針對的是普通進程。
1：針對實時進程的先進先出調度。適合對時間性要求比較高但每次運行時間比較短的進程。
2：針對的是實時進程的時間片輪轉調度。適合每次運行時間比較長得進程。
3：針對批處理進程的調度，適合那些非交互性且對cpu使用密集的進程。
SCHED_ISO：是內核的一個預留欄位，目前還沒有使用
5：適用於優先順序較低的後台進程。
註：每個進程的調度策略保存在進程描述符task_struct中的policy欄位

3.調度器中的機制

內核引入調度類（struct sched_class）說明了調度器應該具有哪些功能。內核中每種調度策略都有該調度類的一個實例。（比如：基於公平調度類為：fair_sched_class，基於實時進程的調度類實例為：rt_sched_class），該實例也是針對每種調度策略的具體實現。調度類封裝了不同調度策略的具體實現，屏蔽了各種調度策略的細節實現。
調度器核心函數schele()只需要調用調度類中的介面，完成進程的調度，完全不需要考慮調度策略的具體實現。調度類連接了調度函數和具體的調度策略。

• 武特師兄關於sche_class和sche_entity的解釋，一語中的。

• 調度類就是代表的各種調度策略，調度實體就是調度單位，這個實體通常是一個進程，但是自從引入了cgroup後，這個調度實體可能就不是一個進程了，而是一個組

4.schele()函數

linux 支持兩種類型的進程調度，實時進程和普通進程。實時進程採用SCHED_FIFO 和SCHED_RR調度策略，普通進程採用SCHED_NORMAL策略。
preempt_disable()：禁止內核搶占
cpu_rq（）：獲取當前cpu對應的就緒隊列。
prev = rq->curr;獲取當前進程的描述符prev
switch_count = &prev->nivcsw;獲取當前進程的切換次數。
update_rq_clock() ：更新就緒隊列上的時鍾
clear_tsk_need_resched()清楚當前進程prev的重新調度標志。
deactive_task():將當前進程從就緒隊列中刪除。
put_prev_task() :將當前進程重新放入就緒隊列
pick_next_task():在就緒隊列中挑選下一個將被執行的進程。
context_switch():進行prev和next兩個進程的切換。具體的切換代碼與體系架構有關，在switch_to()中通過一段匯編代碼實現。
post_schele():進行進程切換後的後期處理工作。

5.pick_next_task函數

選擇下一個將要被執行的進程無疑是一個很重要的過程，我們來看一下內核中代碼的實現
對以下這段代碼說明：
1.當rq中的運行隊列的個數(nr_running)和cfs中的nr_runing相等的時候，表示現在所有的都是普通進程，這時候就會調用cfs演算法中的pick_next_task(其實是pick_next_task_fair函數)，當不相等的時候，則調用sched_class_highest(這是一個宏，指向的是實時進程)，這下面的這個for(;;)循環中，首先是會在實時進程中選取要調度的程序（p = class->pick_next_task(rq);）。如果沒有選取到，會執行class=class->next;在class這個鏈表中有三種類型（fair,idle,rt）.也就是說會調用到下一個調度類。

• static inline struct task_struct *pick_next_task(struct rq *rq){ const struct sched_class *class; struct task_struct *p; /*


• * Optimization: we know that if all tasks are in


• * the fair class we can call that function directly:


• *///基於公平調度的普通進程


• if (likely(rq->nr_running == rq->cfs.nr_running)) {


• p = fair_sched_class.pick_next_task(rq); if (likely(p)) return p;


• }//基於實時調度的實時進程


• class = sched_class_highest; for ( ; ; ) {


• p = class->pick_next_task(rq); //實時進程的類


• if (p) return p; /*


• * Will never be NULL as the idle class always


• * returns a non-NULL p:


• */


• class = class->next; //rt->next = fair; fair->next = idle


• }


• }



在這段代碼中體現了Linux所支持的兩種類型的進程，實時進程和普通進程。回顧下：實時進程可以採用SCHED_FIFO 和SCHED_RR調度策略，普通進程採用SCHED_NORMAL調度策略。
在這里首先說明一個結構體struct rq,這個結構體是調度器管理可運行狀態進程的最主要的數據結構。每個cpu上都有一個可運行的就緒隊列。剛才在pick_next_task函數中看到了在選擇下一個將要被執行的進程時實際上用的是struct rq上的普通進程的調度或者實時進程的調度，那麼具體是如何調度的呢？在實時調度中，為了實現O(1)的調度演算法，內核為每個優先順序維護一個運行隊列和一個DECLARE_BITMAP,內核根據DECLARE_BITMAP的bit數值找出非空的最高級優先隊列的編號，從而可以從非空的最高級優先隊列中取出進程進行運行。
我們來看下內核的實現

• struct rt_prio_array {


• DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */


• struct list_head queue[MAX_RT_PRIO];


• };



數組queue[i]裡面存放的是優先順序為i的進程隊列的鏈表頭。在結構體rt_prio_array 中有一個重要的數據構DECLARE_BITMAP，它在內核中的第一如下：

• define DECLARE_BITMAP(name,bits)


• unsigned long name[BITS_TO_LONGS(bits)]



5.1對於實時進程的O(1)演算法

這個數據是用來作為進程隊列queue[MAX_PRIO]的索引點陣圖。bitmap中的每一位與queue[i]對應，當queue[i]的進程隊列不為空時，Bitmap的相應位就為1，否則為0，這樣就只需要通過匯編指令從進程優先順序由高到低的方向找到第一個為1的位置，則這個位置就是就緒隊列中最高的優先順序（函數sched_find_first_bit()就是用來實現該目的的）。那麼queue[index]->next就是要找的候選進程。
如果還是不懂，那就來看兩個圖


由結果可以看出當nice的值越小的時候，其睡眠時間越短，則表示其優先順序升高了。

7.關於獲取和設置優先順序的系統調用：sched_getscheler（）和sched_setscheler

• #include <sched.h>#include <stdlib.h>#include <stdio.h>#include <errno.h>#define DEATH(mess) { perror(mess); exit(errno); }void printpolicy (int policy){ /* SCHED_NORMAL = SCHED_OTHER in user-space */



• if (policy == SCHED_OTHER) printf ("policy = SCHED_OTHER = %d ", policy); if (policy == SCHED_FIFO) printf ("policy = SCHED_FIFO = %d ", policy); if (policy == SCHED_RR) printf ("policy = SCHED_RR = %d ", policy);


• }int main (int argc, char **argv){ int policy; struct sched_param p; /* obtain current scheling policy for this process */


• //獲取進程調度的策略


• policy = sched_getscheler (0);


• printpolicy (policy); /* reset scheling policy */



• printf (" Trying sched_setscheler... ");


• policy = SCHED_FIFO;


• printpolicy (policy);


• p.sched_priority = 50; //設置優先順序為50


• if (sched_setscheler (0, policy, &p))


• DEATH ("sched_setscheler:"); printf ("p.sched_priority = %d ", p.sched_priority); exit (0);


• }



輸出結果：

• [root@wang schele]# ./get_schele_policy policy = SCHED_OTHER = 0



• Trying sched_setscheler...


• policy = SCHED_FIFO = 1


• p.sched_priority = 50



可以看出進程的優先順序已經被改變。

『陸』 linux內核進程調度子系統根據什麼演算法選擇最值得運行的進程

你可以查看相關linux書籍關於這部分的介紹。
操作系統這一門課程回答了你的答案。
據我的了解，應該是多級反饋輪轉調度的演算法。
每個進程都是按時間片運行的。每個進程都被分配了優先順序。
每個進程位於調度隊列的某一級上。操作系統根據這個多級隊列來調度。
每個隊列按照FIFO的方式調度。
就這么多了。你可以去圖書館借書看看。

『柒』 linux 進程調度有沒有先來先服務方式

有的，先來先服務就是將來的任務按照時間先後放到隊列裡面，然後一個一個調度。

『捌』 Linux內核中等待隊列的幾種用法

1. 睡眠等待某個條件發生(條件為假時睡眠)：
睡眠方式：wait_event, wait_event_interruptible
喚醒方式：wake_up (喚醒時要檢測條件是否為真，如果還為假則繼續睡眠，喚醒前一定要把條件變為真)
2. 手工休眠方式一：
1)建立並初始化一個等待隊列項
DEFINE_WAIT(my_wait) <== wait_queue_t my_wait; init_wait(&my_wait);
2)將等待隊列項添加到等待隊列頭中，並設置進程的狀態
prepare_to_wait(wait_queue_head_t *queue, wait_queue_t *wait, int state)
3)調用schele()，告訴內核調度別的進程運行
4)schele返回，完成後續清理工作
finish_wait()
3. 手工休眠方式二：
1)建立並初始化一個等待隊列項：
DEFINE_WAIT(my_wait) <== wait_queue_t my_wait; init_wait(&my_wait);
2)將等待隊列項添加到等待隊列頭中：
add_wait_queue
3)設置進程狀態
__set_current_status(TASK_INTERRUPTIBLE);
4)schele()
5)將等待隊列項從等待隊列中移除
remove_wait_queue()
其實，這種休眠方式相當於把手工休眠方式一中的第二步prepare_to_wait拆成兩步做了，即prepare_to_wait <====add_wait_queue + __set_current_status，其他都是一樣的。
4. 老版本的睡眠函數sleep_on(wait_queue_head_t *queue)：

『玖』 操作系統中進程調度策略有哪幾種

linux內核的三種調度方法：

1，SCHED_OTHER 分時調度策略，

2，SCHED_FIFO實時調度策略，先到先服務

3，SCHED_RR實時調度策略，時間片輪轉

實時進程將得到優先調用，實時進程根據實時優先順序決定調度權值，分時進程則通過nice和counter值決定權值，nice越小，counter越大，被調度的概率越大，也就是曾使用了cpu最少的進程將會得到優先調度。

SHCED_RR和SCHED_FIFO的不同：

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

『拾』 Linux 工作隊列和等待隊列的區別

work queue是一種bottom half，中斷處理的後半程，強調的是動態的概念，即work是重點，而queue是其次。
wait queue是一種「任務隊列」，可以把一些進程放在上面睡眠等待某個事件，強調靜態多一些，重點在queue上，即它就是一個queue，這個queue如何調度，什麼時候調度並不重要
等待隊列在內核中有很多用途，尤其適合用於中斷處理，進程同步及定時。這里只說，進程經常必須等待某些事件的發生。例如，等待一個磁碟操作的終止，等待釋放系統資源，或者等待時間經過固定的間隔。
等待隊列實現了在事件上的條件等待，希望等待特定事件的進程把放進合適的等待隊列，並放棄控制權。因此。等待隊列表示一組睡眠的進程，當某一條件為真時，由內核喚醒進程。
等待隊列由循環鏈表實現，其元素包括指向進程描述符的指針。每個等待隊列都有一個等待隊列頭，等待隊列頭是一個類型為wait_queue_head_t的數據結構。
等待隊列鏈表的每個元素代表一個睡眠進程，該進程等待某一事件的發生，描述符地址存放在task欄位中。然而，要喚醒等待隊列中所有的進程有時並不方便。例如，如果兩個或多個進程在等待互斥訪問某一個要釋放的資源，僅喚醒等待隊列中一個才有意義。這個進程佔有資源，而其他進程繼續睡眠可以用DECLARE_WAIT_QUEUE_HEAD(name)宏定義一個新的等待隊列，該宏靜態地聲明和初始化名為name的等待隊列頭變數。 init_waitqueue_head()函數用於初始化已動態分配的wait queue head變數等待隊列可以通過DECLARE_WAITQUEUE()靜態創建，也可以用init_waitqueue_head()動態創建。進程放入等待隊列並設置成不可執行狀態。
工作隊列，workqueue，它允許內核代碼來請求在將來某個時間調用一個函數。用來處理不是很緊急事件的回調方式處理方法.工作隊列的作用就是把工作推後,交由一個內核線程去執行，更直接的說就是寫了一個函數,而現在不想馬上執行它，需要在將來某個時刻去執行，那就得用工作隊列准沒錯。
如果需要用一個可以重新調度的實體來執行下半部處理，也應該使用工作隊列。是唯一能在進程上下文運行的下半部實現的機制。這意味著在需要獲得大量的內存時、在需要獲取信號量時，在需要執行阻塞式的I/O操作時，都會非常有用。