第9章 虛拟存儲器
9.1 實體和虛拟
1.一個使用實體尋址的系統：當CPU執行這條加載指令時，它會産生一個有效的實體位址，通過存儲器總線，把它傳遞給主存。主存取出從實體位址4處開始的4位元組的字，并将它傳回給CPU，CPU會将它存放在一個寄存器裡。
2.一個使用虛拟尋址的系統：使用虛拟尋址時，CPU通過生成一個虛拟位址來通路主存，這個虛拟位址在被送到存儲器之前先轉換成适當的實體位址。
3.位址翻譯：将一個虛拟位址轉換為實體位址的任務。
4.存儲器管理單元（MMU）:利用存放在主存中的查詢表來動态翻譯位址。
9.2 位址空間
1.位址空間：一個非負整數位址的有序集合：
{0， 1， 2， 3，...} 2.線性位址空間：位址空間的整數是連續的。
3.虛拟位址空間：在一個帶虛拟存儲器的系統中，CPU從一個N = 2n {0, 1, 2, 3, …, N-1}
4.實體位址空間：{0, 1, 2, 3, …, M-1}
5.虛拟存儲器的基本思想：允許每個資料對象有多個獨立位址，其中每個位址都選自一個不同的位址空間。
6.主存中的每個位元組都有一個選自虛拟位址空間虛拟位址和一個選自實體位址空間的實體位址。
9.3 虛拟存儲器作為緩存的工具
1.虛拟存儲器（VM）被組織為一個有存放在磁盤上的N個連續的位元組大小的單元組成的數組。每個虛拟頁的大小為P = 2p（2的p次方）。實體存儲器杯分割為實體頁（PP），大小也為P位元組（實體頁也稱為頁幀）
2.任意時刻，虛拟頁面的集合都分成3個不相交的子集：
（1）未配置設定的：VM系統還有未配置設定（或建立）的頁；不占任何磁盤空間
（2）緩存的：目前緩存在實體存儲器中的已配置設定頁。
（3）未緩存的：沒有緩存在實體存儲器中的已配置設定頁。
3.DRAM緩存的組織結構：
①SRAM緩存：表示位于CPU和主存之間的L1、L2和L3高速緩存。
②DRAM緩存：表示虛拟存儲器系統的緩存，它在主存中緩存虛拟頁。
4.頁表：
頁表就是一個頁表條目（PTE）的數組。每個PTE由一個有效位和一個n位位址字段組成的。有效位表明了該虛拟頁是否緩存在DRAM中。（DRAM是全相連的，任意實體頁都可以包含任意虛拟頁）。
5.頁命中：當CPU讀取含在VP2中的虛拟存儲器的一個字時，VP2是被緩存在DRAM中的，位址翻譯硬體将虛拟位址作為一個索引來定位PTE2，并從存儲器中讀取它。因為設定了有效位，那麼位址翻譯硬體就将知道VP2是緩存在存儲器中的了。是以它使用PTE中的實體存儲器位址構造出這個字的實體位址。
6.缺頁：DRAM的緩存不命中。
①交換或頁面排程：在磁盤和存儲器之間傳送頁的活動。
②按需頁面排程：頁從磁盤換入（或者頁面調入）DRAM和從DRAM換出（或者頁面調出）磁盤。一直等待，直到最後時刻，也就是有不命中發生時，才換入頁面的這種政策。
VM缺頁（之前）：對VP3中的字的引用不命中，進而觸發了缺頁
③VM缺頁（之後）：缺頁處理程式選擇VP4作為犧牲頁，并從磁盤上用VP3的拷貝取代它。在缺頁處理程式重新啟動導緻缺頁的指令之後，該指令将從存儲器中正常地讀取字，而不會再産生異常。
7.颠簸：工作集的大小超出實體存儲器的大小。
9.4 虛拟存儲器作為存儲器管理的工具
1.VM如何為程序提供獨立的位址空間。作業系統為系統中的每個程序都維護一個獨立的頁表：（多虛拟頁面可以映射到同一個共享實體頁面上）
在這個示例中，程序i的頁表将VP1映射到PP2，VP2映射到PP7.相似的，程序j的頁表将VP1映射到PP7，VP2映射到PP 10.
2.VM簡化了連結和加載、代碼和資料共享，以及應用程式的存儲器配置設定。
9.5虛拟存儲器作為存儲器保護的工具
1.SUP位表示程序是否必須運作在核心（超級使用者）模式下才能通路該頁。運作在核心模式中的程序可以通路任何頁面，但是運作在使用者模式的程序隻允許通路那些SUP為0的頁面。
2.如上圖：程序i運作在使用者模式下，那麼它有讀VP 0和VP 1 的權限。然而，不允許它通路VP 2.
9.6 位址翻譯
1.頁面命中： CPU硬體執行的步驟
第一步：處理器生成一個虛拟位址，并把它傳送給MMU。
第二步：MMU生成PTE位址，并從高速緩存/主存請求得到它。
第三步：高速緩存/主存向MMU傳回PTE.
第四步；MMU構造實體位址，并把它傳送給高速緩存/主存。
第五步：高速緩存/主存傳回所請求的資料字給處理器。 2.實體缺頁：要求硬體和作業系統核心完成
第一步：處理器生成一個虛拟位址，并把它傳送給MMU。
第二步：MMU生成PTE位址，并從高速緩存/主存請求得到它。
第三步：高速緩存/主存向MMU傳回PTE.
第四步：PTE中的有效位是0，是以MMU觸發了一次異常，傳遞CPU中的控制到作業系統核心中的缺頁異常處理程式。
第五步：缺頁處理程式确定出實體存儲器中的犧牲頁，如果這個頁已經被修改了，則把它換出到磁盤。
第六步：缺頁處理程式頁面調入新的頁面，并更新存儲器中的PTE.
第七步：缺頁處理程式傳回到原來的程序，再次執行導緻缺頁的指令。CPU将引起缺頁的虛拟位址重新發送給MMU. 3.TLB(翻譯後備緩沖器):有T = 2t(2的t次方)，那麼TLB索引（TLBI）是由VPN的t個最低位組成的，而TLB标記（TLBT）是由VPN中剩餘的位組成的。
4.TLB命中：
第一步：CPU産生一個虛拟位址
第二步和第三步：MMU從TLB中取出相應的PTE.
第四步：MMU将這個虛拟位址翻譯成一個實體位址，并且将它發送到高速緩存/主存。
第五步：高速緩存/主存将所請求的資料字傳回給CPU. 當TLB不命中時，MMU必須從L1緩存中取出相應的PTE(新取出的PTE放在TLB中，可能會覆寫一個已經存在的條目)。
5.多級頁表：
一級頁表中的每個PTE負責映射虛拟位址中的一個4MB的片，這裡的每一片都是由1024個連續的頁面組成的。比如，PTE0映射第一片，PTE1映射接下來的一片，以此類推。如果位址空間是4GB，1024個PTE已經足夠覆寫真整個空間。
6.綜合：端到端的位址翻譯： A ---> B ---> C
假設：
存儲器是按位元組尋址的。
存儲器通路是針對1位元組的字的。
虛拟位址是14位長的（n = 14）.
實體位址是12位長的（m = 12）。
頁面大小是64位元組（P = 64）。 9.8 存儲器映射
1.定義：Linux通過将一個虛拟存儲器區域與一個磁盤上對象關聯起來，已初始化這個虛拟存儲器區域的内容。
2.虛拟存儲器區域可以映射到兩種類型的對象中的一種：
①Unix檔案系統中的普通檔案：一個區域可以映射到一個普通磁盤檔案的連續部分。
②匿名檔案：一個區域也可以映射到一個匿名檔案，匿名檔案是由核心建立的，包含的全是二進制零。由于磁盤和存儲器之間并沒有實際的資料傳送，映射到匿名檔案的區域中的頁面有時也叫二進制零的頁。
3.共享對象
一個對象可以被映射到虛拟存儲器的一個區域，要麼作為共享對象，要麼作為私有對象。如果一個程序将一個共享對象映射到它的虛拟位址空間的一個區域内，那麼這個程序對這個區域的任何操作，對于那些也把這個共享對象映射它們虛拟存儲器的其他程序而言是不可見的。而且，這些變化也會反映在磁盤上的原始對象中。
另一方面，對一個映射到私有對象的區域做的改變，對于其他程序來說是不可見的，并且程序歲這個區域所做的任何操作都不會反映在磁盤的對象中。一個映射到共享對象到的虛拟存儲器區域也叫共享區域。
A.程序1将一個對象映射到它的虛拟存儲器的一個區域中;
B.程序2映射到同一個共享對象之後;
4.一個私有的寫時拷貝對象：
A.兩個程序都映射了私有的寫時拷貝對象之後：
如A展示了一種請況，其中兩個程序将一個私有對象映射到他們虛拟存儲器的不同區域，但是共享這個對象同一個實體拷貝。對于每個映射私有對象的程序，相應私有區域的頁表條目都被标記為隻讀，并且區域結構被标記為私有的寫時拷貝。隻要沒有程序師徒寫它自己的私有區域，它們就可以繼續共享實體存儲器中對象的一個單獨拷貝。然而，隻要有一個程序試圖寫私有區域内的某個頁面，那麼這個寫操作就會觸發一個保護故障。
B.程序2寫了私有區域的一個頁之後：
當故障處理程式注意到保護異常是由于程序試圖寫私有的寫時拷貝區域中的一個頁面而引起的，它會在實體存儲器中建立這個頁面的一個新拷貝，更新頁表條目指向這個新的拷貝，然後恢複這個頁面的可寫權限，如B圖。當故障處理程式傳回時，CPU重新執行這個寫操作，現在就在新建立的頁面上這個寫操作就可以正常執行了。
5.execve函數：
假設運作在目前程序中的程式：
Execve( “ a.out ”, NULL, NULL);
加載并運作a.out需要以下幾個步驟：
删除已存在的使用者區域。
映射私有區域。為新程式的文本、資料、bss和stack區域建立新的結構。
映射共享區域。
設定程式計數器。 6.使用Mmap函數的使用者級存儲器映射：
Mmap函數要求核心建立一個新的虛拟存儲器區域，最好是從位址start開始的一個區域，并将檔案描述fd指定的對象的一個連續的片映射到這個新的區域。連續的對象片的大小為length位元組，從距檔案開始處偏移量為offset位元組的地方開始。
7.munmap函數删除虛拟存儲器的區域：
#include <unistd.h>
#include <sys/mman.h>
int munmap( void *start, size_t length); Munmap函數删除從虛拟位址start開始的，由接下來的length位元組組成的區域。接下來對已删除區域的引用會導緻段錯誤。
9.9 動态存儲配置設定
1.配置設定器的分類：
①顯式配置設定器：要求應用顯式地釋放任何已配置設定的塊。C程式通過調用malloc函數來配置設定一個塊，并通過調用free函數來釋放一個塊。
②隐式配置設定器：要求擴充卡檢測一個已配置設定塊何時不再被程式所使用，那麼就釋放這個塊。隐式配置設定器也叫垃圾收集器，而自動釋放未使用的已配置設定的塊的過程叫做垃收集。
2.Malloc和free函數：
#include <stdlib.h>
void *malloc(size_t size) ; Malloc函數傳回一個指針，指向大小為至少size位元組的存儲器塊，這個塊會為可能包含在這個塊内的任何資料對象類型做對齊。
下圖展示了Malloc和free函數是如何管理一個C程式的16字小的堆。每個方框代表一個4位元組的字。粗線标出的矩形對應于已配置設定塊（有陰影的）和空閑塊（無陰影的）。初始時，堆是有一個大小為16個字、雙字對齊的、空閑塊組成的。
a.程式請求一個4字的塊。malloc的響應是：從空閑塊的前部切出一個4字的塊，并傳回一個指向這個塊的第一字的指針。
b.程式請求一個5字的塊。malloc的響應是：從空閑塊的前部配置設定一個6字的塊。在本例中，malloc在塊裡填充了一個額外的字，是為了保持空閑塊是雙字邊界對齊的。
c.程式請求一個6字的塊。而malloc就從空閑塊的前部切出一個6字的塊。
d.程式釋放在圖b中6字的塊。注意：在調用free傳回之後，指針p2仍然指向被釋放了的塊。應有責任在它被一個新的malloc調用重新初始化之前不再使用p2.
e.程式請求一個2字的塊。在這種情況下，malloc配置設定在前一步中被釋放了的塊一部分，并傳回一個指向這個新塊的指針。 3.為什麼要使用動态存儲器配置設定：經常直到程式實際運作時，它們才知道某些資料結構的大小。
4.配置設定器的要求和目标
A.要求：
處理任意請求序列。一個應用可以有任意的配置設定請求和釋放請求序列，隻要滿足限制條件：每個釋放請求必須對應于一個目前已配置設定的順序，這個塊是由一個以前的配置設定器請求獲得的。
立即響應請求。不允許配置設定器為了提高性能重新排列或者緩沖請求。
隻使用堆：為了使配置設定器可拓展。
對齊塊（對齊要求）：可以儲存任何類型的資料對象。
不修改已配置設定的塊 B.目标：
①最大吞吐率:每個機關時間裡完成的請求數。合理性能是指一個婦配置設定請求的最糟運作時間與空閑塊的數量呈線性關系，而一個釋放請求的運作時間是個常數。
②最大化存儲器使用率：給定n個配置設定和釋放請求的某種順序：
R0， R1， R2， .... , RN 如果一個應用程式的一個p位元組的塊，那麼得到的已配置設定的有效載荷是p位元組。在請求RK完成之後，聚集有效載荷表示為PK,為目前已配置設定的塊的有效載荷之和，而HK表示堆的目前的大小。
UK = maxi<k Pi / Hk 配置設定器的目的是在整個序列中使峰值使用率Un-1最大化。
5.碎片分類：
内部碎片：在一個已配置設定塊比有效載荷大時發生的。
内部碎片的量化 = (已配置設定塊大小 - 有效載荷大小).在任意時刻，内部碎片數量隻取決于以前請求的模式和配置設定器的實作方式。
外部碎片：當空閑存儲器合計起來足夠滿足一個配置設定請求，但是沒有一個單獨的空閑塊足夠大可以來處理這個請求是發生。
外部碎片比内部碎片的量化要困難的多，因為它不僅取決于以前的請求模式和配置設定器的實作，還取決于将來請求的模式。
6.隐式空閑連結清單：
（1）一個簡單的堆塊模式：
一個塊由一個字的頭部、有效載荷，以及可能的一些額外的填充組成的。頭部編碼了這個塊的大小（包括頭部和所有的填充），以及這個塊是已配置設定的還是空閑的。如果我們強加一個雙字的限制條件，那麼塊大小就總是8的倍數，且塊大小的最低位3位總是零。是以，我們隻需要存儲大小的29個高位，釋放剩餘的低3位來編碼其他資訊。
例如：假設我們有一個已配置設定的塊，大小為24（0x18）位元組，那麼它的頭部是：
0x00000018 | 0x1 = 0x00000019 若一個塊大小為40（0x28）位元組的空閑塊有如下頭部：
0x00000028 | 0x0 = 0x00000028 堆組織為一個連續的已配置設定塊和空閑塊的隊列：
7.帶邊界的标記的合并
（1）前面的與後面的塊都是已配置設定的
（2）前面的塊是已配置設定的，後面的塊空閑
（3）前面的塊空閑，後面的塊已配置設定
（4）後面的塊和前面的塊都空閑
當我們試圖在存儲器中合并目前的塊和後面的塊時，隻要在前面的塊是空閑的，才會需要用到它的腳部，如果我們把前面塊的已配置設定/空閑位存放在目前塊中多出來的低位中，那麼已配置設定的塊就不需要腳部了，這樣我們就可以把多出來的空間用作有效載荷。
8.顯式空閑連結清單
①先進先出（FLFO）：，維護連結清單，将新釋放的塊位置在連結清單的開始處。釋放一個塊可以在常數時間内完成，合并也是
②按照位址順序來維護連結清單，其中連結清單中每個塊的位址都小于它後繼的位址
③缺點：空閑塊必須足夠大，以包含所有需要的指針，以及頭部和可能的腳部。這就導緻了更小塊大小，也潛在地提高了内部碎片的程度。
9.分離的空閑連結清單
（1）簡單分離存儲：每個大小類的空閑連結清單包含大小相等的塊，每個塊的大小就是這個大小類中最大元素的大小。
（2）分離适配：
（3）夥伴系統：是分離适配的一種特例，其中每個大小類都是2的幂。基本的思路是假設一個堆的大小為2m個字，我們為每個塊大小2k維護一個分離空閑塊，其中:
0 ≤ k ≤ m 請求塊大小向上舍入到最接近的2 的幂。最開始，隻有一個大小為2m個字的空閑塊。
（4）主要優點：快速搜尋和快速合并
（5）主要缺點：要求塊大小為2的幂可能導緻顯著的内部碎片。
9.10垃圾回收
1.垃圾收集器：是一種動态存儲配置設定器，它自動釋放程式不再需要的已配置設定塊。自動回收堆存儲器的過程叫做垃圾收集。在一個支援垃圾收集的系統中，應用顯式配置設定堆塊，但是從不顯式地釋放它們。
2.垃圾收集器的基本知識：垃圾收集器将視為一張有向可達圖。下圖的節點被分成一組根節點和一組堆節點。每個堆節點對應于對中的一個已配置設定塊。
3.當存在一條任意根節點出發并到達p的有效路徑時，我們說節點p是可達的。不可達節點對應于垃圾，是不能被應用再次使用的.