Chapter 2 記憶體管理：簡易系統

學習目標 四種記憶體配置方式：單一使用者、固定分割、動態分割以及可重新定址的動態分割。 最適配置法與先適配置法。 以記憶體清單管理可用記憶體。 記憶體釋回的重要性。 界限暫存器對記憶體配置架構的重要性。 記憶體密合的重要性及其如何改善記憶體配置的效率。 第2章 記憶體管理：簡易系統 第27頁

簡介 整個電腦系統的效能和兩項因素直接相關 四種記憶體配置法 可用的記憶體容量 系統在處理工作時，是否以最有效率的方式使用記憶體 單一使用者系統（Single-User System） 固定分割（Fixed Partition） 動態分割（Dynamic Partition） 可重新定址的動態分割（Relocatable Dynamic Partition） 第2章 記憶體管理：簡易系統 第28頁

簡介 主記憶體又稱為隨機存取記憶體 (Random Access Memory, RAM) 或核心記憶體 (Core Memory)，也稱為主要儲存裝置 (Primary Storage)。 第2章 記憶體管理：簡易系統 第28頁

單一使用者連續式架構 單一使用者連續式架構 (Single-User Contiguous Scheme) 為一種記憶體配置架構 (Memory Allocation Scheme) 記憶體管理器將待處理的程式「整個」載入記憶體，並安排「連續」的記憶體空間，以滿足該程式的記憶體需求 整個（Entirety） 連續（Contiguous） 如果程式對記憶體的需求超過系統能夠提供的範圍，該程式便無法執行。 第2章 記憶體管理：簡易系統 第28頁

圖2.1：每次只載入一支程式 第2章 記憶體管理：簡易系統 第28頁

單一使用者系統載入工作的演算法 1 將程式的第一個記憶體位置載入基底暫存器，以保護記憶體位置 2 將程式計數器 (記錄程式使用的記憶體空間) 設為記憶體位置的位址 3 讀取程式的第一個指令 4 將程式計數器的值，加上指令的位元組數 5 是否是最後一個指令？ 若是，則停止載入程式 若否，則繼續執行步驟6 (課本請見附錄A) 第2章 記憶體管理：簡易系統

單一使用者系統載入工作的演算法 6 程式計數器是否大於記憶體的大小？ 7 將指令載入到記憶體 8 讀取程式中的下一個指令 9 回到步驟4 若是，則停止載入程式 若否，則繼續執行步驟7 7 將指令載入到記憶體 8 讀取程式中的下一個指令 9 回到步驟4 (課本請見附錄A) 第2章 記憶體管理：簡易系統

單一使用者連續式架構 主要問題： 每次只能處理一件工作，無法支援多元程式 (Multi- programming) 商界無法接受這種電腦──成本效益太差 花費將近200,000 美元買來的設備，每次只能讓一個人使用 第2章 記憶體管理：簡易系統 第29頁

固定分割（Fixed Partition） 又稱為靜態分割（Static Partition） 第一種為了支援多元程式而做出的嘗試 主記憶體被分割成很多個固定大小的分割區，每一個分割區配置給一個工作(Job) 每一個分割區的大小，在電腦開機時就已經固定 新觀念：保護每一件工作各自的記憶體空間 第2章 記憶體管理：簡易系統 第29頁

將工作載入固定分割區的演算法 1 決定工作所要求的記憶體大小 2 If job_size > 最大分割區的大小 Then 拒絕該工作 列印適當訊息 回到步驟1 處理下一個工作 Else 繼續執行步驟3 3 將counter 設為1 (課本請見附錄A) 第2章 記憶體管理：簡易系統

將工作載入固定分割區的演算法 4 Do while counter <= 記憶體中的分割區數量 If job_size > memory_partition_size (counter) Then counter = counter + 1 Else If memory_partition_size (counter) = "free" Then 將工作載入到memory_partition (counter) 將memory_partition_size (counter) 改成 "busy" 回到步驟1 處理下一個工作 counter = counter + 1 End do 5 此時無分割區可用，將工作放入等待佇列 6 回到步驟1 處理下一個工作 (課本請見附錄A) 第2章 記憶體管理：簡易系統

固定分割（Fixed Partition） 記憶體內可以同時保存許多程式。 但是，程式還是必須「整個」載入，配置「連續」的記憶體空間。 第2章 記憶體管理：簡易系統 第30頁

表2.1 ：簡化的固定分割記憶體管制表範例 分割區大小 記憶體位址 存 取 分割區狀態 100K 200K Job 1 Busy 25K 存　取 分割區狀態 100K 200K Job 1 Busy 25K 300K Job 4 325K Free 50K 350K Job 2 第2章 記憶體管理：簡易系統 第30頁

圖2. 2：依照表2.1 配置的4 個 固定分割 第2章 記憶體管理：簡易系統 第31頁

固定分割（Fixed Partition） 固定分割的缺點 大型工作不易獲得記憶體分割 如果目前可用記憶體分割區太小，而較大的分割區都已遭占用，大型工作就必須等待 如果工作大於系統最大分割區的大小，該工作就完全沒有機會執行 內部碎塊（Internal Fragmentation） 固定分割會在分割區內產生閒置空間，使得記憶體的使用效率不高 第2章 記憶體管理：簡易系統 第31頁

動態分割（Dynamic Partition） 每項工作可以配置到連續的記憶體區塊 只會配置所要求的記憶體空間，不多也不少 外部碎塊（External Fragmentation） 第2章 記憶體管理：簡易系統 第32頁

圖2.3：動態配置 第2章 記憶體管理：簡易系統 第33頁

記憶體分割區配置策略 先適記憶體配置（First-Fit Memory Allocation） 取用記憶體配置表中第一個夠大的閒置分割區 最適記憶體配置（Best-Fit Memory Allocation） 取用夠大而且最貼近需求的閒置分割區 次適（Next-Fit） 最不適 （Worst-Fit） 第2章 記憶體管理：簡易系統 第34、39頁

記憶體分割區配置法 忙碌清單（Busy List） 閒置清單（Free List） 列出已使用的空間 列出所有的可用空間 第2章 記憶體管理：簡易系統 第34頁

圖2.4：最先與最適法 第2章 記憶體管理：簡易系統 第35頁

圖2.5 ：最適配置法範例 第2章 記憶體管理：簡易系統 第36頁

圖2.6 ：最適配置法範例 第2章 記憶體管理：簡易系統 第37頁

先適演算法 1 將counter 設為1 2 Do while counter <= 記憶體中的分割區數量 If job_size > memory_size (counter) Then counter = counter + 1 Else 將工作載入到memory_block (counter) 調整 free/busy 記憶體清單 回到步驟4 End do 3 將工作放入等待佇列 4 擷取下一個工作 (課本請見附錄A) 第2章 記憶體管理：簡易系統

表2.2：先適配置法 配置前 配置後 開始位址 記憶體區大小 4075 105 5225 5 6785 600 *6985 400 7560 20 7600 205 10250 4050 15125 230 24500 1000 第2章 記憶體管理：簡易系統 第38頁

最適演算法 1 設定初始值memory_block (0) = 99999 2 計算initial_memory_waste = memory_block (0) – job_size 3 設定初始值Initialize subscript = 0 4 將counter 設為1 5 Do while counter <= 記憶體中的區塊數量 If job_size > memory_size (counter) Then counter = counter + 1 Else memory_waste = memory_size (counter) – job_size If initial_memory_waste > memory_waste Then subscript = counter initial_memory_waste = memory_waste counter = counter + 1 End do (課本請見附錄A) 第2章 記憶體管理：簡易系統

最適演算法 6 If subscript = 0 Then 將工作放入等待佇列 Else 將工作載入到memory_size (subscript) 調整 free/busy 記憶體清單 7 擷取下一個工作 (課本請見附錄A) 第2章 記憶體管理：簡易系統

表2.3 ：最適配置法 配置前 配置後 開始位址 記憶體區大小 4075 105 5225 5 4785 600 6785 7560 20 7600 205 *7800 10250 4050 15125 230 24500 1000 第2章 記憶體管理：簡易系統 第38頁

釋回記憶體區塊 釋回（Deallocation） 三種狀況： 處理工作結束後歸還給系統的記憶體區塊 狀況一：釋回的記憶體區塊緊鄰著一個閒置區塊。 狀況二：釋回的記憶體區塊夾在兩個閒置區塊之間。 狀況三：釋回的記憶體區塊不與任何閒置區塊相鄰。 第2章 記憶體管理：簡易系統 第39頁

釋回記憶體區塊的演算法 If job_location 與一個或多個可用區塊相鄰 Then memory_size (counter – 1) = memory_size (counter – 1) + job_size + memory_size (counter+1) 將memory_size (counter+1) 的狀態設為null entry Else 將兩個區塊合併成一個 + job_size (課本請見附錄A) 第2章 記憶體管理：簡易系統

釋回記憶體區塊的演算法 Else 搜尋可用記憶體清單中的null entry enter job_size and beginning_address in the entry slot 將它的狀態設為 "free" DONE (課本請見附錄A) 第2章 記憶體管理：簡易系統

表2.4 ：狀況一。閒置清單在釋 回區塊前的狀態 起始位址 記憶體區塊大小 狀態 4075 105 Free 5225 5 6785 600 7560 20 (7600) (200) (Busy)1 *7800 10250 4050 15125 230 24500 1000 1 釋回的記憶體區塊起始位址為7600，大小為200，此時應該還在忙碌清單中，作者將它列於此處加上括號以便說明。 第2章 記憶體管理：簡易系統 第40頁

表2.5 ：狀況一。閒置清單在釋 回區塊後的狀態 起始位址 記憶體區塊大小 狀態 4075 105 Free 5225 5 6785 600 7560 20 *7600 205 10250 4050 15125 230 24500 1000 第2章 記憶體管理：簡易系統 第40頁

表2.6 ：狀況二。閒置清單在釋 回區塊前的狀態 起始位址 記憶體區塊大小 狀態 4075 105 Free 5225 5 6785 600 *7560 20 (7580) (20) (Busy)1 *7600 205 10250 4050 15125 230 24500 1000 第2章 記憶體管理：簡易系統 第41頁

表2.7：狀況二。釋回作業完畢 後的閒置清單 起始位址 記憶體區塊大小 狀態 4075 105 Free 5225 5 6785 600 7560 245 * (Null Entry) 10250 4050 15125 230 24500 1000 第2章 記憶體管理：簡易系統 第41頁

表2.8：狀況三。釋回區塊前的 閒置清單 起始位址 記憶體區塊大小 狀態 4075 105 Free 5225 5 6785 600 7560 245 (Null Entry) 10250 4050 15125 230 24500 1000 第2章 記憶體管理：簡易系統 第42頁

表2.9：狀況三。 釋回區塊前的 忙碌清單 起始位址 記憶體區塊大小 狀態 7805 1000 Busy *8805 445 9250 第2章 記憶體管理：簡易系統 第42頁

表2.10 ： 狀況三。釋回區塊後的 忙碌清單 起始位址 記憶體區塊大小 狀態 7805 1000 Busy * (Null entry) 9250 第2章 記憶體管理：簡易系統 第42頁

表2.11：狀況三。釋回區塊後的 閒置清單 起始位址 記憶體區塊大小 狀態 4075 105 Free 5225 5 6785 600 7560 245 *8805 445 10250 4050 15125 230 24500 1000 第2章 記憶體管理：簡易系統 第42頁

可重新定址的動態分割 （Relocatable Dynamic Partition） 記憶體密合（Compaction of Memory） 記憶體碎塊重整 (Memory Defragmentation)， 作業系統藉此收回記憶體碎塊浪費掉的儲存空間。 記憶體中的程式全部都會被搬動，從原來的位置搬到另一個位置，以連續記憶體區塊存放 程式中每一道指令的位址參照都可能需要調整，以符合新的記憶體位址，並且要小心不要誤將資料當作位址而加以調整 第2章 記憶體管理：簡易系統 第43頁

圖2.7 ：一個執行累加運算的組合語言程式 第2章 記憶體管理：簡易系統 第44頁

圖2.8 ：重新定址的考量 第2章 記憶體管理：簡易系統 第44頁

圖2.9 ：程式於密合與重新定址期間的變化 第2章 記憶體管理：簡易系統 第45頁

可重新定址的動態分割 （Relocatable Dynamic Partition） 記憶體密合引發了三個問題： 在記憶體密合與重新定址期間，發生了什麼事情？ 如何追蹤每一支程式的移動狀況？ 那一些清單需要更新？ 界限暫存器（Bounds Register） 重新定址暫存器（Relocation Register） 第2章 記憶體管理：簡易系統 第45~46頁

圖2.10 第2章 記憶體管理：簡易系統 第46頁

圖2.11：重新定址暫存器 第2章 記憶體管理：簡易系統 第46頁

可重新定址的動態分割 （Relocatable Dynamic Partition） 何時才是進行記憶體密合的好時機？應該多久做一次記憶體密合？ 設定一個門檻值，每當記憶體使用量達到這個門檻值，便進行記憶體密合。 只有在工作因為記憶體不足而進入等待狀態時，進行記憶體密合。 定時執行記憶體密合。 第2章 記憶體管理：簡易系統 第47頁

結論 本章介紹了四種記憶體管理技術： 共通處有三點：程式必須整個 單一使用者系統 (Single-User System) 固定分割 (Fixed Partition) 動態分割 (Dynamic Partition) 可重新定址的動態分割 (Relocatable Dynamic Partition) 共通處有三點：程式必須整個 載入記憶體 儲存在連續的記憶體區塊內 保留在記憶體內直到工作完成 第2章 記憶體管理：簡易系統 第48頁

結論 程式設計師必須嚴格限制程式的大小，以免程式的大小超過最大的記憶體分割區而無法執行。 第2章 記憶體管理：簡易系統 第48頁