# Background
* 程式必須（從磁碟(disk)）放入記憶體(memory)並放置在進程中才能運行
* 主記憶體(Main memory)和暫存器(registers)是CPU唯二可以直接存取的存儲(storage)
* 記憶體單元只看到一個流(stream)：
* 位址(addresses)+讀取請求(read requests)，或
* 位址+資料(data)和寫入請求(write requests)
* 暫存器存取(Registers access)會在一個 CPU 時脈（或更少）內完成
* 主記憶體可能需要許多週期，導致停頓(stall)->delay=>thats why we use cache
* 高速緩存(Cache)位於main memory和 CPU registers之間
* 確保正確操作所需的記憶體保護

## Protection
* 需要確保進程只能存取其位址空間中的那些位址。
* 我們可以透過使用一對定義進程邏輯位址空間的**基址和限制暫存器**(**base** and **limit registers**)來提供這種保護

## Hardware Address Protection
* CPU 必須檢查在使用者模式(user mode)下產生的每個記憶體訪問(memoty access)，以確保它位於該使用者的基本和限制之間
* 載入基址和限制暫存器的指令是有特權的(1)
* 此方案可防止使用者程式（意外或故意）修改作業系統或其他使用者的程式碼或資料結構

# Address Binding(綁訂)
* 磁碟上的程序，準備好從輸入佇列放入記憶體中執行
* 不支持，必須載入到地址0000
* 讓第一個使用者進程物理位址始終位於 0000 很不方便
* 怎麼可能不是呢？
* 在程式生命週期的不同階段，地址以不同的方式表示
* 原始碼位址通常是符號性的
* 編譯程式碼位址綁定到可重定位位址
* 即“從該模組開始算起 14 個位元組”
* 連結器或載入器會將可重定位位址綁定到絕對位址
* i.e. 74014
* 每個綁定將一個位址空間映射到另一個位址空間

## Binding of Instructions and Data to Memory
* 指令和資料到記憶體位址的位址綁定可以發生在三個不同的階段
* 編譯時(Compile time)：如果先驗知道記憶體位置，則可以產生**絕對程式碼**(absolute code)；如果起始位置發生變化，則必須重新編譯程式碼。 （MS-DOS .com 格式）
* 載入時間(Load time)：如果編譯時不知道記憶體位置，則必須產生**可重定位程式碼**(relocatable code)。最終出價將延遲至載入時間。
* 執行時間(Execution time)：如果進程在執行期間可以從一個記憶體段移動到另一個記憶體段，則綁定會延遲到運行時
* 需要地址映射的硬體支援（例如基址和限制暫存器）

## Multistmp Processing of a user program
* 來源程式中的位址一般都是符號性的（例如count）
* 編譯器會將符號位址綁定到可重定位位址（例如「從開頭算起的14個位元組」）
* 將可重定位位址綁定到絕對位址
* 每個綁定都從一個位址空間映射到另一個位址空間

# Logical vs. Physical Address Space
* 綁定到單獨物理位址空間的邏輯位址空間的概念對於正確的記憶體管理至關重要
* 邏輯位址(Logical address)－由CPU產生；也稱為虛擬位址(virtual address)
* 實體位址(Physical address)－記憶體單元(memory unit)看到的位址
* 邏輯位址和物理位址在編譯時和載入時位址綁定方案是相同的；邏輯（虛擬）和實體位址在執行時位址綁定方案上有所不同
* 邏輯位址空間：程式產生的所有邏輯位址的集合
* 物理位址空間：程式產生的所有實體位址的集合

## Memory-Management Unit(MMU)
* 在運行時將虛擬位址對應到實體位址的硬體設備
* 本章其餘部分將介紹多種可能的方法

* 考慮簡單的方案。這是基址暫存器方案的推廣。
* 基址暫存器現在稱為**重定位暫存器**(relocation register)
* 重定位暫存器中的值在使用者進程產生的每個位址被傳送到記憶體時被加入到該位址中
* 使用者程式處理的是邏輯位址(logical addresses)；它永遠看不到真正的實體地址(physical addresses)
* 當引用記憶體中的位置時，就會發生執行時綁定
* 邏輯位址與實體位址綁定

## Dynamic Loading
* 整個程式確實需要在記憶體(memory)中才能執行
* 例程(Routine)在呼叫之前不會載入
* 更好的記憶體空間利用率；從未載入未使用的例程
* 所有例程均以可重定位載入格式儲存在磁碟上
* 當需要大量程式碼來處理不經常發生的情況時很有用
* 不需要作業系統的特殊支持
* 透過程式設計來實現
* 作業系統可以透過提供庫(libraries)來幫助實現動態加載(dynamic loading)

## Dynamic Linking
* 靜態連結(static linking)－載入器將系統庫和程式碼組合成二進位程式映像
* 動態連結(Dynamic linking)－連結推遲到執行時間
* 小段程式碼，存根(stub)，用於定位適當的記憶體駐留庫例程
* 存根(stub)將其自身替換為例程的位址，並執行例程
* 作業系統檢查例程是否在進程的記憶體位址中
* 如果不在位址空間中，則新增至位址空間
* 動態連結對於函式庫特別有用
* 系統(system)也稱為共享庫(shared libraries)
* 考慮修補系統庫的適用性
* 可能需要版本控制
---
# Contiguous Allocation
* 主記憶體必須支援作業系統和使用者進程
* 有限的資源，必須有效分配
* 連續配置(contiguous allocation)是早期的一種方法
* 主記憶體通常分為兩個分區：
* 駐留作業系統(resident operating system)，通常存放在低記憶體中，帶有中斷向量(interrupt vector)
* 然後使用者進程存放在高記憶體中
* 每個進程包含在單一連續的記憶體部分中

* 重定位暫存器用於保護使用者進程彼此之間，以及防止更改作業系統程式碼和資料
* 基底暫存器包含最小物理位址的值
* 限制暫存器包含邏輯位址的範圍 - 每個邏輯位址必須小於限制暫存器
* 記憶體管理單元(MMU)動態映射邏輯位址
* 然後可以執行像是核心程式碼是暫時的以及核心大小變更的動作

## Hardware Support for Relocation and Limit Registers

## Variable Partition(可變分區)
* 多分割分配
* 多工程程度受到分割數量的限制
* 變量分割(variable-partition)大小以提高效率（根據給定進程的需求大小）
* 空位(hole) - 可用記憶體區塊；各種大小的空位散佈在整個記憶體中
* 當一個進程到達時，它將從足夠容納它的空位中分配記憶體
* 進程退出後，釋放其分割，相鄰的空分割結合
* 作業系統維護關於：
1. 已分配的分割
2. 空分割（空位）的資訊

## Contiguous Memory Allocation
* 如果空位對於到達的進程而言過大，則將其分割為兩部分：一部分分配給到達的進程，另一部分返回到空位集合中。
* 當一個進程終止時，空位被放回空位集合中。
* 如果新的空位與其他空位相鄰，則合併形成一個更大的空位，並檢查它是否能滿足任何正在等待記憶體的進程。
## Dynamic Storage-Allocation Problem
* 如何從空閒孔清單中滿足大小為 n 的請求？
* 首適應法(first-fit)：分配第一個足夠大的空位
* 最佳適應法(Best-fit)：分配最小的足夠大的空位；除非按大小排序，否則必須搜索整個列表
* 產生最小的剩餘空位
* 最差適應法：分配最大的空位；同樣需要搜索整個列表
* 產生最大的剩餘空位
* 在速度和儲存利用率方面，首次適應和最佳適應優於最差適應

## Fragmentation
* 外部碎片化(External Fragmentation) - 當可用的記憶體空間被分割成小片段時，儘管總體記憶體空間存在以滿足請求，但它並不是連續的。
* 內部碎片化(Internal Fragmentaion) - 已分配的記憶體可能略大於請求的記憶體；這種大小差異是分割內部的記憶體，但未被使用。
* 首適應法分析顯示，對於給定的N個區塊已分配，另外的0.5N個區塊因外部碎片化而遺失。
* 1/3 可能無法使用 -> 50%規則
* 通過整理來減少外部碎片化
* 將記憶體內容重新排序，將所有可用的記憶體放在一個大區塊中
* 只有在重定位是動態的並且在執行時完成時才能進行整理
* I/O 問題
* 在進行 I/O 操作時將作業保留在記憶體中
* 只將 I/O 操作執行到作業系統緩衝區中
* 現在考慮到後端存儲也有相同的碎片化問題
---
# Paging
* 進程的物理地址空間可以是非連續的；只要有空閒的物理內存，就會為進程分配物理內存。
* 避免了外部碎片化的問題
* 避免了不同大小的記憶體塊的問題
* 將物理內存劃分為稱為框架的固定大小的區塊，稱為幀(frames)
* 大小是2的次方(2^n^)，介於512bytes(2^9^)和16Mbytes(2^24^)之間
* 將邏輯內存劃分為相同大小的區塊，稱為頁面(pages)
* 跟蹤所有的空閒框架
* 要運行大小為N頁的程序，需要找到N個空閒框架(free framges)並加載程序
* 設置一個頁表來將邏輯地址轉換為物理地址
* 備份存儲(backing store)同樣分成頁面
* **仍然存在內部碎片问题**
## Address Translation Scheme
* CPU 生成的地址分為：
* 頁號(page number)（p）- 用作索引進入頁表(page table)，該表包含物理內存中每個頁的基地址
* 頁偏移(page offset)（d）- 與基地址結合，定義發送到記憶體單元的物理內存地址
* Size of logical address space：2^m^
* Size of one page：2^n^
* the high-order m－ n bits: page number
* n low-order bits designate the page offset


## Paging Hardware

## Paging Model of Logical and Physical Memory

## Paging Example
* Logical address: n = 2 and m = 4. Using a page size of 4 bytes and a physical memory of 32 bytes (8 pages)

## Paging -- Calculating internal fragmentation
* Page size = 2,048 bytes
* Process size = 72,766 bytes
* 35 pages + 1,086 bytes
* Internal fragmentation of 2,048 - 1,086 = 962 bytes
* Worst case fragmentation = 1 frame – 1 byte
* On average fragmentation = 1 / 2 frame size
* Suggest small page sizes
* But each page table entry takes memory to track(但每個頁表條目都需要內存來跟踪)
* Suggest Large page sizes
* Page sizes growing over time(頁面大小隨著時間的推移而增長)
* Solaris supports two page sizes – 8 KB and 4 MB

## Free Frames

## Implementation of Page Table
* 頁表(page table)存放在主記憶體中
* 頁表基底暫存器（PTBR - Page table base register）指向頁表(page table)
* 頁表長度暫存器（PTLR - Page table length register）指示頁表的大小
* 在這個方案中，每次數據/指令訪問都需要兩次記憶體訪問
* 一次是為了頁表，一次是為了數據/指令
* 通過使用一種特殊的快速查找硬件緩存，稱為翻譯後援緩存（TLBs - translation look aside buffers）（也稱為聯想記憶體 - associative），可以解決兩次記憶體訪問的問題

## Translation Look-Aside Buffer(TLBS)
* 一些 TLBs 存儲每個 TLB 項目中的地址空間標識符（ASIDs - address space identifiers）- 這個標識符獨特地識別每個進程，以提供該進程的地址空間保護
* 否則需要在每次上下文切換時刷新
* TLB 通常很小（64 到 1,024 個enties）
* 在 TLB 沒有時，值會被加載到 TLB 中，以便下次更快地訪問
* 必須考慮替換策略
* 一些項目可以被固定下來，以永久快速訪問

## Hardware
* 關聯記憶 (TLB) – 當呈現一個項目時，它會同時與所有鍵進行比較
* 地址轉換（p，d）
* 如果在 TLB 中找到頁號，則其幀號立即可用並用於存取內存
* 如果頁號不在TLB中，則必須對頁表進行記憶體引用
* TLB隨後做更新動作，以供下次參考

## Paging Hardware With TLB

## TLB Example

## Effective Access Time
* 命中率(Hit ratio) - 頁號在 TLB 中找到的次數百分比
* 80% 的命中率意味著我們在 TLB 中找到所需的頁號的次數佔總訪問次數的 80%。
* 假設存取內存需要 10 納秒。
* 如果我們在 TLB 中找到所需的頁面，則映射內存訪問需要 10 納秒
* 否則，我們需要兩次內存訪問，所以是 20 納秒
* 有效存取時間（EAT - Effective Access Time）
* EAT = 0.80 x 10 + 0.20 x 20 = 12 納秒
* 這意味著存取時間減慢了 20%
* 考慮一個更現實的命中率為99%
* EAT = 0.99 x 10 + 0.01 x 20 = 10.1 納秒
* 這意味著存取時間僅減慢了 1%

## Memory Protection
* 透過將保護位元(protection bit)與每個幀(bit)相關聯來指示是否允許read-only或read-write access來實現記憶體保護(Memory Protection)
* 也可以添加更多bits以指示頁面僅執行(page execute-only)，等等
* 附加到page table中每個enties的有效-無效(Valid-invalid)位：
* "有效" 表示關聯的頁面位於進程的邏輯地址空間中，因此是一個合法的頁面
* "無效" 表示該頁面不在進程的邏輯地址空間中
* 或使用頁表長度寄存器（PTLR）
* 任何違反都會導致陷阱到核心

## Valid (v) or Invalid (i) Bit In A Page Table

## Shared Pages
* 共享代碼(Shared code)
* 在進程間共享一個read-only（可重入）代碼的一份拷貝（例如文本編輯器、編譯器、窗口系統）
* 類似於多個線程共享相同的進程空間
* 如果允許共享讀寫頁面，還可用於進程間通信
* 私有代碼和數據(Private code and data)
* 每個進程都保留代碼和數據的獨立拷貝
* 私有代碼和數據的頁面可以出現在邏輯地址空間的任何位置

## Shared Pages Example
---
# Structure of the Page Table
* 使用直接的方法，對於分頁的記憶體結構可能會變得非常龐大。
* 考慮一下現代計算機上的32位邏輯地址空間。
* 頁大小為4 KB（2^12^）
* 頁表將有100萬個enties（2^32^ / 2^12^）
* 如果每個entry是4bytes=>則每個進程僅用於頁表的物理地址空間就需要4MB
* 不希望在主記憶體中連續分配這麼大的空間
* 將頁表分成較小的單元是一個簡單的解決方案
* 階層式分頁(Hierarchical Paging)
* 哈希分頁表(Hashed Page Tables)
* 反向分頁表(Inverted Page Tables)

## Hierarchical Page Tables
* 將邏輯位址空間分解為多個頁表
* 一個簡單的技巧是兩級頁表(two-level page table)
* 然後我們將頁表分頁

## Two-Level Paging Example
* 一個邏輯地址（在具有1K頁大小的32位機器上）被分成
* 由20bits組成的頁號(page number)
* 由12bits組成的頁偏移(page offset)
* 由於頁表被分頁，頁號進一步分為：
* 10位頁號
* 12位頁偏移
* 因此，一個邏輯地址如下：
* 其中p1是外部頁表的索引，p2是內部頁表的頁內的位移
* 這種結構被稱為正向映射的頁表(forward-mapped page table)

## Address-Translation Scheme

## 64-bit Logical Address Space
* 即使是兩級分頁方案也不足夠
* 如果page size為4 KB（2^12^）
* 那麼page table將有2^52^個entries
* 如果是兩級方案，內部頁表可能有2^10^個4字節的項目
* 地址將如下所示
* 外部頁表有2^42^個enties或2^44^bytes(2^42^*2^2^)
* 一個解決方案是添加第二個外部頁表
* 但在下面的例子中，第二個外部頁表仍然大小為2^34^字節
* 可能需要4次記憶體訪問才能到達一個物理內存位置

## Three-level Paging Scheme

## Hashed Page Tables
* 在大於32bits的地址空間中常見
* 虛擬頁號被哈希到一個頁表中
* 這個頁表包含哈希到同一位置的一個元素鏈
* 每個元素包含
1. 虛擬頁號(virtual page number)
2. 映射頁框的值(the value of the mapped page frame)
3. 指向下一個元素的指針(a pointer to the next element)
* 虛擬頁號在這個鏈中進行比較，尋找匹配的頁面
* 如果找到匹配，則提取對應的physical frame
* 對於64位地址的變化是分組頁表
* 類似於哈希，但每個項目引用多個頁面（例如16pages）而不是1page
* 尤其適用於稀疏的地址空間（其中內存引用是非連續且分散的）

## Inverted Page Table
* 追蹤所有physical pages，而不是每個進程都有一個page table並追蹤所有可能的logical pages
* 每個實際內存頁有一個項目
* 項目包含存儲在該實際內存位置的頁的虛擬地址，以及擁有該頁的進程的信息
* 減少了存儲每個頁表所需的記憶體，但增加了在發生頁引用時搜索表所需的時間
* 使用哈希表來限制搜索到一個、或最多幾個的page-table entries
* TLB 可以加速訪問
* 但如何實現共享內存呢？
* 一個虛擬地址映射到共享的物理地址

## Inverted Page Table Architecture

## Oracle SPARC Solaris(skip)
* 考慮具有緊密整合硬體的現代 64 位元作業系統範例
* 目標是效率、低開銷
* 基於哈希，但更複雜
* 兩個哈希表
* 一個核心和一個用於所有用戶進程
* 每個將記憶體位址從虛擬記憶體映射到物理記憶體
* 每個條目代表映射虛擬記憶體的一個連續區域
* 比每個頁面使用單獨的哈希表條目更有效
* 每個條目都有基底位址和跨度（表示該條目代表的頁數）
* TLB 保存用於快速硬體查找的轉換表條目 (TTE)
* TTE 快取駐留在轉換儲存緩衝區 (TSB) 中
* 包括每個最近造訪的頁面的條目
* 虛擬地址引用引起TLB搜索
* 如果未命中，硬體將遍歷記憶體中的 TSB 尋找與該位址對應的 TTE
* 如果找到匹配，CPU 將 TSB 條目複製到 TLB 中並完成轉換
* 如果沒有找到匹配項，核心會中斷搜尋哈希表
* 然後核心從適當的雜湊表建立一個TTE並將其儲存在TSB中，中斷處理程序將控制權傳回給MMU，MMU完成位址轉換

## Swapping
* 一個進程可以被暫時地交換到後端存儲中，然後再被帶回到內存中繼續執行
* 進程的總物理內存空間可能超過物理內存
* 後端存儲(backing store) - 快速磁盤足夠大，可以容納所有用戶的所有內存映像的副本；必須直接訪問這些內存映像
* 滾出、滾入(Roll ou, roll in) - 用於基於優先級的調度算法的交換變體；低優先級的進程被交換出去，以便較高優先級的進程可以被加載和執行
* 交換時間的主要部分是傳輸時間(transfer time)；總傳輸時間與交換的內存量**成正比**
* 系統維護一個準備隊列，其中包含在磁盤上具有內存映像的準備運行的進程

* 換出的進程是否需要換回相同的實體位址？
* 取決於地址綁定方法
* 另外還要考慮進程記憶體空間的掛起 I/O
* 許多系統（即 UNIX、Linux 和 Windows）上都存在交換的修改版本
* 交換通常禁用
* 如果分配的記憶體量超過閾值(threshold)則啟動
* 一旦記憶體需求降低到閾值以下就再次停用

## Schematic View of Swapping

## Context Switch Time including Swapping
* 如果下一個要放到CPU上的進程不在記憶體中，則需要換出一個進程並換入目標進程
* 上下文切換時間可能會非常長
* 100MB 程序交換到硬碟，傳輸速率為 50MB/秒
* 換出時間為 2000 毫秒
* 加上相同大小進程的交換
* 上下文切換交換組件的總時間為 4000 毫秒（4 秒）
* 如果減少交換記憶體的大小，則可以減少 - 透過了解實際使用了多少內存
* 透過 `request_memory()` 和 `release_memory()` 通知作業系統記憶體使用情況的系統調用
* 交換的其他限制條件也存在
* 掛起的I/O(pending I/O) - 不能交換出去，因為I/O可能發生在錯誤的進程上
* 或者始終將I/O傳輸到核心空間，然後再傳輸到I/O設備
* 被稱為雙緩衝(double buffering)，增加了開銷(overhead)
* 標準的交換在現代操作系統中不再使用
* 但修改過的版本很常見
* 只有在**可用內存非常低**的情況下才進行交換
## Swapping on Mobile Systems
* 通常不支援的方法：
* 基於閃存的方法
* 空間較小
* 寫入週期有限
* 在移動平台上，閃存內存與 CPU 之間的吞吐量較低
* 如果內存不足，取而代之的是使用其他方法來釋放內存：
* iOS 要求應用程序自願放棄已分配的內存
* 如果需要，read-only data將被清除並重新從閃存中加載
* 如果未能釋放，可能導致終止
* Android 在內存不足時終止應用程序，但首先將應用程序狀態寫入閃存以快速重新啟動
* 這兩個操作系統都支持下面討論的分頁。

## Swapping with Paging

## Example: The Intel 32 and 64-bit Architectures
* 主導產業晶片
* Pentium CPU是32-bit的，稱為 IA-32 架構
* 目前的 Intel CPU是64-bit的，稱為 IA-64 架構
* 晶片有很多變化，這裡涵蓋了主要思想

## Example: The Intel IA-32 Architecture
* 支持分段和帶分頁的分段。
* 每個段可以是4 GB。
* 每個進程最多有16 K個segments。
* 分為兩個分區
* 最多有8K個segments的第一個分區是進程私有的（保存在本地描述符表（LDT-local descriptor table）中）。
* 最多有8K個segments的第二個分區在所有進程之間共享（保存在全局描述符表（GDT-global descriptor table）中）。
* CPU產生邏輯位址
* 給予分段單元的選擇器
* 產生線性位址
* 分配給分頁單元的線性位址
* 它在主記憶體中產生物理位址
* 分頁單元相當於 MMU
* 頁面大小可以是 4KB 或 4MB

## Logical to Physical Address Translation in IA-32

## Intel IA-32 Segmentation

## Intel IA-32 Paging Architecture

## Intel IA-32 Page Address Extensions
* 32位地址限制促使英特爾創建了頁地址擴展（PAE），允許32位應用程序訪問超過4GB的內存空間。
* 分頁採用了三級方案。
* 最上面的兩位比特指向一個頁目錄指針表(page directory pointer table)。
* page-directory和page-table的大小增加到64-bits。
* 淨效果是將地址空間增加到36bits - 64GB的物理內存。

## Intel x86-64
* 目前一代 Intel x86 架構
* 64位地址空間非常巨大（大於16exabytes）
* 但實際上只實現了48位的地址空間
* 頁大小為4KB、2MB、1GB
* 具有四級分頁層次結構
* 也可以使用PAE（頁地址擴展），因此虛擬地址為48位，物理地址為52位。

## Example: ARM Architecture
* 主要的移動平台芯片（例如蘋果iOS和谷歌Android設備）
* 現代、節能的32位CPU
* 有4 KB和16 KB的頁面
* 有1 MB和16 MB的頁面（稱為部分）
* 對於部分使用單級分頁，對於較小的頁面使用雙級分頁
* 兩級TLB
* 外部級別有兩個微型TLB（一個用於數據，一個用於指令）
* 內部是單一的主TLB
* 首先檢查內部TLB，如果未命中，則檢查外部TLB；如果外部TLB也未命中，CPU執行頁表遍歷

# important sentance
1. to check the range of the address in kernel mode.
2. .com => will be placed in the main memory at the same place all the time