Memory Management

Chapter 6 Memory Management

前一章 | 首頁 | 下一章

• Binding及其時期
• 動態變動分區記憶體管理
  • First-Fit
  • Best-Fit
  • Worst-Fit
  • Next-Fit
• External Fragmentation
• Internal Fragmentation
• Compaction
• Paging Memory Management
• Segment Memory Management
• Paged Segment Memory Management

Binding

1. Def：
   決定程式執行之起始位址
2. Binding之時期
   • Compiling Time(Static Binding)
   • Loading Time(Static Binding)
   • Execution Time(Dynamic Binding)

Dynamic Binding

1. Def：
   在execution time，才真正決定程式執行之起始位址，即程式在執行時可任意變動起始位址
2. 所需要的額外Hardware支援

Dynamic Loading

1. Def：
   在execution time，當某個module被真正呼叫到時，才將其載入到Memory中(if this module is not in Memory Now)
   其主要目的在於想節省Memory空間，發揮Memory utilization
2. eg.overlay(覆載，programmer負擔)屬於Dynamic Loading

Dynamic Linking

1. Def：
   在execution time，當某個module被真正呼叫時，才將其載入並與其它module及library進行外部符號參考之解決(Linking)
   主要的目的是節省不必要的Linking Time

動態變動分區之Memory Management

1. Def：
   OS會依據process大小，找到一塊夠大的連續可用空間配置給此process
   圖示：
   OS會利用Linked List來管理這些Free Blocks，稱為AV(Available) List
2. 配置方式
   (假設process大小為n)
   1. First-Fit
      從AV串列的第一個Block開始找起，直到找到第一個Free Block之size≧n為止。進行配置
   2. Best-Fit
      檢查AV串列中所有Blocks，找出size≧n，且size-n值為最小者
   3. Worst-Fit
      檢查AV串列中所有Blocks，找出size≧n，且size-n值為最大者
   4. Next-Fit(First-Fit的變形)

比較：

	Time效益	空間利用度
☆First-Fit	優	≒優
Best-Fit	差	優
Worst-Fit	差	差

First-Fit之深入分析：

缺點：在經過多次配置後，易於在AV串列前端附近產生許多小小的可用空間(被配置機率低)
然而每次search皆要經過這些區塊，徒增search time
圖示：
解法：Next-Fit Allocation
Next：從上次配置Block之下一個Block開始找起，直到找到第一個夠大的Free Block，即行配置
(通常：AV list以Circular Linked List表示)
例：相關計算題(p7-36例15、19)

結論

無論是First/Best/Worst/Next Fit Allocation，皆存在下列共通問題：

1. 均有External Fragmentation(外部碎裂)問題
   Def：
   在連續性配置方式下，可能記憶體中所有Free Block的size總和≧process需求大小
   但因為這些Free Blocks並不連續
   ∴仍無法配置，形成Memory空間浪費，降低Memory utilization
2. 配置完所剩的極小Free Blocks仍會保存在AV list中，徒增searching time及記錄成本
   解決：OS規定一個ε值，若(Free Block size-process大小)<ε，則整個Free Block全配給此process

Internal Fragmentation(內部碎裂)

Def：
若系統配置給process之Memory空間超過process實際需求，其所產生的差值空間，此process使用不到，其它processes亦無法使用，形成Memory浪費
Summary：

有外部碎裂	有內部碎裂
First/Best/Worst/Next Fit	Paging
segment	Paged segment

External Fragmentation之解決方法

[法一]使用Compaction(壓縮)

1. Def：
   移動執行中的process使得非連續的Free Blocks得以聚集在一起，形成夠大的連續可用區塊
2. 例 (p6-13)
3. 結論：
   缺點：
   1. Optimal Compaction策略很難決定
   2. 需要各process為Dynamic Binding的支援，否則無法移動process

[法二]利用Paging Memory Management解決
[法三](可不寫)將程式拆成Code與Data section，每段有各自的Base/Limit registers來記錄其起始位址/大小
∵size變小∴比較容易裝填，故可降低(不是解決)外部碎裂機率

Paging Memory Management(分頁記憶體管理)

1. Physical Memory視為一組Frame(頁框)的集合。各Frame大小相同
2. Logical Memory(user program)
   視為一組page(頁面)的集合，page size等同於Frame size
3. 配置方式
   假設user program(process)大小為n個pages，則OS只要在memory中找到≧n個Free Frames即可配置。這些Frames不一定要連續(即Paging是採非連續性配置策略)
4. 圖示：
   OS會替每個process準備一個Page Table，記錄各page被載入之Frame編號(或起始位址)
5. Logical Address轉換到Physical Address之過程
   1. CPU送出來的logical Address會自動拆成：
      p：page#
      d：page offset
   2. 依據p查詢page Table取得f
   3. f+d即得physical Address

Paging之Summary

優點：

1. 解決External Fragmentation問題
2. 支援Memory sharing及protection

1. Memory sharing(共享)
   ⇒各process透過本身分頁表對應的相同的頁框，即可達成
2. Memory Protection
   ⇒在分頁表上多加一個"Protection Bit"欄位，值為
   • R：表Read-Only
   • W：表Read/Write皆可
3. 可支援Dynamic Loading、Linking及Virtual Memory製作

缺點：

1. 會有Internal Fragmentation
   (∵program size不見得是page size的整數倍數)
   ⇒Page size越大，則越嚴重
2. 需要額外的Hardware支援，包含
   • Page Table的製作
   • Logical Address→(查表、加法)→Physical Address
3. Memory存取時間較長

Page Table的製作(如何保存Page Table)

[法一]使用Registers保存
優點：速度快
缺點：不適用於page table size太大(entry個數太多)之情況
[法二]使用Memory保存Page Table，同時，利用一個PTBR(Page Table Base Register)保存其在Memory中之起始位址
缺點：需多一次Memory Access動作，用以抓取page table
∴浪費時間
[法三]使用TLB(Transaction Lookaside Buffer)保存部分Page Table經常被使用的項目內容
當要查詢page table時，則先到TLB中search，若Hit，則輸出f(頁框起始位址)，否則(miss)到Memory中取出page table，再取得f
∵TLB是由高速的Associative Registers組成
∴若Hit ratio高，速度幾近[法一]
圖示：
例：[計算題]
若

• TLB Access花20ns
• Memory Access花200ns
• TLB Hit ratio：80%

求有效的(effective) memory Access Time為?ns
Ans：0.8*(20+200)+(1-0.8)*(20+200(抓page table)+200) = 260ns

基礎計算題

例1：page size為1024 Bytes
user program at most 8 pages
physical memory有32個Frames
求(1)Logical Address (2)physical Address各佔?Bits
Ans：
(1)Logical Address
∵程式at most 8 pages
∴p佔3 bits
∵page size = 1024 = 2¹⁰
∴d佔10 bits，Hence，共 13 Bits
(2)physical Address

(∵32個frames)
15 bits
例2：
Page size：256 Bytes
若一個user program大小為16MB，且page table entry占4 bytes
則其page table size為？
Ans：此program有16MB/256 Bytes個pages = 2¹⁶個pages
∴page table size = 2¹⁶個entry * 4 Bytes = 2¹⁸ Bytes = 256 KB
例3：
page size：1024 Bytes
若Logical Address佔32 Bits, physical Address為22 Bits，(if page table entry佔4 Bytes)則

1. process最多有?個pages
2. 最大的page table size為?
3. physical Memory有?個Frames

Ans：

1. (∵1024 bytes)
   ∴p佔32 - 10 = 22 bits
   ∴program at most 2²² 個 pages
2. 2²² * 4 Bytes = 2²⁴ Bytes = 16 MB
3. ∴f佔12 bits
   ∴2¹²個Frames

Page Table size太大之解決

[法一]Multilevel paging(多層的分頁)

將page table再予以分頁
• 例1：single level paging
  假設page size：1024 Bytes
  Logical Address：32 Bits
  page table entry：4 bytes
  ∵d佔10 bits
  ∴p佔32-10=22 bits
  ⇒page table size = 4 byte * 2²²個entries = 16 MB ⇒ Too Large!!
• 例2：Two-Level paging
• 例3：3-Level paging

[法二]Hashing Page Table(雜湊)

• Def：
  將Logical Address中的p(page#)經由Hashing function計算取得Hashing Table(page table)的Bucket Address
• 而在每個Bucket中，皆以linked list串連具相同Hashing address的page number及對應的frame number
  Node structure為：
• 因此，我們會去linked list中search符合的page number之節點。取得f，然後與d相加得出physical address
  圖示：

[法三]Invert Page Table(反轉分頁表)

1. Def：以physical memory為對象，建立一個表格(若有m個Frames，Table Entry有m格)
   每個entry記錄此頁框被哪個process的哪個page所佔用
   以<Process id, Page No>
2. Logical Address→Physical Address圖示
   
   優點：大幅降低page table size
   缺點：
   1. searching Invert page table非常耗時
   2. 無法支援Memory sharing

Segment Memory Management(分段的記憶體管理)