# 作業系統 CH8 Memory Management
###### tags: `作業系統 Operating System`
## Background
- 主記憶體和暫存器為唯二 CPU 可以直接存取資料的地方
- Programs 在硬碟中等待被讀入記憶體中及被執行
- 多個 program 被讀入記憶體中可以改進資源使用率以及反應時間
- Process 在執行期間有可能在硬碟及記憶體之間移動
![](https://i.imgur.com/TKJ10p9.png)
### How to refer memory in a program -- Address Binding
#### Compile Time
程式中的資料、參數等必須要有對應的記憶體位置,早期的作法是在編譯期間,就決定要放在哪裡,送進 CPU 時 CPU 就知道該去哪裡存取資料
- Compiler 會將組合語言轉換成實際的記憶體位置(absolute code)
- 若起始地址變更(可能該地址被其他 process 占住),則需要重新編譯 (recompile),等於要關閉並重新執行
- ex: MS-DOS .COM format
![](https://i.imgur.com/B6Pg9qw.png)
#### Load Time
- Compiler 不會決定實際的記憶體地址,而是會留一個變數(Base Register),給出相對位置。程式讀取後(loader,loader 一般假設程式是重新執行,因此會執行非常多動作,如 process 的 control block、記憶體初始化、data structure 的創建等,也就是 program 變成 process 的過程),才透過該變數決定真正的地址(relocatable code)
- 若 run time 起始地址變更,則需要重新讀取 (reload)
![](https://i.imgur.com/omyeIe3.png)
#### 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 產生實際地址
![](https://i.imgur.com/V9QIIi2.png)
- MMU 可以看成 OS 的一部分,但因為使用頻率非常高,所以一般用硬體來實作
- 多數 general-purpose 的作業系統使用這個方法
![](https://i.imgur.com/gTGWsQK.png)
#### 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 決定該使用哪個函式。
![](https://i.imgur.com/h2zi94u.png)
![](https://i.imgur.com/q5gW8TF.png)
### Static Linking
- 函式庫透過 loader 被結合進 program 的 image 當中,compile 的時候,將函式庫加入程式碼
- 每一個用到函式庫的 program 都有一份,浪費記憶體資源,但執行比較快
- 即便改用 Static Linking 加上 Dynamic Loading,因為函式庫仍然需要,因此無法解決程式碼重複複製的問題
![](https://i.imgur.com/BrL1XIu.png) ![](https://i.imgur.com/wIobI54.png)
### 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)
![](https://i.imgur.com/dDe4AEV.png)
## 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
![](https://i.imgur.com/IQOGruN.png)
### 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 決定才能使用
![](https://i.imgur.com/hUMguQT.png)
- 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 的記憶體地址
![](https://i.imgur.com/vPdD4cn.png)
### 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
![](https://i.imgur.com/8P3rtfY.png)
- 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
![](https://i.imgur.com/yW0Ji0r.png)
### 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 左右
![](https://i.imgur.com/EmcOw6E.png)
### 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 拖慢效能的主要原因
![](https://i.imgur.com/LGkNvzf.png)
### 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 真正使用的記憶體空間,限制無效的存取
![](https://i.imgur.com/KGRNopy.png)
### 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
![](https://i.imgur.com/504ifks.png)
### 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]
![](https://i.imgur.com/UzoJhcX.png)
![](https://i.imgur.com/8Y4ZNgv.png)
![](https://i.imgur.com/DgCi4Yf.png)
- 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)
![](https://i.imgur.com/P58VzqA.png)
- 一個改善的實作是將 linked-list 的 element 設為 array,降低 linked-list traverse 的次數
![](https://i.imgur.com/gcV1b2n.png)
### Inverted Page Table
- 不使用 page table,而是改用 frame table, entry 為 PID + Page Number
- 若使用 page table,當 process 數量越來越多, page table 的數量跟著增加
- frame table 只需要一個,可以事先配置,且使用率接近 100%,減少儲存 table 的記憶體需求
- 但存取時要搜尋整個 table,增加存取的時間
- 最麻煩的是難以實作 page 的 sharing,所以這種作法比較少見
![](https://i.imgur.com/w7ISaZC.png)
## Non-Contiguous Memory Allocation — Segmentation
### Segmentation
- 以使用者的角度來決定如何切割記憶體
- 一個 program 可以看成 segments 的集合,segment 是一個 logic unit,可能包含:
- main program
- function, object
- local/global variables
- stack, symbol table
- arrays, etc...
![](https://i.imgur.com/1cONsRe.png)![](https://i.imgur.com/RGvmMCA.png)
### 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 允許的空間可能不同
![](https://i.imgur.com/6lys5rn.png)
### 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
![](https://i.imgur.com/1zqnC2b.png)
### 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 做地址的映射,提高記憶體使用的效率
![](https://i.imgur.com/C8F6gZq.png)
### Address Translation
- CPU 產生 logical address
- 交給 segmentation unit 後產生 linear address
- Linear address 交給 page unit
- 產生 physical memory address
- Segmentation & pageing units 都由 MMU 處理
![](https://i.imgur.com/jV2nB0n.png)
### 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
![](https://i.imgur.com/2MyFP8D.png)
### Segmentation
- Segment descriptor
- Segment base address & length
- 存取權利及優先級
![](https://i.imgur.com/vwiSyUa.png)
### 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
![](https://i.imgur.com/8eEbCq5.png)
### 範例題目
- 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
![](https://i.imgur.com/FpIVeTg.png)
## 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)