# 作業系統 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 解題筆記](https://hackmd.io/@Chang-Chia-Chi/r13xrF0Vt)
### 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](https://hackmd.io/@Chang-Chia-Chi/rkPuUJVaY)
### 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. [清大開放課程 - 作業系統](https://www.youtube.com/watch?v=aK0_PBLWCAM&list=PL9jciz8qz_zyO55qECi2PD3k6lgxluYEV&index=38)
2. [Operating System Concept 9th edition](https://www.os-book.com/OS9/slide-dir/index.html)