Paging 將Virtual memory和Physical memory都劃分為固定大小的區塊，稱為page和frames。

以下是各個組件的說明：

* Virtual Address Space：這是process使用的地址範圍。每個process都有自己的Virtual Address Space，它不一定直接對應到Physical memory。

* Physical Address Space：這是系統中實際可用的物理memory，被劃分為固定大小的框架。

* Address Mapping Function（MAP）：此函數將Virtual 地址映射到Physical Address 。如果Virtual 地址對應的數據存在於Physical memory中，則映射函數會返回對應的Physical Address 。如果數據不存在，則返回空值（∅）。

* Address Translation：當程序引用Virtual 地址時，作業系統使用Address Mapping Function將其轉換為Physical Address 。如果Virtual 地址對應的數據存在於Physical memory中，則轉換成功。如果不存在，則OS可能需要從二級存儲（例如磁盤）中將所需的page加載到Physical memory中，然後完成轉換。

* Page Faults：如果程序訪問了一個目前未映射到Physical memory中的Virtual 地址，則會發生Page Faults。然後，OS通過從二級存儲中（例如磁盤）將所需的page加載到Physical memory中來處理此錯誤。

Paging 使得Physical memory能夠被有效利用，同時允許不同的process共享同一塊Physical memory，同時保持它們的Virtual Address Space獨立。

這種隔離和共享的組合是多道程序設計的基礎，使得多個process可以同時運行，而彼此之間不會互相干擾或影響。

每個process都有自己的Virtual Address Space，通過分頁的方式，可以讓每個process擁有一個連續的地址空間，而不受Physical memory的限制。

這樣，每個process可以以為自己獨有的方式使用內存，同時操作系統通過內部機制，保證了這些process之間的隔離性和安全性。
## Page Tables
Page Tables是一種儲存分配資訊的結構：

* 它由一系列的 Page Table Entries 組成，透過Virtual page編號進行索引。
* 在 CPU 中有一個Page Tables暫存器，指向Physical memory中的Page Tables。
* 如果page存在於memory中，Page Tables項目儲存了Physical page編號，以及其他狀態位（如被參考過、被修改過等）。
* 如果page不存在於memory中，Page Tables項目可以參考到位於磁碟上交換空間的位置。

## Page Replacement and Writes
Page Replacement and Writes 是兩個重要的概念：

* 為了降低page錯誤率，傾向於使用最近最少使用（LRU）替換策略：
* 在訪問page時，Page Table項目中的參考位（也稱為使用位）被設置為1。
* 由OS定期將參考位清零，以確定該page是否最近被使用過。
* 參考位為0表示該page最近未被使用。
* 磁碟寫入需要數百萬個週期：
* 寫入操作通常以區塊為單位，而不是單個位置。
* 寫通過（Write-through）方法不切實際，因為寫入操作太頻繁。
* 採用寫回（Write-back）方式。
* 當page被寫入時，Page Table項目中的髒位被設置。

## Problems of Page Table

Page Table存在以下問題：

* Page Table過於龐大：隨著系統中process數目的增加，Page Table的大小也會增加，可能會占用大量的memory空間。
* 存取Page Table速度太慢：獲取Page Table內容需要進行一次memory讀取操作，這會增加存取page映射信息的時間成本。

Page的影響之一是可能導致龐大的Page Table大小：

* 假設Virtual Address Space為32位元，page大小為4KB，每個Page Table項目（PTE）占用4位元組。這意味著每個Virtual Address Space可能需要2^20個PTE。因此，Page Table大小為4MB。
* 可能的解決方案包括：
* 使用界限register來限制表的大小，如果超出限制，則可以添加更多的界限register。
* 允許page在兩個方向上擴展，因此可能需要兩個表，兩個界限register（一個用於散列，一個用於堆棧）。
* 使用哈希方法，這樣Page Table的大小就與物理page相同。
* 使用多級Page Table。
* 使用Page的Page Table（即Page Table位於virtual space中）。

對於具有Two-level Page Tables結構的32位元地址空間：

* 地址分為三個部分：
* P1 索引（10位元）：用於索引第一級Page Table（PTE1）。
* P2 索引（10位元）：用於索引第二級Page Table（PTE2）。
* Page offset（12位元）：指示頁內的偏移量。
考慮到Virtual 地址空間為4 GB，假設每個Page Table項目（PTE）為4 KB：

PTE1 覆蓋 4 GB / （4 KB）= 1M 個項目。
PTE2 覆蓋 4 MB / （4 KB）= 1K 個項目。
現在，讓我們考慮一個更大的地址空間，例如48位元或64位元：

* 對於48位元地址空間，Page Table結構可能保持不變，但 PTE1 和 PTE2 的項目數量將相應增加，以覆蓋更大的地址空間。您需要根據新的地址空間大小重新計算。
* 對於64位元地址空間，Two-level Page Tables結構可能不足以有效地覆蓋整個地址空間。在這種情況下，可能需要具有更多級別的多級Page Table結構來有效管理較大的地址空間。每個額外的Page Table級別將提供更多的索引位元，從而允許覆蓋更大的地址空間。具體的細節將取決於系統的具體要求和限制。

Page Table的影響之一是增加了對memory的訪問次數：

* 每次memory操作（指令取出、加載、存儲）都需要訪問Page Table。
* 基本上，這意味著memory操作的數量翻倍：
* 首先是訪問Page Table，然後才是實際的memory訪問。
* 這增加了系統的負擔，尤其是在訪問Page Table時，因為它需要兩次memory訪問。

儘管如此，需要指出的是，訪問Page Table具有良好的局部性，這意味著經常訪問相鄰的Page Table項目，這些項目通常位於相同的Page Table頁面中，從而減少了對Physical memory的訪問時間。

## Fast Translation Using a TLB
TLB（Translation Look-aside Buffer）是一種位於 CPU 內的cache，用於加速Page Table轉換的過程：

* Page Table訪問具有良好的局部性，意味著CPU經常訪問相鄰的Page Table項目。
* TLB將最近使用的Page Table項目暫存在CPU內，因此在進行地址轉換時，CPU可以直接從TLB中獲取所需的Page Table項目，而不必每次都訪問主記憶體中的Page Table。
* 這樣可以大大加速地址轉換的過程，因為TLB的訪問速度比訪問主記憶體快得多。

總之，TLB作為一種cache，幫助CPU加快了對Page Table的訪問，從而提高了系統的整體性能。