第三章 存儲管理 存儲管理子系統時操作系統中最重要的組成部分之一。在早期計算時代，由於人們所需要的內存數目遠遠大於物理內存，人們設計出了各種各樣的策略來解決此問題，其中最成功的是虛擬內存技術。它使得系統中為有限物理內存競爭的進程所需內存空間
第三章 存儲管理
存儲管理子系統時操作系統中最重要的組成部分之一。在早期計算時代，由於人們所需要的內存數目遠遠大於物理內存，人們設計出了各種各樣的策略來解決此問題，其中最成功的是虛擬內存技術。它使得系統中為有限物理內存競爭的進程所需內存空間得到滿足。
虛擬內存技術不僅僅可讓我們可以使用更多的內存，它還提供了以下功能：
巨大的尋址空間
操作系統讓系統看上去有比實際內存大得多的內存空間。虛擬內存可以是系統中實際物理空間的許多倍。每個進程運行在其獨立的虛擬地址空間中。這些虛擬空間相互之間都完全隔離開來，所以進程間不會互相影響。同時，硬件虛擬內存機構可以將內存的某些區域設置成不可寫。這樣可以保護代碼與數據不會受惡意程序的干擾。
內存映射
內存映射技術可以將映象文件和數據文件直接映射到進程的地址空間。在內存映射中，文件的內容被直接連接到進程虛擬地址空間上。
公平的物理內存分配
內存管理子系統允許系統中每個運行的進程公平地共享系統中的物理內存。
共享虛擬內存
盡管虛擬內存允許進程有其獨立的虛擬地址空間，但有時也需要在進程之間共享內存。 例如有可能系統中有幾個進程同時運行BASH命令外殼程序。為了避免在每個進程的虛擬內存空間內都存在BASH程序的拷貝，較好的解決辦法是系統物理內存中只存在一份BASH的拷貝並在多個進程間共享。動態庫則是另外一種進程間共享執行代碼的方式。共享內存可用來作為進程間通訊(IPC)的手段，多個進程通過共享內存來交換信息。 Linux支持SYSTEM V的共享內存IPC機制。
3.1 虛擬內存的抽象模型
圖3.1 虛擬地址到物理地址映射的抽象模型
在討論Linux是如何具體實現對虛擬內存的支持前，有必要看一下更簡單的抽象模型。
在處理器執行程序時需要將其從內存中讀出再進行指令解碼。在指令解碼之前它必須向內存中某個位置取出或者存入某個值。然後執行此指令並指向程序中下一條指令。在此過程中處理器必須頻繁訪問內存，要麼取指取數，要麼存儲數據。
虛擬內存系統中的所有地址都是虛擬地址而不是物理地址。通過操作系統所維護的一系列表格由處理器實現由虛擬地址到物理地址的轉換。
為了使轉換更加簡單，虛擬內存與物理內存都以頁面來組織。不同系統中頁面的大小可以相同，也可以不同，這樣將帶來管理的不便。Alpha A
XP處理器上運行的Linux頁面大小為8KB，而Intel X86系統上使用4KB頁面。每個頁面通過一個叫頁面框號的數字來標示(PFN) 。
頁面模式下的虛擬地址由兩部分構成：頁面框號和頁面內偏移值。如果頁面大小為4KB，則虛擬地址的 11：0位表示虛擬地址偏移值，12位以上表示虛擬頁面框號。處理器處理虛擬地址時必須完成地址分離工作。在頁表的幫助下，它將虛擬頁面框號轉換成物理頁面框號，然後訪問物理頁面中相應偏移處。
圖3.1給出了兩個進程X和Y的虛擬地址空間，它們擁有各自的頁表。這些頁表將各個進程的虛擬頁面映射到內存中的物理頁面。在圖中，進程X的虛擬頁面框號0被映射到了物理頁面框號4。理論上每個頁表入口應包含以下內容：
有效標記，表示此頁表入口是有效的
頁表入口描敘的物理頁面框號
訪問控制信息。用來描敘此頁可以進行哪些操作，是否可寫？是否包含執行代碼?
虛擬頁面框號是為頁表中的偏移。虛擬頁面框號5對應表中的第6個單元（0是第一個）。
為了將虛擬地址轉換為物理地址，處理器首先必須得到虛擬地址頁面框號及頁內偏移。一般將頁面大小設為2的次冪。將圖3.1中的頁面大小設為0x2000字節（十進制為8192）並且在進程Y的虛擬地址空間中某個地址為0x2194，則處理器將其轉換為虛擬頁面框號1及頁內偏移0x194。
處理器使用虛擬頁面框號為索引來訪問處理器頁表，檢索頁表入口。如果在此位置的頁表入口有效，則處理器將從此入口中得到物理頁面框號。如果此入口無效，則意味著處理器存取的是虛擬內存中一個不存在的區域。在這種情況下，處理器是不能進行地址轉換的，它必須將控制傳遞給操作系統來完成這個工作。
某個進程試圖訪問處理器無法進行有效地址轉換的虛擬地址時，處理器如何將控制傳遞到操作系統依賴於具體的處理器。通常的做法是：處理器引發一個頁面失效錯而陷入操作系統核心，這樣操作系統將得到有關無效虛擬地址的信息以及發生頁面錯誤的原因。
再以圖3.1為例，進程Y的虛擬頁面框號1被映射到系統物理頁面框號4，則再物理內存中的起始位置為 0x8000(4 * 0x2000)。加上0x194字節偏移則得到最終的物理地址0x8194。
通過將虛擬地址映射到物理地址，虛擬內存可以以任何順序映射到系統物理頁面。例如，在圖3.1中，進程X的虛擬頁面框號0被映射到物理頁面框號1而虛擬頁面框號7被映射到物理頁面框號0，雖然後者的虛擬頁面框號要高於前者。這樣虛擬內存技術帶來了有趣的結果：虛擬內存中的頁面無須在物理內存保持特定順序。
3.1.1 請求換頁
在物理內存比虛擬內存小得多的系統中，操作系統必須提高物理內存的使用效率。節省物理內存的一種方法是僅加載那些正在被執行程序使用的虛擬頁面。比如說，某個
數據庫程序可能要對某個數據庫進行查詢操作，此時並不是數據庫的所有內容都要加載到內存中去，而只加載那些要用的部分。如果此數據庫查詢是一個搜索查詢而無須對數據庫進行添加記錄操作，則加載添加記錄的代碼是毫無意義的。這種僅將要訪問的虛擬頁面載入的技術叫請求換頁。
當進程試圖訪問當前不在內存中的虛擬地址時，處理器在頁表中無法找到所引用地址的入口。在圖3.1中，對於虛擬頁面框號2，進程X的頁表中沒有入口，這樣當進程X試圖訪問虛擬頁面框號2內容時，處理器不能將此地址轉換成物理地址。這時處理器通知操作系統有頁面錯誤發生。
如果發生頁面錯的虛擬地址是無效的，則表明進程在試圖訪問一個不存在的虛擬地址。這可能是應用程序出錯而引起的，例如它試圖對內存進行一個隨機的寫操作。此時操作系統將終止此應用的運行以保護系統中其他進程不受此出錯進程的影響。
如果出錯虛擬地址是有效的，但是它指向的頁面當前不在內存中，則操作系統必須將此頁面從磁盤映象中讀入到內存中來。由於訪盤時間較長，進程必須等待一段時間直到頁面被取出來。如果系統中還存在其他進程，操作系統就會在讀取頁面過程中的等待過程中選擇其中之一來運行。讀取回來的頁面將被放在一個空閒的物理頁面框中，同時此進程的頁表中將添加對應此虛擬頁面框號的入口。最後進程將從發生頁面錯誤的地方重新開始運行。此時整個虛擬內存訪問過程告一段落，處理器又可以繼續進行虛擬地址到物理地址轉換，而進程也得以繼續運行。
Linux使用請求換頁將可執行映象加載到進程的虛擬內存中。當命令執行時，可執行的命令文件被打開，同時其內容被映射到進程的虛擬內存。這些操作是通過修改描敘進程內存映象的數據結構來完成的，此過程稱為內存映射。然而只有映象的起始部分被調入物理內存，其余部分仍然留在磁盤上。當映象執行時，它會產生頁面錯誤，這樣Linux將決定將磁盤上哪些部分調入內存繼續執行。
3.1.2 交換
如果進程需要把一個虛擬頁面調入物理內存而正好系統中沒有空閒的物理頁面，操作系統必須丟棄位於物理內存中的某些頁面來為之騰出空間。
如果那些從物理內存中丟棄出來的頁面來自於磁盤上的可執行文件或者數據文件，並且沒有修改過則不需要保存那些頁面。當進程再次需要此頁面時，直接從可執行文件或者數據文件中讀出。
但是如果頁面被修改過，則操作系統必須保留頁面的內容以備再次訪問。這種頁面被稱為dirty頁面， 當從內存中移出來時，它們必須保存在叫做交換文件的特殊文件中。相對於處理器和物理內存的速度，訪問交換文件的速度是非常緩慢的，操作系統必須在將這些dirty頁面寫入磁盤和將其繼續保留在內存中做出選擇。
選擇丟棄頁面的算法經常需要判斷哪些頁面要丟棄或者交換，如果交換算法效率很低，則會發生"顛簸"現象。在這種情況下，頁面不斷的被寫入磁盤又從磁盤中讀回來，這樣一來操作系統就無法進行其他任何工作。以圖3.1為例，如果物理頁面框號1被頻繁使用，則頁面丟棄算法將其作為交換到硬盤的侯選者是不恰當的。一個進程當前經常使用的頁面集合叫做工作集。高效的交換策略能夠確保所有進程的工作集保存在物理內存中。
Linux使用最近最少使用（
LRU）頁面衰老算法來公平地選擇將要從系統中拋棄的頁面。這種策略為系統中的每個頁面設置一個年齡，它隨頁面訪問次數而變化。頁面被訪問的次數越多則頁面年齡越年輕；相反則越衰老。年齡較老的頁面是待交換頁面的最佳侯選者。
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 訪問控制
頁表入口包含了訪問控制信息。由於處理器已經將頁表入口作為虛擬地址到物理地址的映射，那麼可以很方便地使用訪問控制信息來判斷處理器是否在以其應有的方式來訪問內存。
諸多因素使得有必要嚴格控制對內存區域的訪問。有些內存，如包含執行代碼的部分，顯然應該是只讀的，操作系統決不能允許進程對此區域的寫操作。相反包含數據的頁面應該是可寫的， 但是去執行這段數據肯定將導致錯誤發生。多數處理器至少有兩種執行方式：核心態與用戶態。任何人都不會允許在用戶態下執行核心代碼或者在用戶態下修改核心數據結構。
圖3.2 Alpha AXP頁表入口
頁表入口中的訪問控制信息是處理器相關的；圖3.2是Alpha AXP處理器的PTE(Page Table Entry)。這些位域的含義如下：
V
有效，如果此位置位，表明此PTE有效
FOE
“執行時失效”，無論合時只要執行包含在此頁面中的指令，處理器都將報告頁面錯誤並將控制傳遞
FOW
“寫時失效”, 除了頁面錯誤發生在對此頁面的寫時，其他與上相同。
FOR
“讀時失效”，除了頁面錯誤發生在對此頁面的讀時，其他與上相同。
ASM
地址空間匹配。被操作系統用於清洗轉換緩沖中的某些入口。
KRE
運行在核心模式下的代碼可以讀此頁面。
URE
運行在用戶模式下的代碼可以讀此頁面。
GH
將整個塊映射到單個而不是多個轉換緩沖時的隱含粒度。
KWE
運行在核心模式下的代碼可以寫此頁面。
UWE
運行在用戶模式下的代碼可以寫此頁面。
page frame number
對於V位置位的PTE，此域包含了對應此PTE的物理頁面框號；對於無效PTE，此域不為0，它包含了頁面在交換文件中位置的信息。
以下兩位由Linux定義並使用。
_PAGE_DIRTY
如果置位，此頁面要被寫入交換文件。
_PAGE_A
CCESSED
Linux用它表示頁面已經被訪問過。
3.2 高速緩沖
如果用上述理論模型來實現一個系統，它可能可以工作，但效率不會高。操作系統設計者和處理器設計者都在努力以提高系統的
性能。除了制造更快的CPU和內存外，最好的辦法是在高速緩沖中維護有用信息和數據以加快某些操作。Linux使用了許多與高速緩沖相關的內存管理策略。
Buffer Cache
這個buffer cache中包含了被塊設備驅動使用的數據緩沖。
這些緩沖的單元的大小一般固定(例如說512字節)並且包含從塊設備讀出或者寫入的信息塊。塊設備是僅能夠以固定大小塊進行讀寫操作的設備。所有的硬盤都是塊設備。
利用設備標志符和所需塊號作索引可以在buffer cache中迅速地找到數據。塊設備只能夠通過buffer cache來存取。如果數據在buffer cache中可以找到則無需從物理塊設備(如硬盤)中讀取，這樣可以加速訪問。
Page Cache
用來加速硬盤上可執行映象文件與數據文件的存取。
它每次緩沖一個頁面的文件內容。頁面從磁盤上讀入內存後緩存在page cache中。
Swap Cache
只有修改過的頁面存儲在交換文件中。
只要這些頁面在寫入到交換文件後沒有被修改，則下次此頁面被交換出內存時，就不必再進行更新寫操作，這些頁面都可以簡單的丟棄。在交換頻繁發生的系統中，Swap Cache可以省下很多不必要且耗時的磁盤操作。
Hardware Caches
一個常見的hardware cache是處理器中的頁表入口cache。處理器不總是直接讀取頁表而是在需要時緩存頁面的轉換。這種cache又叫做轉換旁視緩沖(Translation Look-aside Buffers)，它包含系統中一個或多個處理器的頁表入口的緩沖拷貝。
當發出對虛擬地址的引用時，處理器試圖找到相匹配的TLB入口。如果找到則直接將虛擬地址轉換成物理地址並對數據進行處理。如果沒有找到則向操作系統尋求幫助。處理器將向操作系統發出TLB失配信號，它使用一個特定的系統機制來將此異常通知操作系統。操作系統則為此地址匹配對產生新的TLB入口。當操作系統清除此異常時，處理器將再次進行虛擬地址轉換。由於此時在TLB中已經有相應的入口，這次操作將成功。
使用高速緩存的缺點在於Linux必須消耗更多的時間和空間來維護這些緩存，並且當緩存系統崩潰時系統也將崩潰。
3.3 Linux 頁表
圖3.3 Linux的三級頁表結構
Linux總是假定處理器有三級頁表。每個頁表通過所包含的下級頁表的頁面框號來訪問。圖3.3給出了虛擬地址是如何分割成多個域的，每個域提供了某個指定頁表的偏移。為了將虛擬地址轉換成物理地址，處理器必須得到每個域的值。這個過程將持續三次直到對應於虛擬地址的物理頁面框號被找到。最後再使用虛擬地址中的最後一個域，得到了頁面中數據的地址。
為了實現跨平台運行，Linux提供了一系列轉換宏使得核心可以訪問特定進程的頁表。這樣核心無需知道 頁表入口的結構以及它們的排列方式。
這種策略相當成功，無論在具有三級頁表結構的Alpha AXP還是兩級頁表的Intel X86處理器中，Linux總是使 用相同的頁表操縱代碼。
3.4 頁面分配與回收
對系統中物理頁面的請求十分頻繁。例如當一個可執行映象被調入內存時，操作系統必須為其分配頁面。當映象執行完畢和卸載時這些頁面必須被釋放。物理頁面的另一個用途是存儲頁表這些核心數據結構。虛擬內存子系統中負責頁面分配與回收的數據結構和機制可能用處最大。
系統中所有的物理頁面用包含mem_map_t結構的鏈表mem_map來描敘，這些結構在系統啟動時初始化。每個 mem_map_t描敘了一個物理頁面。其中與內存管理相關的重要域如下：
count
記錄使用此頁面的用戶個數。當這個頁面在多個進程之間共享時，它的值大於1。
age
此域描敘頁面的年齡，用於選擇將適當的頁面拋棄或者置換出內存時。
map_nr
記錄本mem_map_t描敘的物理頁面框號。
頁面分配代碼使用free_area數組來尋找和釋放頁面，此機制負責整個緩沖管理。另外此代碼與處理器使用的頁面大小和物理分頁機制無關。
free_area中的每個元素都包含頁面塊的信息。數組中第一個元素描敘1個頁面，第二個表示2個頁面大小的塊而接下來表示4個頁面大小的塊，總之都是2的次冪倍大小。list域表示一個隊列頭，它包含指向mem_map數組中page數據結構的指針。所有的空閒頁面都在此隊列中。map域是指向某個特定頁面尺寸的頁面組分配情況位圖的指針。當頁面的第N塊空閒時，位圖的第N位被置位。
圖free-area-figure畫出了free_area結構。第一個元素有個自由頁面（頁面框號0），第二個元素有4個頁面大小的2個自由塊，前一個從頁面框號4開始而後一個從頁面框號56開始。
3.4.1 頁面分配
Linux使用Buddy算法來有效的分配與回收頁面塊。頁面分配代碼每次分配包含一個或者多個物理頁面的內存塊。頁面以2的次冪的內存塊來分配。這意味著它可以分配1個、2個和4個頁面的塊。只要系統中有足夠的空閒頁面來滿足這個要求(nr_free_pages > min_free_page)，內存分配代碼將在free_area中尋找一個與請求大小相同的空閒塊。free_area中的每個元素保存著一個反映這樣大小的已分配與空閒頁面 的位圖。例如，free_area數組中第二個元素指向一個反映大小為四個頁面的內存塊分配情況的內存映象。
分配算法首先搜尋滿足請求大小的頁面。它從free_area數據結構的list域著手沿鏈來搜索空閒頁面。如果沒有這樣請求大小的空閒頁面，則它搜索兩倍於請求大小的內存塊。這個過程一直將持續到free_area 被搜索完或找到滿足要求的內存塊為止。如果找到的頁面塊大於請求的塊則對其進行分割以使其大小與請求塊匹配。由於塊大小都是2的次冪所以分割過程十分簡單。空閒塊被連進相應的隊列而這個頁面塊被分配給調用者。
圖3.4 free_area數據結構
在圖3.4中，當系統中有大小為兩個頁面塊的請求發出時，第一個4頁面大小的內存塊（從頁面框號4開始）將分成兩個2頁面大小的塊。前一個，從頁面框號4開始的，將分配出去返回給請求者，而後一個，從頁面框號6開始，將被添加到free_area數組中表示兩個頁面大小的空閒塊的元素1中。
3.4.2 頁面回收
將大的頁面塊打碎進行分配將增加系統中零碎空閒頁面塊的數目。頁面回收代碼在適當時機下要將這些頁面結合起來形成單一大頁面塊。事實上頁面塊大小決定了頁面重新組合的難易程度。
當頁面塊被釋放時，代碼將檢查是否有相同大小的相鄰或者buddy內存塊存在。如果有，則將它們結合起來形成一個大小為原來兩倍的新空閒塊。每次結合完之後，代碼還要檢查是否可以繼續合並成更大的頁面。最佳情況是系統的空閒頁面塊將和允許分配的最大內存一樣大。
在圖3.4中，如果釋放頁面框號1，它將和空閒頁面框號0結合作為大小為2個頁面的空閒塊排入free_area的第一個元素中。
3.5 內存映射
映象執行時，可執行映象的內容將被調入進程虛擬地址空間中。可執行映象使用的共享庫同樣如此。然而可執行文件實際上並沒有調入物理內存，而是僅僅連接到進程的虛擬內存。當程序的其他部分運行時引用到這部分時才把它們從磁盤上調入內存。將映象連接到進程虛擬地址空間的過程稱為內存映射。
圖3.5 虛擬內存區域
每個進程的虛擬內存用一個mm_struct來表示。它包含當前執行的映象（如BASH）以及指向vm_area_struct 的大量指針。每個vm_area_struct數據結構描敘了虛擬內存的起始與結束位置，進程對此內存區域的存取權限以及一組內存操作函數。這些函數都是Linux在操縱虛擬內存區域時必須用到的子程序。其中一個負責處理進程試圖訪問不在當前物理內存中的虛擬內存(通過頁面失效)的情況。此函數叫nopage。它用在Linux試圖將可執行映象的頁面調入內存時。
可執行映象映射到進程虛擬地址時將產生一組相應的vm_area_struct數據結構。每個vm_area_struct數據結構表示可執行映象的一部分：可執行代碼、初始化數據(變量)、未初始化數據等等。Linux支持許多標准的虛擬內存操作函數，創建vm_area_struct數據結構時有一組相應的虛擬內存操作函數與之對應。
3.6 請求換頁
當可執行映象到進程虛擬地址空間的映射完成後，它就可以開始運行了。由於只有很少部分的映象調入內存，所以很快就會發生對不在物理內存中的虛擬內存區域的訪問。當進程訪問無有效頁表入口的虛擬地址時，處理器將向Linux報告一個頁面錯誤。
頁面錯誤帶有失效發生的虛擬地址及引發失效的訪存方式。Linux必須找到表示此區域的vm_area_struct結構。對vm_area_struct數據結構的搜尋速度決定了處理頁面錯誤的效率，而所有vm_area_struct結構是通過一種AVL(Adelson-Velskii and Landis) 樹結構連在一起的。如果無法找到vm_area_struct與此失效虛擬地址的對應關系，則系統認為此進程訪問了非法虛擬地址。這時Linux將向進程發送SIGSEGV信號，如果進程沒有此信號的處理過程則終止運行。
如果找到此對應關系，Linux接下來檢查引起該頁面錯誤的訪存類型。如果進程以非法方式訪問內存，比如對不可寫區域進行寫操作，系統將產生內存錯誤的信號。
如果Linux認為頁面出錯是合法的，那麼它需要對這種情況進行處理。
首先Linux必須區分位於交換文件中的頁面和那些位於磁盤上的可執行映象。Alpha AXP的頁表中有可能存在有效位沒有設置但是在PFN域中有非0值的頁表入口。在這種情況下，PFN域指示的是此頁面在交換文件中的位置。如何處理交換文件中的頁面將在下章討論。
不是所有的vm_area_struct數據結構都有一組虛擬內存操作函數，它們有的甚至沒有nopage函數。這是因為 Linux通過分配新的物理頁面並為其創建有效的頁表入口來修正這次訪問。如果這個內存區域存在nopage操作函數，Linux將調用它。
一般Linux nopage函數被用來處理內存映射可執行映象，同時它使用頁面cache將請求的頁面調入物理內存中去。
當請求的頁面調入物理內存時，處理器頁表也必須更新。更新這些入口必須進行相關硬件操作，特別是處理器使用TLB時。這樣當頁面失效被處理完畢後，進程將從發生失效虛擬內存訪問的位置重新開始運行。
3.7 Linux頁面cache
圖3.6 Linux頁面Cache
Linux使用頁面cache的目的是加快對磁盤上文件的訪問。內存映射文件以每次一頁的方式讀出並將這些頁面存儲在頁面cache中。圖3.6表明頁面cache由page_hash_table，指向mem_map_t數據結構的指針數組組成。
Linux中的每個文件通過一個VFS inode（在文件系統一章中講敘）數據結構來標識並且每個VFS inode都是唯一的，它可以並僅可以描敘一個文件。頁表的索引從文件的VFS inode和文件的偏移中派生出來。
從一個內存映射文件中讀出頁面，例如產生換頁請求時要將頁面讀回內存中，系統嘗試從頁面cache來讀出。如果頁面在cache中，則返回頁面失效處理過程一個指向mem_map_t數據結構；否則此頁面將從包含映象的文件系統中讀入內存並為之分配物理頁面。
在映象的讀入與執行過程中，頁面cache不斷增長。當不再需要某個頁面時，即不再被任何進程使用時，它將被從頁面cache中刪除。
3.8 換出與丟棄頁面
當系統中物理內存減少時，Linux內存管理子系統必須釋放物理頁面。這個任務由核心交換後台進程(kswapd )來完成。
核心交換後台進程是一種特殊的核心線程。它是沒有虛擬內存的進程，在物理地址空間上以核心態運行。核心交換後台進程的名字容易使人誤解，其實它完成的工作比僅僅將頁面交換到系統的交換文件中要多得多。其目標是保證系統中有足夠的空閒頁面來維持內存管理系統運行效率。
此進程由核心的init進程在系統啟動時運行，被核心交換定時器周期性的調用。
當定時器到時後，交換後台進程將檢查系統中的空閒頁面數是否太少。它使用兩個變量：free_pages_high 和free_page_low來判斷是否該釋放一些頁面。只要系統中的空閒頁面數大於free_pages_high，核心交換後台進程不做任何工作；它將睡眠到下一次定時器到時。在檢查中，核心交換後台進程將當前被寫到交換文件中的頁面數也計算在內，它使用nr_async_pages來記錄這個數值；當有頁面被排入准備寫到交換文件隊列中時，它將遞增一次，同時當寫入操作完成後遞減一次。如果系統中的空閒頁面數在free_pages_high甚至 free_pages_low以下時，核心交換後台進程將通過三個途徑來減少系統中使用的物理頁面的個數：
減少緩沖與頁面cache的大小，
將系統V類型的內存頁面交換出去，
換出或者丟棄頁面。
如果系統中空閒頁面數低於free_pages_low，核心交換後台進程將在下次運行之前釋放6個頁面。否則它只釋放3個。以上三種方法將依次使用直到系統釋放出足夠的空閒頁面。當核心交換後台進程試圖釋放物理頁面時它將記錄使用的最後一種方法。下一次它會首先運行上次最後成功的算法。
當釋放出足夠頁面後，核心交換後台進程將再次睡眠到下次定時器到時。如果導致核心交換後台進程釋放頁面的原因是系統中的空閒頁面數小於free_pages_low，則它只睡眠平時的一半時間。一旦空閒頁面數大於 free_pages_low則核心交換進程的睡眠時間又會延長。
3.8.1 減少Page Cache和Buffer Cache的大小
Page Cache和Buffer cache中的頁面將被優先考慮釋放到free_area數組中。Page Cache中包含的是內存映射文件的頁面，其中有些可能是不必要的，它們浪費了系統的內存。而Buffer Cache中包含的是從物理設備中讀寫的緩沖數據，有些可能也是不必要的。當系統中物理頁面開始耗盡時，從這些cache中丟棄頁面比較簡單（它不需要象從內存中交換一樣，無須對物理設備進行寫操作）。除了會使對物理設備及內存映射文件的訪問速度降低外，頁面丟棄策略沒有太多的副作用。如果策略得當，則所有進程的損失相同。
每次核心交換後台進程都會嘗試去壓縮這些cache。
它首先檢查mem_map頁面數組中的頁面塊看是否有可以從物理內存中丟棄出去的。當系統中的空閒頁面數降低 到一個危險水平時，核心後台交換進程頻繁進行交換，則檢查的頁面塊一般比較大。檢查的方式為輪轉，每次試圖壓縮內存映象時，核心後台交換進程總是檢查不同的頁面塊。這是眾所周知的clock算法，每次在整個mem_map頁面數組中對頁面進行檢查。
核心後台交換進程將檢查每個頁面看是否已經被page cache或者buffer cache緩沖。讀者可能已經注意到共享頁面不在被考慮丟棄的頁面之列，這種頁面不會同時出現在這兩種cache中。如果頁面不在這兩者中任何一種之中時，它將檢查mem_map頁面數組中的下一個頁面。
緩存在buffer cache(或者頁面中的緩沖被緩存)中的頁面可以使緩沖分配和回收更加有效。內存壓縮代碼將 力圖釋放在受檢頁面中包含的緩沖區。
如果頁面中包含的所有緩沖區都被釋放，這個頁面也將被釋放。如果受檢頁面在Linux的page cache中，則它會從page cache中刪除並釋放。
如果釋放出來了足夠的頁面，核心交換後台進程將等待到下一次被喚醒。這些被釋放的頁面都不是任何進程虛擬內存的一部分，這樣無須更新頁表。如果沒有足夠的緩沖頁面丟棄則交換進程將試圖將一些共享頁面交換出去。
3.8.2 換出系統V內存頁面
系統V共享內存是一種用來在進程之間通過共享虛擬內存來實現進程通訊的機制。進程是如何共享內存將在IPC 一章中詳細討論。現在只需要說明系統V共享內存的任何區域都可以用一個shmid_ds數據結構來表示就足夠了。 此結構包含一個指向vm_area的鏈表指針，vm_area是為每個共享此虛擬內存區域設計的結構。它們之間通過 vm_next_shared和vm_prev_shared指針來連接。每個shmid_ds數據結構包含一個頁表入口，每個入口描敘物理頁面與共享虛擬頁面之間的映射關系。
核心交換後台進程同樣使用clock算法來將系統V共享內存頁面交換出去。
每次運行時，它要記得哪個共享虛擬內存區域的哪個頁面是最後一個被交換出去的。兩個索引可以協助它完成這項工作，其一是一組shmid_ds數據結構的索引，另一個是系統V共享內存區域的頁表入口鏈表的索引。 這能夠保證對系統V共享內存區域作出公平的選擇。
由於對於給定的系統V共享虛擬內存的物理頁面框號被保存在所有共享此虛擬內存區域進程的頁表中，核心 交換後台進程必須同時修改所有的頁表以表示頁面不再在內存而在交換文件中。對於每個要交換出去的共享 頁面，核心交換後台進程可以在每個共享進程的頁表中的頁表入口中找到它們(通過vm_area_struct數據結 構)。如果對應此系統V共享內存的頁面的進程頁表入口是有效的，它可以將其轉變成無效，這樣換出頁表入口和共享頁面的用戶數將減一。換出系統V共享頁表入口的格式中包含一個對應於一組shmid_ds數據結構的索引以及一個對系統V共享內存區域的頁表入口索引。
如果所有共享進程的頁表都被修改後此頁面的記數為0則共享頁面可以被寫到交換文件中。同樣指向此系統V共享內存區域的shmid_ds數據結構鏈表中的頁表入口也被換出頁表入口代替。換出頁表入口雖然無效但是它包含一組打開的交換文件的索引，同時還能找到換出頁面在文件中的偏移。當頁面重新被帶入物理內存時，這些信息十分有用。
3.8.3 換出和丟棄頁面
交換後台進程依次檢查系統中的每個進程以確認誰最適合交換出去。
比較好的候選者是那些可以被交換出去（有些是不可被交換出去的）並且只有一個或者幾個頁面在內存中的進程。只有那些包含的數據無法檢索的頁面才會從物理內存中交換到系統交換文件中去。
可執行映象的許多內容都可以從映象文件中讀出並且可以很容易重讀出來。例如，映象中的可執行指令不能被映象本身修改，所以決不會寫到交換文件中去。這些頁面直接丟棄就可以。當進程再次引用它們時，只需要從可執行映象文件中讀入內存即可。
一旦確定了將要被交換出去的進程，交換後台進程將搜索其整個虛擬內存區域以找到那些沒有共享或者加鎖的區域。
Linux並不會將選中的進程的整個可交換頁面都交換出去，它只刪除一小部分頁面。
如果內存被加鎖則頁面不能被交換或者丟棄。
Linux交換算法使用頁面衰老算法。每個頁面有一個計數器來告訴核心交換後台進程這個頁面是否值得交換出 去（此計數器包含在mem_map_t結構中）。當頁面沒有使用或者沒有找到時將會衰老；交換後台進程僅僅交換 出那些老頁面。缺省操作是：當頁面被首次分配時，其年齡初始值為3，每次引用其年齡將加3，最大值為20。 每次核心交換後台進程運行它來使頁面衰老-將年齡減1。這個缺省操作可以改變並且由於這個原因它們被存儲在swap_control數據結構中。
如果頁面變老了(age=0)，則交換後台進程將進一步來處理它。dirty頁面可以被交換出去。Linux在PTE中使 用一個硬件相關位來描敘頁面的這個特性（見圖3.2）。然而不是所有的dirty頁面都有必要寫入到交換文件 中去。進程的每個虛擬內存區域可能有其自身的交換操作(由vm_area_struct結構中的vm_ops指針表示)，在 交換時使用的是這些方法。否則，交換後台進程將在交換文件中分配一個頁面並將頁面寫到設備上去。
頁面的頁表入口被標志成無效但是它包含了頁面在在交換文件中位置的信息，包括一個表示頁面在交換文件中位置的偏移值以及使用的是哪個交換文件。但是不管使用的是哪種交換算法，以前那個物理頁面將被標志成空閒並放入free_area中。Clean（或者not dirty）的頁面可以丟棄同時放入free_area以備重新使用。
如果有足夠的可交換進程頁面被交換出去或丟棄，則交換後台進程將再次睡眠。下次它醒來時將考慮系統中 的下一個進程。通過這種方法，交換後台進程一點一點地將每個進程的可交換或可丟棄物理頁面收回知道系 統再次處於平衡狀態。這比將整個進程交換出去要公平得多。
3.9 The Swap Cache
當將頁面交換到交換文件中時，Linux總是避免頁面寫，除非必須這樣做。當頁面已經被交換出內存但是當有進程再次訪問時又要將它重新調入內存。只要頁面在內存中沒有被寫過，則交換文件中的拷貝是有效的。
Linux使用swap cache來跟蹤這些頁面。這個swap cache是一個頁表入口鏈表，每個對應於系統中的物理頁面。這是一個對應於交換出頁面的頁表入口並且描敘頁面放置在哪個交換文件中以及在交換文件中的位置。 如果swap cache入口為非0值，則表示在交換文件中的這一頁沒有被修改。如果此頁被修改（或者寫入）。 則其入口從swap cache中刪除。
當Linux需要將一個物理頁面交換到交換文件時，它將檢查swap cache，如果對應此頁面存在有效入口，則 不必將這個頁面寫到交換文件中。這是因為自從上次從交換文件中將其讀出來，內存中的這個頁面還沒有被修改。
swap cache中的入口是已換出頁面的頁表入口。它們雖被標記為無效但是為Linux提供了頁面在哪個交換文件中以及文件中的位置等信息。
3.10 頁面的換入
保存在交換文件中的dirty頁面可能被再次使用到，例如，當應用程序向包含在已交換出物理頁面上的虛擬內存區域寫入時。對不在物理內存中的虛擬內存頁面的訪問將引發頁面錯誤。由於處理器不能將此虛擬地址轉換成物理地址，處理器將通知操作系統。由於已被交換出去，此時描敘此頁面的頁表入口被標記成無效。處理器不能處理這種虛擬地址到物理地址的轉換，所以它將控制傳遞給操作系統，同時通知操作系統頁面錯誤的地址與原因。這些信息的格式以及處理器如何將控制傳遞給操作系統與具體硬件有關。
處理器相關頁面錯誤處理代碼將定位描敘包含出錯虛擬地址對應的虛擬內存區域的vm_area_struct數據結構。 它通過在此進程的vm_area_struct中查找包含出錯虛擬地址的位置直到找到為止。這些代碼與時間關系重大，進程的vm_area_struct數據結構特意安排成使查找操作時間更少。
執行完這些處理器相關操作並且找到出錯虛擬地址的有效內存區域後，頁面錯處理過程其余部分和前面類似。
通用頁面錯處理代碼為出錯虛擬地址尋找頁表入口。如果找到的頁表入口是一個已換出頁面，Linux必須將其 交換進入物理內存。已換出頁面的頁表入口的格式與處理器類型有關，但是所有的處理器將這些頁面標記成無效並把定位此頁面的必要信息放入頁表入口中。Linux利用這些信息以便將頁面交換進物理入內存。
此時Linux知道出錯虛擬內存地址並且擁有一個包含頁面位置信息的頁表入口。vm_area_struct數據結構可能包含將此虛擬內存區域交換到物理內存中的子程序:swapin。如果對此虛擬內存區域存在swapin則Linux會使用它。這是已換出系統V共享內存頁面的處理過程-因為已換出系統V共享頁面和普通的已換出頁面有少許不同。如果沒有swapin操作，這可能是Linux假定普通頁面無須特殊處理。
系統將分配物理頁面並將已換出頁面讀入。關於頁面在交換文件中位置信息從頁表入口中取出。
如果引起頁面錯誤的訪問不是寫操作則頁面被保留在swap cache中並且它的頁表入口不再標記為可寫。如果 頁面隨後被寫入，則將產生另一個頁面錯誤，這時頁面被標記為dirty，同時其入口從swap cache中刪除。 如果頁面沒有被寫並且被要求重新換出，Linux可以免除這次寫，因為頁面已經存在於交換文件中。
如果引起頁面從交換文件中讀出的操作是寫操作，這個頁面將被從swap cache中刪除並且其頁表入口被標記 成dirty且可寫。
