OS 筆記 - Ch8 Memory Management

Posted on 2019-10-31 Edited on 2020-03-07 In OS Views: Views: Disqus: Word count in article: 11k Reading time ≈ 10 mins.

Ch8 Memory Management 的整理筆記

Background
Swapping
Contiguous Allocation
Paging
Segmentation
Segmentation with Paging

Background

所有東西都在 memory 裡面，即使有 cache 也都是暫時的
memory management 要坐到保護，以及支援 Multiple programs，甚至跨到 Disk

How to "refer" memory in a program

這三個看圖就好 ...
- Compile Time : Compile 時間
- Load Time : Load 到 Memory 時間
- Execution Time : 執行時間
  - Dynamic Loading, Dynamic Linking 也在這
- Address binding 在這三個都可能發生

Timing

Address Binding : 程式將來要在 Memory 的那個 address 執行。
- 在 Compile Time 決定
  - 由 Compile 決定 Physical address 在哪裡
  - Memory 想要搬動程式 → 就完ㄌ，要 Recompile
    - 為何要搬來搬去 ? Run time 才知道要跳到哪，以及 swap in 的時候原本位置可能被別人佔住了
- 在 Load Time 決定 ( Linking Loader 做 Binding )
  - 用 Base Reg 做相對對址 (起始位置)，
    - 真正的 addr 就是 Base + 相對位址
  - Load 時重新決定 ? OK ! 免 Recompile
  - Run Time 重新決定 ? GG !
    - 需要 Reload the code
  - 其中有分 Relocation 修正和 Linking 修正
    - Relocation 修正 : 修改 Base Reg
    - Linking 修正 : 有些副程式或者 Library 的 memory segment 可能是分開的
      對於此，如果有移動的話就會由 Linking Loader 修正
- 在 Execution Time 決定
  - 完全都是相對位置
  - 使用 logical-address (virtual-address) -> 但是要 MMU 支援，Hardware Support
    - MMU 就是一個硬體，後面會簡單介紹
- 現在基本上都這樣做
Logical vs. Physical Address
- Logical address 就是 "虛擬位址"，又稱 Virtual address。
  程式雖然指定了要去讀某個地方，但實際上是被 OS 騙的，不會真的去讀那個地方。
  當然，相對的，OS 也會給他相對應的資料讓他正常運作，
  一切都是為了更好的去做記憶體管理。 ~~為了蔚藍清淨世界 (青き清浄なる世界のために )~~
- 如果是 Compile-time & Load-time Address binding
  - logical addr = physical addr
  - Execution-time address binding 的話當然就不是

How to "load" a program into memory ?

Dynamic Loading
- 整個 Program 不一定全部都會用到，全部 Loading 很浪費
  - 像是很多 debug 用的 error handling code 就不是一定用到
  - 所以做成 Dynamic Loading
    - A routine is loaded into memory when it called
- 並不是 OS 幫你決定哪些是 Dynamic Loading 的 function call
  - 是使用者自己決定的 !
  - ex : C語言中使用 <dlfcn.h>

Dynamic Loading

Static Linking
- libraries are combined by the loader into the program in memory image
  - 你 C程式 Compile 完就會把所有 Lib Link 到程式中
    這是沒辦法的，不然沒辦法執行阿，一定要有那些 Lib
- Static linking + Dynamic loading
  - 無法避免還是要 duplicated code
Dynamic Linking
- 新的解決方式 !
- Lib 定義也不會改系統存一份就好
- Run Time 再去找
- 像是 DLL 檔案 in Windows
- Compile 時要告訴 Linker 下個 flag 說要用 static 還是 dynamic
- Dynamic Library 可以用在兩種 Linking 上，Static Library 就只能 Static

Memory-Management Unit

Hardware device that maps virtual to physical address
實際上的功用就是負責把 Logical address 轉成 Physical address。
是一個 Hardware。
以前的 MMU 可能是負責做在主機板上，不過現在嘛，CPU 已經算是一個大單元了
廠商可能直接把 MMU 整合在 CPU 裡面，但實際上細分的話邏輯運算單元跟 MMU 還是分開的。
TLB 是 MMU 的好朋友。就像這張圖一樣。
- TLB 後面會介紹，簡單來說就像是 MMU 的 Cache。

MMU

Swap

Backing store : 就一塊空間 (a chunk of disk)，跟 File system 是分開的
跟 Binding Address 關聯 :
- 如果你在 Compile / Load Time 就 Binding :
  - 你一定要 Swap 回相同位置不然會出問題
- 如果你在 Execution Time (用 Base Reg 等的) :
  - OK !
A process to be swapped == must be idle
- 也就是不能在做 I/O。雖然在 waiting queue，但他在做 I/O，如果做 Swaping ... 就會寫錯。
- 如果他是在 Sleeping waiting queue 就沒問題
- Solution :
  1. 做完 I/O 再 Swap
  2. 要搬的那些先由 OS Buffer 代管
搬誰，很重要 : 如果剛搬過去，OS 又需要他了，尷尬 (CH9 Algo)

Contiguous Memory Allocation

Fixed-partition allocation :
- 停車場，每個停車格都一樣
- degree of multi-programming 很好管理
- 問題 : 路邊停車有人一次得停很多格亂停到別人那邊
Variable-size partition :
- 很多洞可以找洞塞
Dynamic Storage Allocation Problem
- First-fit : match 到的第一個
- Best-fit : 最佳 match 解
- Worst-fit : 最ㄎㄅ的，找最大的洞
  - 我先用掉大的就會產生剩餘的小的，搞不好別人就剛好可以塞進來
- 比較 : First-fit 最快找到，另外兩個要 O(n) 全 parse

但是一定不可能會把記憶體剛好都弄滿，於是出現 Fragmentation 問題

Fragmentation

External fragmentation
- 每個格子外，會有零碎的記憶體區塊
- Occur in variable-size allocation
Internal fragmentation
- 每個格子內，會有零碎的記憶體區塊
- Occur in fixed-partition allocation
真要說，也是有解法 : **Compaction **(壓縮)
- 定期清理整理，壓縮
- 其實不會那麼常用，反正後面有 Paging 解法了 ...

External 與 Internal

Page

Page Concept

在 Physical Memory 切割 fixed-sized blocks，叫做 Frames
在 Logical address space 切割同大小 blocks ，叫做 Pages
Keep track of free frames

Benifit :

可以不連續的使用記憶體
shared memory : Share page 很方便做到
Avoid external fragmentation，Limit internal fragmentation

Page Table

每個 Entry 都對應到 base address of a page in Physical Memory。
每個 Process 都有一個 Page Table
Logical address 由 Page number 和 Page Offset 組成
- Page number 就是 page table 的 index
  也就是說，假設這邊有 n bits，那這個程式最多只能用 2^n 個 page 組成
  你用超過這麼多 page ... 會無法表示
- Page offset : 有時候只是要 page 裡面的某些片段，offset 可以拿來表示你要哪個 byte address
轉換過程 : 先查好 Page Number 對應到的 Frame Number
然後把原本 Logical address 的 Page number 的部份替換成 Frame number
就是 physical address。

Page Table

會有 Free Frame List 來記錄，這樣我們需要的時候就能直接分配
相對的，Free 掉一個程式，就把他用的 Frame 加入這個 List 即可。
Page / Frame Size : 通常都是 4KB 或 8KB。有點經驗法則。
- 如果太大 ? 那可能 internal fragmentation 會有點嚴重。
- 如果太小 ? 那我要花很多 entry 去紀錄，也就是 Page Table 會很大
  而且程式會因此跳來跳去，要 access 很多，也要很頻繁從 Disk 抓
其實有 Frame table 的存在，只是 ... 基本上沒啥用
- 比較有用的也只有 invertible page table
Implementation
- Page table 在 Memory
- Page table 有個 base register (PTBR) : 指到 Page table 的實體位置 (physical memory address)
  - 這東西在 PCB 會記錄起來 (用一個 reg 紀錄)
  - Changing the value of PTBR during Context-switch
    - 應該是指 PCB 裡面的內容需要替換，所以 PTBR 這格會被換成另一個 Process 的 PTBR
  - 因為 PTBR 的存在，所以每次 memory reference 就需要 2 次的 memory reads
- " 2 次" 這個問題，我們使用 TLB ( Translation Look-aside Buffers ) 來做改善。

TLB

Associative Memory
- 也是個 Table，但是是很快的 memory。
- 他設計成可以一次查詢所有 Entry，可以 O(1) 而非 O(n)
- 故，設計複雜，價格昂貴，不可能所有 page table 都塞進去
TLB 就像是 MMU 的 Cache
做 Context Switch 時，TLB 會被 flush。總不能混用別人的 Frame ...
- 或是也可能在 TLB 加一個欄位，寫 PID，但通常不會這樣做，不然又要再浪費空間，又要花時間比對
- Flush 之後 ... 恩，下個 process 上來其實也會瘋狂 miss (Table look up)
  所以又要到填滿了之後才會有更好的效率

What is ASID ?
全名 Address Space ID，以下節錄一篇文章中的解釋

還有可能進一步提升TLB的性能嗎？有沒有可能根本不flush TLB？

當然可以，不過這需要我們在設計TLB block的時候需要識別process specific的tlb entry，也就是說，TLB block需要感知到各個進程的地址空間。

為了完成這樣的設計，我們需要標識不同的address space，這裡有一個術語叫做ASID（address space ID）。原來TLB查找是通過虛擬地址VA來判斷是否TLB hit。

有了ASID的支持後，TLB hit的判斷標準修改為（虛擬地址＋ASID），ASID是每一個進程分配一個，標識自己的進程地址空間。

TLB block如何知道一個tlb entry的ASID呢？

一般會來自CPU的系統寄存器（對於ARM64平台，它來自TTBRx_EL1寄存器），這樣在TLB block在緩存（VA-PA-Global flag）的同時，也就把當前的ASID緩存在了對應的TLB entry中，這樣一個TLB entry中包括了（VA-PA-Global flag-ASID）。

有了ASID的支持後，A進程切換到B進程再也不需要flush tlb了，因為A進程執行時候緩存在TLB中的殘留A地址空間相關的entry不會影響到B進程，雖然A和B可能有相同的VA，但是ASID保證了硬件可以區分A和B進程地址空間。

Effective Memory-Access Time

假設題目

20 ns for TLB Search
100 ns for memory access
Effective Memory-Access Time (EMAT)
- 70% TLB hit-ratio : EMAT = 0.70 x (20 + 100) + (1-0.70) * (20+100+100) = 150 ns
- 98% TLB hit-ratio : EMAT = 0.98 x 120 + 0.02 x 220 = 122 ns
- 註 : (20+100+100) 是兩次 Memory access (前面提的 PTBR)，20 是踩 TLB。
  但是私自認為 20 應該不用算進去，如果說查 TLB 和 Page Table 是同時的話。

Memory Protection

每個 Page Table 通常會再加一個 Protection bit，可以當作 valid，或者是 read write 等
不過一般都是當 valid-invalid bit
- 有可能你 malloc 先幫你開了，但你還沒用到，畢竟 Process 是會成長的
- 另外，Virtual Memory 章節 : 有可能他已經被 Swap out 了，所以不能用
- 或是 OS 動手腳，不給你權限
- 程式隨時在變，也有可能中間某個 page 突然不要了，直接標記 invalid
可能 Page Table 很大但後面都沒用到 ...
- Use page table length register (PTLR)
  紀錄長度，方便檢測
- 另外這個 Length，有時候可能是我們用到了 "第N個 Page的第80%"
  單位是 byte，長度可以表示的更細

Shared Pages

對於一些 Pure code (Reentrant code)(Library 之類的)，很好用
Two (several) virtual addresses are mapped to one physical address

Page Table Memory Structure

有時候很難 allocate 一塊空間去放 Page Table
- 4G 的 Memory + 4KB 大的 Page
  - 2^20 個 entry，每個 entry 4 bytes，4MB 的 Page Table !
  - 但是我們不一定有這麼大的連續空間 ...
Solutions:
- Hierarchical Paging
- Hash Page Tables
- Inverted Page Table

Hierarchical Paging

我們乾脆把 Page Table 做 Page Table 吧。
舉例 : Two-Level Paging
- 下面這張圖，第一層有 2^10 個 Entry，每個 Entry 對應到一個小 Page Table
- 每個 Page Table 大小當然也會跟著變小。
- 這樣我們就指要找到 2^10 個連續的 1KB 大小的記憶體就行了~
- 然而，這樣子做的目的在於 : 更好的分配記憶體空間。而非減少 Page Table 所佔用空間
- 缺點 : 3 次 Memory Access

是說，如果是 64 bits Address ?
- 假設 42(p1) + 10(p2) + 12(offset)
  - 2^42 個 entry，2^42 * 4B(每個entry大小) = 16TB ...
    - 所以即使你想要把 64 全部拿來做，你根本沒這麼大的記憶體
- 換成 12 + 10 + 10 + 10 + 10 + 12 好了
  - 2^12 * 4B = 16KB 的連續 Memory
  - ... 問題是要 6 次 Memory Access，一般通常做到 4 就受不了了

Hash Page Tables

把 Virtual page number 做 hash，變成 entry。重複的話跟 hash 一樣，直接串在 bucket 後面
經濟效益 :
- 不管 virtual address 空間，反正是 hash
- Page table 你可能剛好用第一個 entry 和最後一個 entry (有點極端)，但你整張表還是要建；
  hash table 的話，沒用到的就不存在於此 hash table 中。
  真的很少的話，其實找 bucket 後面的也不會到說很久
缺點 :
- Pointer 的浪費
- 走 Linked-List 有點浪費時間

改善 : 如果採這樣的改善方式，每次走一個 Node 就能直接掃多個小 entry
不過實做上可能有些困難

Inverted Page Table

管理好多 Page Table 太麻煩，直接做個管理 Frame 的 Frame Table
每個 Entry (index) 就代表哪個 Frame，取而代之，那格裡面儲存的是 PID 和 Page Number。
優點 : 只要 allocate 一次，反正 Frame 的數量，Size 並不會變。
- virtual address bits 數量通常遠大於 physical address
  他的 Size 跟 physical memory size 有關所以表會小一些
缺點 : 你要找超久，Worst case 要找整張 (也許能用 hash 解決一些)
主要問題是很難做 share memory

Segmentation

基礎概念

fixed-size 的概念
A program is a collection of segments
- main program segment
- function segment
- ... etc，可以個別去增長
external fragmentation 會比較嚴重
Logical address: (seg#, offset)
- offset has the SAME length as physical addr.
  - 因為現在沒有 Page 大小限制了，可以無限增長，甚至整個 physical memory 大小都可能
Segmentation Table : maps two-dimensional physical addresses;
each table entry has :
- Base (4 bytes): the start physical addr
- Limit (4 bytes): the length of the segment
  - 長度任意，所以要有一個限制 (Compiler 或 OS 幫你決定)
Segment-table base register (STBR) :
- the physical addr of the segmentation table
  你這個 Table 總也有個位置要記起來，讓 OS 可以查
Segment-table length register (STLR) :
- 因為這個 Table 可能放非常多 segment，所以也要紀錄一下長度(當然只要一個reg就好)

流程

CPU 請求 logical address
查詢在 table 的哪個 entry
查詢 entry 內的 limit 欄位，看一下 logical address 的 offset 是否有超過。

超過代表非法存取，丟 trap (addressing error)；
- Physical address cannot overlap between segments
沒超過則拿 segment base address 去組合成真正的 physical address
→ 成功 access

Protection bits associated with segments
- 可以設定 Read-only segment code
  - (code section)
- Read-write segments
  - (data section, heap, stack)
Code sharing occurs at segment level
- 兩個程式，在 segment table 的某一 entry 都記錄同個 limit 和 base
- Shared memory communication
- Shared library

Segmentation with Paging

我覺得偏補充，如果是考試生，真的覺得不好懂的話就別搞懂了，幾乎沒考過
先把 Process 做 Segment，再把 Segment 做 Paging 的一個神奇轉換方式。
以下舉例，部分使用 Intel Pentium Segmentation 實例做解釋
可以先看這張圖簡單理解一下，下面雖然分段解釋，但內容偏多，有點散。

第一段，CPU → Descriptor Table : Logical address
CPU 仍然請求他的 Logical address，這點並不變。
- Logical address 的組成是 Selector + offset
  - 這個 Logical address 的長度可能超過 32，舉例，Selector 16 bits，offset 32 bits
- Selector 的組成是
  - Segment number (13 bit) + Table Indicator (1 bit) + Protection info (2 bit)
    - Segment number 就像是 index 一樣的存在
    - 所以，其實系統可以表示 2^13 個 segment。
      加上 TI 的話，變成 14 bits，實際上可以表示 2^14 個，一半 share 一半不 share
  - Table Indicator (TI) : 紀錄該用 GDT/LDT，0 就是 share，1 就是 private
    - TI 為 0 時，會取用 GDT 中的 Segment descriptor
      - GDT = Global descriptor table，shared segment
      - GDT 的第 0 個位置實際上是不會被用到的，
        故把 index 和 TI 都設 0 的話就是 Null Segment，去存他會被丟 exception
    - TI 為 1 時，則會取用 LDT 中的 Segment descriptor
      - LDT = Local descriptor table，private segment
  - Requested Privilege Level (RPL) : Protection info，表示 0~3，RWX (讀寫執行)

第二段，Selector 查出要找 share / 不 share 的 Descriptor Table ( GDT 或是 LDT)，
然後根據 Segment number (index) 去找 Table，得知 Segment descriptor。
從這東西可以再提取出 Base address，把 Base address + offset 得到 Linear address (32bits)。
- 簡單來說的話是上面這樣啦，實際上還有很多細節。以下順便說說
  1. Segment Descriptor 是 8 bytes，對，不要懷疑
  2. 這是 Segment Descriptor 的結構，兩排，所以 8 bytes 沒錯。
  3. Base Address 雖然分開三個地方放，但是組起來的話仍然是 32 bits，完美。
    Offset 根據上一段所說明也是 32 bits，所以相加也是 32 bits，完美完美。
    產出的東西我們叫他 Linear address，因為他什麼也不是，反正就是個中間值
  4. 其餘欄位的介紹大概是這樣，看看就好。
  5. 我個人是把 Descriptor Table 想像成 Segment Table，只是記錄的東西有點不太一樣。
    可以直接當作 Segment Table 裡面有個 Data Structure 反正會幫我們產 Base Addr 就行啦 !
  6. 這中間有很多邊界問題，如何設計才能不讓程式隨意 access 其他區段，是 MMU 要去自行處理的
第三段，假設是 Two-Level Paging，就到我們熟悉的部分 ... 分段，查 Page Table
- 這邊說到，第一層的 Page Table (Outer page table) 可以拿來指到多種 Table。
  你可以跟平常一樣，指到一個小的第二層的 page table
  (一個 2^10 entry 的 table，對到很多個大小為 4KB 的 Page)
  也可以直接拿去指一塊 offset 很大的 Page
  - 想想，其實一個小 Page table 能表示的 Physical memory 就是 2^22，其實也剛好就是這塊大 Page 的 4MB 大小。
- 當然，會有一個 bit 在第一層 Page Table 那邊。
Example
- Physical Memory 512 B = 2^9 → 灰色部分 9 bits 合理 (灰色部分是 Segment offset)；
  Page Size 32B = 2^5 → offset 5bits (在 Liner 轉 Page 分割才要取)
  8 Segments = 2^3 → 3 bits 在控制要到哪個 segment。
- 題目給 Logical address 448 (hex) = 010001001000 (binary)(前面自己補0)
  - 010 = 2 (dec)，找第二個 entry，得到 001110110 (Base address)，和 001001000 (Segment offset) 相加，得到 010111110 (Linear address)。
- 010111110 (Linear address) 可以再根據 Page Size 的 offset 5bits 此資訊切割。
  所以 Page number 是 5，查 Page Table 得 2，這樣 Physical address 就是 001011110

Review

P.17

3 types of address binding?
- compile-time
  - 越簡單的越快，MMU 也要時間，簡單的 Device 可能會選擇這個
- load-time
- execution-time
logical address? physical address ?
- virtual → physical mapping ?
dynamic loading ? static loading ?
dynamic linking ? static linking ?

P. 42

memory frame? page? typical page size?
page table? virtual → physical translation?
What is PTBR register? When to update it?
Memory reads # for each reference?
HW support for paging speed?
- associative memory
- TLB

P.58

memory protection by page table?
- valid, invalid bits?
page table memory structure?
- hierarchical → 2-level, 3-level, etc
- hash table → linked list
- inverted page table
How are pages shared by different processes?

P.75

Segmentation vs. Paging?

Paging Segmentation

Length Fixed Varied

Fragmentation Internal External

Table Entry Page number -> Frame Number Seg ID → <base addr, limit length>

View Physical memory User progam
Paged segmentation ?
補充
- - A page fault is signaled by hardware ! ( 洪 : 只要是 singal 87% 都是硬體造成 )
    - The computer hardware traps to the kernel
  - TLB Miss -> TLB exception -> can also page fault ( 非 result in )
    - 當TLB是由軟體實作時, TLB miss會產生 "TLB exception" 給 OS,
      然後OS會去處理之後的 page table access (by PTT leosnake，不確定正確性)
  - TLB miss 是 OS 處理，Page fault 也是 OS 處理
    如果非 MIPS 系統軟硬體都可以處理 (偵測時就都是硬體)
- Page Fault 處理流程
- Page Fault 是一種 exceptions，其中又是 Exceptions 的 Fault 類別
- swap out 不盡然是必要的！需視 victim page 是否曾被修改，利用 dirty bit 來判斷，節省不必要的 I/O 動作。

	Paging	Segmentation
Length	Fixed	Varied
Fragmentation	Internal	External
Table Entry	Page number -> Frame Number	Seg ID → <base addr, limit length>
View	Physical memory	User progam

參考

Mage 大的筆記、周志遠教授 PPT 與影片、Segment with paging、Segment_descriptor wiki、MMU Wiki

END

-----------------------------------

2019.10.31

Background

How to "refer" memory in a program

How to "load" a program into memory ?

Memory-Management Unit

Swap

Contiguous Memory Allocation

Fragmentation

Page

Page Concept

Page Table

TLB

Effective Memory-Access Time

Memory Protection

Shared Pages

Page Table Memory Structure

Hierarchical Paging

Hash Page Tables

Inverted Page Table

Segmentation

基礎概念

流程

Protection & Sharing

Segmentation with Paging

Review

參考