Intro

  • Load program : disk -> memory
  • CPU能直接存取的只有Main memory, register
  • Memory unit : addr + read request / write request
  • Main memory可能需要很多CPU cycle : Stall
  • Cache介於Memory與Register之間

記憶體管理的目標

  • 性能
    • 最大化利用記憶體
    • 提升存取速度
  • 保護
    • 防止越界存取
    • 保護資料
  • 靈活性
    • 動態分配
  • Responsiveness
    • Context switch

Address binding

  • Compile-time binding
    • Logical address -> known physical address
    • Prehistoric / Embeded
  • Load-time binding
    • 程式載入memory -> 轉換physical address
    • 靜態分配
  • Run-time binding
    • 硬體支援(MMU)
    • 動態分配 + Virtual memory -> 程式可以在任意address執行

Contiguous allocation

  • Early method
  • 通常拆成兩個partition : OS(通常在高address), 剩下的是Process
  • 每個process分配到一個segment
  • Relocation register : 防止越界存取
    • Base register : 最低address
    • Limit register : 邏輯address上界
    • MMU 動態分配邏輯地址
  • 破碎化問題
    • First-fit 或是 Best-fit
    • Internal fragment : 分配到的chunk太大
    • External fragment : 總空間可以滿足request, 但是分散掉
    • First-fit analysis : 大約 $\frac{1}{3}$ 的memory沒辦法使用 -> 50% rule

Paging

Intro

  • Process -> memory pages (4k/8k)
  • Physical -> memory page frames (4k/8k)
  • Page table
    • 對每個process建映射表
    • Access某個address時, Page table上 Page number -> Frame number
    • Page table base register : PTBR
    • Page table length register : PTLR
    • Page miss -> page fault, 從disk載入
  • Address translation
    • Logical address
      • Page number
      • Page offset
    • MMU自動做 logical address -> physical address 的轉換
  • 問題
    • Internal fragmentation
    • 位址轉換的overhead
      • 透過TLB解決, 如TLB miss才去查page table (TLB為MMU的一部分)
    • Page table占用的空間

Structure

Types

  • Sigle-level page table
  • Multi-level page table
  • Inverted page table : physical -> index
  • Huge pages : larger page size

Two-level paging : 對page table做paging

PTE結構

  • Frame number : 對應page frame
  • Valid bit : 是否在main memory
  • Access bits : RWX flag
  • Dirty bit : 是否被修改過
  • Reference bit : 是否最近用過
  • 其他metadata : tag / hardware info

Shared pages

  • Shared code
  • Libc, Ld…
  • 允許寫入 -> IPC

Swapping

  • 把閒置的Process swap到硬碟裡面, 空出memory給新的process

    • 放入ready queue

  • 上下文切換的成本可能很高 (disk讀寫速度遠低於RAM)

Hashed page table

  • 用於比較大的尋址空間
  • 對Page number進行hash
  • 每個hash value都維護list (解決collision)
  • 每次對Page number hash過後遍歷對應的list