# OS Chapter 9: Memory- Management Strategies

- 程式必須（從磁碟）放入記憶體並放置在process中才能運行
- main memory & registers 只被cpu進行存儲
- 在cpu時脈或更少存去register
- 更多週期存取main memory，可能會導致停頓
- Cache 在main memory 和cpu 之間
- base & limit register定義logic memory address
- CPU需要檢查user mode下的記憶體訪問，確保在base和limit之間
## Binding
- 程式必須被帶入memory並放置於process行成input queue
- 指令和資料到記憶體位址的位址binding可以發生在三個不同的階段
- 編譯時間
- 載入時間
- 執行時間
- compile time:
- 如果已知記憶體位址，則可以產生絕對代碼
- 如果起始位置更改，則必須重新編譯
- Load time:
- 如果編譯時記憶體位置未知，則必須產生可重定位程式碼(relocatable code)
- 不必要的模組重新鏈接，浪費時間和內存空間
- Execution time:
- 如果進程在執行期間可以從一個記憶體段移動到另一個記憶體段，則binding會延遲到執行時間。
- 需要位址對映的硬體支援（例如base&limit register）
## Logical vs. Physical Address Space
- 綁定到單獨physic address space的logic address space的概念是正確記憶體管理的核心
- logic address是由cpu產生，也稱為virual address
- physical address，記憶體單元看到的位址
- 編譯與載入的address binding方案
- logic address = physical address
- 執行時address binding方案
- logic address(virual address)和physical address不同
## Memory mapping / binding
考慮全域變數的記憶體分配

do 10 times
print(x)
x := x+7

原始碼時先給予x記憶體位址，編譯時對應到給予的記憶體位址，載入的時候根據當時的內存狀況決定從哪個位置開始，之後再執行的時候先從記憶體位址拿出來之後加7再放回該記憶體位址
## Memory-Management Unit (MMU)
運行時將虛擬記憶體對應到實體記憶體的硬體設備
使用者處理的事邏輯位址，不會知道實體位址，透過MMU映射
- 當引用記憶體位址時引發執行時綁定
- 邏輯位址只綁定到實體位址

	1.	Logical Address Space（邏輯地址空間）：
	•	也稱為虛擬地址空間，是由程序生成的地址，通常是由操作系統或編譯器分配給進程的。
	•	邏輯地址是進程在運行時使用的地址，進程無法直接接觸到物理內存，而是通過操作系統的內存管理單元（MMU）進行映射。
	•	邏輯地址在不同的進程中是獨立的，即每個進程都有自己獨立的邏輯地址空間。
	•	這些地址在內存管理中是虛擬的，並且可以在程序運行時被動態地重新分配和重定位。
	2.	Physical Address Space（物理地址空間）：
	•	物理地址空間是指計算機的實際內存地址，即處理器直接訪問的內存。
	•	這些地址是硬體層級的，對操作系統和進程來說是透明的。
	•	物理地址是指內存芯片中的實際位置，並不會受到程序的影響，因此物理地址空間是固定的。

主要區別：

	•	邏輯地址是進程在運行時生成的，並且是虛擬的，通常由操作系統進行映射到物理地址。
	•	物理地址是真正存在於計算機硬體中的地址，對所有進程來說是共享的。

映射過程：

操作系統使用一個叫做 頁表（Page Table） 的結構來將邏輯地址映射到物理地址。當進程需要訪問某個邏輯地址時，MMU（內存管理單元）會查找相應的頁表，將邏輯地址轉換成物理地址，並訪問對應的內存位置。

優點：

	•	邏輯地址空間允許多個進程使用相同的地址範圍而不會互相干擾，提高了內存的隔離和安全性。
	•	操作系統可以實現內存重定位、虛擬內存等技術，增加了內存管理的靈活性。

簡單來說，邏輯地址是進程使用的虛擬地址，而物理地址是內存中的實際地址，操作系統通過內存管理單元（MMU）將兩者進行映射。

## Dynamic relocation using a relocation register
使用重定位暫存器進行動態重定位

- 動態載入：例程在被呼叫前不會載入
- 更好的記憶體利用率：從未載入位使用的例程
- 所有例程均以重定位載入格式儲存在磁碟上
- 當需要大量程式碼來處理不經常發生的時候很管用
- 不需要作業系統的特殊支持
- 透過程式設計實施
## Dynamic Linking
- 靜態連結
- 系統程式庫和程式碼由載入器組合成二進位程式映像
- 動態連結
- 連結延後到執行時間
- Stub
- 小段程式碼
- 定位適當的記憶體函式庫例程
- 將其自身定位到其例程的位址，並執行該例程

- 作業系統檢查例程是否在process的記憶體位址中
- 如果不在address space中(不會先全部都載入到logic address space)，則新增至logic address space
- 共享庫
- 動態連結對於函式庫特別有用

頁面錯誤（Page Fault）詳解：

	1.	頁面錯誤的原因：
	•	當進程試圖訪問一個邏輯地址時，內存管理單元（MMU）會檢查該邏輯地址是否已經對應到物理內存中的頁。
	•	如果該邏輯地址沒有找到對應的物理頁（例如，該頁還未被載入內存，或者在交換區中），就會發生頁面錯誤。
	2.	頁面錯誤處理：
	•	當發生頁面錯誤時，控制權會暫時交給操作系統。
	•	操作系統會檢查該邏輯地址是否屬於進程的有效地址空間（例如，確保進程確實有權訪問這個地址）。
	•	如果該地址是合法的但尚未載入，操作系統會將對應的頁從磁碟或交換區（swap space）載入到內存中。
	•	如果該頁不在交換區而是首次訪問，則操作系統會從程序的可執行文件中載入相應的頁。
	•	載入頁面後，操作系統會更新頁表，讓邏輯地址映射到新的物理地址，並恢復進程的執行。
	3.	頁面錯誤的作用：
	•	頁面錯誤是一種正常的內存管理機制，用於實現虛擬內存的按需加載(Demand Paging)。通過延遲頁面加載，頁面錯誤可以提高內存利用效率，避免將不必要的頁載入內存。
	•	不過，如果頁面錯誤頻繁發生，會造成進程頻繁等待頁面載入，導致性能下降，這種現象稱為 抖動（Thrashing）。

總結

當邏輯地址找不到相應的物理頁時，會發生頁面錯誤。操作系統會根據情況將所需頁面載入到內存，更新映射並恢復進程執行。頁面錯誤是虛擬內存管理中的重要機制。

## Swapping
- process可以暫時從memory切換到後備儲存中，等到需要時再返回記憶體繼續執行。
- 後備儲存
- 足夠大的快速磁碟，可容納所有內容的副本
- 必須提供對這些記憶體映像的直接存取
- 系統維護一個準備運行一個有後備儲存與記憶體的記憶體映像的就緒佇列
- Roll in , Roll out
- 用於基於優先順序的調度交換變體演算法
- 較低優先權的進程被換出，以便可以載入和執行較高優先權的進程
- 交換時間的主要部分是傳輸時間
- 總傳輸時間與交換的內存量成正比
- 這部分可能會有I/O中斷
## Context Switch Time including Swapping
- 如果下一個要放到CPU的process不在記憶體中，則需要換出一個process並把目標process放入記憶體中
- context switch 時間可能會很長
- 如果減少交換記憶體大小，可以減少時間，所以可以計算實際需要用的內存
- 交換的其他限制
- 掛起的IO無法換出，因為會發生錯誤process
- 或是總是傳輸到IO kernel，然後再到IO device，稱為雙緩衝，增加了開銷
- 現代作業系統中未使用標準交換
- 但修改版本常見
- 僅當可用記憶體極低時才進行交換
## Swapping on Mobile Systems
- 通常不支持
- 基於快閃記憶體(Flash memory)
- 空間較小
- 有限的寫入週期數
- mobile platform上的快閃記憶體和CPU之間的吞吐量較差
- 如果記憶體不足，請使用其他方法來釋放記憶體
- IOS要求應用程式自願放棄分配的內存
- Read-only資料被丟棄，並在需要時從閃存重新加載
- 未能釋放可能會導致終止
- 如果可用記憶體不足，Android 將終止應用程序，但首先將應用程式狀態寫入閃存以便快速重啟
- 兩種作業系統都支援分頁
## Contiguous Allocation
- Main memory通常分為兩個partitions：
- 常駐作業系統(OS)，通常透過中斷向量保存在低記憶體中
- 然後User processes保存在high memory中（以與操作系統內核分開，確保內存保護）
- 每個process包含在單一連續的記憶體中(single contiguous section of memory)
- 重定位暫存器(Relocation register)用於保護使用者進程避免受彼此影響以及作業系統程式碼和資料的更改
- 基址暫存器(Base register)包含最小物理位址(physical address)的值
- 限制暫存器(Limit register)包含邏輯位址範圍
- 每個邏輯位址必須小於限制暫存器
- MMU動態對應邏輯位址
- 然後可以允許諸如內核程式碼瞬態(transient)和核心更改大小之類的操作

> Base Register：負責地址轉換，確定程序的物理內存起始位置。
Limit Register：負責內存保護，確保程序訪問的內存範圍合法。
>這張圖可以看到logical address主要是由CPU生成，然後要轉成記憶體的物理地址必須先看看有沒有超過limit register範圍（保護），如果超過的話是addressing error，如果沒超過則透過relocation register重定位(relocation)，轉為物理地址
- 多區分配(Multiple-partition allocation)
- 可變分區(Variable-partition)大小以提高效率（大小適合給定process的需求）
- Hole-可用記憶體區塊
- 記憶體中散佈者各種大小的Hole
- 當process到達時，會從足夠大的hole中為其分配記憶體
- 進程退出時會釋放其分區，相鄰的空間分區合併
- 作業系統維護分配的分區和空閒分區(hole)
- 當發出記憶體請求時，作業系搜尋所有空閒區塊(即hole)以找到合適的區塊
- 如果hole大於要求的尺寸，則將其分成兩半
- 所請求的大小之一被提供給process，剩餘大小的成為一個新的hole
- 當一個process傳回一個記憶體區塊時，他就變成一個hole，必須與其鄰居合併
- First-fit（首次適配）
- 分配第一個夠大的hole
- 搜尋時間長：記憶體前面有很多小洞
- 簡單快速，但可能產生很多外部碎片(External Fragmentation)
- 變體(Variant)：下一個適合(Next-fit)
- 從分配區塊之後的下一個區塊開始搜索
- Best-fit
- 分配足夠大的最小hole
- 必須搜尋整個列表，除非按大小排序
- 產生最小的剩餘hole
- 減少內存浪費，但增加搜尋時間
- Worst-fit
- 分配最大的hole
- 還必須搜尋整個列表
- 產生最大的剩餘hole
- 目的是保留最大的空閒分區以便後續使用
- 在速度和儲存利用率方面，First-fit和best-fit優於worst-fit
## Fragmentation
- Process從記憶體中載入和刪除，最終記憶體被切成最小hole，這些小hole不足以運行任何傳入的process
- External Fragmentation（外部碎片）
- 當內存中的空閒區域總量足夠，但這些空閒區域分布得很零散，無法連續地滿足新進程的需求時，形成 外部碎片。
- 雖然內存總量夠用，但無法找到一個足夠大的連續空間來分配。
- 例如：
- 動態分區（Dynamic Partitioning）：進程分配和釋放內存後，內存空閒區變得不連續。
- 分段系統（Segmentation）：段的大小多樣，導致內存分布不均勻。
- Internal Fragmentation（內部碎片）
- 當分配給進程的內存大小大於進程實際需要的內存時，未使用的那部分內存就形成了 內部碎片。
- 這些未使用的內存雖然在進程的分區內，但無法被其他進程使用
- 例如：
- 固定分區（Fixed Partitioning）：內存劃分為大小固定的區域，進程無法剛好填滿分區。
- 分頁系統（Paging）：最後一個頁框中的未使用空間。

>內部碎片 是因為內存分配不精確，進程無法完全利用分區內存。
外部碎片 是因為內存釋放後變得零散，無法有效利用空閒空間。

- 減少外部碎片
- 透過壓縮(compaction)
- 通過將分散的空閒內存區合併，形成連續的大空間。
- 但需要移動內存內容，開銷較高。
- 透過頁記憶體管理(page memory management)
- 分頁系統避免了外部碎片，因為進程可以不要求連續的物理內存。
- 分段系統通過靈活分配段，降低碎片問題。
- 減少內部碎片
- 動態分區（Dynamic Partitioning）
- 根據進程需求動態分配內存，減少浪費。
- 分頁系統（Paging）
- 使用固定大小的頁框，簡化管理，雖然仍可能有頁框級別的內部碎片，但影響較小。
## Compaction
- 打亂記憶體內容，將分散的空閑內存區合併程一個大區塊
- 缺點：
- 僅當重定位是動態的，且在執行時完成時才可能
- 很難決定最佳壓縮(Compaction)策略
## Segmentation
- 支援使用者記憶體視圖的記憶體管理方案
- 程式是segments的集合
- 系統有更多的自由來管理記憶體
- 程式設計師有更自然的程式設計環境
- 邏輯位址由二元組組成：<segment-number, offset>
- Segement table映射二維物理地址
- 每個表格條目有：
- base：包含segment在記憶體中駐留的起始實體位址
- limit：指定segment的長度
- Segement-table base register(STBR)指向segment table在記憶體中的位址
- Segment-table length register(STLR)指示程式所使用的segments數
- 如果s<STLR，則segment number是合法的
- 保護
- 與segment table中的每個項目關聯
- validation bit = 0 ，非法segment
- read/write/execute 權限
- 與segments相關的保護位(Protection bits)
- 程式碼共享發生在segment level
- 由於segements的長度不同，記憶體分配是一個動態儲存分配問題
- 優點
- 無內部碎片
- 支援記憶體共享和保護
- 缺點
- 外部碎片
- 額外的硬體支持
- 後備儲存中存在相同的碎片問題
- 壓縮速度慢很多，因此不可能
## Paging
- 將整個物理記憶體(physical memory)分割為「固定大小」的區塊，稱為frames
- 大小是2的冪，介於512bytes和8192bytes
- 將邏輯記憶體分為相同大小的區塊（稱為pages）
- Page size = frame size
- 追蹤所有空閒的frames
- 非連續分配
- 要執行n頁大小的程序，需要找到n free frame並載入程序

- 設定page table以將邏輯位址轉為實體位址
- CPU產生的虛擬位址(virtual address)分為
- Page number(p) - 用作page table的索引，page table包含實體記憶體中的每個base address
- Page offset(d) - 與base address結合定義傳送至記憶體單元的實體記憶體位址
- 對於給定的邏輯位址空間2^m和page size 2^n
- MMU中邏輯位址到物理位址的轉換
- CPU計算邏輯位址
- 邏輯位址被提取為
- p:商
- q:餘數
- 使用p檢查page table並擷取對應frame f 的起始位址或編號
- 起始位址 = frame數乘以page的大小
- 實體位址 = f的起始位址 + d
>可以看到有四個新的process要執行，有五個空閒的frame，After allocation那邊的new-process page table用來映射
- Page(frame)大小由硬體定義
- 通常為2的冪
- 範圍從512bytes到16MB/page
- 內部碎片？
- 更大的頁面->更多的空間浪費
- 但頁面大小隨時間的推移而增長
- 記憶體、process、資料集變的更大
- 更好的I/O效能(during page fault)
- page table更小
優點：
- 無外部碎片
- 因為位使用的page frames可以被其他process使用
- 支援記憶體共享和保護
缺點：
- 內部碎片
- 由於位址空間被劃分為大小相等的page，因此除了最後一個page之外所有的page都將完全填滿
- 因此，最後一個page可能有內部碎片，並且可能已滿50%
## Implementation of Page Table
- 如果Page數較少，Page table可以儲存在特殊暫存器中
- Page table保存於主記憶體中
- Page-table base register(PTBR)指向page table
- Page-table length register(PTLR)指示page table的大小
- 減少context-switch time
- 每次資料/指令存取需要兩次記憶體存取
- 一次用於page talbe，一次用於資料/指令
- 稱為associative memory或translation look-aside buffers(TLBs)的快速查找硬體快取
- TLB儲存最近使用的pairs（page#,frame#)
- 它將輸入page#和儲存的進行比對
- 如果找到匹配，則輸出相應的frame #
- 不需要page table存取
- Address translation(p,d)
- 如果p在associative register , 取得frame # 輸出
- 否則從記憶體page table中獲取frame #
- 帶有TLB的paging硬體
- TLB查找是指令pipeline的一部分
- 不增加效能損失
- TLB 更換
- 最近最少使用(LRU)
- Address-space identifiers(ASIDs)
- 多個行程(multiple processes)
>圖的意思是，邏輯地址有p(page number)和d（偏移量)，page nubmer先去看看TLB有沒有對應的frame number，如果沒有則查page table，之後實體位址為(f*page size) + d
- Associative查找需要𝜀時間單位
- 假設記憶體週期時間為1 microsecond
- 命中率
- 在associative registers中找到page number的次數百分比
- 與associative registers數量相關得比率
- 命中率= 𝛼
- Effective Access Time(EAT) = (1 + 𝜀)𝛼 + (2 + 𝜀)(1 - 𝛼) = 2 + 𝜀 - 𝛼
- EAT = (1 - p)XMemory Access Time + pX(Page Fault Service Time)
## Memory Protection
- 透過將protection bit 與每個frame相關聯來實現記憶體保護
- page table每個entry附加valid-invalid
- valid
- 表示關聯的page table在進程的邏輯位址空間中，因此是合法的page
- invalid
- 表示該page不在process的邏輯位址中
- 每種存取提供單獨的protection bits
- Read-write , read-only , execute-only
- Page-table length register(PTLR)
- 驗證process的valid範圍
## Shared Pages
- 共享程式碼
- 在process之間共用一份read-only(reentrant)程式碼副本
- 文字編輯器、編譯器、視窗系統
- 標準C函式庫：libc
- 它在執行過程中永遠不會改變：唯獨
- 共享程式碼必須出現在所有程序的邏輯位址空間中的相同位址
- Private code and data
- 每個程序保留程式碼和資料的單獨副本
- private code和資料的page table可以出現在邏輯位址空間的任何位置
>圖中表示共享程式碼必須出現在所有程序的邏輯位址空間中的相同位址
## Struture of the Page Table
- 使用直接的方法，用於分頁的記憶體結構可能變的巨大
- 考慮現代電腦上的32-bit邏輯位址空間
- page size為4KB(2^12)
- page table將有一百萬筆(2^32 /2^12)
- 如果每個條目是4bytes->記憶體為4MB/單獨page table的實體位址空間
- 過去的記憶體量花費很大
- 不想在主記憶體中連續分配
- 分層分頁(Hierarchical Paging)
- 哈希頁表(Hashed Page Tables)
- 倒排頁表(Inverted Page Tables)
## Hierarchical Page Tables
- 將邏輯位址空間分解為多個page table
- 由於邏輯追很大，page table也很大，很難找到連續的記憶體來放置page table
- 一個簡單的技巧就是two-level page table
- 邏輯位址(在4K page size的32-bit機器上)分為：
- 由20bits組成的page number
- 由12bits組成的page offset
- 由於page table是分頁的，所以page number又分為：
- 12-bit page number
- 10-bit page offset
- 因此，邏輯位址如下
- 其中p1是outer page table(外頁表)的索引，p2是外頁表頁內的位移
- 稱為forward-mapped page table（前向映射頁表）
## 64-bit Logical Address Space
- 即使two-level paging 方案也不夠
- 若page size為4KB(2^12)
- 那麽有page table 有2^52 個entires
- 如果是two level方案，內部table可以是2^10 4-byte entries
- 位址看起來像
- 外層page table有2^42 entries 或2^44bytes
- 一個解決方案是新增2^nd個外層頁表
- 但在下面的範例中，2^nd個外層頁表大小仍然是2^34bytes
- 可能需要四次記憶體存取才能達到一個實體記憶體位置
## Three-level Paging Scheme
## Hashed Page Table
- 常見於 >32bits的address spaces中
- virtual page number 被hashed到page table中
- 此page table包含散裂到相同位置的元素鏈
- 在此鏈中比較virtual page number以搜尋符合項
- 如果找到匹配，則提取相應的physical frame
- 64-by addresses的變體是clustered page tables
- 與hashed類似，但每個entry引用多個pages，而不是1個
- 對於稀疏位址空間（其中記憶體引用不連續且分散）特別有用

## Inverted Page Table
- 每個實際記憶體page一個entry
- entry有儲存在該十記憶體位置中的page table的virtual address以及有關擁有該頁面的process的資訊組成
- 減少儲存每個page table所需的內存，但會增加發生page引用時搜尋表所需的時間
- 使用哈希表將搜尋時間限制為一格獲最多幾個page table entires
- 每有記憶體共享

1. Inverted Page Table (反向頁表)

概念

	•	反向頁表不是按進程維護的邏輯地址對應物理地址的表，而是按物理內存中的每一個頁框維護一條記錄。
	•	每一條記錄存儲：
	•	對應的進程 ID
	•	邏輯頁號
	•	其他元數據（如有效位）
	•	在這種結構中，每個頁框對應一條記錄，因此頁表的大小僅依賴於物理內存的大小，而與邏輯地址空間無關。

優點

	1.	節省內存：
	•	傳統頁表大小與邏輯地址空間大小有關，而反向頁表的大小只與物理內存的大小有關，對於大虛擬地址空間的進程（如 64 位系統）尤其有效。
	2.	簡化頁表管理：
	•	不需要為每個進程維護獨立的頁表，整個系統只需要一張全局的反向頁表。

缺點

	1.	查找速度慢：
	•	為找到特定的邏輯地址，需要遍歷反向頁表，效率低下。
	•	需要輔助數據結構（如哈希表）來加速查找。

2. Hashed Page Table (哈希頁表)

概念

	•	哈希頁表使用哈希函數來快速定位邏輯地址到物理地址的映射。
	•	哈希頁表中的每個條目通常存儲：
	•	邏輯頁號
	•	物理頁框號
	•	鏈接指針（用於處理哈希碰撞）
	•	使用邏輯頁號通過哈希函數計算出哈希值，然後快速查找對應的條目。

優點

	1.	查找速度快：
	•	通過哈希函數，可以快速找到邏輯地址對應的物理地址，大幅降低查找的時間複雜度。
	2.	適合大地址空間：
	•	哈希頁表可以處理大地址空間，而不需要像傳統頁表一樣耗費大量內存。

缺點

	1.	哈希碰撞：
	•	當多個邏輯頁號被映射到同一哈希桶時，需要額外的機制（如鏈表）來處理碰撞，這可能會影響性能。
	2.	內存開銷：
	•	虽然比傳統頁表節省內存，但需要存儲額外的哈希結構，內存占用比反向頁表略高。