[資源分享] Linux Kemel - 內存管理

祐祐

內存管理
內存管理子系統是操作系統中最重要的組成部份之一。從早期計算機開始，系統的實際內存總是不能滿足需求，為解決這一矛盾，人們想了許多辦法，其中虛存是最成功的一個。虛存讓各進程共享系統內存空間， 這樣系統就似乎有了更多的內存。虛存不僅使計算機的內存看起來更多，內存管理子系統還提供以下功能：擴大地址空間操作系統擴大了系統的內存空間。虛存能比系統的實際內存大許多倍。內存保護 系統中每個進程都有它自己的虛擬地址空間。這些虛擬地址空間之間彼此分開，以保証應用程序運行時互不影響。另外，虛存機制可以對內存部份區域提供寫保護，以防止代碼和數據被其它惡意的應用程序所篡改。內存映射內存映射被用于將映像和數據文件映射到一個進程的虛擬地址空間中，也就是將文件內容連接到虛地址中。公平分配內存內存管理子系統公平地分配內存給正在運行的各進程。虛存共享盡管虛存允許各進程有各自的 ( 虛擬 ) 地址空間，但有時進程間需要共享內存。例如，若干進程同時運行 Bash 命令。并非在每個進程的虛地址空間中，都有一個Bash的拷貝。在內存中僅有一個運行的Bash拷貝供各進程共享。又如，若干進程可以共享動態函數庫。共享內存也能作為一種進程間的通信機制(IPC)。兩個或兩個以上進程可以通過共享內存來交換數據。

在分析 Linux 實現虛存的方法前，讓我們先來看一個沒有過多細節的抽象模型。當處理器執行一段程序時，它先從內存中讀出一條指令并對它進行解碼。解碼時可能需要在內存中的某一地址存取數據。然后處理器執行這條指令并移向下一條。可見處理器總是不斷地在內存中存取數據或指令。在虛存系統中，所有地址都是虛地址而非物理地址。處理器根據操作系統中的一組表格而把這些虛地址翻譯成相應的物理地址。為使這翻譯的過程更容易，虛存和物理內存被划分成許多適當大小的塊，叫做“頁”(page)。為便于系統管理，這些頁都是一樣大小的。在 Alpha AXP 上的 Linux 系統中，每頁有 8 Kbyte，但在 Intel x86 系統中，每頁有 4 Kbyte。每一頁又被分配了一個各不相同的數字，叫頁號 ( PFN ) 。在本模型中，一個虛地址由兩部份組成﹔偏移量和虛頁號。如果頁的大小是 4Kbytes，那么虛地址的0至11位是偏移量，第12位以上是虛頁號。每次處理器遇到虛地址時，它先取出偏移量和虛頁號。然后，處理器把虛頁號翻譯成物理頁號，再由偏移量得到正確的物理地址，最后存取數據。處理器需要使用頁表來完成這整個過程。

3.1.1 按需裝載頁(Demanding Paging)
虛存比實際內存大很多，所以操作系統一定要小心有效地使用內存。節省內存的一個方法是只裝載被當前執行程序使用的虛頁。例如，有一個用來查詢數據庫的程序。此時，并非所有數據庫中的數據都需被裝載進內存，只需要那些正在被訪問的數據。如果正運行一條數據庫搜索命令，那么就不必載入添加新記錄的代碼。當代碼或數據被訪問時才裝載進內存，這叫作按需裝載頁(demand paging)。當進程試圖存取一個不在內存中的虛地址時，處理器不可能在頁表中找到這一虛頁的記錄。例如，在圖 3.1中， 進程 X 的虛存第 2頁沒有對應的頁表記錄，如果嘗試對這頁進行讀操作，那么處理器不能把虛地址翻譯成物理地址。處理器就會通知操作系統頁錯發生了。如果頁錯(faulting) 對應的虛地址是無效的，這意味著進程試圖存取它不應該訪問的虛地址。這也許是因為應用程序出了某些錯誤， 例如試圖在內存中任意進行寫操作。在這種情況下，操作系統將終止這個錯誤進程，以保護其它進程。如果頁錯(faulting) 對應的虛地址是有效的，只是它所在頁目前不在內存中，操作系統必須將對應的頁從磁盤載入內存。相對來說，磁盤存取會花很多時間，所以進程必須等待相當一會兒直到頁被讀入。這時候，如果有其它進程能運行，操作系統將選擇其中之一。被取的頁將被讀入內存一空頁中，并在進程頁表中加入一條記錄。然后，進程從產生頁錯的機器指令重新啟動。這次處理器能將虛地址翻譯成物理地址了，因此進程能繼續運行下去。 Linux 使用按需裝載頁來讀入可執行進程的映像。一個命令被執行時，包含它的文件被打開，它的內容被印射入進程的虛存。這操作需修改描述這進程內存映像的數據結構 (memory mapping)。然而，只有映像的第一部份被實際載入物理內存，余下部份被留在磁盤上。當映像執行時，它將不斷產生頁錯， Linux 使用進程的內存映像表來決定哪塊映像該被載入內存。

3.1.2 頁交換 (Swapping)
當進程要裝載一虛頁進物理內存時，如果得不到空頁, 操作系統必須從內存中丟棄別的頁，為這頁提供空間。如果從內存中被丟棄的那頁是從映像或數據文件中來的，并且映像和數據文件沒被修改過，那這頁不需再被保存，可以直接丟掉。如果進程再需要那頁，它可以重新被從映像或數據文件中讀入內存。但如果該頁已被修改了，操作系統必須保存這頁的內容以便它以后能再被訪問。這類頁叫作臟 (dirty) 頁，當它們被從內存中移出時，它們被作為特殊的交換文件 (swap file) 保存。相對于處理器和內存的速度，交換文件的存取時間是很長的，所以操作系統必須權衡是否需要把頁寫到磁盤上，還是保留在內存中以備后用。如果交換算法的效率不高，那么thrashing現象就會發生。在這種情況下，頁常常一會兒被寫到磁盤上，一會兒又被讀回來，操作系統忙于文件存取而不能執行真正的工作。例如，圖3.1 中，如果內存第 1頁不斷被訪問，那它就不應該被交換到硬盤上。進程當前正在使用的頁的集合被叫作工作集 (working set)。有效的交換算法將保証所有進程的工作集都在內存中。Linux 使用最近最少使用算法(Least Recently Used) 來公平選擇從內存中被丟棄的頁。這個算法中，當頁被存取時，它的年齡 (aging) 就變化了。頁越多被存取，便越年輕﹔越少被存取就越舊。舊頁通常是被丟棄的好候選。

3.1.3 共享虛存
虛存使得若干進程更容易共享內存。進程所有的內存訪問都要通過頁表，并且各進程有各自獨立的頁表。當多進程共享內存中一頁時，物理頁號就會同時出現在每個進程的頁表中。圖3.1 中顯示兩進程共享物理第4頁。對進程 X 而言，那是虛存的第 4頁，對進程Y而言，那是虛存第 6頁。這說明一個有趣的現象：被共享的物理頁對應的虛存頁號可以各不相同。
3.1.4 物理和虛擬地址模式
把操作系統運行在虛存中是不明智之舉，如果操作系統還要為自己保存頁表，那將是一場惡夢。因此，很多種處理器同時支持虛擬地址模式和物理地址模式。物理地址模式不需要頁表，處理器不必做任何地址翻譯。 Linux 內核被直接連在物理地址空間中運行。Alpha AXP 處理器沒有物理地址模式。相反，它把內存划分成若干區域并且指定其中兩塊為物理地址區。這段核地址空間叫作KSEG，包括所有0xfffffc0000000000以上的地址。在 KSEG執行的 (按定義，核代碼 ) 或在那里存取數據的代碼肯定是在核模式下執行。在 Alpha 上的 Linux 核被連接從0xfffffc0000310000開始執行。
3.1.5 存取控制
頁表記錄中也包含了存取控制信息。處理器使用頁表記錄來把虛地址翻譯成物理地址的同時，它也很容易地使用其中的存取控制信息來檢查進程是否在正確地訪問內存。在很多種情況下，你想要為內存的一段區域設置存取限制。一段內存， 例如包含可執行的代碼, 應為只讀內存﹔操作系統應該不允許進程在它的可執行的代碼上寫數據。相反的，包含數據的頁能被寫，但是當指令試圖執行那段內存時，應該失敗。大多數處理器的執行代碼有兩種模式：核 態和用戶態。你將不想由一個用戶執行核代碼，或者讓核數據結構被不是核態執行的代碼所訪問。存取控制信息被保存在 PTE中，并且不同的處理器，PTE的格式是不同的﹔當在這頁上進行寫操作時報頁錯。FOR (Fault on Read)當在這頁上進行讀操作時報頁錯。ASM(Address Space Match) 地址空間匹配。當操作系統僅僅希望清除翻譯緩沖區中若干記錄時，這一位被使用。KRE 在核模式下運行的代碼能讀這頁。 URE 在用戶模式下運行的代碼能讀這頁。GH 粒度性，指在映射一整塊虛存時，是用一個翻譯緩沖記錄還是多個。KWE 在核模式下運行的代碼能寫這頁。UWE在用戶模式下運行的代碼能寫這頁。頁號在有效的PFE中， 這域包含對應的物理頁號 (page frame number )。對無效的PTEs ，如果這域不是零，它包含了頁在交換文件中的信息。
以下兩位是 Linux 定義并使用的：
_PAGE_DIRTY 如果設置，頁需要被寫到交換文件中。
_PAGE_ACCESSED 由 Linux 標記這頁是否曾被訪問。

3.2 緩存
如果你按照上面理論模型，可以實現一個工作的系統，但不會特別高效。操作系統和處理器的設計者都在努力提高系統性能。除提高處理器和內存的速度外，最好的途徑是把有用的信息和數據保存在緩存中。 Linux 就使用了很多與內存管理有關的緩存：
緩沖區
緩沖區包含塊設備驅動程序 (block device driver) 使用的數據緩沖區。
這些緩沖區有固定的大小 ( 例如 512 個字節 ) ，記錄從一台塊設備讀或寫的信息。一台塊設備只能存取整塊數據。所有的硬盤都是塊設備。緩沖區通過設備標識符和需要的塊號的索引來迅速發現所需數據。塊設備只能通過緩沖區進行存取操作。如果數據在緩沖區中，那么它就不需要再從塊設備中被讀(例如硬盤)，這樣存取得更快。
頁緩存
它被用來加快磁盤上映像和數據的存取。它被用來一次緩存文件的一頁，存取操作通過文件名和偏移量來實現。當頁從磁盤被讀進內存時，他們被緩存在頁緩存中。
交換緩存
只有修改了的頁，即臟(dirty ) 頁，被保存在交換文件中。只要一頁在被寫進交換文件以后，沒有再被修改，下次這頁被換出內存時，可以直接被扔掉。對一個進行許多頁面交換的系統，這將節省許多不必要的并且昂貴的磁盤操作。
硬件緩存
處理器中有一經常用到的硬件緩存：頁表記錄的緩存。通常情況下，處理器并不總是直接讀頁表，而是用頁表緩存保留用到的記錄。這些被叫做 Translation Look-aside Buffer，保存了系統中多個進程頁表的拷貝。當翻譯地址時，處理器先試圖找到一匹配的TLB 記錄。如果它發現了一個，它能直接把虛地址翻譯成物理地址，并且對數據進行存取操作。如果處理器不能發現一匹配的 TLB 記錄，那就必須借助操作系統。它發信號給操作系統，報告有一個 TLB 疏漏。特定的機制將把異常信號送給操作系統的代碼。操作系統為印射的地址產生一個新的 TLB 記錄。當異常被解決后，處理器將嘗試再翻譯那個虛地址。因為現在那個地址在 TLB 中有一個有效的記錄，這次的地址翻譯一定成功。使用緩沖區，硬件緩存等的缺點是Linux 必須花費更多的時間和空間來維護這些緩存，如果緩存發生錯誤，系統將崩潰。

3.3 Linux 頁表
Linux頁表有3層。每一層負責保存下一層頁表所在的頁號。每個域記錄在某一層頁表中的偏移量。把一個虛地址翻譯成物理地址時，處理器拿出每個域的內容把它變成頁表中的偏移量，進而讀出下層頁表的所在頁號。這樣重復 3 次直到找到包含虛地址的物理頁號。虛地址的最后一個域，叫做字節偏移量, 被用來在物理頁內找到所需數據。每個運行 Linux 的平台必須提供翻譯宏(Translation macros) 以便內核可以檢索頁表，完成某種操作。這樣，內核不需要知道各平台上頁表記錄的具體格式和它們是怎么被安排的。這就是為什么 Linux 的 Alpha 處理器和Intel x 86 處理器使用一樣的頁表操作代碼， 而Alpha有3層頁表，Intel x86處理器只有2層頁表。