OS - Ch8 記憶體管理 Memory Management

Memory management components on Linux.

出自 ADMIN 21/2014 Managing Linux Memory 

記憶體管理是 OS 重要章節，binding, paging, segment 相關的議題都很重要，計算題不少，要熟練一番：）

2015.1.15 初版

2017.8.24 二版

一、Binding

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

1. Compile time

由 compiler 決定，將來程式執行的起始位址不得變更。

缺點：若所決定的位址內有其它的程式在執行，或之後要變更程式執行的起始位址，則須 recompile。

2. Load time

由 linking loader (or linkage editor) 決定，程式不一定都由固定位址開始執行，支援重定位。

在 load time binding 有以下缺點：

• execution time 沒有被呼叫到的模組仍需事先 linking, Allocation, Loading，浪費時間也浪費記憶體。 (e.g. if-else 的程序、OS 錯誤處理程序。)
• 程式執行期間仍不可以改變起始位址。

[補充] loader：解決 external symbol reference 之問題，例如：呼叫 module、呼叫 library 函式、其他 module 定義之變數。

3. Execution time

由 OS 動態決定，又稱 dynamic binding，在程式執行期間才決定程式執行的起始位址。需要的額外硬體支援 (Memory-Management Unit, MMU)。

• Base Register : 記錄目前程式的起始位址。
• Local Address : local address 須與 base register 相加才會得出 physical address。 

優缺點：

• 優點：彈性高 
• 缺點： 程式執行較慢，Performance差。

[用心去感覺] 系統程式重複使用其他程式碼的三種機制

dynamic loading, static linking 和 dynamic linking 是複用其他軟體程式碼的三種機制。特性分別人如下：

1. Static link

Compile 時 library 就加入程式碼。


2. Dynamic linking (Share library) 

在程式執行期間，當某個模組被真正呼叫到時才將其載入到 main memory 中。

• 節省 main memory 空間。(即是 dynamic 方法的目的)
• 節省編譯、組譯、連結所花費的時間。(動態連結函式庫可以單獨重新編譯)
• 常用於 library 導入。
• 需要 OS 支持，不同 OS 有不同的稱呼。
• Windows .dll (Dynamic Linking Libraries)
• Linux .so (Shared Object)。

3. Dynamic loading

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

優點：

• 節省 main memory 空間。
• 讓 programmer 可以呼叫 loader，比 dynamic linking 更具有彈性，靈活度也更高。

缺點：

• programmer 的負擔，要 programmer 自己規劃而不是 OS 負責。
• 拖長執行時間
• dynamic loading 是古老的方法，e.g. MS-DOS Overlay files

二、Swapping

A process can be swapped temporarily out of memory to a backing store (such as disk), and then brought back into memory for continued execution (using priority-based scheduling algorithms).

• Swapping is a mid-term scheduler.
• Major part of swap time is transfer time.

[感覺] 儲存階層化

• 從 main memory 到 cache（用位址 mod 去 mapping)
• 從 disk 到 memory

[例題] swapping transfer time 計算

Consider that the disk transfer rate is 40MB/s, and the average disk seek overhead is 8 ms. To swap out a 10-MB process and then to swap in a 10-MB process require

• 10,000KB/40,000KB = 250ms (250ms+8)*2=0.516s (mid-term scheduler)
• The time quantum of a typical time-sharing system is 10ms; (short-term scheduler)

much smaller than this number.

三、Contiguous Memory Allocation

OS 依據各個 Process 的大小找到一塊夠大的連續可用的記憶體，配置給該 process 使用；OS 會利用 Link List 管理 Free Blocks，稱為 Available list。

Single-partition allocation :

• Relocation-register scheme used to protect user processes from each other, and from changing OS code and data. 
• Relocation register contains value of smallest physical address; limit register contains range of logical addresses. Each logical address must be less than the limit register.

找尋連續可用空間的方法：

• First-Fit：從 AV list head 找，第一個 free block size >= n 就配置。
• Next-Fit：從上次配置後的下一個 Block 開始搜尋，改善 First-Fit 易在 AV-list 前端附近產生許多非常小的可用空間的問題。
• Best-Fit：找所有 free block，比 n 大且最接近 n。
• 長期而言會剩下很大的洞跟很小的洞。
• Worst-Fit：找所有 free block，比 n 大且（size – n）值最大者。
• 長期結果每個洞大小差不多。
• Buddy System：16,8,4,2,1的二元樹，每一層有 list 可以搜尋有無空間。

找尋連續可用空間方法的示意圖。

找尋連續可用空間方法的表格比較。

Contiguous Allocation 缺點 :

• 均有外部碎裂(External Fragmentation)問題：所有可用空間總和大於某個 process 所需要，但因為此空間不連續所以無法配給該 process 使用，造成 memory 空間閒置。
• 配置完所剩的極小 Free Blocks 仍會保存在 AV-list 中，徒增 Search Time 與記錄成本。 

四、Fragmentation

外部碎裂 (External Fragmentation)

系統中，所有可用空間總和大於某個 process 所需要，但因為這些空間不連續所以無法配給該 process 使用，造成 memory 空間閒置。

解決方法 :

• Compaction：類似磁碟重組的概念，移動執行中的 process，使不連續的 free blocks 得以聚集成一塊夠大的連續可用空間 
• 很難在短時間內決定一個最佳的壓縮策略。
• process 必須是 dynamic binding 才可以支援。
• Page memory management

內部碎裂 (Internal Fragmentation)

作業系統配置給 process 的 memory 空間大於 process 真正所需的空間，這些多出來的空間該 process 用不到，而且也沒辦法供其他 process 使用，形成浪費。

• Reducing the page size can alleviate Internal Fragmentation.
• Enlarging the page size helps to reduce the size of the page table. 

五、Paging

OS 會將 disk 中的資料分割成固定大小的區塊，稱為頁（pages）。當不需要時，將分頁由 memory 移到 disk ；當需要時再將資料取回載入 memory 中。分頁是磁碟和記憶體間傳輸資料塊的最小單位。

• 實體記憶體 (Physical Memory)：視為一組頁框(Frame)之集合。各頁框的大小均相等。 
• 邏輯記憶體 (Logical Memory)：即User  Program。視為一組頁面(Page)的集合。頁面大小等同於頁框之大小。 

一個 process 有一個 page table，page table 儲存在記憶體中，執行時用 page table 的資訊來把 logical address 轉成 physical address。

優點：

• 解決 external fragmentation問題 
• 可以支援記憶體的共享(Sharing)：不同 page 對應相同的 frame。
• 可以支援記憶體的保護(Protection)：在分頁表上多加一個 protection bit 欄位
• R : 表示Read only
• RW : 表示Read/Write皆可 
• 支援 Dynamic Loading 及 Virtual Memory 的製作 

缺點：

• 會有 internal fragmentation 問題 (page size 愈大愈嚴重)
• memory 有效存取時間較長 (logical address 轉 physical address)
• 需要額外的硬體支援
• page table implementation (每個 Process 皆有 1 個 page table) 
• logic address -> physical address (用到搜尋器、加法器) 

[例題] logical address 轉 physical address 計算

how many bit are ...

• page number (p) : 2 bit (logical 有 4 大格)
• frame number (f) : 3 bit (physical 有 8 大格)
• displacement (d) : 2 bit (1 大格有 4 小格)
• logical address : [p, d] = [2, 2]
• physical address : [f, d] = [3, 2]
• page table entry : [p, f] = [2, 3]

六、Page Table 的製作 

方法1：使用 register 保存分頁表每個項目的內容

• 優點 : 速度快 
• 缺點 : 僅適用於 page table 大小較小的情況，太大的 page table 則不適用。 

方法 2：page table 保存在 memory 中，OS 利用 PTBR(Page Table Base Register) 記錄起始位址，PRLR(Page-table length register) 紀錄 page table 的大小。

• 優點 : 適用於 page table size 較大之情況 
• 缺點 : 速度慢。因為需要存取兩次 memory。(一次用於存取 page table、一次用於真正的資料存取) 

方法 3：使用 TLB(Transaction Lookaside Buffer) 來保存部份常用的 page table，完整的 page table 在 memory 中，TLB 是 full associate cache。

流程如下：

1. 首先，到 TLB 查詢有無對應的 Page Number 存在。
2. 若 Hit，則輸出 Frame 的起始位址，只存取記憶體 1 次。
3. 若 Miss，則到記憶體中取出 page table 查詢，存取記憶體 2 次。

[例題] TLB 的 Effective Access Time (EAT) 計算

Let the TLB hit ratio= 98 %, 20ns to lookup the TLB, 100 ns to access memory.

• TLB hit time = 20+100
• TLB miss time = 20 + 100 (page table) + 100 (target address)
• EAT = 0.98*120 + 0.02*220 = 122 ns

七、Structure of Page Table

目的：page table size 太大太稀疏的解決方法。


[法一]  Multilevel paging (多層的分頁)

將 page table 再予以分頁，透過 paging page table，只抓所需的 page table 進 memory。只需 1 個level 1 和 1 個 level 2 在 memory 就可執行。

[法二]  Hashing Page Table (雜湊)

• 將 logical address 中的 p(page#) 經由 hashing function 計算取得 hashing table (page table) 的 bucket address。
• 而在每個 bucket 中，皆以 linked list 串連具相同 hashing address 的 page number 及對應的 frame number。
• 去 linked list 中搜尋符合的 page number 之節點。取得 f，然後與 d 相加得出 physical address。

[感覺] hash function collision 的次數等同於 TLB miss 時需要存取記憶體的次數。

[法三]  Invert Page Table (反轉分頁表)

• 以 physical memory 為對象，建立一個 global page table 給所有 process (若有 m 個frames，table entry 有 m 格)
• 每個 entry 記錄此頁框被哪個 process 的哪個 page 所佔用以 <Process id, Page No>

優點：

• 大幅降低 page table size 

缺點：

• searching invert page table 耗時，可用 hash 增加搜尋速度
• 無法支援 memory sharing

八、Segmentation

分段(Segmentation) 使得記憶體的 logical 配置的看法與使用者一致。配置方式為單一段之間連續配置。OS 會替每個 process 準備 segment table :

• 用 Segment-table length register (STLR) 記錄各段的大小(Limit)。
• 用 Segment-table base register (STBR) 紀錄各段載入記憶體的起始位址(Base)。 

segment 個數不多，OS 內約 10 幾個，segment 數目很少增減，為靜態配置。

優點 :

• 無 internal fragmentation。
• 支援 memory sharing 和 protection，且比 paging 容易實施(有的Page可能會涵蓋到不同需求的程式片段)。
• 可支援 dynamic loading 及 virtual memory 的製作。 
• segmentation 和 page 為兩獨立觀念，可同時使用

缺點 :

• external fragmentation (但 segments 很少 allocated/de-allocated 所以還好)
• 記憶體存取時間較長。 
• 需要額外硬體的支援。 

paging 和 segment 的比較。

Paged Segment Memory Management (分頁式分段)

先分段、再分頁。 user program 由一組 segment 所組成，而每個段由一組 page 所組成。每個 process 會有一個 segment table，而每個段會有一個 page table。

目的：

• 保有分段法「與User對Memory看法一致」及「Sharing/Protection易實作」之優點。 
• 避免分段法的 external fragmentation 問題。 

分析：

• 沒有 external fragmentation problem 
• 仍有 internal fragmentation problem (因為最終仍是分頁) 
• table 數目太多，極佔空間，memory access time 更長。

References

陳鍾誠的網站 - Linux 的動態連結與載入 (Dynamic Linking)
http://ccckmit.wikidot.com/lk:dynamiclinking

wiki - 動態連結函式庫
https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E9%93%BE%E6%8E%A5%E5%BA%93

Abraham Silberschatz, Peter B. Galvin, Greg Gagne - Operating System Concepts 8th Edition
https://www.amazon.com/Operating-System-Concepts-Abraham-Silberschatz/dp/0470128720

聯合大學陳士杰教授課程教材
http://web.nuu.edu.tw/~sjchen/

洪逸 - 作業系統金寶典
http://m.sanmin.com.tw/product/index/001601057