磁盤管理 存儲管理

{

\"code\": 200,

\"title\": \"\",

\"content\": \"存儲管理子係統是操作係統中最重要的組成部分之一。在早期計算時代，由於人們所需要的內存數目遠遠大於物理內存，人們設計出了各種各樣的策略來解決此問題，其中最成功的是虛擬內存技術。它使得係統中為有限物理內存競爭的進程所需內存空間得到滿足。\\n\\n存儲管理的方式\\n\\n1.分區存儲管理\\n\\n分區存儲管理又有三種不同的方式：靜態分區、可變分區、可重定位分區。\\n\\n2.分頁存儲管理\\n\\n分頁存儲管理是將一個進程的邏輯地址空間分成若乾個大小相等的片，稱為頁麵或頁，併爲各頁加以編號，從0開始，如第0頁、第1頁等。相應地，也把內存空間分成與頁麵相同大小的若乾個存儲塊，稱為(物理)塊或頁框(frame)，也同樣為它們加以編號，如0#塊、1#塊等等。在為進程分配內存時，以塊為單位將進程中的若乾個頁分彆裝入到多個可以不相鄰接的物理塊中。由於進程的最後一頁經常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內碎片”。\\n\\n3.分段存儲管理\\n\\n在分段存儲管理方式中，作業的地址空間被劃分爲若乾個段，每個段定義了一組邏輯資訊。例如，有主程式段MAIN、子程式段X、數據段D及棧段S等，如圖4-17所示。每個段都有自己的名字。為了實現簡單起見，通常可用一個段號來代替段名，每個段都從0開始編址，並采用一段連續的地址空間。段的長度由相應的邏輯資訊組的長度決定，因而各段長度不等。整個作業的地址空間由於是分成多個段，因而是二維的，亦即，其邏輯地址由段號(段名)和段內地址所組成。分段地址中的地址具有如下結構：在該地址結構中，允許一個作業最長有64K個段，每個段的最大長度為64KB。 分段方式已得到許多編譯程式的支援，編譯程式能自動地根據源程式的情況而產生若乾個段。例如，Pascal編譯程式可以為全域性變量、用於存儲相應參數及返回地址的過程調用棧、每個過程或函數的代碼部分、每個過程或函數的區域性變量等等，分彆建立各自的段。類似地，Fortran編譯程式可以為公共塊(Commonblock)建立單獨的段，也可以為數組分配一個單獨的段。裝入程式將裝入所有這些段，併爲每個段賦予一個段號。\\n\\n4.段頁式存儲管理\\n\\n段頁式係統的基本原理，是基本分段存儲管理方式和基本分頁存儲管理方式原理的結合，即先將用戶程式分成若乾個段，再把每個段分成若乾個頁，併爲每一個段賦予一個段名。右圖示出了一個作業的地址空間和地址結構。該作業有三個段，頁麵大小為4KB。在段頁式係統中，其地址結構由段號、段內頁號及頁內地址三部分所組成，如下圖所示。\\n\\n5.虛擬存儲管理\\n\\n當程式的存儲空間要求大於實際的內存空間時，就使得程式難以運行了．虛擬存儲技術就是利用實際內存空間和相對大的多的外部儲存器存儲空間相結合構成一個遠遠大於實際內存空間的虛擬存儲空間，程式就運行在這個虛擬存儲空間中．能夠實現虛擬存儲的依據是程式的區域性性原理，即程式在運行過程中經常體現出運行在某個區域性範圍之內的特點．在時間上，經常運行相同的指令段和數據（稱為時間區域性性），在空間上，經常運行與某一區域性存儲空間的指令和數據(稱為空間區域性性），有些程式段不能同時運行或根本得不到運行．虛擬存儲是把一個程式所需要的存儲空間分成若乾頁或段，程式運行用到頁和段就放在內存裡，暫時不用就放在外存中．當用到外存中的頁和段時，就把它們調到內存，反之就把它們送到外存中．裝入內存中的頁或段可以分散存放．\\n\\n功能\\n\\n虛擬內存技術不僅僅可讓我們可以使用更多的內存，它還提供了以下功能：\\n\\n巨大的尋址空間\\n\\n操作係統讓係統看上去有比實際內存大得多的內存空間。虛擬內存可以是係統中實際物理空間的許多倍。每個進程運行在其獨立的虛擬地址空間中。這些虛擬空間相互之間都完全隔離開來，所以進程間不會互相影響。同時，硬體虛擬內存機構可以將內存的某些區域設置成不可寫。這樣可以保護代碼與數據不會受惡意程式的乾擾。\\n\\n內存對映\\n\\n內存對映技術可以將映象檔案和數據檔案直接對映到進程的地址空間。在內存對映中，檔案的內容被直接連接到進程虛擬地址空間上。\\n\\n公平的物理內存分配\\n\\n內存管理子係統允許係統中每個運行的進程公平地共享係統中的物理內存。\\n\\n共享虛擬內存\\n\\n儘管虛擬內存允許進程有其獨立的虛擬地址空間，但有時也需要在進程之間共享內存。例如有可能係統中有幾個進程同時運行BASH命令外殼程式。為了避免在每個進程的虛擬內存空間內都存在BASH程式的拷貝，較好的解決辦法是係統物理內存中隻存在一份BASH的拷貝並在多個進程間共享。動態庫則是另外一種進程間共享執行代碼的方式。共享內存可用來作為進程間通訊(IPC)的手段，多個進程通過共享內存來交換資訊。Linux支援SYSTEMV的共享內存IPC機製。\\n\\n虛擬內存的抽象模型\\n\\n虛擬地址到實體地址對映的抽象模型\\n\\n在討論Linux是如何具體實現對虛擬內存的支援前，有必要看一下更簡單的抽象模型。\\n\\n在處理器執行程式時需要將其從內存中讀出再進行指令解碼。在指令解碼之前它必須向內存中某個位置取出或者存入某個值。然後執行此指令並指向程式中下一條指令。在此過程中處理器必須頻繁訪問內存，要麼取指取數，要麼存儲數據。\\n\\n虛擬內存係統中的所有地址都是虛擬地址而不是實體地址。通過操作係統所維護的一係列表格由處理器實現由虛擬地址到實體地址的轉換。\\n\\n為了使轉換更加簡單，虛擬內存與物理內存都以頁麵來組織。不同係統中頁麵的大小可以相同，也可以不同，這樣將帶來管理的不便。AlphaAXP處理器上運行的Linux頁麵大小為8KB，而IntelX86係統上使用4KB頁麵。每個頁麵通過一個叫頁麵框號的數字來標示(PFN)。\\n\\n頁麵模式下的虛擬地址由兩部分構成：頁麵框號和頁麵內偏移值。如果頁麵大小為4KB，則虛擬地址的11：0位表示虛擬地址偏移值，12位以上表示虛擬頁麵框號。處理器處理虛擬地址時必須完成地址分離工作。在頁表的幫助下，它將虛擬頁麵框號轉換成物理頁麵框號，然後訪問物理頁麵中相應偏移處。\\n\\n圖3.1給出了兩個進程X和Y的虛擬地址空間，它們擁有各自的頁表。這些頁表將各個進程的虛擬頁麵對映到內存中的物理頁麵。在圖中，進程X的虛擬頁麵框號0被對映到了物理頁麵框號4。理論上每個頁表入口應包含以下內容：\\n\\n有效標記，表示此頁表入口是有效的\\n\\n頁表入口描敘的物理頁麵框號\\n\\n訪問控製資訊。用來描敘此頁可以進行哪些操作，是否可寫？是否包含執行代碼?\\n\\n虛擬頁麵框號是為頁表中的偏移。虛擬頁麵框號5對應表中的第6個單元（0是第一個）。\\n\\n為了將虛擬地址轉換為實體地址，處理器首先必須得到虛擬地址頁麵框號及頁內偏移。一般將頁麵大小設為2的次冪。將圖3.1中的頁麵大小設為0x2000字節（十進製爲8192）並且在進程Y的虛擬地址空間中某個地址為0x2194，則處理器將其轉換為虛擬頁麵框號1及頁內偏移0x194。\\n\\n處理器使用虛擬頁麵框號為索引來訪問處理器頁表，檢索頁表入口。如果在此位置的頁表入口有效，則處理器將從此入口中得到物理頁麵框號。如果此入口無效，則意味著處理器存取的是虛擬內存中一個不存在的區域。在這種情況下，處理器是不能進行地址轉換的，它必須將控製傳遞給操作係統來完成這個工作。\\n\\n某個進程試圖訪問處理器無法進行有效地址轉換的虛擬地址時，處理器如何將控製傳遞到操作係統依賴於具體的處理器。通常的做法是：處理器引發一個頁麵失效錯而陷入操作係統核心，這樣操作係統將得到有關無效虛擬地址的資訊以及發生頁麵錯誤的原因。\\n\\n再以圖3.1為例，進程Y的虛擬頁麵框號1被對映到係統物理頁麵框號4，則再物理內存中的起始位置為0x8000(4*0x2000)。加上0x194字節偏移則得到最終的實體地址0x8194。\\n\\n通過將虛擬地址對映到實體地址，虛擬內存可以以任何順序對映到係統物理頁麵。例如，在圖3.1中，進程X的虛擬頁麵框號0被對映到物理頁麵框號1而虛擬頁麵框號7被對映到物理頁麵框號0，雖然後者的虛擬頁麵框號要高於前者。這樣虛擬內存技術帶來了有趣的結果：虛擬內存中的頁麵無須在物理內存保持特定順序。\\n\\n請求換頁\\n\\n在物理內存比虛擬內存小得多的係統中，操作係統必須提高物理內存的使用效率。節省物理內存的一種方法是僅加載那些正在被執行程式使用的虛擬頁麵。比如說，某個數據庫程式可能要對某個數據庫進行查詢操作，此時並不是數據庫的所有內容都要加載到內存中去，而隻加載那些要用的部分。如果此數據庫查詢是一個搜尋查詢而無須對數據庫進行新增記錄操作，則加載新增記錄的代碼是毫無意義的。這種僅將要訪問的虛擬頁麵載入的技術叫請求換頁。\\n\\n當進程試圖訪問當前不在內存中的虛擬地址時，處理器在頁表中無法找到所引用地址的入口。在圖3.1中，對於虛擬頁麵框號2，進程X的頁表中冇有入口，這樣當進程X試圖訪問虛擬頁麵框號2內容時，處理器不能將此地\\n\\n存儲管理\\n\\n址轉換成實體地址。這時處理器通知操作係統有頁麵錯誤發生。\\n\\n存儲管理如果發生頁麵錯的虛擬地址是\\n\\n無效的，則表明進程在試圖訪問一個不存在的虛擬地址。這可能是應用程式出錯而引起的，例如它試圖對內存進行一個隨機的寫操作。此時操作係統將終止此應用的運行以保護係統中其他進程不受此出錯進程的影響。\\n\\n如果出錯虛擬地址是有效的，但是它指向的頁麵當前不在內存中，則操作係統必須將此頁麵從磁盤映象中讀入到內存中來。由於訪盤時間較長，進程必須等待一段時間直到頁麵被取出來。如果係統中還存在其他進程，操作係統就會在讀取頁麵過程中的等待過程中選擇其中之一來運行。讀取回來的頁麵將被放在一個空閒的物理頁麵框中，同時此進程的頁表中將新增對應此虛擬頁麵框號的入口。最後進程將從發生頁麵錯誤的地方重新開始運行。此時整個虛擬內存訪問過程告一段落，處理器又可以繼續進行虛擬地址到實體地址轉換，而進程也得以繼續運行。\\n\\nLinux使用請求換頁將可執行映象加載到進程的虛擬內存中。當命令執行時，可執行的命令檔案被打開，同時其內容被對映到進程的虛擬內存。這些操作是通過修改描敘進程內存映象的數據結構來完成的，此過程稱為內存對映。然而隻有映象的起始部分被調入物理內存，其餘部分仍然留在磁盤上。當映象執行時，它會產生頁麵錯誤，這樣Linux將決定將磁盤上哪些部分調入內存繼續執行。\\n\\n交換\\n\\n如果進程需要把一個虛擬頁麵調入物理內存而正好係統中冇有空閒的物理頁麵，操作係統必須丟棄位於物理內存中的某些頁麵來為之騰出空間。\\n\\n如果那些從物理內存中丟棄出來的頁麵來自於磁盤上的可執行檔案或者數據檔案，並且冇有修改過則不需要儲存那些頁麵。當進程再次需要此頁麵時，直接從可執行檔案或者數據檔案中讀出。\\n\\n但是如果頁麵被修改過，則操作係統必須保留頁麵的內容以備再次訪問。這種頁麵被稱為dirty頁麵，當從內存中移出來時，它們必須儲存在叫做交換檔案的特殊檔案中。相對於處理器和物理內存的速度，訪問交換檔案的速度是非常緩慢的，操作係統必須在將這些dirty頁麵寫入磁盤和將其繼續保留在內存中做出選擇。\\n\\n選擇丟棄頁麵的演算法經常需要判斷哪些頁麵要丟棄或者交換，如果交換演算法效率很低，則會發生\\\"顛簸\\\"現象。在這種情況下，頁麵不斷的被寫入磁盤又從磁盤中讀回來，這樣一來操作係統就無法進行其他任何工作。以圖3.1為例，如果物理頁麵框號1被頻繁使用，則頁麵丟棄演算法將其作為交換到硬盤的候選者是不恰當的。一個進程當前經常使用的頁麵集合叫做工作集。高效的交換策略能夠確保所有進程的工作集儲存在物理內存中。\\n\\nLinux使用最近最少使用（LRU）頁麵衰老演算法來公平地選擇將要從係統中拋棄的頁麵。這種策略為係統中的每個頁麵設置一個年齡，它隨頁麵訪問次數而變化。頁麵被訪問的次數越多則頁麵年齡越年輕；相反則越衰老。年齡較老的頁麵是待交換頁麵的最佳候選者。\\n\\n共享虛擬內存\\n\\n虛擬內存讓多個進程之間可以方便地共享內存。所有的內存訪問都是通過每個進程自身的頁表進行。對於兩個共享同一物理頁麵的進程，在各自的頁表中必須包含有指向這一物理頁麵框號的頁表入口。\\n\\n圖3.1中兩個進程共享物理頁麵框號4。對進程X來說其對應的虛擬頁麵框號為4而進程Y的為6。這個有趣的現象說明：共享物理頁麵的進程對應此頁麵的虛擬內存位置可以不同。\\n\\n物理與虛擬尋址模式\\n\\n操作係統自身也運行在虛擬內存中的意義不大。如果操作係統被迫維護自身的頁表那將是一個令人噁心的方案。多數通用處理器同時支援物理尋址和虛擬尋址模式。物理尋址模式無需頁表的參與且處理器不會進行任何地址轉換。Linux核心直接運行在實體地址空間上。\\n\\nAlphaAXP處理器冇有特殊的物理尋址模式。它將內存空間劃分爲幾個區域並將其中兩個指定為物理對映地址。核心地址空間被稱為KSEG地址空間，它位於地址0xfffffc0000000000以上區域。為了執行位於KSEG的核心代碼或訪問那裡的數據，代碼必須在覈心模式下執行。Alpha上的Linux核心從地址0xfffffc0000310000開始執行.\\n\\n訪問控製\\n\\n頁表入口包含了訪問控製資訊。由於處理器已經將頁表入口作為虛擬地址到實體地址的對映，那麼可以很方便地使用訪問控製資訊來判斷處理器是否在以其應有的方式來訪問內存。\\n\\n諸多因素使得有必要嚴格控製對內存區域的訪問。有些內存，如包含執行代碼的部分，顯然應該是隻讀的，操作係統決不能允許進程對此區域的寫操作。相反包含數據的頁麵應該是可寫的，但是去執行這段數據肯定將導致錯誤發生。多數處理器至少有兩種執行方式：核心態與用戶態。任何人都不會允許在用戶態下執行核心代碼或者在用戶態下修改核心數據結構。\\n\\n圖3.2AlphaAXP頁表入口\\n\\n頁表入口中的訪問控製資訊是處理器相關的；圖3.2是AlphaAXP處理器的PTE(PageTableEntry)。這些位域的含義如下：\\n\\nV\\n\\n有效，如果此位置位，表明此PTE有效\\n\\nFOE\\n\\n“執行時失效”，無論何時隻要執行包含在此頁麵中的指令，處理器都將報告頁麵錯誤並將控製傳遞\\n\\nFOW\\n\\n“寫時失效”,除了頁麵錯誤發生在對此頁麵的寫時，其他與上相同。\\n\\nFOR\\n\\n“讀時失效”，除了頁麵錯誤發生在對此頁麵的讀時，其他與上相同。\\n\\nA**\\n\\n地址空間匹配。被操作係統用於清洗轉換緩衝中的某些入口。\\n\\nKRE\\n\\n運行在覈心模式下的代碼可以讀此頁麵。\\n\\nURE\\n\\n運行在用戶模式下的代碼可以讀此頁麵。\\n\\nGH\\n\\n將整個塊對映到單個而不是多個轉換緩衝時的隱含粒度。\\n\\nKWE\\n\\n運行在覈心模式下的代碼可以寫此頁麵。\\n\\nUWE\\n\\n運行在用戶模式下的代碼可以寫此頁麵。\\n\\npageframenumber\\n\\n對於V位置位的PTE，此域包含了對應此PTE的物理頁麵框號；對於無效PTE，此域不為0，它包含了頁麵在交換檔案中位置的資訊。\\n\\n以下兩位由Linux定義並使用。\\n\\n_PAGE_DIRTY\\n\\n如果置位，此頁麵要被寫入交換檔案。\\n\\n_PAGE_ACCESSED\\n\\nLinux用它表示頁麵已經被訪問過。\\n\\n高速緩衝\\n\\n如果用上述理論模型來實現一個係統，它可能可以工作，但效率不會高。操作係統設計者和處理器設計者都在努力以提高係統的效能。除了製造更快的CPU和內存外，最好的辦法是在高速緩衝中維護有用資訊和數據以加快某些操作。Linux使用了許多與高速緩衝相關的內存管理策略。\\n\\nBufferCache\\n\\n這個buffercache中包含了被塊設備驅動使用的數據緩衝。\\n\\n這些緩衝的單元的大小一般固定(例如說512字節)並且包含從塊設備讀出或者寫入的資訊塊。塊設備是僅能夠以固定大小塊進行讀寫操作的設備。所有的硬盤都是塊設備。\\n\\n利用設備標誌符和所需塊號作索引可以在buffercache中迅速地找到數據。塊設備隻能夠通過buffercache來存取。如果數據在buffercache中可以找到則無需從物理塊設備(如硬盤)中讀取，這樣可以加速訪問。\\n\\nPageCache\\n\\n用來加速硬盤上可執行映象檔案與數據檔案的存取。\\n\\n它每次緩衝一個頁麵的檔案內容。頁麵從磁盤上讀入內存後緩存在pagecache中。\\n\\nSwapCache\\n\\n隻有修改過的頁麵存儲在交換檔案中。\\n\\n隻要這些頁麵在寫入到交換檔案後冇有被修改，則下次此頁麵被交換出內存時，就不必再進行更新寫操作，這些頁麵都可以簡單的丟棄。在交換頻繁發生的係統中，SwapCache可以省下很多不必要且耗時的磁盤操作。\\n\\nHardwareCache\\n\\n一個常見的hardwarecache是處理器中的頁表入口cache。處理器不總是直接讀取頁表而是在需要時緩存頁麵的轉換。這種cache又叫做轉換旁視緩衝(TranslationLook-asideBuffers)，它包含係統中一個或多個處理器的頁表入口的緩衝拷貝。\\n\\n當發出對虛擬地址的引用時，處理器試圖找到相匹配的TLB入口。如果找到則直接將虛擬地址轉換成實體地址並對數據進行處理。如果冇有找到則向操作係統尋求幫助。處理器將向操作係統發出TLB失配信號，它使用一個特定的係統機製來將此異常通知操作係統。操作係統則為此地址匹配對產生新的TLB入口。當操作係統清除此異常時，處理器將再次進行虛擬地址轉換。由於此時在TLB中已經有相應的入口，這次操作將成功。\\n\\n使用高速緩存的缺點在於Linux必須消耗更多的時間和空間來維護這些緩存，並且當緩存係統崩潰時係統也將崩潰。\\n\\nLinux頁表\\n\\n圖3.3Linux的三級頁表結構\\n\\nLinux總是假定處理器有三級頁表。每個頁表通過所包含的下級頁表的頁麵框號來訪問。圖3.3給出了虛擬地址是如何分割成多個域的，每個域提供了某個指定頁表的偏移。為了將虛擬地址轉換成實體地址，處理器必須得到每個域的值。這個過程將持續三次直到對應於虛擬地址的物理頁麵框號被找到。最後再使用虛擬地址中的最後一個域，得到了頁麵中數據的地址。\\n\\n為了實現跨平台運行，Linux提供了一係列轉換宏使得核心可以訪問特定進程的頁表。這樣核心無需知道頁表入口的結構以及它們的排列方式。\\n\\n這種策略相當成功，無論在具有三級頁表結構的AlphaAXP還是兩級頁表的IntelX86處理器中，Linux總是使用相同的頁表操縱代碼。\\n\\n頁麵分配與回收\\n\\n對係統中物理頁麵的請求十分頻繁。例如當一個可執行映象被調入內存時，操作係統必須為其分配頁麵。當映象執行完畢和卸載時這些頁麵必須被釋放。物理頁麵的另一個用途是存儲頁表這些核心數據結構。虛擬內存子係統中負責頁麵分配與回收的數據結構和機製可能用處最大。\\n\\n係統中所有的物理頁麵用包含mem_map_t結構的鏈表mem_map來描敘，這些結構在係統啟動時初始化。每個mem_map_t描敘了一個物理頁麵。其中與內存管理相關的重要域如下：\\n\\ncount\\n\\n記錄使用此頁麵的用戶個數。當這個頁麵在多個進程之間共享時，它的值大於1。\\n\\nage\\n\\n此域描敘頁麵的年齡，用於選擇將適當的頁麵拋棄或者置換出內存時。\\n\\nmap_nr\\n\\n記錄本mem_map_t描敘的物理頁麵框號。\\n\\n頁麵分配代碼使用free_area數組來尋找和釋放頁麵，此機製負責整個緩衝管理。另外此代碼與處理器使用的頁麵大小和物理分頁機製無關。\\n\\nfree_area中的每個元素都包含頁麵塊的資訊。數組中第一個元素描敘1個頁麵，第二個表示2個頁麵大小的塊而接下來表示4個頁麵大小的塊，總之都是2的次冪倍大小。list域表示一個隊列頭，它包含指向mem_map數組中page數據結構的指針。所有的空閒頁麵都在此隊列中。map域是指向某個特定頁麵尺寸的頁麵組分配情況位圖的指針。當頁麵的第N塊空閒時，位圖的第N位被置位。\\n\\n圖free-area-figure畫出了free_area結構。第一個元素有個自由頁麵（頁麵框號0），第二個元素有4個頁麵大小的2個自由塊，前一個從頁麵框號4開始而後一個從頁麵框號56開始。\\n\\n頁麵分配\\n\\nLinux使用Buddy演算法來有效的分配與回收頁麵塊。頁麵分配代碼每次分配包含一個或者多個物理頁麵的內存塊。頁麵以2的次冪的內存塊來分配。這意味著它可以分配1個、2個和4個頁麵的塊。隻要係統中有足夠的空閒頁麵來滿足這個要求(nr_free_pages>min_free_page)，內存分配代碼將在free_area中尋找一個與請求大小相同的空閒塊。free_area中的每個元素儲存著一個反映這樣大小的已分配與空閒頁麵的位圖。例如，free_area數組中第二個元素指向一個反映大小為四個頁麵的內存塊分配情況的內存映象。\\n\\n分配演算法首先搜尋滿足請求大小的頁麵。它從free_area數據結構的list域著手沿鏈來搜尋空閒頁麵。如果冇有這樣請求大小的空閒頁麵，則它搜尋兩倍於請求大小的內存塊。這個過程一直將持續到free_area被搜尋完或找到滿足要求的內存塊為止。如果找到的頁麵塊大於請求的塊則對其進行分割以使其大小與請求塊匹配。由於塊大小都是2的次冪所以分割過程十分簡單。空閒塊被連進相應的隊列而這個頁麵塊被分配給調用者。\\n\\n圖3.4free_area數據結構\\n\\n在圖3.4中，當係統中有大小為兩個頁麵塊的請求發出時，第一個4頁麵大小的內存塊（從頁麵框號4開始）將分成兩個2頁麵大小的塊。前一個，從頁麵框號4開始的，將分配出去返回給請求者，而後一個，從頁麵框號6開始，將被新增到free_area數組中表示兩個頁麵大小的空閒塊的元素1中。\\n\\n頁麵回收\\n\\n將大的頁麵塊打碎進行分配將增加係統中零碎空閒頁麵塊的數目。頁麵回收代碼在適當時機下要將這些頁麵結合起來形成單一大頁麵塊。事實上頁麵塊大小決定了頁麵重新組合的難易程度。\\n\\n當頁麵塊被釋放時，代碼將檢查是否有相同大小的相鄰或者buddy內存塊存在。如果有，則將它們結合起來形成一個大小為原來兩倍的新空閒塊。每次結合完之後，代碼還要檢查是否可以繼續合併成更大的頁麵。最佳情況是係統的空閒頁麵塊將和允許分配的最大內存一樣大。\\n\\n在圖3.4中，如果釋放頁麵框號1，它將和空閒頁麵框號0結合作為大小為2個頁麵的空閒塊排入free_area的第一個元素中。\\n\\n內存對映\\n\\n映象執行時，可執行映象的內容將被調入進程虛擬地址空間中。可執行映象使用的共享庫同樣如此。然而可執行檔案實際上並冇有調入物理內存，而是僅僅連接到進程的虛擬內存。當程式的其他部分運行時引用到這部分時才把它們從磁盤上調入內存。將映象連接到進程虛擬地址空間的過程稱為內存對映。\\n\\n圖3.5虛擬內存區域\\n\\n每個進程的虛擬內存用一個mm_struct來表示。它包含當前執行的映象（如BASH）以及指向vm_area_struct的大量指針。每個vm_area_struct數據結構描敘了虛擬內存的起始與結束位置，進程對此內存區域的存取權限以及一組內存操作函數。這些函數都是Linux在操縱虛擬內存區域時必須用到的子程式。其中一個負責處理進程試圖訪問不在當前物理內存中的虛擬內存(通過頁麵失效)的情況。此函數叫nopage。它用在Linux試圖將可執行映象的頁麵調入內存時。\\n\\n可執行映象對映到進程虛擬地址時將產生一組相應的vm_area_struct數據結構。每個vm_area_struct數據結構表示可執行映象的一部分：可執行代碼、初始化數據(變量)、未初始化數據等等。Linux支援許多標準的虛擬內存操作函數，創建vm_area_struct數據結構時有一組相應的虛擬內存操作函數與之對應。\\n\\n請求換頁\\n\\n當可執行映象到進程虛擬地址空間的對映完成後，它就可以開始運行了。由於隻有很少部分的映象調入內存，所以很快就會發生對不在物理內存中的虛擬內存區域的訪問。當進程訪問無有效頁表入口的虛擬地址時，處理器將向Linux報告一個頁麵錯誤。\\n\\n頁麵錯誤帶有失效發生的虛擬地址及引發失效的訪存方式。Linux必須找到表示此區域的vm_area_struct結構。對vm_area_struct數據結構的搜尋速度決定了處理頁麵錯誤的效率，而所有vm_area_struct結構是通過一種AVL(Adelson-VelskiiandLandis)樹結構連在一起的。如果無法找到vm_area_struct與此失效虛擬地址的對應關係，則係統認為此進程訪問了非法虛擬地址。這時Linux將向進程發送SIGSEGV信號，如果進程冇有此信號的處理過程則終止運行。\\n\\n如果找到此對應關係，Linux接下來檢查引起該頁麵錯誤的訪存類型。如果進程以非法方式訪問內存，比如對不可寫區域進行寫操作，係統將產生內存錯誤的信號。\\n\\n如果Linux認為頁麵出錯是合法的，那麼它需要對這種情況進行處理。\\n\\n首先Linux必須區分位於交換檔案中的頁麵和那些位於磁盤上的可執行映象。AlphaAXP的頁表中有可能存在有效位冇有設置但是在PFN域中有非0值的頁表入口。在這種情況下，PFN域指示的是此頁麵在交換檔案中的位置。如何處理交換檔案中的頁麵將在下章討論。\\n\\n不是所有的vm_area_struct數據結構都有一組虛擬內存操作函數，它們有的甚至冇有nopage函數。這是因為Linux通過分配新的物理頁麵併爲其創建有效的頁表入口來修正這次訪問。如果這個內存區域存在nopage操作函數，Linux將調用它。\\n\\n一般Linuxnopage函數被用來處理內存對映可執行映象，同時它使用頁麵cache將請求的頁麵調入物理內存中去。\\n\\n當請求的頁麵調入物理內存時，處理器頁表也必須更新。更新這些入口必須進行相關硬體操作，特彆是處理器使用TLB時。這樣當頁麵失效被處理完畢後，進程將從發生失效虛擬內存訪問的位置重新開始運行。\\n\\nLinux頁麵cache\\n\\n圖3.6Linux頁麵Cache\\n\\nLinux使用頁麵cache的目的是加快對磁盤上檔案的訪問。內存對映檔案以每次一頁的方式讀出並將這些頁麵存儲在頁麵cache中。圖3.6表明頁麵cache由page_hash_table，指向mem_map_t數據結構的指針數組組成。\\n\\nLinux中的每個檔案通過一個VFSinode（在檔案係統一章中講敘）數據結構來標識並且每個VFSinode都是唯一的，它可以並僅可以描敘一個檔案。頁表的索引從檔案的VFSinode和檔案的偏移中派生出來。\\n\\n從一個內存對映檔案中讀出頁麵，例如產生換頁請求時要將頁麵讀回內存中，係統嘗試從頁麵cache來讀出。如果頁麵在cache中，則返回頁麵失效處理過程一個指向mem_map_t數據結構；否則此頁麵將從包含映象的檔案係統中讀入內存併爲之分配物理頁麵。\\n\\n在映象的讀入與執行過程中，頁麵cache不斷增長。當不再需要某個頁麵時，即不再被任何進程使用時，它將被從頁麵cache中刪除。\\n\\n換出與丟棄頁麵\\n\\n當係統中物理內存減少時，Linux內存管理子係統必須釋放物理頁麵。這個任務由核心交換後台進程(kswapd)來完成。\\n\\n核心交換後台進程是一種特殊的核心線程。它是冇有虛擬內存的進程，在實體地址空間上以核心態運行。核心交換後台進程的名字容易使人誤解，其實它完成的工作比僅僅將頁麵交換到係統的交換檔案中要多得多。其目標是保證係統中有足夠的空閒頁麵來維持內存管理係統運行效率。\\n\\n此進程由核心的init進程在係統啟動時運行，被核心交換定時器週期性的調用。\\n\\n當定時器到時後，交換後台進程將檢查係統中的空閒頁麵數是否太少。它使用兩個變量：free_pages_high和free_page_low來判斷是否該釋放一些頁麵。隻要係統中的空閒頁麵數大於free_pages_high，核心交換後台進程不做任何工作；它將睡眠到下一次定時器到時。在檢查中，核心交換後台進程將當前被寫到交換檔案中的頁麵數也計算在內，它使用nr_async_pages來記錄這個數值；當有頁麵被排入準備寫到交換檔案隊列中時，它將遞增一次，同時當寫入操作完成後遞減一次。如果係統中的空閒頁麵數在free_pages_high甚至free_pages_low以下時，核心交換後台進程將通過三個途徑來減少係統中使用的物理頁麵的個數：\\n\\n減少緩衝與頁麵cache的大小，\\n\\n將係統V類型的內存頁麵交換出去，\\n\\n換出或者丟棄頁麵。\\n\\n如果係統中空閒頁麵數低於free_pages_low，核心交換後台進程將在下次運行之前釋放6個頁麵。否則它隻釋放3個。以上三種方法將依次使用直到係統釋放出足夠的空閒頁麵。當核心交換後台進程試圖釋放物理頁麵時它將記錄使用的最後一種方法。下一次它會首先運行上次最後成功的演算法。\\n\\n當釋放出足夠頁麵後，核心交換後台進程將再次睡眠到下次定時器到時。如果導致核心交換後台進程釋放頁麵的原因是係統中的空閒頁麵數小於free_pages_low，則它隻睡眠平時的一半時間。一旦空閒頁麵數大於free_pages_low則核心交換進程的睡眠時間又會延長。\\n\\n減少PageCache和BufferCache的大小\\n\\nPageCache和Buffercache中的頁麵將被優先考慮釋放到free_area數組中。PageCache中包含的是內存對映檔案的頁麵，其中有些可能是不必要的，它們浪費了係統的內存。而BufferCache中包含的是從物理設備中讀寫的緩衝數據，有些可能也是不必要的。當係統中物理頁麵開始耗儘時，從這些cache中丟棄頁麵比較簡單（它不需要象從內存中交換一樣，無須對物理設備進行寫操作）。除了會使對物理設備及內存對映檔案的訪問速度降低外，頁麵丟棄策略冇有太多的副作用。如果策略得當，則所有進程的損失相同。\\n\\n每次核心交換後台進程都會嘗試去壓縮這些cache。\\n\\n它首先檢查mem_map頁麵數組中的頁麵塊看是否有可以從物理內存中丟棄出去的。當係統中的空閒頁麵數降低到一個危險水平時，核心後台交換進程頻繁進行交換，則檢查的頁麵塊一般比較大。檢查的方式為輪轉，每次試圖壓縮內存映象時，核心後台交換進程總是檢查不同的頁麵塊。這是眾所周知的clock演算法，每次在整個mem_map頁麵數組中對頁麵進行檢查。\\n\\n核心後台交換進程將檢查每個頁麵看是否已經被pagecache或者buffercache緩衝。讀者可能已經注意到共享頁麵不在被考慮丟棄的頁麵之列，這種頁麵不會同時出現在這兩種cache中。如果頁麵不在這兩者中任何一種之中時，它將檢查mem_map頁麵數組中的下一個頁麵。\\n\\n緩存在buffercache(或者頁麵中的緩衝被緩存)中的頁麵可以使緩衝分配和回收更加有效。內存壓縮代碼將力圖釋放在受檢頁麵中包含的緩衝區。\\n\\n如果頁麵中包含的所有緩衝區都被釋放，這個頁麵也將被釋放。如果受檢頁麵在Linux的pagecache中，則它會從pagecache中刪除並釋放。\\n\\n如果釋放出來了足夠的頁麵，核心交換後台進程將等待到下一次被喚醒。這些被釋放的頁麵都不是任何進程虛擬內存的一部分，這樣無須更新頁表。如果冇有足夠的緩衝頁麵丟棄則交換進程將試圖將一些共享頁麵交換出去。\\n\\n換出係統V內存頁麵\\n\\n係統V共享內存是一種用來在進程之間通過共享虛擬內存來實現進程通訊的機製。進程是如何共享內存將在IPC一章中詳細討論。現在隻需要說明係統V共享內存的任何區域都可以用一個shmid_ds數據結構來表示就足夠了。此結構包含一個指向vm_area的鏈表指針，vm_area是為每個共享此虛擬內存區域設計的結構。它們之間通過vm_next_shared和vm_prev_shared指針來連接。每個shmid_ds數據結構包含一個頁表入口，每個入口描敘物理頁麵與共享虛擬頁麵之間的對映關係。\\n\\n核心交換後台進程同樣使用clock演算法來將係統V共享內存頁麵交換出去。\\n\\n每次運行時，它要記得哪個共享虛擬內存區域的哪個頁麵是最後一個被交換出去的。兩個索引可以協助它完成這項工作，其一是一組shmid_ds數據結構的索引，另一個是係統V共享內存區域的頁表入口鏈表的索引。這能夠保證對係統V共享內存區域作出公平的選擇。\\n\\n由於對於給定的係統V共享虛擬內存的物理頁麵框號被儲存在所有共享此虛擬內存區域進程的頁表中，核心交換後台進程必須同時修改所有的頁表以表示頁麵不再在內存而在交換檔案中。對於每個要交換出去的共享頁麵，核心交換後台進程可以在每個共享進程的頁表中的頁表入口中找到它們(通過vm_area_struct數據結構)。如果對應此係統V共享內存的頁麵的進程頁表入口是有效的，它可以將其轉變成無效，這樣換出頁表入口和共享頁麵的用戶數將減一。換出係統V共享頁表入口的格式中包含一個對應於一組shmid_ds數據結構的索引以及一個對係統V共享內存區域的頁表入口索引。\\n\\n如果所有共享進程的頁表都被修改後此頁麵的記數為0則共享頁麵可以被寫到交換檔案中。同樣指向此係統V共享內存區域的shmid_ds數據結構鏈表中的頁表入口也被換出頁表入口代替。換出頁表入口雖然無效但是它包含一組打開的交換檔案的索引，同時還能找到換出頁麵在檔案中的偏移。當頁麵重新被帶入物理內存時，這些資訊十分有用。\\n\\n換出和丟棄頁麵\\n\\n交換後台進程依次檢查係統中的每個進程以確認誰最適合交換出去。\\n\\n比較好的候選者是那些可以被交換出去（有些是不可被交換出去的）並且隻有一個或者幾個頁麵在內存中的進程。隻有那些包含的數據無法檢索的頁麵纔會從物理內存中交換到係統交換檔案中去。\\n\\n可執行映象的許多內容都可以從映象檔案中讀出並且可以很容易重讀出來。例如，映象中的可執行指令不能被映象本身修改，所以決不會寫到交換檔案中去。這些頁麵直接丟棄就可以。當進程再次引用它們時，隻需要從可執行映象檔案中讀入內存即可。\\n\\n一旦確定了將要被交換出去的進程，交換後台進程將搜尋其整個虛擬內存區域以找到那些冇有共享或者加鎖的區域。\\n\\nLinux並不會將選中的進程的整個可交換頁麵都交換出去，它隻刪除一小部分頁麵。\\n\\n如果內存被加鎖則頁麵不能被交換或者丟棄。\\n\\nLinux交換演算法使用頁麵衰老演算法。每個頁麵有一個計數器來告訴核心交換後台進程這個頁麵是否值得交換出去（此計數器包含在mem_map_t結構中）。當頁麵冇有使用或者冇有找到時將會衰老；交換後台進程僅僅交換出那些老頁麵。預設操作是：當頁麵被首次分配時，其年齡初始值為3，每次引用其年齡將加3，最大值為20。每次核心交換後台進程運行它來使頁麵衰老-將年齡減1。這個預設操作可以改變並且由於這個原因它們被存儲在swap_control數據結構中。\\n\\n如果頁麵變老了(age=0)，則交換後台進程將進一步來處理它。dirty頁麵可以被交換出去。Linux在PTE中使用一個硬體相關位來描敘頁麵的這個特性（見圖3.2）。然而不是所有的dirty頁麵都有必要寫入到交換檔案中去。進程的每個虛擬內存區域可能有其自身的交換操作(由vm_area_struct結構中的vm_ops指針表示)，在交換時使用的是這些方法。否則，交換後台進程將在交換檔案中分配一個頁麵並將頁麵寫到設備上去。\\n\\n頁麵的頁表入口被標誌成無效但是它包含了頁麵在在交換檔案中位置的資訊，包括一個表示頁麵在交換檔案中位置的偏移值以及使用的是哪個交換檔案。但是不管使用的是哪種交換演算法，以前那個物理頁麵將被標誌成空閒並放入free_area中。Clean（或者notdirty）的頁麵可以丟棄同時放入free_area以備重新使用。\\n\\n如果有足夠的可交換進程頁麵被交換出去或丟棄，則交換後台進程將再次睡眠。下次它醒來時將考慮係統中的下一個進程。通過這種方法，交換後台進程一點一點地將每個進程的可交換或可丟棄物理頁麵收回知道係統再次處於平衡狀態。這比將整個進程交換出去要公平得多。\\n\\nTheSwapCache\\n\\n當將頁麵交換到交換檔案中時，Linux總是避免頁麵寫，除非必須這樣做。當頁麵已經被交換出內存但是當有進程再次訪問時又要將它重新調入內存。隻要頁麵在內存中冇有被寫過，則交換檔案中的拷貝是有效的。\\n\\nLinux使用swapcache來跟蹤這些頁麵。這個swapcache是一個頁表入口鏈表，每個對應於係統中的物理頁麵。這是一個對應於交換出頁麵的頁表入口並且描敘頁麵放置在哪個交換檔案中以及在交換檔案中的位置。如果swapcache入口為非0值，則表示在交換檔案中的這一頁冇有被修改。如果此頁被修改（或者寫入）。則其入口從swapcache中刪除。\\n\\n當Linux需要將一個物理頁麵交換到交換檔案時，它將檢查swapcache，如果對應此頁麵存在有效入口，則不必將這個頁麵寫到交換檔案中。這是因為自從上次從交換檔案中將其讀出來，內存中的這個頁麵還冇有被修改。\\n\\nswapcache中的入口是已換出頁麵的頁表入口。它們雖被標記為無效但是為Linux提供了頁麵在哪個交換檔案中以及檔案中的位置等資訊。\\n\\n頁麵的換入\\n\\n儲存在交換檔案中的dirty頁麵可能被再次使用到，例如，當應用程式向包含在已交換出物理頁麵上的虛擬內存區域寫入時。對不在物理內存中的虛擬內存頁麵的訪問將引發頁麵錯誤。由於處理器不能將此虛擬地址轉換成實體地址，處理器將通知操作係統。由於已被交換出去，此時描敘此頁麵的頁表入口被標記成無效。處理器不能處理這種虛擬地址到實體地址的轉換，所以它將控製傳遞給操作係統，同時通知操作係統頁麵錯誤的地址與原因。這些資訊的格式以及處理器如何將控製傳遞給操作係統與具體硬體有關。\\n\\n處理器相關頁麵錯誤處理代碼將定位描敘包含出錯虛擬地址對應的虛擬內存區域的vm_area_struct數據結構。它通過在此進程的vm_area_struct中查詢包含出錯虛擬地址的位置直到找到為止。這些代碼與時間關係重大，進程的vm_area_struct數據結構特意安排成使查詢操作時間更少。\\n\\n執行完這些處理器相關操作並且找到出錯虛擬地址的有效內存區域後，頁麵錯處理過程其餘部分和前麵類似。\\n\\n通用頁麵錯處理代碼為出錯虛擬地址尋找頁表入口。如果找到的頁表入口是一個已換出頁麵，Linux必須將其交換進入物理內存。已換出頁麵的頁表入口的格式與處理器類型有關，但是所有的處理器將這些頁麵標記成無效並把定位此頁麵的必要資訊放入頁表入口中。Linux利用這些資訊以便將頁麵交換進物理入內存。\\n\\n此時Linux知道出錯虛擬內存地址並且擁有一個包含頁麵位置資訊的頁表入口。vm_area_struct數據結構可能包含將此虛擬內存區域交換到物理內存中的子程式:swapin。如果對此虛擬內存區域存在swapin則Linux會使用它。這是已換出係統V共享內存頁麵的處理過程-因為已換出係統V共享頁麵和普通的已換出頁麵有少許不同。如果冇有swapin操作，這可能是Linux假定普通頁麵無須特殊處理。\\n\\n係統將分配物理頁麵並將已換出頁麵讀入。關於頁麵在交換檔案中位置資訊從頁表入口中取出。\\n\\n如果引起頁麵錯誤的訪問不是寫操作則頁麵被保留在swapcache中並且它的頁表入口不再標記為可寫。如果頁麵隨後被寫入，則將產生另一個頁麵錯誤，這時頁麵被標記為dirty，同時其入口從swapcache中刪除。如果頁麵冇有被寫並且被要求重新換出，Linux可以免除這次寫，因為頁麵已經存在於交換檔案中。\\n\\n如果引起頁麵從交換檔案中讀出的操作是寫操作，這個頁麵將被從swapcache中刪除並且其頁表入口被標記成dirty且可寫。\\n\\n\"

}