9.虛擬存儲器

為了更加有效地管理存儲器且少出錯，現代系統提供了對主存的抽象概念，叫做虛擬存儲器(VM）。

• 虛擬存儲器是硬體異常，硬體地址翻譯，主存，磁碟文件和內核軟體的完美交互。
• 為每個進程提供一個大的，一致的和 私有的地址空間。
• 提供了3個重要能力。
  • 將主存看成磁碟地址空間的高速緩存。
    • 只保留了活動區域，並根據需要在磁碟和主存間來回傳送數據，高效使用主存。
  • 為每個進程提供一致的地址空間
    • 簡化存儲器管理
  • 保護了每個進程的地址空間不被其他進程破壞。
• 程式員為什麼要理解它？
  • 虛擬存儲器是中心的。
    • 遍佈在電腦系統所有層次，硬體異常，彙編器，連接器，載入器，共用對象，文件和進程中扮演重要角色。
  • 虛擬存儲器是強大的。
    • 可以創建和銷毀存儲器片(chunk)
    • 將存儲器片映射到磁碟文件的某個部分。
    • 其他進程共用存儲器。
    • 例子
      • 能讀寫存儲器位置來修改磁碟文件內容。
      • 載入文件到存儲器不需要顯式的拷貝。
  • 虛擬存儲器是危險的
    • 引用變數，間接引用指正，調用malloc動態分配程式，就會和虛擬存儲器交互。
    • 如果使用不當，將遇到複雜危險的與存儲器有關的錯誤。
    • 例子
      • 一個帶有錯誤指針的程式可以立即崩潰於段錯誤或者保護錯誤。
      • 運行完成，卻不產生正確結果。
• 本章從兩個角度分析。
  • 虛擬存儲器如何工作。
  • 應用程式如何使用和管理虛擬存儲器。

9.1 物理與虛擬定址

• 物理地址(Physical Address,PA):電腦系統的主存被組織為M個連續的位元組大小的單元組成的數組。每個位元組的地址叫物理地址.

• CPU訪問存儲器的最自然的方式使用物理地址，這種方式稱為物理定址。
  - 早期的PC，數字信號處理器，嵌入式微控制器以及Cray超級電腦使用物理定址。

• 現代處理器使用的是虛擬定址(virtual addressing)的定址形式。

  
  • CPU通過生成一個虛擬地址(Virtual address,VA)來訪問主存。
    • 將虛擬地址轉換為物理地址叫做地址翻譯(address translation)。
  • 地址翻譯也需要CPU硬體和操作系統之間的緊密結合。
    • CPU晶元上有叫做存儲器管理單元(Memory Management Unit,MMU)的專用硬體。
      • 利用存儲在主存中的查詢表來動態翻譯虛擬地址。
      • 查詢表由操作系統管理。

9.2 地址空間

地址空間(address space)是一個非負整數地址的有序集合。

• 如果地址空間中整數是連續的，我們說它是線性地址空間(linear address space)。
  • 為了簡化討論，我們總是假設使用線性地址空間。

• 在一個帶虛擬存儲器的系統中，CPU從一個有N=2^n個地址的地址空間中生成虛擬地址，這個地址空間稱為虛擬地址空間(virtual address space)。

• 一個地址空間大小是由表示最大地址所需要的位數來描述的。
  • 如N=2^n個地址的虛擬地址空間叫做n位地址空間。
  • 現在操作系統支持32位或64位。

• 一個系統還有物理地址空間,它與系統中物理存儲器的M=2^m(假設為2的冪)個位元組相對應。

地址空間的概念很重要，因為它區分了數據對象(位元組)和 它們的屬性(地址)。

• 每個位元組(數據對象)一般有多個 獨立的地址(屬性)。每個地址都選自不同的地址空間。
  • 比如一般來說。
    • 位元組 有一個在虛擬地址空間的虛擬地址。
    • 還有一個在物理地址空間的 物理地址。
    • 兩個地址都能訪問到這個位元組。
  • 類似現實世界的門牌號, 和經緯度。

9.3 虛擬存儲器作為緩存的工具

感悟

在講述這一小章之前，必須交代一下我對虛擬存儲器概念的存疑。

原本我以為虛擬存儲器=虛擬記憶體。

以下是虛擬記憶體的定義

虛擬記憶體是電腦系統記憶體管理的一種技術。它使得應用程式認為它擁有連續的可用的記憶體（一個連續完整的地址空間），而實際上，它通常是被分隔成多個物理記憶體碎片，還有部分暫時存儲在外部磁碟存儲器上，在需要時進行數據交換

而在下麵的定義我們可以看到CSAPP中認為虛擬存儲器是存放在磁碟上的。

在此，我們姑且當做兩者是不同的東西，以後有更深刻的理解，再思考。

虛擬存儲器(VM)被組織為一個存放在磁碟上的N個連續位元組大小的單元組成的數組。

• 每個位元組都有一個唯一的虛擬地址，這個虛擬地址作為到數組的索引。
• 磁碟上數組的內容被緩存到主存中。
  • 同存儲器層次結構其他緩存一樣，磁碟上的數據被分割稱塊。
    • 這些塊作為磁碟和主存之間的傳輸單元。
    • 虛擬頁(Virtual Page,VP)就是這個塊
      • 每個虛擬頁大小為P=2^p位元組。
  • 物理存儲器被分割為物理頁,大小也為P位元組
    • 也被稱為頁幀(page frame)
• 任何時候，虛擬頁的集合都被分為3個不相交的子集。
  • 未分配的:VM系統還未分配(或者創建)的頁。未分配的塊沒有任何數據與之相關聯。
    • 不占用磁碟空間
    • 通過malloc來分配
  • 緩存的：當前緩存在物理存儲器的已分配頁。
  • 未緩存的:沒有緩存在物理頁面存儲器中的已分配頁。
  

9.3.1 DRAM緩存的組織結構

DRAM表示虛擬存儲器系統的緩存，在主存中緩存虛擬頁,有兩個特點。

• DRAM緩存不命中處罰十分嚴重。
  • 因為磁碟比DRAM慢100000多倍。
• 訪問一位元組開銷
  • :從一個磁碟的一個扇區讀取第一個位元組的時間開銷要比從該扇區中讀連續的位元組慢大約100000倍

DRAM緩存的組織結構由這種巨大的不命中開銷驅動。因此有以下特點。
(有些地方不是特別懂，之後看完第六章應該會好點)

• 虛擬頁往往很大。
  • 4KB~2MB
  • 訪問一位元組開銷的原因才要這麼大。
• DRAM緩存是全相聯
  • 也就是： 任何虛擬頁都能放在任何物理頁中。
  • 原因在於大的不命中懲罰
• 更精密的替換演算法
  • 替換錯了虛擬頁的懲罰很高。
• DRAM緩存總是寫回
  • 因為對磁碟的訪問時間很長
  • 而不用直寫

9.3.2 頁表

判斷命中和替換又多種軟硬體聯合提供。

• 操作系統軟體，MMU中的地址翻譯硬體和頁表(page table)。
  • 頁表是存放在物理存儲器的數據結構。
    • 頁表將虛擬頁映射到物理頁。
    • 地址翻譯硬體將虛擬地址轉換為物理地址都會讀取頁表。
  • 操作系統負責維護頁表的內容，以及磁碟及DRAM之間來回傳送頁。

• 頁表就是一個頁表條目(Page Table Entry,PTE)的數組.
  • 虛擬地址空間 中每個頁在頁表的固定偏移量處都有一個PTE.
  • 每個PTE由一個有效位和n位地址欄位。
    • 有效位表明虛擬頁是否被緩存。
      • 如果有效位存在，那麼地址欄位指向對應的物理存儲器。
      • 如果有效位不存在。
        • 地址欄位要麼為NULL
        • 要麼指向虛擬頁在磁碟所在的位置。

9.3.3 頁命中

• 一個頁命中的過程。
• 一個虛擬地址轉換為物理地址的過程。

9.3.4 缺頁

在虛擬存儲器的習慣說法中，DRAM緩存不命中稱為缺頁。

處理過程如下：

• 讀取虛擬地址所指向的PT。
• 讀取PTE有效位，發現未被緩存，觸發缺頁異常。
• 調用缺頁異常處理程式
  • 選擇犧牲頁。
  • 如果犧牲頁發生了改變，將其拷貝回磁碟(因為是寫回)
  • 需要讀取的頁代替了犧牲頁的位置。
  • 結果：犧牲也不被緩存，需要讀取的頁被緩存。
• 中斷結束，重新執行最開始的指令。
• 在DRAM中讀取成功。

虛擬存儲器是20世紀60年代發明的，因此即使與SRAM緩存使用了不同的術語。

• 塊被稱為頁。
• 磁碟和DRAM之間傳送頁的活動叫做交換(swapping)或者頁面調度(paging)。
• 有不命中發生時，才換入頁面，這種策略叫做按需頁面調度(demand paging)。
  • 現代系統基本都是用這個。

9.3.5 分配頁面

比如某個頁面所指向地址為NULL，將這個地址指向磁碟某處，那麼這就叫分配頁面。

此時虛擬頁從未分配狀態 變為 未緩存。

9.3.6 又是局部性拯救了我們

虛擬存儲器工作的相當好，主要歸功於老朋友局部性(locality)

儘管從頭到尾的活動頁面數量大於物理存儲器大小。

但是在局部內，程式往往在一個較小的活動頁面集合工作

• 這個集合叫做工作集(working set)或者叫常駐集(resident set)
  • 初始載入開銷比較大。
• 程式有良好的時間局部性，虛擬存儲器都工作的相當好。
• 如果程式實在很爛，或者物理空間很小，工作集大於物理存儲器大小。這種狀態叫顛簸(thrashing).
  • 這時，頁面不斷換進換出。性能十分低。

統計缺頁次數

可以利用Unix的getrusage函數檢測缺頁數量。

9.4 虛擬存儲器作為存儲器的管理工具

實際上，操作系統為每個進程提供一個獨立的頁表。

因此，VM簡化了鏈接和載入,代碼和數據共用,以及應用程式的存儲器分配。

• 簡化鏈接
  • 獨立的空間地址意味著每個進程的存儲器映像使用相同的格式。
    • 文本節總是從0x08048000(32位)處或0x400000(64位)處開始。
    • 然後是數據，bss節,棧。
  • 一致性極大簡化了鏈接器的設計和實現。

• 簡化載入

  • 載入器可以從不實際拷貝任何數據從磁碟到存儲器。

  • 基本都是虛擬存儲系統完成。

    將一組連續的虛擬頁映射到任意一個文件中的任意位置的表示法稱作存儲器映射。Unix提供一個稱為mmap的系統調用，允許程式自己做存儲器映射。在9.8詳細講解。

• 簡化共用

  • 獨立地址空間為操作系統提供了一個管理用戶進程和操作系統自身之間的一致共用機制.
  • 例子
    • 操作相同的操作系統內核代碼
    • C標準庫的printf.
  • 因此操作系統需要將不同進程的適當的虛擬頁映射到相同的物理頁面。
    • 多個進程共用這部分代碼的一個拷貝。
    • 而不是每個進程都要載入單獨的內核和C標準庫的拷貝。
• 簡化存儲器分配.
  • 即虛擬頁連續(虛擬頁還是單獨的)，物理頁可以不連續。使得分配更加容易。

9.5 虛擬存儲器作為存儲器保護的工具

任何現代操作系統必須為操作系統提供手段來控制對 存儲器系統的訪問。

• 不應該允許用戶進程修改它的只讀文本段。
• 不允許它讀或修改任何內核的代碼和數據結構
• 不允許讀寫其他進程的私有存儲器。
• 不允許修改共用的虛擬頁，除非所有共用者顯示允許這麼做(通過調用明確的進程間通信）

方式：在PTE上添加一些格外的許可位來控制訪問。

• SUP:是否只有在內核模式下才能訪問?
• READ：讀許可權。
• WRITE：寫許可權。

如果指令違反了許可條件，觸發一般保護性異常，然後交給異常處理程式，Shell一般會報告為段錯誤(segmentaion fault)。

9.6 地址翻譯

認識到硬體在支持虛擬存儲器中的角色

以下是接下來可能要用到的符號，作參考。

• 形式上來說，地址翻譯是一個N元素的虛擬地址空間(VAS)中的元素和一個M元素的物理地址空間（PAS)元素之間的映射,

  

• 以下展示了MMU(Memory Management Unit,存儲器管理單元)如何利用頁表實現這樣的功能

  
  • 頁表基址寄存器(Page Table Base Register,PTBR)指向當前頁表。
  • n位的虛擬地址包含兩個部分
    • 一個p位的虛擬頁面偏移(Virtual Page Offset,VPO)
    • 一個n-p位的虛擬頁號(Virtual Page Number,VPN)
      • MMU利用VPN選取適當的PTE(頁麵條目,Page Tabe Entry,PTE)
  • 頁麵條目 (PTE)中物理頁號(PPN)和虛擬地址中的VPO串聯起啦，即是物理地址
    • PPO和VPO是相同的
    • 不要忘記VPN,PPN都是塊，都是首地址而已，所以需要偏移地址PPO,VPO

圖(a)展示頁面命中,CPU硬體執行過程

• 第一步：處理器生成虛擬地址，把它傳送給MMU。
• 第二步: MMU生成PTE地址(PTEA)，並從高速緩存/主存請求中得到它。
• 第三步: 高速緩存/主存向MMU返回PTE。
• 第四步: MMU構造物理地址(PA)，並把它傳送給高速緩存/主存。
• 第五步: 高速緩���/主存返回所請求的數據字給處理器。

頁面命中完全由硬體處理，與之不同的是，處理缺頁需要 硬體和操作系統內核協作完成。

• 第一到三步: 與命中時的一樣
• 第四步:PTE有效位是零，所以MMU觸發異常，傳遞CPU中的控制到操作系統內核中的 缺頁異常處理程式。
• 第五步:缺頁異常處理程式確定出物理存儲頁中的犧牲頁，如果這個頁面已經被修改，則把它換出到磁碟。
• 第六步:缺頁異常處理程式調入新的頁面，並更新存儲器中的PTE。
• 第七部:缺頁異常處理程式返回到原來的進程，再次執行導致缺頁的指令，之後就是頁面命中一樣的步驟。

9.6.1 結合高速緩存和虛擬存儲器(PA->記憶體)

在任何使用虛擬存儲器又使用SRAM高速緩存的系統中，都存在應該使用虛擬地址 還是 使用 物理地址 來訪問SRAM高速緩存的問題。

使用虛擬地址的優點，就是類似於使用虛擬存儲器的優點，更好的利用空間。但是設計更複雜。兩者的使用需要權衡。

大多數系統是選擇物理定址。

• 使用物理定址,多個進程同時在高速緩存中有存儲塊和共用來自相同虛擬頁面的塊稱為簡單的事。
  • 而且還無需處理保護問題，因為 訪問許可權的檢查在地址翻譯中(PTE)的一部分。
• 以下是一個例子(將PTE進行高速緩存)。

9.6.2 利用TLB加速地址翻譯(VA->PA)

　
每次CPU產生一個虛擬地址，MMU就必須查閱一個PTE，以便將虛擬地址翻譯為 物理地址。

• 在最糟糕的情況下，會從記憶體中取數據，代價是幾十 到幾百個周期
• 如果PTE碰巧緩存在L1中，那麼開銷就下降到一到兩個周期

許多系統都試圖消除這樣的開銷，他們在MMU中包含了一個關於PTE的小緩存，稱為翻譯後備緩衝器(Translation Lookaside Buffer,TLB)。

• TLB是一個小的，虛擬定址的緩存。

  • 每一行都保存著一個由單個PTE組成的塊。
  • TLB通常用於高度的相連性

  • 如圖所示

    

    • 用於組選擇和行匹配的索引和標記欄位是從虛擬地址中的虛擬頁號中提取出來的。
    • 如果TLB有T=2^t個組
      • 那麼TLB索引(TLBI)是由VPN的t個最低位組成。(對應於VPO)
      • TLB標記(TLBT)是由VPN中剩餘位組成(對應於VPN)
• 下圖展示了TLB命中步驟
  • 關鍵點:所有的地址翻譯步驟都是在晶元上的MMU中執行的，因此非常快

  

  • TLB命中
    • 第一步:CPU產生虛擬地址。
    • 第二步和第三部:MMU從TLB取出對應的PTE。
    • 第四步:MMU將這個虛擬地址翻譯成一個物理地址，發送到高速緩存/主存
    • 第五步:高速緩存/主存所請求的數據字返回給CPU
  • 當TLB不命中的時候，MMU必須從L1緩存或記憶體中取出相應的PTE,併進行類似缺頁處理過程。

9.6.3 多級頁表

如果我們有一個32位地址空間，4KB大小的頁面(p=2^12)和一個4B的PTE，即使應用所引用的只是虛擬地址空間中很小的一部分，也總是需要一個4MB的頁表駐留在存儲器中。

所以多級頁表的誕生用於解決在很少使用時有一個很大的頁表常駐於記憶體。

計算方式，最多可能要2^32/4KB=1MB 個頁面，每個頁面需要4B的PTE 所以需要4MB大小的頁表。

思考虛擬地址是31~p,p-1~0即VPN,VPO。

VPN即可表示頁面個數(上文中的1MB)，VPO即頁面大小(上文中的4KB)，顯然知道兩者相乘為2^32 次方、

用來壓縮頁表的常用方式是使用層次結構的頁表。

頁表本身一個優點就是用來解決 記憶體不夠裝載程式所用記憶體的情況，進行動態分配。那麼當我們發現記憶體裝載那麼大的頁表也是負擔的時候，顯然也可以用類似頁表的形式來解決，這就是多級頁表。

以下用上圖的 兩層 作為例子。

• 總共有9KB個頁面，PTE為4個位元組。

  • 前2KB個頁面分配給代碼和數據。
  • 接下來6KB個頁面未分配
  • 再接下來1023個頁面也未分配
  • 接下一個頁面分配給用戶棧
• 一級頁表中的每個PTE負責映射虛擬地址空間中一個4MB大小的片(chunk).
  • 每一個片都是由1024個連續的頁面組成。
  • 4MB=1024個頁面*PTE大小4位元組。
• 如果片i中每個頁面都沒有分配，那麼一級PTE i就為空。
  • 例如圖中的PTE 2~PTE 7
  • 但是如果片i中有一個被分配了，那麼PTE i就不能為空。
    • 是不是覺得這樣很浪費啊~所以說，三級四級頁表的原由也是如此。
    • 而且後文會發現，頁表級數即使很大，複雜度也不會怎麼變化。
• 這種方法從兩個方面減少了存儲器要求。
  • 如果一級頁表PTE為空，那麼相應的二級頁表就根本不會存在。
    • 一種巨大的潛在節約，大部分時候記憶體都是未分配的。
  • 只有一級頁表才需要總是在主存中。
    • 虛擬存儲器系統可以在需要時創建，頁面調入，調出二級頁面，減少主存壓力。

  

k級頁表層次結構的地址翻譯。

• 虛擬地址被分為k個VPN和一個VPO。每個VPN i都是i-1級頁表到i級頁表的索引。
• PPN存於k級頁表。
• PPO依舊與VPO相同。

此時TLB能發揮作用，因為層次更細，更利於緩存。使得多級頁表的地址翻譯不比單級頁表慢很多。

9.6.4 綜合:端到端的地址翻譯

在這一節里，我們通過一個具體的端到端的地址翻譯示例，來綜合一下我們學過的內容。

一個在有一個TLB和L1 d-cache的小系統上。作出如下假設:

• 存儲器都是按位元組定址的。(?)
• 存儲器訪問是針對一位元組的字的。(?)
• 虛擬地址是14位長(n=14)
• 物理地址是12位長(m=12)
• 頁面大小是64位元組(P=2^6)
• TLB是四路組相連的，總共有16個條目(?)
• L1 d-cache是物理定址，高速緩存，直接映射(E=1)的，行大小為4位元組，而總共有16個組。(?)

存儲結構快照

• TLB: TLB利用VPN的位進行緩存。
• 頁表: 這個頁表是一個單級設計。一個有256個，但是這裡只列出16個。
• 高速緩存:直接映射的緩存通過物理地址的欄位來定址。
  • 因為是直接映射，通過索引就能直接找到。且E=1。
  • 直接能判定是否命中。

9.7 案例研究: Intel Core i7/Linux 存儲器系統

• 處理器包(processor package)
  • 四個核
    • 層次結構的TLB
      • 虛擬定址
      • 四路組相連
      • Linux 一頁4kb
    • 層次結構的數據和指令高速緩存。
      • 物理定址
      • L1，L2 八路組相連
      • L3 十六路組相連
      • 塊大小64位元組。
    • 快速的點到點鏈接。
      • 基於Intel QuickPath技術。
      • 為了讓核與其他核和外部I/O橋直接通信。
  • L3高速緩存
  • DDR3存儲器控制器。

9.7.1 Core i7地址翻譯

上圖完整總結了Core i7地址翻譯過程，從虛擬地址到找到數據傳入CPU。

• Core i7採用四級頁表層次結構。
  • CR3 控制寄存器指向第一級頁表(L1)的起始位置
    • CR3也是每個進程上下文的一部分。
    • 上下文切換的時候，CR3也要被重置。

一級，二級，三級頁表PTE的格式:

• P=1時 地址欄位包含了一個40位物理頁號(PPN)，指向適當的頁表開始處。

• 強加了一個要求，要求物理頁4kb對齊。
  • 因為 PPO 為12位 = 4kb
  • PPO的大小就跟物理頁的大小有關。

四級頁表的PTE格式:

• PTE有三個許可權位，控制對頁的訪問
  • R/W位確定頁的內容是可以 讀寫還是 只讀。
  • U/S位確定用戶模式是否能夠訪問，從而保護操作系統內核代碼不被用戶程式訪問。
  • XD (禁止執行) 位是在64位系統引入，禁止某些存儲器頁取指令。
    • 這是一個重要的新特性，限制只能執行只讀文本段，降低緩衝區溢出的風險。
• 當MMU翻譯虛擬地址時，還會更新兩個內核缺頁處理程式會用到的位。
  • A位
    • 每次訪問一個頁，MMU都會設置A位，稱為引用位(reference bit).
    • 可以利用這個引用位來實現它的頁替換演算法。
  • D位
    • 每次對一個頁進行了寫 就會設置D位，又稱臟位(dirty bit).
    • 臟位告訴內核在拷貝替換頁前是否要寫回。
  • 內核通過調用一條特殊的內核模式指令來清除引用位或臟位。

四級頁表如何將VPN 翻譯成物理地址

• 每個VPN被用作頁表的偏移量。
• CR3寄存器包含L1頁的物理地址

優化地址翻譯

在對地址翻譯中，我們順序執行這兩個過程

• MMU將虛擬地址翻譯成物理地址。
• 物理地址傳送到L1高速緩存。

然而實際的硬體實現使用了一個靈巧的技巧，允許這兩個步驟並行。加速了對高速緩存的訪問


例如:頁面大小為4KB的Core i7上的虛擬地址有12位的VPO，且PPO=VPO.

而且物理地址的緩存，也是6位索引+6位偏移，剛好是VPO的12位。這不是巧合

• 一方面通過VPN找PPN。
• 另一方面直接通過PPO對高速緩存進行組選擇。
• 等找到VPN後就能立即進行關鍵字匹配。

9.7.2 Linux 虛擬存儲系統

目標:對Linux的虛擬存儲系統做一個描述，大致瞭解操作系統如何組織虛擬存儲器，如何處理缺頁。

內核虛擬存儲器

• 內核虛擬存儲器包含內核中的代碼和數據。
  • 內核虛擬存儲器的某些區域被映射到所有進程共用的物理頁面
    • 如:內核代碼，全局數據結構。
  • Linux也將一組連續的虛擬頁面(大小等同於系統DRAM總量)映射到相應的一組物理頁面。(這句話啥意思???????????????????????????????)
• 內核虛擬存儲器包含每個進程不相同的數據。
  • 頁表，內核在進程上下文中時使用的棧，等等。

Linux 虛擬存儲器區域

Linux將虛擬存儲器組織成一些區域(也叫做段)的集合。

• 一個區域就是已經存在著的(已分配的) 虛擬存儲器的連續片，這些片/頁已某種形式相關聯。
  • 代碼段，數據段，堆，共用庫段，用戶棧。
  • 所有存在的虛擬頁都保存在某個區域。
• 區域的概念很重要
  • 允許虛擬地址空間有間隙。

一個進程中虛擬存儲器的內核數據結構。

內核為系統中每個進程維護了一個單獨的任務結構。任務結構中的元素包含或指向內核運行該進程所需要的全部信息。

• task_struct
  • mm_struct
    • 描述了虛擬存儲器的當前狀態。
    • pgd
      • 指向第一級頁表的基址。
      • 當進程運行時，內核將pgd存放在CR3控制寄存器
    • mmap
      • vm_area_structs(區域結構)
        • 每個vm_area_structs都描述了當前虛擬地址空間的一個區域(area).
        • vm_start:指向這個區域的起始處。
        • vm_end:指向這個區域的結束處。
        • vm_port:描述這個區域內包含的所有頁的讀寫許可許可權。
        • vm_flags:描述這個區域頁面是否與其他進程共用，還是私有。
          • 還有一些其他事情
        • vm_next: 指向鏈表的下一個區域。

Linux 缺頁異常處理

MMU在試圖翻譯虛擬地址A時，觸發缺頁。這個異常導致控制轉移到缺頁處理程式，執行一下步驟。

• 虛擬地址A是合法的嗎?
  • A在某個區域結構定義的區域內嗎?
  • 解決方法:
    • 缺頁處理程式搜索區域結構鏈表。
    • 把A和每個區域的vm_start和vm_end做比較。
      • 通過某種 樹的數據結構演算法查找
  • 如果不合法，觸發段錯誤。
• 試圖訪問的存儲器是否合法?
  • 即是否有讀，寫，執行這個頁面的許可權?
  • 如果不合法，觸發保護異常，終止進程。
• 一切正常的話
  • 選擇犧牲頁，替換，重新執行指令

9.8 存儲器映射

存儲器映射: Linux通過將一個虛擬存儲器區域與一個磁碟上的對象關聯起來，以初始化這個虛擬存儲器區域的內容，這個過程叫做存儲器映射。

虛擬存儲器區域可以映射到以下兩種類型文件。

• Unix文件系統中的普通文件:一個區域可以映射到一個普通磁碟文件的連續部分。
  • 例如，一個可執行文件。
  • 文件區(section)被分成頁大小的片，每一片包含一個虛擬頁面的初始化內容。
  • 僅僅是初始化，虛擬頁面此時還並未進入物理存儲器。
    • 直到CPU第一次引用這個頁面。
• 匿名文件 : 一個區域 可以映射到一個匿名文件。
  • 匿名文件由內核創建，包含的全是二進位零。
  • CPU第一次引用這樣區域(匿名文件)的虛擬頁面時。
    • 將存儲器中犧牲頁面全部用二進位零覆蓋。
    • 並將虛擬頁面標記為駐留在存儲器中。
    • 註意: 實際上，虛擬頁面並沒有跟存儲器進行數據傳送。
      • 反正是送零過去，不如我自己用零賦值，這樣子更快。
  • 又叫請求二進位零的頁(demand-zero page)。

交換文件，交換空間。(win下叫做paging file)

• 一旦一個虛擬頁面被初始化了，它就在一個由內核維護的專門的交換文件(swap file)之間換來換去。交換文件也叫交換空間或者交換區域。

• 需要意識到，在任何時刻，交換空間都限制著當前運行著的進程分配的虛擬頁面總數。

• 這一段不太明白。

9.8.1 再看共用對象

共用對象的由來

• 許多進程有同樣的只讀文本區域。
  • printf
  • 運行Uinx shell的tcsh
  • 如果每個進程都載入進記憶體一次，極其浪費。
• 存儲器映射提供一種機制，來共用對象。

一個對象被映射到虛擬存儲器的一個區域，一定屬於以下兩種。

• 共有對象
  • 一個進程將一個共有對象映射到它的虛擬地址空間的一個區域。
    • 進程對這個區域的寫操作，對於那些也把這個共用對象映射它的虛擬存儲器的進程是可見的。
    • 這���變化也會反映到磁碟上的原始對象。
  • 映射到的虛擬存儲器那個區域叫做共用區域。
• 私有對象
  • 對一個映射到私有對象的區域做出的改變，對於其他進程不可見.
  • 並且進行的寫操作不會反映到磁碟上。
  • 映射到的虛擬存儲器那個區域叫做私有區域。

9.8.1.1 共用對象

• 進程1，將共用對象映射到虛擬存儲器中，然後虛擬存儲器將這一段找一塊物理存儲器存儲。
• 當進程2也要引用同樣的共用對象時。
  • 內核迅速判定，進程1已經映射了這個對象。
  • 使進程2的虛擬存儲器直接指向了那一塊進程1指向的物理存儲器。
• 即使對象被映射到多個共用區域，物理存儲器依舊只有一個共用對象的拷貝。
  • 大大解決了物理存儲器記憶體。

9.8.1.2 私有對象

私有對象使用一種叫做寫時拷貝(conpy-on-write)的巧妙技術。

• 私有對象開始生命周期的方式基本與共用對象一樣。
  • 即使對象被多個引用，在物理記憶體都只保留一個拷貝。
• 對於每個映射私有對象的進程，相應私有區域的頁表條目都被標記為只讀。
  • 並且區域結構(vm_area_structs)被標記為私有的寫時拷貝。
• 過程:只要有進程試圖寫私有區域內的某個頁面，那麼這個寫操作觸發保護異常。
  • 故障處理程式會在物理存儲器中創建被修改頁面的一個新拷貝。
  • 更新頁表條目(PTE)指向這個新的拷貝，恢復被修改頁面的可寫許可權。
  • 故障處理程式返回，CPU重新執行這個寫操作。
• 通過延遲私有對象中的拷貝直到最後可能的時刻，寫時拷貝充分使用了稀缺的物理存儲器。

9.8.2 再看fork函數(私有對象的應用)

瞭解fork函數如何創建一個帶有自己獨立虛擬地址空間的新進程。

• 當fork函數被當前進程調用時。
  • 內核為新進程創建內核數據結構，並分配給它唯一一個PID。
  • 為了給新進程創建虛擬存儲器。
    • 創建了當前進程的mm_struct,區域結構和頁表的原樣拷貝。
    • 將兩個進程的每個頁面都標記為只讀。並給兩個區域進程的每個區域結構都標記為私有的寫時拷貝。
    • 註意:並沒有對物理存儲器進行拷貝哦~，利用的是私有對象的寫時拷貝技術。
• 當fork函數在新進程返回時。
  • 新進程現在的虛擬存儲器剛好和調用fork時存在的虛擬存儲器相同。
  • 當兩個進程中任一個需要被寫時，觸發寫時拷貝機制。

9.8.3 再看execve函數

理解execve函數實際上如何載入和運行程式。

• 假設運行在當前的進程中的程式執行瞭如下的調用:
  • Execve("a.out",NULL,NULL);
• execve函數在當前進程載入並執行目標文件a.out中的程式，用a.out代替當前程式。
  • 載入並運行需要以下幾個步驟。
    • 刪除已存在的用戶區域。
      • 刪除當前進程虛擬地址的用戶部分中已存在的區域結構。
    • 映射私有區域。
      • 為新程式的文本，數據，bss和棧區域創建新的區域結構。
        • 所有新的區域結構都是私有的，寫時拷貝的。
        • 文本和數據區域被映射到a.out文件中的文件和數據區。
        • bss區域是請求二進位零，映射到匿名文件。
          • 大小包含在a.out中
        • 堆，棧區域也是請求二進位零。
    • 映射共用區域
      • a.out程式與共用對象鏈接。
        • 這些對象都是動態鏈接到這個程式。
        • 然後映射到用戶虛擬地址的共用區域。
    • 設置程式計數器(PC)
      • execve最後一件事設置PC指向文本區域的入口點。

9.8.4 使用mmap函數的用戶級存儲器映射

Unix進程可以使用mmap函數來創建新的虛擬存儲器區域，並將對象映射到這些區域中。

#include <unistd.h>
#include <sys/mman.h>

void *mmap(void *start,size_t length,int prot,int flags,int fd,off_t offset);

返回:若成功時則為指向映射區域的指正，若出錯則為MAP_FAILED(-1).

參數解釋:

fd,start,length,offset:

mmap函數要求內核創建一個新的虛擬存儲器區域，最好是從地址start開始的一個區域，並將文件描述符fd指定的對象的一個連續的片chunk映射到這個新的區域。

• 連續對象片大小為length位元組
• 從據文件開始處偏移量為offset位元組的地方開始。
• statr地址僅僅是個暗示
  • 一般被定義為NULL，讓內核自己安排。

prot

參數prot包含描述新映射的虛擬存儲器區域的訪問許可權位。(對應區域結構中的vm_prot位)

• PROT_EXEC:這個區域內的頁面由可以被CPU執行的指令組成。
• PROT_READ:這個區域內的頁面可讀。
• PROT_WRITE: 這個區域內的頁面可寫。
• PROT_NONE: 這個區域內的頁面不能被訪問。

flag

參數flag由描述被映射對象類型的位組成。

• MAP_ANON標記位:映射對象是一個匿名對象。
• MAP_PRIVATE標記位:被映射對象是一個私有的，寫時拷貝的對象。
• MAP_SHARED標記位:被映射對象是一個共用對象。

例子

bufp = mmap(NULL,size,PROT_READ,MAP_PRIVATE|MAP_ANON,0,0);

• 讓內核創建一個新的包含size位元組的只讀，私有，請求二進位零的虛擬存儲區域。
• 如果調用成功，那麼bufp包含新區域地址。

munmap函數刪除虛擬存儲器的區域:

9.9 動態存儲器分配

雖然可以使用更低級的mmap和munmap函數來創建和刪除虛擬存儲器的區域。

但是C程式員還是覺得用動態存儲器分配器(dynamic memory allocator)更方便。

• 動態存儲器分配器維護著一個進程的虛擬存儲區域，稱為堆(heap)。
  • 系統之間細節不同，但是不失通用型。
  • 假設
    • 堆是一個請求二進位零的區域。
    • 緊接著未初始化的bss區域，並向上生長(向更高的地址)。
    • 對於每個進程，內核維護一個變數brk(break)，指向堆頂。
• 分配器將堆視為一組不同大小的塊block的集合來維護。
  • 每個塊就是一個連續的虛擬存儲器片，即頁面大小。
  • 要麼是已分配，要麼是空閑。
    • 已分配
      • 已分配的塊顯式地保留供應用程式使用。
      • 已分配的塊保持已分配狀態，直到它被釋放。
        • 這種釋放要麼是應用程式顯示執行。
          
        • 要麼是存儲器分配器自身隱式執行(JAVA)。
    • 空閑
      • 空閑塊可用於分配。
      • 空閑快保持空閑，直到顯式地被應用分配。
• 分配器有兩種基本分格。
  • 都要求應用顯式分配。
  • 不同之處在於那個實體負責釋放已分配的塊。
  • 顯式分配器(explict allocator)
    • 要求應用程式顯式地釋放。
    • C語言中提供一種叫malloc程式顯示分配器。
      • malloc和free
    • C++
      • new和delete
  • 隱式分配器(implicit allocator)
    • 要求分配器檢測一個已分配塊何時不再被程式所使用，那麼就釋放這個塊。
    • 隱式分配器又叫做垃圾收集器(garbage collector).
      • 自動釋放未使用的已分配的塊的過程叫做垃圾收集(garbage collection).
    • Lisp,ML以及Java等依賴這種分配器。

本節剩餘的部分討論的是顯示分配器的設計與實現。

9.9.1 malloc和free 函數

malloc

C標準庫提供了一個稱為malloc程式包的顯示分配器。

#include<stdlib.h>
void* malloc(size_t size);
                    返回:成功則為指針，失敗為NULL

• malloc 返回一個指針，指向大小為至少size位元組的存儲器塊。
  • 不一定是size位元組，很有可能是4或8的倍數
    • 這個塊會為可能包含在這個塊內的任何數據對象類型做對齊。
    • Unix系統用8位元組對齊。
  • malloc不初始化它返回的存儲器。
    • 如果想要初始化，可以用calloc函數。
      • calloc是malloc一個包裝函數。
  • 想要改變已分配塊大小。
    • 用realloch函數
• 如果malloc遇到問題。
  • 返回NULL， 並設置errno。
• 動態存儲分配器，可以通過使用mmap和munmap函數，顯示分配和釋放堆存儲器。

  • 或者可以使用sbrk函數。

    #include<unistd.h>
    
    void *sbrk(intptr_t incr);
    
                        返回:若成功則為舊的brk指針，若出錯則為-1，並設置errno為ENOMEML.

    • sbrk函數通過將內核的brk指針增加incr(可為負)來收縮和擴展堆。

free

程式通過調用free函數來釋放已分配的堆塊。

#include<stdlib.h>

void free(void *ptr);
                返回:無

• ptr參數必須指向一個從malloc,calloc,realloc獲得的已分配塊的起始位置。
  • 如果不是，那麼free行為未定義。
  • 更糟糕的是，free沒有返回值，不知道是否錯了。

這裡的字=4位元組，且malloc是8位元組對齊。

9.9.2 為什麼要使用動態存儲器分配

程式使用動態存儲器分配的最重要原因是:

• 經常直到程式實際運行時，它們才知道某些數據結構的大小。

9.9.3 分配器的要求和目標

約束

顯式分配器有如下約束條件

• 處理任意請求序列。
• 立即響應請求。
  • 不允許為提高性能重新排列或緩衝請求。
• 只使用堆。
• 對齊塊。
  • 上文的8位元組。
• 不修改已分配的塊。

目標

吞吐率最大化和存儲器使用率最大化。這兩個性能要求通常是相互衝突的。

• 目標1:最大化吞吐率
  • 假定n個分配和釋放請求的某種序列R1,R2,R3.....Rn
    • 吞吐率 :每個單位時間完成的請求數。
  • 通過使分配和釋放請求的平均時間最小化 來最大化吞吐率
• 目標2:最大化存儲器利用率
  • 設計優秀的分配演算法。

  • 需要增加分配和釋放請求的時間。

  • 評估使用堆的效率，最有效的標準是峰值利用率(peak utilization)

    • 假定n個分配和釋放請求的某種序列R1,R2,R3.....Rn
      • 有效載荷(payload):如果一個應用程式請求一個p位元組的塊，那麼得到的已分配塊的有效載荷是p位元組。(很有可能會分配p+1個位元組之類的)
      • 聚集有效載荷(aggregate payload):請求Rk完成之後，Pk表示當前已分配塊的有效載荷之後。又叫做聚集有效載荷。
      • Hk表示堆的當前的大小(單調非遞減的)。
    • 峰值利用率為Uk

    

• 吞吐率和存儲器利用率是相互牽制的，分配器設計的一個有趣的挑戰就是在兩者之間找到一個平衡。

9.9.4 碎片

造成堆利用率很低的主要原因是一種稱為碎片(fragmentation)的現象。

• 碎片:雖然有未使用的存儲器但不能滿足分配要求時的現象。
  • 1.內部碎片:已分配塊比有效載荷(實際所需要的)大時發生。
    • 比如:上文中只要5個字(有效載荷)，卻給了6個字(已分配塊)，那一個多的就是碎片.
    • 任何時刻，內部碎片的數量取決於以前請求的模式和分配器的實現方式。
      • 可計算的，可量化的。
  • 2.外部碎片:當空閑存儲器合計起來足夠滿足一個分配請求，但是沒有一個單獨的空閑塊足夠大可以處理這個請求發生的。
    • 外部碎片的量化十分困難。
      • 不僅取決於以前請求的模式和分配器的實現方式，還要知道將來請求的模式。
    • 優化: 需要啟髮式策略來用少量的大空閑塊替換大量的小空閑塊。

9.9.5 實現問題

一個實際的分配器要在吞吐率和利用率把我平衡，必須考慮一下幾個問題。

• 空閑塊組織: 如何記錄空閑塊? (對應 9.9.6)
• 放置: 如何選擇一個合適的空閑快來放置一個新分配的塊? (對應 9.9.7)
• 分割: 將一個新分配的塊放入某個空閑塊後，如何處理這個空閑快中的剩餘部分?(對應9.9.8)
• 合併: 我們如何處理一個剛剛被釋放的塊

9.9.6 隱式空閑鏈表(老本行了)

堆塊(十分巧妙的利用了本該永遠為0的低三位):

• 一個塊由一個字的頭部，有效載荷，以及可能的填充組成。
  • 頭部:編碼了這個塊的大小(包括頭部和填充)，以及這個塊是否分配。
    • 假設是8位元組的對齊約束條件
      • 那麼頭部低三位一定是0。
      • 所以釋放低三位來表示一些其他信息。
        • 即塊大小還是能表示0~2^32(只是必須是8的倍數),非0~2^29。
        • 低三位就能表示是否分配之類的信息。

將堆組織為一個連續的已分配塊和空閑塊的序列。

這種結構就叫做隱式空閑鏈表

• 隱式 :
  • 為什麼叫隱式鏈表。
    • 因為不是通過指針(next)來鏈接起來。
    • 而是通過頭部的長度隱含地鏈接起來。
  • 終止頭部(類似與普通鏈表的NULL)
    • 已分配，大小為零的塊
• 優缺點:
  • 優點:簡單
  • 缺點1:任何操作的開銷都與已分配塊和空閑塊的總數呈線性關係O(N).
    • 放置分配的塊。
    • 對空閑鏈表的搜索。
  • 缺點2: 即使申請一個位元組，也會分配2個字的塊。空間浪費。

9.9.7 放置已分配的塊

當應用請求k位元組的塊，分配器搜索空閑鏈表，查找一個足夠大可以放置請求的空閑塊。

有一下幾種搜索放置策略

• 首次適配
  • 從頭開始搜索空閑鏈表，選擇第一個合適的空閑塊。
• 下一次適配
  • 和首次適配很類似，但不是從頭開始，而是從上一次查詢的地方開始。
• 最佳適配
  • 檢查每個空閑塊，找一個滿足條件的最小的空閑塊(貪心)。

優缺點

• 首次適配
  • 優點
    • 往往將大的空閑塊保留在鏈表後面。
  • 缺點
    • 小的空閑塊往往在前面，增大了對較大快的搜索時間。
• 下一次適配
  • 優點
    • 速度塊。
  • 缺點
    • 存儲器利用率低
• 最佳適配
  • 優點
    • 利用率高
  • 缺點
    • 要完整搜索鏈表，速度慢。
  • 後面有更加精細複雜的分離式空閑鏈表。

9.9.8 分割空閑塊

兩種策略

• 占用所有空閑塊
  • 缺點:產生更多的內部碎片(但是如果內部碎片很少，可以接受)
  • 優點:能使得 空閑塊+已分配塊的數量減少
    • 能加快搜索速度。
    • 有的外部碎片(幾個位元組，很有可能是外部碎片)可能根本放置不了東西，但是卻占用了搜索時間，還不如當內部碎片算了
  • 放置策略趨向於產生好的匹配中使用。
    • 即占用所有空閑塊，內部碎片也很少。
• 分割空閑塊
  • 缺點:更多的空閑塊和已分配塊，搜索速度降低。
  • 優點:空間利用率更高。

9.9.9 獲取額外的堆存儲器

如果分配器不能為請求塊找到合適的空閑塊將發生什麼?

• 合併相鄰的空閑塊(下一節描述)。
• sbrk函數
  • 在最大化合併還不行的情況。
  • 向內核請求額外的堆存儲器。
    • 並將其轉為大的空閑塊
    • 將塊插入鏈表。

9.9.10 合併空閑塊

假碎片: 因為釋放，使得某些時候會出現相鄰的空閑塊。

• 單獨的放不下請求(碎片)，合併卻可以(假性)，所以叫假碎片。

何時合併?

重要的決策決定，何時執行合併?

• 立即合併
  • 定義:塊被釋放時，合併所有相鄰的塊。
  • 缺點:對於某些請求模式，會產生抖動。
• 推遲合併
  • 定義: 一個稍晚的時候，再合併。
    • 比如:上文中的找不到合適空閑塊的時候。

在對分配器的討論中，我們假設使用立即合併。

但要知道，快速的分配器通常會選擇某種形式的推遲合併。

9.9.11 帶邊界標記的合併

Q:釋放當前塊後，如果要合併下一個塊是十分簡單，但是合併上一塊複雜度卻很高。


A:Knuth提出邊界標記。

• 就是是頭部的副本。

• 其實就是雙向鏈表啦。

• 缺點:每個塊保持一個頭部和腳部，浪費空間。
  • 在應用程