存儲管理

存儲器管理的對象是主存，也稱記憶體。它的主要功能包括分配和回收主存空間、提高主存利用率、擴充主存、對主存信息實現有效保護。

基本介紹

• 中文名：存儲管理
• 外文名：storage management
• 屬於：作業系統
• 對象：主存儲器
• 分區存儲：靜態分區可變分區、可重定位分區

存儲管理方案

存儲管理方案的主要目的是解決多個用戶使用主存的問題，其存儲管理方案主要包括分區存儲管理、分頁存儲管理、分段存儲管理、段頁式存儲管理以及虛擬存儲管理。

分區存儲

分區存儲管理又有三種不同的方式：靜態分區、可變分區、可重定位分區 。

靜態分區

靜態分區存儲管理是預先把可分配的主存儲器空間分割成若干個連續區域，每個區域的大小可以相同，也可以不同。為了說明各分區的分配和使用情況，存儲管理需設定一張“主存分配表”。主存分配表指出各分區的起始地址和長度，表中的占用標誌位用來指示該分區是否被占用了，當占用的標誌位為“0”時，表示該分區尚未被占用。進行主存分配時總是選擇那些標誌為“0”的分區，當某一分區分配給一個作業後，則在占用標誌欄填上占用該分區的作業名。採用靜態分區存儲管理，主存空間的利用不高。

可變分區

可變分區方式是按作業的大小來劃分分區。當要裝入一個作業時，根據作業需要的主存量查看主存中是否有足夠的空間，若有，則按需要量分割一個分區分配給該作業；若無，則令該作業等待主存空間。由於分區的大小是按作業的實際需要量來定的，且分區的個數也是隨機的，所以可以克服固定分區方式中的主存空間的浪費。

隨著作業的裝入、撤離，主存空間被分成許多個分區，有的分區被作業占用，而有的分區是空閒的。當一個新的作業要求裝入時，必須找一個足夠大的空閒區，把作業裝入該區，如果找到的空閒區大於作業需要量，則作業裝入後又把原來的空閒區分成兩部分，一部分給作業占用了；另一部分又分成為一個較小的空閒區。當一作主行結束撤離時，它歸還的區域如果與其它空閒區相鄰，則可合成一個較大的空閒區，以利大作業的裝入。

可變分區調度算法

1）首次適應算法。每次分配時，總是順序查找未分配表，找到第一個能滿足長度要求的空閒區為止。分割這個找到的未分配區，一部分分配給作業，另一部分仍為空閒區。這種分配算法可能將大的空間分割成小區，造成較多的主存“碎片”。

2）最佳適應算法。從空閒區中挑選一個能滿足作業要求的最小分區，這樣可保證不去分割一個更大的區域，使裝入大作業時比較容易得到滿足。採用這種分配算法時可把空閒區按大小以遞增順利排列，查找時總是從最小的一個區開始，直到找到一個滿足要求的區為止。

3）最壞適應算法。挑選一個最大的空閒區分割給作業使用，這樣可使剩下的空閒區不至於太小，這種算法對中、小作業是有利的。採用這種分配算法時可把空閒區按大小以遞減順利排列，查找時總是從最大的一個區開始。按這種方法，在收回一個分區時也必須對表格重新排列。

分頁存儲

分頁存儲管理是將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，並為各頁加以編號，從0開始，如第0頁、第1頁等。相應地，也把記憶體空間分成與頁面相同大小的若干個存儲塊，稱為(物理)塊或頁框(frame)，也同樣為它們加以編號，如0#塊、1#塊等等。在為進程分配記憶體時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。由於進程的最後一頁經常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內碎片”。

分段存儲

在分段存儲管理方式中，作業的地址空間被劃分為若干個段，每個段定義了一組邏輯信息。例如，有主程式段MAIN、子程式段X、數據段D及棧段S等。每個段都有自己的名字。為了實現簡單起見，通常可用一個段號來代替段名，每個段都從0開始編址，並採用一段連續的地址空間。段的長度由相應的邏輯信息組的長度決定，因而各段長度不等。整個作業的地址空間由於是分成多個段，因而是二維的，亦即，其邏輯地址由段號(段名)和段內地址所組成。

段頁存儲

段頁式系統的基本原理，是基本分段存儲管理方式和基本分頁存儲管理方式原理的結合，即先將用戶程式分成若干個段，再把每個段分成若干個頁，並為每一個段賦予一個段名。

虛擬存儲

當程式的存儲空間要求大於實際的記憶體空間時，就使得程式難以運行了．虛擬存儲技術就是利用實際記憶體空間和相對大的多的外部儲存器存儲空間相結合構成一個遠遠大於實際記憶體空間的虛擬存儲空間，程式就運行在這個虛擬存儲空間中．能夠實現虛擬存儲的依據是程式的局部性原理，即程式在運行過程中經常體現出運行在某個局部範圍之內的特點．在時間上，經常運行相同的指令段和數據（稱為時間局部性），在空間上，經常運行與某一局部存儲空間的指令和數據(稱為空間局部性），有些程式段不能同時運行或根本得不到運行。虛擬存儲是把一個程式所需要的存儲空間分成若干頁或段，程式運行用到頁和段就放在記憶體里，暫時不用就放在外存中．當用到外存中的頁和段時，就把它們調到記憶體，反之就把它們送到外存中．裝入記憶體中的頁或段可以分散存放．

功能

虛擬記憶體技術不僅僅可讓我們可以使用更多的記憶體，它還提供了以下功能：

定址空間

作業系統讓系統看上去有比實際記憶體大得多的記憶體空間。虛擬記憶體可以是系統中實際物理空間的許多倍。每個進程運行在其獨立的虛擬地址空間中。這些虛擬空間相互之間都完全隔離開來，所以進程間不會互相影響。同時，硬體虛擬記憶體機構可以將記憶體的某些區域設定成不可寫。這樣可以保護代碼與數據不會受惡意程式的干擾。

記憶體映射

記憶體映射技術可以將映象檔案和數據檔案直接映射到進程的地址空間。在記憶體映射中，檔案的內容被直接連線到進程虛擬地址空間上。

物理記憶體分配

記憶體管理子系統允許系統中每個運行的進程公平地共享系統中的物理記憶體。

共享虛擬記憶體

儘管虛擬記憶體允許進程有其獨立的虛擬地址空間，但有時也需要在進程之間共享記憶體。 例如有可能系統中有幾個進程同時運行BASH命令外殼程式。為了避免在每個進程的虛擬記憶體空間內都存在BASH程式的拷貝，較好的解決辦法是系統物理記憶體中只存在一份BASH的拷貝並在多個進程間共享。動態庫則是另外一種進程間共享執行代碼的方式。共享記憶體可用來作為進程間通訊(IPC)的手段，多個進程通過共享記憶體來交換信息。 Linux支持SYSTEM V的共享記憶體IPC機制。

抽象模型

虛擬地址到物理地址映射的抽象模型

在討論Linux是如何具體實現對虛擬記憶體的支持前，有必要看一下更簡單的抽象模型。

在處理器執行程式時需要將其從記憶體中讀出再進行指令解碼。在指令解碼之前它必須向記憶體中某個位置取出或者存入某個值。然後執行此指令並指向程式中下一條指令。在此過程中處理器必須頻繁訪問記憶體，要么取指取數，要么存儲數據。

虛擬記憶體系統中的所有地址都是虛擬地址而不是物理地址。通過作業系統所維護的一系列表格由處理器實現由虛擬地址到物理地址的轉換。

為了使轉換更加簡單，虛擬記憶體與物理記憶體都以頁面來組織。不同系統中頁面的大小可以相同，也可以不同，這樣將帶來管理的不便。Alpha AXP處理器上運行的Linux頁面大小為8KB，而Intel X86系統上使用4KB頁面。每個頁面通過一個叫頁面框號的數字來標示(PFN) 。

頁面模式下的虛擬地址由兩部分構成：頁面框號和頁面內偏移值。如果頁面大小為4KB，則虛擬地址的 11：0位表示虛擬地址偏移值，12位以上表示虛擬頁面框號。處理器處理虛擬地址時必須完成地址分離工作。在頁表的幫助下，它將虛擬頁面框號轉換成物理頁面框號，然後訪問物理頁面中相應偏移處。

圖3.1給出了兩個進程X和Y的虛擬地址空間，它們擁有各自的頁表。這些頁表將各個進程的虛擬頁面映射到記憶體中的物理頁面。在圖中，進程X的虛擬頁面框號0被映射到了物理頁面框號1。理論上每個頁表入口應包含以下內容：

1、有效標記，表示此頁表入口是有效的

2、頁表入口描敘的物理頁面框號

3、訪問控制信息。用來描敘此頁可以進行哪些操作，是否可寫？是否包含執行代碼?

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中，對於虛擬頁面框號2，進程X的頁表中沒有入口，這樣當進程X試圖訪問虛擬頁面框號2內容時，處理器不能將此地址轉換成物理地址。這時處理器通知作業系統有頁面錯誤發生。如果發生頁面錯的虛擬地址是無效的，則表明進程在試圖訪問一個不存在的虛擬地址。這可能是應用程式出錯而引起的，例如它試圖對記憶體進行一個隨機的寫操作。此時作業系統將終止此套用的運行以保護系統中其他進程不受此出錯進程的影響。

存儲管理

如果出錯虛擬地址是有效的，但是它指向的頁面當前不在記憶體中，則作業系統必須將此頁面從磁碟映象中讀入到記憶體中來。由於訪盤時間較長，進程必須等待一段時間直到頁面被取出來。如果系統中還存在其他進程，作業系統就會在讀取頁面過程中的等待過程中選擇其中之一來運行。讀取回來的頁面將被放在一個空閒的物理頁面框中，同時此進程的頁表中將添加對應此虛擬頁面框號的入口。最後進程將從發生頁面錯誤的地方重新開始運行。此時整個虛擬記憶體訪問過程告一段落，處理器又可以繼續進行虛擬地址到物理地址轉換，而進程也得以繼續運行。

Linux使用請求換頁將可執行映象載入到進程的虛擬記憶體中。當命令執行時，可執行的命令檔案被打開，同時其內容被映射到進程的虛擬記憶體。這些操作是通過修改描敘進程記憶體映象的數據結構來完成的，此過程稱為記憶體映射。然而只有映象的起始部分被調入物理記憶體，其餘部分仍然留在磁碟上。當映象執行時，它會產生頁面錯誤，這樣Linux將決定將磁碟上哪些部分調入記憶體繼續執行。

交換

如果進程需要把一個虛擬頁面調入物理記憶體而正好系統中沒有空閒的物理頁面，作業系統必須丟棄位於物理記憶體中的某些頁面來為之騰出空間。

如果那些從物理記憶體中丟棄出來的頁面來自於磁碟上的執行檔或者數據檔案，並且沒有修改過則不需要保存那些頁面。當進程再次需要此頁面時，直接從執行檔或者數據檔案中讀出。

但是如果頁面被修改過，則作業系統必須保留頁面的內容以備再次訪問。這種頁面被稱為dirty頁面， 當從記憶體中移出來時，它們必須保存在叫做交換檔案的特殊檔案中。相對於處理器和物理記憶體的速度，訪問交換檔案的速度是非常緩慢的，作業系統必須在將這些dirty頁面寫入磁碟和將其繼續保留在記憶體中做出選擇。

選擇丟棄頁面的算法經常需要判斷哪些頁面要丟棄或者交換，如果交換算法效率很低，則會發生"顛簸"現象。在這種情況下，頁面不斷的被寫入磁碟又從磁碟中讀回來，這樣一來作業系統就無法進行其他任何工作。以圖3.1為例，如果物理頁面框號1被頻繁使用，則頁面丟棄算法將其作為交換到硬碟的候選者是不恰當的。一個進程當前經常使用的頁面集合叫做工作集。高效的交換策略能夠確保所有進程的工作集保存在物理記憶體中。

Linux使用最少使用（LRU）頁面衰老算法來公平地選擇將要從系統中拋棄的頁面。這種策略為系統中的每個頁面設定一個年齡，它隨頁面訪問次數而變化。頁面被訪問的次數越多則頁面年齡越年輕；相反則越衰老。年齡較老的頁面是待交換頁面的最佳候選者。

虛擬記憶體

虛擬記憶體讓多個進程之間可以方便地共享記憶體。所有的記憶體訪問都是通過每個進程自身的頁表進行。對於兩個共享同一物理頁面的進程，在各自的頁表中必須包含有指向這一物理頁面框號的頁表入口。

共享物理頁面的進程對應此頁面的虛擬記憶體位置可以不同。

存儲知識結構

1、系統管理：UNIX/Linux/Windows作業系統管理。
2、開發技術：C/C++，網路編程，多進程/多執行緒，進程間通信。
3、存儲基礎：磁碟、RAID陣列、檔案系統等存儲相關硬體和軟體的安裝、配置、調試。
4、存儲系統：RAID, DAS, SAN, NAS, CAS等。
5、存儲協定：TCP/IP, SCSI, iSCSI, NFS/CIFS等。
6、檔案系統：VFS, EXTx/NTFS/FAT32等磁碟檔案系統, NFS/CIFS網路檔案系統, Lustre/GFS/AFS等分散式檔案系統。
7、存儲技術：Deduplication, SSD, HSM, Virtualization, Snapshot, Replication, CDP, VTL, Thin Provision等等。
8、存儲架構：掌握不同行業的存儲需求，能夠根據實際需求提出存儲解決方案，並進行存儲系統架構、設計和實現。

其它相關

物理與虛擬定址模式

作業系統自身也運行在虛擬記憶體中的意義不大。如果作業系統被迫維護自身的頁表那將是一個令人噁心的方案。多數通用處理器同時支持物理定址和虛擬定址模式。物理定址模式無需頁表的參與且處理器不會進行任何地址轉換。Linux核心直接運行在物理地址空間上。

Alpha AXP處理器沒有特殊的物理定址模式。它將記憶體空間劃分為幾個區域並將其中兩個指定為物理映射地址。核心地址空間被稱為KSEG地址空間，它位於地址0xfffffc0000000000以上區域。為了執行位於KSEG的核心代碼或訪問那裡的數據，代碼必須在核心模式下執行。Alpha上的Linux核心從地址0xfffffc0000310000開始執行.

訪問控制

頁表入口包含了訪問控制信息。由於處理器已經將頁表入口作為虛擬地址到物理地址的映射，那么可以很方便地使用訪問控制信息來判斷處理器是否在以其應有的方式來訪問記憶體。

諸多因素使得有必要嚴格控制對記憶體區域的訪問。有些記憶體，如包含執行代碼的部分，顯然應該是唯讀的，作業系統決不能允許進程對此區域的寫操作。相反包含數據的頁面應該是可寫的， 但是去執行這段數據肯定將導致錯誤發生。多數處理器至少有兩種執行方式：核心態與用戶態。任何人都不會允許在用戶態下執行核心代碼或者在用戶態下修改核心數據結構。

圖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_ACCESSED

Linux用它表示頁面已經被訪問過。

高速緩衝

如果用上述理論模型來實現一個系統，它可能可以工作，但效率不會高。作業系統設計者和處理器設計者都在努力以提高系統的性能。除了製造更快的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必須消耗更多的時間和空間來維護這些快取，並且當快取系統崩潰時系統也將崩潰。

Linux 頁表

圖3.3 Linux的三級頁表結構

Linux總是假定處理器有三級頁表。每個頁表通過所包含的下級頁表的頁面框號來訪問。圖3.3給出了虛擬地址是如何分割成多個域的，每個域提供了某個指定頁表的偏移。為了將虛擬地址轉換成物理地址，處理器必須得到每個域的值。這個過程將持續三次直到對應於虛擬地址的物理頁面框號被找到。最後再使用虛擬地址中的最後一個域，得到了頁面中數據的地址。

為了實現跨平台運行，Linux提供了一系列轉換宏使得核心可以訪問特定進程的頁表。這樣核心無需知道頁表入口的結構以及它們的排列方式。

這種策略相當成功，無論在具有三級頁表結構的Alpha AXP還是兩級頁表的Intel X86處理器中，Linux總是使 用相同的頁表操縱代碼。

頁面分配與回收

對系統中物理頁面的請求十分頻繁。例如當一個可執行映象被調入記憶體時，作業系統必須為其分配頁面。當映象執行完畢和卸載時這些頁面必須被釋放。物理頁面的另一個用途是存儲頁表這些核心數據結構。虛擬記憶體子系統中負責頁面分配與回收的數據結構和機制可能用處最大。

系統中所有的物理頁面用包含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開始。

頁面分配

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中。

頁面回收

將大的頁面塊打碎進行分配將增加系統中零碎空閒頁面塊的數目。頁面回收代碼在適當時機下要將這些頁面結合起來形成單一大頁面塊。事實上頁面塊大小決定了頁面重新組合的難易程度。

當頁面塊被釋放時，代碼將檢查是否有相同大小的相鄰或者buddy記憶體塊存在。如果有，則將它們結合起來形成一個大小為原來兩倍的新空閒塊。每次結合完之後，代碼還要檢查是否可以繼續合併成更大的頁面。最佳情況是系統的空閒頁面塊將和允許分配的最大記憶體一樣大。

在圖3.4中，如果釋放頁面框號1，它將和空閒頁面框號0結合作為大小為2個頁面的空閒塊排入free_area的第一個元素中。

記憶體映射

映象執行時，可執行映象的內容將被調入進程虛擬地址空間中。可執行映象使用的共享庫同樣如此。然而執行檔實際上並沒有調入物理記憶體，而是僅僅連線到進程的虛擬記憶體。當程式的其他部分運行時引用到這部分時才把它們從磁碟上調入記憶體。將映象連線到進程虛擬地址空間的過程稱為記憶體映射。

圖3.5虛擬記憶體區域

每個進程的虛擬記憶體用一個mm_struct來表示。它包含當前執行的映象（如BASH）以及指向vm_area_struct 的大量指針。每個vm_area_struct數據結構描敘了虛擬記憶體的起始與結束位置，進程對此記憶體區域的存取許可權以及一組記憶體操作函式。這些函式都是Linux在操縱虛擬記憶體區域時必須用到的子程式。其中一個負責處理進程試圖訪問不在當前物理記憶體中的虛擬記憶體(通過頁面失效)的情況。此函式叫nopage。它用在Linux試圖將可執行映象的頁面調入記憶體時。

可執行映象映射到進程虛擬地址時將產生一組相應的vm_area_struct數據結構。每個vm_area_struct數據結構表示可執行映象的一部分：可執行代碼、初始化數據(變數)、未初始化數據等等。Linux支持許多標準的虛擬記憶體操作函式，創建vm_area_struct數據結構時有一組相應的虛擬記憶體操作函式與之對應。

請求換頁

當可執行映象到進程虛擬地址空間的映射完成後，它就可以開始運行了。由於只有很少部分的映象調入記憶體，所以很快就會發生對不在物理記憶體中的虛擬記憶體區域的訪問。當進程訪問無有效頁表入口的虛擬地址時，處理器將向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時。這樣當頁面失效被處理完畢後，進程將從發生失效虛擬記憶體訪問的位置重新開始運行。

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中刪除。

換出與丟棄頁面

當系統中物理記憶體減少時，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則核心交換進程的睡眠時間又會延長。

減少P C和B C的大小

(注釋：精簡Page Cache和Buffer Cache為(PC和BC)在本文中閱讀)

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中刪除並釋放。

如果釋放出來了足夠的頁面，核心交換後台進程將等待到下一次被喚醒。這些被釋放的頁面都不是任何進程虛擬記憶體的一部分，這樣無須更新頁表。如果沒有足夠的緩衝頁面丟棄則交換進程將試圖將一些共享頁面交換出去。

換出系統V記憶體頁面

系統V共享記憶體是一種用來在進程之間通過共享虛擬記憶體來實現進程通訊的機制。指針，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數據結構鍊表中的頁表入口也被換出頁表入口代替。換出頁表入口雖然無效但是它包含一組打開的交換檔案的索引，同時還能找到換出頁面在檔案中的偏移。當頁面重新被帶入物理記憶體時，這些信息十分有用。

換出和丟棄頁面

交換後台進程依次檢查系統中的每個進程以確認誰最適合交換出去。

比較好的候選者是那些可以被交換出去（有些是不可被交換出去的）並且只有一個或者幾個頁面在記憶體中的進程。只有那些包含的數據無法檢索的頁面才會從物理記憶體中交換到系統交換檔案中去。

可執行映象的許多內容都可以從映象檔案中讀出並且可以很容易重讀出來。例如，映象中的可執行指令不能被映象本身修改，所以決不會寫到交換檔案中去。這些頁面直接丟棄就可以。當進程再次引用它們時，只需要從可執行映象檔案中讀入記憶體即可。

一旦確定了將要被交換出去的進程，交換後台進程將搜尋其整個虛擬記憶體區域以找到那些沒有共享或者加鎖的區域。

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以備重新使用。

如果有足夠的可交換進程頁面被交換出去或丟棄，則交換後台進程將再次睡眠。下次它醒來時將考慮系統中 的下一個進程。通過這種方法，交換後台進程一點一點地將每個進程的可交換或可丟棄物理頁面收回知道系 統再次處於平衡狀態。這比將整個進程交換出去要公平得多。

The Swap Cache

當將頁面交換到交換檔案中時，Linux總是避免頁面寫，除非必須這樣做。當頁面已經被交換出記憶體但是當有進程再次訪問時又要將它重新調入記憶體。只要頁面在記憶體中沒有被寫過，則交換檔案中的拷貝是有效的。

Linux使用swap cache來跟蹤這些頁面。這個swap cache是一個頁表入口鍊表，每個對應於系統中的物理頁面。這是一個對應於交換出頁面的頁表入口並且描敘頁面放置在哪個交換檔案中以及在交換檔案中的位置。 如果swap cache入口為非0值，則表示在交換檔案中的這一頁沒有被修改。如果此頁被修改（或者寫入）。 則其入口從swap cache中刪除。

當Linux需要將一個物理頁面交換到交換檔案時，它將檢查swap cache，如果對應此頁面存在有效入口，則 不必將這個頁面寫到交換檔案中。這是因為自從上次從交換檔案中將其讀出來，記憶體中的這個頁面還沒有被修改。

swap cache中的入口是已換出頁面的頁表入口。它們雖被標記為無效但是為Linux提供了頁面在哪個交換檔案中以及檔案中的位置等信息。

頁面的換入

保存在交換檔案中的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且可寫。

移動存儲管理系統

特點

► 獲國家保密局認證，安全可靠；

► 與加密系統無縫結合，防護能力倍增；

► 國內首創，將普通隨身碟變為加密隨身碟，徹底解決隨身碟的方便性帶來的風險；

► 採用雙因子認證技術；

► 專用加密移動存儲與系統無縫結合，管理更流暢；

► 功能多樣，可滿足各種不同需求的保密要求；

► 完善的審計功能，隨時掌握隨身碟持有人的行為。

功能

● 集中註冊與授權。可通過註冊信息實現隨身碟身份識別和介質追蹤；

● 主機身份認證。所有安裝客戶端的計算機都須經管理員分配實名信息後方可使用；

● 加密上鎖。對加密上鎖後的隨身碟需要用戶進行身份認證；

● 訪問控制。可靈活控制移動存儲介質註冊策略和信息，設定允許使用的計算機或租；

● 外出拷貝。拷入隨身碟內的數據可與外界的計算機進行數據互動使用，也可實現定向拷貝；

● 用戶審計。移動管理存儲系統提供詳細的審計記錄及審計報告。