第九章 虛擬存儲器
虛擬存儲器是計算機系統最重要的概念之一，它是對主存的一個抽象
三個重要能力：
- 它將主存看成是一個存儲在磁盤上的地址空間的高速緩存，在主存中只保存活動區域，并根據需要在磁盤和主存之間來回傳送數據，通過這種方式，高效的使用了主存
- 它為每個進程提供了一致的地址空間，從而簡化了存儲器管理
- 它保護了每個進程的地址空間不被其他進程破壞
第一節 物理和虛擬尋址
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字節。
?
1.DRAM緩存的組織結構
2.頁表
3.缺頁
4.虛擬存儲器中的局部性
第四節 虛擬存儲器作為存儲器管理的工具
- 操作系統為每個進程提供了一個獨立的頁表，也就是一個獨立的虛擬地址空間。
- 抖個虛擬頁面可以映射到同一個共享物理頁面上。
- 存儲器映射：將一組連續的虛擬頁映射到任意一個文件中的任意位置的表示法。
VM簡化了鏈接和加載、代碼和數據共享，以及應用程序的存儲器分配。
第五節 虛擬存儲器作為存儲器保護的工具
這里需要知道PTE的三個許可位：
- SUP：表示進程是否必須運行在內核模式下才能訪問該頁
- READ：讀權限
- WRITE：寫權限
第六節 地址翻譯
具體符號見上圖
地址翻譯就是一個N元素的虛擬地址空間VAS中的元素和一個M元素的物理地址空間PAS中元素之間的映射。
頁面基址寄存器PTBR指向當前頁表。
MMU利用VPN選擇適當的PTE。
PPO=VPO。
1.當頁面命中時，CPU動作：
- 處理器生成虛擬地址，傳給MMU
- MMU生成PTE地址，并從高速緩存/主存請求得到他
- 高速緩存/主存向MMU返回PTE
- MMU構造物理地址，并把它傳給高速緩存/主存
-
高速緩存/主存返回所請求的數據給處理器。
2.處理缺頁時：
- 處理器生成虛擬地址，傳給MMU
- MMU生成PTE地址，并從高速緩存/主存請求得到他
- 高速緩存/主存向MMU返回PTE
- PTE中有效位為0，觸發缺頁異常
- 確定犧牲頁
- 調入新頁面，更新PTE
-
返回原來的進程，再次執行導致缺頁的指令，會命中
一、結合高速緩存和虛擬存儲器來看
- 首先，在既使用SRAM高速緩存又使用虛擬存儲器的系統中，大多數系統選擇物理尋址
- 主要思路是地址翻譯發生在高速緩存之前
- 頁表目錄可以緩存，就像其他的數據字一樣
二、利用TLB加速地址翻譯
TLB：翻譯后備緩沖器，是一個小的、虛擬存儲的緩存，其中每一行都保存著一個由單個PTE組成的塊
步驟：
- CPU產生一個虛擬地址
- MMU從TLB中取出相應的PTE
- MMU將這個虛擬地址翻譯成一個物理地址，并且將它發送到高速緩存/主存
- 高速緩存/主存將所請求的數據字返回給CPU
三、多級頁表
多級頁表——采用層次結構，用來壓縮頁表。
1.以兩層頁表層次結構為例，好處是：
- 如果一級頁表中的一個PTE是空的，那么相應的二級頁表就根本不會存在
- 只有一級頁表才需要總是在主存中，虛擬存儲器系統可以在需要時創建、頁面調入或調出二級頁表，只有最經常使用的二級頁表才緩存在主存中。
2.多級頁表的地址翻譯：
四、端對端的地址翻譯
這一部分看懂書上的例題。
第七節 案例研究
一、Core i7地址翻譯
在這里，PTE有三個權限位：
- R/W位：確定內容是讀寫還是只讀
- U/S位：確定是否能在用戶模式訪問該頁
- XD位：禁止執行位，64位系統中引入，可以用來禁止從某些存儲器頁取指令
還有連個缺頁處理程序涉及到的位：
- A位，引用位，實現頁替換算法
- D位，臟位，告訴是否必須寫回犧牲頁
二、Linux虛擬存儲器系統
Linux為每個進程維持了一個單獨的虛擬地址空間，如圖：
內核虛擬存儲器包括：內核中的代碼和數據結構。
一部分區域映射到所有進程共享的物理頁面
另一部分包含每個進程都不相同的數據。
一、Linux虛擬存儲器區域
區域：就是已分配的虛擬存儲器的連續片。
區域的例子：
- 代碼段
- 數據段
- 堆
- 共享庫段
- 用戶棧
- ……
每個存在的虛擬頁面都保存在某個區域中。內核為系統中的每個進程維護一個單獨的任務結構task_struct：
一個具體區域的區域結構包括：
- vm_start：指向起始處
- vm_end：指向結束處
- vm_prot：描述這個區域包含的所有頁的讀寫許可權限
- vm_flags：是共享的還是私有的
- vm_next：指向下一個區域
二、Linux缺頁異常處理
1.虛擬地址A是否合法？
不合法，觸發段錯誤，終止進程
合法，進入下一條
2.存儲器訪問是否合法？即，是否有權限？
不合法，觸發保護異常，終止程序
合法，進入下一條
3.這時，是針對合法的虛擬地址進行合法的操作。所以：選擇一個犧牲頁面，如果被修改過就換新的并更新頁表。
第八節 存儲器映射
即指Linux通過將一個虛擬存儲器區域與一個磁盤上的對象關聯起來，以初始化這個虛擬存儲器區域的內容的過程。
映射對象：
1.Unix文件系統中的普通文件
2.匿名文件（全都是二進制0）
一、共享對象和私有對象
1.共享對象
-
共享對象對于所有把它映射到自己的虛擬存儲器進程來說都是可見的
-
即使映射到多個共享區域，物理存儲器中也只需要存放共享對象的一個拷貝。
2.私有對象
- 私有對象運用的技術：寫時拷貝
- 在物理存儲器中只保存有私有對象的一份拷貝
fork函數就是應用了寫時拷貝技術，至于execve函數：
二、使用mmap函數的用戶級存儲器映射
1.創建新的虛擬存儲器區域
#include <unistd.h>
#include <sys/mman.h> void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset); 成功返回指向映射區域的指針，若出錯則為-1參數含義：
- start：這個區域從start開始
- fd：文件描述符
- length：連續的對象片大小
- offset：距文件開始處的偏移量
-
prot：訪問權限位，具體如下：
PROT_EXEC:由可以被CPU執行的指令組成 PROT_READ:可讀 PROT_WRITE:可寫 PROT_NONE:不能被訪問 -
flag：由描述被映射對象類型的位組成，具體如下：
MAP_ANON:匿名對象，虛擬頁面是二進制0 MAP_PRIVATE:私有的、寫時拷貝的對象 MAP_SHARED：共享對象2.刪除虛擬存儲器：
include
include <sys/mman.h>
int munmap(void *start, size_t length);
成功返回0，失敗返回-1
從start開始刪除，由接下來length字節組成的區域。
第九節 動態存儲器分配
1.堆：
是一個請求二進制0的區域，緊接在未初始化的bss區域后開始，并向上（更高的地址）生長。有一個變量brk指向堆的頂部
2.分配器的兩種基本風格：
a.顯示分配器-malloc和free
b.隱式分配器/垃圾收集器
一、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語言不會用類型標記來標記存儲器位置。
