# Operating System #8

## Logical vs. Physical Address Space

* Logical address: CPU產生的記憶體位置，又稱為virtual address
* Physical address: 實際的硬體上，記憶體單元的位置。
* process中的資料會有一個虛擬記憶體位置，再印射到實體記憶體上面。
* 

## Fragmentation

* 記憶體在配置、歸還的過程中，會產生多個小小的洞(不足以讓一個process使用的空間)，我們稱做**Fragmentation(斷裂)**。
* 斷裂又分為External Fragmentation和Internal Fragmentation兩種：
* 外部斷裂：所有剩餘的空間加起來可以讓process使用，但是它們不連續。使用compaction修復。
* 內部斷裂：每次分配時都會多給一些多的空間。使用page memory management修復。

### Compaction

* 基本上就是電腦磁碟重組在做的事情，搬動記憶體內的檔案，來讓剩餘的空間連續。
* 
* 由上圖可以知道，可以透過最佳化去讓搬運的效率提升，但實際很難做到。

### Segmentation

* 一種支援user view的格式，他將一個process的資料分為多個分段，每個段落印射到實體記憶體上的連續片段。
* 然後使用一個表格去查詢記憶體，格式為<段落開頭,偏差量>，先去找該分段的位置，再往下移動到所需的資料上。
* Segment table中有該分段的起始位置和它的極限位置。
* 優點：沒有內部斷裂，方便資源共享和保護(簡單)。
* 缺點：外部斷裂，需要硬體支援，長的資料讀取時間。

### Paging

* 將空間切成一個一個固定大小的Page。
* CPU產生的Virtual address分為以下兩塊：
* Page number (𝑝): 一個page table的索引值，用於表示資料在實體記憶體中哪個Page
* Page offset (𝑑): 表示資料在Page中的哪裡。
* 
* 優點：沒有外部斷裂，支援資源共享和保護(困難)。
* 缺點：內部斷裂。
---
* 假設一個32位元的電腦，Page size為4 KB。
* entries數量 = 2^32 / 2^12 = 2^20
* 如果entry = 4 bytes，每個process就需要4 MB在page table上面。
* 太大！！１
* 使用其他結構：
* Hierarchical Paging: 階層式的table，第一層查詢第二層，第二層查實體記憶體。
* Hashed Page Table: 將虛擬的page number做Hash後才放到表格中，重複的就用linked list串起來。雖然查詢時要去查list較花費時間，但可以縮小table佔的空間。
* Inverted Page Table: 反過來做一張實體記憶體的表格，透過pid等資訊去找page。

###### tags: `note`