首頁

# Background

  • CPU 可直接存取 register 和 memory，但不能直接存取 disk
  • Process 等待 Loader 將程式從 disk 載入到 memory 中才能執行（執行期間可在 memory 和 disk 間移動）
  • 多個 process 被載入 memory 中以提升資源使用率和反應時間

How to refer memory in a program?

# address binding

  • Compile Time（還不知道地址，只給個變數（BASE））
    • program 改成 symbolic code
    • 地址：compiler 將 symbolic code 轉成 absolute code（絕對地址）
    • 想換起始位置必須要 recompile
  • Load Time
    • compiler 將 symbolic code 轉成 relocatable code
    • 地址：給實際的值，其他是相對 BASE 的地址
    • 想換起始位置必須要 reload
  • Execution Time
    • compiler 將 symbolic code 轉成 logical-address（i.e. virtual-address）code
    • 使用這種方式需要特別的硬體（ex: MMU）
    • memory address translator，從 cpu 送到 memory 才做轉換

# Memory-Management Unit (MMU)

  • 使虛擬位址對應到實體位址
  • 每個由 user process 產生的：logical-addr. + relocation register = 實體地址

# Logical vs. Physical Address

Logical Address Physical Address
Generated by CPU Address seen by memory unit
Also referred to as virtual address Also referred to as real address
Address generated in program Address after address translation
  • compile-time & load-time address binding –-> logical addr = physical addr
  • Execution-time address binding –-> logical addr ≠ physical addr

How to load a program into memory?

# static/dynamic loading and linking

dynamic loading, static linking 和 dynamic linking 是複用其他軟體程式碼的三種機制。特性分別人如下：

  • Static Linking
    Compile 時 library 就加入程式碼
    • 執行比較快但浪費記憶體空間
  • Dynamic Loading (Share library)
    在程式執行期間，當某個模組被真正呼叫到時才將其載入到 main memory 中
    • 需要 OS support
    • 節省 main memory 空間 (即是 dynamic 方法的目的)
    • 節省編譯、組譯、連結所花費的時間 (動態連結函式庫可以單獨重新編譯)
    • 常用於 library 導入
    • 需要 OS 支持，不同 OS 有不同的稱呼：
      • Windows .dll (Dynamic Linking Libraries)
      • Linux .so (Shared Object)
  • Dynamic Linking
    讓 programmer 在程式執行的過程中，動態決定要載入的 libraries
    • 不能跨程式
    • 不會檢查其他程式是否已載入該 library，容易產生重複載入
    • 不用特別的 OS 支持
    • 優點：
      • 節省 main memory 空間
      • 讓 programmer 可以呼叫 loader，比 dynamic linking 更具有彈性，靈活度也更高
    • 缺點：
      • programmer 的負擔，要 programmer 自己規劃而不是 OS 負責
      • 拖長執行時間
      • dynamic loading 是古老的方法，e.g. MS-DOS Overlay files

# Swapping

How to move a program between mem. & disk? Swapping!

  • midterm scheduling：process 從 memory swap out 至 backing store (disk)，稍後又 swap in memory 繼續執行（不同於 context switch）
  • Backing store：獨立於 file system，提供 memory image 直接的存取
  • swap 的目的：
    • 釋放 memory
    • Roll out, roll in: 將低優先權的換出，換優先權高的進來

# Swap back memory location

If binding is done at

  • compile/load time –-> 換回來的 memory addr. 必須一樣
  • execution time –-> 換回來的 memory addr. 可以不一樣

# A process to be swapped == must be idle

  • 狀況：Imagine a process that is waiting for I/O is swapped
  • 解法：
    • 不去 swap 一個 process 等待未決的 I/O
    • 做完的 I/O 先 copy 到 os buffer（memory space 不屬於任何 user process），就能把 user swap 掉，wake up 程式，再將 os buffer data 還給他
  • 大部分的 swap time 落在 tranfer time，transfer time 正比於 memory 被交換的數量

# Contiguous Memory Allocation

# Fixed-partition allocation

  • 每個 process 載入 one partition of fixed-size
  • multi-programming 的程度被 partition 的數量所限

# Variable-size partition（Multiple Partition）

  • 多個不同大小的 hole（一塊連續記憶體）分散在記憶體
  • 當一個 process 抵達，他會被分配在足夠容納他的 hole 中
  • OS 維護 in-use, free hole 的資訊
  • 被釋放的 hole 能與其他的 hole 做合併形成更大的 hole

# Dynamic Storage Allocation Problem

問題：如何從一個 list 的 hole 滿足要求 size n?
解法：

  • First-fit：分配在第一個合適的 hole
  • Best-fit：分配在最小且合適的 hole（必須整個 list 都尋找過）
  • Worst-fit：分配在最大的 hole（必須整個 list 都尋找過）

First-fit 和 Best-fit 比 Worst-fit 在速度與資源的使用好

# Fragmentation

# External fragmentation（發生在 variable-size allocation）

系統中，所有可用空間總和大於某個 process 所需要，但因為這些空間不連續所以無法配給該 process 使用，造成 memory 空間閒置

  • 解法：
    • compaction：移動執行中的 process，使不連續的 free blocks 得以聚集成一塊夠大的連續可用空間
      • 很難在短時間內決定一個最佳的壓縮策略
      • process 必須是 dynamic binding 才可以支援
    • Page memory management

# Internal fragmentation（發生在 fixed-partition allocation）


作業系統配置給 process 的 memory 空間大於 process 真正所需的空間，這些多出來的空間該 process 用不到，而且也沒辦法供其他 process 使用，形成浪費

  • Reducing the page size can alleviate Internal Fragmentation
  • Enlarging the page size helps to reduce the size of the page table

# Non-Contiguous Memory Allocation

# Paging

OS 會將 disk 中的資料分割成固定大小的區塊，稱為頁（pages）

  • 不需要時，將分頁由 memory 移到 disk ；當需要時再將資料取回載入 memory 中
  • 分頁是磁碟和記憶體間傳輸資料塊的最小單位
  • 一個 process 有一個 page table
    • page table 每個 entry 存在 physical memory 的 base address of a page
    • 執行時用 page table 的資訊來把 logical address 轉成 physical address
    • 每一個 process 都會有一個 page table 由 OS 所維護

# Logical address

  • 頁數 (page number): 當作指向分頁表 (page table) 的索引
  • 頁偏移量 (page offset)
  • 若邏輯位址空間為 2ᵐ，而頁的大小為 2ⁿ，則
    • page number = m - n
    • page offset = n
  • 分欄表 (frame table)：紀錄欄是否可用或已被配置

# 效益

  1. 允許程式的 physical-address space 可以不連續
  2. 避免 external fragmentation 但無法避免 internal fragmentation
  3. 提供和共享 memory /pages

# Address Translation Scheme

Physical addr = page base addr + page offset
Logical address 被分成兩部分

  1. page number（p）
    • page table 的 index
    • n bits 表示一個 process 能 allocate 至多 2N2^N 個 pages
  2. page offset（d）
    • 與 base address 結合定義 physical memory address
    • n bits 表示 page size 為 2N2^N

# Example

  • 如果 page size = 1KB = 2^
  • Page 2 對應到 frame 5
  • 13-bit logical address (p=2, d=20)
  • Physical address = frame number * frame size + offset = 5 * (1KB) + 20 = 5120 + 20 = 5140

# Address Translation

page 不需要與 frame 的數量一樣，4KB/8KB 最常使用（32bit -> 4KB；64bit -> 8KB）

  • page 數量：決定於一個 process 的 logical memory 大小
    但越大的 page size 越容易造成 Internal fragmentation
  • frame 數量：決定於系統的 physical memory 大小
  • 增加的好處
    • memory, process, dataset 能變更大
    • 更好的 I/O（during page fault）
    • page table 變小

# Page Table 的製作

  • 法 1：使用 register 保存分頁表每個項目的內容
    • 優點：速度快
    • 缺點：僅適用於 page table 大小較小的情況，太大的 page table 則不適用
  • 法 2：page table 保存在 memory 中，
    • OS 利用 PTBR (Page Table Base Register) 記錄起始位址
    • PRLR (Page-table length register) 紀錄 page table 的大小
    • 優點：適用於 page table size 較大之情況
    • 缺點：速度慢。因為需要存取兩次 memory (一次用於存取 page table、一次用於真正的資料存取)
  • 法 3：用 TLB (Transaction Lookaside Buffer) 保存部份常用的 page table
    • 完整的 page table 在 memory 中
    • TLB 是 full associate cache。
    • 流程：到 TLB 查詢有無對應的 Page Number 存在
      • 若 Hit，則輸出 Frame 的起始位址，只存取記憶體 1 次
      • 若 Miss，則到記憶體中取出 page table 查詢，存取記憶體 2 次

# Structure of Page Table

目的：page table size 太大太稀疏的解決方法

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

    • 問題：分頁表太大，不希望連續的放在記憶體內，也稱向前對映分頁表 (forward-mapped page table)
    • 解：將 page table 再予以分頁，透過 paging page table，只抓所需的 page table 進 memory。只需 1 個 level 1 和 1 個 level 2 在 memory 就可執行
      • 一頁 4kb，32 位元系統
      • 64 位元的系統，不適合階層式架構，因為必須分很多層，導致轉換困難

  • [法二] Hashing Page Table (雜湊)

    • 邏輯位址被雜湊到雜湊表中比對
    • 位址空間大於 32 位元可使用
    • 使用列結串列 (linked list) 處理碰撞

      碰撞 (collision): 雜湊到相同位置

    • hash function collision 的次數等同於 TLB miss 時需要存取記憶體的次數
    • 解
      • logical address 中的 p (page#) 經由 hashing function 計算取得 hashing table (page table) 的 bucket address
      • 每個 bucket 中皆以 linked list 串連相同 hashing address 的 page number 及對應的 frame number
      • 去 linked list 中搜尋符合的 page number 之節點。取得 f，然後與 d 相加得出 physical address

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

    以 physical memory 為對象，建立一個 global page table 給所有 process (若有 m 個 frames，table entry 有 m 格)

    • 每個 entry 記錄此頁框被哪個 process 的哪個 page 所佔用以 <Process id, Page No>
    • 優點：大幅降低 page table size
    • 缺點：
      • searching invert page table 耗時，可用 hash 增加搜尋速度
      • 無法支援 memory sharing

# Segmentation

分段 (Segmentation) 使得記憶體的 logical 配置的看法與使用者一致，配置方式為單一段之間連續配置。
OS 會替每個 process 準備 segment table :

segment 個數不多，OS 內約 10 幾個，segment 數目很少增減，為靜態配置

  • 優點：
    • 無 internal fragmentation
    • 支援 memory sharing 和 protection，且比 paging 容易實施 (有的 Page 可能會涵蓋到不同需求的程式片段)
    • 可支援 dynamic loading 及 virtual memory 的製作
    • segmentation 和 page 為兩獨立觀念，可同時使用
  • 缺點：
    • external fragmentation (但 segments 很少 allocated/de-allocated 所以還好)
    • 記憶體存取時間較長
    • 需要額外硬體的支援

# Segmentation Table

  • mapping 到 physical addr.
  • logical addr. = (seg#, offset) offset 的長度與 physical 長度一樣
  • 每個 entry 有 BASE（4 Bytes）和 LIMIT（4 Bytes）
  • 用 Segment-table length register (STLR) 記錄各段的大小 (Limit)
  • 用 Segment-table base register (STBR) 紀錄各段載入記憶體的起始位址 (Base)

# Segmentation Hardware

  • limit register 檢查 offset 有沒有超過範圍
  • MMU 用指派一個合適的 base addr. 給 segment 以分配 memory

# Paging vs. Segmentation

- Paging Segmentation
Table entry (frame base addr.) (segment base addr. , limit )
base addr frame number * page size 可以是隨意的
length of “offset” 與 page size 一樣 與 physical memory size 一樣

# Segmentation with Paging

  • segmentation 應用在 logical addr. space
  • paging 應用在 physical addr. space

# Address Translation

  • logical address 給 segmentation unit 產生 linear address
  • linear address 給 paging unit 產生 physical address
  • CPU generates logical address
    • logical address 給 segmentation unit 產生 linear address
    • linear address 給 paging unit 產生 physical address

# Example: The Intel Pentium

Logical-address space 被分成 2 部分

  1. segments (private), local descriptor table
  2. segments (shared), global descriptor table
  • Logical address
    • max # of segments per process = 2^
    • size of a segment ≤ 2^
  • Segmentation
  • Paging(2 level)

# Ref Notes

  • Kipper’s Note
  • Chang-Chia-Chi’s Note
  • 陳品媛的筆記
  • Mr. Opengate. OS - Ch7
  • WillyWangkaa’s Note