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