---
# System prepended metadata

title: Chap. 08 - Memory management
tags: [課堂筆記, 作業系統]

---

# 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: <font color="ffffff">Address binding.</font> (反白看答案)

程式在執行期間可分為 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: <font color="ffffff">Static/dynaic loading and linking.</font> (反白看答案)

### 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 會造成

* 優點：執行速度較快
* 缺點：**浪費記憶**體空間，因為有很多**重複**的程式碼

<!-- 這種記憶體空間的浪費就算使用 static linking + dynamic loading 也無法解決。因為 **dynamic loading 是針對==單一獨立程式==進行**，但 **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: <font color="ffffff">Swap.</font> (反白看答案)

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

<!-- ![未命名](https://hackmd.io/_uploads/rkxm9c7ryl.png) -->

<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

<!-- ![image](https://hackmd.io/_uploads/HJPV5cQH1x.png) -->

:::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
<!--frame 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}
$$























