Chap. 08 - Memory management

# Chap. 08 - Memory management > 課程內容 : 清華大學開放式課程周志遠教授 > 參考書目 : Operating System Concepts (9th), Abraham Silberschatz, Peter Baer, Galvin, Greg Gagne > > 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl) **Note:** [#loading](#Q-請簡述-dynamic-loading-與-static-loading-的差別) [#linking](#Q-請說明-static-linkingdynamic-linking-的差異) [#fragmentation](#Q-請簡述-externalinternal-fragmentation) [#paging](#1-Paging-concept) ## Content * [Overview](#Overview) * [1. Background](#1-Background) * [Address binding](#Address-binding) * [1. Compile time](#1-Compile-time) * [2. Load time](#2-Load-time) * [3. Execution time](#3-Execution-time) * [Static/dynaic loading and linking](#Staticdynaic-loading-and-linking) * [1. Dynamic loading](#1-Dynamic-loading) * [2. Static linking](#2-Static-linking) * [3. Dynamic linking](#3-Dynamic-linking) * [Swapping](#Swapping) * [1. Challenge](#1-Challenge) * [2. Time](#2-Time) * [3. Efficiency](#3-Efficiency) * [Contiguous memory allocation](#Contiguous-memory-allocation) * [1. Dynamic storage allocation problem](#1-Dynamic-storage-allocation-problem) * [2. Fragmentation](#2-Fragmentation) * [Non-contiguous memory allocation - paging](#Non-contiguous-memory-allocation---paging) * [1. Paging concept](#1-Paging-concept) * [2. Address translation](#2-Address-translation) * [2.1 Scheme](#21-Scheme) * [2.2 Example](#22-Example) * [2.3 Complementary](#23-Complementary) * [3. Free frames](#3-Free-frames) * [4. Paging summary](#4-Paging-summary) * [5. Implement of page table](#5-Implement-of-page-table) * [6. Translation Look-aside Buffer](#6-Translation-Look-aside-Buffer) * [7. Memory Protection](#7-Memory-Protection) * [8. Shared pages](#8-Shared-pages) * [9. Page table memory structure](#9-Page-table-memory-structure) * [9.1 Hierarchical paging](#91-Hierarchical-paging) * [9.2 Hash page table(暫略)](#92-Hash-page-table暫略) * [9.3 Inverted page table](#93-Inverted-page-table) * [Non-contiguous memory allocation - segmentation](#Non-contiguous-memory-allocation---segmentation) * [1. Segmentataion table](#1-Segmentataion-table) * [2. Hardware](#2-Hardware) * [3. Example](#3-Example) * [4. Sharing](#4-Sharing) * [Segmentation with paging](#Segmentation-with-paging) * [1. Basic concept](#1-Basic-concept) * [2. Example](#2-Example) ## Overview ### 1. Background * **Main memory 與 register** 是 CPU 唯二可以**直接存取**的儲存裝置 * Processes 大部分時間都在 disk 中等待被載入到 memory 中執行 * Process 執行期間，通常會在 disk 與 memory 之間移動 ## Address binding > Q: How to refer memory in program ? (程式中如何參考記憶體位址) > A: Address binding. (反白看答案) 程式在執行期間可分為 3 個階段 * Compile time：編譯期間，此時 compiler 會將程式轉譯成 machine code * Load time：程式準備**載入記憶體**的期間，載入前 linker 會將程式所需要的其他函式庫(libary)連結在一起 * Run time/Execution time：程式執行期間 <img src="https://hackmd.io/_uploads/rya-VFkJel.png" width=300> 程式需要參考(refer)並決定記憶體位址的動作稱為 address biding，可以分別在上述三個階段進行。 > [!Note] > **1. 連結器(linker)** > > 編譯器會將程式(Ex. `.c` 檔)編譯成物件檔(object file，通常是 `.o` 或 `.obj` 結尾)。例如使用 gcc 的 `gcc -c main.c` 指令，可將 source code 編譯成物件檔 `main.o` > > 如果 source code 有使用到多其他函式庫，則需要將每個函式庫的 source code 編譯成物件檔(分離編譯)，再透過連結器將所有物件檔連結起來產生可執行檔，使得修改單一文件並不需要重新編譯整個程式。 > > 例如使用 gcc 編譯器的 `gcc main.o userDefine.o -o main` 指令可產生 `main.exe`。 > > 但其實可以直接使用 `gcc main.c userDefine.c -o` 一次執行編譯與連結。此外，只有使用者自訂的函式庫需要手動連結，標準函式庫中的內容會由 gcc 自動連結。 > > **2. 載入器(loader)** > > 產生可執行檔案後，執行程式時載入器會將程式從硬碟搬移到記憶體中開始執行，屬於作業系統的一部分。 ### 1. Compile time <img src="https://hackmd.io/_uploads/SkgRTaDEkx.png" width=650> 在 compile time 期間，程式會被編譯器轉譯成 machind code 並**決定實際的記憶體位址**(physical address)，後續**載入到記憶體的位址與編譯時的記憶體位址相同**，如下圖所示。 **缺點** : 因為編譯後的記憶體位址是寫死的，所以一旦程式有經過搬移，或是編譯時綁定的記憶體位址有其他程式佔用，就必須重新編譯決定記憶體位址。 ### 2. Load time <img src="https://hackmd.io/_uploads/S1j7yCv4Je.png" width=650> 程式編譯成 machine code 後是寫入記憶體的**相對位址**，在 **load time 期間才會把相對位址中的 base address 改為絕對位址**。 * 優點：可以載入到記憶體中的任意位址 * 缺點：在 run time 期間如果**程式有經過搬移，就需要重新載入** ### 3. Execution time <img src="https://hackmd.io/_uploads/H1n5DfKNyg.png" width=650> 程式在**執行階段才載入記憶體位址**。這種方式不論在 compile time 或是 load time 期間都是使用相對的 logical address，甚至連 CPU 都是讀取 logical address，需要透過特殊的硬體設備(Ex: MMU)才能在 CPU 存取記憶體位址時將 logical address 轉換成 physical address。 > [!Note] > * Logical address 又稱為 virtual address，是在編譯期間產生的虛擬記憶體位址 > * Physical address 是記憶體中實際的位址 > * CPU 接收到的指令中使用的也是 virtual address > * 使用者針對記憶體的處理都是 logical address **M**emory-**M**anagement **U**nit(MMU)是一個**特殊的硬體裝置**，用來**將 virtual address 轉換成 physical address**。如下圖所示，MMU 內部有一個 relocation register 用來儲存 base address。 <img src="https://hackmd.io/_uploads/r1Nf9GK4yl.png" width=600> 當 CPU 需要存取記憶體位址時會將 virtual address 發送給 MMU，而 MMU 內部將 relocation register 的值與 virtual address 的值相加後的結果才是 physical address。 > [!Note] > 可重定位暫存器(relocation regieter)與基底暫存器(base register)是相同的東西 ## Static/dynaic loading and linking > Q: How to load a program into memory ? > A: Static/dynaic loading and linking. (反白看答案) ### 1. Dynamic loading 程式在 load time 期間並**不需要將所有內容完全整入記憶體**中才可以執行，可以使用一種 **dynamic loading** 的方式來將 program 載入至記憶體。 > **Dynamic loading** > > A routine(i.e., function call) is load into memory **when it is called**. 動態載入(dynamic loading)指的是當 program 的某些功能/函式/模組**有需要/被呼叫時**，才會將它**載入到記憶體之中**。這種方式會有更好的記憶體空間使用效率，原因如下： * 不需要用到的 routine 不會被載入 * 對某些不常用到但數量龐大的程式碼(Ex: error handling)非常有效 Dynamic loading **不需要 OS 特別支援**，因為哪些函式是屬於 dyanmic loading 是**由==使用者==在撰寫程式時==決定==**。與 dynamic loading 相反的是 **static loading**。會**將完整的 program** 讀取到記憶體中才開始執行，但會造成**記憶體空間的浪費**，因為並不是每行程式碼都會被使用到。 <img src="https://hackmd.io/_uploads/B1XHJQYEye.png" width=600> 以 C 為例有以下的函式 * `dlopen()`：opens a library and prepares it for use * `desym()`：looks up the value of a symbol in a given (opened) library * `dlclose()`：close a DL library ```c= #include <dlfcn.h> int main() { double (*cosine)(double); void* handle = dlopen("/lib/libm.so.6", RTLD_LAZY); cosine = dlsym(handle, "cos"); printf("%f\n", (*cosine)(2.0)); dlclose(handle); } ``` 上述程式碼中，在 `"/lib/libm.so.6"` 函式庫中有很多的函式，但這些東西都不會用到，只有在執行了 `printf("%f\n", (*cosine)(2.0));` 後才會使用 dynamic loading 並放到記憶體之中。 > [!Tip] **Interview Ques.** > ##### Q: 請簡述 dynamic loading 與 static loading 的差別 > **Dynamic loading** 是指程式在執行過程中，根據使用者需求動態的載入某些模組或函式庫。 > **Static loading** 則是指所有的模組或函式庫不論是否會被實際執行，在程式啟動時就被一次性載入記憶體中，不論是否實際會被執行。 ### 2. Static linking 在 load time 期間，static linking 會將 program 與**需要用到的 library** 組合在一起並**一同載入記憶體**之中。但其實許多程式在執行時都會用到**重複的 library**，所以 static linking 會造成 * 優點：執行速度較快 * 缺點：**浪費記憶**體空間，因為有很多**重複**的程式碼  <img src="https://hackmd.io/_uploads/H1E5VmtVkl.png" width=500> ### 3. Dynamic linking > **Dynamic linking** > > Linking postponed until execution time Dynamic linking 會**將連結(linking)的過程延後到 ==run time 期間才進行==**。此時只有當 program **需要時才會==由 OS 載入==需要的函式庫**。這些函式庫還會**共享**給所有的 program 節省記憶體空間。 Compiler 會在每個 program 中需要用到 library 的地方加入一個小程式(stub)，用來檢查需要使用的 library 是否已經載入。當 program 執行到需要引用(refer)函式庫的地方時會呼要 stub 檢查 library 是否載入到記憶體中 * 已載入，直接執行 * 未載入，請求 OS 將函式庫載入 <img src="https://hackmd.io/_uploads/rJRitXKNJe.png" height=400> :::info 如果要使用 dynamic linker，則需要**在 compile 期間就要編譯成 dynamic 的形式**。例如在 Windows 系統中，動態連結的函式庫通常以 `.DLL`(Dynamic Linked Libary)儲存，在 Linux 系統中的概念則是共享函式庫，以 `.so` 結尾。 ::: > [!Tip] > ##### Q: 請說明 static linking/dynamic linking 的差異 > **Static linking** 是在編譯階段將所有用到的函式庫與程式碼直接打包進可執行檔中，產生的執行檔體積較大但不需要依賴外部函式庫。 > **Dynamic linking** 則是在執行階段透過作業系統載入外部的共享函式庫，允許多支程式共用一個函式庫。 ## Swapping > Q: How to move a program between memory and disk ? > A: Swap. (反白看答案) Swapping 是一種**記憶體管理**的技術，將某些 process **從 memoey 移動到 disk 的特殊空間**(backing store)。當需要再次執行此 process 時再從 disk 載回記憶體。 * 通常會搭配 midterm scheduling 一起使用 * **與 context switch 的概念不同** * 優點 * 釋放記憶體空間 * 將某些較**低優先度(lower priority)的 process 移出**記憶體並與較高優先度的 process 交換 > [!Note] > Backing store：磁碟(disk)中的一塊儲存空間，但**與檔案系統不同**，在安裝 OS 的時候就會將這個區域做切割，有時又稱為** swap space**，由 MMU 管理。 > > * 記憶體 $\rightarrow$ 硬碟: swap out > * 硬碟 $\rightarrow$ 記憶體: swap in <img src="https://hackmd.io/_uploads/BkknRnQJel.png" width=500> ### 1. Challenge 在進行 swap in 的時候會遇到兩個問題: * 如果 address binding 是在 compile/load time 完成 * 則 swap in 的位址必須要於 swap out 之前的位址一樣 * 但**幾乎不可能** * 如果 address binding 是在 run time 完成 * 則 swap in 的位址與 swap out 之前的位址可以不同 * 所以 swap 的技術通常會搭配 execution time 一起使用 ### 2. Time Process 被 swap 的**時機點**有嚴格限制，必須是 process 在 **idle 期間才能做 swap**。就算是等待 I/O 狀態(沒有使用 CPU 資源)也不能做 swap，**因為 I/O 的操作可能會被中斷**。解決方法如下： * 確認 process 沒有未完成的 I/O 且沒有使用 CPU 資源，才進行 swap * 透過 OS 的緩衝區來進行 I/O 運算 ### 3. Efficiency Swap 的大多數時間都是在做資料轉移的時間，影響 swap 速度原因有 2 個重點： * 欲移動的 **process 的大小** * 如果要移動的 process 太大(記憶體交換空間大)，則速度就會降低 * 移動 **process 的選擇** * 避免選擇到常用 process，才不會 swap out 後又要馬上 swap in ## Contiguous memory allocation 連續(contiguous)記憶體分配，指的是當系統將 program 載入至記憶體時，**每個 process 分配到的空間是==連續不可分割==的**。連續記憶體分配有兩種分配方式 : * **Fixed**-partition allocation(固定大小) * 將記憶體空間切成**固定的大小**，每個 process 佔據其中一個位置 * **Variable-size** allocation(可變大小) * 依照每個 process 的需求來分配**足夠大(large enough)的記憶體空間** * 會由 OS 管理正在使用/可以使用的記憶體空間 * 當有多個**連續的未使用空間**(free hole)，可以**合併**成一個更大的空間 * Variable-size allocation 的空間切割與分配方式會涉及到 2 個問題 1. process 應該載入至多大的記憶體空間 ? 剛好滿足或是大於 process 2. 如果有很多空間符合需求，那該選哪一個？ ![未命名](https://hackmd.io/_uploads/SJ0lag-Sye.png) ### 1. Dynamic storage allocation problem Vriable-size allocation 的第二個問題又稱為 dynamic storage allocation problem，有 3 種方式 | Method | Intro. | Remark | | :- | :- | :- | | First-fit | 放入**第一個符合**條件的空間 | 較多人使用 | | Best-fit | 放入**剛好符合**大小的空間 | 需要事先搜索(search)完整的空間 | | Worst-fit | 放入**當前最大**空間 | 需要事先搜索(search)完整的空間 | 常用的方式是 first-fit 為主，因為不用去搜尋整個記憶體空間，時間複雜度為 $O(1)$。 ### 2. Fragmentation 不論是 fix-partition 還是 variable-size 的分配，只要做了記憶體空間的切割後一定會有剩餘無法使用的**零碎空間**，稱為 fragmentation。依照不同的分配方式，fragmentation 也有兩種區別： * **External** fragmentation(外部零碎空間) * 整體的**可用空間(free memory space)滿足(大於等於)要載入的 process** 所要求的空間，但這些空間是**不連續的** * 發生在 variable size allocation * Solution：壓縮(compaction) * 將記憶體空間進行重整(shuffle)，使得**可用空間放置在連續的位置**，例如常見的磁碟重組 * **Internal** frgmentation(內部零碎空間) * process **分配到的空間大於實際要求**的空間，使得 process 載入後該塊**被分配的空間還有剩餘**(i.e., 指程式分配但沒用到的空間) * 發生在 fixed-partition allocation * Solution：將記憶體空間切割的更小 <img src="https://hackmd.io/_uploads/ryQA4Zbrkx.png" width=600> > [!Tip] **Interview Ques.** > ##### Q: 請簡述 external/internal fragmentation > **External fragmntation**是指記憶體中的總空間足夠，但被分散成不同的小區塊，無法滿足連續大空間的分配需求。可以使用壓縮(compaction)的方式整合這些空洞(free hole)。 > > **Internal fragmentation**是指記憶體以固定大小進行分配時，程式無法填滿被分配區塊的現象，導致已分配空間的內部浪費。只能將記憶體空間切的更小來改善。 ## Non-contiguous memory allocation - paging 非連續(non-contiguous)的記憶體分配，指的是針對**單一程式**而言**使用/佔用的記憶體空間是==不連續==的**。 ### 1. Paging concept * Method * 將 **physical memory space 分割成==固定大小==**(fixed-size)的區塊(block)，這些區塊稱為 **frames** * 將 **logical memory space 分割成(與 physical)==相同大小==的區塊**，這些區塊稱為 **pages** * 假設 user program 執行時需要 n 個 pages 的空間，則載入到記憶體時也會需要 n 個空的 frames(free frames) * OS 需要**追蹤**目前有哪些 free frames * 建立一個 **page table** 儲存 **logical address 與 physical address 之間的==對應關係==** * Benefit * 能夠讓 process 以**不連續的方式儲存**在 physical memory 之中 * 避免 external fragmentation * 但**無法避免** internal fragmentation > [!Note] > * Frame v.s. page (兩者不可混用) > * Frame 是以 hardware 的角度**切割 physical memory 的區塊**，只能用在 physical memory > * Pages 是以 program 的角度**切割 logical memory 的區塊**，只能用在 logical memory > > Logical space 會被切成與 phisical space 相同大小的區塊。對 user/cpu 來說，假設執行一支程式需要 n 個 pages 的記憶體空間(logical)，OS 會在 physical space 確認有多少可用的 frame，並建立一個 page table 來儲存 n 個 pages 與 n 個 frames 之間的**映射關係**。雖然 CPU 只能知道 logical address，但 **MMU** 可以透過查表(look-up)的方式知道要在哪個 physical address 做資料存取。 > > 好處是 program 可以在 physical space 上以**不連續**的方式使用，但對於 CPU/user 來說卻還是連續的 logical address。以下圖為例，關於 paging 與 page table 的說明： * **Page table 由 ==OS 建立==**分配，並且**儲存在 main memory 中** * OS 也會負責 page table 後續的**維護和更新** * ==**每個 process 都會有自己的 page table**== * Page table 同時也具備 **protection** 的機制，因為每個 process **不會**碰到自己 page 以外的記憶體位址 * 每個 entry 會對應到 physical memory 中對應 frame 的 base address  <img src="https://hackmd.io/_uploads/S1Cy4Qjklg.png" width=500> ### 2. Address translation #### 2.1 Scheme > [!Note] > * 每個 process 會被**切割**成很多個 page > * Page size 預設是**以 bytes 為單位**(byte address) <img src="https://hackmd.io/_uploads/S1jzBzo1eg.png" width=500> 在 logical space 中，每個 logical address 會被切成兩段(上圖)解釋： * 前半段(高位元)的 bits 稱為 **page number**\(p)：表示在 process 的**第幾個 page** * 用來表示 page table 中**每個 entry 的 index**，每個 entry 中儲存的內容(frame)是**該 page 在 physical space 中==對應的 base address==** * $N$ bits 表示這個 process 最多可以分配到 $2^N$ 個 pages(i.e., 即 logical space 的大小) * Logical memory 的總大小 = $2^N \times$ page size * 後半段(低位元)的 bits 稱為 **page offset**(d)：表示某個 page 裡的**第幾個位置** * 與 base address 組合在一起就是 physical address * $N$ bits 表示**每個 page 的大小**是 $2^N$ $$ \text{physical address} = \text{page base address} + \text{page offset} $$ ![未命名](https://hackmd.io/_uploads/HJcvz7o1eg.png) #### 2.2 Example  :::info **Problem:** 假設 page size = 1KB = $2^{10}$ bytes，且 page 2 對應到 frame 5。給定一個 13-bits 的 logical address 且 (p, d) = (2, 20)，試問這個 logical address 對應的 physical address 為何？ ::: 因為 page size = 1 KB = $2^{10}$ bytes，所以 13-bits 的 logical address 中 * 後 10-bits 用來表示 page offset * 前 3 bits 用來表示 page number 因此 logical space 總共有 $2^3$ 個 pages，每個 page 的大小是 $2^{10}$ bytes。題目所給的 logical address (p, d) = (2, 20) 為 $$ \begin{aligned} \text{logical address} & = \text{page number(p)} | \text{page offset(d)}\\ & = 010 | 0000010100\\ & = 0100000010100 \end{aligned} $$ 因為題目說第 2 個 pages 對應到第 5 個 frames，且 frame size = page size，所以 frame 5 的 base address = $5 \times 1$ KB。因此實際的記憶體位為 $$ \begin{aligned} \text{physical address} & = \text{base(f)} + \text{offset(d)}\\ & = 5 \times (1 \text{KB}) + 20\\ & = 1010000000000 + 0000010100\\ & = 1010000010100 \end{aligned} $$ > [!Note] > * 記憶體是以 byte 作為定址單位 > * 此處的 bits 是用來計算記憶體位址(i.e., 第幾個 bytes)，與容量大小沒關係 > * Ex. 容量 = $2^{10}$ bytes 表示 > * 記憶體大小是 $2^{10} = 1024$ bytes = $1$ GB > * 但需要 10-bits 來表示這 1024 個 byte 的位址 #### 2.3 Complementary * Page 的總數量**不一定** = frame 的總數量 * 因為 page 的數量是會決定一個 process 的 logical memory size * 但 **frame 的數量是==根據 physical memory size== 決定** * 給定一個 32-bits 的 logical 與 36-bits 的 physical address，且 page size = frame size = 4 KB = $4 \times 2^{10}$ bytes = $2^{12}$ bytes * Page table size $= 2^{32}$ bytes $/ 4$ KB $= 2^{32} / 2^{12} = 2^{20}$ entries * Max program memory $= 2^{32}$ bytes $= 2^{22}$ KB $= 2^{12}$ MB $= 4$ GB * Total physical memory size $= 2^{36}$ bytes $= 64$ GB * Number of bits for page number：$20$ bits $(\because$ entries $= 2^{20})$ * Number of bits for frame number：$24$ bits $(\because$ entries $= 2^{36}$ bytes $/ 4$ KB $= 2^{36} / 2^{12} = 2^{24})$ * Number of bits for page offset：$32 - 20 = 12$ bits ### 3. Free frames Free frames 指的是**目前沒有使用**到的 frame，通常會使用一個 **linked list** 儲存。當 user 每創建一個 process，OS 就會**從 free frame list 找==目前沒有使用==到的 frame 使用**，用完後再儲存回 list 之中。 <img src="https://hackmd.io/_uploads/Bk9_5cXByg.png" width=600> ### 4. Paging summary (1) Page/frame size * Page/frame 的大小是**由 hardware 決定** * 一般都是以 2 的次方為單位，範圍大概從 512 bytes - 16 MB/page * 較常見的大小時 4KB 或 8KB/page * 當 page size 過大，容易發生 internal fragmentation (2) Advantage * Paging 的概念將 physical address 與 logical address 的概念分離 * 使得 user 能夠**以連續的概念使用不連續的記憶體位址** * 由 **OS 負責維護**每個 process 的 page table  ### 5. Implement of page table Page table 本身是一個**類似陣列**的資料結構，會**儲存在 main memory 之中**，所以也需要一組記憶體位址來**存取** page table。 Page table 的 physical base address 會儲存在一個暫存器之中，稱為 Page Table Base Register(PTBR)，是實作在處理器中的一個硬體。當 process 之間進行 context switch 的時候 : * 會將 new process 的 page table 位址從 PCB 載入到 PTBR 中 * 並將 old process 的 page table 位址存入它的 PCB 中 > [!Note] > * PCB = Process Control Block > * 除了 page table 的 base address 外，也需要紀錄 page table 的長度並儲存在另一個暫存器(Page Table Length Register, PTLR)之中因為 PTBR 的關係，所以每次進行 memory reference 都會需要**兩次的讀取動作**，使得效率變低 * 第一次，MMU 根據 PTBR 儲存的值**讀取 page table 的位址** * 第二次，MMU 根據 page table 的記錄**讀取 physical address** 可以藉由 **Translation Look-aside Buffer(TLB)** 解決上面的問題。TLB 是一個實作在處理器中的硬體(associative memory，類似 cache)，可以**儲存最近使用過的 page/frame** 並提供給 MMU 查詢。 > [!Note] > Associative Memory 是一種特殊的儲存設備，不是以位址為基礎做存取，而是以內容(值)為單位進行資料的存取。(類似 hash table) > <img src="https://hackmd.io/_uploads/ryZA55XBye.png" width=500> ### 6. Translation Look-aside Buffer TLB 的結構類似 hash table，會**儲存(最近)使用過的 page number 與 frame number**，如下圖所示。 ![未命名](https://hackmd.io/_uploads/rkN6ocmSJl.png) **MMU** 要從 logical address 轉換成對應的 physical address 時會**先從 TLB 中尋找**最近有沒有使用過對應的 page * Page 存在 TLB 中(TLB hit) * 直接找對應的 frame number 再加上 page offset 算出 physical address * Page 不存在 TLB 中(TLB miss) * 依照正規步驟讀取 page table 作轉換整個過程都是由 MMU 控制。當 OS 進行 context switch 時，因為前後的 process 不同，所以**對應的 page table 與最近用過的 TLB 也會==不同==**，此時有兩種解決辦法： * Context switch 後，舊的 TLB 也一併被清除(flush)，才不會拿到別人的 frame * 缺點是一旦 TLB 清空就必須要**重新建立**，使得一開始的 access time 一樣是兩倍(context switch 浪費效能的證據之一) * 在 TLB 中額外**加上 process ID(PID)**，使 MMU 從 TLB 取值時可以確認有沒有拿錯 ### 7. Memory Protection 在 page table 中的每個 page 都有一個 **protection bit** 來保護資料的安全性，例如：使用 1-bit 來定義讀寫權限。常見的方式是使用 valid-invalid bit。 * 當 protection bit = valid * 表示這個 page 在該 process 的合法位址中，且也會有一個對應的 frame * 當 protection = invalid 表示這個 page 並不在該 process 的合法位址中，可能是下這些狀況(包含但不限於) * 這個 page 沒有分配給該 process * 這個 page 屬於其他 process > [!Note] > 每個 process 會被分配到屬於自己的 memory space 以下圖為例，process 在 logical space 的位址是 00000 到 12287，每個頁面都是屬於這個 process，所以 page 0 到 page 5 都是正確(valid)的。但實際上： 1. Page 5 對應的 frame 9 的位址卻不是 process 在 physical space 中的合法(legal)位置，所以被標記為 valid but illegal * 使用 hardware 的方式(Memory Limit Register)來限制 physical address 在頁面邊界上 2. 這個 process 的 page table 太大，會導致記憶體空間的浪費 * 使用 hardware 的方式(Page Table Length Register)限制 page table 的長度 ![未命名](https://hackmd.io/_uploads/SJ1skjmBJx.png) ### 8. Shared pages Page 的概念也可以讓**多個 process 進行==共享==**。共享的內容必須具有 reentrant(可重入)的性質，指的是在執行期間(execution time)不會改變的部分。這些重複的部分只要在 physical space 中載入一次即可，可以透過 page mapping 的方式當多個 process 使用這些重複內容。 ![未命名](https://hackmd.io/_uploads/HJmyioXryx.png) ### 9. Page table memory structure 當 **page table 變得越來越大**時會非常難載入到記憶體中。以 4 GB 的 logical space 和 4 KB 的 page size 為例，一個 page table 最多會有： $$ \frac{4 \text{GB}}{4 \text{KB}} = \frac{2^{32}}{2^{12}} = 2^{20} $$ 個 entry，假設每個 entry 需要 4 bytes 的空間(32-bits)，則 page table 的大小為 $$ 2^{20} \times 4\text{bytes} = 4 \times 2^{10} \text{KB} = 4 \text{MB} $$ 但實際上在 physical memory 中**不可能**有這麼大的**連續空間**可以儲存這個 page table，所以需要想辦法**減少 page table size**。解決方式有 3 種： * Hierarchical paging * Hash page table * Inverted page table #### 9.1 Hierarchical paging 使用**多層次的 page**，將大的 page table 視為 logical space 分割成多個更小的 page table。以 2-level 的 paging 為例如下圖 ![0482CC83-5A64-4EB6-B648-C487A8A45CC5](https://hackmd.io/_uploads/r1X7xnmBJl.jpg) 假設 32-bit address 與 4 KB 的 page size： * 後 12-bits 作為 page offset(d) * 前 20-bits 作為 page number\(p)，但因為做了 2-level paged，所以要把 page number 再做切割 * 前 10-bits 作為 outer numer($p_1$) * 後 10-bits 作為 inner numbber($p_2$) <img src="https://hackmd.io/_uploads/Sk5W-2XBJl.png" width=400> 缺點顯而易見，需要做**更多次的 memory access**(2 for physical 1 for data)，且層次越高，需要的存取次數越多。 <img src="https://hackmd.io/_uploads/HkDTX37Bkl.png" width=700> ##### Example 以 12-bits 的 address 為例 * 前 3-bits 表示 outer：有 $2^3 = 8$ 個 entry，表示有 8 個小的 page table * 中間 4-bits 表示 inner：有 $2^4 = 16$ 個 entry，表示每個 page table 可以儲存 16 個 pages/frames * 最後 5-bits 表示 page offset ![未命名](https://hackmd.io/_uploads/ryOtIhQBye.png) #### 9.2 Hash page table(暫略) #### 9.3 Inverted page table > [!Warning] > 這方法很少見，因為很難支援 shared memory 這種方法不再為每個 process 創建 page table，而是把整個 physical spac 視為 (global) frame table，其中 * Index = frame number * Content = page number 當需要某個 process 的第 i 個 page，就去找 frame table 中哪個 index 的內容是 page$_i$ (假設是 frame$_k$)，最後再將 frame$_k$ + page offset 就是最後的 physical address。但缺點是，因為一個 frame number 可能會對應到多個 page number，所以 frame table 的內容還會再加上每個 process 的 ID <img src="https://hackmd.io/_uploads/HkKA9nQHkl.png" width=500> ## Non-contiguous memory allocation - segmentation Segmentation 指的是**依照 ==program 的結構==做切割**，把一個大的 program 分成多個小的部分。每個小的 segment 都可以看成是 page 的概念去執行。 ![未命名](https://hackmd.io/_uploads/Sk0annQHyx.png) ### 1. Segmentataion table > [!Note] > 類似 page table 的模式，但是以 segment 的數量作為 array 的 entry。 * Logical address：(#seg, offset) * #seg 指的是**第幾個 segment** * 理想上 offset 的長度不受限，可以跟 physical address 的長度相同 * Segmentation table * 用一個 2D-array 來找出 physical address，每個 entry 的內容包含 * Base(4 bytes)：segmentation 的 base address * Limit(4 bytes)：segmentation 的 length ### 2. Hardware Segmentation 的架構如下圖。在最後檢查完後，直接將 base address + limit = physical address。且每個 segment 互相獨立不影響。在這之中，MMU 控制的是分配一個適當的 base address 給每一個 segment ![image](https://hackmd.io/_uploads/rJaE1pQrye.png) ### 3. Example ![未命名](https://hackmd.io/_uploads/S1hgx6QHye.png) ### 4. Sharing 與 page 的概念相同，segmentation 同樣也可以做到分享的概念，將多個 segment 指到同一個 physical 即可。 ![未命名](https://hackmd.io/_uploads/BkyFg6XSJg.png) ## Segmentation with paging > 將 segmentation 與 paging 兩者結合，實務上比較常用這個方式 ### 1. Basic concept :::info **Review** Page 的概念是將一個 process 分解，讓 process 執行時可以使用不連續的記憶體空間。缺點是無法針對 program 的邏輯結構分割。 Segmentation 的概念是依照 program 的邏輯結構分割成不同的區塊(text, data, stack, heap, ...)，每個區塊映射到一段連續的記憶體空間。缺點是可能會發生 external fragmentation 將兩者結合，既可以做到以程式邏輯分割，又能做到以不連續的方式使用記憶體空間。 ::: ![未命名](https://hackmd.io/_uploads/BJJWN0Arke.png) (1) 在 logical address 中把一個 process 依照程式邏輯切分成不同的 segmentation，例如：stack, heap, code, data, ...等。這個步驟與 segmentaion 的概念相同。 (2) 在 linear address 中每個 segment 會再次被切成相同大小(fixed-size)的 page。中間這段地址稱為 linear address，是一個假象的空間地址。 (3) 在 phyiscal address 中將前一步產生的 page 映射到 physical space 中的實際位址這個步驟與 paging 中 page table 的轉換和 MMU 的控制相同。在完整的 address translation 過程中，是由 CPU 產生 logical address，後續的各層的轉換與映射全部都是由 MMU 控制。 ![image](https://hackmd.io/_uploads/ByEMECRBkx.png) ### 2. Example > 給定以下條件： > > * Physical memory size: 512 bytes (9-bits) > * Page size: 32 bytes (5-bits) > * Program 的 logical address 可以有 8 個 segments (3-bits) > > 假設 logical address sapce 是 12-bits 的大小，則當 address = 448 (十六進位制) 時，對應的 physical address 是多少？ > (以下圖表格為例) > ![未命名](https://hackmd.io/_uploads/ry48N0Rrkl.png) (1) Logical address $$ \begin{align} \text{Logical address} &= (448)_{16}\\ &= 0100|0100|1000_2 \end{align} $$ (2) Linear address Logical address 的前 3-bits 表示 #seg = 010$_2$ = 2$_{10}$，根據 segmentation table 查表(look-up)可以找到 base address = 001110110。 Logical address 的後 9-bits 表示 offset。將 base + offset 可得 linear address： $$ \begin{align} \text{Linear address} & = \text{base address} + \text{offset}\\ & = 001110110 + 001001000\\ & = 010111110 \end{align} $$ (3) Physical address 因為 physical memory size = 512 bytes = 2$^9$ 且 page size = 32 bytes = 2$^5$，所以 page table length = 2$^4$ (4-bits)。 Linear address 的前 4-bits 表示 page number = 0101$_2$ = 5$_{10}$，對應的 frame number = 2$_{10}$ = 0010$_2$。 Linear address 的後 5-bits 表示 page offset。將 page number 連接(concatenate) page offset 後可得 physical address： $$ \begin{align} \text{Physical address} &= \text{page number}\ ||\ \text{page offset}\\ & = 0010\ ||\ 11110\\ & = 001011110 \end{align} $$