第三章 記憶體管理：虛擬記憶體

學習目標 各種記憶體配置法：分頁、需求分頁、分段以及分段 / 需求分頁記憶體配置法。 分頁配置法對虛擬記憶體的影響。 比較三種分頁置換的差異：先進先出、最近最少使用及時鐘法。 分頁的機制，以及記憶體配置策略如何判斷應置換出去的分頁。 工作集的概念，以及如何將工作集應用於記憶體配置。 快取記憶體如何提升系統的反應時間。 第3章 記憶體管理：虛擬記憶體 第55頁

簡介 隨著虛擬記憶體的演進，新的配置法可以 記憶體配置法 除去程式必須儲存於連續空間的限制 除去程式在執行過程中必須完整保存在記憶體內的限制 分頁（Page） 需求分頁（Demand Paging） 分段（Segmentation） 分段/需求分頁（Segmented / Demand Paged MemoryAllocation） 第3章 記憶體管理：虛擬記憶體 第56頁

分頁記憶體配置 主要概念 非連續儲存方式 內部碎塊 分頁（Page）：將工作切割成許多固定大小的單位 頁框（Page Frame）：記憶體內與分頁大小相同的區段 磁區（Sector）：磁碟內與分頁大小相同的區塊 非連續儲存方式 每一個分頁儲存於一個頁框內，而這些頁框可以分散在記憶體內任何一個地方，如此可提升記憶體的使用率 無需進行記憶體密合，也不會產生外部碎塊 內部碎塊 最後一個頁框總是會填不滿，分頁架構還是會有內部碎塊的問題。 第3章 記憶體管理：虛擬記憶體 第56~57頁

圖3.1：大小超過一個分頁的程式，被切割成許多個分頁 第3章 記憶體管理：虛擬記憶體 第57頁

分頁記憶體配置 工作表 (Job Table, JT) 分頁對照表 (Page Map Table, PMT) 記憶體對照表 (Memory Map Table, MMT) 位址解析 (Address Resolution) 將工作的邏輯位址轉換成實體位址 第3章 記憶體管理：虛擬記憶體 第57.62頁

表3.1 ：工作表 工作表 工作大小 PMT位置 400 3096 200 3100 700 500 3150 (a) (b) (c) 初始狀態，存在三件進行中的工作 第二件工作結束後，空出紀錄項目 載入下一件工作，重新使用第二列的紀錄項目 第3章 記憶體管理：虛擬記憶體 第58頁

圖3.2 ： Job 1的大小為350位元組，切割成4個分頁，分頁大小為100個位元組。 第3章 記憶體管理：虛擬記憶體 第59頁

表3.2 ：圖3.1之中Job 1的分頁對照表 工作的分頁編號 頁框編號 8 1 10 2 5 3 11 8 1 10 2 5 3 11 第3章 記憶體管理：虛擬記憶體 第60頁

圖3.3 ： Job 1的分頁對照表 第3章 記憶體管理：虛擬記憶體 第61頁

分頁記憶體配置 優點 缺點 分頁架構成功的關鍵在於分頁大小 允許工作可以載入到非連續的記憶體位置 可更有效率的使用記憶體 額外的管理工作 內部記憶體碎塊 分頁架構成功的關鍵在於分頁大小 分頁愈小則PMT 愈大 分頁愈大則內部碎塊愈大 第3章 記憶體管理：虛擬記憶體 第62頁

需求分頁（Demand Paging） 執行程式時，不一定要把整支程式全部載入主記憶體 程式會被切割成許多大小相同的分頁、且儲存在輔助儲存體 利用程式結構的特性來提升記憶體的使用率 程式不可能同時使用全部的模組，有些模組始終不會被使用到 促成虛擬記憶體技術的發展 讓使用者用比較少的記憶體執行比較大的程式 需求分頁的成功關鍵在於使用高速直接存取儲存裝置 第3章 記憶體管理：虛擬記憶體 第62-63頁

圖3.4 ： 作業系統只須載入被打開的選單模組，其他的選單的模組不必載入主記憶體 第3章 記憶體管理：虛擬記憶體 第63頁

需求分頁（Demand Paging） 在主記憶體與輔助儲存體之間傳遞分頁的過程稱為置換。 置換存在著許多重要決策，系統必須事先制定 何時載入分頁？ 如何為新載入的分頁配置頁框？ 當記憶體空間全部被占滿時，如何騰出一個空間來容納新載入的分頁？ 被犧牲掉的舊分頁應當如何處置？ 第3章 記憶體管理：虛擬記憶體 第63~64頁

圖3.5 ：需求分頁的分頁對照表，記錄每一個分頁的狀態 第3章 記憶體管理：虛擬記憶體 第64頁

硬體指令處理演算法 1. 開始處理指令 2. 產生資料位址 3. 計算分頁編號 4. If 分頁已在記憶體中 Then 取得資料並完成指令 前進到下一個指令 返回至步驟1 Else 產生分頁插斷 呼叫分頁錯誤處理常式 DONE (課本請見附錄A) 第3章 記憶體管理：虛擬記憶體

需求分頁（Demand Paging） 分頁錯誤（Page Fault） 分頁錯誤處理常式 (Page Fault Handler) 所需分頁不在記憶體內 分頁錯誤處理常式 (Page Fault Handler) 作業系統模組中負責處理分頁錯誤的軟體 擺盪現象（Thrashing） 記憶體和磁碟之間發生過多分頁置換(Page Swapping)時，系統效能將會降低 第3章 記憶體管理：虛擬記憶體 第65頁

圖3.6 ：擺盪現象的例子 第3章 記憶體管理：虛擬記憶體 第66頁

分頁取代策略與概念 1 If 沒有可用頁框 Then 利用分頁移除演算法，選擇可被置換出去的分頁 更新工作的Page Map Table If 分頁的內容有更改 將該分頁寫回磁碟 2 以硬體指令處理演算法中步驟3 得到的分頁編號，取得要 求分頁儲存於磁碟中的位址 (檔案管理器使用此分頁編號取得磁碟位址) (課本請見附錄A) 第3章 記憶體管理：虛擬記憶體

分頁取代策略與概念 3 將該分頁讀入記憶體 4 更新該工作的Page Map Table 5 更新Memory Map Table 6 重新執行被插斷的指令 DONE (課本請見附錄A) 第3章 記憶體管理：虛擬記憶體

圖3.7 ： FIFO策略 第3章 記憶體管理：虛擬記憶體 第67頁

圖3.8 ： FIFO範例 第3章 記憶體管理：虛擬記憶體 第68頁

圖3.9 ： LRU分頁取代 第3章 記憶體管理：虛擬記憶體 第69頁

圖3.10 ：時鐘法(二次機會法) 第3章 記憶體管理：虛擬記憶體 第70頁

圖3.11 ：每一個時間週期更新參照位元組的過程 第3章 記憶體管理：虛擬記憶體 第71頁

分頁機制 PMT 中的三個特殊位元 狀態位元（Status Bit） 參照位元（Referenced Bit） 修改位元（Modified Bit） 第3章 記憶體管理：虛擬記憶體 第72頁

表3.3 ： 圖3.5之中Job 1的分頁對照表 1 5 9 2 7 3 12 分頁 狀態位元 修改位元 參照位元 頁框 1 5 9 2 7 3 12 第3章 記憶體管理：虛擬記憶體 第72頁

表3.4 ： 分頁對照表內各個位元的意義 狀態位元 修改位元 參照位元 值 意義 不在記憶體內 未曾修改 未曾調用 1 在記憶體內 經過修改 不在記憶體內 未曾修改 未曾調用 1 在記憶體內 經過修改 經過調用 第3章 記憶體管理：虛擬記憶體 第72頁

表3.5 ： 修改位元和參照位元組合的四種可能狀況與意義 意　義 狀況1 未曾修改，也未曾調用 狀況2 1 未曾修改，但曾經調用 狀況3 經過修改，但未經調用(不可能？) 狀況4 經過修改，也曾經調用 第3章 記憶體管理：虛擬記憶體 第73頁

工作集（Working Set） 工作集是由程式最常調用的分頁所組成。 把工作集裡的分頁保留在主記憶體內，這支程式就不會發生分頁錯誤。 工作集會隨著工作在系統中的狀態而變更。 參照區域性（Locality of Reference） 程式執行的過程可分成幾個階段，每一階段都會集中使用少數幾段程式 副程式、陣列、堆疊等，都具有參照區域性 第3章 記憶體管理：虛擬記憶體 第73~74頁

圖3.12：Windows 作業系統的「資源監視器」 第3章 記憶體管理：虛擬記憶體 第74頁

圖3.13：為一支程式處理分頁錯誤花費的時間 第3章 記憶體管理：虛擬記憶體 第75頁

分段記憶體配置 分段（Segmentation） 區段對照表 (Segment Map Table, SMT) 從程式邏輯出發，每一個區段的大小不一 分頁則不考慮程式邏輯 每一個區段內含性質相近的程式碼或資料 主記憶體沒有頁框，所以必須採用動態切割 分頁則是以固定大小進行切割 區段對照表 (Segment Map Table, SMT) 記錄各區段的記憶體配置狀況 第3章 記憶體管理：虛擬記憶體 第76~77頁

圖3.14 ： 分段記憶體配置範例 第3章 記憶體管理：虛擬記憶體 第77頁

圖3.15 ： Job 1的區段對照表 第3章 記憶體管理：虛擬記憶體 第78頁

圖3.16 ： 執行期間主程式呼叫副程式A，藉由SMT計算副程式A在主記憶體中的位址 第3章 記憶體管理：虛擬記憶體 第79頁

程式先以其邏輯架構切割成許多區段，然後再將這些區段切割成固定大小的分頁 分段/需求分頁記憶體配置 分段/需求分頁記憶體配置（Segmented/Demand Paged memory Allocation）架構，乃是分段記憶體配置與需求分頁兩者的合體 程式先以其邏輯架構切割成許多區段，然後再將這些區段切割成固定大小的分頁 第3章 記憶體管理：虛擬記憶體 第79頁

圖3.17 ： 分段 / 需求分頁記憶體配置架構 第3章 記憶體管理：虛擬記憶體 第80頁

分段/需求分頁記憶體配置 分段 / 需求分頁記憶體配置架構缺點 關聯記憶體 (Associative Memory) 管理資料表的額外負擔以及參照這些表格所花的時間 關聯記憶體 (Associative Memory) 由一組高速的關聯暫存器（Associative Register）組成 可快速的執行查表工作 可以在一個指令週期內，將輸入的分頁編號或區段編號，轉換成相對應的實體記憶體位址 第3章 記憶體管理：虛擬記憶體 第81頁

圖3.18 第3章 記憶體管理：虛擬記憶體 第81頁

虛擬記憶體（Virtual Memory） 虛擬記憶體的可行在於 分頁可在主記憶體和輔助儲存裝置之間自由置換 執行程式的大小不受限制 虛擬記憶體架構下 每個程式只有一小部分儲存於記憶體內 在必要的時候將記憶體分頁儲存到輔助儲存裝置 讓記憶體空間的管理更具彈性 可用高速的磁碟裝置達成此一目標 第3章 記憶體管理：虛擬記憶體 第82頁

表3.6 ： 比較虛擬記憶體的兩種實作方式 以分頁實作虛擬記憶體 以分段實作虛擬記憶體 頁框裡有內部碎塊 沒有內部碎塊 沒有外部碎塊 程式切割成固定大小的分頁 程式依邏輯結構，切割成大小不一的區段 以分頁編號與位移值，計算實體記憶體位址 以區段編號與位移值，計算實體記憶體位址 需要PMT 需要SMT 第3章 記憶體管理：虛擬記憶體 第83頁

虛擬記憶體 優點 程式的大小不受主記憶體容量的限制。 提升記憶體使用效率，記憶體內只存放立即需要的程式片段。 可以同時執行更多程式，或者讓更多使用者同時上線。 讓程式碼和資料得以在使用者之間共用。 程式區段可以動態連結。 第3章 記憶體管理：虛擬記憶體 第83頁

虛擬記憶體 缺點 增加處理器的硬體成本。 處理分頁錯誤的工作增加系統額外的管理負擔。 系統必須提高複雜度，以避免擺盪發生。 第3章 記憶體管理：虛擬記憶體 第84頁

快取記憶體（Cache Memory） 利用小而高速的記憶體，來提升系統的整體效能 第一階（L1）快取 第二階（L2）快取 速度比主記憶體快五到十倍 第一階（L1）快取 指令快取（I-Cache） 資料快取（D-Cache） 第二階（L2）快取 第三階 (L3) 快取 一些特殊用途的快取 第3章 記憶體管理：虛擬記憶體 第84~85頁

圖3.19 ： 記憶體階層架構 第3章 記憶體管理：虛擬記憶體 第84頁

主記憶體傳送演算法 1 CPU 將記憶體位置的地址放入Memory Address Register， 並要求可從該位址擷取的資料或指令 2 判斷包含此位址的區塊是否已經在cache slot 中： If YES，將此資訊傳送到CPU 暫存器 – DONE If NO，從主記憶體中取得包含所要求位址的區塊 配置一個可用的cache slot 給該區塊 並行處理下列兩項動作： 將資訊傳送到CPU 將該區塊載入到slot DONE (課本請見附錄A) 第3章 記憶體管理：虛擬記憶體

快取記憶體 設計快取記憶體時，必須考慮下列四項因素： 快取大小（Cache Size） 區塊大小（Block Size） 區塊取代演算法（Block Replacement Algorithm） 覆寫策略（Rewrite Policy） 第3章 記憶體管理：虛擬記憶體 第86頁

快取記憶體 命中率（Hit Ratio） 命中次數和存取次數的比率 命中（Hit） 失誤（Miss） 第3章 記憶體管理：虛擬記憶體 第86頁

快取記憶體 平均記憶體存取時間（Average Memory Access Time） 第3章 記憶體管理：虛擬記憶體 第87頁

結論 作業系統的記憶體管理負責為程式配置主記憶體儲存空間 (主記憶體、快取記憶體及暫存器)，待程式結束後再收回這些記憶體儲存空間。 作業系統的記憶體管理負責為程式配置主記憶體儲存空間 (主記憶體、快取記憶體及暫存器)，待程式結束後再收回這些記憶體儲存空間。  我們在第2 章和第3 章介紹的各種記憶體配置架構，各自解決了一些問題，也同時產生了一些問題。 第3章 記憶體管理：虛擬記憶體 第87頁

第2章與第3章記憶體配置架構比較表 第3章 記憶體管理：虛擬記憶體 第88頁