作業系統 CH8 Memory Management

tags: 作業系統 Operating System

Background

• 主記憶體和暫存器為唯二 CPU 可以直接存取資料的地方
• Programs 在硬碟中等待被讀入記憶體中及被執行
• 多個 program 被讀入記憶體中可以改進資源使用率以及反應時間
• Process 在執行期間有可能在硬碟及記憶體之間移動
  

How to refer memory in a program – Address Binding

Compile Time

程式中的資料、參數等必須要有對應的記憶體位置，早期的作法是在編譯期間，就決定要放在哪裡，送進 CPU 時 CPU 就知道該去哪裡存取資料

• Compiler 會將組合語言轉換成實際的記憶體位置(absolute code)
• 若起始地址變更(可能該地址被其他 process 占住)，則需要重新編譯 (recompile)，等於要關閉並重新執行
• ex: MS-DOS .COM format
  

Load Time

• Compiler 不會決定實際的記憶體地址，而是會留一個變數(Base Register)，給出相對位置。程式讀取後(loader，loader 一般假設程式是重新執行，因此會執行非常多動作，如 process 的 control block、記憶體初始化、data structure 的創建等，也就是 program 變成 process 的過程)，才透過該變數決定真正的地址(relocatable code)
• 若 run time 起始地址變更，則需要重新讀取 (reload)
  

Execution Time

• Compiler 將組合語言轉換成 logical-address(i.e. virtual-address)
• 雖然看似 compile time 決定實際地址，但這其實是個虛擬的地址。
• CPU 以為記憶體地址就是 compiler 轉換的位置，但送要求去記憶體存取資料時，中間還有一個硬體單元 MMU(i.e. Memory-Management-Unit, MMU)，會做記憶體地址的轉換，導向正確的實際地址
  • MMU 將虛擬地址 map 為實際地址
  • 由 logical-address 加上 relocation register 產生實際地址
    
• MMU 可以看成 OS 的一部分，但因為使用頻率非常高，所以一般用硬體來實作
• 多數 general-purpose 的作業系統使用這個方法
  

Logical vs. Physical Address

• Logical address 為 CPU 送出的地址，也就是 virtual address
• Physical address 為記憶體看到的真實地址
• Compile time & Load time address binding 的方式，logical address = physical address
• Execution-time address binding 的方式，logical address != physical
• User program(Programming, Compiling…etc) 只管 logical address，永遠不會看到 physical address

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

Dynamic Loading

• 不會將整個程式 load 到記憶體，子程式在 function call 的時候才 load
• 這樣做有更好的記憶體空間使用
  • 未用到 routine 不會被載入記憶體
  • 在大量程式碼使用率較低時(如 error handling code)特別有用
• OS 提供功能，但不會決定 routine 是 dynamic 或 static loading，而是由使用者決定(library, API)
• 在 C 語言中使用 Dynamic Loading 的範例，當呼叫 printf("%f\n", (*cosine)(2.0)) 時，cosine 才會讀到記憶體中。現在 programmer 使用 Dynamic Loading 常常是希望在 run time 決定該使用哪個函式。
  
  

Static Linking

• 函式庫透過 loader 被結合進 program 的 image 當中，compile 的時候，將函式庫加入程式碼
• 每一個用到函式庫的 program 都有一份，浪費記憶體資源，但執行比較快
• 即便改用 Static Linking 加上 Dynamic Loading，因為函式庫仍然需要，因此無法解決程式碼重複複製的問題
  

Dynamic Linking

• Dynamic Linking 在 run time 才去找連結
• 因此只需要一份 library 在記憶體當中
• OS 在 program 中加入 stub，call stub 的時候會向 OS 確認 library 是否在記憶體中
• stub call –> 找 referred lib 是否在 memory 中，沒有的話則 Load 進來 –> 將其位址替換掉，之後就不用經過 stub(relocation)
• 因為在 run time 時期才找函式庫，執行速度較慢
• 在 windows 中為了系統效能，是編譯成 DLL(Dynamic link library)

How to move a program between mem. & disk? – Swap

• Process 可以從記憶體中 swap 到 backing store，稍後再 swap 回記憶體中執行
  • virtual memory 及 mid-term scheduler 使用
  • backing store 是與檔案系統(file system)分離的一塊硬碟空間，透過 OS 的 MMU 直接管理
• 為何需要 Swap
  • 釋放 memory space
  • 讓重要性較低的 process roll out，roll in 重要性較高的 process
• swap back memory location
  • 若 binding address 是在編譯或 load 時期決定，則 swap 回去的記憶體位置要相同
  • 若 binding address 是在 run time 動態決定，則 swap 回去的記憶體位置可以不同
• 程序被 swap 前， OS 會確認是否是閒置的(idle)，除 CPU 執行外，也不能執行 I/O
  • 若想 swap 在 I/O pending 的 process，有以下解法：
    • 乾脆不要 swap 的 I/O pending 的 process
    • 做完的 I/O 先copy 資料到 OS buffers(memory space 不屬於任何 user process)，就能把 process swap 出去，swap 回來時，只要 OS buffer 中的資料複製到 process 的 buffer 即可
• swap 主要時間花在資料的傳輸，transfer time 與資料傳輸的大小成正比，該如何決定被 swap 的 process 非常重要，詳見 CH9 - virtual memory

Contiguous Memory Allocation

相關資料 CS:APP Malloc Lab 解題筆記

Memory Allocation

• Fixed-partition allocation:
  • 每個 process 讀進一個 fixed-size 的 partition
  • Multi-programming 的程度由 partition 的數量決定
• Variable-size partition (Multiple Partition)
  • Hole 定義為一塊連續的記憶體位置
  • 不同大小的 Holes 散布在記憶體當中
  • 當有 process 抵達，會被 allocate 在一個夠大的 hole 裡頭
  • OS 會理 in-use 及 free 的 hole 的資訊
  • 一個被釋放的 hole 能夠跟其他 hole 合併成一個更大的 hole
    

Dynamic Storage Allocation Problem

• 問題：如何從一串 free holes 中找出符合大小 n 要求的 hole
• 解法：
  • First fit - 1st 符合的 hole 就直接配置
  • Best fit - 配置大小最剛好的 hole
    • 可能要搜尋整個 hole list
  • Worst fit - 配置最大的 hole
    • 可能要搜尋整個 hole list
  • First fit and Best fit 無論在速度或空間使用上都比 Worst fit 好

Fragmentation

• External fragmentation (frag space 在 process 外)
  • 全部的 free memory space 是足夠滿足需求的，但卻不是連續的
  • 發生在 variable-size allocation
  • 解法： Compaction
    • 將記憶體空間做 shuffle，在 execution time 讓 free memory 結合成一整塊
    • 只有 binding address 在 run time 決定才能使用
      
• Internal fragmentation
  • 部份被配置到的記憶體沒有被 process 所用
  • 發生在 fixed-partition allocation

Non-Contiguous Memory Allocation — Paging

相關資料 MIT6.s081 Lab: page tables

Paging Concept

• Method:
  • 將 physical memory 切成 fixed-sized blocks 稱為 frames
  • 將 logical address space 切成一樣大小的 blocks 稱為 pages
  • 為了要 run 一個有 n pages 的 program，需要找 n 個 free frames 並載入 program
  • OS 會持續追蹤 free frames，以 page table 建立 logical to physical address 的轉換關係
• Benefit:
  • 允許 process 的 physical-address space 可以是不連續的
  • 避免 external fragmentation
  • 盡可能降低 internal fragmentation
  • 提供 shared memory/pages

Page Table

• 每一個 entry 對應到在 physical memory 中的 page 的 base address
• 每一個 process 有一個 page table，由 OS 直接進行管理
  • Page table 只包含 process 擁有的 pages
  • process 無法存取不是其 space 的記憶體地址
    

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$
  • 由 page number 找出放在第幾個 page，再加上 page offset 得到實際的記憶體位置
• physical address = page base address + page offset
• 如果 page size 為 1kb(2^10) 且 page 2 map 到 frame 5
• 若 logical address 為 13 bits (p=2, d=20)，則 physical address 為？
  • 5 * 1kB + 20 = 1,010,000,000,000 + 0,000,010,100 = 1,010,000,010,100
    
• pages 的總數量不一定和 frames 的總數量相同
  • pages 的總數量決定 process 的 logical memory size
  • frames 的總數量則與 physical memory 大小有關
• 例如： 給定一個 32-bits 的 logical address，36 bits 的 physical address 以及 4KB 的 page size，這代表？
  • page table size = 2^32 / 2^12 = 2^20 個 entries
  • Max program memory: 2^32 = 4GB
  • Total physical memory size = 2^36 = 64GB
  • Number of bits for page number = 2^20 pages -> 20 bits
  • Number of bits for frame number = 2^24 frames -> 24 bits
  • Number of bits for page offset = 4KB page size = 2^12 bytes -> 12 bits

Free Frames

OS 用 free frame list 記下所有 free 的 frame

Page/Frame Size

• page & frame size 由 hardware 定義
  • 通常是 2 的冪次
  • 通常從 512 bytes 到 16 MB/page
  • 最常見的是 4KB/8KB(32bit -> 4KB；64bit -> 8KB)
• Internal fragmentation?
  • Larger page size -> 更多空間的浪費
• 但因為以下原因， page sizes 有變大的趨勢
  • 記憶體、process、data sets 變得更大， process 變大代表要 access 的 page 也越多，若 page size 太小一來找尋的次數增加，二來因為 page 太多很可能部份的 page 放在 disk 中，降低執行及讀取速度
  • 更好的 I/O performance(during page fault)
  • page table 可以比較小

Page Summary

• 使用者看到的是連續性的記憶體，但實際上是分散的
• OS 為每個 process 維持一個 page table
• OS 維持 frame table 管理 physical memory
  • 每個 frame 有自己的 entry
  • 表示 frame 是 free 還是 allocated
  • entry 記 " process id " 和 " page number "

Implementation of Page Table

• Page table 保存在記憶體中
• 因為做 translate 的為 MMU，而 MMU 是硬體單元，所以 Page table 在記憶體中的位置會存在 Page-table base register (PTBR)
  • 記憶 Page table 在記憶體的位置
  • 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 為硬體，所有的 memory entires 可以同時被讀取 (查詢為 O(1))
  • 每一個 entry 對應一個 associative register
• 但 entries 的數量是有限制的，一般來說是 64~1024 左右
  

Translation Look-aside Buffer (TLB)

• 由 Associative Memory 組成，是硬體單元
• page table 的快取被所有的 process 共享
• Context switch 後，因為 process 不同，page table 也不同，一般會 flush 整個 TLB; 另一個解法是在 TLB entry 增加 PID 的欄位，同時符合 page number 及 PID 才叫做 hit (address-space identifiers(ASIDs))
• 因為 context switch 後 TLB 被清空，等於剛開始記憶體地址都要兩步才能取得，是 context switch 拖慢效能的主要原因
  

Effective Memory-Access Time

• 20ns for TLB search
• 100 ns for memory access
• Effective Memory-Access Time (EMAT)
  • 假設 70% TLB hit-ratio: EMAT = 0.7x(20+100) + (1-0.7)x(20+100+100) = 150 ns
  • 假設 98% TLB hit-ratio: EMAT = 0.98x120 + 0.02x220 = 122 ns

Memory Protection

• page table 中，每一個 page 都有 protection bit ，表示 "唯讀" 或 “可讀寫”
• valid-invalid bit
  • Valid: page/frame 在 process 的 logical address space，process 可以讀取
  • Invalid: page/frame 不在 process 的 logical address space ，禁止 process 存取
  • 早期會先創建固定大小的 page table，因為 program 會長，有可能目前 page 的數量少於 page table 的大小，若此時有 pointer 不小心指到該處，就會報 segmentation fault
    • 缺點是可能很多 entry 沒有用到 -> 使用 page table length register (PTLR)，動態變更 page table 的大小。
    • program 配置記憶體以 byte 為單位，而 valid-invalid bit 以 page 為單位，因此需要 memory limit register 紀錄 program 真正使用的記憶體空間，限制無效的存取
      

Shared Pages

• 允許 page 在不同 processes 間共享相同的 Reentrant code(read only)
• Reentrant code (Pure code)
  • 在執行期間不會改變
  • 如 text editors, compilers, web servers, etc
• 在 physical memory 中只需要保存一份 shared code
• Process 保有自己的 private data 以及 code
• 數個 virtual address map 到相同的 physical address
  

Page Table Memory Structure

• Page table 有可能很大而且難以存取
  • 4GB (2^32) logical address space with 4KB (2^12) page
    • 要有 1 million(2^20) page table entry
    • 若一個 entry 4 bytes，則 page table 要 4MB，又因為 page table　是給 MMU 讀取的，MMU 沒有 address translation，所以這 4MB 的空間必須連續，但 physical address 通常很難找到 4MB 的連續空間
  • 需要將 page table 切分成數個較小的 page tables，最好在一個 page size 大小(4KB) 的範圍內
  • 或著將 page table 的總大小限縮
• 解法：
  • Hierarchical Paging
  • Hash Page Tables
  • Inverted Page Table

Hierarchical Paging

將 page table 拆成數個較小的 table，將 logical address space 化成多層 page tables (n-level page table)，但因為多層的結構，實際上總 entry 是增加的。ex: A[1000] -> A[10][100] -> A[10][10][10]

• 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 的連續記憶體
    • 但記憶體存取次數變成 6 倍

Hashed Page Table

• 通常用在 address > 32 bits
• Virtual page number 會被 hash 進 hash table
• Hash table 的大小影響 bucket 的 chain 的長度
• 每一個 hash table 的 entry 包含以下資訊
  • Virtual Page Number, Frame Number, Next Pointer
• 不過 pointer 的結構會浪費額外記憶體。另外，linked-list 搜尋時間為 O(N)
  
• 一個改善的實作是將 linked-list 的 element 設為 array，降低 linked-list traverse 的次數
  

Inverted Page Table

• 不使用 page table，而是改用 frame table， entry 為 PID + Page Number
• 若使用 page table，當 process 數量越來越多， page table 的數量跟著增加
  • frame table 只需要一個，可以事先配置，且使用率接近 100%，減少儲存 table 的記憶體需求
  • 但存取時要搜尋整個 table，增加存取的時間
  • 最麻煩的是難以實作 page 的 sharing，所以這種作法比較少見
    

Non-Contiguous Memory Allocation — Segmentation

Segmentation

• 以使用者的角度來決定如何切割記憶體
• 一個 program 可以看成 segments 的集合，segment 是一個 logic unit，可能包含：
  • main program
  • function, object
  • local/global variables
  • stack, symbol table
  • arrays, etc…

Segmentation Table

• Logical address:(seg#, offset)
  • Offset 可以描述的長度不受 program 長度限制，只受限於系統定義 program 最多可配置多少記憶體有關
• Segmentation table - map 二維的 physical address，每一個 entry 有
  • Base(4 bytes): physical address 的起始位置
  • Limit(4 bytes): segment 的長度
• Segment-table base register (STBR)：儲存 table 的 physical addr.
• Segment-table length register (STLR): 儲存 segment 的數量

Segmentation Hardware

• limit register 檢查 offset 有沒有超過範圍
• MMU 指派一個合適的 base address 給 segment 以配置 memory
  • segment 之間的 physical address 不能重疊
• s 為 table 的 index， d 是 offset，若 offset 超過 limit，就發生 segmentation fault; 若符合條件，與 page table 不同， physical address 為 base + offset 直接相加沒有單位(page) 的概念
• 每一個 segment 的 control 是獨立的，如 heap, stack 允許的空間可能不同
  

Address Translation Comparison

• 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

Sharing of Segments

Protection & Sharing

• Segments 的 protection bits
  • Read only segment (code)
  • Read-write segments (data, heap, stack)
• Code sharing 發生在 segment level
  • Shared memory communication
  • Shared library
• 不同的 segment tables 有相同的 base address 就共享 segment

Segmentation with Paging

基本概念

• 在 logical address space 使用 segmentation，映射到 pages 時再切，compiler 不用管 physical address 怎麼對應
• 在 physical address space 使用 paging，藉由 MMU 做地址的映射，提高記憶體使用的效率
  

Address Translation

• CPU 產生 logical address
  • 交給 segmentation unit 後產生 linear address
  • Linear address 交給 page unit
  • 產生 physical memory address
• Segmentation & pageing units 都由 MMU 處理
  

Example: Intel Pentium

• Logical-address space 分成兩部份
  • 1st: 8K(2^13) segments(private), local descriptor table
  • 2st: 8K(2^13) segments (shared), global descriptor table
  • private & share 會是兩個分開的 segment
• Logical address
  • 一個 process 其 segments 的數量為 2^14 = 16K
  • segment 的大小 <= 2^32 = 4GB
    

Segmentation

• Segment descriptor
  • Segment base address & length
  • 存取權利及優先級
    

Paging (2 Level)

• Page size 可以是 4KB 或 4MB
• 將 32 bits 切成 page directory(outer page table), page tables(inner page table) & offset
  • 每一個 page directory entry 有 indication 用的 flag，代表使用 4KB 或是 4MB 的 page，系統會動態決定，若是 4MB 則 32 bits 只切兩份，後面的 bits 都給 offset
    

範例題目

• physical mem size = 512B 代表 seg offset 為 9 bits
• page size = 32 B 代表 page offset 為 5 bits
• 8 個 segments linear address 前 3 bits 是 segment table 的 index
  現有 12 bits 的 logical address = 448 -> 010|001001000

1. segment index = 010 = 2
2. 對應到 001110110
3. 加上 segment offset 001110110 + 001001000 = 0101|11110
4. 因為 page offset 為 5 bits，所以 page table index = 0101 = 5
5. 對應到 physical frame number = 2
6. 所以最終結果為 0010|11110
   

Reference

1. 清大開放課程 - 作業系統
2. Operating System Concept 9th edition