從2.x到4.x，Linux內核這十年經歷了哪些重要變革
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]