【作業系統筆記1】記憶體層次結構之 實體存儲空間--邏輯存儲空間

cpu <-- Cache（L1緩存，L2緩存） <-- 主存（掉電丢失）<-- 硬碟（虛拟記憶體）（掉電不丢失）

作業系統在記憶體管理方面需要重點完成的目标：

抽象：邏輯位址空間

保護：獨立位址空間

共享：通路相同記憶體

虛拟化：獲得更多的位址空間

實體位址空間：

硬體支援的位址空間，實際硬碟位址

邏輯位址空間：

程式擁有的記憶體範圍（每個程式邏輯位址都是從0x00開始的，和實際實體記憶體存在一定的偏移，由MMU控制映射關系）

整個過程為，CPU需要通路程式的一個位址，MMU根據映射表查詢對應的實體位址，如果有就直接把實體位址告訴CPU；如果沒有，則到記憶體中去查找，找到後，将主存内的内容通過總線給到CPU。

記憶體碎片問題：

①記憶體空間不能夠再被利用

②外部碎片： 在配置設定單元間的未使用記憶體

③内部碎片：在配置設定單元中的使用記憶體

記憶體配置設定方法：

首次适配First fit：（簡單，容易産生更大的空閑塊；缺點：容易産生外部碎片，不确定性）

最優适配算法Best fit：查找一個更加适配配置設定的空閑塊，避免分割大空閑塊，減少外部碎片産生的尺寸

最差适配

記憶體分段尋址方案

段通路機制： 二維，一個段一個記憶體塊，段表由作業系統來建立，不同段的大小不一緻

通路位址需要知道 段号 + 段内偏移

記憶體分頁尋址方案

頁：劃分實體記憶體為固定大小的幀，大小是2的幂 （實體記憶體的頁frames 和 邏輯記憶體的頁pages 大小 要一緻，由MMU控制轉換）

幀（Frame）: 實體記憶體被分割為大小相等的幀，實體位址二進制組(f,o) = 2^n(幀大小) x f (幀号) + o(幀内偏移)

頁（Pages）: 邏輯位址空間被劃分為大小相等的頁，邏輯位址二進制組(p,o) = 2^n(頁大小) x p(頁号) + o(頁内偏移)

Pages Table：由作業系統建立，儲存了邏輯位址 – 實體位址 之間的映射關系，進而可以由頁轉換為幀。

注意： 頁是連續的虛拟記憶體，幀不一定是連續的實體記憶體，不是所有的頁都有對一個的幀，如果CPU通路了不存在對應幀的頁，則會産生一個異常

頁表結構：

每個運作的程式都有一個頁表

PTBR: 頁表基位址寄存器

resident bit ： 駐留位，1說明該頁存在對應的幀，0說明不存在對應的幀

舉例：比如16bit位址的系統，具有32k實際實體記憶體，每頁1024byte，16bit 可以通路的虛拟空間為 64kB

希望空間越小越好，希望速度越快越好

分頁機制的性能問題：頁表可能占用很大，每個程式需要獨立的頁表，當頁表很大時，不可能放入CPU存儲中，隻能放在記憶體中，是以CPU查找位址時，需要首先通路記憶體中的頁表，再通路記憶體位址，需要通路兩次記憶體，時間開銷比較大。

基于邏輯位址頁表的查找方案

頁表的空間和時間問題：

TLB(Translation Look-aside Buffer)： 位于CPU内部，緩存近期通路的頁幀轉換表項

CPU 查找位址時，如果TLB命中，實體頁号可以很快被擷取；如果TLB未被命中，對應的表項被更新到TLB中(該動作可能時CPU完成，也可能時作業系統完成)。

二級頁表： p1(一級頁表) + p2（二級頁表） + o（頁表内偏移）

通過這種方式，以時間來換空間

從時間上，開銷更大，CPU查詢3次才能擷取到位址，

從空間上，這種方式，因為可以将P1總駐留位為0的P2二級表搬出主存，儲存再記憶體中，節省空間

多級頁表： p1(一級頁表) + p2（二級頁表）+ p3（三級頁表） + o（頁表内偏移）

基于實體位址頁幀号的查找方案

反向查找： 通過實際實體幀号 來 查找對應的邏輯位址頁号，這樣可以確定頁表大小可以隻與實體大小相關，而不與邏輯大小相關，節省記憶體開銷。

每一個幀和一個寄存器關聯，寄存器包括如下資訊：

Residence bit： 此幀是否被占用

Occupier：對應的頁号

Protection bit：保護位

舉例：

實體記憶體實際大小為 4096*4096 = 4K * 4K = 16M

頁面大小： 4096Byte = 4K

頁幀數：4096 = 4K

頁寄存器使用的空間（假設8byte/register）： 8 * 4096 = 32kb

頁寄存器帶來的額外開銷： 32k/16M = 0.2% (大概)

虛拟記憶體大小： 任意

基于哈希（hash）查找的方案

哈希函數：輸入是邏輯page num ，程序标志PID，輸出實體frame num

對頁号來做哈希計算，在CPU中隻儲存實體頁幀号，相對傳統頁表來說占用空間小，付出的代價是哈希計算的時間開銷（需要高速和高效的哈希計算函數–硬體實作，以及有效的解決沖突的處理機制–軟體配合）