linux多線程調度策略

『壹』 如何查看linux線程的調度策略

方法一抄：PS
在ps命令中，「-T」選項可以開啟線程查看。下面的命令列出了由進程號為<pid>的進程創建的所有線程。
1.$ ps -T -p <pid>

「SID」欄表示線程ID，而「CMD」欄則顯示了線程名稱。

方法二： Top
top命令可以實時顯示各個線程情況。要在top輸出中開啟線程查看，請調用top命令的「-H」選項，該選項會列出所有Linux線程。在top運行時，你也可以通過按「H」鍵將線程查看模式切換為開或關。
1.$ top -H

要讓top輸出某個特定進程<pid>並檢查該進程內運行的線程狀況：
$ top -H -p <pid>

『貳』 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 進程管理之進程調度與切換

我們知道，進程運行需要各種各樣的系統資源，如內存、文件、列印機和最

寶貴的 CPU 等，所以說，調度的實質就是資源的分配。系統通過不同的調度演算法（Scheling Algorithm）來實現這種資源的分配。通常來說，選擇什麼樣的調度演算法取決於資源分配的策略（Scheling Policy）。

有關調度相關的結構保存在 task_struct 中，如下：

active_mm 是為內核線程而引入的，因為內核線程沒有自己的地址空間，為了讓內核線程與普通進程具有統一的上下文切換方式，當內核線程進行上下文切換時，讓切換進來的線程的 active_mm 指向剛被調度出去的進程的 active_mm（如果進程的mm 域不為空，則其 active_mm 域與 mm 域相同）。

在 linux 2.6 中 sched_class 表示該進程所屬的調度器類有3種：

進程的調度策略有5種，用戶可以調用調度器里不同的調度策略：

在每個 CPU 中都有一個自身的運行隊列 rq，每個活動進程只出現在一個運行隊列中，在多個 CPU 上同時運行一個進程是不可能的。

運行隊列是使用如下結構實現的：

tast 作為調度實體加入到 CPU 中的調度隊列中。

系統中所有的運行隊列都在 runqueues 數組中，該數組的每個元素分別對應於系統中的一個 CPU。在單處理器系統中，由於只需要一個就緒隊列，因此數組只有一個元素。

內核也定義了一下便利的宏，其含義很明顯。

Linux、c/c++伺服器開發篇-------我們來聊聊進程的那些事

Linux內核 進程間通信組件的實現

學習地址：C/C++Linux伺服器開發/後台架構師【零聲教育】-學習視頻教程-騰訊課堂

需要C/C++ Linux伺服器架構師學習資料加qun812855908獲取（資料包括 C/C++，Linux，golang技術，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK，ffmpeg 等），免費分享

在分析調度流程之前，我們先來看在什麼情況下要執行調度程序，我們把這種情況叫做調度時機。

Linux 調度時機主要有。

時機1，進程要調用 sleep() 或 exit() 等函數進行狀態轉換，這些函數會主動調用調度程序進行進程調度。

時機2，由於進程的時間片是由時鍾中斷來更新的，因此，這種情況和時機4 是一樣的。

時機3，當設備驅動程序執行長而重復的任務時，直接調用調度程序。在每次反復循環中，驅動程序都檢查 need_resched 的值，如果必要，則調用調度程序 schele() 主動放棄 CPU。

時機4 ， 如前所述， 不管是從中斷、異常還是系統調用返回， 最終都調用 ret_from_sys_call()，由這個函數進行調度標志的檢測，如果必要，則調用調用調度程序。那麼，為什麼從系統調用返回時要調用調度程序呢？這當然是從效率考慮。從系統調用返回意味著要離開內核態而返回到用戶態，而狀態的轉換要花費一定的時間，因此，在返回到用戶態前，系統把在內核態該處理的事全部做完。

Linux 的調度程序是一個叫 Schele() 的函數，這個函數來決定是否要進行進程的切換，如果要切換的話，切換到哪個進程等。

從代碼分析來看，Schele 主要完成了2個功能：

進程上下文切換包括進程的地址空間的切換和執行環境的切換。

對於 switch_mm 處理，關鍵的一步就是它將新進程頁面目錄的起始物理地址裝入到寄存器 CR3 中。CR3 寄存器總是指向當前進程的頁面目錄。

switch_to 把寄存器中的值比如esp等存放到進程thread結構中，保存現場一邊後續恢復，同時調用 __switch_to 完成了堆棧的切換。

在進程的 task_struct 結構中有個重要的成分 thread，它本身是一個數據結構 thread_struct, 裡面記錄著進程在切換時的（系統空間）堆棧指針，取指令地址（也就是「返回地址」）等關鍵性的信息。

關於__switch_to 的工作就是處理 TSS （任務狀態段）。

TSS 全稱task state segment，是指在操作系統進程管理的過程中，任務（進程）切換時的任務現場信息。

linux 為每一個 CPU 提供一個 TSS 段，並且在 TR 寄存器中保存該段。

linux 中之所以為每一個 CPU 提供一個 TSS 段，而不是為每個進程提供一個TSS 段，主要原因是 TR 寄存器永遠指向它，在任務切換的適合不必切換 TR 寄存器，從而減小開銷。

在從用戶態切換到內核態時，可以通過獲取 TSS 段中的 esp0 來獲取當前進程的內核棧 棧頂指針，從而可以保存用戶態的 cs,esp,eip 等上下文。

TSS 在任務切換過程中起著重要作用，通過它實現任務的掛起和恢復。所謂任務切換是指，掛起當前正在執行的任務，恢復或啟動另一任務的執行。

在任務切換過程中，首先，處理器中各寄存器的當前值被自動保存到 TR（任務寄存器）所指定的任務的 TSS 中；然後，下一任務的 TSS 被裝入 TR；最後，從 TR 所指定的 TSS 中取出各寄存器的值送到處理器的各寄存器中。由此可見，通過在 TSS 中保存任務現場各寄存器狀態的完整映象，實現任務的切換。

因此，__switch_to 核心內容就是將 TSS 中的內核空間（0級）堆棧指針換成 next->esp0。這是因為 CPU 在穿越中斷門或者陷阱門時要根據新的運行級別從TSS中取得進程在系統空間的堆棧指針。

thread_struct.esp0 指向進程的系統空間堆棧的頂端。當一個進程被調度運行時，內核會將這個變數寫入 TSS 的 esp0 欄位，表示這個進程進入0級運行時其堆棧的位置。換句話說，進程的 thread_struct 結構中的 esp0 保存著其系統空間堆棧指針。當進程穿過中斷門、陷阱門或者調用門進入系統空間時，處理器會從這里恢復期系統空間棧。

由於棧中變數的訪問依賴的是段、頁、和 esp、ebp 等這些寄存器，所以當段、頁、寄存器切換完以後，棧中的變數就可以被訪問了。

因此 switch_to 完成了進程堆棧的切換，由於被切進的進程各個寄存器的信息已完成切換，因此 next 進程得以執行指令運行。

由於 A 進程在調用 switch_to 完成了與 B 進程堆棧的切換，也即是寄存器中的值都是 B 的，所以 A 進程在 switch_to 執行完後，A停止運行，B開始運行，當過一段時間又把 A 進程切進去後，A 開始從switch_to 後面的代碼開始執行。

schele 的調用流程如下：

『肆』 Linux進程的調度

上回書說到 Linux進程的由來 和 Linux進程的創建 ，其實在同一時刻只能支持有限個進程或線程同時運行(這取決於CPU核數量，基本上一個進程對應一個CPU)，在一個運行的操作系統上可能運行著很多進程，如果運行的進程占據CPU的時間很長，就有可能導致其他進程餓死。為了解決這種問題，操作系統引入了 進程調度器 來進行進程的切換，輪流讓各個進程使用CPU資源。

1）rq： 進程的運行隊列( runqueue)， 每個CPU對應一個 ，包含自旋鎖(spinlock)、進程數量、用於公平調度的CFS信息結構、當前運行的進程描述符等。實際的進程隊列用紅黑樹來維護(通過CFS信息結構來訪問)。

2）cfs_rq： cfs調度的進程運行隊列信息 ，包含紅黑樹的根結點、正在運行的進程指針、用於負載均衡的葉子隊列等。

3）sched_entity： 把需要調度的東西抽象成調度實體 ，調度實體可以是進程、進程組、用戶等。這里包含負載權重值、對應紅黑樹結點、 虛擬運行時vruntime 等。

4）sched_class：把 調度策略(演算法)抽象成調度類 ，包含一組通用的調度操作介面。介面和實現是分離，可以根據調度介面去實現不同的調度演算法，使一個Linux調度程序可以有多個不同的調度策略。

1） 關閉內核搶占 ，初始化部分變數。獲取當前CPU的ID號，並賦值給局部變數CPU， 使rq指向CPU對應的運行隊列 。 標識當前CPU發生任務切換 ，通知RCU更新狀態，如果當前CPU處於rcu_read_lock狀態，當前進程將會放入rnp-> blkd_tasks阻塞隊列，並呈現在rnp-> gp_tasks鏈表中。 關閉本地中斷 ，獲取所要保護的運行隊列的自旋鎖， 為查找可運行進程做准備 。

2） 檢查prev的狀態，更新運行隊列 。如果不是可運行狀態，而且在內核態沒被搶占，應該從運行隊列中 刪除prev進程 。如果是非阻塞掛起信號，而且狀態為TASK_INTER-RUPTIBLE，就把該進程的狀態設置為TASK_RUNNING，並將它 插入到運行隊列 。

3）task_on_rq_queued(prev) 將pre進程插入到運行隊列的隊尾。

4）pick_next_task 選取將要執行的next進程。

5）context_switch(rq, prev, next)進行 進程上下文切換 。

1) 該進程分配的CPU時間片用完。

2) 該進程主動放棄CPU(例如IO操作)。

3) 某一進程搶佔CPU獲得執行機會。

Linux並沒有使用x86 CPU自帶的任務切換機制，需要通過手工的方式實現了切換。

進程創建後在內核的數據結構為task_struct ， 該結構中有掩碼屬性cpus_allowed，4個核的CPU可以有4位掩碼，如果CPU開啟超線程，有一個8位掩碼，進程可以運行在掩碼位設置為1的CPU上。

Linux內核API提供了兩個系統調用 ，讓用戶可以修改和查看當前的掩碼：

1) sched_setaffinity()：用來修改位掩碼。

2) sched_getaffinity()：用來查看當前的位掩碼。

在下次task被喚醒時，select_task_rq_fair根據cpu_allowed里的掩碼來確定將其置於哪個CPU的運行隊列，一個進程在某一時刻只能存在於一個CPU的運行隊列里。

在Nginx中，使用了CPU親和度來完成某些場景的工作：

worker_processes      4;

worker_cpu_affinity 0001001001001000;

上面這個配置說明了4個工作進程中的每一個和一個CPU核掛鉤。如果這個內容寫入Nginx的配置文件中，然後Nginx啟動或者重新載入配置的時候，若worker_process是4，就會啟用4個worker，然後把worker_cpu_affinity後面的4個值當作4個cpu affinity mask，分別調用ngx_setaffinity，然後就把4個worker進程分別綁定到CPU0～3上。

worker_processes      2;

worker_cpu_affinity 01011010;

上面這個配置則說明了兩個工作進程中的每一個和2個核掛鉤。

『伍』 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系統進程調度

主要參考 ：Linux manual page - sched

自從linux內核2.6.23以來，默認的進程調度器就被設置為完全公平調度器（CFS，complete fair scheler），取代了之前的O(1)調度器。

每個線程都有一個靜態調度優先順序，即 sched_priority 欄位。

一個線程的調度策略決定了線程會被插入到同級靜態優先順序的線程隊列的位置，以及它在隊列中會怎樣移動。

所有的調度都是可插入的，如果一個更高靜態優先順序的線程准備好了，現在運行中的線程就會被插入。而調度策略則僅僅影響了同樣靜態優先順序的線程。

進程（線程）可以通過系統調用設置自身或者其他進程（線程）的調度策略。

其中 pid 為0時，設置自身的調度策略和參數。結構體 sched_attr 包含以下欄位： size 、 sched_policy （即調度策略，具體會在下一節介紹）、 sched_flags 、 sched_nice 、 sched_runtime 、 sched_deadline 、 sched_period （最後三個為 SCHED_DEADLINE 相關的參數）。當設置成功，系統調用返回0；否則返回-1，並會設置 errno 。

普通進程： SCHED_OTHER / SCHED_BATCH / SCHED_IDLE
實時進程： SCHED_FIFO / SCHED_RR
特殊實時進程： SCHED_DEADLINE
靜態優先順序：Static_priority：對於普通進程，靜態優先順序為0；對於實時進程，靜態優先順序為1-99，99為最高優先順序。
動態優先順序：Dynamic_priority：僅對普通進程有用，取決於nice和一個動態調整的量（比如進程ready卻沒被調度，則增加）。

『柒』 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



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