嗚呀～今天人在台東，但也不能忘記發文＠＠

分頁（paging）

在傳統的連續記憶體配置中，一個完整的程式（或行程）必須被完整地載入到一塊連續的實體記憶體區塊中。當記憶體中的程式不斷進出時，會留下許多大小不一的「小洞」。即使這些小洞的總和空間足夠容納一個新程式，但因為沒有一個單一、連續的大洞，導致新程式無法被載入，這就是外部碎裂。而分頁（Paging）能夠解決外部碎裂（External Fragmentation）的原因，在於它徹底改變了程式在記憶體中存放的方式。

• Page（頁）：將邏輯記憶體切成固定大小的區塊（通常 4 KB）
• Frame（框）：將實體記憶體切成相同大小的區塊
• Page Table（頁表）：記錄每個頁（page）對應到哪個框（frame）

分頁系統則引入了「非連續記憶體配置」的概念。它將程式的邏輯記憶體切成固定大小的頁（Page），並將實體記憶體也切成相同大小的框（Frame）。當程式需要被載入時，它的各個頁可以被分散地載入到實體記憶體中任何可用的框裡，不需要連續排列。這樣一來，無論實體記憶體中的空洞多麼分散，只要能找到足夠多的「框」來存放程式的「頁」，程式就能順利載入。系統不再需要尋找一大塊連續的空間，而是只需要將這些小空洞（框）拼湊起來，這就從根本上消除了外部碎裂的問題。

分頁的缺點：內部碎裂

雖然分頁解決了外部碎裂，但它也可能產生內部碎裂（Internal Fragmentation）。內部碎裂指的是：當記憶體被分配給一個程式時，實際分配的空間比程式所需要的空間還要大，而多出來的這部分空間因為太小，無法被其他程式使用，因此被浪費掉。在分頁系統中，這種情況發生在每個「頁」的最後。因為頁的大小是固定的（例如 4 KB），如果一個程式的大小不是頁大小的整數倍，那麼它的最後一頁就不會被完全填滿。

舉例來說，如果一個程式的大小是 13 KB，而頁的大小是 4 KB：

• 前三頁（Page 0, 1, 2）將各佔用 4 KB，總共 12 KB。
• 最後剩下的 1 KB 內容會被放入第四頁（Page 3）中。
• 但是，系統會為 Page 3 分配一個完整的 4 KB 框。
• 這導致在 Page 3 的框中，有 3 KB 的空間是沒有被使用的，這 3 KB 就是內部碎裂。

地址轉換過程

每個邏輯位址分為兩部分：

Logical Address = [ p | d ]
p = Page number（頁號）
d = Page offset（頁內偏移）

轉換公式為：Physical Address = (Frame number × Frame size) + d

假設：
page size = 4 bytes，Logical address = 13
Page number = 13 / 4 = 3, offset = 1
查 page table 得 page 3 → frame 2
所以 physical address = (2 × 4) + 1 = 9

硬體支援與 TLB（Translation Lookaside Buffer）

當分頁（Paging）透過頁表（Page Table）將邏輯位址轉換成實體位址。這個過程會產生一個嚴重的效能問題：每次資料存取都需要兩次記憶體存取。

第一次存取：從主記憶體讀取頁表，以找到對應的頁框號碼（Frame number）。
第二次存取：利用這個頁框號碼，從主記憶體存取實際的資料。

這使得分頁系統的執行速度變成傳統記憶體存取的一半，顯然是無法接受的。為了解決這個問題，硬體設計者引入了一種名為 TLB（Translation Lookaside Buffer） 的硬體裝置。

什麼是 TLB

TLB 是一種小型、高速的專用快取記憶體，專門用來存放最近被存取過的頁表項目。你可以把它想像成一個小型的、專門的頁表副本，它直接內建在記憶體管理單元（MMU）中，通常位於 CPU 晶片上，因此速度比主記憶體快上許多。

TLB 的運作原理非常簡單，就像任何快取一樣：它利用了參考的局部性原理（Principle of Locality of Reference），即程式在執行時，會重複存取相近的位址。因此，最近被存取過的頁表項目很可能在不久的將來會再次被存取。

TLB 的運作流程

1. 當 CPU 產生一個邏輯位址（Logical Address）時，位址轉換的過程會優先查詢 TLB，而不是直接去主記憶體中的頁表。
2. 查詢 TLB：系統首先會用頁號（p）去查詢 TLB。這個查詢是透過硬體並行完成的，速度非常快。
   • TLB Hit（命中）：如果 TLB 中找到了該頁號對應的頁框號碼（Frame number），這就是「TLB 命中」。系統會直接從 TLB 取得頁框號碼，然後直接進入下一步計算實體位址。這個過程只需要一次記憶體存取（存取資料本身）。
   • TLB Miss（未命中）：如果 TLB 中沒有找到該頁號，這就是「TLB 未命中」。此時，系統才會去主記憶體中查詢完整的頁表，找到對應的頁框號碼。找到後，這個頁號和頁框號碼的配對會被存入 TLB 中，以供下次使用。如果 TLB 已滿，會根據替換演算法（如 FIFO、LRU 等）替換掉舊的項目。此過程需要兩次記憶體存取。
3. 計算實體位址：無論是從 TLB 還是頁表取得頁框號碼，最終都會用相同的公式計算出實體位址：Physical Address = Frame * Frame size + Offset。

TLB Hit Rate

TLB 的效能取決於它的命中率（Hit Rate）。命中率越高，表示邏輯位址轉換的過程越常在高速的 TLB 中完成，而不必去存取速度慢的主記憶體。

舉例而言，如果 TLB 的命中率是 90%，假設主記憶體存取時間為 100ns，TLB 存取時間為 20 ns。

在沒有TLB情況下，每次存取都需要兩次主記憶體存取，總時間為 2 * 100 ns = 200 ns。
而有TLB情況下：

• 命中時（90%）：TLB 存取 (20 ns) + 主記憶體存取 (100 ns) = 120 ns。
• 未命中時（10%）：TLB 存取 (20 ns) + 兩次主記憶體存取 (100 ns + 100 ns) = 220 ns。
• 平均存取時間 = (0.90 * 120 ns) + (0.10 * 220 ns) = 108 ns + 22 ns = 130 ns。
  從這個簡單的例子可以看出，即使 TLB 只有 90% 的命中率，它也能顯著地降低平均記憶體存取時間，讓分頁系統的效能趨近於單次記憶體存取。

分頁保護機制（Paging Protection Mechanisms）

在分頁系統中，每個程式都擁有自己獨立的邏輯位址空間，並透過頁表（Page Table）映射到實體記憶體。然而，如果沒有適當的保護機制，一個程式可能會意外或惡意地存取不屬於它的記憶體區域，例如：

• 非法越界存取：程式存取超出其分配範圍的記憶體，例如陣列索引超出界限。
• 破壞共享資料：程式不小心寫入到其他程式（例如作業系統核心或共享函式庫）的記憶體頁面，造成系統不穩定或崩潰。

為了解決這些問題，分頁系統在硬體層級提供了保護機制。這些保護機制的核心是在頁表中為每個頁面附加額外的控制位元（control bits），讓記憶體管理單元（MMU）在進行位址轉換時，同時檢查這些位元，以確保存取的合法性。

除了記錄邏輯頁（Page）與實體框（Frame）的對應關係外，頁表中的每一個項目（entry）還包含了以下重要的保護位元：

1. 保護位元（Protection Bits）：這些位元用來設定每個頁面的存取權限。最常見的三種權限是：

   • 讀（Read）：允許程式讀取該頁面的內容。
   • 寫（Write）：允許程式修改該頁面的內容。
   • 執行（Execute）：允許程式從該頁面中執行指令。
     舉例來說，一個包含程式碼的頁面通常會設定為「可讀可執行但不可寫」，以防止程式意外修改自身的程式碼。而一個資料頁面則可能設定為「可讀可寫但不可執行」。如果 CPU 試圖執行一個不被允許的動作（例如寫入一個只讀頁面），MMU 會立刻觸發一個陷阱（trap），將控制權交還給作業系統，由作業系統來處理這個錯誤。

2. 有效/無效位元（Valid/Invalid Bit）：這個位元是分頁保護機制中最基礎的防護。它用來標記頁表中的一個項目是否有效，即該邏輯頁是否屬於目前程式的合法邏輯位址範圍。

   • 有效位元（V）：表示該頁是合法的，並且已經載入到實體記憶體中的一個框裡。MMU 會繼續進行位址轉換。
   • 無效位元（I）：表示該頁是無效的，即不屬於該程式的合法位址空間。這通常發生在：

運作流程：

• CPU 產生邏輯位址 (p, d)
• MMU 查 page table
• 檢查有效位元：
  • V（有效）： 繼續轉換 frame number
  • I（無效）： 觸發 trap（異常），交由 OS 處理
    • 可能是 非法存取 → 程式中止
    • 可能是 頁面不在記憶體（page fault） → OS 從硬碟載入該頁

Shared Pages（共用頁面）

在多工作業系統中，多個程式（Process）經常需要使用相同的資源，最常見的就是標準函式庫（Standard Libraries）、系統呼叫介面或共用的執行檔。如果每個程式都單獨複製一份這些共用的程式碼到自己的記憶體空間中，會造成極大的記憶體浪費。

舉例來說，當你同時開啟多個瀏覽器分頁時，每個分頁背後的瀏覽器程式（例如 Chrome）都使用相同的核心程式碼。如果這些核心程式碼被每個分頁單獨載入一次，會佔用大量的實體記憶體。為了解決這個問題，分頁（Paging）系統提供了一個強大的機制：共用頁面（Shared Pages）。

共用頁面的核心思想是，讓多個程式可以共用一份存在實體記憶體中的程式碼副本。這個機制之所以可行，是因為分頁將邏輯位址與實體位址分開，並透過頁表（Page Table）進行映射。

1. 實體記憶體只有一個副本：共用的程式碼（例如 libc.so 函式庫）只會被載入到實體記憶體中的一個固定區域。
2. 每個程式都有自己的頁表：每個使用這個函式庫的程式，其頁表中都會有一個項目，將一個特定的邏輯頁（例如 Page 3）映射到實體記憶體中存放該函式庫的同一塊實體框（Frame）。
3. 多對一映射：兩個或多個程式的頁表，其各自的邏輯頁號會同時指向實體記憶體中的同一個實體框。

可重入程式碼（Reentrant Code）

共用頁面機制要能安全運作，前提是所共用的程式碼必須是可重入的（Reentrant），也稱為純程式碼（Pure Code）。可重入程式碼指的是一種特殊的程式碼，它在執行過程中不會修改自身的內容。這意味著：

• 只讀性質：程式碼中不包含任何寫入操作，所有變數和狀態都存放在每個程式獨立的資料區（Data Segment）中。
• 無內部狀態：程式碼的執行結果完全取決於輸入參數，而不受之前執行的狀態或全域變數的影響。

因此，即使有多個程式同時執行同一份可重入程式碼，它們各自的變數、堆疊（Stack）和資料都是獨立的，互不干擾。這就確保了共用程式碼的安全性：一個程式的執行不會意外地修改或破壞其他程式所使用的程式碼。

頁表的結構設計 (Structure of the Page Table)

在分頁系統中，每個 process 都有一份 page table，用來記錄邏輯頁號（Page Number）與實體框號（Frame Number）的對應。

• 32-bit 系統：邏輯位址空間 = 4GB
• Page size = 4KB → 1 個 process 需要：
  • 4GB / 4KB = 2^20 = 1M 個頁表項目
  • 每項 4 bytes → 4MB 的 page table

若有數百個 process 同時執行 → page table 空間消耗極大。解決方案：改良頁表結構，降低記憶體浪費。

階層式分頁（Hierarchical Paging）

不再使用單一線性（flat）頁表。改成多層頁表（multi-level page table）。
分頁 page table 本身，只建立需要的部分，節省空間。

範例：二階層分頁範例（Two-Level Paging）

• 32-bit 位址空間
• Page size = 4KB → offset = 12 bits
• 剩下 20 bits 作為頁號，拆成：
• 地址格式：|p1 (10 bits)|p2 (10 bits)|d (12 bits)|

運作流程：

• CPU 提供邏輯位址 (p1, p2, d)
• 外層頁表（Page Directory）：用 p1 找到內層頁表位置
• 內層頁表（Page Table）：用 p2 找到 frame number
• 組合 frame number + offset → 物理位址

雜湊頁表（Hashed Page Table）

• 適用於 64-bit 位址空間（非常大且稀疏，頁表太龐大）
• 使用雜湊函式（hash function）快速定位頁表項

運作流程：

• 取虛擬頁號 p
• 計算 hash(p) → 找到 hash table index
• 該索引對應一條 linked list
• 遍歷該 list：
  • 若找到虛擬頁號匹配 → 取得對應 frame number
  • 找不到 → 表示該頁不存在（可能 page fault）

反向頁表（Inverted Page Table）

傳統缺點：每個 process 都有一份 page table，當系統 process 很多時，浪費大量記憶體。

核心概念：

• 只建立一張 全域頁表（全系統共用）
• 每個實體框（frame）對應一個表項
• 表項內容：<Process ID, Page Number>

運作流程：

• CPU 產生邏輯位址 (PID, PageNumber, Offset)
• 在反向頁表中搜尋該 <PID, PageNumber> 是否存在
• 找到 → frame number + offset = physical address
• 找不到 → page fault

Swapping

Swapping（交換）是指將整個程序或程序的一部分從主記憶體移到備份儲存裝置（如硬碟）以釋放記憶體空間，等到需要時再搬回主記憶體。這項技術的目的是：允許實體記憶體不足的情況下，同時容納更多程序，提升多工程度（degree of multiprogramming）。

Standard Swapping（標準交換）

1. 系統將整個 Process P1 swap-out 到 backing store（例如硬碟）。
2. 騰出的空間可供其他程式如 P2 swap-in 執行。
3. 當 P1 再次活躍時，再把它 swap-in 回來。

儲存內容包括：

• 程式本體與資料
• Thread 的資料結構（若是多執行緒）
• 作業系統追蹤的中介資料（metadata）

優點是有效利用有限的主記憶體資源，非常適合用於「長時間閒置的程序」。缺點是整體速度慢，因為搬移整個程序耗時。在記憶體壓力不大的現代系統中已不常見。

Swapping with Paging（分頁交換）

標準交換是要般整個 process。分頁交換的話是只搬「需要的頁面」（Page-level Swapping）。優勢

• 效率更高 → 僅搬移活躍頁面
• 節省 IO 開銷
• 能與虛擬記憶體完美整合