第九章-----虛拟記憶體 系統中的程序共享CPU和主存資源，但存儲器空間是有限的
虛拟記憶體（virtual memory） 将使用者邏輯記憶體和實體記憶體分開。這在現有實體記憶體有限的情況下，為程式員提供了巨大的虛拟記憶體。 1.實體和虛拟位址 計算機系統的主存被組織成一個由M個連續的位元組大小的單元組成的數組。每位元組都有一個唯一地實體位址(Physical Address, PA)。第一個位元組的位址為0，接下來的位元組位址為1，再下一個為2，以此類推。給這種簡單的結構，CPU通路記憶體的最自然的方式就是使用實體位址。我們把這種方式稱為 實體尋址 。 早期的PC使用實體位址 ，然而現代處理器使用的是一種稱為 虛拟尋址的尋址形式。如下圖：
1、 使用虛拟尋址的過程： 1、CPU通過生成一個虛拟位址(Virtual Address, VA)來通路主存，這個虛拟位址在被送到記憶體之前先轉換成适當的實體位址。2、 将一個虛拟位址轉換為實體位址的任務叫做位址翻譯 。 3、CPU晶片上叫做記憶體管理單元(Memory Management Unit， MMU)的專用硬體，利用存放在主存中的查詢表來動态翻譯虛拟位址，該表的内容由作業系統管理。
虛拟位址空間：CPU從一個有N=2^n個位址的位址空間中生成虛拟位址
實體位址空間：對應系統中實體記憶體的M個位元組
主存中的每個位元組都有一個選自虛拟位址空間的虛拟位址和一個選自實體位址空間的實體位址
2、連續記憶體配置設定
給程序配置設定一塊不小于指定大小的連續的實體記憶體區域.
記憶體碎片：空閑記憶體不能被利用,使記憶體使用率降低
當申請6個字的虛拟記憶體時，雖然堆中有6個空閑的字但卻是在兩個空閑塊中的，是以必須向核心請求額外的連續的6個字的虛拟記憶體。
外部碎片：配置設定單元之間的未被使用記憶體
内部碎片：配置設定單元内部的未被使用記憶體，取決于配置設定單元大小是否要取整
2.1 動态記憶體配置設定
使用動态記憶體配置設定器配置設定虛拟記憶體空間比mmap和munmap要簡便和移植性強
動态記憶體配置設定器維護着一個程序的虛拟記憶體區域——堆，對于每個程序，核心維護着一個變量brk,它指向堆的頂部
配置設定器将堆視為不同大小的塊的集合，每個塊就是一個連續的虛拟記憶體片，要麼是已配置設定的，要麼是空閑的
malloc函數：
程式可以通過調用malloc函數從堆中配置設定塊
malloc函數傳回一個指針，指向一個至少包含size位元組的塊。（一個字是4個位元組）
程式通過調用free函數釋放已配置設定的塊
ptr指向一個已配置設定塊的起始位置。
使用動态記憶體配置設定的原因： 通常直到程式實際執行時才知道某些資料結構的大小。
連續記憶體配置設定的缺點：配置設定給程式的實體記憶體必須連續、存在外碎片和内碎片，記憶體使用率較低
3、非連續記憶體配置設定：
特點：允許一個程式使用非連續的實體位址空間、允許共享代碼與資料、支援動态加載和動态連結
3.1 段式存儲管理（以一個段作為一個配置設定機關（塊），較大）
段位址空間的邏輯視圖：
段通路機制：
3.2頁式存儲管理（以一個頁作為一個配置設定機關（塊），較小）：
3.2.1虛拟記憶體作為緩存的工具 1、 虛拟記憶體被組織為一個由存放在磁盤上的N個連續的位元組大小的單元組成的數組。每位元組都有一個唯一地虛拟位址，作為到數組的索引。 2、磁盤上數組的内容被緩存在主存中。和存儲器層次結構中其它緩存一樣，磁盤(較低層)上的資料被分割成塊，這些塊作為磁盤和主存(較高層)之間的傳輸單元。 3、VM系統通過将虛拟記憶體分割為稱為虛拟頁(Virtual Page， VP)的大小固定的塊來處理這個問題。每個虛拟頁的大小為P=2^p個位元組。 4、類似地，實體記憶體被分割為實體頁(Physical Page，PP)，大小也為P位元組(實體頁也被稱為頁幀)。 一個位址空間的大小由表示最大位址所需要的位數來描述的。例如，一個包含N=2^n 個位址虛拟位址空間就叫做一個n位位址空間。現代系統通常支援32位或者64位虛拟位址空間。 在任意時刻，虛拟頁面的集合都分為三個不相交的子集: ● 未配置設定的：VM系統還未配置設定(或者建立)的頁。未配置設定的塊沒有任何資料和它們相關聯，是以也就不占用任何磁盤空間。 ● 緩存的：目前已緩存在實體記憶體中的已配置設定頁。 ● 未緩存的： 未緩存在實體記憶體中的已配置設定頁。 3.2.2.DRAM緩存的組織結構 在存儲層次結構中，DRAM緩存的位置對它的組織結構有很大的影響。回想一下，DRAM比SRAM要慢大約10倍，而磁盤要比DRAM慢大約100 000多倍。一次DRAM緩存中的不命中比起SRAM緩存中的不命中要昂貴的多，這是因為DRAM緩存不命中要由磁盤來服務，而SRAM緩存不命中通常是由基于DRAM的主存來服務的。而且，從磁盤的第一個扇區讀取第一個位元組的時間開銷比起讀這個扇區中連續的位元組慢大約100 000倍。 因為大的不命中處罰和通路第一個位元組的開銷，虛拟頁往往很大，通常是4KB~2MB。 3.2.3.頁表 虛拟記憶體系統必須有某種方法來判定一個虛拟頁是否緩存在DRAM中的某個地方。如果是，系統還必須确定這個虛拟頁存放在哪個實體頁。如果不命中，系統必須判斷這個虛拟頁存放在磁盤的哪個位置，在實體記憶體中選擇一個犧牲頁，并将虛拟頁從磁盤複制到DRAM中，替換這個犧牲頁。 這些功能是由軟硬體聯合提供的，包括作業系統軟體、MMU(記憶體管理單元)中的位址翻譯硬體和一個存放在實體記憶體中叫做頁表的資料結構，頁表将虛拟頁映射到實體頁。每次位址翻譯硬體将一個虛拟位址轉換為實體位址時，都會讀取頁表。作業系統負責維護頁表内容，以及在磁盤與DRAM之間來回傳送頁。 下圖展示了一個頁表的基本組織結構。頁表就是一個頁表條目(Page Table Entry， PTE)的數組。虛拟位址空間中的每個頁中一個固定偏移量處都有一個PTE。假設每個PTE都由一個有效位和一個n位位址字段組成的。 有效位表明了該虛拟頁目前是否被緩存在DRAM中。 如果設定了有效位，那麼位址字段就表示DRAM中相應的實體頁的起始位址。 如果沒有設定有效位，那麼一個空位址表示這個虛拟頁還未配置設定。若不是空位址，這個位址就指向該虛拟頁在磁盤上的起始位置。
上圖展示了一個有8個虛拟頁和4個實體頁的系統的頁表。 1、四個虛拟頁(VP1、VP2、VP4和VP7)目前被緩存在DRAM中。 2、兩個頁(VP0和VP5)還未被配置設定。 3、而剩下的頁(VP3和VP6)已經被配置設定了，但是目前還未被緩存。 ● 頁命中 考慮一下當CPU想要讀包含在VP2中的虛拟記憶體的一個字時會發生什麼，VP2被緩存在DRAM中。使用位址翻譯技術，位址翻譯硬體将虛拟位址作為一個索引來定位PTE2，并從記憶體中讀取它。因為設定了有效位，那麼位址翻譯硬體就知道VP2是緩存在記憶體中的了。是以它使用PTE中的實體記憶體位址(該位址指向PP1中緩存頁的起始位置)，構造出這個字的實體位址。
● 缺頁 在虛拟記憶體的習慣說法中，緩存不命中稱為缺頁。 下圖展示了在缺頁之前我們的示例頁表的狀态： CPU引用了VP3中的一個字，VP3并未緩存在DRAM中。 1、位址翻譯硬體從記憶體中讀取PTE3，從有效位推斷出VP3未被緩存，并且觸發一個缺頁異常。 2、缺頁異常調用核心中的缺頁異常處理程式，該程式會選擇一個犧牲頁，在此例中就是存放在PP3中的VP4。 3、如果VP4已經被修改了，那麼核心就會将它複制回磁盤 4、無論哪種情況，核心都會修改VP4的頁表條目，反映出VP4不再緩存在主存中這一事實。
5、 接下來，核心從磁盤複制VP3到記憶體中的PP3，更新PTE3，随後傳回。
6、當異常處理程式傳回時，它會重新啟動導緻缺頁的指令，該指令會把導緻缺頁的虛拟位址重發送到位址翻譯硬體。但是現在，VP3已經緩存在主存中了，那麼頁命中也能由位址翻譯硬體正常處理了。下圖展示了在缺頁之後我們的示例頁表的狀态。
3.2.4 置換算法的功能 當出現缺頁異常，需調入新頁面而記憶體已滿時，置換算法幫助選擇被置換的實體頁面
目标
1、盡可能減少頁面的調入調出次數
2、把未來不再通路或短期内不通路的頁面調出
置換算法的分類：
1、最優置換算法（OPT）
基本思路：置換在未來最長時間不通路的頁面
算法實作：
1、缺頁時，計算記憶體中每個邏輯頁面的下一次通路時間
2、選擇未來最長時間不被通路的頁面（實際過程中無法預估）
3、理想算法
2、先進先出算法（FIFO）
基本思路：選擇在記憶體駐留時間最長的頁面進行置換
實作：
1、維護一個記錄所有位于記憶體中的邏輯頁面連結清單
2、連結清單元素按駐留記憶體的時間排序，鍊首最長，鍊尾最短
3、出現缺頁時，選擇鍊首頁面進行置換，新頁面加到鍊尾
3、最近最久未使用算法（LRU）
基本思路：選擇最長時間沒有被引用的頁面進行置換
如某些頁面長時間未被通路，則它們在将來還可能會長時間不會通路
實作：
1、缺頁時，計算記憶體中每個邏輯頁面的上一次通路時間
2、選擇上一次使用到目前時間最長的頁面（最優置換算法的一種近似）
可能的實作方法：
頁面連結清單
1、系統維護一個按最近一次通路時間排序的頁面連結清單，連結清單首節點是最近剛剛使用過的頁面，連結清單尾節點是最久未使用的頁面
2、通路記憶體時，找到相應頁面，并把它移到連結清單之首
3、缺頁時，置換連結清單尾節點的頁面
活動頁面棧
1、通路頁面時，将此頁号壓入棧頂，并将棧内相同的頁号抽出
2、缺頁時，置換棧底的頁面
頁面請求中的缺頁率計算
答：缺頁率 = (頁面置換次數+配置設定給該程序的實體塊數)/要通路的頁面總數；
缺頁數=頁面置換次數+配置設定給該程序的實體塊數；
注意：
1）要通路的頁面總數：不是數值最大，而是看要通路的總次數，例如某程式通路以下頁面0、1、4、2、0、2、6、5、1、2、3、
2、1、2、6、2、1、3、6、2，總共20個數，則要通路的頁面總數是20，并不是6；
2）由于程序開始時，都會給該程序配置設定一定數量的實體塊，當實體塊充足時，直接将要通路的頁面添加進實體塊中就好，并不算頁面置換次數；
3）頁面置換次數：目前要通路的頁面不在記憶體中，且，實體塊已經被占滿，沒有實體塊可用，就需要将實體塊中的頁面按照一定的算法将不用的頁面換出記憶體，把要通路的頁面換進記憶體中。
技巧：在算缺頁率時，可以假設配置設定給程序的實體塊為0，則每進入一個頁面就算一次缺頁，這樣就把配置設定給該程序的實體塊數合并到頁面置換次數中，友善記憶。當把實體塊占完以後，再考慮要不要從實體塊中換出記憶體。
舉例：
若程序通路頁面的次序是1、2、3、6、4、7、3、2、1、4、7、5、6、5、2、1，采用最佳置換算法，情況如下圖：
3.2.5、虛拟記憶體作為記憶體管理的工具
作業系統為每個程序提供了一個獨立的頁表，即一個獨立的虛拟位址空間。
注意：可以将多個虛拟頁面映射到同一個共享實體 頁面上
如下圖所示：
程序i 頁表中的虛拟頁面VP2，和程序j 頁表中的虛拟頁面VP1映射到同一個實體頁面上，稱為共享頁面。
3.2.6.位址翻譯
形式上來說，位址翻譯是一個N元素的虛拟位址空間(VAS)的元素和一個M元素的實體位址空間(PAS)中元素之間的映射，
這裡
下圖展示了MMU（記憶體管理單元）如何利用頁表來實作這種映射。 1、CPU中的一個控制寄存器，頁表基址寄存器(Page Table Base Register, PTRB)指向目前頁表。 2、n位的虛拟位址包含兩個部分:一個p位的虛拟頁面偏移(Virtual Page Offset, VPO)和一個(n-p)位的虛拟頁号(Virtual Page Number， VPN)。 3、MMU利用VPN來選擇适當的PTE。例如，VPN 0選擇PTE 0，VPN 1選擇PTE 1，以此類推。 4、将頁表條目中實體頁号(Physical Page Number，PPN)和虛拟位址中的VPO串聯起來，就得到相應的實體位址。
注意：因為實體頁面和虛拟頁面都是P位元組的，是以實體頁面偏移PPO和VPO是相同的。
頁面命中完全是由硬體來處理的。但缺頁要求硬體和作業系統核心協作完成。
- 利用TLB（快表）加速位址翻譯
在MMU中包含一個關于PTE的小緩存，稱為翻譯後備緩沖器（TLB）
TLB是一個小的，虛拟尋址的緩存，其中的每一行都儲存着一個由單個PTE組成的塊。
用于組選擇和行比對的索引和标記字段是從虛拟位址的虛拟頁号中提取出來的。
如果TLB有T=2^t個組，那麼TLB索引是由VPN的t個最低位組成的，剩餘的位組成TLB标記。
● 多級頁表 用來壓縮頁表的常用方法是使用層次結構的頁表。 用一個具體的示例是最容易了解這個思想的： 1、假設32位虛拟位址空間被分為4KB的頁，而每個頁表條目都是4位元組。 2、還假設在這一時刻，虛拟位址空間有如下形式:記憶體的前2K個頁面配置設定給了代碼和資料，接下來6K個頁面未配置設定，再接下來的1023個也未配置設定，接下來的1個頁面配置設定給了使用者棧。 下圖展示了如何為虛拟空間構造一個兩級也表層次結構:
4.Linux虛拟記憶體區域 下圖記錄了一個程序中虛拟記憶體區域的核心資料結構。核心為系統中的每個程序維護一個單獨的任務結構(源代碼中的task_struct)。任務結構中的元素包含或者指向核心運作該程序所需要的所有資訊(例如，PID、指向使用者棧的指針、可執行目标檔案的名字，以及程式計數器)。
任務結構中的一個條目指向mm_struct，它描述了虛拟記憶體的目前狀态。我們感興趣的兩個字段是pgd和mmap，其中pgd指向第一級頁表(頁全局目錄)的基址，而mmap指向一個vm_area_structs(區域結構)的連結清單，其中每個vm_area_structs都描述了目前虛拟位址空間的區域。當核心運作這個程序時，就将pgd存放在CR3控制寄存器中。 一個具體區域結構包含下面的字段: ● vm_start： 指向這個區域的起始處。 ● vm_end： 指向這個區域的結束處。 ● vm_prot： 描述這個區域内包含的所有頁的讀寫許可權限。 ● vm_flags：描述這個區域内的頁面是與其他程序共享的，還是這個程序私有的(還描述了其他一些資訊)。 ● vm_next： 指向連結清單中的下一個區域結構。 5.記憶體映射 Linux通過将虛拟記憶體區域與磁盤上的對象關聯起來，以初始化這個虛拟記憶體區域的内容，這個過程稱為記憶體映射。 使用mmap函數的使用者級記憶體映射
Linux 使用mmap函數來建立新的虛拟記憶體區域，并将對象映射到這些區域中
1、mmap要求核心建立一個新的虛拟記憶體區域，最好從位址start開始
2、并将檔案描述符fd指定的對象的一個連續的片映射到這個新的區域
3、連續的對象片大小為length個位元組，從距檔案開始處偏移量為offerset位元組的地方開始。
使用munmap函數删除虛拟記憶體區域
munmap删除從start開始的length個位元組的虛拟記憶體區域。接下來如果對已删除的區域引用會導緻段錯誤。
6 C程式中常見的與記憶體有關的錯誤
1、間接引用壞指針
在進行的虛拟位址空間中有較大一部分沒有映射到任何有意義的資料，如果我們試圖間接引用一個指向這些空間的指針，将會導緻段錯誤。
2、讀未初始化的記憶體
雖然bss記憶體位置總是被加載器初始化為0，但是對于堆記憶體卻不是這樣的，常見的錯誤就是假設對記憶體被初始化為0：
3、引用指針，而不是它指向的對象
4、誤解指針運算
忘記了指針的算術運算是以他們指向的對象的大小為機關進行的，而這種大小機關并不一定是位元組
函數目的是通過掃描一個int 數組，找到val第一次時，指向它的指針。
5、引用不存在的變量
6、引起記憶體洩漏
小結: