第九章 虛拟存儲器
虛拟存儲器的三個重要能力：
它将主存看成是一個存儲在磁盤上的位址空間的高速緩存，在主存中隻儲存活動區域，并根據需要在磁盤和主存之間來回傳送資料，通過這種方式，高效的使用了主存
它為每個程序提供了一緻的位址空間，進而簡化了存儲器管理
它保護了每個程序的位址空間不被其他程序破壞 第一節 實體和虛拟尋址
1.實體位址
計算機系統的主存被組織成一個由M個連續的位元組大小的單元組成的數組，每位元組都有一個唯一的實體位址PA。
根據實體位址尋址的是實體尋址。
2.虛拟位址
虛拟存儲器被組織為一個由存放在磁盤上的N個連續的位元組大小的單元組成的數組。
使用虛拟尋址時，CPU通過生成一個虛拟位址VA來通路主存，這個虛拟位址在被送到存儲器之前先轉換成适當的實體位址。
第二節 位址空間
1.位址空間
位址空間是一個非負整數位址的有序集合：{0,1,2,……}
2.線性位址空間
位址空間中的整數是連續的。
3.虛拟位址空間
CPU從一個有 N=2^n 個位址的位址空間中生成虛拟位址，這個位址空間成為稱為虛拟位址空間。
4.位址空間的大小
由表示最大位址所需要的位數來描述。N=2^n：n位位址空間
第三節 虛拟存儲器作為緩存的工具
虛拟存儲器——虛拟頁VP，每個虛拟頁大小為P=2^平位元組。
實體存儲器——實體頁PP，也叫頁幀，大小也為P位元組。
任意時刻，虛拟頁面的集合都被分為三個不相交的子集：
未配置設定的：VM系統還沒配置設定/建立的頁，不占用任何磁盤空間。
緩存的：目前緩存在實體存儲器中的已配置設定頁
未緩存的：沒有緩存在實體存儲器中的已配置設定頁 1.DRAM緩存的組織結構
不命中處罰很大
是全相聯的——任何虛拟頁都可以放在任何的實體頁中。
替換算法精密
總是使用寫回而不是直寫。 2.頁表
頁表是一個資料結構，存放在實體存儲器中，将虛拟頁映射到實體頁。
頁表就是一個頁表條目PTE的數組，組成為：有效位+n位位址字段
1.如果設定了有效位：
位址字段表示DRAM中相應的實體頁的起始位置，這個實體頁中緩存了該虛拟頁
2.如果沒有設定有效位：
(1)空位址：
表示該虛拟頁未被配置設定
(2)不是空位址：
這個位址指向該虛拟頁在磁盤上的起始位置。
3.缺頁
缺頁：就是指DRAM緩存不命中。
缺頁異常：會調用核心中的缺頁異常處理程式，選擇一個犧牲頁。
頁：虛拟存儲器的習慣說法，就是塊
交換=頁面排程：磁盤和存儲器之間傳送頁的活動
按需頁面排程：直到發生不命中時才換入頁面的政策，所有現代系統都使用這個。
4.虛拟存儲器中的局部性
局部性原則保證了在任意時刻，程式将往往在一個較小的活動頁面集合上工作，這個集合叫做工作集/常駐集。
是以隻要程式有良好的時間局部性，虛拟存儲器系統就能工作的相當好。
第四節 虛拟存儲器作為存儲器管理的工具
- 作業系統為每個程序提供了一個獨立的頁表，也就是一個獨立的虛拟位址空間。
- 抖個虛拟頁面可以映射到同一個共享實體頁面上。
- 存儲器映射：将一組連續的虛拟頁映射到任意一個檔案中的任意位置的表示法。
VM簡化了連結和加載、代碼和資料共享，以及應用程式的存儲器配置設定。
第五節 虛拟存儲器作為存儲器保護的工具
這裡需要知道PTE的三個許可位：
- SUP：表示程序是否必須運作在核心模式下才能通路該頁
- READ：讀權限
- WRITE：寫權限
第六節 位址翻譯
位址翻譯就是一個N元素的虛拟位址空間VAS中的元素和一個M元素的實體位址空間PAS中元素之間的映射。
頁面基址寄存器PTBR指向目前頁表。
MMU利用VPN選擇适當的PTE。
PPO=VPO。
一、結合高速緩存和虛拟存儲器來看
首先，在既使用SRAM高速緩存又使用虛拟存儲器的系統中，大多數系統選擇實體尋址
主要思路是位址翻譯發生在高速緩存之前
頁表目錄可以緩存，就像其他的資料字一樣 二、利用TLB加速位址翻譯
TLB：翻譯後備緩沖器，是一個小的、虛拟存儲的緩存，其中每一行都儲存着一個由單個PTE組成的塊
步驟：
- CPU産生一個虛拟位址
- MMU從TLB中取出相應的PTE
- MMU将這個虛拟位址翻譯成一個實體位址，并且将它發送到高速緩存/主存
- 高速緩存/主存将所請求的資料字傳回給CPU
三、多級頁表
多級頁表——采用層次結構，用來壓縮頁表。
1.以兩層頁表層次結構為例，好處是：
如果一級頁表中的一個PTE是空的，那麼相應的二級頁表就根本不會存在
隻有一級頁表才需要總是在主存中，虛拟存儲器系統可以在需要時建立、頁面調入或調出二級頁表，隻有最經常使用的二級頁表才緩存在主存中。
2.多級頁表的位址翻譯：
四、端對端的位址翻譯
這一部分看懂書上的例題。
第七節 案例研究
一、Core i7位址翻譯
二、Linux虛拟存儲器系統
Linux為每個程序維持了一個單獨的虛拟位址空間，如圖：
核心虛拟存儲器包括：核心中的代碼和資料結構。
一部分區域映射到所有程序共享的實體頁面
另一部分包含每個程序都不相同的資料。
第八節 存儲器映射
即指Linux通過将一個虛拟存儲器區域與一個磁盤上的對象關聯起來，以初始化這個虛拟存儲器區域的内容的過程。
一、共享對象和私有對象
1.共享對象
共享對象對于所有把它映射到自己的虛拟存儲器程序來說都是可見的，即使映射到多個共享區域，實體存儲器中也隻需要存放共享對象的一個拷貝。
2.私有對象
私有對象運用的技術：寫時拷貝，在實體存儲器中隻儲存有私有對象的一份拷貝
fork函數就是應用了寫時拷貝技術，至于execve函數：
二、使用mmap函數的使用者級存儲器映射
1.建立新的虛拟存儲器區域
2.删除虛拟存儲器
第九節 動态存儲器配置設定
1.堆：
是一個請求二進制0的區域，緊接在未初始化的bss區域後開始，并向上（更高的位址）生長。有一個變量brk指向堆的頂部
2.配置設定器的兩種基本風格：
- 顯示配置設定器-malloc和free
- 隐式配置設定器/垃圾收集器
一、malloc和free函數：
系統調用malloc函數，從堆中配置設定塊：
#include <stdlib.h>
void *malloc(size_t size);
成功傳回指針，指向大小至少為size位元組的存儲器塊，失敗傳回NULL 系統調用free函數來釋放已配置設定的堆塊：
#include <stdlib.h>
void free(void *ptr);
無傳回值 ptr參數必須指向一個從malloc、calloc或者reallov獲得的已配置設定塊的起始位置。
二、配置設定器的要求和目标：
1.要求
處理任意請求序列
立即響應請求
隻使用堆
對齊塊
不修改已配置設定的塊 2.目标：
最大化吞吐率（吞吐率：每個機關時間裡完成的請求數）
最大化存儲器使用率——峰值使用率最大化 三、碎片
雖然有未使用的存儲器，但是不能用來滿足配置設定請求時，發生這種現象。
1.内部碎片
發生在一個已配置設定塊比有效載荷大的時候，易于量化。
2.外部碎片
發生在當空閑存儲器合計起來足夠滿足一個配置設定請求，但是沒有一個單獨的空間塊足以處理這個請求時發生，難以量化。
四、隐式空閑連結清單
堆塊的格式：
由一個字的頭部，有效荷載，和可能的額外填充組成。
将堆組織成一個連續的已配置設定塊和空閑塊的序列：
空閑塊通過頭部中的大小字段隐含地連接配接着，配置設定器可以通過周遊堆中所有的塊，進而間接地周遊整個空閑塊的集合。
系統對齊要求和配置設定器對塊格式的選擇會對配置設定器上的最小塊大小有強制的要求。
五、放置已配置設定的塊——放置政策
1.首次适配
從頭開始搜尋空閑連結清單，選擇第一個合适的空閑塊
2.下一次适配
從上一次搜尋的結束位置開始搜尋
3.最佳适配
檢索每個空閑塊，選擇适合所需請求大小的最小空閑塊
六、申請額外的堆存儲器
用到sbrk函數：
#include <unistd.h>
vid *sbrk(intptr_t incr);
成功則傳回舊的brk指針，出錯為-1 通過将核心的brk指針增加incr來擴充和收縮堆。
七、合并空閑塊
合并是針對于假碎片問題的，任何實際的配置設定器都必須合并相鄰的空閑塊。
有兩種政策：
- 立即合并
- 推遲合并
八、帶邊界的合并
這個合并的意思是，因為頭部的存在，是以向後合并是簡單的，但是向前合并是不友善的，是以���在塊的最後加一個腳部，作為頭部的副本，就友善了合并，具體四種情況如下：
空閑塊總是需要腳部的。
九、實作簡單的配置設定器
序言塊和結尾塊：序言塊是初始化時建立的，而且永不釋放；結尾塊是一個特殊的塊，總是以它為結束。
有一個技巧，就是将重複使用的，操作複雜又有重複性的，這些可以定義成宏，友善使用也友善修改。
需要注意強制類型轉換，尤其是帶指針的，非常複雜。
因為規定了位元組對齊方式為雙字，就代表塊的大小是雙字的整數倍，不是的舍入到是。 十、顯式空閑連結清單
1.差別
（1）配置設定時間
隐式的，配置設定時間是塊總數的線性時間
但是顯式的，是空閑塊數量的線性時間。
（2）連結清單形式
隐式——隐式空閑連結清單
顯式——雙向連結清單，有前驅和後繼，比頭部腳部好使。
2.排序政策：
後進先出
按照位址順序維護
十一、分離的空閑連結清單
分離存儲，是一種流行的減少配置設定時間的方法。一般思路是将所有可能的塊大小分成一些等價類/大小類。
配置設定器維護着一個空閑連結清單數組，每個大小類一個空閑連結清單，按照大小的升序排列。
有兩種基本方法：
1.簡單分離存儲
每個大小類的空閑連結清單包含大小相等的塊，每個塊的大小就是這個大小類中最大元素的大小。
（1）操作
如果連結清單非空：配置設定其中第一塊的全部
如果連結清單為空：配置設定器向作業系統請求一個固定大小的額外存儲器片，将這個片分成大小相等的塊，并且連接配接起來成為新的空閑連結清單。
（2）優缺點
優點：時間快，開銷小
缺點：容易造成内部、外部碎片
2.分離适配
每個空閑連結清單是和一個大小類相關聯的，并且被組織成某種類型的顯示或隐式連結清單，每個連結清單包含潛在的大小不同的塊，這些塊的大小是大小類的成員。
這種方法快速并且對存儲器使用很有效率。
3.夥伴系統——分離适配的特例
其中每個大小類都是2的幂
這樣，給定位址和塊的大小，很容易計算出它的夥伴的位址，一個塊的位址和它的夥伴的位址隻有一位不同。
優點：快速檢索，快速合并。
第十節 垃圾收集
垃圾收集器是一種動态存儲配置設定器，它自動釋放程式不再需要的已配置設定塊，這些塊被稱為垃圾，自動回收堆存儲的過程叫做垃圾收集。
1.垃圾收集器将存儲器視作一張有向可達圖，隻有當存在一條從任意根節點出發并到達p的有向路徑時，才說節點p是可達的，而不可達點就是垃圾。
2.Mark&Sweep垃圾收集器
有兩個階段：
- 标記：标記出根節點的所有可達的和已配置設定的後繼
- 清楚：釋放每個未被标記的已配置設定塊。
相關函數：
ptr定義為typedef void *ptr ptr isPtr(ptr p)：如果p指向一個已配置設定塊中的某個字，那麼就傳回一個指向這個塊的起始位置的指針b，否則傳回NULL
int blockMarked(ptr b)：如果已經标記了塊b，那麼就傳回true
int blockAllocated(ptr b)：如果塊b是已配置設定的，那麼久傳回ture
void markBlock(ptr b)：标記塊b
int length(ptr b)：傳回塊b的以字為機關的長度，不包括頭部
void unmarkBlock(ptr b)：将塊b的狀态由已标記的改為未标記的
ptr nextBlock(ptr b)：傳回堆中塊b的後繼
3.C保守的Mark&Sweep——平衡二叉樹
因為C語言不會用類型标記來标記存儲器位置。
第十一節 C程式中常見的與存儲器有關的錯誤
1.間接引用壞指針
常見錯誤：
——scanf錯誤
2.讀未初始化的存儲器
——假設堆存儲器被初始化為0
3.允許棧緩沖區溢出
——緩沖區溢出錯誤
4.假設指針和它們指向的對象是相同大小的
在遠處起作用action at distance
5.造成錯位錯誤
6.引用指針，而不是它所指向的對象
7.誤解指針運算
8.引用不存在的變量
9.引用空堆塊中的資料
10.引起存儲器洩露
學習總結
本周學習了存儲器的相關知識，對于配置設定器的相關内容學習得不是很透徹，希望老師上課可以着重講解一下。
參考資料
教材：《深入了解計算機系統》