linux內核紅黑樹

㈠ linux kernel可不可以完成進程調度

操作系統要實現多進程，進程調度必不可少。 有人說，進程調度是操作系統中最為重要的一個部分。我覺得這種說法說得太絕對了一點，就像很多人動輒就說"某某函數比某某函數效率高XX倍"一樣，脫離了實際環境，這些結論是比較片面的。 而進程調度究竟有多重要呢? 首先，我們需要明確一點：進程調度是對TASK_RUNNING狀態的進程進行調度(參見《linux進程狀態淺析》)。如果進程不可執行(正在睡眠或其他)，那麼它跟進程調度沒多大關系。 所以，如果你的系統負載非常低，盼星星盼月亮才出現一個可執行狀態的進程。那麼進程調度也就不會太重要。哪個進程可執行，就讓它執行去，沒有什麼需要多考慮的。 反之，如果系統負載非常高，時時刻刻都有N多個進程處於可執行狀態，等待被調度運行。那麼進程調度程序為了協調這N個進程的執行，必定得做很多工作。協調得不好，系統的性能就會大打折扣。這個時候，進程調度就是非常重要的。 盡管我們平常接觸的很多計算機(如桌面系統、網路伺服器、等)負載都比較低，但是linux作為一個通用操作系統，不能假設系統負載低，必須為應付高負載下的進程調度做精心的設計。 當然，這些設計對於低負載(且沒有什麼實時性要求)的環境，沒多大用。極端情況下，如果CPU的負載始終保持0或1(永遠都只有一個進程或沒有進程需要在CPU上運行)，那麼這些設計基本上都是徒勞的。 優先順序 現在的操作系統為了協調多個進程的“同時”運行，最基本的手段就是給進程定義優先順序。定義了進程的優先順序，如果有多個進程同時處於可執行狀態，那麼誰優先順序高誰就去執行，沒有什麼好糾結的了。 那麼，進程的優先順序該如何確定呢?有兩種方式：由用戶程序指定、由內核的調度程序動態調整。(下面會說到) linux內核將進程分成兩個級別：普通進程和實時進程。實時進程的優先順序都高於普通進程，除此之外，它們的調度策略也有所不同。 實時進程的調度 實時，原本的涵義是“給定的操作一定要在確定的時間內完成”。重點並不在於操作一定要處理得多快，而是時間要可控(在最壞情況下也不能突破給定的時間)。 這樣的“實時”稱為“硬實時”，多用於很精密的系統之中(比如什麼火箭、導彈之類的)。一般來說，硬實時的系統是相對比較專用的。 像linux這樣的通用操作系統顯然沒法滿足這樣的要求，中斷處理、虛擬內存、等機制的存在給處理時間帶來了很大的不確定性。硬體的cache、磁碟尋道、匯流排爭用、也會帶來不確定性。 比如考慮“i++;”這么一句C代碼。絕大多數情況下，它執行得很快。但是極端情況下還是有這樣的可能： 1、i的內存空間未分配，CPU觸發缺頁異常。而linux在缺頁異常的處理代碼中試圖分配內存時，又可能由於系統內存緊缺而分配失敗，導致進程進入睡眠; 2、代碼執行過程中硬體產生中斷，linux進入中斷處理程序而擱置當前進程。而中斷處理程序的處理過程中又可能發生新的硬體中斷，中斷永遠嵌套不止……; 等等…… 而像linux這樣號稱實現了“實時”的通用操作系統，其實只是實現了“軟實時”，即盡可能地滿足進程的實時需求。 如果一個進程有實時需求(它是一個實時進程)，則只要它是可執行狀態的，內核就一直讓它執行，以盡可能地滿足它對CPU的需要，直到它完成所需要做的事情，然後睡眠或退出(變為非可執行狀態)。 而如果有多個實時進程都處於可執行狀態，則內核會先滿足優先順序最高的實時進程對CPU的需要，直到它變為非可執行狀態。 於是，只要高優先順序的實時進程一直處於可執行狀態，低優先順序的實時進程就一直不能得到CPU;只要一直有實時進程處於可執行狀態，普通進程就一直不能得到CPU。 那麼，如果多個相同優先順序的實時進程都處於可執行狀態呢?這時就有兩種調度策略可供選擇： 1、SCHED_FIFO：先進先出。直到先被執行的進程變為非可執行狀態，後來的進程才被調度執行。在這種策略下，先來的進程可以執行sched_yield系統調用，自願放棄CPU，以讓權給後來的進程; 2、SCHED_RR：輪轉調度。內核為實時進程分配時間片，在時間片用完時，讓下一個進程使用CPU; 強調一下，這兩種調度策略以及sched_yield系統調用都僅僅針對於相同優先順序的多個實時進程同時處於可執行狀態的情況。 在linux下，用戶程序可以通過sched_setscheler系統調用來設置進程的調度策略以及相關調度參數;sched_setparam系統調用則只用於設置調度參數。這兩個系統調用要求用戶進程具有設置進程優先順序的能力(CAP_SYS_NICE，一般來說需要root許可權)(參閱capability相關的文章)。 通過將進程的策略設為SCHED_FIFO或SCHED_RR，使得進程變為實時進程。而進程的優先順序則是通過以上兩個系統調用在設置調度參數時指定的。 對於實時進程，內核不會試圖調整其優先順序。因為進程實時與否?有多實時?這些問題都是跟用戶程序的應用場景相關，只有用戶能夠回答，內核不能臆斷。 綜上所述，實時進程的調度是非常簡單的。進程的優先順序和調度策略都由用戶定死了，內核只需要總是選擇優先順序最高的實時進程來調度執行即可。唯一稍微麻煩一點的只是在選擇具有相同優先順序的實時進程時，要考慮兩種調度策略。 普通進程的調度 實時進程調度的中心思想是，讓處於可執行狀態的最高優先順序的實時進程盡可能地佔有CPU，因為它有實時需求;而普通進程則被認為是沒有實時需求的進程，於是調度程序力圖讓各個處於可執行狀態的普通進程和平共處地分享CPU，從而讓用戶覺得這些進程是同時運行的。 與實時進程相比，普通進程的調度要復雜得多。內核需要考慮兩件麻煩事： 一、動態調整進程的優先順序 按進程的行為特徵，可以將進程分為“互動式進程”和“批處理進程”： 互動式進程(如桌面程序、伺服器、等)主要的任務是與外界交互。這樣的進程應該具有較高的優先順序，它們總是睡眠等待外界的輸入。而在輸入到來，內核將其喚醒時，它們又應該很快被調度執行，以做出響應。比如一個桌面程序，如果滑鼠點擊後半秒種還沒反應，用戶就會感覺系統“卡”了; 批處理進程(如編譯程序)主要的任務是做持續的運算，因而它們會持續處於可執行狀態。這樣的進程一般不需要高優先順序，比如編譯程序多運行了幾秒種，用戶多半不會太在意; 如果用戶能夠明確知道進程應該有怎樣的優先順序，可以通過nice、setpriority系統調用來對優先順序進行設置。(如果要提高進程的優先順序，要求用戶進程具有CAP_SYS_NICE能力。) 然而應用程序未必就像桌面程序、編譯程序這樣典型。程序的行為可能五花八門，可能一會兒像互動式進程，一會兒又像批處理進程。以致於用戶難以給它設置一個合適的優先順序。 再者，即使用戶明確知道一個進程是互動式還是批處理，也多半礙於許可權或因為偷懶而不去設置進程的優先順序。(你又是否為某個程序設置過優先順序呢?) 於是，最終，區分互動式進程和批處理進程的重任就落到了內核的調度程序上。 調度程序關注進程近一段時間內的表現(主要是檢查其睡眠時間和運行時間)，根據一些經驗性的公式，判斷它現在是互動式的還是批處理的?程度如何?最後決定給它的優先順序做一定的調整。 進程的優先順序被動態調整後，就出現了兩個優先順序： 1、用戶程序設置的優先順序(如果未設置，則使用默認值)，稱為靜態優先順序。這是進程優先順序的基準，在進程執行的過程中往往是不改變的; 2、優先順序動態調整後，實際生效的優先順序。這個值是可能時時刻刻都在變化的; 二、調度的公平性 在支持多進程的系統中，理想情況下，各個進程應該是根據其優先順序公平地佔有CPU。而不會出現“誰運氣好誰佔得多”這樣的不可控的情況。 linux實現公平調度基本上是兩種思路： 1、給處於可執行狀態的進程分配時間片(按照優先順序)，用完時間片的進程被放到“過期隊列”中。等可執行狀態的進程都過期了，再重新分配時間片; 2、動態調整進程的優先順序。隨著進程在CPU上運行，其優先順序被不斷調低，以便其他優先順序較低的進程得到運行機會; 後一種方式有更小的調度粒度，並且將“公平性”與“動態調整優先順序”兩件事情合而為一，大大簡化了內核調度程序的代碼。因此，這種方式也成為內核調度程序的新寵。 強調一下，以上兩點都是僅針對普通進程的。而對於實時進程，內核既不能自作多情地去動態調整優先順序，也沒有什麼公平性可言。 普通進程具體的調度演算法非常復雜，並且隨linux內核版本的演變也在不斷更替(不僅僅是簡單的調整)，所以本文就不繼續深入了。 調度程序的效率 “優先順序”明確了哪個進程應該被調度執行，而調度程序還必須要關心效率問題。調度程序跟內核中的很多過程一樣會頻繁被執行，如果效率不濟就會浪費很多CPU時間，導致系統性能下降。 在linux 2.4時，可執行狀態的進程被掛在一個鏈表中。每次調度，調度程序需要掃描整個鏈表，以找出最優的那個進程來運行。復雜度為O(n); 在linux 2.6早期，可執行狀態的進程被掛在N(N=140)個鏈表中，每一個鏈表代表一個優先順序，系統中支持多少個優先順序就有多少個鏈表。每次調度，調度程序只需要從第一個不為空的鏈表中取出位於鏈表頭的進程即可。這樣就大大提高了調度程序的效率，復雜度為O(1); 在linux 2.6近期的版本中，可執行狀態的進程按照優先順序順序被掛在一個紅黑樹(可以想像成平衡二叉樹)中。每次調度，調度程序需要從樹中找出優先順序最高的進程。復雜度為O(logN)。 那麼，為什麼從linux 2.6早期到近期linux 2.6版本，調度程序選擇進程時的復雜度反而增加了呢? 這是因為，與此同時，調度程序對公平性的實現從上面提到的第一種思路改變為第二種思路(通過動態調整優先順序實現)。而O(1)的演算法是基於一組數目不大的鏈表來實現的，按我的理解，這使得優先順序的取值范圍很小(區分度很低)，不能滿足公平性的需求。而使用紅黑樹則對優先順序的取值沒有限制(可以用32位、64位、或更多位來表示優先順序的值)，並且O(logN)的復雜度也還是很高效的。 調度觸發的時機 調度的觸發主要有如下幾種情況： 1、當前進程(正在CPU上運行的進程)狀態變為非可執行狀態。 進程執行系統調用主動變為非可執行狀態。比如執行nanosleep進入睡眠、執行exit退出、等等; 進程請求的資源得不到滿足而被迫進入睡眠狀態。比如執行read系統調用時，磁碟高速緩存里沒有所需要的數據，從而睡眠等待磁碟IO; 進程響應信號而變為非可執行狀態。比如響應SIGSTOP進入暫停狀態、響應SIGKILL退出、等等; 2、搶占。進程運行時，非預期地被剝奪CPU的使用權。這又分兩種情況：進程用完了時間片、或出現了優先順序更高的進程。 優先順序更高的進程受正在CPU上運行的進程的影響而被喚醒。如發送信號主動喚醒，或因為釋放互斥對象(如釋放鎖)而被喚醒; 內核在響應時鍾中斷的過程中，發現當前進程的時間片用完; 內核在響應中斷的過程中，發現優先順序更高的進程所等待的外部資源的變為可用，從而將其喚醒。比如CPU收到網卡中斷，內核處理該中斷，發現某個socket可讀，於是喚醒正在等待讀這個socket的進程;再比如內核在處理時鍾中斷的過程中，觸發了定時器，從而喚醒對應的正在nanosleep系統調用中睡眠的進程。 所有任務都採用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內核什麼地方

紅黑樹是平衡二叉樹的一種，它有很好的性質，樹中的結點都是有序的，而且因為它本身就是平衡的，所以查找也不會出現非常惡劣的情況，基於二叉樹的操作的時間復雜度是O(log(N))。Linux內核在管理vm_area_struct時就是採用了紅黑樹來維護內存塊的。

先到include/linux/rbtree.h中看一下紅黑樹的一些定義，如下：

struct rb_node
{
unsigned long rb_parent_color;
#define RB_RED 0
#define RB_BLACK 1
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

struct rb_root只是struct rb_node*的一個包裝，這樣做的好處是看起來不用傳遞二級指針了。不錯，很簡單。再看一下下面幾個重要的宏，細心的你一定會發現，rb_parent_color其實沒那麼簡單，Andrea Arcangeli在這里使用了一個小的技巧，不過非常棒。正如名字所暗示，這個成員其實包含指向parent的指針和此結點的顏色！它是怎麼做到的呢？很簡單，對齊起了作用。既然是sizeof(long)大小的對齊，那麼在IA-32上，任何rb_node結構體的地址的低兩位肯定都是零，與其空著不用，還不如用它們表示顏色，反正顏色就兩種，其實一位就已經夠了。

這樣，提取parent指針只要把rb_parent_color成員的低兩位清零即可：

#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))

取顏色只要看最後一位即可：

#define rb_color(r) ((r)->rb_parent_color & 1)

測試顏色和設置顏色也是水到渠成的事了。需要特別指出的是下面的一個內聯函數：

static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link);

它把parent設為node的父結點，並且讓rb_link指向node。

我們把重點集中在lib/rbtree.c上，看看一些和紅黑樹相關的重要演算法。開始之前我們一起回憶一下紅黑樹的規則：

1. 每個結點要麼是紅色要麼是黑色；
2. 根結點必須是黑色；
3. 紅結點如果有孩子，其孩子必須都是黑色；
4. 從根結點到葉子的每條路徑必須包含相同數目的黑結點。

這四條規則可以限制一棵排序樹是平衡的。

__rb_rotate_left是把以root為根的樹中的node結點進行左旋，__rb_rotate_right是進行右旋。這兩個函數是為後面的插入和刪除服務，而不是為外部提供介面。

新插入的結點都設為葉子，染成紅色，插入後如果破壞了上述規則，通過調整顏色和旋轉可以恢復，二叉樹又重新平衡。插入操作的介面函數是

void rb_insert_color(struct rb_node *node, struct rb_root *root);

它把已確定父結點的node結點融入到以root為根的紅黑樹中，具體演算法的分析可以參考[1]中第14.3節，這里的實現和書中的講解幾乎完全一樣。怎麼確定node的父結點應該在調用rb_insert_color之前通過手工迭帶完成。值得指出的一點是，雖然插入操作需要一個循環迭代，但是總的旋轉次數不會超過兩次！所以效率還是很樂觀的。

刪除操作多多少少都有點麻煩，它要先執行像普通二叉查找樹的「刪除」，然後根據刪除結點的顏色來判斷是否執行進一步的操作。刪除的介面是：

void rb_erase(struct rb_node *node, struct rb_root *root);

其實它並沒有真正刪除node，而只是讓它和以root為根的樹脫離關系，最後它還要判斷是否調用__rb_erase_color來調整。具體演算法的講解看參考[1]中第13.3和14.4節，__rb_erase_color對應書中的RB-DELETE-FIXUP，此處的實現和書上也基本上一致。

其餘的幾個介面就比較簡單了。

struct rb_node *rb_first(struct rb_root *root);

在以root為根的樹中找出並返回最小的那個結點，只要從根結點一直向左走就是了。

struct rb_node *rb_last(struct rb_root *root);

是找出並返回最大的那個，一直向右走。

struct rb_node *rb_next(struct rb_node *node);

返回node在樹中的後繼，這個稍微復雜一點。如果node的右孩子不為空，它只要返回node的右子樹中最小的結點即可；如果為空，它要向上查找，找到迭帶結點是其父親的左孩子的結點，返回父結點。如果一直上述到了根結點，返回NULL。

struct rb_node *rb_prev(struct rb_node *node);

返回node的前驅，和rb_next中的操作對稱。

void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root);

用new替換以root為根的樹中的victim結點。

紅黑樹介面使用的一個典型例子如下：

static inline struct page * rb_search_page_cache(struct inode * inode,
unsigned long offset)
{
struct rb_node * n = inode->i_rb_page_cache.rb_node;
struct page * page;

while (n)
{
page = rb_entry(n, struct page, rb_page_cache);

if (offset < page->offset)
n = n->rb_left;
else if (offset > page->offset)
n = n->rb_right;
else
return page;
}
return NULL;
}

static inline struct page * __rb_insert_page_cache(struct inode * inode,
unsigned long offset,
struct rb_node * node)
{
struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
struct rb_node * parent = NULL;
struct page * page;

while (*p)
{
parent = *p;
page = rb_entry(parent, struct page, rb_page_cache);

if (offset < page->offset)
p = &(*p)->rb_left;
else if (offset > page->offset)
p = &(*p)->rb_right;
else
return page;
}

rb_link_node(node, parent, p);

return NULL;
}

static inline struct page * rb_insert_page_cache(struct inode * inode,
unsigned long offset,
struct rb_node * node)
{
struct page * ret;
if ((ret = __rb_insert_page_cache(inode, offset, node)))
goto out;
rb_insert_color(node, &inode->i_rb_page_cache);
out:
return ret;
}

因為紅黑樹的這些良好性質和實現中介面的簡易性，它被廣泛應用到內核編程中，大大提高了內核的效率。

㈢ 面試 linux 文件系統怎樣io到底層

前言：本文主要講解LinuxIO調度層的三種模式：cfp、deadline和noop，並給出各自的優化和適用場景建議。IO調度發生在Linux內核的IO調度層。這個層次是針對Linux的整體IO層次體系來說的。從read()或者write()系統調用的角度來說，Linux整體IO體系可以分為七層，它們分別是：VFS層：虛擬文件系統層。由於內核要跟多種文件系統打交道，而每一種文件系統所實現的數據結構和相關方法都可能不盡相同，所以，內核抽象了這一層，專門用來適配各種文件系統，並對外提供統一操作介面。文件系統層：不同的文件系統實現自己的操作過程，提供自己特有的特徵，具體不多說了，大家願意的話自己去看代碼即可。頁緩存層：負責真對page的緩存。通用塊層：由於絕大多數情況的io操作是跟塊設備打交道，所以Linux在此提供了一個類似vfs層的塊設備操作抽象層。下層對接各種不同屬性的塊設備，對上提供統一的BlockIO請求標准。IO調度層：因為絕大多數的塊設備都是類似磁碟這樣的設備，所以有必要根據這類設備的特點以及應用的不同特點來設置一些不同的調度演算法和隊列。以便在不同的應用環境下有針對性的提高磁碟的讀寫效率，這里就是大名鼎鼎的Linux電梯所起作用的地方。針對機械硬碟的各種調度方法就是在這實現的。塊設備驅動層：驅動層對外提供相對比較高級的設備操作介面，往往是C語言的，而下層對接設備本身的操作方法和規范。塊設備層：這層就是具體的物理設備了，定義了各種真對設備操作方法和規范。有一個已經整理好的[LinuxIO結構圖]，非常經典，一圖勝千言：我們今天要研究的內容主要在IO調度這一層。它要解決的核心問題是，如何提高塊設備IO的整體性能？這一層也主要是針對機械硬碟結構而設計的。眾所周知，機械硬碟的存儲介質是磁碟，磁頭在碟片上移動進行磁軌定址，行為類似播放一張唱片。這種結構的特點是，順序訪問時吞吐量較高，但是如果一旦對碟片有隨機訪問，那麼大量的時間都會浪費在磁頭的移動上，這時候就會導致每次IO的響應時間變長，極大的降低IO的響應速度。磁頭在碟片上尋道的操作，類似電梯調度，實際上在最開始的時期，Linux把這個演算法命名為Linux電梯演算法，即：如果在尋道的過程中，能把順序路過的相關磁軌的數據請求都「順便」處理掉，那麼就可以在比較小影響響應速度的前提下，提高整體IO的吞吐量。這就是我們為什麼要設計IO調度演算法的原因。目前在內核中默認開啟了三種演算法/模式：noop，cfq和deadline。嚴格算應該是兩種：因為第一種叫做noop，就是空操作調度演算法，也就是沒有任何調度操作，並不對io請求進行排序，僅僅做適當的io合並的一個fifo隊列。目前內核中默認的調度演算法應該是cfq，叫做完全公平隊列調度。這個調度演算法人如其名，它試圖給所有進程提供一個完全公平的IO操作環境。註：請大家一定記住這個詞語，cfq，完全公平隊列調度，不然下文就沒法看了。cfq為每個進程創建一個同步IO調度隊列，並默認以時間片和請求數限定的方式分配IO資源，以此保證每個進程的IO資源佔用是公平的，cfq還實現了針對進程級別的優先順序調度，這個我們後面會詳細解釋。查看和修改IO調度演算法的方法是：cfq是通用伺服器比較好的IO調度演算法選擇，對桌面用戶也是比較好的選擇。但是對於很多IO壓力較大的場景就並不是很適應，尤其是IO壓力集中在某些進程上的場景。因為這種場景我們需要的滿足某個或者某幾個進程的IO響應速度，而不是讓所有的進程公平的使用IO，比如資料庫應用。deadline調度（最終期限調度）就是更適合上述場景的解決方案。deadline實現了四個隊列：其中兩個分別處理正常read和write，按扇區號排序，進行正常io的合並處理以提高吞吐量。因為IO請求可能會集中在某些磁碟位置，這樣會導致新來的請求一直被合並，可能會有其他磁碟位置的io請求被餓死。另外兩個處理超時read和write的隊列，按請求創建時間排序，如果有超時的請求出現，就放進這兩個隊列，調度演算法保證超時（達到最終期限時間）的隊列中的請求會優先被處理，防止請求被餓死。不久前，內核還是默認標配四種演算法，還有一種叫做as的演算法（Anticipatoryscheler），預測調度演算法。一個高大上的名字，搞得我一度認為Linux內核都會算命了。結果發現，無非是在基於deadline演算法做io調度的之前等一小會時間，如果這段時間內有可以合並的io請求到來，就可以合並處理，提高deadline調度的在順序讀寫情況下的數據吞吐量。其實這根本不是啥預測，我覺得不如叫撞大運調度演算法，當然這種策略在某些特定場景差效果不錯。但是在大多數場景下，這個調度不僅沒有提高吞吐量，還降低了響應速度，所以內核乾脆把它從默認配置里刪除了。畢竟Linux的宗旨是實用，而我們也就不再這個調度演算法上多費口舌了。1、cfq：完全公平隊列調度cfq是內核默認選擇的IO調度隊列，它在桌面應用場景以及大多數常見應用場景下都是很好的選擇。如何實現一個所謂的完全公平隊列（CompletelyFairQueueing）？首先我們要理解所謂的公平是對誰的公平？從操作系統的角度來說，產生操作行為的主體都是進程，所以這里的公平是針對每個進程而言的，我們要試圖讓進程可以公平的佔用IO資源。那麼如何讓進程公平的佔用IO資源？我們需要先理解什麼是IO資源。當我們衡量一個IO資源的時候，一般喜歡用的是兩個單位，一個是數據讀寫的帶寬，另一個是數據讀寫的IOPS。帶寬就是以時間為單位的讀寫數據量，比如，100Mbyte/s。而IOPS是以時間為單位的讀寫次數。在不同的讀寫情境下，這兩個單位的表現可能不一樣，但是可以確定的是，兩個單位的任何一個達到了性能上限，都會成為IO的瓶頸。從機械硬碟的結構考慮，如果讀寫是順序讀寫，那麼IO的表現是可以通過比較少的IOPS達到較大的帶寬，因為可以合並很多IO，也可以通過預讀等方式加速數據讀取效率。當IO的表現是偏向於隨機讀寫的時候，那麼IOPS就會變得更大，IO的請求的合並可能性下降，當每次io請求數據越少的時候，帶寬表現就會越低。從這里我們可以理解，針對進程的IO資源的主要表現形式有兩個：進程在單位時間內提交的IO請求個數和進程佔用IO的帶寬。其實無論哪個，都是跟進程分配的IO處理時間長度緊密相關的。有時業務可以在較少IOPS的情況下佔用較大帶寬，另外一些則可能在較大IOPS的情況下佔用較少帶寬，所以對進程佔用IO的時間進行調度才是相對最公平的。即，我不管你是IOPS高還是帶寬佔用高，到了時間咱就換下一個進程處理，你愛咋樣咋樣。所以，cfq就是試圖給所有進程分配等同的塊設備使用的時間片，進程在時間片內，可以將產生的IO請求提交給塊設備進行處理，時間片結束，進程的請求將排進它自己的隊列，等待下次調度的時候進行處理。這就是cfq的基本原理。當然，現實生活中不可能有真正的「公平」，常見的應用場景下，我們很肯能需要人為的對進程的IO佔用進行人為指定優先順序，這就像對進程的CPU佔用設置優先順序的概念一樣。所以，除了針對時間片進行公平隊列調度外，cfq還提供了優先順序支持。每個進程都可以設置一個IO優先順序，cfq會根據這個優先順序的設置情況作為調度時的重要參考因素。優先順序首先分成三大類：RT、BE、IDLE，它們分別是實時（RealTime）、最佳效果（BestTry）和閑置（Idle）三個類別，對每個類別的IO，cfq都使用不同的策略進行處理。另外，RT和BE類別中，分別又再劃分了8個子優先順序實現更細節的QOS需求，而IDLE只有一個子優先順序。另外，我們都知道內核默認對存儲的讀寫都是經過緩存（buffer/cache）的，在這種情況下，cfq是無法區分當前處理的請求是來自哪一個進程的。只有在進程使用同步方式（syncread或者syncwirte）或者直接IO（DirectIO）方式進行讀寫的時候，cfq才能區分出IO請求來自哪個進程。所以，除了針對每個進程實現的IO隊列以外，還實現了一個公共的隊列用來處理非同步請求。當前內核已經實現了針對IO資源的cgroup資源隔離，所以在以上體系的基礎上，cfq也實現了針對cgroup的調度支持。總的來說，cfq用了一系列的數據結構實現了以上所有復雜功能的支持，大家可以通過源代碼看到其相關實現，文件在源代碼目錄下的block/cfq-iosched.c。1.1cfq設計原理在此，我們對整體數據結構做一個簡要描述：首先，cfq通過一個叫做cfq_data的數據結構維護了整個調度器流程。在一個支持了cgroup功能的cfq中，全部進程被分成了若干個contralgroup進行管理。每個cgroup在cfq中都有一個cfq_group的結構進行描述，所有的cgroup都被作為一個調度對象放進一個紅黑樹中，並以vdisktime為key進行排序。vdisktime這個時間紀錄的是當前cgroup所佔用的io時間，每次對cgroup進行調度時，總是通過紅黑樹選擇當前vdisktime時間最少的cgroup進行處理，以保證所有cgroups之間的IO資源佔用「公平」。當然我們知道，cgroup是可以對blkio進行資源比例分配的，其作用原理就是，分配比例大的cgroup佔用vdisktime時間增長較慢，分配比例小的vdisktime時間增長較快，快慢與分配比例成正比。這樣就做到了不同的cgroup分配的IO比例不一樣，並且在cfq的角度看來依然是「公平「的。選擇好了需要處理的cgroup（cfq_group）之後，調度器需要決策選擇下一步的service_tree。service_tree這個數據結構對應的都是一系列的紅黑樹，主要目的是用來實現請求優先順序分類的，就是RT、BE、IDLE的分類。每一個cfq_group都維護了7個service_trees，其定義如下：其中service_tree_idle就是用來給IDLE類型的請求進行排隊用的紅黑樹。而上面二維數組，首先第一個維度針對RT和BE分別各實現了一個數組，每一個數組中都維護了三個紅黑樹，分別對應三種不同子類型的請求，分別是：SYNC、SYNC_NOIDLE以及ASYNC。我們可以認為SYNC相當於SYNC_IDLE並與SYNC_NOIDLE對應。idling是cfq在設計上為了盡量合並連續的IO請求以達到提高吞吐量的目的而加入的機制，我們可以理解為是一種「空轉」等待機制。空轉是指，當一個隊列處理一個請求結束後，會在發生調度之前空等一小會時間，如果下一個請求到來，則可以減少磁頭定址，繼續處理順序的IO請求。為了實現這個功能，cfq在service_tree這層數據結構這實現了SYNC隊列，如果請求是同步順序請求，就入隊這個servicetree，如果請求是同步隨機請求，則入隊SYNC_NOIDLE隊列，以判斷下一個請求是否是順序請求。所有的非同步寫操作請求將入隊ASYNC的servicetree，並且針對這個隊列沒有空轉等待機制。此外，cfq還對SSD這樣的硬碟有特殊調整，當cfq發現存儲設備是一個ssd硬碟這樣的隊列深度更大的設備時，所有針對單獨隊列的空轉都將不生效，所有的IO請求都將入隊SYNC_NOIDLE這個servicetree。每一個servicetree都對應了若干個cfq_queue隊列，每個cfq_queue隊列對應一個進程，這個我們後續再詳細說明。cfq_group還維護了一個在cgroup內部所有進程公用的非同步IO請求隊列，其結構如下：非同步請求也分成了RT、BE、IDLE這三類進行處理，每一類對應一個cfq_queue進行排隊。BE和RT也實現了優先順序的支持，每一個類型有IOPRIO_BE_NR這么多個優先順序，這個值定義為8，數組下標為0-7。我們目前分析的內核代碼版本為Linux4.4，可以看出，從cfq的角度來說，已經可以實現非同步IO的cgroup支持了，我們需要定義一下這里所謂非同步IO的含義，它僅僅表示從內存的buffer/cache中的數據同步到硬碟的IO請求，而不是aio(man7aio)或者linux的native非同步io以及lio機制，實際上這些所謂的「非同步」IO機制，在內核中都是同步實現的（本質上馮諾伊曼計算機沒有真正的「非同步」機制）。我們在上面已經說明過，由於進程正常情況下都是將數據先寫入buffer/cache，所以這種非同步IO都是統一由cfq_group中的async請求隊列處理的。那麼為什麼在上面的service_tree中還要實現和一個ASYNC的類型呢？這當然是為了支持區分進程的非同步IO並使之可以「完全公平」做准備嘍。實際上在最新的cgroupv2的blkio體系中，內核已經支持了針對bufferIO的cgroup限速支持，而以上這些可能容易混淆的一堆類型，都是在新的體系下需要用到的類型標記。新體系的復雜度更高了，功能也更加強大，但是大家先不要著急，正式的cgroupv2體系，在Linux4.5發布的時候會正式跟大家見面。我們繼續選擇service_tree的過程，三種優先順序類型的service_tree的選擇就是根據類型的優先順序來做選擇的，RT優先順序最高，BE其次，IDLE最低。就是說，RT里有，就會一直處理RT，RT沒了再處理BE。每個service_tree對應一個元素為cfq_queue排隊的紅黑樹，而每個cfq_queue就是內核為進程（線程）創建的請求隊列。每一個cfq_queue都會維護一個rb_key的變數，這個變數實際上就是這個隊列的IO服務時間（servicetime）。這里還是通過紅黑樹找到servicetime時間最短的那個cfq_queue進行服務，以保證「完全公平」。選擇好了cfq_queue之後，就要開始處理這個隊列里的IO請求了。這里的調度方式基本跟deadline類似。cfq_queue會對進入隊列的每一個請求進行兩次入隊，一個放進fifo中，另一個放進按訪問扇區順序作為key的紅黑樹中。默認從紅黑樹中取請求進行處理，當請求的延時時間達到deadline時，就從紅黑樹中取等待時間最長的進行處理，以保證請求不被餓死。這就是整個cfq的調度流程，當然其中還有很多細枝末節沒有交代，比如合並處理以及順序處理等等。1.2cfq的參數調整理解整個調度流程有助於我們決策如何調整cfq的相關參數。所有cfq的可調參數都可以在/sys/class/block/sda/queue/iosched/目錄下找到，當然，在你的系統上，請將sda替換為相應的磁碟名稱。我們來看一下都有什麼：這些參數部分是跟機械硬碟磁頭尋道方式有關的，如果其說明你看不懂，請先補充相關知識：back_seek_max:磁頭可以向後定址的最大范圍，默認值為16M。back_seek_penalty:向後定址的懲罰系數。這個值是跟向前定址進行比較的。以上兩個是為了防止磁頭尋道發生抖動而導致定址過慢而設置的。基本思路是這樣，一個io請求到來的時候，cfq會根據其定址位置預估一下其磁頭尋道成本。設置一個最大值back_seek_max，對於請求所訪問的扇區號在磁頭後方的請求，只要定址范圍沒有超過這個值，cfq會像向前定址的請求一樣處理它。再設置一個評估成本的系數back_seek_penalty，相對於磁頭向前定址，向後定址的距離為1/2(1/back_seek_penalty)時，cfq認為這兩個請求定址的代價是相同。這兩個參數實際上是cfq判斷請求合並處理的條件限制，凡事復合這個條件的請求，都會盡量在本次請求處理的時候一起合並處理。fifo_expire_async:設置非同步請求的超時時間。同步請求和非同步請求是區分不同隊列處理的，cfq在調度的時候一般情況都會優先處理同步請求，之後再處理非同步請求，除非非同步請求符合上述合並處理的條件限制范圍內。當本進程的隊列被調度時，cfq會優先檢查是否有非同步請求超時，就是超過fifo_expire_async參數的限制。如果有，則優先發送一個超時的請求，其餘請求仍然按照優先順序以及扇區編號大小來處理。fifo_expire_sync:這個參數跟上面的類似，區別是用來設置同步請求的超時時間。slice_idle:參數設置了一個等待時間。這讓cfq在切換cfq_queue或servicetree的時候等待一段時間，目的是提高機械硬碟的吞吐量。一般情況下，來自同一個cfq_queue或者servicetree的IO請求的定址局部性更好，所以這樣可以減少磁碟的定址次數。這個值在機械硬碟上默認為非零。當然在固態硬碟或者硬RAID設備上設置這個值為非零會降低存儲的效率，因為固態硬碟沒有磁頭定址這個概念，所以在這樣的設備上應該設置為0，關閉此功能。group_idle:這個參數也跟上一個參數類似，區別是當cfq要切換cfq_group的時候會等待一段時間。在cgroup的場景下，如果我們沿用slice_idle的方式，那麼空轉等待可能會在cgroup組內每個進程的cfq_queue切換時發生。這樣會如果這個進程一直有請求要處理的話，那麼直到這個cgroup的配額被耗盡，同組中的其它進程也可能無法被調度到。這樣會導致同組中的其它進程餓死而產生IO性能瓶頸。在這種情況下，我們可以將slice_idle＝0而group_idle＝8。這樣空轉等待就是以cgroup為單位進行的，而不是以cfq_queue的進程為單位進行，以防止上述問題產生。low_latency:這個是用來開啟或關閉cfq的低延時（lowlatency）模式的開關。當這個開關打開時，cfq將會根據target_latency的參數設置來對每一個進程的分片時間（slicetime）進行重新計算。這將有利於對吞吐量的公平（默認是對時間片分配的公平）。關閉這個參數（設置為0）將忽略target_latency的值。這將使系統中的進程完全按照時間片方式進行IO資源分配。這個開關默認是打開的。我們已經知道cfq設計上有「空轉」（idling）這個概念，目的是為了可以讓連續的讀寫操作盡可能多的合並處理，減少磁頭的定址操作以便增大吞吐量。如果有進程總是很快的進行順序讀寫，那麼它將因為cfq的空轉等待命中率很高而導致其它需要處理IO的進程響應速度下降，如果另一個需要調度的進程不會發出大量順序IO行為的話，系統中不同進程IO吞吐量的表現就會很不均衡。就比如，系統內存的cache中有很多臟頁要寫回時，桌面又要打開一個瀏覽器進行操作，這時臟頁寫回的後台行為就很可能會大量命中空轉時間，而導致瀏覽器的小量IO一直等待，讓用戶感覺瀏覽器運行響應速度變慢。這個low_latency主要是對這種情況進行優化的選項，當其打開時，系統會根據target_latency的配置對因為命中空轉而大量佔用IO吞吐量的進程進行限制，以達到不同進程IO佔用的吞吐量的相對均衡。這個開關比較合適在類似桌面應用的場景下打開。target_latency:當low_latency的值為開啟狀態時，cfq將根據這個值重新計算每個進程分配的IO時間片長度。quantum:這個參數用來設置每次從cfq_queue中處理多少個IO請求。在一個隊列處理事件周期中，超過這個數字的IO請求將不會被處理。這個參數只對同步的請求有效。slice_sync:當一個cfq_queue隊列被調度處理時，它可以被分配的處理總時間是通過這個值來作為一個計算參數指定的。公式為：time_slice=slice_sync+(slice_sync/5*(4-prio))。這個參數對同步請求有效。slice_async:這個值跟上一個類似，區別是對非同步請求有效。slice_async_rq:這個參數用來限制在一個slice的時間范圍內，一個隊列最多可以處理的非同步請求個數。請求被處理的最大個數還跟相關進程被設置的io優先順序有關。1.3cfq的IOPS模式我們已經知道，默認情況下cfq是以時間片方式支持的帶優先順序的調度來保證IO資源佔用的公平。高優先順序的進程將得到的時間片長度，而低優先順序的進程時間片相對較小。當我們的存儲是一個高速並且支持NCQ（原生指令隊列）的設備的時候，我們最好可以讓其可以從多個cfq隊列中處理多路的請求，以便提升NCQ的利用率。此時使用時間片的分配方式分配資源就顯得不合時宜了，因為基於時間片的分配，同一時刻最多能處理的請求隊列只有一個。這時，我們需要切換cfq的模式為IOPS模式。切換方式很簡單，就是將slice_idle=0即可。內核會自動檢測你的存儲設備是否支持NCQ，如果支持的話cfq會自動切換為IOPS模式。另外，在默認的基於優先順序的時間片方式下，我們可以使用ionice命令來調整進程的IO優先順序。進程默認分配的IO優先順序是根據進程的nice值計算而來的，計算方法可以在manionice中看到，這里不再廢話。2、deadline：最終期限調度deadline調度演算法相對cfq要簡單很多。其設計目標是：在保證請求按照設備扇區的順序進行訪問的同時，兼顧其它請求不被餓死，要在一個最終期限前被調度到。我們知道磁頭對磁碟的尋道是可以進行順序訪問和隨機訪問的，因為尋道延時時間的關系，順序訪問時IO的吞吐量更大，隨機訪問的吞吐量小。如果我們想為一個機械硬碟進行吞吐量優化的話，那麼就可以讓調度器按照盡量復合順序訪問的IO請求進行排序，之後請求以這樣的順序發送給硬碟，就可以使IO的吞吐量更大。但是這樣做也有另一個問題，就是如果此時出現了一個請求，它要訪問的磁軌離目前磁頭所在磁軌很遠，應用的請求又大量集中在目前磁軌附近。導致大量請求一直會被合並和插隊處理，而那個要訪問比較遠磁軌的請求將因為一直不能被調度而餓死。deadline就是這樣一種調度器，能在保證IO最大吞吐量的情況下，盡量使遠端請求在一個期限內被調度而不被餓死的調度器。

㈣ Linux中普通進程調度選擇紅黑樹結構的理由是什麼

加快查找速度?

㈤ 如何利用linux內核中的紅黑樹庫，調試和運行紅黑樹

1、 初識紅黑樹
從網上搜索了許多紅黑樹的介紹，這些文章中主要介紹了紅黑樹的性質，然後就是紅黑樹的旋轉如下示意圖。

左旋、右旋，旋轉過程中爸爸變成了兒子，兄弟變成了孫子；紅的變成黑的，黑的變成紅的。經過一系列的旋轉，就把我旋轉的暈頭轉向了，腦子里攪成了一團漿糊。相信，沒有學過二叉樹的同學肯定會遇到和我一樣窘況。

㈥ linux中使用了什麼內存管理方法,為什麼

「事實勝於雄辯」，我們用一個小例子（原形取自《User-Level Memory Management》）來展示上面所講的各種內存區的差別與位置。

進程的地址空間對應的描述結構是「內存描述符結構」,它表示進程的全部地址空間，——包含了和進程地址空間有關的全部信息，其中當然包含進程的內存區域。

進程內存的分配與回收

創建進程fork()、程序載入execve()、映射文件mmap()、動態內存分配malloc()/brk()等進程相關操作都需要分配內存給進程。不過這時進程申請和獲得的還不是實際內存，而是虛擬內存，准確的說是「內存區域」。進程對內存區域的分配最終都會歸結到do_mmap（）函數上來（brk調用被單獨以系統調用實現，不用do_mmap()），

內核使用do_mmap()函數創建一個新的線性地址區間。但是說該函數創建了一個新VMA並不非常准確，因為如果創建的地址區間和一個已經存在的地址區間相鄰，並且它們具有相同的訪問許可權的話，那麼兩個區間將合並為一個。如果不能合並，那麼就確實需要創建一個新的VMA了。但無論哪種情況，do_mmap()函數都會將一個地址區間加入到進程的地址空間中－－無論是擴展已存在的內存區域還是創建一個新的區域。

同樣，釋放一個內存區域應使用函數do_ummap()，它會銷毀對應的內存區域。

如何由虛變實！

從上面已經看到進程所能直接操作的地址都為虛擬地址。當進程需要內存時，從內核獲得的僅僅是虛擬的內存區域，而不是實際的物理地址，進程並沒有獲得物理內存（物理頁面——頁的概念請大家參考硬體基礎一章），獲得的僅僅是對一個新的線性地址區間的使用權。實際的物理內存只有當進程真的去訪問新獲取的虛擬地址時，才會由「請求頁機制」產生「缺頁」異常，從而進入分配實際頁面的常式。

該異常是虛擬內存機制賴以存在的基本保證——它會告訴內核去真正為進程分配物理頁，並建立對應的頁表，這之後虛擬地址才實實在在地映射到了系統的物理內存上。（當然，如果頁被換出到磁碟，也會產生缺頁異常，不過這時不用再建立頁表了）

這種請求頁機制把頁面的分配推遲到不能再推遲為止，並不急於把所有的事情都一次做完（這種思想有點像設計模式中的代理模式（proxy））。之所以能這么做是利用了內存訪問的「局部性原理」，請求頁帶來的好處是節約了空閑內存，提高了系統的吞吐率。要想更清楚地了解請求頁機制，可以看看《深入理解linux內核》一書。

這里我們需要說明在內存區域結構上的nopage操作。當訪問的進程虛擬內存並未真正分配頁面時，該操作便被調用來分配實際的物理頁，並為該頁建立頁表項。在最後的例子中我們會演示如何使用該方法。

系統物理內存管理

雖然應用程序操作的對象是映射到物理內存之上的虛擬內存，但是處理器直接操作的卻是物理內存。所以當應用程序訪問一個虛擬地址時，首先必須將虛擬地址轉化成物理地址，然後處理器才能解析地址訪問請求。地址的轉換工作需要通過查詢頁表才能完成，概括地講，地址轉換需要將虛擬地址分段，使每段虛地址都作為一個索引指向頁表，而頁表項則指向下一級別的頁表或者指向最終的物理頁面。

每個進程都有自己的頁表。進程描述符的pgd域指向的就是進程的頁全局目錄。下面我們借用《linux設備驅動程序》中的一幅圖大致看看進程地址空間到物理頁之間的轉換關系。

上面的過程說起來簡單，做起來難呀。因為在虛擬地址映射到頁之前必須先分配物理頁——也就是說必須先從內核中獲取空閑頁，並建立頁表。下面我們介紹一下內核管理物理內存的機制。

物理內存管理（頁管理）

Linux內核管理物理內存是通過分頁機制實現的，它將整個內存劃分成無數個4k（在i386體系結構中）大小的頁，從而分配和回收內存的基本單位便是內存頁了。利用分頁管理有助於靈活分配內存地址，因為分配時不必要求必須有大塊的連續內存[3]，系統可以東一頁、西一頁的湊出所需要的內存供進程使用。雖然如此，但是實際上系統使用內存時還是傾向於分配連續的內存塊，因為分配連續內存時，頁表不需要更改，因此能降低TLB的刷新率（頻繁刷新會在很大程度上降低訪問速度）。

鑒於上述需求，內核分配物理頁面時為了盡量減少不連續情況，採用了「夥伴」關系來管理空閑頁面。夥伴關系分配演算法大家應該不陌生——幾乎所有操作系統方面的書都會提到,我們不去詳細說它了，如果不明白可以參看有關資料。這里只需要大家明白Linux中空閑頁面的組織和管理利用了夥伴關系，因此空閑頁面分配時也需要遵循夥伴關系，最小單位只能是2的冪倍頁面大小。內核中分配空閑頁面的基本函數是get_free_page/get_free_pages，它們或是分配單頁或是分配指定的頁面（2、4、8…512頁）。

注意：get_free_page是在內核中分配內存，不同於malloc在用戶空間中分配，malloc利用堆動態分配，實際上是調用brk()系統調用，該調用的作用是擴大或縮小進程堆空間（它會修改進程的brk域）。如果現有的內存區域不夠容納堆空間，則會以頁面大小的倍數為單位，擴張或收縮對應的內存區域，但brk值並非以頁面大小為倍數修改，而是按實際請求修改。因此Malloc在用戶空間分配內存可以以位元組為單位分配,但內核在內部仍然會是以頁為單位分配的。

另外,需要提及的是，物理頁在系統中由頁結構structpage描述，系統中所有的頁面都存儲在數組mem_map[]中，可以通過該數組找到系統中的每一頁（空閑或非空閑）。而其中的空閑頁面則可由上述提到的以夥伴關系組織的空閑頁鏈表（free_area[MAX_ORDER]）來索引。

內核內存使用

Slab

所謂尺有所長，寸有所短。以頁為最小單位分配內存對於內核管理系統中的物理內存來說的確比較方便，但內核自身最常使用的內存卻往往是很小（遠遠小於一頁）的內存塊——比如存放文件描述符、進程描述符、虛擬內存區域描述符等行為所需的內存都不足一頁。這些用來存放描述符的內存相比頁面而言，就好比是麵包屑與麵包。一個整頁中可以聚集多個這些小塊內存；而且這些小塊內存塊也和麵包屑一樣頻繁地生成/銷毀。

為了滿足內核對這種小內存塊的需要，Linux系統採用了一種被稱為slab分配器的技術。Slab分配器的實現相當復雜，但原理不難，其核心思想就是「存儲池[4]」的運用。內存片段（小塊內存）被看作對象，當被使用完後，並不直接釋放而是被緩存到「存儲池」里，留做下次使用，這無疑避免了頻繁創建與銷毀對象所帶來的額外負載。

Slab技術不但避免了內存內部分片（下文將解釋）帶來的不便（引入Slab分配器的主要目的是為了減少對夥伴系統分配演算法的調用次數——頻繁分配和回收必然會導致內存碎片——難以找到大塊連續的可用內存），而且可以很好地利用硬體緩存提高訪問速度。

Slab並非是脫離夥伴關系而獨立存在的一種內存分配方式，slab仍然是建立在頁面基礎之上，換句話說，Slab將頁面（來自於夥伴關系管理的空閑頁面鏈表）撕碎成眾多小內存塊以供分配，slab中的對象分配和銷毀使用kmem_cache_alloc與kmem_cache_free。

Kmalloc

Slab分配器不僅僅只用來存放內核專用的結構體，它還被用來處理內核對小塊內存的請求。當然鑒於Slab分配器的特點，一般來說內核程序中對小於一頁的小塊內存的請求才通過Slab分配器提供的介面Kmalloc來完成（雖然它可分配32到131072位元組的內存）。從內核內存分配的角度來講，kmalloc可被看成是get_free_page（s）的一個有效補充，內存分配粒度更靈活了。

有興趣的話，可以到/proc/slabinfo中找到內核執行現場使用的各種slab信息統計，其中你會看到系統中所有slab的使用信息。從信息中可以看到系統中除了專用結構體使用的slab外，還存在大量為Kmalloc而准備的Slab（其中有些為dma准備的）。

內核非連續內存分配（Vmalloc）

夥伴關系也好、slab技術也好，從內存管理理論角度而言目的基本是一致的，它們都是為了防止「分片」，不過分片又分為外部分片和內部分片之說，所謂內部分片是說系統為了滿足一小段內存區（連續）的需要，不得不分配了一大區域連續內存給它，從而造成了空間浪費；外部分片是指系統雖有足夠的內存，但卻是分散的碎片，無法滿足對大塊「連續內存」的需求。無論何種分片都是系統有效利用內存的障礙。slab分配器使得一個頁面內包含的眾多小塊內存可獨立被分配使用，避免了內部分片，節約了空閑內存。夥伴關系把內存塊按大小分組管理，一定程度上減輕了外部分片的危害，因為頁框分配不在盲目，而是按照大小依次有序進行，不過夥伴關系只是減輕了外部分片，但並未徹底消除。你自己比劃一下多次分配頁面後，空閑內存的剩餘情況吧。

所以避免外部分片的最終思路還是落到了如何利用不連續的內存塊組合成「看起來很大的內存塊」——這里的情況很類似於用戶空間分配虛擬內存，內存邏輯上連續，其實映射到並不一定連續的物理內存上。Linux內核借用了這個技術，允許內核程序在內核地址空間中分配虛擬地址，同樣也利用頁表（內核頁表）將虛擬地址映射到分散的內存頁上。以此完美地解決了內核內存使用中的外部分片問題。內核提供vmalloc函數分配內核虛擬內存，該函數不同於kmalloc，它可以分配較Kmalloc大得多的內存空間（可遠大於128K，但必須是頁大小的倍數），但相比Kmalloc來說,Vmalloc需要對內核虛擬地址進行重映射，必須更新內核頁表，因此分配效率上要低一些（用空間換時間）

與用戶進程相似,內核也有一個名為init_mm的mm_strcut結構來描述內核地址空間，其中頁表項pdg=swapper_pg_dir包含了系統內核空間（3G-4G）的映射關系。因此vmalloc分配內核虛擬地址必須更新內核頁表，而kmalloc或get_free_page由於分配的連續內存，所以不需要更新內核頁表。

vmalloc分配的內核虛擬內存與kmalloc/get_free_page分配的內核虛擬內存位於不同的區間，不會重疊。因為內核虛擬空間被分區管理，各司其職。進程空間地址分布從0到3G(其實是到PAGE_OFFSET,在0x86中它等於0xC0000000)，從3G到vmalloc_start這段地址是物理內存映射區域（該區域中包含了內核鏡像、物理頁面表mem_map等等）比如我使用的系統內存是64M(可以用free看到)，那麼(3G——3G+64M)這片內存就應該映射到物理內存，而vmalloc_start位置應在3G+64M附近（說"附近"因為是在物理內存映射區與vmalloc_start期間還會存在一個8M大小的gap來防止躍界）,vmalloc_end的位置接近4G(說"接近"是因為最後位置系統會保留一片128k大小的區域用於專用頁面映射，還有可能會有高端內存映射區，這些都是細節，這里我們不做糾纏)。

上圖是內存分布的模糊輪廓

由get_free_page或Kmalloc函數所分配的連續內存都陷於物理映射區域，所以它們返回的內核虛擬地址和實際物理地址僅僅是相差一個偏移量（PAGE_OFFSET），你可以很方便的將其轉化為物理內存地址，同時內核也提供了virt_to_phys（）函數將內核虛擬空間中的物理映射區地址轉化為物理地址。要知道，物理內存映射區中的地址與內核頁表是有序對應的，系統中的每個物理頁面都可以找到它對應的內核虛擬地址（在物理內存映射區中的）。

而vmalloc分配的地址則限於vmalloc_start與vmalloc_end之間。每一塊vmalloc分配的內核虛擬內存都對應一個vm_struct結構體（可別和vm_area_struct搞混，那可是進程虛擬內存區域的結構），不同的內核虛擬地址被4k大小的空閑區間隔，以防止越界——見下圖）。與進程虛擬地址的特性一樣，這些虛擬地址與物理內存沒有簡單的位移關系，必須通過內核頁表才可轉換為物理地址或物理頁。它們有可能尚未被映射，在發生缺頁時才真正分配物理頁面。

這里給出一個小程序幫助大家認清上面幾種分配函數所對應的區域。

#include<linux/mole.h>

#include<linux/slab.h>

#include<linux/vmalloc.h>

unsignedchar*pagemem;

unsignedchar*kmallocmem;

unsignedchar*vmallocmem;

intinit_mole(void)

{

pagemem = get_free_page(0);

printk("<1>pagemem=%s",pagemem);

kmallocmem = kmalloc(100,0);

printk("<1>kmallocmem=%s",kmallocmem);

vmallocmem = vmalloc(1000000);

printk("<1>vmallocmem=%s",vmallocmem);

}

voidcleanup_mole(void)

{

free_page(pagemem);

kfree(kmallocmem);

vfree(vmallocmem);

}

實例

內存映射(mmap)是Linux操作系統的一個很大特色，它可以將系統內存映射到一個文件（設備）上，以便可以通過訪問文件內容來達到訪問內存的目的。這樣做的最大好處是提高了內存訪問速度，並且可以利用文件系統的介面編程（設備在Linux中作為特殊文件處理）訪問內存，降低了開發難度。許多設備驅動程序便是利用內存映射功能將用戶空間的一段地址關聯到設備內存上，無論何時，只要內存在分配的地址范圍內進行讀寫，實際上就是對設備內存的訪問。同時對設備文件的訪問也等同於對內存區域的訪問，也就是說，通過文件操作介面可以訪問內存。Linux中的X伺服器就是一個利用內存映射達到直接高速訪問視頻卡內存的例子。

熟悉文件操作的朋友一定會知道file_operations結構中有mmap方法，在用戶執行mmap系統調用時，便會調用該方法來通過文件訪問內存——不過在調用文件系統mmap方法前，內核還需要處理分配內存區域（vma_struct）、建立頁表等工作。對於具體映射細節不作介紹了，需要強調的是,建立頁表可以採用remap_page_range方法一次建立起所有映射區的頁表，或利用vma_struct的nopage方法在缺頁時現場一頁一頁的建立頁表。第一種方法相比第二種方法簡單方便、速度快，但是靈活性不高。一次調用所有頁表便定型了，不適用於那些需要現場建立頁表的場合——比如映射區需要擴展或下面我們例子中的情況。

我們這里的實例希望利用內存映射，將系統內核中的一部分虛擬內存映射到用戶空間，以供應用程序讀取——你可利用它進行內核空間到用戶空間的大規模信息傳輸。因此我們將試圖寫一個虛擬字元設備驅動程序，通過它將系統內核空間映射到用戶空間——將內核虛擬內存映射到用戶虛擬地址。從上一節已經看到Linux內核空間中包含兩種虛擬地址：一種是物理和邏輯都連續的物理內存映射虛擬地址；另一種是邏輯連續但非物理連續的vmalloc分配的內存虛擬地址。我們的例子程序將演示把vmalloc分配的內核虛擬地址映射到用戶地址空間的全過程。

程序里主要應解決兩個問題：

第一是如何將vmalloc分配的內核虛擬內存正確地轉化成物理地址？

因為內存映射先要獲得被映射的物理地址，然後才能將其映射到要求的用戶虛擬地址上。我們已經看到內核物理內存映射區域中的地址可以被內核函數virt_to_phys轉換成實際的物理內存地址，但對於vmalloc分配的內核虛擬地址無法直接轉化成物理地址，所以我們必須對這部分虛擬內存格外「照顧」——先將其轉化成內核物理內存映射區域中的地址，然後在用virt_to_phys變為物理地址。

轉化工作需要進行如下步驟：

如下圖所示：

第二是當訪問vmalloc分配區時，如果發現虛擬內存尚未被映射到物理頁，則需要處理「缺頁異常」。因此需要我們實現內存區域中的nopaga操作，以能返回被映射的物理頁面指針，在我們的實例中就是返回上面過程中的內核物理內存映射區域中的地址。由於vmalloc分配的虛擬地址與物理地址的對應關系並非分配時就可確定，必須在缺頁現場建立頁表，因此這里不能使用remap_page_range方法，只能用vma的nopage方法一頁一頁的建立。

程序組成

map_driver.c，它是以模塊形式載入的虛擬字元驅動程序。該驅動負責將一定長的內核虛擬地址(vmalloc分配的)映射到設備文件上。其中主要的函數有——vaddress_to_kaddress（）負責對vmalloc分配的地址進行頁表解析,以找到對應的內核物理映射地址（kmalloc分配的地址）；map_nopage()負責在進程訪問一個當前並不存在的VMA頁時，尋找該地址對應的物理頁，並返回該頁的指針。

test.c它利用上述驅動模塊對應的設備文件在用戶空間讀取讀取內核內存。結果可以看到內核虛擬地址的內容（ok!），被顯示在了屏幕上。

執行步驟

編譯map_driver.c為map_driver.o模塊,具體參數見Makefile

載入模塊：insmodmap_driver.o

生成對應的設備文件

1在/proc/devices下找到map_driver對應的設備命和設備號：grepmapdrv/proc/devices

2建立設備文件mknodmapfilec 254 0（在我的系統里設備號為254）

利用maptest讀取mapfile文件，將取自內核的信息列印到屏幕上。

㈦ 操作系統內核具體實現中比較巧妙的思想有哪些

1. 我大VFS！通過VFS的抽象層，一切都變成了文件。於是Linux的系統調用精簡了好多，於是很多虛擬文件系統(proc, sysfs, cgroup, tmpfs)得以實現，於是linux可以相對容易的支持多種文件系統。2. current宏的實現。將內核棧建立在當前的進程描述符的上面，通過棧地址偏移即可快速獲得當前進程的信息。3. clone系統調用。模糊了進程，線程的界線，在linux內核中沒有明確的線程、進程的概念，都是task_struct表示的運行實例，且依據clone的參數，實例間靈活的可以共享多種信息。而共享程度的兩種特殊情況，就是進程和線程。4. cgroup, namespace。內核居然要虛擬化進程的運行環境！也成就了Docker。5. 紅黑樹的數組做hash結構。用紅黑樹而非鏈表來組織哈希沖突的元素(源碼中部分哈希是這樣的)。6. CFS調度器。通過紅黑樹、vruntime等將之前多鏈表表示不同優先順序的調度演算法簡化，妙！7. ……（內核的學習是一個充滿了驚喜的旅程

㈧ linux內核哪些地方用到了紅黑樹

Linux內核[kernel]是整個操作系統的最底層，它負責整個硬體的驅動，以及提供各種系統所需的核心功能，包括防火牆機制、是否支持LVM或Quota等文件系統等等，如果內核不認識某個最新的硬體，那麼硬體也就無法被驅動，你也就無法使用該硬體。 計算...

㈨ 紅黑樹和平衡二叉樹 區別

紅黑樹和平衡二叉樹的主要區別如下：
平衡二叉樹（AVL）樹是嚴格的平衡二叉樹，平衡條件必須滿足（所有節點的左右子樹高度差不超過1）。不管我們是執行插入還是刪除操作，只要不滿足上面的條件，就要通過旋轉來保持平衡，而的英文旋轉非常耗時的。所以平衡二叉樹（AVL）適合用於插入與刪除次數比較少，但查找多的情況。
紅黑樹在二叉查找樹的基礎上增加了著色和相關的性質使得紅黑樹相對平衡，從而保證了紅黑樹的查找、插入、刪除的時間復雜度最壞為O(log
n)。所以紅黑樹適用於搜索，插入，刪除操作較多的情況。
(9)linux內核紅黑樹擴展閱讀：
平衡二叉樹在Windows
NT內核中廣泛存在。
紅黑樹的應用：
1、在C
++的STL中，地圖和集都是用紅黑樹實現的；
2、著名的Linux的的進程調度完全公平調度程序，用紅黑樹管理進程式控制制塊，進程的虛擬內存區域都存儲在一顆紅黑樹上，每個虛擬地址區域都對應紅黑樹的一個節點，左指針指向相鄰的地址虛擬存儲區域，右指針指向相鄰的高地址虛擬地址空間；
3、IO多路復用的epoll的的的實現採用紅黑樹組織管理的sockfd，以支持快速的增刪改查；
4、Nginx的的的中用紅黑樹管理定時器，因為紅黑樹是有序的，可以很快的得到距離當前最小的定時器；
5、Java中的TreeMap中的實現。
參考資料：
網路-平衡二叉樹
網路-紅黑樹

㈩ Linux 虛擬地址空間如何分布

一個進程的虛擬地址空間主要由兩個數據結來描述。一個是最高層次的：mm_struct，一個是較高層次的：vm_area_structs。最高層次的mm_struct結構描述了一個進程的整個虛擬地址空間。較高層次的結構vm_area_truct描述了虛擬地址空間的一個區間（簡稱虛擬區）。

1. MM_STRUCT結構

mm_strcut 用來描述一個進程的虛擬地址空間，在/include/linux/sched.h 中描述如下：

struct mm_struct {

struct vm_area_struct * mmap; /* 指向虛擬區間（VMA）鏈表 */

rb_root_t mm_rb; ／*指向red_black樹*/

struct vm_area_struct * mmap_cache; /* 指向最近找到的虛擬區間*/

pgd_t * pgd; ／*指向進程的頁目錄*/

atomic_t mm_users; /* 用戶空間中的有多少用戶*/

atomic_t mm_count; /* 對"struct mm_struct"有多少引用*/

int map_count; /* 虛擬區間的個數*/

struct rw_semaphore mmap_sem;

spinlock_t page_table_lock; /* 保護任務頁表和 mm->rss */

struct list_head mmlist; /*所有活動（active）mm的鏈表 */

unsigned long start_code, end_code, start_data, end_data;

unsigned long start_brk, brk, start_stack;

unsigned long arg_start, arg_end, env_start, env_end;

unsigned long rss, total_vm, locked_vm;

unsigned long def_flags;

unsigned long cpu_vm_mask;

unsigned long swap_address;

unsigned mpable:1;

/* Architecture-specific MM context */

mm_context_t context;

};

對該結構進一步說明如下：

在內核代碼中，指向這個數據結構的變數常常是mm。

每個進程只有一個mm_struct結構，在每個進程的task_struct結構中，有一個指向該進程的結構。可以說，mm_struct結構是對整個用戶空間的描述。

一個進程的虛擬空間中可能有多個虛擬區間（參見下面對vm_area_struct描述），對這些虛擬區間的組織方式有兩種，當虛擬區較少時採用單鏈表，由mmap指針指向這個鏈表，當虛擬區間多時採用「紅黑樹（red_black
tree）」結構，由mm_rb指向這顆樹。在2.4.10以前的版本中，採用的是AVL樹，因為與AVL樹相比，對紅黑樹進行操作的效率更高。

因為程序中用到的地址常常具有局部性，因此，最近一次用到的虛擬區間很可能下一次還要用到，因此，把最近用到的虛擬區間結構應當放入高速緩存，這個虛擬區間就由mmap_cache指向。

指針pgt指向該進程的頁目錄（每個進程都有自己的頁目錄，注意同內核頁目錄的區別）,當調度程序調度一個程序運行時，就將這個地址轉成物理地址，並寫入控制寄存器（CR3）。

由於進程的虛擬空間及其下屬的虛擬區間有可能在不同的上下文中受到訪問，而這些訪問又必須互斥，所以在該結構中設置了用於P、V操作的信號量mmap_sem。此外，page_table_lock也是為類似的目的而設置。

雖然每個進程只有一個虛擬地址空間，但這個地址空間可以被別的進程來共享，如，子進程共享父進程的地址空間（也即共享mm_struct結構）。所以，用mm_user和mm_count進行計數。類型atomic_t實際上就是整數，但對這種整數的操作必須是「原子」的。

另外，還描述了代碼段、數據段、堆棧段、參數段以及環境段的起始地址和結束地址。這里的段是對程序的邏輯劃分，與我們前面所描述的段機制是不同的。

mm_context_t是與平台相關的一個結構，對i386 幾乎用處不大。

在後面對代碼的分析中對有些域給予進一步說明。

2. VM_AREA_STRUCT 結構

vm_area_struct描述進程的一個虛擬地址區間，在/include/linux/mm.h中描述如下：

struct vm_area_struct

struct mm_struct * vm_mm; /* 虛擬區間所在的地址空間*/

unsigned long vm_start; /* 在vm_mm中的起始地址*/

unsigned long vm_end; /*在vm_mm中的結束地址 */

/* linked list of VM areas per task, sorted by address */

struct vm_area_struct *vm_next;

pgprot_t vm_page_prot; /* 對這個虛擬區間的存取許可權 */

unsigned long vm_flags; /* 虛擬區間的標志. */

rb_node_t vm_rb;

/*

* For areas with an address space and backing store,

* one of the address_space->i_mmap{,shared} lists,

* for shm areas, the list of attaches, otherwise unused.

*/

struct vm_area_struct *vm_next_share;

struct vm_area_struct **vm_pprev_share;

/*對這個區間進行操作的函數 */

struct vm_operations_struct * vm_ops;

/* Information about our backing store: */

unsigned long vm_pgoff; /* Offset (within vm_file) in PAGE_SIZE

units, *not* PAGE_CACHE_SIZE */

struct file * vm_file; /* File we map to (can be NULL). */

unsigned long vm_raend; /* XXX: put full readahead info here. */

void * vm_private_data; /* was vm_pte (shared mem) */

};

vm_flag是描述對虛擬區間的操作的標志，其定義和描述如下

標志名 描述

VM_DENYWRITE 在這個區間映射一個打開後不能用來寫的文件。

VM_EXEC 頁可以被執行。

VM_EXECUTABLE 頁含有可執行代碼。

VM_GROWSDOWN 這個區間可以向低地址擴展。

VM_GROWSUP 這個區間可以向高地址擴展。

VM_IO 這個區間映射一個設備的I/O地址空間。

VM_LOCKED 頁被鎖住不能被交換出去。

VM_MAYEXEC VM_EXEC 標志可以被設置。

VM_MAYREAD VM_READ 標志可以被設置。

VM_MAYSHARE VM_SHARE 標志可以被設置。

VM_MAYWRITE VM_WRITE 標志可以被設置。

VM_READ 頁是可讀的。

VM_SHARED 頁可以被多個進程共享。

VM_SHM 頁用於IPC共享內存。
VM_WRITE 頁是可寫的。

較高層次的結構vm_area_structs是由雙向鏈表連接起來的，它們是按虛地址的降順序來排列的，每個這樣的結構都對應描述一個相鄰的地址空間范圍。之所以這樣分割，是因為每個虛擬區間可能來源不同，有的可能來自可執行映象，有的可能來自共享庫，而有的則可能是動態分配的內存區，所以對每一個由vm_area_structs結構所描述的區間的處理操作和它前後范圍的處理操作不同。因此Linux
把虛擬內存分割管理，並利用了虛擬內存處理常式（vm_ops）來抽象對不同來源虛擬內存的處理方法。不同的虛擬區間其處理操作可能不同，Linux在這里利用了面向對象的思想，即把一個虛擬區間看成一個對象，用vm_area_structs描述了這個對象的屬性，其中的vm_operation結構描述了在這個對象上的操作，其定義在／include／linux／mm.h中：

/*

* These are the virtual MM functions - opening of an area, closing and

* unmapping it (needed to keep files on disk up-to-date etc), pointer

* to the functions called when a no-page or a wp-page exception occurs.

*/

struct vm_operations_struct {

void (*open)(struct vm_area_struct * area);

void (*close)(struct vm_area_struct * area);

struct page * (*nopage)(struct vm_area_struct * area, unsigned long address, int unused);

};

vm_operations結構中包含的是函數指針；其中，open、close分別用於虛擬區間的打開、關閉，而nopage用於當虛存頁面不在物理內存而引起的「缺頁異常」時所應該調用的函數。

3．紅黑樹結構

Linux內核從2.4.10開始，對虛擬區的組織不再採用AVL樹，而是採用紅黑樹，這也是出於效率的考慮，雖然AVL樹和紅黑樹很類似，但在插入和刪除節點方面，採用紅黑樹的性能更好一些，下面對紅黑樹給予簡單介紹。
一顆紅黑樹是具有以下特點的二叉樹：
每個節點著有顏色，或者為紅，或者為黑
根節點為黑色
如果一個節點為紅色，那麼它的子節點必須為黑色
從一個節點到葉子節點上的所有路徑都包含有相同的黑色節點數