Linux目前的進程調(diào)度算法是CFS算法，替換了之前的時間片輪轉(zhuǎn)調(diào)度算法，CFS算法平滑了動態(tài)優(yōu)先級的計算過程，使整個系統(tǒng)在任何時間都可以被任何 執(zhí)行實體搶占，事實上這是分時系統(tǒng)的基本原則，試想，如何每一個進程/線程都像中斷那樣，依靠自己的優(yōu)先級隨時執(zhí)行，那整個系統(tǒng)才真的成了“公平的”利他 系統(tǒng)。要想理解這種利他行為的本質(zhì)，如果我們?nèi)パ芯緾FS調(diào)度算法的各種統(tǒng)計數(shù)據(jù)，或者去研究其代碼，那么其效果肯定是不好的，如果我們?nèi)パ芯?Windows NT內(nèi)核的調(diào)度算法，無疑也會浪費大量的時間和精力，最終陷入了細節(jié)。
       事實上，UNIX最樸素的早期版本便是這種思想的最佳體現(xiàn)，其代碼及其簡潔，邏輯及其簡單。

創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設,南關(guān)企業(yè)網(wǎng)站建設,南關(guān)品牌網(wǎng)站建設,網(wǎng)站定制,南關(guān)網(wǎng)站建設報價,網(wǎng)絡營銷,網(wǎng)絡優(yōu)化,南關(guān)網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學習、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。

0.分時系統(tǒng)

馮. 諾依曼的存儲式機器有兩個要點，更抽象得講，這就是圖靈機。CPU和內(nèi)存，兩大部件，如果想要實現(xiàn)分時系統(tǒng)，那么看看早期的人們是怎么使用計算機的，或者 怎么使用機床的，反正任意一臺共享的機器...人們排著隊，手里面拿著牌子，然后管理員叫號，其實就跟如今銀行里辦理業(yè)務一樣...但是這些實現(xiàn)在計算機 里面，就簡單多了，只有兩點需要實現(xiàn)，即：如何使用CPU，如何使用內(nèi)存。關(guān)于這兩點，看似簡單，其實還真的有些細節(jié)。如何使用CPU，那就必須一個個 來，一次性執(zhí)行完任務，然后下一個，但是如果一個任務時間太久，后面的排隊者難免長時間等待，于是按照任務的生命周期分時便顯得粒度過于粗糙了，更細粒度 的分時系統(tǒng)便是需求，要想實現(xiàn)更細粒度的分時系統(tǒng)，就需要一個上下文，以便一個被管理員中斷的任務接著執(zhí)行，這個上下文必須有一個存儲的位置，那就是內(nèi) 存，這就涉及到了如何使用內(nèi)存的問題。
       談到內(nèi)存的使用，簡單來講就是整個物理內(nèi)存被所有的進程共享，如何共享呢？當然要涉及到分配策略，即為一個進程分配一塊內(nèi)存區(qū)域，為另一個進程分配另一塊 內(nèi)存區(qū)域，按照這個思路來理解分段和分頁就容易了，總之，分段一般用于一個進程內(nèi)部不同的內(nèi)存類型的區(qū)分，比如代碼，數(shù)據(jù)，堆棧等，而分頁一般用于進程之 間的內(nèi)存頁面劃分，比如一個頁面屬于一個進程，另一個頁面屬于另一個區(qū)域，到底怎么劃分，總得需要一張表來指示，對于現(xiàn)代操作系統(tǒng)而言，這張表就是我們熟 悉的頁表，對于古老的PDP11來講，就是APR寄存器組的內(nèi)容。分時操作系統(tǒng)的任務就包括管理這些表以及管理整個物理內(nèi)存。在一個進程切換到另一個進程 的時候，這些表的內(nèi)容也必須隨之切換，對于現(xiàn)代的x86平臺，我們比較熟悉的就是CR3寄存器的切換，而CR3寄存器指向常駐物理內(nèi)存的頁表，無疑，這塊 物理內(nèi)存便不能被進程所用了，因為它存放的是進程元數(shù)據(jù)。早在PDP11年代，由于物理內(nèi)存容量很小，不可能采用這種方式來存儲元數(shù)據(jù)，它也并沒有實現(xiàn)精 密的分頁機制，只是實現(xiàn)了一個樸素的虛擬地址空間，由APR寄存器組來定義虛擬地址和物理內(nèi)存頁面的映射關(guān)系。因此在PDP11年代，都是整個進程全部換 入換出的，不存在一個進程的一部分駐留內(nèi)存，而另一部分在交換空間，由缺頁中斷按需調(diào)入內(nèi)存。
       本質(zhì)上講，樸素的分時系統(tǒng)包括兩方面內(nèi)容，CPU分時使用，物理內(nèi)存分時使用。當然如果物理內(nèi)存足夠大，那么可以將多個進程同時駐留內(nèi)存，這樣無疑會提高 效率，但是這并不是分時系統(tǒng)的本質(zhì)，包括后來的按需調(diào)頁機制也并非分時系統(tǒng)的本質(zhì)，而只是一種MMU管理手段。
       分時系統(tǒng)的實現(xiàn)，內(nèi)存管理是極其重要的，因為內(nèi)存是按空間來編排的，并非像CPU那樣是按時鐘嘀嗒驅(qū)動的，如何將空間使用和時鐘嘀嗒聯(lián)系起來并建立映射是 分時系統(tǒng)實現(xiàn)的關(guān)鍵，因此我才會花大量的篇幅來介紹內(nèi)存管理方面的細節(jié)。分時系統(tǒng)的實現(xiàn)是遞歸分形的，因此出現(xiàn)了搶占的概念，如果說細粒度的分時系統(tǒng)實現(xiàn) 搶占了未完成的任務，那么動態(tài)優(yōu)先級的計算導致出現(xiàn)更高優(yōu)先級進程引發(fā)的切換則搶占了未完成的預分配給進程的時間片。

1.UNIX v6的進程調(diào)度

我 們知道UNIX出生在1969年，但是那個初生的UNIX并不是真正的UNIX，因為它沒有著名的fork調(diào)用，它只能說是可以運行固定2個進程的分時系 統(tǒng)，另外因為這兩個進程連接兩個終端，而終端屬于用戶，此時的UNIX就算是一個多用戶系統(tǒng)了。因此1969年的UNIX雖然不成熟，但確實是一個多進程 多用戶的分時系統(tǒng)，現(xiàn)代操作系統(tǒng)的歷史開篇了。第一個成熟的UNIX是為UNIX v6，也就是著名的萊昂氏神書介紹的那個版本，我稱之為樸素的UNIX。
       在理解樸素的UNIXv6調(diào)度機制之前，必須理解早期運行UNIX系統(tǒng)的內(nèi)存管理機制，在PDP11中，并沒有如今x86平臺的那種精密的分頁MMU設 施。PDP11通過一組叫做APR的寄存器來實現(xiàn)虛擬地址空間，注意，這里使用的是配置在一組寄存器的表，而不是常駐物理內(nèi)存的表。由于寄存器數(shù)量的限 制，這類寄存器表的容量注定不可能太大，因此虛擬地址空間到物理地址空間的轉(zhuǎn)換注定是簡單的，你不可能用多級頁表的理念去嘲笑PDP11的虛擬地址空間的 管理邏輯，即便是多級頁表管理機制，也是一步一步發(fā)展起來的。關(guān)于虛擬內(nèi)存地址空間，我會專門開辟一篇文章來講述樸素的UNIX是如何定義虛擬地址的，在 本文，為了不喧賓奪主，我只能用短短幾言來評價虛擬地址空間：如果說C語言為程序員提供了一套通用的工具，那么虛擬地址空間則為程序員提供了一塊通用固定 大小的空間連續(xù)的場地，有了C語言和虛擬地址空間，程序員便可以不必關(guān)注機器的細節(jié)，C語言為程序員隔離了底層的處理器細節(jié)，虛擬地址空間為程序員隔離了 物理內(nèi)存大小，類型等細節(jié)，程序員認為數(shù)據(jù)在內(nèi)存中，但事實上這里的內(nèi)存只是虛擬內(nèi)存的意思，數(shù)據(jù)真正存在的位置可能是物理內(nèi)存，也可能是磁盤，網(wǎng)絡。
    回到上面的話題，PDP11采用了樸素的一組寄存器來保存虛擬內(nèi)存地址到物理內(nèi)存地址的映射，這是在實現(xiàn)全面分頁按需調(diào)頁機制之前最全面最樸素的機制。因為它按分時系統(tǒng)的定義看來，實現(xiàn)及其簡單高效。它只需要完成：
每一個進程都擁有一組APR寄存器，保存著虛擬地址到物理地址的映射，進程切換時切換APR寄存器組；
一個寄存器映射一個頁面，將一個8k的虛擬頁面映射到一個8k的物理頁面，一組寄存器一共8對，映射8個頁面，因此一個進程的虛擬地址空間總大小為8*8k；
上 面簡述的樸素UNIXv6的MMU機制中直接蘊含了后來的多級頁表機制，它們和PDP11的MMU唯一的區(qū)別就是多級頁表使表項常駐內(nèi)存，這是因為進程需 要越來越大的空間，使得多級頁表成為了需求，而這種需求又因為內(nèi)存越來越大而得到滿足，而寄存器反而越來越不適合來做這種事情，MMU緩存TLB，也稱快 表，這個設施某種程度上替代了APR之類的寄存器。值得注意的是，多級頁表是狹義的，其實在PDP11的APR時期，MMU表就是多級的，一個寄存器映射 整整一個頁面而不是一個地址，頁面內(nèi)的偏移直接由虛擬地址指定。
       但是在物理內(nèi)存很小的年代，進程不可能也不必擁有太大的虛擬地址空間，也不可能通過多級頁表來構(gòu)建MMU表的，因為它會浪費更多的物理內(nèi)存來存儲元數(shù)據(jù)。 有人說，多級頁表節(jié)省內(nèi)存，那是大錯特錯啊，多級頁表節(jié)省內(nèi)存存在一個前提，那就是巨大的4G地址空間很多頁面都用不到，因此不用建立頁表和頁表項。如果 每一個虛擬地址空間的頁面都被使用，那反而需要更多的內(nèi)存來存儲多級頁表。另外，多級頁表在實現(xiàn)了按需調(diào)頁的精密虛擬內(nèi)存管理之后才有比較大的用武之地。 后面專門描述樸素的UNIX內(nèi)存管理的時候，我會詳細描述。
       好了，說了這么多的MMU相關(guān)的東西，終于開始說進程調(diào)度了。要知道，在PDP11年代，虛擬地址空間只有64k的大小，而物理內(nèi)存總線寬度卻有18位， 也就是256k，物理內(nèi)存空間遠大于虛擬內(nèi)存空間，一般安裝的物理內(nèi)存都在64k以上，因此完全有能力讓一個進程一次性完全駐留物理內(nèi)存，一個進程在運行 的時候可以全部駐留內(nèi)存，但是在長期不運行的時候就可以被換出到交換空間中。對于UNIXv6分時系統(tǒng)的實現(xiàn)，這種硬件架構(gòu)促使偉大又樸素的進程調(diào)度系統(tǒng) 完美出爐。UNIXv6的調(diào)度機制如下圖所示：
(我不得不在此忽略圖示，因為我準備在下一篇文章中使用這張圖，因為我要拿它來和其它的調(diào)度器作對比，這樣顯得更加緊湊，如果你能看懂下面的要點，你一定要在腦子里面想象一下那副圖的樣子)
這種調(diào)度機制有以下幾個要點：

1)進程切換需要0號進程的協(xié)助，一個進程除非自己放棄CPU，否則必須將執(zhí)行權(quán)交給0號進程，然后由0號進程決定接下來誰運行。

為 什么非要通過0號進程中轉(zhuǎn)呢？如果理解了上面我大費口舌描述的PDP11的內(nèi)存管理機制，就會馬上理解通過0號進程中轉(zhuǎn)的原因了。因為樸素的PDP11上 的UNIXv6-并沒有按需調(diào)頁機制的實現(xiàn)，它必須確保將要運行的進程的所有頁面是完全駐留內(nèi)存的，因此必須通過0號進程來確保這一點。0號進程也叫 swap進程，也叫調(diào)度進程，它只要被喚醒就會執(zhí)行進程的換入換出，將將要運行的進程換入內(nèi)存，將長期不運行的進程換出內(nèi)存，如果這么做了，并且實在沒有 進程需要換入換出了，0號進程才會將控制權(quán)轉(zhuǎn)交給最高優(yōu)先級的進程，自己則睡眠，如果一開始就沒有這樣的事情要做，便把執(zhí)行權(quán)交給一個最高優(yōu)先級的進程， 自己直接睡眠。

2)進行的優(yōu)先級是實時重新計算的，只要有更高優(yōu)先級進程就緒，進程在用戶態(tài)是隨時可搶占的，進程在內(nèi)核態(tài)是絕對不能被強占的

樸 素的UNIXv6定義了一個原則，那就是，進程一定是可搶占的(因為它沒有時間片的概念)，但是有一個限制，處在內(nèi)核態(tài)的執(zhí)行流是不能被搶占的。 UNIXv6的每一個進程優(yōu)先級是在每N個時鐘中斷處理中實時重計算的，手冊上說是N的值是HZ，即1秒，但是也是可以在編譯前修改的，這種重計算的意義 在于發(fā)現(xiàn)更值得運行的進程，搶占當前的進程！這個思想其實就是當前的Linux的CFS調(diào)度思想以及Windows NT的調(diào)度思想，只是實現(xiàn)策略不同罷了。但是，為了保護內(nèi)核的數(shù)據(jù)結(jié)構(gòu)，定義了一個例外，即內(nèi)核態(tài)的執(zhí)行流不能被用戶進程搶占，這就是刑不上大夫策略，這 個策略雖然最后被內(nèi)核搶占打破，但事實上在服務器領域，特別是需要高吞吐量的環(huán)境下，它依然是最棒的。體制(搶占式)是不變的，但政策(刑不上大夫)卻是 與時俱進的。

3)進程的執(zhí)行間隔是平滑的，進程餓死的幾率很小

我們可以評估一下Linux 2.4的O(n)調(diào)度以及Linux 2.6的O(1)調(diào)度，這兩種算法的最大問題就是進程饑餓，于是出現(xiàn)了各種復雜繁瑣的重新計算優(yōu)先級的所謂“小技巧”，最終適得其反，幸虧CFS此時猶抱 琵琶半遮面，否則....其實問題并不大，因為Win7也面臨的同樣的問題，但是基于Windows NT構(gòu)建的系統(tǒng)有一個平衡器，類似一個內(nèi)核線程，它會定期掃描饑餓線程，將其優(yōu)先級提升，就這樣，在Linux的O(1)在盡力補償交互進程的時 候，Windows便傾注全力高捧而不是補償交互進程，Windows一直都有服務器版本和家用版本，其實跟Linux在編譯時是否啟用內(nèi)核搶占之類的區(qū) 別是差不多的，Windows NT的服務器和家用版本的不同還體現(xiàn)在時間片長短的不同上。樸素的UNIX并沒有這樣的問題，進程的優(yōu)先級是實時計算的，只要有更高優(yōu)先級進程，隨時搶 占，這只是其一，其二就是內(nèi)核執(zhí)行流的優(yōu)先級是和用戶態(tài)執(zhí)行流優(yōu)先級有所區(qū)別的。
       再次值得注意的是，樸素的UNIX進程調(diào)度并非基于時間片的，每一個進程都沒有在運行前計算好的時間片，之有有更適合的進程就緒，馬上搶占當前進程(排除 內(nèi)核態(tài)的進程)。這種平滑的調(diào)度機制要求調(diào)度策略必須是搶占式的，內(nèi)核非搶占(刑不上大夫只是暫時在沒有更好的辦法之前為了保護機要數(shù)據(jù)，一旦有了更好的 保護機制，內(nèi)核必定也是可搶占的！)

4)進程處在內(nèi)核態(tài)時，一旦阻塞，其喚醒時的優(yōu)先級由阻塞原因而定，由于內(nèi)核態(tài)優(yōu)先級比用戶態(tài)優(yōu)先級高，內(nèi)核機要機構(gòu)快速出入

關(guān) 于這一點，我覺得Windows NT內(nèi)核和Solaris內(nèi)核做的超級棒！它們都是將所有的執(zhí)行流都映射到一定的優(yōu)先級之上，即便是中斷也有自己的優(yōu)先級，即便是普通的進程，在執(zhí)行某件 事情的時候，也可以處在中斷的優(yōu)先級上，Solaris走得更遠，它將中斷作為線程來調(diào)度...但是你可知道，早在1975的UNIXv6，這種思想便已 經(jīng)體現(xiàn)了系統(tǒng)中了。UNIXv6將睡眠進程喚醒后的優(yōu)先級和睡眠原因關(guān)聯(lián)，如果你同時也看過《Windows Internals》這本書，你就會發(fā)現(xiàn)，Windows在“I/O完成以后優(yōu)先級的提升”也是和I/O原因關(guān)聯(lián)的，比如磁盤I/O完成后線程優(yōu)先級的提 升值就沒有聲卡I/O完成后線程優(yōu)先級提升的高，這個UNIXv6是多么類似。

2.何謂樸素

我說UNIXv6是樸素的，但是何謂樸素？
       所謂樸素，就是精簡。在下一篇文章中，你會發(fā)現(xiàn)，幾乎所有的現(xiàn)代操作系統(tǒng)的調(diào)度機制的思想，都可以關(guān)聯(lián)到UNIXv6的調(diào)度機制，甚至還不如UNIXv6。比如Linux的早期版本。比較類似的有：
UNIXv6調(diào)度器與Windows NT的所有版本調(diào)度器
UNIXv6調(diào)度器與Linux CFS調(diào)度器