Memory Management

How to refer memory in a program – Address Binding

決定程式起始位置，即程式要在記憶體的哪個地方開始執行。Binding 有 3 個可能執行的時機，compile time, load time 和 execution time。

Compile Time

程式中的資料、參數等必須要有對應的記憶體位置，早期的作法是在編譯期間，就決定要放在哪裡。Compiler 會將組合語言轉換成實際的記憶體位置

在 compile time 就做 binding 的缺點是若起始地址變更(可能該地址被其他 process 占住)，則需要重新編譯 (recompile)，等於要關閉並重新執行

Load Time

Compiler 不會決定實際的記憶體地址，而是會留一個變數(Base Register)，給出相對位置。程式讀取(Load)的時候，確定 memory 哪裡有空位之後，才透過該變數決定真正的地址

缺點為

1. execution time 沒有被呼叫到的模組仍需事先 linking, allocation, loading，浪費時間也浪費記憶體
2. 在 execution time 的時候沒辦法更換位置，需要 reload

Excution Time

Compiler 將組語轉換成 logical address (virtual address)，CPU 去找資料的時候會透過 MMU 將 logical address map 到 physical address

優點: 彈性高

缺點: 程式執行較慢

How to load a program into memory – static/dynamic loading and linking

Static loading

程式執行時就先將所有的 function/libraries 都 load 到記憶體

Dynamic loading

讓 programmer 在程式執行的過程中，動態決定要載入的 libraries

不會將整個 program load 到記憶體，當某個 function 要用到時才會 load 進去記憶體

在大量程式碼使用率較低時(如 error handling code)特別有用

Static Linking

每一個用到函式庫的 program 都有一份，浪費記憶體資源，但執行比較快

Dynamic Linking

Dynamic Linking 在 run time 才去找連結

stub call 找 referred lib 是否在 memory 中，沒有的話則 Load 進來 –> 將其位址替換掉，之後就不用經過 stub(relocation)

需要 OS 支持，不同 OS 有不同的稱呼

• Windows .dll
• Linux .so

Swapping

資料在 Memory 與 Disk 之間互相傳送的動作

為什麼需要 Swap

• 釋放 Memory Space
• 讓重要性較低的 process roll out，roll in 重要性較高的 process

Contiguous Memory Allocation

Fix Partition Allocation

每個 Process 都會放入一個固定大小的 memory 空間中

Variable Size Partition Allocation

• 定義 Hole 為一個連續的記憶體空間
• 記憶體中會有許多不同大小的 Hole
• Process 會被 allocate 到足夠大的 hole 當中

Fragmentation

上述兩種使用記憶體的方法，都有可能會造成空間的浪費，這種空間浪費的狀況稱為 Fragmentation

1. External Fragmentation

   造成雖然有足夠空間可以用，但空間不連續以至於無法讓一個 process 使用，會發生在使用 Variable Size Partition Allocation 的狀況

   Solution: Compaction

   將記憶體空間做 shuffle，在 execution time 讓 free memory 結合成一整塊

2. Internal Fragmentation

   使用 Fix Partition Allocation 時，由於每個 process 都有一個固定大小的空間可以用，但有些 process 用不到這麼多空間，就會造成空間的浪費，這種狀況為 Internal Fragmentation

Non-Contiguous Memory Allocation — Paging

將 physical memory 切成 fixed-sized blocks 稱為 frames，virtual memory 切成一樣大小的 blocks 稱為 pages，建立 page table 去對應每個 page 到 frame 的位置，以此就可以利用零碎的記憶體空間

優點:

• External Fragmentation
• 降低 Internal Fragmentation 的發生狀況

Page Table

• 每一個 process 有一個 page table，由 OS 直接進行管理
• page table 只包含 process 擁有的 pages
• process 無法存取不是其 space 的記憶體地址
• 不同 Process 下只要某個 page 對應 frame number 給一樣，就可以做到 memory sharing

Address Translation Scheme

Logical address 分成兩部份

• Page number ( p )
  • 為 page table 的 key 值，對應 value 為 page 在 physical memory 的 base address
  • N bits 代表一個 process 最多可配置 
    $2^N$  個 pages 的記憶體，限制住 program 可 allocate 的大小 (例如 32-bits 的電腦，一個 program 最多 allocate 4GB 左右的空間)
• Page offset ( d )
  • 與 base address 結合定義 physical memory address
  • N bits 代表 page size 為 
    $2^N$

所以 Physical address = page base address + page offset

Implementation of Page Table

• Page table 保存在記憶體中
• Page table 在記憶體中的位置會存在 Page-table base register (PTBR)
• PTBR value 存在 Process Control Block 裡頭(PCB)
• 在 Context switch 時更新 PTBR value (除了 CPU 的 register，MMU 的 register 也要重新 load)
• 每一次讀取記憶體實際上動作有兩步，第一步先找到 Page Table，mapping 後才到真實的記憶體地址存取資料
• 兩步讀取的動作可以由 Translation Look-aside Buffers (TLB) 解決，簡單來說是一個 cache，若 cache hit，則可以縮短為 1 步，以 Asscociative Memory 實作

Asscociative Memory

Associative Memory 為硬體，會記錄之前讀取過的 Page 對應到哪個 frame，這樣下次如果有用到重複的 page 時就可以很快知道對應到哪個 frame，查詢速度為 O(1)

Translation Look-aside Buffer (TLB)

• Context switch 後，因為 process 不同，page table 也不同，一般會 flush 整個 TLB (清空)
• 因為 context switch 後 TLB 被清空，等於剛開始記憶體地址都要兩步才能取得，是 context switch 脫慢效能的主要原因

Shared Pages

• 允許 page 在不同 processes 間共享相同的 pure code (read only)(e.g. text editor, complilers)
• 在 physical memory 中只需要保存一份 shared code
• 數個 virtual address map 到相同的 physical address

Structure of Page Table

如果我們要做一個 4GB (

$2^{32}$) logical address space, 4KB (

$2^{12}$) page size 的 Page Table，則我們需要

$2^{20}$ 個 entries，每個 entry 如果是 4B，則總共就需要 4MB，而這個空間是需要給 MMU 做讀取的，又沒有裝置可以幫 MMU 做 address translation，因此空間必須為連續，因此這空間若太大，就會 memory 就會很難空出來

Solutions

1. Hierarchical Paging

   將 page table 拆成數個較小的 table，將 logical address space 化成多層 page tables

   64-bit address

   • 如果切成 42(p1) + 10(p2) + 12(offset)，outer table 需要
     $2^{42}$ X 4B = 16TB 的連續記憶體
   • 如果切成 12(p1) + 10(p2) + 10(p3) + 10(p4) + 10(p5) + 12(offset)，outer table 需要
     $2^{12}$ X 4B = 16KB 的連續記憶體

2. Hashed Page Table

3. Inverted Page Table

Non-Contiguous Memory Allocation — Segmentation

• 以使用者的角度來決定如何切割記憶體
• 分成不同 object 去儲存，並且 segmentation 的大小不會固定，跟 page 的固定大小不同，e.g. 一個 array 我們用一個 10KB 的 segment 去做儲存

Segmentation Table

Segmentation Table 中含兩個值

• Base(4 bytes): physical address 的起始位置
• Limit(4 bytes): segment 的長度

Segmentation Flow

1. limit register 檢查 offset 有沒有超過範圍
2. MMU 指派一個合適的 base address 給 segment 以配置 memory
3. s 為 table 的 index， d 是 offset，若 offset 超過 limit，就發生 segmentation fault; 若符合條件，與 page table 不同， physical address 為 base + offset 直接相加沒有單位(page) 的概念

Comparison of Page and Segment

• Segment
  • Table entry: segment base address, limit
  • Segment base address 可以為任意值
  • Offset 的最大值等同於 physical memory size
• Page
  • Table entry: frame base address
  • Frame base address = frame number * page size
  • Offset 的最大值等同於 page size

Segmentation with Paging

• 在 logical address space 使用 segmentation，轉換到 linear address (假空間)，之後再將每個 segment 切成很多個 pages (固定大小)，並投射到 physical address
• 在 pshysical address space 使用 paging，藉由 MMU 做地址的映射，提高記憶體使用的效率

Address Translation

• Segmentation & paging units 都由 MMU 處理