1、FreeBSD虛擬內(nèi)存 VM 系統(tǒng)設(shè)計原理來源：版權(quán)說明：這篇文章原載于2000年1月的DaemonNews。這份版本可能包括了Matt以及其他作者的更新，以反映FreeBSD VM實現(xiàn)的進(jìn)展。這個標(biāo)題實在是一個很自負(fù)的說法，我的意思是，我正試圖描述整個FreeBSD VM系統(tǒng)，以一種讓多數(shù)人都能夠接受的方式。在過去的一年中，我集中精力于FreeBSD的主要內(nèi)核子系統(tǒng)中的大量模塊，特別是VM和磁盤交換(Swap)子系統(tǒng)，以及相關(guān)的NFS代碼。我只是重寫了所有代碼中很少的部分。在VM領(lǐng)域，我做的最主要的重寫是針對磁盤交換部分的代碼進(jìn)行的。我的絕大部分工作是清理和維護(hù)，其中包括適度的代碼重寫，而沒

2、有對VM子系統(tǒng)中的算法進(jìn)行大規(guī)模的調(diào)整。VM子系統(tǒng)的主要理論基礎(chǔ)沒有發(fā)生變化，而絕大多數(shù)與VM相關(guān)的功績應(yīng)該歸于John Dyson和David Greenman。與Kirk這樣有資歷的學(xué)者不同，我并不想嘗試為每一個特性標(biāo)記特定的人名，因為我經(jīng)常把他們搞錯。1.入門在開始介紹實際的設(shè)計之前，讓我們來花些時間來介紹維護(hù)，并讓那些存在已久的代碼基礎(chǔ)(codebase)進(jìn)行現(xiàn)代化的必要性。在編程者的世界中，算法總是趨于比代碼更為重要。同時，作為BSD的學(xué)術(shù)傳統(tǒng)的一部分，在開始時就對算法設(shè)計加以特別的關(guān)注也恰好符合這一點(diǎn)。在設(shè)計上給予特別的關(guān)注的結(jié)果通常就是一個干凈而靈活的代碼基礎(chǔ)，它能夠被很容易地修

3、改、擴(kuò)展，或隨著時間的推移被替換掉。盡管BSD被某些人認(rèn)為是一個古舊的操作系統(tǒng)，我們這些為之工作的人則認(rèn)為它更多地是一個成熟的代碼基礎(chǔ)，其上的眾多組件被修改、擴(kuò)展甚至替換為現(xiàn)代化的代碼。它正在進(jìn)化，而且，無論代碼中的某些部分多么地古老，F(xiàn)reeBSD總在接受新鮮血液。這是FreeBSD的一項重要特點(diǎn)，而許多人往往忽視了它。程序員能夠犯下的最大錯誤是不肯學(xué)習(xí)歷史，而這是許多其他現(xiàn)代操作系統(tǒng)中非常常見的問題。NT是一個最好的例子，而其結(jié)果是相當(dāng)可怕的。Linux也不同程度地犯下了許多類似的錯誤-這些錯誤足夠在BSD開發(fā)者中間，每隔一段時間就流傳一次笑話。Linux的問題可以簡單地歸結(jié)為，缺乏可以用

4、來比較思想的經(jīng)驗和歷史，在不斷的代碼開發(fā)過程中，Linux團(tuán)隊可以和BSD團(tuán)隊一樣快捷地找到問題所在。而NT的開發(fā)者，另一方面，重復(fù)地犯下Unix幾十年前就已經(jīng)解決掉的錯誤，并且花上幾年來修復(fù)它們，并且一而再、再而三地這樣做。他們最嚴(yán)重的問題是not designed here(此處沒有進(jìn)行設(shè)計)和we are always right because our marketing department says so(我們永遠(yuǎn)是對的，因為我們的市場部門這樣說)。我認(rèn)為不愿學(xué)習(xí)歷史的人是不能被原諒的。許多FreeBSD設(shè)計中非常明顯地復(fù)雜的部分，特別是在VM/Swap子系統(tǒng)中的那些，是在不同條件

5、下不得不解決的那些性能問題的直接結(jié)果。這些問題并不是由糟糕的算法設(shè)計造成的，它們來自實際的環(huán)境。在平臺之間的直接比較中，這些問題由于系統(tǒng)資源受到重壓而變得非常明顯。在我描述FreeBSD的VM/Swap子系統(tǒng)的同時，讀者應(yīng)始終在頭腦中保持兩個重要的概念。首先，高性能的設(shè)計的重要方面是我們常說的優(yōu)化關(guān)鍵路徑。這一原則通常的結(jié)果是代碼的膨脹，因為它能夠讓關(guān)鍵路徑的代碼的性能變得更好。第二，堅固的、范型化的設(shè)計在長時間的運(yùn)行中勝過那些深度最優(yōu)化的設(shè)計。盡管范型化的設(shè)計與那些經(jīng)過深度優(yōu)化的設(shè)計相比，前者的性能在最初實現(xiàn)中可能更差，但范型化設(shè)計能夠更容易地適應(yīng)變化的條件，而過分深度優(yōu)化的設(shè)計則無法適應(yīng)，

6、以至于不得不丟棄。任何得以幸存，并在幾年后能夠被維護(hù)的代碼基礎(chǔ)，因此都必須從一開始就進(jìn)行正確的設(shè)計，即使它的代價是少量性能上的衰退。20年前，人們曾認(rèn)為使用匯編語言要好于高級語言，因為它能夠產(chǎn)生快10倍以上的代碼；而今天，上述論點(diǎn)的錯誤是非常明顯的，因為算法設(shè)計和編譯技術(shù)的發(fā)展已經(jīng)大大降低了高級語言與匯編語言的差距。2.VM對象開始描述FreeBSD VM系統(tǒng)的最好方法是從用戶級進(jìn)程的方面去觀察它。每一個用戶進(jìn)程可以看到一個單獨(dú)的、私有的、連續(xù)的虛擬內(nèi)存地址空間，包括多種類型的內(nèi)存對象。這些對象有不同的特征。程序代碼和數(shù)據(jù)被保存在一個單獨(dú)的內(nèi)存映射文件(將要執(zhí)行的二進(jìn)制文件)中，但程序代碼是只

7、讀的，而數(shù)據(jù)則是寫時復(fù)制的。程序BSS是分配的內(nèi)存，而在需要時它們將被清零，這也被稱作按需填零頁。同時，任何文件都可以被映射到內(nèi)存地址空間，這也是共享庫(shared library,Windows上的動態(tài)連接庫與它類似，譯注)的工作機(jī)制。這類映射可以要求其上的修改對進(jìn)程私有。fork系統(tǒng)調(diào)用則是VM管理問題中更為復(fù)雜的一個。從程序的二進(jìn)制數(shù)據(jù)頁(基本上是寫時復(fù)制頁)可以看出上述問題的復(fù)雜性。程序的二進(jìn)制代碼包括了預(yù)先初始化的數(shù)據(jù)部分，它們在初始時，從程序文件直接映射出來。當(dāng)程序被加載到一個進(jìn)程VM空間時，這一區(qū)域被進(jìn)行內(nèi)存映射，隨后由程序代碼本身進(jìn)行維護(hù)，讓VM系統(tǒng)來釋放/重用這些頁，或者從

8、程序文件中重新加載它們。但是，當(dāng)進(jìn)程修改這些數(shù)據(jù)時，VM系統(tǒng)必須為進(jìn)程作一份私有的副本。由于私有副本已經(jīng)被改變，VM系統(tǒng)就不能再釋放他們，因為如果這樣的話，就沒有辦法把它們重新恢復(fù)了。你馬上會注意到，原本簡單的文件映射變得復(fù)雜了許多。數(shù)據(jù)可能被一頁一頁地修改，而文件映射只是一次包含了許多頁。在進(jìn)程fork時，產(chǎn)生的兩個進(jìn)程-每一個都擁有私有的地址空間-都必須包括原先進(jìn)程在調(diào)用fork()之前的所有修改。讓VM系統(tǒng)一次制作所有數(shù)據(jù)的副本是愚蠢的，因為很可能兩個進(jìn)程中至少有一個只需要讀它們所在的頁，這使得原先的頁仍然可以被繼續(xù)使用。私有的頁被再次標(biāo)記為寫時復(fù)制，因為每個進(jìn)程(無論是父進(jìn)程還是子進(jìn)程

9、)都與其他們自己的、在fork之后的修改仍然是私有的，而不會影響另一個進(jìn)程。FreeBSD采用一種分層的VM對象模型來管理所有這些對象。最初的程序二進(jìn)制文件作為VM對象層中的最低部分。寫時復(fù)制層隨后被放到它頂上，以保持那些頁在需要時所產(chǎn)生的副本。如果程序修改了屬于原始文件的數(shù)據(jù)頁，VM系統(tǒng)將獲得一個中斷(fault)，并在更高的這層復(fù)制那一頁。當(dāng)進(jìn)程fork時，將產(chǎn)生附加的VM對象層。通過一個很基本的例子可以得到更多的感性認(rèn)識。fork是所有*BSD系統(tǒng)的一個公共的操作，因此這一事例將考慮一個程序開始，然后fork。當(dāng)進(jìn)程開始時，VM系統(tǒng)創(chuàng)建一個對象層，我們稱之為A：A表示文件-頁面可以在需要

10、時從文件的物理介質(zhì)中換入(page in)和換出(page out)。從磁盤上換入一部分?jǐn)?shù)據(jù)對程序來說是很正常的，但我們并不希望頁面被換出并覆蓋原始的可執(zhí)行文件。VM系統(tǒng)因此建立一個新的層，B，它將由交換空間進(jìn)行物理的維護(hù)。其后第一次頁面寫入將導(dǎo)致B中創(chuàng)建一個新的頁，它的內(nèi)容將根據(jù)A中的對應(yīng)頁初始化。所有B中的頁可以與交換設(shè)備換入和換出。當(dāng)程序fork時，VM系統(tǒng)創(chuàng)建兩個新的對象層，父進(jìn)程的C1和子進(jìn)程的C2，這兩層都在B上：在這個例子中，一個B中的頁由父進(jìn)程進(jìn)行了修改，進(jìn)程將得到一個寫時復(fù)制中斷，并復(fù)制C1中的頁，而B中的頁不會被觸及。現(xiàn)在，子進(jìn)程也修改了一些數(shù)據(jù)，于是在C2中發(fā)生了類似的事

11、情?，F(xiàn)在，B中的原始頁對于C1,C2都不再可見，因為C1和C2都擁有了一份私有的、修改過的副本；此外，如果B層并不表示一個實在的文件的話，它在理論上就可以釋放掉了。然而，釋放B層中的個別塊這類優(yōu)化的價值不高，因為它過于瑣碎，而且是如此的精細(xì)。FreeBSD并不進(jìn)行這類優(yōu)化。現(xiàn)在，假定(就像通常的情況那樣)，子進(jìn)程調(diào)用了exec()，那么當(dāng)前地址空間就被一個新的文件所表示的空間所代替。在這種情況中，C2層被釋放：在這種情況下，B的子節(jié)點(diǎn)個數(shù)下降到1，于是所有對B的訪問將直接通過C1完成。這意味著B和C1可以被折疊到一起。任何在B和C1中都存在的頁在折疊過程中都將從B中刪除。因而，盡管這一油花在前

12、一步驟中不被完成，但我們?nèi)匀豢梢栽趀xec()或exit時恢復(fù)那些不再使用的頁。這一模型造成了一系列潛在的問題。首先，你可能會得到一個相對深的VM對象層棧，當(dāng)產(chǎn)生中斷時，這將造成掃描時間的增加，并浪費(fèi)內(nèi)存。深的層在進(jìn)程fork并再次fork的時候(無論父進(jìn)程還是子進(jìn)程)產(chǎn)生。其次，那些不可能再次被訪問的頁可能逐步在VM對象棧中積累。我們的最后一個例子將是，當(dāng)父進(jìn)程和子進(jìn)程都修改了同一頁，它們都擁有了那一頁的私有副本，而B中的原始頁將不可能被訪問到時，B中的這一頁將被釋放。FreeBSD通過一種被稱作全覆蓋特例的特殊優(yōu)化來解決深層問題。這一情況發(fā)生于，當(dāng)C1或C2產(chǎn)生了足夠的寫時復(fù)制中斷，并完全

13、包含了B中的所有頁面時。以C1達(dá)到這一情況為例。C1現(xiàn)在可以完全繞過B，因此，我們不再采用C1BA和C2BA的訪問方式，相反，我們將采用C1A和C2BA。不過，另一方面，我們觀察到現(xiàn)在B只有1個引用(C2)，因此我們可以將B與C2折疊到一起。最終的結(jié)果是，B可以被整個刪除，因而我們有C1A和C2A。通常情況下，B將包括大量的頁面，而無論是C1還是C2都不能完全地蓋住它。如果此時我們再次fork，并創(chuàng)建一組D層，那么，就非常有可能D層最終完全覆蓋C1或C2中遠(yuǎn)小的數(shù)據(jù)集。同樣的優(yōu)化將在圖中的任意一點(diǎn)工作，而最終結(jié)果將是即使在經(jīng)常進(jìn)行fork的機(jī)器上，VM對象棧也基本上不會超過4層。無論父進(jìn)程和子

14、進(jìn)程是否進(jìn)行fork，無論子進(jìn)程是否進(jìn)行層疊的fork，上述結(jié)論都是正確的。某些不可能被訪問的頁面可能依然存在，如果C1和C2都不能完全覆蓋B。由于我們的其他優(yōu)化，這已經(jīng)不知造成問題，因此我們將允許這樣的頁面存在。如果系統(tǒng)內(nèi)存不足，則這些頁面將被換出，消耗一些交換空間，但不會包括其他的工作了。VM對象模型的好處是fork()非常快，因為并不需要實際進(jìn)行寫操作。缺點(diǎn)是VM對象層相對復(fù)雜，這略微減慢了缺頁中斷的處理，而且，需要額外的內(nèi)存來管理VM對象結(jié)構(gòu)。FreeBSD的優(yōu)化證明這些問題完全可以被忽略，從而實際上不存在什么缺陷。3.交換層私有的數(shù)據(jù)頁在開始時，要么是寫時復(fù)制頁，要么是按需清零頁。當(dāng)

15、發(fā)生修改，并因此進(jìn)行賦值時，頁背后的對象(通常是一個文件)將不能再被作為VM系統(tǒng)需要重用一頁時頁的可靠副本。這時將用到交換區(qū)(swap)。交換區(qū)被分配作為內(nèi)存的一個輔助存儲區(qū)，它不能被用作其他目的。FreeBSD只有在真的需要時才分配交換管理結(jié)構(gòu)。但是，交換管理結(jié)構(gòu)在歷史上是存在問題的。在FreeBSD 3.X中，交換管理結(jié)構(gòu)預(yù)先分配一個數(shù)組，它包括了需要較緩存儲的整個對象-哪怕那個對象中只有很少的頁是基于交換區(qū)的。當(dāng)映射大的對象，或者一個有大的運(yùn)行尺寸(RSS)的進(jìn)程fork時，這會造成內(nèi)核內(nèi)存碎片問題。此外，為了保持對交換空間的追蹤，內(nèi)核內(nèi)存中將保存一個空洞表，這也趨于嚴(yán)重地產(chǎn)生碎片。由于

16、洞表是一個線性表，交換分配和釋放性能不是最優(yōu)的，每頁O(n)。此外，它也要求在交換區(qū)釋放進(jìn)程時進(jìn)行內(nèi)核內(nèi)存分配，而這將造成內(nèi)存不足時的死鎖。由于采用的交錯算法，由空洞產(chǎn)生的問題變得更為嚴(yán)重。同時，在非連續(xù)地分配內(nèi)存時，交換區(qū)塊映射很快就會變得充滿碎片。內(nèi)核內(nèi)存也必須在發(fā)生換出(s)時很快地分配交換區(qū)管理結(jié)構(gòu)。顯然，這些都有很大的改善余地。在FreeBSD 4.X中，我整個地重寫了交換子系統(tǒng)。通過這次重寫，交換區(qū)結(jié)構(gòu)被通過一個散列表(hash table)而不再通過線性數(shù)組來分配，這帶來了固定的分配尺寸和更好的粒度控制。取代原先使用線性鏈表來追蹤預(yù)留交換空間的是，現(xiàn)在的系統(tǒng)使用一個包含空閑區(qū)域線

17、索的采用基數(shù)樹結(jié)構(gòu)(radix tree structure)組織的塊的位映射表(bitmap)。這有效地使交換區(qū)的分配和釋放成為一個O(1)的操作。整個基數(shù)樹位映射表也是預(yù)先分配的，這防止了在內(nèi)存不足時的交換操作中分配新的內(nèi)核內(nèi)存。畢竟，在內(nèi)存不足時系統(tǒng)將趨于使用交換區(qū)，而我們應(yīng)該避免在此時分配內(nèi)存，以預(yù)防出現(xiàn)死鎖。最后，為了減少碎片，基數(shù)樹適合于一次分配大的連續(xù)快，而跳過小的碎片組。我還沒有完成增加分配線索指針的最后步驟，它能夠讓以后的分配更容易得到連續(xù)的空間，或至少保證引用的局部性，但我保證類似的修改能夠完成。4.何時釋放一頁由于VM系統(tǒng)使用所有可用的內(nèi)存作為磁盤緩存，因此通常很少有真正

18、空閑的頁。VM系統(tǒng)的正常運(yùn)轉(zhuǎn)依賴于正確地選擇沒有在用的頁，并為新的分配重用它們的能力。選擇好的頁面淘汰算法可能是VM系統(tǒng)中唯一的一項最重要的功能，因為如果它的選擇不好，那么VM系統(tǒng)可能不得不再次完成從磁盤獲得頁的工作，這將嚴(yán)重降低系統(tǒng)性能。我們究竟希望在關(guān)鍵路徑中承受多少開銷，以防止釋放掉不該釋放的頁?每一次錯誤的選擇都將耗去成百上千的CPU周期，以及相關(guān)進(jìn)程的可以被察覺的停頓，因此我們希望容忍大量的開銷，以確保選擇了正確的那頁。這是為什么在內(nèi)存資源承受重壓時，為什么FreeBSD總趨向于提供更好的性能的主要原因。頁面淘汰算法建立在過去內(nèi)存頁的使用歷史上。為了獲得這一歷史資料，系統(tǒng)得益于絕大多

19、數(shù)硬件頁表中提供的頁在用位。在任何情況下，頁在用位總是在VM系統(tǒng)在該位置位后的某一時刻被復(fù)位。它表示頁仍然被活躍地使用著。如果VM系統(tǒng)遍歷頁表時頁的這個位處于復(fù)位狀態(tài)，則標(biāo)識它沒有被活躍地使用。通過周期性地檢測這個位，使用歷史(以計數(shù)器為形式)就能夠被獲得。當(dāng)VM系統(tǒng)隨后需要釋放一些頁時，這個歷史將成為檢測最佳候選頁的基石。如果系統(tǒng)中沒有頁在用位怎么辦?對于那些不提供這一特性的平臺來說，系統(tǒng)實際上模擬一個頁在用位。它解除映射或保護(hù)頁，從而在頁再次被訪問時強(qiáng)制產(chǎn)生一個中斷。當(dāng)中斷發(fā)生時，系統(tǒng)簡單地標(biāo)記頁在用，并解除保護(hù)從而讓頁可以被使用。由于如此僅僅檢測頁是否在用的代價過于昂貴，因此這一技術(shù)通常

20、用來查找進(jìn)程需要某一頁時必須交換的頁。FreeBSD使用一系列頁隊列，以更好地校正對頁的選擇，同時確認(rèn)何時改過的頁應(yīng)被換出到備用存儲器中。由于頁表在FreeBSD中是動態(tài)的實體，因此，從使用頁的進(jìn)程中解除一頁的映射沒有任何代價。當(dāng)候選頁被通過頁使用計數(shù)器選出時，這部分的工作也就完成了。系統(tǒng)必須區(qū)分那些干凈的(clean)頁和改過的(dirty)頁，干凈的頁可以在任何時候被釋放，而改過的頁則必須首先寫盤。當(dāng)候選頁被發(fā)現(xiàn)時，如果它被改過，則放進(jìn)非活躍(inactive)隊列；如果它是干凈的，則直接放入緩存隊列。一個基于改過和干凈頁比例的獨(dú)立的算法決定何時非活躍隊列中改過的頁必須被寫盤。一旦這些都完

21、成了，已經(jīng)寫盤的頁就從非活躍隊列挪到緩存隊列。此時，在緩存隊列中的頁仍然可以通過一次VM中斷以相對較低的代價重新激活。不過，在緩存隊列中的頁都被認(rèn)為是可以馬上釋放的，并將按照LRU(最近最少用到)的規(guī)則在系統(tǒng)需要分配新的內(nèi)存時被替換掉。注意，F(xiàn)reeBSD VM系統(tǒng)嘗試將干凈和改過的頁分開這一點(diǎn)非常重要，原因非常簡單-避免進(jìn)行不需要的寫入操作(這將消耗I/O帶寬)，當(dāng)內(nèi)存子系統(tǒng)不承受重壓時，它也不在不同的頁隊列之間無理由地移動頁。這是為什么你在一些系統(tǒng)上使用systat-vm命令時看到很低的緩存隊列計數(shù)和很高的活動隊列計數(shù)的原因。當(dāng)VM系統(tǒng)承受重壓時，它將進(jìn)行努力以維持不同的頁面隊列在一個被證

22、明是最有效的級別運(yùn)作。一個存留了幾年的神話是，Linux在防止換出方面比FreeBSD更好，然而這是錯誤的。實際在FreeBSD中發(fā)生的事情是，它主動地?fù)Q出不用的頁，以給磁盤緩存提供更多的空間，而Linux則將不用的頁保留在主存中，而給緩存和進(jìn)程頁剩下更少的內(nèi)存。當(dāng)然，我并不保證今天的Linux系統(tǒng)依然如此。5.中斷前和清零優(yōu)化發(fā)生一次VM中斷的代價并不一定昂貴，如果相關(guān)的頁已經(jīng)在主存中，那么它可以被簡單地映射到進(jìn)程中。然而，如果把所有的工作一次完成就不一樣了。比較常見的例子是類似ls(1)或ps(1)這樣的程序一遍又一遍地執(zhí)行。如果程序的二進(jìn)制映像被映射到內(nèi)存中，而沒有映射進(jìn)頁表，那么所有被

23、程序訪問的頁將在每次運(yùn)行程序時引發(fā)缺頁中斷。當(dāng)請求的頁已經(jīng)在VM緩存中存在時，這顯然不是必需的，因此FreeBSD將嘗試從VM緩存中先行組裝進(jìn)程的頁表。目前FreeBSD還沒有做到的是在exec時進(jìn)行寫時預(yù)復(fù)制(pre-copy-on-write)。例如，當(dāng)你在執(zhí)行vmstat 1時運(yùn)行l(wèi)s(1)程序，就會注意到它總是引發(fā)特定數(shù)量的缺頁中斷，即使一次又一次地執(zhí)行。此外還有填零中斷，而不是程序代碼中斷(它預(yù)先產(chǎn)生中斷)。將在exec或fork時復(fù)制的頁的情況可能更容易研究。缺頁中斷中的很大一部分是填零中斷。通常你可以通過vmstat-s的輸出觀察到這一點(diǎn)。在進(jìn)程訪問BSS區(qū)域時會發(fā)生這種中斷。B

24、SS區(qū)域預(yù)期被填充零，但VM系統(tǒng)在進(jìn)程實際訪問它之前并不為它分配內(nèi)存。當(dāng)發(fā)生中斷時，VM系統(tǒng)不僅需要分配新的頁，而且它還必須被清零。為了優(yōu)化清零操作，VM系統(tǒng)有能力對頁進(jìn)行預(yù)清零，并對它們進(jìn)行標(biāo)記，進(jìn)而在發(fā)生清零中斷時直接請求這些頁。預(yù)清零在CPU空閑的任何時候，只要系統(tǒng)中的預(yù)清零頁面不足時，通過減少內(nèi)存緩存來完成。這是VM系統(tǒng)中優(yōu)化關(guān)鍵路徑時增加復(fù)雜度的很好的例子。6.頁表的優(yōu)化頁表優(yōu)化是FreeBSD VM設(shè)計中最有爭議的部分，它們看來在大量使用mmap()時過于緊張。我認(rèn)為這實際上是絕大多數(shù)BSD系統(tǒng)的一個特性，盡管我并不十分清楚它是何時被引入的。有兩項主要的優(yōu)化。首先是硬件頁表不包含回

25、歸狀態(tài)，但可以被在任何時候丟棄，而只付出很小的管理代價。然后是，系統(tǒng)中每一個活動頁表項有一個控制的pv_entry結(jié)構(gòu)附著于vm_page結(jié)構(gòu)上。FreeBSD能夠簡單地在這些映射上迭代，而在Linux中，則必須檢查所有的頁表，以檢查某個制定的映射是否存在；在某些情況下，Linux的算法的開銷是O(n2)級的。這是因為FreeBSD在內(nèi)存承受重壓時，趨向于更好地選擇被重用或換出的頁，這讓它在高負(fù)荷下有更好的性能表現(xiàn)。然而，F(xiàn)reeBSD需要進(jìn)行內(nèi)核調(diào)節(jié)以適應(yīng)類似新聞組(news)系統(tǒng)中所需要的大的共享地址空間，因為這類系統(tǒng)可能會耗盡pv_entry結(jié)構(gòu)。在這一領(lǐng)域，Linux和FreeBSD都

26、需要進(jìn)行更多的工作。FreeBSD試圖盡可能地挖掘潛在的稀疏活動映射模型(作為例子，并非所有進(jìn)程都需要映射同一共享庫中的所有頁)，而Linux則試圖最簡化它的算法。FreeBSD盡管浪費(fèi)了一點(diǎn)額外的內(nèi)存，但通常具有性能上的優(yōu)勢。不過，F(xiàn)reeBSD當(dāng)大量文件成捆地被許多進(jìn)程映射時則會出現(xiàn)性能衰退。另一方面，Linux，在許多進(jìn)程稀疏地映射同一個共享庫時查找將被淘汰的頁時也經(jīng)常發(fā)生性能衰退現(xiàn)象。7.頁的著色(Page Coloring)在文章的結(jié)尾，我們來討論一下關(guān)于頁面著色問題的優(yōu)化。頁面著色是一種用來確保虛擬內(nèi)存中連續(xù)頁的訪問能夠最好地利用處理器緩存的性能優(yōu)化技術(shù)。在過去(大約十幾年前)，處

27、理器緩存曾嘗試映射虛擬內(nèi)存而非物理內(nèi)存。這導(dǎo)致了大量問題，包括在特定情況下，每次上下文切換時都必須清空緩存，以及在緩存中的數(shù)據(jù)變形問題?，F(xiàn)代的處理器采用映射物理內(nèi)存的方法來解決這些問題。這意味著同一進(jìn)程地址空間中的兩個挨著的頁可能并不對應(yīng)著緩存中的兩個挨著的頁。實際上，如果你不是小心地處理這類頁的話，那么同一頁會很快耗盡處理器的緩存，這將導(dǎo)致應(yīng)該被緩存地數(shù)據(jù)被過早地丟棄，從而降低CPU性能。即使在多路級相聯(lián)緩存中也存在這種現(xiàn)象(盡管它的作用有所減輕)。FreeBSD的內(nèi)存分配代碼實現(xiàn)了頁作色優(yōu)化，這意味著內(nèi)存分配代碼將試圖尋找那些從緩存看來鄰接的空閑頁。例如，如果物理內(nèi)存中的頁16被指定為進(jìn)程

28、虛擬內(nèi)存的頁0，而緩存中能夠保存4頁，則頁著色代碼將不會把物理頁20分配給進(jìn)程虛存頁1，取而代之的是，它將把頁21分配給虛存頁1。頁著色代碼嘗試避免將物理頁20指定給虛存頁1的原因是，映射到與物理頁16相同的緩存中將導(dǎo)致緩存性能衰退?？梢韵胂?，這部分代碼顯著地提高了VM內(nèi)存分配子系統(tǒng)的復(fù)雜度，但其結(jié)果是非常合算的。頁面著色使得VM內(nèi)存在緩存性能上與物理內(nèi)存相差無幾。8.結(jié)論在現(xiàn)代操作系統(tǒng)中，虛擬內(nèi)存部分必須有效地解決相當(dāng)多的問題，并適應(yīng)眾多的使用模式。BSD歷史上采用的模型和算法手段使得我們在研究和理解現(xiàn)在的實現(xiàn)的同時，能夠相對干凈地替換掉大量的代碼。在過去幾年中，F(xiàn)reeBSD VM系統(tǒng)中有

29、相當(dāng)多的改進(jìn)，目前改進(jìn)工作仍在進(jìn)行中。9.由Allen Briggs整理的附加問題與解答單元索引暫時略去1)9.1.在你的文章所里舉的FreeBSD 3.X交換區(qū)排列問題中的交錯算法是什么?FreeBSD使用固定的交換區(qū)交錯因子，其默認(rèn)值為4。這意味著FreeBSD將保留四個交換區(qū)域，即使你只用到了1，2或3個。由于交換區(qū)在線性地址空間中交錯出現(xiàn)4個交換區(qū)域，因此當(dāng)你并不是真的擁有4個交換區(qū)的時候?qū)a(chǎn)生碎片。例如，如果你有兩個交換區(qū)A,B，F(xiàn)reeBSD將以下面的方式表達(dá)交換區(qū)中的16個頁的塊：A BC DA BC DA BC DA BC DFreeBSD 3.X使用一種空閑區(qū)域順序表的方法來

30、記錄空閑的交換區(qū)。主要的想法是空閑的現(xiàn)行空間可以被一個單獨(dú)的表節(jié)點(diǎn)(kern/subr_rlist.c)表示。然而，由于碎片，順序表中的碎片的產(chǎn)生愈演愈烈。在上述例子中，完全為用地交換區(qū)中，A和B將表示為空閑，而C與D則被標(biāo)記為已經(jīng)分配。每一個A-B序列需要一個表項來記錄，因為C和D是空洞，因此表節(jié)點(diǎn)不能和下一個A-B序列合并。為什么交錯地使用交換空間，而不是把一個交換區(qū)用完再用另一個呢?因為這使得分配地址空間中的線性列容易了許多，而且其結(jié)果是自動地交叉使用多個磁盤，而不是在其他地方生硬地實現(xiàn)這一功能。碎片同時造成了其他問題。在3.X中的線性表上，包括許多內(nèi)碎片，分配和釋放交換空間需要O(N)

31、的算法，而不是O(1)的算法。由于同時出現(xiàn)的其他因素(例如大量的交換操作)，可能會付出O(N2)甚至O(N3)級別的開銷，這是非常糟糕的事情。在3.X系統(tǒng)中，也需要在進(jìn)行交換操作以創(chuàng)建新的表象時，也需要分配KVM，這可能導(dǎo)致內(nèi)存不足時的死鎖。在4.X中我們不再使用順序表。取而代之的是一個基數(shù)樹和一組交換塊的位映射表，而不是可延伸的表節(jié)點(diǎn)。預(yù)分配位映射表所需的全部內(nèi)存而不是創(chuàng)建一組鏈表。使用基數(shù)樹代替順序表的結(jié)果是接近O(1)的性能，無論樹上的碎片有多少。9.2.我不明白這段：注意，F(xiàn)reeBSD VM系統(tǒng)嘗試將干凈和改過的頁分開這一點(diǎn)非常重要，原因非常簡單-避免進(jìn)行不需要的寫入操作(這將消耗I

32、/O帶寬)，當(dāng)內(nèi)存子系統(tǒng)不承受重壓時，它也不在不同的頁隊列之間無理由地移動頁。這是為什么你在一些系統(tǒng)上使用systat-vm命令時看到很低的緩存隊列計數(shù)和很高的活動隊列計數(shù)的原因。區(qū)分干凈的和改過(非活動)的頁和在systat-vm中看到的較少的緩存隊列計數(shù)，以及較高的活動隊列計數(shù)之間有什么關(guān)系?systat是否將活動和改過頁一同作為活動隊列計數(shù)?是的，這確實讓人感到困惑。二者之間的關(guān)系是，理想和現(xiàn)實之間的關(guān)系。我們的理想是將頁面分開，但實際上如果我們沒有在內(nèi)存上進(jìn)行處理，我們實際上并不需要那樣做。這意味著，在系統(tǒng)沒有承受重壓時，F(xiàn)reeBSD將不費(fèi)很大的力氣來區(qū)分出改過的(在非活動隊列)和干

33、凈的(在緩存隊列)中的頁。沒有重壓時，它也不嘗試將活動頁去活(活動隊列非活動隊列)，即使它們沒有被用到。9.3.在ls(1)/vmstat 1例子中，難道沒有一些缺頁中斷是數(shù)據(jù)頁導(dǎo)致的嗎(從可執(zhí)行文件到私有頁的寫時復(fù)制)?就是說，我應(yīng)認(rèn)為某些缺頁中斷是填零或程序數(shù)據(jù)造成的?；蛘?，你在暗示FreeBSD確實對程序數(shù)據(jù)作預(yù)先的寫時復(fù)制?寫時復(fù)制中斷在添零或訪問程序數(shù)據(jù)時都可能發(fā)生。這一機(jī)制在兩種情況中是一樣的，因為幾乎可以肯定程序數(shù)據(jù)已經(jīng)在緩存中了。FreeBSD并不預(yù)先復(fù)制程序數(shù)據(jù)或填零，但它確實預(yù)先映射那些已經(jīng)在緩存中的頁。9.4.在頁表優(yōu)化一節(jié)中，是否可以給出關(guān)于pv_entry和vm_pa

34、ge的更多細(xì)節(jié)(或者，vm_page是否和McKusick,Bostic,Karel,Quarterman的4.4,cf.pp.180-181中的vm_pmap一樣)?特別地，哪種操作/反應(yīng)需要掃描映射?Linux在FreeBSD出現(xiàn)性能衰退的情形下做什么?(在大量進(jìn)程之間共享同一個大文件的映射)?vm_page表示一個(object,index#)對。pv_entry表示一個硬件頁表項(pte)。如果你有5個進(jìn)程分享同一個物理頁，其中3個進(jìn)程的頁表實際地映射那一頁，那么這個頁將由1個vm_page結(jié)構(gòu)和3個pv_entry結(jié)構(gòu)表示。pv_entry結(jié)構(gòu)僅僅表示由MMU映射的頁(一個pv_en

35、try表示一個pte)。這意味著我們需要刪除到一個vm_page的所有硬件引用(從而為某些其他，例如換出，清除，修改以及類似的目的重用該頁)?？梢院唵蔚貟呙桕P(guān)聯(lián)到vm_page上的pv_entry的鏈表，并刪除或修改相關(guān)的pte。在Linux中沒有類似的鏈表。為了刪去所有的硬件頁表映射，Linux必須在每一個可能映射了該頁的VM對象上進(jìn)行查找。例如，如果你有50個進(jìn)程映射了同一個共享庫，而像要釋放掉該庫的頁X，那么你需要遍歷50各進(jìn)程的頁表，即使只有10個真的映射了那一頁。因此，Linux實際上犧牲了性能來獲取設(shè)計的簡單。許多在FreeBSD上是O(1)或O(N)的VM算法在Linux上將是O

36、(N)，O(N2)甚至更差。因為pte在對象中表達(dá)特定頁趨于在所有的頁表中偏移量一致，減少同一pte偏移中映射的訪問次數(shù)通常能夠防止過快地耗盡用于它的L1緩存線，這將帶來更好的性能。FreeBSD增加了復(fù)雜性(在pv_entry模式中)，以換取更好的性能(通過把對頁表的訪問限制在那些pte之內(nèi))。然而，F(xiàn)reeBSD存在一個Linux上所沒有的伸縮性難題。因為pv_entry結(jié)構(gòu)的個數(shù)是有限的，因此，再進(jìn)行大量的共享數(shù)據(jù)時，很可能會將它們耗盡。盡管可能仍然有許多物理內(nèi)存，但你可能已經(jīng)把pv_entry結(jié)構(gòu)用光了。這個問題可以輕易地通過提高內(nèi)核配置中的pv_entry數(shù)量來做到，但我們真的很需要更好的方法來解決它。我們來考慮一下頁表和pv_entry格局中的內(nèi)存消耗。Linux使用永久性的頁表，他們不能被釋放，但卻不需要為每一個潛在映射的pte分配pv_entry。FreeBSD使用可丟棄的頁表，但卻為每一個實際映