從2.x到4.x，Linux內核這十年經歷了哪些重要變革
原創【51CTO.com綜合消息】Linux內核現在已經進入4.x時代了，但是據說從版本2.6升到3.0，以及3.19升到4.0這之間都沒什么太大的變革。事實如此嗎?內核版本間的區別有多大?
說實話，這個問題挺大的。Linux內核的2.6 時代跨度非常大，從2.6.1 (2003年12月發布) 到 2.6.39(2011年5月發布)，跨越了39 個大版本。3.0(原計劃的2.6.40，2011年7月發布) 到 3.19(2015年2月發布)，經歷了20個版本。4.0(2015年4月發布)到4.2(2015年8月底發布)，又有3個版本。
總的來說，從進入2.6之后，每個大版本跨度開發時間大概是 2 - 3 個月。2.6.x , 3.x, 4.x，數字的遞進并沒有非常根本性，引人注目的大變化，但每個大版本中都有一些或大或小的功能改變。主版本號只是一個數字而已。不過要直接從 2.6.x 升級 到 3.x, 乃至 4.x，隨著時間間隔增大，出問題的機率當然大很多。
個人覺得 Linux 真正走入嚴肅級別的高穩定性，高可用性，高可伸縮性的工業級別內核大概是在 2003 年之后吧!一是隨著互聯網的迅速普及，更多的人使用、參與開發。二是社區經過11年發展，已經慢慢摸索出一套很穩定的協同開發模式，一個重要的特點是社區開始使用版本管理工具進行管理，脫離了之前純粹手工(或一些輔助的簡陋工具)處理代碼郵件的方式，大大加快了開發的速度和力度。
因此，本文匯總分析一下從 2.6.12 (2005年6月發布，也就是社區開始使用 git 進行管理后的第一個大版本)，到 4.2 (2015年8月發布)這中間共 51個大版本，時間跨度10年的主要大模塊的一些重要的變革。
1.搶占支持(preemption): 2.6 時代開始支持(具體時間難考，是在 2.5 這個奇數版本中引入，可看此文章[1]，關于 Linux 版本規則，可看我文章[2])。
可搶占性，對一個系統的調度延時具有重要意義。2.6 之前，一個進程進入內核態后，別的進程無法搶占，只能等其完成或退出內核態時才能搶占，這帶來嚴重的延時問題，2.6 開始支持內核態搶占。
2.普通進程調度器(SCHED_OTHER)之糾結進化史
Linux一開始，普通進程和實時進程都是基于優先級的一個調度器，實時進程支持 100 個優先級，普通進程是優先級小于實時進程的一個靜態優先級，所有普通進程創建時都是默認此優先級，但可通過 nice() 接口調整動態優先級(共40個)。實時進程的調度器比較簡單，而普通進程的調度器，則歷經變遷[3]：
(1) O(1) 調度器：2.6 時代開始支持(2002年引入)。顧名思義，此調度器為O(1)時間復雜度。該調度器以修正之間的O(n) 時間復雜度調度器，以解決擴展性問題。為每一個動態優先級維護隊列，從而能在常數時間內選舉下一個進程來執行。
(2) 夭折的 RSDL(The Rotating Staircase Deadline Scheduler)調度器，2007 年4 月提出，預期進入2.6.22，后夭折。
O(1) 調度器存在一個比較嚴重的問題：復雜的交互進程識別啟發式算法-為了識別交互性的和批處理型的兩大類進程，該啟發式算法融入了睡眠時間作為考量的標準，但對于一些特殊的情況，經常判斷不準，而且是改完一種情況又發現一種情況。
Con Kolivas (八卦：這家伙白天是個麻醉醫生)為解決這個問題提出RSDL(The Rotating Staircase Deadline Scheduler)算法。該算法的亮點是對公平概念的重新思考：交互式(A)和批量式(B)進程應該是被完全公平對待的，對于兩個動態優先級完全一樣的 A，B 進程，它們應該被同等地對待，至于它們是交互式與否(交互式的應該被更快調度), 應該從他們對分配給他們的時間片的使用自然地表現出來，而不是應該由調度器自作高明地根據他們的睡眠時間去猜測。這個算法的核心是Rotating Staircase，它是一種衰減式的優先級調整，不同進程的時間片使用方式不同，會讓它們以不同的速率衰減(在優先級隊列數組中一級一級下降，這是下樓梯這名字的由來)，從而自然地區分開進程是交互式的(間歇性的少量使用時間片)和批量式的(密集的使用時間片)。具體算法細節可看這篇文章：The Rotating Staircase Deadline Scheduler [LWN.net]
(3) 完全公平的調度器(CFS), 2.6.23(2007年10月發布)
Con Kolivas 的完全公平的想法啟發了原O(1)調度器作者Ingo Molnar，他重新實現了一個新的調度器，叫CFS。新調度器的核心同樣是完全公平性，即平等地看待所有普通進程，讓它們自身行為彼此區分開來，從而指導調度器進行下一個執行進程的選舉。
具體說來，此算法基于一個理想模型。想像你有一臺無限個相同計算力的 CPU，那么完全公平很容易，每個 CPU 上跑一個進程即可。但是，現實的機器 CPU 個數是有限的，超過 CPU 個數的進程數不可能完全同時運行。因此，算法為每個進程維護一個理想的運行時間，及實際的運行時間，這兩個時間差值大的，說明受到了不公平待遇，更應得到執行。
至于這種算法如何區分交互式進程和批量式進程，很簡單。交互式的進程大部分時間在睡眠，因此它的實際運行時間很小，而理想運行時間是隨著時間的前進而增加的，所以這兩個時間的差值會變大。與之相反，批量式進程大部分時間在運行，它的實際運行時間和理想運行時間的差距就較小。因此，這兩種進程被區分開來。
CFS 的測試性能比 RSDS 好，并得到更多的開發者支持，所以它最終替代了 RSDL 在 2.6.23 進入內核，一直使用到現在。可以八卦的是，Con Kolivas 因此離開了社區，不過他本人否認是因為此事，心生齟齬。后來，2009 年，他對越來越龐雜的 CFS 不滿意，認為 CFS 過分注重對大規模機器，而大部分人都是使用少 CPU 的小機器，開發了 BFS 調度器[4]，這個在 Android 中有使用，沒進入 Linux 內核。
3.有空時再跑 SCHED_IDLE, 2.6.23(2007年10月發布)
此調度策略和 CFS 調度器在同一版本引入。系統在空閑時，每個 CPU 都有一個 idle 線程在跑，它什么也不做，就是把 CPU 放入硬件睡眠狀態以節能(需要特定CPU的driver支持)，并等待新的任務到來，以把 CPU 從睡眠狀態中喚醒。如果你有任務想在 CPU 完全 idle 時才執行，就可以用sched_setscheduler() API 設置此策略。
4.吭哧吭哧跑計算 SCHED_BATCH, 2.6.16(2006年3月發布)
概述中講到 SCHED_BATCH 并非 POSIX 標準要求的調度策略，而是 Linux 自己額外支持的。
它是從 SCHED_OTHER 中分化出來的，和 SCHED_OTHER 一樣，不過該調度策略會讓采用策略的進程比 SCHED_OTHER 更少受到調度器的重視。因此，它適合非交互性的，CPU 密集運算型的任務。如果你事先知道你的任務屬于該類型，可以用 sched_setscheduler() API 設置此策略。
在引入該策略后，原來的 SCHED_OTHER 被改名為 SCHED_NORMAL，不過它的值不變，因此保持API 兼容，之前的 SCHED_OTHER 自動成為 SCHED_NORMAL，除非你設置 SCHED_BATCH。
5.十萬火急，限期完成 SCHED_DEADLINE, 3.14(2014年3月發布)
此策略支持的是一種實時任務。對于某些實時任務，具有陣發性(sporadic)，它們陣發性地醒來執行任務，且任務有deadline 要求，因此要保證在deadline 時間到來前完成。為了完成此目標，采用該 SCHED_DEADLINE 的任務是系統中最高優先級的，它們醒來時可以搶占任何進程。
如果你有任務屬于該類型，可以用 sched_setscheduler() 或 sched_setattr() API 設置此策略。
更多可參看此文章：Deadline scheduling: coming soon? [LWN.net]
#p#
6.普通進程的組調度支持(Fair Group Scheduling), 2.6.24(2008年1月發布)
2.6.23 引入的 CFS 調度器對所有進程完全公平對待。但這有個問題，設想當前機器有2個用戶，有一個用戶跑著9個進程，還都是CPU 密集型進程;另一個用戶只跑著一個 X 進程，這是交互性進程。從 CFS 的角度看，它將平等對待這 10 個進程，結果導致的是跑 X 進程的用戶受到不公平對待，他只能得到約 10% 的 CPU 時間，讓他的體驗相當差。
基于此，組調度的概念被引入[6]。CFS 處理的不再是一個進程的概念，而是調度實體(sched entity)，一個調度實體可以只包含一個進程，也可以包含多個進程。因此，上述例子的困境可以這么解決：分別為每個用戶建立一個組，組里放該用戶所有進程，從而保證用戶間的公平性。
該功能是基于控制組(control group, cgroup)的概念，需要內核開啟 CGROUP 的支持才可使用。關于 CGROUP ，以后可能會寫。
7.實時進程的組調度支持(RT Group Scheduling), 2.6.25(2008年4月發布)
該功能同普通進程的組調度功能一樣，只不過是針對實時進程的。
8.組調度帶寬控制((CFS bandwidth control)，3.2(2012年1月發布)
組調度的支持，對實現多租戶系統的管理是十分方便的，在一臺機器上，可以方便對多用戶進行 CPU 均分。然后，這還不足夠，組調度只能保證用戶間的公平，但若管理員想控制一個用戶使用的最大CPU 資源，則需要帶寬控制。3.2 針對 CFS組調度，引入了此功能[6]，該功能可以讓管理員控制在一段時間內一個組可以使用 CPU 的最長時間。
9.極大提高體驗的自動組調度(Auto Group Scheduling)，2.6.38(2011年3月發布)
試想，你在終端里熟練地敲擊命令，編譯一個大型項目的代碼，如Linux內核，然后在編譯的同時悠閑地看著電影等待，結果電腦卻非?？ǎw驗一定很不爽。
2.6.38 引入了一個針對桌面用戶體驗的改進，叫做自動組調度.短短400多行代碼[7]，就很大地提高了上述情形中桌面使用者體驗，引起不小轟動。
其實原理不復雜，它是基于之前支持的組調度的一個延伸。Unix 世界里，有一個會話(session) 的概念，即跟某一項任務相關的所有進程，可以放在一個會話里，統一管理。比如你登錄一個系統，在終端里敲入用戶名，密碼，然后執行各種操作，這所有進程，就被規劃在一個會話。
因此，在上述例子里，編譯代碼和終端進程在一個會話里，你的瀏覽器則在另一個會話里。自動組調度的工作就是，把這些不同會話自動分成不同的調度組，從而利用組調度的優勢，使瀏覽器會話不會過多地受到終端會話的影響，從而提高體驗。
該功能可以手動關閉。
10.基于調度域的負載均衡，2.6.7(2004年6月發布)
計算機依靠并行度來突破性能瓶頸，CPU個數也是與日俱增。最早的是 SMP(對稱多處理)，所以 CPU共享內存，并訪問速度一致。隨著 CPU 個數的增加，這種做法不適應了，因為 CPU 個數的增多，增加了總線訪問沖突，這樣 CPU 增加的并行度被訪問內存總線的瓶頸給抵消了，于是引入了 NUMA(非一致性內存訪問)的概念。機器分為若干個node，每個node(其實一般就是一個socket)有本地可訪問的內存，也可以通過 interconnect 中介機構訪問別的 node 的內存，但是訪問速度降低了，所以叫非一致性內存訪問。Linux 2.5版本時就開始了對NUMA 的支持[5]。
而在調度器領域，調度器有一個重要任務就是做負載均衡。當某個 CPU 出現空閑，就要從別的 CPU 上調整任務過來執行;當創建新進程時，調度器也會根據當前負載狀況分配一個最適合的 CPU 來執行。然后，這些概念是大大簡化了實際情形。
在一個 NUMA 機器上，存在下列層級：
◆每一個NUMA node 是一個 CPU socket(你看主板上CPU位置上那一塊東西就是一個socket)。
◆每一個socket上，可能存在兩個核，甚至四個核。
◆每一個核上，可以打開硬件多純程(HyperThread)。
如果一個機器上同時存在這三個層級，則對調度器來說，它所見的一個邏輯 CPU其實是一個HyperThread。處理同一個core 中的CPU，可以共享L1，乃至 L2 緩存，不同的 core 間，可以共享 L3 緩存(如果存在的話)。
基于此，負載均衡不能簡單看不同 CPU 上的任務個數，還要考慮緩存，內存訪問速度。所以，2.6.7 引入了調度域(sched domain) 的概念，把 CPU 按上述層級劃分為不同的層級，構建成一棵樹，葉子節點是每個邏輯 CPU，往上一層，是屬于 core 這個域，再往上是屬于 socket 這個域，再往上是 NUMA 這個域，包含所有 CPU。
當進行負載均衡時，將從最低一級域往上看，如果能在 core 這個層級進行均衡，那最好;否則往上一級，能在socket 一級進行均衡也還湊合;最后是在 NUMA node 之間進行均衡，這是代價非常大的，因為跨 node 的內存訪問速度會降低，也許會得不償失，很少在這一層進行均衡。
這種分層的做法不僅保證了均衡與性能的平衡，還提高了負載均衡的效率。
關于這方面，可以看這篇文章：Scheduling domains [LWN.net]
11.更精確的調度時鐘(HRTICK), 2.6.25(2008年4月發布)
CPU的周期性調度，和基于時間片的調度，是要基于時鐘中斷來觸發的。一個典型的 1000 HZ 機器，每秒鐘產生 1000 次時間中斷，每次中斷到來后，調度器會看看是否需要調度。
然而，對于調度時間粒度為微秒(10^-6)級別的精度來說，這每秒 1000 次的粒度就顯得太粗糙了。
2.6.25引入了所謂的高清嘀噠(High Resolution Tick)，以提供更精確的調度時鐘中斷。這個功能是基于高清時鐘(High Resolution Timer)框架，這個框架讓內核支持可以提供納秒級別的精度的硬件時鐘(將會在時鐘子系統里講)。
12.自動 NUMA 均衡(Automatic NUMA balancing)，3.8(2013年2月發布)
NUMA 機器一個重要特性就是不同 node 之間的內存訪問速度有差異，訪問本地 node 很快，訪問別的 node 則很慢。所以，進程分配內存時，總是優先分配所在 node 上的內存。然而，前面說過，調度器的負載均衡是可能把一個進程從一個 node 遷移到另一個 node 上的，這樣就造成了跨 node 的內存訪問;Linux 支持 CPU 熱插拔，當一個 CPU 下線時，它上面的進程會被遷移到別的 CPU 上，也可能出現這種情況。
調度者和內存領域的開發者一直致力于解決這個問題.由于兩大系統都非常復雜，找一個通用的可靠的解決方案不容易，開發者中提出兩套解決方案，各有優劣，一直未能達成一致意見。3.8內核中，內存領域的知名黑客 Mel Gorman 基于此情況，引入一個叫自動 NUMA 均衡的框架，以期存在的兩套解決方案可以在此框架上進行整合;同時，他在此框架上實現了簡單的策略：每當發現有跨 node 訪問內存的情況時，就馬上把該內存頁面遷移到當前 node 上。
不過到 4.2 ，似乎也沒發現之前的兩套方案有任意一個遷移到這個框架上，倒是，在前述的簡單策略上進行更多改進。
如果需要研究此功能的話，可參考以下幾篇文章：
◆介紹 3.8 前兩套競爭方案的文章：A potential NUMA scheduling solution [LWN.net]
◆介紹 3.8 自動 NUMA 均衡 框架的文章：NUMA in a hurry [LWN.net]
◆介紹 3.8 后進展的兩篇文章，細節較多，建議對調度/內存代碼有研究后才研讀：
NUMA scheduling progress [LWN.net]
https://lwn.net/Articles/591995/
13.CPU 調度與節能
從節能角度講，如果能維持更多的 CPU 處于深睡眠狀態，僅保持必要數目的 CPU 執行任務，就能更好地節約電量，這對筆記本電腦來說，尤其重要。然而，這不是一個簡單的工作，這涉及到負載均衡，調度器，節能模塊的并互，Linux 調度器中曾經有相關的代碼，但后來發現問題，在3.5, 3.6 版本中，已經把相關代碼刪除.整個問題需要重新思考。
在前不久，一個新的 patch 被提交到 Linux 內核開發郵件列表，這個問題也許有了新的眉目，到時再來更新此小節.可閱讀此文章：Steps toward power-aware scheduling
引用：
[3] IBM developworks 上有一篇綜述文章，值得一讀：Linux調度器發展簡述
[4]CFS group scheduling [LWN.net]
[5]http://lse.sourceforge.net/numa/
[6]CFS bandwidth control [LWN.net]
[7]kernel/git/torvalds/linux.git
