Chapter 6 Memory Management

前一章 | 首頁 | 下一章

Binding

  1. Def:
    決定程式執行之起始位址
  2. 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 sharingprotection
  1. Memory sharing(共享)
    ⇒各process透過本身分頁表對應的相同的頁框,即可達成
  2. Memory Protection
    ⇒在分頁表上多加一個"Protection Bit"欄位,值為
  3. 可支援Dynamic Loading、Linking及Virtual Memory製作
缺點:
  1. 會有Internal Fragmentation
    (∵program size不見得是page size的整數倍數)
    ⇒Page size越,則越嚴重
  2. 需要額外的Hardware支援,包含
  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高,速度幾近[法一]
圖示:
例:[計算題]

求有效的(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 = 210
∴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 = 216個pages
∴page table size = 216個entry * 4 Bytes = 218 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 222 個 pages
  2. 222 * 4 Bytes = 224 Bytes = 16 MB
  3. ∴f佔12 bits
    ∴212個Frames

Page Table size太大之解決

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

[法二]Hashing Page Table(雜湊)

[法三]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(分段的記憶體管理)