虛拟記憶體

虛拟記憶體的三個能力：

它将主存看成磁盤上的位址空間的高速緩存，在主存中隻保持活動區域，并根據需要在磁盤和主存之間來回傳送資料。

為每個程序提供一緻位址空間

保護了每個程序的位址空間不被其他程序破壞

　　計算機的主存可以看做是一個由 M 個連續的位元組大小的單元組成的數組。每個位元組都有一個唯一的實體位址（Physical Address,PA）。第一個位元組的位址為 0，接下來的位址為 1，以此類推。CPU 通路記憶體的最簡單的方式是使用實體尋址（physical addressing）。

　　該圖例的上下文是一條加載指令，讀取從實體位址 4 處開始的 4 位元組字。CPU 在執行這條指令的時候，生成一個有效實體位址，通過記憶體總線，把這個實體位址傳遞給主存，主存取出從實體位址4處開始的 4 個位元組字，然後将它傳回給 CPU，CPU 将它存放在一個寄存器裡。

　　現在處理器采用的是一個程式虛拟尋址（virtual addressing）的尋址方式。CPU 通過生成一個虛拟位址（virtual address,VA）來通路主存，這個虛拟位址在被送到主存之前會先轉換成一個實體位址。将虛拟位址轉換成實體位址的任務叫做位址翻譯（address translation），位址翻譯需要 CPU 硬體和作業系統之間的配合。 CPU 晶片上叫做記憶體管理單元（Menory Management Unit, MMU）的專用硬體，利用存放在主存中的查詢表來動态翻譯虛拟位址，該表的内容由作業系統管理。

　　在一個帶虛拟記憶體的系統中，CPU 從一個有 N= 2的n次方個位址的位址空間中生成虛拟位址，這個位址空間就稱為虛拟位址空間：{0，1，2，3，…, N-1}。

　　一個位址空間的大小通常是由表示最大位址所需要的位數來描述的，比如，一個包含 N = 2 的 n 次方 個位址的虛拟位址空間就叫做一個 n 位位址空間，現代作業系統通常支援 32 位或者 64 位虛拟位址空間。

　　每個資料對象都有獨立的位址，每個位址選自不同的一個位址空間，主存中的每個位元組都有一個虛拟位址和一個實體位址。

　　從概念上來說，虛拟記憶體被組織成為一個由存放在磁盤上的 N 個連續的位元組大小的單元組成的數組，也就是位元組數組。每個位元組都有一個唯一的虛拟位址作為數組的索引。磁盤上活動的數組内容被緩存在主存中。在存儲器結構中，較低層次上的磁盤的資料被分割成塊，這些塊作為和較高層次的主存之間的傳輸單元。

　　虛拟記憶體（VM）系統将虛拟記憶體分割成稱為虛拟頁（Virtual Page,VP）的大小固定的塊，每個虛拟頁的大小為 P = 2 的 p 次方 位元組。同樣的，實體記憶體被分割為實體頁（Physical Page,PP）,大小也為 P 位元組（實體頁也稱作頁幀（page frame））。

在任意時刻，虛拟頁面的集合都分為三個不相交的子集：

未配置設定的，VM 系統還未配置設定（或者建立）的頁，未配置設定的頁沒有任何資料和它們關聯，是以不占用任何記憶體空間。

緩存的，目前已緩存在實體記憶體中的已配置設定頁。

未緩存的，未緩存在實體記憶體中的已配置設定頁。

　　上圖展示了在一個有 8 個虛拟記憶體的虛拟記憶體中，虛拟頁 0 和 3 還沒有被配置設定，是以在磁盤上不存在。虛拟頁 1，4，6 被緩存在實體記憶體中。虛拟頁 2，5，7 已經被配置設定了，但是目前并沒有緩存在主存中。

　　SRAM緩存：位于CPU和主存之間的 L1, L2 和 L3高速緩存（cache）

　　DRAM緩存：來表示虛拟記憶體系統中的緩存，也就是主存。

　　在存儲器層次結構中， DRAM 比 SRAM 慢個大約 10x 倍，磁盤比 DRAM 慢大約 10, 000x 倍。是以 DRAM 緩存的不命中比 SRAM 緩存中的不命中要昂貴的多，因為 DRAM 緩存不命中需要和磁盤傳送資料，而 SRAM 緩存不命中是和 DRAM 傳送資料。

頁表

　　頁表存放在實體記憶體中，将虛拟頁映射到實體頁。每次位址翻譯（MMU）硬體将一個虛拟位址轉換成實體位址時都會讀取頁表。

　　虛拟記憶體系統必須有某種方法來判定一個虛拟也是否緩存在 DRAM 的某個地方。如果命中緩存，那麼虛拟記憶體系統還必須确認這個虛拟頁存在哪個實體頁中。如果沒有命中緩存，那麼虛拟記憶體系統必須判斷虛拟頁存放在磁盤的哪個位置，在實體記憶體中選擇一個犧牲頁，并将虛拟頁從磁盤複制到 DRAM，替換這個犧牲頁。

　　頁表就是一個頁表條目（Page Table Entry,PTE）的數組，頁表條目也可以緩存，像其他資料一樣。虛拟位址空間中的每個頁在頁表中都有一個 PTE。在這裡我們假設每個 PTE 是由一個有效位（Valid bit）和一個 n 位位址字段組成的。有效位表明了該虛拟頁目前是否被緩存在 DRAM 中。如果有效位為 1，那麼位址字段就表示 DRAM 中相應的實體頁的起始位置，這個實體頁緩存了該虛拟頁。如果有效位為 0，那麼一個 null 位址表示這個虛拟頁還未被配置設定，否則對應的這個位址就指向該虛拟頁在磁盤上的起始位置。

　　上圖所示中一共有 8 個虛拟頁和 4 個實體頁的頁表，4 個虛拟頁 VP1, VP2, VP4, VP7 目前被緩存在 DRAM 中，VP0 和 VP5 還未被配置設定，而剩下的 VP3 和 VP6 已經被配置設定了，但是目前未被緩存。

頁命中

　　CPU要讀取VP2中的虛拟記憶體中的一個字時，位址翻譯硬體将虛拟位址作為一個索引來定位到 PTE2, 并從主存中讀取它。因為 PTE2 設定了有效位，是以 VP2 是緩存在主存中的，是以位址翻譯硬體使用 PTE 中的實體記憶體位址構造出這個字的實體位址。

缺頁

　　在虛拟記憶體中，DRAM緩存不命中稱為缺頁（page fault）。CPU 引用了 VP3 中的一個字， VP3 并未緩存在 DRAM 中。位址翻譯硬體從記憶體中讀取 PTE3, 從有效位判斷出 VP3 未被緩存，并且觸發了一個缺頁異常。缺頁異常會調用核心的缺頁異常處理程式，該程式會選擇一個犧牲頁。

　　接下來，核心程式從磁盤指派 VP3 到記憶體中的 PP3并更新 PTE3。随後傳回使用者程序。當異常處理程式傳回時，它會重新開機執行導緻缺頁的指令，該指令會将導緻缺頁的虛拟位址重新發送到位址翻譯硬體。

　　配置設定内面

　　多個虛拟頁面可以映射到同一個共享的實體頁面上。

　　按需頁面排程和獨立的虛拟位址空間的結合，讓虛拟記憶體簡化了連結和加載，代碼和資料共享，以及應用程式的記憶體配置設定。

簡化連結。獨立的位址空間允許每個程序的記憶體映像使用相同的基本格式，而不管代碼和資料實際存放在實體記憶體的何處。

簡化加載。虛拟記憶體使得容易向記憶體中加載可執行檔案和共享對象檔案。将一組連續的虛拟頁面映射到任意一個檔案中的任意位置的表示法稱作記憶體映射（memory mapping）。Linux 提供了一個 nmap 的系統調用，允許應用程式自己做記憶體映射。

簡化共享。獨立位址空間為作業系統提供了一個管理使用者程序和作業系統自身之間共享的一緻機制。一般情況下，每個程序都有自己私有的代碼、資料、堆棧。這些内容不與其他程序共享。在這種情況下，作業系統建立頁表，将相應的虛拟頁映射到不連續的實體頁面。

簡化記憶體配置設定。虛拟記憶體向使用者程序提供一個簡單的配置設定額外記憶體的機制。當一個使用者程式要求額外的堆空間時候（malloc），作業系統配置設定 k個适當的連續的虛拟記憶體頁面，并且将他們映射到實體記憶體的中的 k 個任意頁面，作業系統沒有必要配置設定 k個連續的實體記憶體頁面。

　　每次CPU生成一個位址時，位址翻譯硬體都會讀一個PTE ，通過在PTE上添加一些額外的控制位來控制對一個虛拟頁面内容的通路。

　　SUP位表示程序是否必須運作在超級用也就是核心模式下才能通路該頁，如果有指令違反了這些控制條件，那麼CPU會觸發一個一般保護故障（段錯誤），将控制傳遞給核心中的異常處理程式。

　　位址翻譯就是将N個元素的虛拟位址空間中的元素和M個元素的實體位址空間中的元素映射。MMU利用VPN選擇PTE，将頁表條目中的實體号（PPN）和虛拟位址中的VPO串聯起來就得到相應的實體位址（實體位址和虛拟位址中的頁面大小相同）。

　　頁面命中（全部由硬體來處理的）的場景，CPU 硬體的執行步驟：

處理器生成一個虛拟位址，并把它傳送給 MMU。

MMU 生成 PTE位址，并從高速緩存/主存中請求這個 PTE 。

高速緩存/主存向 MMU 傳回 PTE。

MMU構造實體位址，并把它傳送給高速緩存/主存。

高速緩存/主存傳回所請求的資料字給處理器。

　　缺頁，CPU硬體執行步驟

處理器 生成一個虛拟位址，并把它傳送給 MMU。

MMU 生成 PTE 位址，并從高速緩存/主存中請求這個 PTE 。

PTE 中的有效控制位為0 ，是以 MMU 觸發了一次異常，傳遞 CPU 中的控制到作業系統核心中的缺頁異常處理程式。

缺頁處理程式确定出實體記憶體中的犧牲頁，如果這個頁面已經被修改了，則把它換出到磁盤。

缺頁處理程式調入新的頁面，并更新記憶體中的 PTE。

缺頁處理程式傳回原來的程序，再次執行導緻缺頁的指令， CPU 将引起缺頁的虛拟位址重新發送給 MMU ，因為虛拟頁面現在存在主存中，是以會命中，主存将請求字傳回給處理器。

結合高速緩存和虛拟記憶體

　　位址翻譯發生在查找緩存之前

用TLB加速位址翻譯

　　在MMU中包含了一個關于PTE的小緩存，稱為翻譯後備緩沖器（TLB）。它是個小的虛拟位址的緩存，每行是單個PTE塊，用于組選擇和行比對的索引和标記字段是從虛拟位址中的虛拟頁号提取出來的，如果TLB有T=2^t個組，那麼TLB索引（TLBI）是由VPN的t個最低位組成，而TLB标記（TLBT）是由VPN的剩餘位組成。所有的位址翻譯步驟是在MMU中完成的

CPU産生一個虛拟位址

MMU 從 TLB 中取出對應的 PTE 。

MMU 将這個虛拟位址翻譯成一個實體位址，并且将它發送到高速緩存/主存。

高速緩存/主存将所請求的資料字傳回 CPU。

　　TLB不命中時，MMU從L1緩存中取PTE。

多級頁表

　　多級頁表相當于樹結構，它從兩個方面減少了記憶體要求：

如果一級頁表中的一個PTE是空的，相應的二級頁表就不會存在

隻有一級頁表才需要總是在主存中。虛拟記憶體系統可以在需要時建立、頁面調入或調出二級頁表。

　　以32位系統4GB位址空間為例，我們将實體記憶體分割為虛拟的頁面，每個頁面儲存4KB大小的内容，這樣我們總共需要1048576個頁面，才能瓜分所有的4GB空間。那麼我們的頁表要能夠完成所有實體記憶體的映射，就必須要1048576個頁表項，由于每個頁表項占用4B的空間，那麼我們這個頁表就需要占用4194304B（4M）的記憶體空間，每個程序都有這樣的一個4M的頁表占用着記憶體空間，才能完成映射。

　　加入分級的思想以後，每一級的頁表就都隻有4KB的大小，數量也有原來的1048576變成了1024個，兩級相乘其實表示的數量還是原來那麼多。上圖所示，一級頁表每條PTE負責映射二級頁表1024個PTE項，二級頁表的每個PTE在映射虛拟存儲器中4KB大小的位置。也就是說一級頁表每條PTE負責映射一塊4M大小的空間，而一級頁表總共有1024個頁表項，也就能用來映射完成所有實體記憶體空間。這樣做的好處是，如果一級頁表中有未被配置設定的項目，那麼這條PTE直接設定成null，不指向任何二級清單，也就不再占用空間。還有一個好處是不是所有的二級清單都需要常駐記憶體，每個程序隻需要在記憶體中建立一級頁表（4kb）大小，二級清單按需要的時候建立調入，這樣就更省了。

　　虛拟位址被劃分為k個vpn和一個vpo，每個vpn i都是一個到第i級頁表的索引。

　　核心虛拟記憶體的某些區域被映射到所有程序的共享實體頁面，如：每個程序共享核心的代碼和全局資料結構。虛拟位址空間有間隙。

　　核心為系統中的沒給程序單獨維護一個單獨的任務結構task_struct，包含核心運作程序時所需要的資訊（PID，使用者棧指針，可執行目标檔案的名字，程式計數器）。這個結構中有一個mm字段，指向的是mm_struct中的pgd和mmap，其中pgd是一級頁表的基位址，mmap指向的是一個vm_area_structs的連結清單，每個該連結清單中的一個元素描述的是目前虛拟位址空間的一個段（text、data、bss等），當核心運作該程序的時候CR3寄存器就被放入了pgd。

Linux缺頁異常

通路位址是否合法：缺頁處理程式隻需要将這個位址A與vm_area_struct連結清單中的每個元素的vm_start和vm_end資料（段的起始和結束位址）比較，如果都沒有的話，表示該位址不在相應的段中。就是一個段錯誤。

保護異常：vm_area_struct中的vm_prot結構是包含了所有頁面的讀寫權限，是以當對隻有讀權限的文本内容寫入資料的時候，就會引發保護異常。

正常缺頁。也就是相應的頁面不在實體記憶體的時候，缺頁程式就會鎖定一個犧牲頁面，将它的内容與實際需要的内容交換過來，當缺頁程式傳回的時候就可以正常的通路了。

　　記憶體映射是将一個虛拟區域與磁盤上的對象關聯起來，以初始化這個虛拟區域的内容，這個過程稱為記憶體映射。虛拟記憶體區域可以映射到兩種類型中的一種：

Linux檔案系統中的普通檔案：一個區域可以映射到普通磁盤檔案的連續部分，如一個可執行目标檔案。檔案區被分成頁片大小，每一頁包含虛拟頁面的初始内容，因為按需進行頁面排程，是以虛拟頁面沒有實際交換進入實體記憶體，直到CPU第一次引用該頁面（即發射一個虛拟位址，落在位址空間這個頁面範圍之内），如果區域比檔案大，就用0來填充剩下的部分。

匿名檔案：一個區域可以映射到一個匿名檔案，匿名檔案由核心建立，包含的全是二進制0，cpu第一次引用這樣一個區域的虛拟頁面時，核心就在屋裡記憶體中找到一個合适的頁犧牲，如果這個頁面被修改過，就将這個頁面換出來，用二進制0覆寫犧牲頁面并修改頁表。這個頁面标記為是駐留記憶體的，磁盤和記憶體之間并沒有實際傳輸資料，是以有時也稱請求二進制0的頁。

共享對象

　　一個對象被映射到虛拟存儲器的一個區域，這個區域要麼是共享對象，要麼是私有對象。如果一個程序A将一個共享對象映射到了它的虛拟存儲器中，那麼對于也把這個共享對象映射了的其他程序而言，程序A對共享對象的任何讀寫操作都是可見的，而這些變化也會反映在磁盤原始對象中。

　　因為每個對象有唯一的檔案名，核心可以判定程序1已經映射了這個對象，可以使用程序2中的頁表條目指向相應的實體頁面。即使共享對象被映射到了多個共享區域，實體記憶體也隻需要儲存一個共享對象的一個副本。

私有對象

　　私有對象和共享對象聲明周期方式基本相同，在實體記憶體中隻儲存私有對象的資料副本。對于每個映射私有對象的程序，相應區域的頁表條目都被标記為隻讀，并且這個區域結構被标記為私有的寫時複制，隻要沒有程序試圖寫自己的私有區域，他們可以繼續共享實體記憶體中的對象副本，隻要有一個程序試圖寫私有區域的某個頁面，會觸發寫保護故障，此時在記憶體中建立這個頁面的副本，更新頁表條目指向新的副本，回複頁面的可寫權限。

再看fork

　　當目前程序調用fork函數的時候，核心為新程序建立各種資料結構，并配置設定PID。為了給新程序建立一個虛拟存儲器，它建立的目前程序的mm_struct、區域結構和頁表的一個拷貝，核心為兩個程序的每個頁表标記為隻讀，并将每個區域标記為私有的寫時拷貝。

　　當fork函數傳回的時候，新程序的虛拟存儲器和目前程序的虛拟存儲器剛好相同。任何一個程序進行寫操作的時候，才會建立新的頁面。

再看execv函數

删除已存在的使用者區域：删除目前已存在的使用者資料結構。

映射私有區域：所有的.text、.data、.bss區域都是新建立的，這些區域是私有的、寫時拷貝。.bss是匿名檔案區域（二進制請求0），大小包含在a.out中；棧、堆也都是二進制請求0的，長度為0。

映射共享區域：這些共享區域是動态連結到程式然後映射到虛拟位址空間的共享區域。

設定程式計數器：設定目前程序的上下文計數器，并指向.text入口

使用mmap的使用者級記憶體映射

　　該函數要求核心建立一個新的虛拟記憶體區域，位址最好是從start開始的一個區域，并将描述符fd指定的對象是一個連續的片（chunk）映射到這個新區域，連續對象大小為length位元組，start僅是一個暗示，通常指定為NULL。

内部碎片：已配置設定塊比有效載荷大，比如配置設定器可能增加塊大小滿足對齊限制條件

外部碎片：空閑記憶體合起來滿足一個請求配置設定，但是沒有單獨的一個空閑塊足夠大可以來處理這個請求發生。

隐式空閑連結清單

　　配置設定器需要一個資料結構來差別塊邊界，以及差別已配置設定塊和空閑塊，大多數配置設定器将這些資訊嵌入塊本身。

　　頭部後面是調用malloc時請求的有效載荷，有效載荷後面的填充塊大小任意，填充的原因可能是對付外部碎片也可能是滿足對其要求。

　　這個連結清單（大小/是否配置設定）是通過頭部中的大小字段 隐含連接配接着的（頭部+大小=下一塊位置），配置設定器可以周遊所有的塊，在遇到結束位（0/1）處停止。即使是要求配置設定一個資料塊，也要有（8/0）一個頭部，兩個字來完成。

　　稱這種結構為隐式連結清單，因為空閑塊是通過頭部中的大小字段隐含連接配接着的。配置設定器可以周遊堆中所有的塊進而周遊空閑塊。優點：簡單；缺點：放置配置設定塊，要對空閑連結清單搜尋。最重要的是系統對其要求和配置設定器對塊格式的選擇會對配置設定器上的最小塊大小有強制要求。

放置已配置設定的塊

首次适配：從頭搜尋，遇到第一個合适的塊就停止；

下次适配：從頭搜尋，遇到下一個合适的塊停止；

最佳适配：全部搜尋，選擇合适的塊停止。

分割空閑塊

　　适配到合适的空閑塊，配置設定器将空閑塊分割成兩個部分，一個是配置設定塊，一個是新的空閑塊

合并空閑塊

　　當釋放已配置設定塊時，其他空閑塊可能與剛釋放的空閑塊相鄰，這些臨界快引起假碎片現象。

　　雖然釋放了兩個3位元組大小的資料空間，而且空閑的空間相鄰，但是就是無法再配置設定4位元組的空間了，這時候就需要進行一般合并：合并的政策是立即合并和推遲合并，我們可能不立即推遲合并，如果有空間直接合并不好嗎？有時候的确還真不好，如果我們馬上合并上圖的空間後又申請3位元組的塊，那麼就會開始分割，釋放以後立即合并的話，又将是一個合并分割的過程，這樣的話推遲合并就有好處了。需要的時候再合并，就不會産生抖動了。

帶邊界标記的合并

　　考慮四種情況

目前塊前後都是已配置設定

目前塊前配置設定後空閑

目前塊前空閑後配置設定

目前塊前後都是空閑

顯示空閑連結清單

　　程式不需要一個空閑塊的主體，是以實作這個資料結構的指針可以存放這些空閑塊的主體裡。使用顯示連結清單，首次配置設定的時間從塊總數的時間減少到了空閑塊數量的線性時間。但是顯示空閑連結清單的缺點是空閑塊必須足夠大，以包含所有需要的指針，以及頭部和腳部，導緻了更大的最小塊，也提高了内部碎片的成都。

分離的空閑連結清單

　　維護多個空閑連結清單，每個連結清單中的塊有大緻相等的大小。配置設定器維護空閑連結清單數組，每個大小類（空閑連結清單的大小）一個空閑連結清單按照大小的升序排列。配置設定一個大小為n的塊時，他就搜尋相應的空閑連結清單。如果不能找到合适的塊相比對就搜尋下一個大小的空閑連結清單。

簡單分離存儲：每個空閑連結清單包含大小相等的塊，配置設定時檢查空閑連結清單，如果非空就把第一塊空閑連結清單分出去，不分割；如果為空，配置設定器就像作業系統申請固定大小的額外存儲片，将此片分成大小相等的塊，釋放時，簡單的把此塊插入到空閑連結清單的前部。因為不需要合并，已配置設定的塊不需要已配置設定/空閑标記，不需要腳部。空閑不會被分割，會造成内部碎片，不合并空閑塊，會造成外部碎片。

分離适配：配置設定器維護空閑連結清單數組，被組成連結清單類型是顯示或隐式連結清單。配置設定時，對空閑連結清單做首次适配，如果找到合适的塊就将其分割，将剩餘的空閑連結清單插入到合适的連結清單中，如果找不到合适的塊，就搜尋更大的空閑連結清單，如果空閑連結清單中沒有合适的塊，向作業系統申請額外的堆記憶體，從新的堆記憶體中配置設定一個合适的塊，将剩餘的插入到适當的大小類中。釋放一個塊執行合并，将結果插入到響應的空閑連結清單中。malloc就采用這種方法。

夥伴系統：分離适配的特例，每個大小類都是2的幂。假設一個堆大小2^m個字。每個塊大小2^k空閑連結清單。0<=k<=m；最開始隻有一個2^m個字的空閑塊。配置設定大小2^k的空閑塊，找到第一個可用的大小為2^j空閑塊k<=j<=m，如果j==k，則完成。否則遞歸二分這個塊直到j==k，分割時剩下的半塊（叫作夥伴）被置在相應的空閑連結清單中，釋放大小為2^j的塊，繼續合并空閑塊的夥伴，遇到一個已配置設定的夥伴時，停止合并。一個塊的位址和他夥伴的位址隻有一位不同。有點是快速搜尋或合并，缺點是大小我2的幂次方可能導緻顯著内部碎片。

　　系統記憶體中的每個實體記憶體頁（頁幀），都對應于一個struct page執行個體, 每個記憶體域都關聯了一個struct zone的執行個體，其中儲存了用于管理夥伴資料的主要數數組

　　階是夥伴系統中一個非常重要的術語. 它描述了記憶體配置設定的數量機關. 記憶體塊的長度是2^0,order , 其中order的範圍從0到MAX_ORDER

　　zone->free_area[MAX_ORDER]數組中階作為各個元素的索引, 用于指定對應連結清單中的連續記憶體區包含多少個頁幀.

數組中第0個元素的階為0, 它的free_list連結清單域指向具有包含區為單頁(2^0 = 1)的記憶體頁面連結清單

數組中第1個元素的free_list域管理的記憶體區為兩頁(2^1 = 2)

第3個管理的記憶體區為4頁, 依次類推，直到 2^MAXORDER-1個頁面大小的塊，MAXORDER預設值為11

　　垃圾收集是一種很有用的方法，當使用了malloc配置設定了空間卻忘記了釋放，就會造成記憶體的極大浪費。垃圾收集就是使用特殊的方法，定期回收這部分不使用或者無效的空間。

　　從根節點出發到達p有路徑時，說p是可達的，任意時刻不可達對應于垃圾是不能再次利用的，垃圾器的作用是維護可達視圖的某種表示，釋放不可達結點将他們傳回給空閑連結清單，定期回收它們。