## Swapping

將不常用的或暫時不需要的 page table 從主記憶體（RAM）移到次級存儲裝置（通常是disk），以釋放出 RAM 空間供其他頁面使用。

* process 可以從 memory Swapping 到backing store，然後再帶回memory以連續執行
> 也用於期中調度，與context switch不同

#### backing store - 與文件系統分離的一塊 disk ，用於提供對這些文件的直接訪問 memory 圖像

#### 為什麼 Swapping process：
當一個程序運行時，它的 memory 需求可能會超過RAM的容量。

RAM的大小是有限的，當同時運行的 process 數量增加或者某個 process 需要更多的 memory 時，可能會導致RAM不足。這種情況下，操作系統需要采取一些措施來處理 memory 不足的問題，其中一個方式就是進行 process 交換釋放memory
* Roll out, roll in：將優先級較低的process與優先級較高的process Swapping
* "Roll out" 是指將一個 memory page 從 RAM 中移出，並存儲到次級存儲裝置（通常是disk）的交換文件中。
* "Roll in" 是指將一個先前被 "rolled out" 的 memory page 從次級存儲裝置（通常是disk）的交換文件中讀回到 RAM 中。

#### Swapping 回memory位置
* 如果綁定是在compile/load時完成的
-> 換回memory addr必須相同
* 如果綁定是在 execution 時完成的
->換回memory addr可以不同

#### 要 Swapping 的process 必須是空閒的
* 想像一個正在等待 I/O Swapping 的process
* 解決方案：
• 切勿 Swapping 具有待處理 I/O 的process
I/0 操作是通過作業系統緩衝區完成的（即不屬於任何用戶process的memory空間）

#### process Swapping 到backing store
* Swapping 時間的主要部分是傳輸時間； 總傳輸時間與 Swapping 的 memory 量成正比

## memory 分配
* Fixed-partition：

* 每個process加載到固定大小的一個分區中
* 多道程序設計的程度受分區數量限制
* Variable-size partition
* Hole：連續空閒memory塊
* 各種大小的 Hole 分散在memory中

### 多分區(Variable-size)方法
* 當一個process到達時，它被分配一個足夠大的洞來容納它

* 作業系統維護信息。 在每個使用中和空閒的孔上
* 釋放的孔可以與另一個孔合併以形成更大的孔


#### 動態存儲分配問題
如何從空閒孔列表中滿足大小為 n 的請求
* First-fit - 分配第一個適合的孔
* Best-fit - 分配最適合的最小孔

* 必須搜索整個列表
* Worst-fit — 分配最大的孔
* 還必須搜索整個列表
* 在速度和存儲利用率方面，First-fit 和 Best-fit 優於 Worst-fit

## Fragmentation
* External fragmentation
* 總可用memory空間足以滿足請求，但不連續
* 發生在可變大小分配中
* Internal fragmentation
* 分區內部但未使用的memory
* 發生在固定分區分配中
* Solution: compaction
* 在執行時打亂memory內容，將所有空閒memory放在一個大塊中
* 僅當綁定在執行時完成


## Paging Concept
* 方法：
* 將 physical memory 劃分為固定大小的塊，稱為frames
* 將 logical address 空間劃分為相同大小的塊（稱為pages）
* 運行一個n pages的程序，需要找到n個空閒frames並加載程序
* 跟踪空閒frames
* 設置pages table以將logical address轉換為physical memory
* 好處：
* 允許process的 physical memory 空間不連續
* 避免External fragmentation
* 有限的Internal fragmentation
* 提供 sharing memory/pages table

若要比較page 與 frame 的差別，可以想像成 筆記本 與 卷軸

筆記本的紙頁 (page) 是一張一張的，並且各個 process 都能夠借來共用，不必擔心一個人佔用太多紙頁(page)

但卷軸的紙frame是一卷紙所有 process 共用，若是process間有佔用太多 frame 的 process，便只能夠其他 process 等待這個 process完成作業。

## Paging 示例
pages table：
* 每個 entry 映射到 physical memory 中pages table的基addr
* 操作系統為每個process維護的結構
pages table僅包含process擁有的pages
process無法訪問其空間之外的 memory


## addr轉換方案
logical address 分為兩部分：
* Page number ( p )
* 用作 pages table 的索引， pages table 包含 physical memory 中每個頁的基addr
* N 位表示一個 process 最多可以分配 2^N 個page table
* →2^N x 頁大小 memory 大小
* page offset ( d )
* 與 base addr 結合定義發送到 memory 單元的 physical memory addr
* N 位表示page table大小為 2^N
* physical memory = page base addr + page offset

## addr轉換架構
如果page table大小為 1KB(2^10) 並且 Page 2 映射於 frame 5
給定 13 位 logical address ：(p=2,d=20)， physical memory 是什麼？
physical memory 是什麼？ 5 * (1KB) + 20=1,010,000,000,000+0,000,010,100 =1,010,000,010,100


## addr翻譯
* 總 page 數不必與總幀數相同
* 總 # page 數決定 process 的 logical memory 大小
* 總 # frames 數取決於 physical memory 的大小
* 例如：給定32位 logical addr、36位 physicaladdr和4KB page 面大小，這意味著什麼？
* pages table 大小：2^32 / 2^12 = 2^20 個 entry
* 最大program memory ：2^32 = 4GB
* 總physical memory 大小：2^36 = 64GB
* page number 位數：2^20 頁 -> 20bits
* page offset 位數：4KB 頁大小 = 2^12 字節 -> 12


## page/frame尺寸
* page（frame尺寸）大小由硬體定義
* 通常為 2 的冪
* 從512字節到16MB/page不等
* 常用4KB/8KB頁
* Internal fragmentation? > Larger page size→ More space waste
* 但page sizes隨著時間的推移而增大
* memory, process, data sets集變得更大
* 更好的 I/O 性能（page table錯誤期間）
* page table較小

# Paging
* Paging 有助於將user's view of memory 與實際physical memory分開
* user's view of memory：一個連續的空間
* 實際上，user's memory分散在physical memory中

* 作業系統為每個 process 維護 page table 副本
* 作業系統維護一個 frame table 來管理physical memory
* 每個 physical frame 一個 entry
* 指示 frame 是空閒的還是已分配的
* 如果分配的話，分配給哪個 process 的哪個page

### Page Table的實現

* Page table 保存在 memory 中
* Page-table base register (PTBR)
* Page Table 的 physical memory address
* PTBR值存儲在PCB(Process Control Block) 中
* 在 Context-switch 期間更改 PTBR 的值
* 使用PTBR，每個 memory 引用都會產生
* 2 memory 讀取
* 一份用於Page Table，一份用於真實addr
* 2-access 問題可以通過 > Translation Look-aside Buffers (TLB) (HW) 來解決，它是由 **Associative memory** (HW) 實現的

## Associative memory
所有 memory entries 可以同時訪問
> 每個 entry 對應一個associative register
但 entries 數量有限
> 典型entries數：64~ 1024
聯想記憶——並行搜索

addr轉換（A'，A''）
* 如果 A' 在關聯寄存器中，則取出 #frame。
→ 否則從memory中的page table獲取 #frame

### Translation Look-aside Buffer (TLB)
■ 所有 processes sharing 的Page Table高速緩存

用於存儲最近經常使用的虛擬addr和相應的Physicaladdr之間的映射關係。

每當處理器需要進行addr轉換時，它首先在TLB中查找。

如果在TLB中找到了對應的虛擬addr，則可以立即獲取Physicaladdr，從而節省了訪問Page Table的時間。

context switch後必須刷新 TLB 否則，TLB entry 必須具有 PID 字段（addr空間標識符 (ASID)） (address-space identifiers (ASIDs))


### 有效memory訪問時間
* TLB 搜索 20 ns
* memory訪問時間為100 ns
* 有效memory訪問時間 (EMAT)
> 70% TLB 命中率：

EMAT = 0.70 x (20+100) + (1-0.70) (20+100+100) = 150 納秒
>98% TLB 命中率

EMAT 0.98 x 120 +0.02 x 220 = 122 納秒

## Memory protection
每個頁都與Page Table中的一組 protection 位相關聯
> 例如，定義讀/寫/執行權限的位
* 常用：有效-無效位
* 有效：page/frame於process的logical addr空間中，因此是合法page table
* 無效：page/frame不在process的logical addr空間中

#### 有效-無效位 示例
潛在問題：
* 未使用的頁 entry 導致Memory 浪費→使用Page Table長度寄存器（PTLR）
* process Memory 可能不在page Memory 限制寄存器的邊界上，但仍然需要


## sharing pages

Each page 允許process sharing 公共code，這些 code 必須是 Reentrant code
■ Reentrant code（純code）
> 在執行過程中它永遠不會改變
> 文本編輯器、編譯器、網絡服務器等

■ Physical Memory 中只需保存一份 sharing code
兩個（多個）logical addr映射到一個Physicaladdr
process 保留自己的私有數據和code的副本

#### Shared Pages by Page Table
■ sharing code 必須出現在所有 process 的 logical addr 空間中的同一位置


## Page Table memory 結構

Page Table可能很大並且難以加載
4GB (2^32) logical addr空間，具有 4KB (2^12) 頁
→ 100萬（2^20）個 Page Table 項
> 假設每個 entry 需要4個字節（32位）

總大小 = 4MB
> 需要將其分成幾個較小的Page Table，最好在單個page table大小（即 4KB）內
> 或者減小Page Table總大小

Physical memory 中只需保存一份 sharing 代碼
兩個（多個）logical addr映射到一個 Physical addr

**相當於一個二維(多維)陣列，將一個陣列給分得更細**


## 64 bit addr
64位addr怎麼樣？ （假設每個 entry 需要4Bytes）
>42 (p1) + 10 (p2) + 12（偏移量）

→ 外表需要 2^42 x 4B = 16TB 連續 memory ！
> 12 (p1) + 10 (p2) + 10 (p3) + 10 (p4) + 10 (p5) + 12（偏移）

→ 外表需要 2^12 x 4B = 16KB 連續 memory
→6 次 memory 訪問！！！

例子：
> SPARC（32 位）和 Linux 使用 3 級 paging
> Motorola 68030 (32位) 使用 4 級 paging

## Hashed Page Table
* Hashed Page Table 使用 hash 函數將 Physical addr 號碼映射到 Page Table 中的索引位置。 hash 函數將 Physical addr 號碼轉換為一個數字或索引，這個索引對應到 Page Table 中的 entry 。

* 由於 logical addr號碼的範圍可能大於Page Table entry的數量，因此可能會出現hashed碰撞的情況
>即兩個或多個 logical addr映射到相同的索引位置。

* 為了處理碰撞，hashed Page Table通常使用"碰撞解決策略"，例如 linked list 或 tree

* 常用於addr
> 32位

## Inverted Page Table

* 在 Inverted Page Table 中，每個 Physical table 都有一個 entry，該entry 紀錄了該 Page 所對應的 Page Table（或process）的相關信息

* 例如 logical table 的標識符或指標。這樣的設計可以使多個 logical table 共享相同的 Physical Page Table，並且可以方便地進行查詢。

>是將Physical Page Table 映射到 logical Page Table 的資料結構。
通常用於logical空間很大但Physical addr量有限的情況

* frame table中的每個 entry 都有（PID、頁碼）
* 消除 page tables 所需的memory ，但增加memory 訪問時間
* 每次訪問都需要查找整個page tables
* 解決方案：對page tables使用hashing


# Segmentation

是一種記憶體管理的方式，用於將logical addr空間分為不同的logical unit或block。每個 Segmentation 具有不同的大小和用途，Segmentation 是一個 logical unit，例如：
>main program
> function, object
> local/global variables,
stack, symbol table,
> arrays, etc...


## Segmentation Table

* Logical address: (seg#, offset)

* Offset 與 physical addr的長度相同。
* Segmentation table - 映射二維Physical address； 每個table entry有：
> Base（4字節）：起始Physical address
> Limit（4字節）：段的長度

Segment-table base register （STBR）：
> 分段表的Physical address

Segment-table length register（STLR）：
> 段數

## Segmentation Hardware
Limit register 用於檢查 offset 長度
MMU通過為每個段分配適當的基地址來分配 memory
> 段之間的Physical address不能重疊
>

## Address Translation Comparison
* Segment
> Table entry: (segment base addr., limit)
> Segment base addr. 可以是任意的
> “offset”的長度與physical memory size相同

* Page:
>Table entry: (frame base addr.)
Frame base addr. = frame number * page size
“offset”的長度與page size相同


## Sharing of Segmentation


## Protection & Sharing
* 與 segments 相關的 Protection bits
> Read-only segment (code)
Read-write segments (data, heap, stack)

* Code sharing 發生在 segment level
> Shared memory 通信
> Shared library

通過在兩個 segment tables 中具有相同的基數來 Share segment

## Basic concept

* 在logical address space中應用segmentation
* 在physical address space中應用paging


## Address Translation
* CPU 生成 logical address
>給定segmentation unit → 產生linear addresses
> Linear address 分配給 paging unit

→ 在 main memory 中生成 physical address

* Segmentation 跟 paging units 相當於MMU

## Intel Pentium Segmentation

* Segment descriptor
> Segment base address和length
> 訪問權限和特權級別


## Intel Pentium Paging (Two-Level)
Page size 可以是 4KB 或 4MB
> 每個 page 目錄項都有一個 flag 用於指示

## Example Question
* 假設 physical mem size為512B，page size 為32B，程序的logical address 可以有8個segments。 給定 12 位十六進制logical address “448”，轉換 addr。 帶有 blow page 和 segment tables。

* 線性地址：010111110，物理地址：001011110