第九章 虛拟存儲器
一、虛拟存儲器提供了三個重要能力：
1、将主存看作是一個存儲在磁盤上的位址空間的高速緩存，在主存中隻保護活動的區域，并根據需要在磁盤和主存之間來回傳送資料；
2、為每個程序提供了一緻的位址空間，進而簡化了存儲器管理；
3、保護了每個程序的位址空間不被其它程序破壞。
二、了解虛拟存儲器的原因：
1、虛拟存儲器是中心的：它是硬體異常、硬體位址翻譯、主存、磁盤檔案和核心軟體的互動中心；
2、虛拟存儲器是強大的：它可以建立和銷毀存儲器片、可以映射存儲器片映射到磁盤某個部分等等；
3、虛拟存儲器若操作不當則十分危險。
9.1 實體和虛拟尋址
一、實體位址
實體尋址（PA）：主存中每個位元組都有唯一的實體位址；依靠此來尋址，就叫做實體尋址。
二、虛拟位址
虛拟尋址（VA）：CPU生成一個虛拟位址然後用這個位址通路主存，這個虛拟位址在送到存儲器之前先被轉換成适當的實體位址（這個過程叫做位址翻譯）。
9.2 位址空間
一、位址空間：位址空間是一個非負整數位址的有序集合：{0,1,2,……}
二、線性位址空間：位址空間中的整數是連續的。
三、虛拟位址空間：CPU從一個有 N=2^n 個位址的位址空間中生成虛拟位址，這個位址空間成為稱為虛拟位址空間。
四、位址空間的大小：由表示最大位址所需要的位數來描述。N=2^n：n位位址空間。
主存中的每個位元組都有一個選自虛拟位址空間的虛拟位址和一個選自實體位址空間的實體位址。
9.3 虛拟存儲器作為緩存的工具
一、首先，VM上被組織為一個由存放在磁盤上的N個連續的位元組大小的單元組成的數組。每個位元組都有一個唯一的虛拟位址，這個虛拟位址是作為到數組的索引的。其次，VM系統将虛拟存儲器分割為大小固定的虛拟頁，每個虛拟頁的大小為P=2^p位元組；類似地，實體存儲器被分割為實體頁（也叫做頁幀），大小也為P位元組。
二、任意時刻，虛拟頁面的集合都被分為三個不相交的子集：
1、未配置設定的：VM系統還沒配置設定/建立的頁，不占用任何磁盤空間。
2、緩存的：目前緩存在實體存儲器中的已配置設定頁。
3、未緩存的：沒有緩存在實體存儲器中的已配置設定頁。
三、頁表
1、作用：将虛拟頁映射到實體頁。每次位址翻譯硬體将一個虛拟位址轉換為實體位址時都會讀取頁表。作業系統負責維護頁表中的内容。
2、結構：頁表就是一個頁表條目（PTE）數組；虛拟位址空間中的每個頁在頁表中一個固定偏移量處都有一個PTE。為了我們的目的，我們假設每個PTE是由一個有效位和一個n位的位址字段組成的。有效位表明了該實體頁的起始位置，這個實體頁中緩存了該虛拟頁。
四、缺頁
1、 DRAM緩存不命中稱為缺頁。
2、處理過程：
- 缺頁異常調用核心中的缺頁異常處理程式，該程式會選擇一個犧牲頁，将其換出記憶體；
- 核心從磁盤中拷貝需要的條目到犧牲頁之前所在的位置，随後傳回；
- 當異常處理程式傳回之後，它會再次啟動導緻缺頁的指令，該指令會把導緻缺頁的虛拟位址重發送到位址翻譯硬體；
- 此時，頁面命中
3、概念補充：
- 在存儲器的習慣說法中，塊被稱為頁；
- 在磁盤和存儲器之間傳送頁的活動叫做交換或者頁面排程；
- 頁從磁盤換入DRAM和從DRAM換出磁盤；一直等待到不命中發生的時候才換入頁面；這種政策被稱為按需頁面排程
五、虛拟存儲器中的局部性
1、局部性原則保證了在任意時刻，程式将往往在一個較小的活動頁面集合上工作，這個集合叫做工作集/常駐集。
2、 颠簸：工作集大小超出了實體存儲器的大小。
9.4虛拟存儲器作為存儲器管理的工具
1、作業系統為每個程序提供了一個獨立的頁表，也就是一個獨立的虛拟位址空間。
2、抖個虛拟頁面可以映射到同一個共享實體頁面上。
3、存儲器映射：将一組連續的虛拟頁映射到任意一個檔案中的任意位置的表示法。
VM簡化了連結和加載、代碼和資料共享，以及應用程式的存儲器配置設定。
9.5 虛拟存儲器作為存儲器保護的工具
PTE的三個許可位：
1、SUP：表示程序是否必須運作在核心模式下才能通路該頁
2、READ：讀權限
3、WRITE：寫權限
9.6 位址翻譯
一、位址翻譯：形式上說，位址翻譯是一個N元素的虛拟位址空間（VAS）中的一個元素和一個M元素的實體位址空間(PAS）之間的映射；
二、過程：
- CPU中的一個控制寄存器，頁表基址寄存器指向目前頁表；
- n位的虛拟位址包括以下兩個部分：一個p位的虛拟頁面偏移和一個（n-p）位的虛拟頁号；
- MMU用後者選擇适當的PTE，再将實體頁号和虛拟位址中的VPO串聯起來得到實體位址；
- 因為實體和虛拟頁面都是P位元組的，是以實體頁面偏移和VPO是相同的
三、CPU執行步驟（頁面命中）
- 處理器生成一個虛拟位址，并把它傳遞給MMU；
- MMU生成一個PTE位址，并從高速緩存/主存中請求得到它；
- 高速緩存/主存向MMU傳回PTE；
- MMU構造實體位址，并把它傳給高速緩存/主存；
- 高速緩存/主存傳回所請求的資料字給處理器
四、CPU執行步驟（缺頁）
- PTE中有效位是0，觸發了一次異常，傳遞CPU中的控制到作業系統核心中的缺頁異常處理程式；
- 缺頁處理程式确定實體存儲器中的犧牲頁，如果這個頁已經被修改了，則把它換出到磁盤；
- 缺頁處理程式調入新的頁面，并更新存儲器中的PTE；
- 缺頁處理程式傳回到原來的程序，再次執行導緻缺頁的指令。CPU将引起缺頁的虛拟位址重新發送給MMU；因為虛拟頁面現在緩存在實體存儲器中，是以發生命中。
9.7 案例研究
一、Core i7位址翻譯
PTE有三個權限位：
1、R/W位：确定内容是讀寫還是隻讀
2、U/S位：确定是否能在使用者模式通路該頁
3、XD位：禁止執行位，64位系統中引入，可以用來禁止從某些存儲器頁取指令
還有兩個缺頁處理程式涉及到的位：
1、A位，引用位，實作頁替換算法
2、D位，髒位，告訴是否必須寫回犧牲頁
二、Linux虛拟存儲器系統
1、 Linux為每個程序維持了一個單獨的虛拟位址空間，如圖：
2、 linux為每個程序維持了一個單獨的虛拟位址空間，其中，核心虛拟存儲器位于使用者棧之上；
3、核心虛拟存儲器包含核心中的代碼和資料結構，還有一些被映射到一組連續的實體頁面（主要是便捷地通路特定位置，比如執行I/O操作的時候需要的位置）
4、linux将虛拟存儲器組織成一些區域（也叫做段）的集合。一個區域就是已經存在的（已配置設定的）虛拟存儲器的連續片；
（1）意義：允許虛拟位址空間有間隙；核心不用記錄那些不存在的頁，這樣的頁也不用占用存儲器；
（2）區域結構：
vm_start：指向起始處
vm_end：指向結束處
vm_prot：描述這個區域包含的所有頁的讀寫許可權限
vm_flags：是共享的還是私有的
vm_next：指向下一個區域
9.8 存儲器映射
一、概念：linux（以及一些其他形式的unix）通過将一個虛拟存儲器區域與一個磁盤上的對象關聯起來，以初始化這個虛拟存儲器區域的内容；
二、類型：
1、unix檔案系統中的普通檔案：一個區域可以映射到一個普通磁盤檔案的連續部分，例如一個可執行目标檔案；
2、匿名檔案：一個區域也可以映射到一個匿名檔案，匿名檔案由核心建立，包含的全是二進制零（CPU第一次引用這樣一個區域内的虛拟頁面的時候，核心就在實體存儲器中找到合适的犧牲頁面然後用二進制零将其覆寫）
三、共享對象和私有對象
1.共享對象
（1）共享對象對于所有把它映射到自己的虛拟存儲器程序來說都是可見的
（2）即使映射到多個共享區域，實體存儲器中也隻需要存放共享對象的一個拷貝。
2.私有對象
（1）私有對象運用的技術：寫時拷貝
（2）在實體存儲器中隻儲存有私有對象的一份拷貝
9.9 動态存儲器配置設定
一、堆：是一個請求二進制0的區域，緊接在未初始化的bss區域後開始，并向上（更高的位址）生長。有一個變量brk指向堆的頂部
二、配置設定器的兩種基本風格：
1、顯示配置設定器-malloc和free
2、隐式配置設定器/垃圾收集器
三、為什麼要使用動态存儲器配置設定？
因為經常知道程式實際運作時，它們才知道某些資料結構的大小。
四、配置設定器的要求和目标：
1、要求：
（1）處理任意請求序列
（2）立即響應請求
（3）隻使用堆
（4）對齊塊
（5）不修改已配置設定的塊
2、目标：
（1）最大化吞吐率（吞吐率：每個機關時間裡完成的請求數）
（2）最大化存儲器使用率——峰值使用率最大化
五、碎片
雖然有未使用的存儲器，但是不能用來滿足配置設定請求時，發生這種現象。
1、内部碎片
（1）發生在一個已配置設定塊比有效載荷大的時候
（2）易于量化。
2、外部碎片
（1）發生在當空閑存儲器合計起來足夠滿足一個配置設定請求，但是沒有一個單獨的空間塊足以處理這個請求時發生
（2）難以量化，不可預測。
六、隐式空閑連結清單
堆塊的格式：由一個字的頭部，有效荷載，和可能的額外填充組成。
七、放置已配置設定的塊——放置政策
1、首次适配
從頭開始搜尋空閑連結清單，選擇第一個合适的空閑塊
2、下一次适配
從上一次搜尋的結束位置開始搜尋
3、最佳适配
檢索每個空閑塊，選擇适合所需請求大小的最小空閑塊
八、申請額外的堆存儲器
用到sbrk函數：
#include <unistd.h>
vid *sbrk(intptr_t incr);
成功則傳回舊的brk指針，出錯為-1
通過将核心的brk指針增加incr來擴充和收縮堆。
九、合并空閑塊
合并是針對于假碎片問題的，任何實際的配置設定器都必須合并相鄰的空閑塊。
有兩種政策：
1、立即合并
2、推遲合并
十、實作簡單的配置設定器
實作一個簡單配置設定器的設計，有幾點是需要注意的：
1、序言塊和結尾塊：序言塊是初始化時建立的，而且永不釋放；結尾塊是一個特殊的塊，總是以它為結束。
2、有一個技巧，就是将重複使用的，操作複雜又有重複性的，這些可以定義成宏，友善使用也友善修改。
3、需要注意強制類型轉換，尤其是帶指針的，非常複雜。
4、因為規定了位元組對齊方式為雙字，就代表塊的大小是雙字的整數倍，不是的舍入到是。
十一、顯式空閑連結清單
1、差別
（1）配置設定時間
隐式的，配置設定時間是塊總數的線性時間
顯式的，是空閑塊數量的線性時間。
（2）連結清單形式
隐式——隐式空閑連結清單
顯式——雙向連結清單，有前驅和後繼，比頭部腳部好使。
2、排序政策：
後進先出
按照位址順序維護
十二、分離的空閑連結清單
分離存儲，是一種流行的減少配置設定時間的方法。一般思路是将所有可能的塊大小分成一些等價類/大小類。
配置設定器維護着一個空閑連結清單數組，每個大小類一個空閑連結清單，按照大小的升序排列。
有兩種基本方法：
1、簡單分離存儲
每個大小類的空閑連結清單包含大小相等的塊，每個塊的大小就是這個大小類中最大元素的大小。
2、分離适配
每個空閑連結清單是和一個大小類相關聯的，并且被組織成某種類型的顯示或隐式連結清單，每個連結清單包含潛在的大小不同的塊，這些塊的大小是大小類的成員。
這種方法快速并且對存儲器使用很有效率。
分離适配的特例-----夥伴系統
其中每個大小類都是2的幂。這樣，給定位址和塊的大小，很容易計算出它的夥伴的位址，也就是說：一個塊的位址和它的夥伴的位址隻有一位不同。
優點：快速檢索，快速合并。
9.10 垃圾收集
一、垃圾收集器是一種動态存儲配置設定器，它自動釋放程式不再需要的已配置設定塊，這些塊被稱為垃圾，自動回收堆存儲的過程叫做垃圾收集。垃圾收集器定期地識别垃圾塊，并相應地調用free，将這些塊放回到空閑連結清單中
二、垃圾收集器将存儲器視作一張有向可達圖，隻有當存在一條從任意根節點出發并到達p的有向路徑時，才說節點p是可達的，而不可達點就是垃圾。
9.11 C程式中常見的與存儲器有關的錯誤
1、間接引用壞指針
2、讀未初始化的存儲器
3、允許棧緩沖區溢出
4、假設指針和它們指向的對象是相同大小的
5、造成錯位錯誤
6、引用指針，而不是它所指向的對象
7、誤解指針運算
8、引用不存在的變量
9、引用空堆塊中的資料
10、引起存儲器洩露
參考資料
《深入了解計算機系統》
學習體會
本周學習了第九章虛拟存儲器的内容，作業系統這門課程中提到過相關的内容，但是比較淺，通過本周的學習，更加深入地了解了虛拟存儲器。這是本學期學習的最後一章内容，内容比較多。通過一學期的學習，發現學習不僅要學知識，而且要有端正的學習态度，要有耐心、信心、恒心！