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

目前創(chuàng)新互聯(lián)已為上千多家的企業(yè)提供了網(wǎng)站建設(shè)、域名、雅安服務(wù)器托管、網(wǎng)站運(yùn)營、企業(yè)網(wǎng)站設(shè)計(jì)、高邑網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

0.分時(shí)系統(tǒng)

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

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

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

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

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

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

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

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

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

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

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

2.何謂樸素

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

本文名稱：樸素的UNIX之-調(diào)度器前傳-創(chuàng)新互聯(lián)
網(wǎng)頁地址：http://weahome.cn/article/cssdse.html