# OS-Chap8 - Memory_記憶體管理
###### tags: `作業系統 Operating System note`, `110-1`, `2021`

# Contents

[TOC]

---

# Chapter Objective
1. detailed description of various ways of organizing memory hardware.
2. various techniques of allocating memory to processes
3. discuss in detail how paging works in contemporary computer systems.

# 一、background(背景)
1. 程式(program)必須從硬碟(disk)移動到**記憶體(memory)** 中，並變成一個行程(process)才能執行
2. 因 CPU 只能直接存取 「CPU 內暫存器(register)」或「記憶體(memory)」的內容。
> #### memory unit 只能看到位址(a stream addresses) 和要做甚麼事情的需求(read/data and write requests)
- CPU 可以在一個時脈週期(a clock cycle)內，存取暫存器(register)多次
- 當存取相同內容時，存取記憶體(memory)可能要花數個 CPU 時脈週期(因 memory 速率較 register 慢)，導致 CPU 需要等待(stall)
3. 補救方法：「加入快取記憶體(cache)」（存取速率中等）
> cache 會放在 主記憶體(memory) 和 CPU暫存器(registers) 之間


## Hardware Address Protection
### Base Registers and Limit Registers
- 使用兩個 registers 定義 邏輯位置空間(Logical address space)
- Register
1. Base register：紀錄該 process 的起始記憶體地址，稱為基底暫存器
2. Limist register：紀錄該 process 所佔記憶體地址大小，稱為限制暫存器

- CPU 送出一個 address，由 software 去測試該 address 是否在 memory 的範圍內(base reg. 和 limit reg. 之間)。
- 若超出 memory 可存取的範圍，CPU(?) 會產生 addressing error 的 trap 給 OS，強迫 OS 暫停現在在做的事情，也無法再繼續執行之後的 process。

# 小小的 Q & A
- Q1. 如何在 program 中，連結到 memory ?????
A：address binding
- Q2. 如何 load program 進入 memory？
A：static/ dynamic loading and linking
- Q3. 如何將 program 在 memory 和 virtual memory(disk) 之間移動(傳遞)？
A：swap
- Q4. 如何 allocate memory？
A：paging、segment

# 二、multistep processing of a user program
##### 如何從一個 user 完成的 program(.c/.cpp)，變成被執行的一個程式
1. source program D
- 這邊的 program 是指在編輯器中的文字檔案，並且已經被存入(store) disk 中。
> 在尚未按下「儲存」鍵(strl+S) 前，所有打在文字輸入檔的 code，都會先暫時被儲存在 memory 提供的 space 中，等到按下「儲存」鍵(strl+S) 後，整個 file 才會被放到 disk。

2. compiler : (編譯器)
- IDE 告訴 compiler 要被執行的 file 的 address 在哪裡，讓 compiler 抓 program ，並將高階語言(.c/.cpp) 轉換成組合語言(.s)，最後將 .s 檔存回 disk 中。
> - IDE (Integrated Development Environment)
> - 整合開發環境
> - 將編輯器(Editor)、編譯器(Compiler)、連結器(Linker)、除錯器(Debugger)、執行(Execution)等功能整合在同一套軟體中
> - ex. 微軟的 Visual Studio系列，Borland的C++ Builder、Delphi系列等。

3. assembler : (組譯器)
- 將 assemble code 轉換為 machine code，即 .s file 轉換為 .o file(object file/ module)。
> Machine Code == Object code == Binary code

4. linker : (鏈結器)
- 將很多個不同的 object file 連結在一起，即將多份 machine code 合併成執行檔(execution files)，並更正檔案內的參考位址(address)。
- (因一個程式所呼叫的函式，可能在**另一個原始碼檔案(.c 或 .cpp)** 中，也可能在**另一個機械碼檔案(.obj)** 中，也可能在**程式庫檔案中(.lib)** 中)
- 
> **ref.** [compiler 與 assembler 的運作原理](https://rexpighj123.pixnet.net/blog/post/207609288-%E7%B7%A8%E8%AD%AF%E5%99%A8(compiler)%E8%88%87%E9%80%A3%E7%B5%90%E5%99%A8(linker)%E7%9A%84%E9%81%8B%E4%BD%9C%E5%8E%9F%E7%90%86)

5. Loader
- 四大功能
- allocation: 分配記憶體給程式
- Linking:
- 處理external reference，重新解決符號參考(symbolic reference)
- 合併兩個以上的的目的程式，並且提供其間相互參考的資訊。
- relocation:
- 調整 address-dependent，進行 relocation 調整
- 調整目的程式中在載入記憶體時需要修改的位址
- Loading:
- 將程式指令與資料放入記憶體
- 配置記憶體位置，將目的程式載入記憶體中準備執行。
- 再這邊是使用他的 loading 功能，將資料放進 memory 中。
> **ref** [[SP]系統程式筆記3](https://r888800009.github.io/system-program/sp3/)

---

# 三、**Address Binding (地址的連結)**
##### ＜How to refer memory in a program＞
## address binding 決定的時間點有以下三者
- Binding: 決定程式起始位置，即程式要在 memory 中的哪個地方開始執行。
### in **compile time**
- 由 compiler 決定程式起始位置。
- 因程式中的資料、參數等必須*要有對應的記憶體位置*，早期的作法是在編譯期間(compile time) 就決定要放在哪裡，送進 CPU 時、 CPU 就知道該去哪裡存取資料。

> **上圖表示 program 在組譯成 assemble code 時，就已經決定好要放入 memory 的位置，但此時並無法知道這個位址是否真的可以在 main memory 中被使用**
- absolute code
- compiler 會將組合語言(assemble code)轉換成實際的記憶體位置(absolute code)
- Recompile (重新編譯)
- 若起始地址變更，則需要重新編譯，等同於要關閉並重新執行。
- 起始地址變更的原因
1. 原決定的地址被其他 process 占用
2. kernel 改變位置(why?)*--待補*
- ex: MS-DOS .COM format
> COM format 是什麼？
> 是一種簡單的執行檔格式
> 一開始是 [Digital Research](https://en.wikipedia.org/wiki/Digital_Research)的 [CP/M](https://en.wikipedia.org/wiki/CP/M) 微電腦作業系統在使用
> 後來替代 CP/M的 [DOS](https://en.wikipedia.org/wiki/DOS)也繼續使用這個格式
> 特色：
> * 格式內沒有Header(如PNG的資料是0x89開頭，告訴你他是PNG)或[metadata](https://en.wikipedia.org/wiki/Metadata)(例如作者、描述，常見於相片或影片)
> * 整個程式+資料可以直接放進一個segment

### in **load time**
- 由 linking loader (or linkage editor) 決定程式起始位置。
- relocatable code
- compiler 會將組合語言(assemble code)轉換成(relocatable code)
- 程式的起始位址如果改變，就會重新load一份


### in **execution time**
- 由 OS 動態決定程式起始位置。(又稱 dynamic binding)
- compiler 將組合語言(assemble code)轉換成 logical-address(i.e. virtual-address)


# :star: 重要小補充 :star:
:star2: Logical memory v.s. Physical memory :star2:
- Logical memory = virtual address
- 為 CPU 送出的 address
- Physical memory
- 為記憶體看到的真實地址

## Memory-Management Unit(MMU)
MMU是CPU內的硬體單元，負責轉virtual address轉換成physical address
* base register在 MMU 中會順便檢查轉換是否合法
* 所以base register 又被稱作relocation register

> ref: [2019 iT 邦幫忙鐵人賽 - DAY 18 Memory Management(上)](https://ithelp.ithome.com.tw/articles/10207547)
### dynamic relocation
relocation: 記憶體地址的轉換

Static relocation:
* 程式執行前，就把資料放在**固定的**記憶體區段內
* 不需要有 base register

dynamic relocation:
* 會有relocation register
* 轉換時會檢查是否超出limit register，如果超出會發生trap
* 有dynamic recolation便可以任意移動process到不同記憶體位置

> ref: [Intro To Operating Systems - Memory management](https://intro2operatingsystems.wordpress.com/tag/dynamic-relocation/)
> ref: [Stackoverflow : How does C++ linking work in practice? ](http://stackoverflow.com/a/30507725/895245)
---

# 四、Loading & Linking
##### ＜How to laod a program into memory＞

## dynamic laoding
當程式中的模組，需要時才載入記憶體
* routine 在被呼叫時就會載入記憶體
* 不需要OS特別設計，通常是library或API實現這部分

範例：

#include <dlfcn.h>
int main(){
    // function pointer
    double (*cosine)(double);
    
    // load library
    void *handle = dlopen("/lib/libm.so.6", RTLD_LAZY)
    
    // use library as function pointer
    cosine = dlsym(handle, "cos");
    printf("%f\n", (*cosine)(2.0));
    
    // release the library module
    dlclose(handle);
    
}

呼叫函式的範例

## Linking
### Static Linking
Loader會把 library 跟程式合並
* 程式碼會重復，浪費硬碟&記憶體空間
* 執行時較快，在load time就已經做linking了

### Dynamic Linking
直到執行階段才進行link


* 記憶體內只會有一份library，不會重復
* 用 **Stub** 來代表 library的參照(reference)
* Windows的DLL(Dynamic link library)就是這個類型

---

# 五、Swapping
##### ＜How to move a program between memory & disk＞
* **backing store**(後備儲存器)
* 和檔案系統分離開的一塊硬碟區塊
* 可以直接使用區塊內的記憶體映像(memory images)，把這塊空間當作記憶體來使用
* 可以釋出更多記憶體
* 只有 **閒置(idle)** 的process可以被swap
* 例如process正在等 I/O輸入，結果被swap ：*尷尬*
* **swap back memory location**(回置記憶體位址)
* 記憶體位置在compile/load time鏈接：回置記憶體位址**需要一樣**
* 記憶體位置在execution time鏈接：**不需要一樣**
* transfer time佔swap的時間的大部分，data越多transfer越久

### content switch with swapping
如果在content switch的時候會進行swap
* content switch time會很高，而且主要由硬碟到記憶體的轉移速度決定
* 100MB 的process + 50MB/s的轉移速度
* swap到硬碟需要 2000ms
* 把另一個100MB的process 從硬碟swap進記憶體也需要 2000ms
* 總共4000ms
* 及時監控目前的記憶體用量，就不需要swap的太頻繁

---

# 六、Memory Allocation
## Contiguous Memory Allocation
- OS 依據各個 Process 的大小找到一塊**夠大的連續可用的記憶體**，配置給該 process 使用

- OS 會利用 Link List 管理 Free Blocks，稱為 Available list。

### Fixed-partition allocation(固定 size 的切割)
- 每個 process 讀進一個 fixed-size 的 partition
- Multi-programming 的程度由 partition 的數量決定
### Variable-size partition (Multiple Partition)
- Hole 定義為一塊連續的記憶體位置。
> block of contiguous free memory
- 不同大小的 Holes 散布在記憶體當中。
- 當有 process 抵達，會被 allocate 進入一個夠大的 hole 裡頭。(hole sizew >= process needed)
- OS 會維護 in-use & free hole 的資訊。
- 一個被釋放的 hole (free hole) 能夠跟其他 hole 合併成一個更大的 hole。
- 如上圖，釋放 process 8 後，救會產生一個 hole ，這個 hole 又能夠被 process 9&10 使用

### Dynamic Storage Allocation Problem
- Ｑ：如何從一串 free holes 中，找出需要 size n 大小的 hole？
- Ａ：
- First fit - 1st 符合的 hole 就直接配置。
- Best fit - 配置大小最剛好的 hole
- 需搜尋整個 hole list(AV-list)，效率低。
- Worst fit - 配置最大的 hole
- 需搜尋整個 hole list，效率低。

| Fit Way | Time 效益 | 空間利用度 |
|:---------:|:--------:|:---------:|
| First-fit | 優 | ≈優 |
| Best-fit | 差 | 優 |
| Worst-fit | 差 | 差 |
- First fit 和 Best fit 無論在速度或空間使用上都比 Worst fit 好

### Contiguous Allocation 的缺點
- 必有外部碎裂(External Fragmentation)
- 配置完所剩的極小 Free Blocks 仍會保存在 AV-list 中，徒增 Search Time 與記錄成本。

# :star: 重要小補充 :star:
**:star2: External Fragmentation v.s. Internal Fragmentation :star2:**
- External Fragmentation(外部破碎)
- 所有可用空間總和(free blocks size) ≥ process 需求大小
- **因為這些 free blocks 不連續，所以仍無法配置。**
- fixed-partition、variable-size 都有可能發生。
- ex. 有一個 process 需要 450K 的空間
- Solution Way:
1. Compaction(壓縮)
2. 利用 Page Memory Management

- Internal Fragmentation(內部破碎)
- OS 配置給 process 的 memory space > process 實際所需 space
- **此一差值空間該 process 用不到，且其它 process 也使用不到，形成空間之閒置浪費**
- fixed-partition 有可能發生。

:heavy_exclamation_mark: 有足夠 memory space 給需要的 processes 使用，但因這些 memory space 仍被其他 processes hold 住，故需要 memory space 的 processes 仍無法使用該空間。


## Non-Contiguous Memory Allocation
### Paging :star2: :star2: :star2:
* 實體記憶體切成固定數量的區塊叫：**框架(frames)**
* 邏輯記憶體切成固定大小的區塊叫：**分頁(pages)**

#### 特性：
* 使用 n 個 pages 就需要 n 個空 frames
* 使用 **分頁表(page table)** 來轉換 **實體記憶體位置和邏輯記憶體**
* 可以讓 process 使用**非連續的記憶體**
* 記憶體使用更彈性：同時避免了 內外部碎片化
* 共用記憶體的實作也比較容易 ： 共用分頁

#### page table : Address translation

* **<span style="color:red">每一個process都會有一個 page table</span>**
* table內每一列會對應到一個 base address
* 第 $i$ 個 page 對應第 $i$ 列 (陣列的第 $i$ 個元素)
* Logical Address 有兩個部分(如下圖)
* Page number (p) ： 第幾個 page
* 每一個 page number 都會對應一個 base address
* page number 有 $N$ bits 代表最多 $2^N$ 個 pages
* Page offset (d) ： page 內的哪個位置
* page offset 有 $N$ bits 代表每一個 page 都有 $2^N$這麼大
* 邏輯記憶體位置：
* 位址長度 $M$ bits，最多能有 $2^M$個位址，page size $2^N$


#### MMU進行位址的轉換：

$\textrm{實體記憶體位置} = \textrm{Base address}_i + \textrm{page offset}$

> Example Q:
> If page is $1KB$ & $page 2$ maps to $frame 5$. Given **13 bits logical address :(p=2, d=20)**, what is *physical address*?
> A: $\because 1\textrm{KB} = 2^{10}$

### Segmentation :star2: :star2: :star2:
- **<span style="color:red">以使用者的角度來決定如何切割 memory。</span>**
- 配置方式
- segment 與 segment 之間可以採用『不連續性』配置。
- 單個 segment 內，採用『連續性』配置。
- 實體記憶體：
- 不須事先區分 memory space。
- 若 memory 中存在 process 所需要(夠大)的連續 free memory space，就將該 space 分配給該 process。
- 邏輯記憶體：
- 即 **User Program**
- 視為一組 **<span style="color:red">段 (Segment)</span>** 的集合，而且各 segment 大小不同。

- #### Segmentation table
- OS 會替每個 process 準備 Segment Table，**<span style="color:green">用來記錄各段的大小 (Limit)</span>** 及 **<span style="color:green">各段載入M.M. 的起始位置 (Base)</span>**。
-

:heavy_exclamation_mark: **11/25 說 考試會考名詞解釋!!! 要懂這個名詞是在做什麼!!!** :heavy_exclamation_mark:
:heavy_exclamation_mark: **12/02 說 paging必考** :heavy_exclamation_mark:

# Homework
### 先放一些網路查到的資料，自己的之後補上

## 8.1
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
內部破碎和外部破碎的內外是對於 process而言
process外的破碎就叫外部破碎
* 連續的記憶體空間不夠分配給其他process，造成記憶體碎片化，而且這些碎片也無法使用
process內的破碎即內部破碎
* process被分配到的記憶體過多，不需要這麼多資源，而其他prcess也無法存取這些資源

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
[輔大考古](https://blog.pulipuli.info/2006/04/922-2.html)
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

## 8.3
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
**ｅｘａｍｐｌｅ　ｑｕｅｓｔｉｏｎ**

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
# 慶隆的 answer
### Fisrt-fit
with avaliable list:

| Space(KB) | allocated(KB) | iteration |
|:---------:|:-------------:|-----------|
| 300 | 115 | 1 |
| 600 | 500 | 1 |
| 350 | 200 | 1 |
| 200 | | |
| 700 | 358 | 1 |
| 125 | | |
| no space | 375 | 2 |
| total | 1173 | 6 |

總共分配：1173 KB，只需要 6次iteration
* 效率最好、空間利用率最大

### best-fit:
with avaliable list:

| Space(KB) | allocated(KB) | iteration |
|:---------:|:-------------:| --------- |
| 300 | | |
| 600 | 500 | 5 |
| 350 | | |
| 200 | 200 | 3 |
| 700 | 358 | 4 |
| 125 | 115 | 6 |
| no space | 375 | 2 |
| total | 1173 | 20 |

if we sort it first

| Space(KB) | allocated(KB) | iteration |
|:---------:|:-------------:|-----------|
| 125 | 115 | 2 |
| 200 | 200 | 2 |
| 300 | | |
| 350 | | |
| 600 | 500 | 5 |
| 700 | 358 | 4 |
| no space | 375 | 2 |
| total | 1173 | 15 |

總共分配：1173 KB，沒排序需要20次，排序後15次
* 效率中等，空間利用率最大

### worst-fit:
with avaliable list:

| Space(KB) | allocated(KB) | iteration |
|:---------:|:-------------:| --------- |
| 300 | | |
| 600 | 500 | 5 |
| 350 | 200 | 4 |
| 200 | | |
| 700 | 115 | 6 |
| 125 | | |
| no space | 358, 375 | 4+3 |
| total | 815 | 22 |

if we sort it first:

| Space(KB) | allocated(KB) | iteration |
|:---------:|:-------------:|-----------|
| 125 | | |
| 200 | | |
| 300 | | |
| 350 | 200 | 1 |
| 600 | 500 | 1 |
| 700 | 115 | 1 |
| no space | 358, 375 | 4+3 |
| total | 815 | 10 |

總共分配：815 KB，沒排序需要22次，排序後10次
* 排序後效率接近最好，空間利用率最小
* 沒排序的效率則最差

空間利用率： $\textrm{best-fit} = \textrm{first-fit} > \textrm{worst-fit}$
未排序效率： $\textrm{first-fit} > \textrm{best-fit} > \textrm{worst-fit}$
已排序效率： $\textrm{first-fit} > \textrm{worst-fit} > \textrm{best-fit}$

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

## 8.4
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
* 連續記憶體分配：需要，否則需要更多空間時，要重新分配整個程式的記憶體空間
* 純segmentation：需要，單一sementation內的記憶體用完就沒了，也要分配一個更大的segmentation替代
* 純paging：**不需要額外的dynamic memory allocation**，page本身的機制就支援分配新的page，而不需要重新分配舊的空間

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

## 8.5
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
| Memory allocation | External fragmentation | Internal fragmentation | Share Code |
|:-----------------:|:-----------------------------------------------------:|:---------------------------------------------------------------------------------------------------------------------------------:|:--------------------------------------:|
| Contiguous | fixed-size partition 不會；variable-size partition 會 | 會發生，有些process有資源過剩的情況 | 無法，每個 process 會有一份 code的副本 |
| Pure Segmentation | 會，Segmentation 也是一塊塊連續記憶體 | 不會，因為 Segment Table 記錄每個 segment 的 limit，可以從 memory 中的 base 提取所需長度(limit)，所以每個 segmentation 的大小不同 | 可以，藉由共用單一 segmentation |
| Pure Paging | 不會，Page size 夠小，可以完整利用整個記憶體 | 會，但發生的機率很小，因爲每個page的大小都很小。當 User Program 的大小不是 Page Size 的整數倍時，會產生內部破碎。 | 可以，藉由共用單一 frame |
> :star: pure paging 的 internal fragmentation:
> - ex1.
> - page size=4K, user program=21K, 需配置 6 個 frame，產生 24K-21K=**3K** 的內部破碎
> - ex2.
> - page size=100K, user program=101K, 需配置 2 個 frame，產生 200K-101K=**99K** 的內部破碎
> :heavy_exclamation_mark: Page Size 越大，破碎的情況越嚴重。:heavy_exclamation_mark:
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

## 8.11
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
### a. contiguous
contiguous memory allocation中，如果需要分配更多記憶體，則需要重新分配整個process，
### b. pure seg.
因爲segmentation同時兼具連續和區塊性，可以看作更有彈性的contiguous memory allocation，而需要記憶體時，只需要要求一塊新的segmentation而不用重新分配整個記憶體。
### c. pure paging
paging得益於量大而尺寸迷你的分頁，使得本身就具有極良好的動態記憶體分配能力，同時也可以用更小的尺度來分配記憶體，但是每一個process都需要分配page table消耗部分記憶體空間。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

## 8.12
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
$1KB = 1024 byte= 2^{10} byte$
一個offset由 10 個 bits 組成
* 除以 page size 的商即是 page number
* 除以 page size 的餘即是 page offset

### a. 3085
$3085 \div 1024 = 3 \ldots 13$

* page number = **3**
* page offset = **13**

### b. 42095
$42095 \div 1024 = 41 \ldots 111$

* page number = **41**
* page offset = **111**

### c.215201
$215201 \div 1024 = 210 \ldots 161$

* page number = **210**
* page offset = **161**

### d.650000
$650000 \div 1024 = 634 \ldots 784$

* page number = **634**
* page offset = **784**

### e.2000001
$650000 \div 1024 = 1953 \ldots 129$

* page number = **1953**
* page offset = **129**

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

## 8.15
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
Explanation

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

## 8.16
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
### a. page table
page size : 4 KB = 12 bytes -> offset is 12 bit
page number is 32-12 = 20 bit

A page table is 1MB which has $2^{20}$ entries.
### b. inverted page table
based on physical memory

$512 MB \div 4KB = 128*1024 = 2^{17}$

A inverted page table is 128KB which has $2^{17}$ entries.
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

## 8.20
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

## 8.23

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

when handling a large address spaces, the size of page table is getting very big, which is fatal in memory sensitive situation by page table devouring the memory space. For low-latency circumstances, iterating through the hierarchical page tables is also harmful to access time.

For the situation as using few address space, a full page table would be a huge waste and the hashed page tables provide a elegent solution to this problem by mapping multiple page table to one entry which is dynamic on the amount of address resulting space saving.

segmented paging is more efficient.
hashed page tables has higer space utilizaiton.

### 中文版
當地址空間很大時，page table也會變得很大，此時對於空間需求大的場景非常不利， 因爲會有一部分的memory被page table吃掉，而階層式的hashed page table則可以解決這個問題，尤其是實際使用的地址很少時，hashed page table新建的sub page table也會很少，這種情況就可以節省大量的空間，宏觀上類似一種動態大小的page table，但是相對的也增加了存取延遲，對於需要極低延遲的應用場景不利，但是在page table使用量不高和空間需求大的場景非常有利。

＊補充小東西＊

# 我的答案