两层式分页表.ppt

虛擬記憶體 程式的總長度可以超過實體記憶體的長度，在這種情況下，程式設計師就好像是在一塊連續，而且巨大的邏輯記憶體位址空間中寫程式，而不需考慮到程式長度限制的問題。這種 邏輯記憶體位址空間就稱為虛擬記憶體。 需求分頁 將行程暫時沒有用到的頁面放在輔助記憶體中，等到要執行某個頁面時，再將它移回記憶體中，這種作法就稱為需求分頁。 分頁程式與置換程式 分頁程式—負責將頁面移入/移出記憶體的程式。在需求分頁機制下，負責行程頁面在主記憶體與輔助記憶體間的搬移，而且這種搬移並不會影響該行程目前的執行狀態。 置換程式—負責整個行程在主記憶體與輔助記憶體間的置換，被換出的行程會進入置換狀態，並且不會被納入短期排程的考量。 分頁錯誤 當行程試圖去存取ㄧ個無效的頁面時，硬體會產生分頁錯誤的例外中斷，並且將控制權移轉給作業系統中的分頁錯誤常式。 分頁錯誤的處裡流程 頁面替換局部性原則 行程再某一時克所進行的記憶體存取，多半會聚集在幾個主要的位址附近，這種現象稱為局部性原則。 時間性局部性 記憶體的某個位置剛被存取過，不久又可能還會在被存取，這種現象稱為時間的局部性。 空間性局部性 記憶體的某個位置剛被存取過之後，他附近的位置可能又很快就會被存取，這種現象稱為空間的局部性。 最佳替換演算法 頁面移出/移入的時間與記憶體存取時間的相對差距極大，所以在選擇要將哪些頁面移出時，理想上最好是能將以後永遠不會用到的頁面移出，退而求其次。則是將最久以後才會用到的頁面移出，已達到最有效率的替換；這種最有效的頁面替換方式稱為最佳替換演算法。 最佳替換演算法範例 現有的頁面替換演算法 先進先出演算法(FIFO) 最久未用演算法(LRU) 最久未用近似法(LRU近似法) 先進先出演算法 最久未用演算法 最久未用近似法 雖然最久未用演算法的表現不錯，但是由於必須依靠特殊的硬體支援，很少系統能夠完整實作，所以有人提出近似的LRU演算法，以簡化所需的運算。例如:老化演算法，二次機會法。 超額配置 在沒有使用需求分頁的技巧時，100個頁框大概只能放入個10行程，但是因為行程在執行的過程中，未必會使用到所有的頁面，假使每個行程通常會用到的頁面是5頁，則100個頁框就可以放入個20行程了。如果我們利用這個特性，增加程式多工的數量，例如在100個頁框中配置了個15行程，就會對記憶體造成超額配置。 輾轉現象 當行程用來處理分頁的時間多於執行指令的時間，而造成效能大幅降低的這種現象，就稱為輾轉現象。 頁框數量配置 固定配置策略—在行程建立的時候，根據其互動或批次的類型或是由系統管理者指定，預先分配給它固定數量的頁框。 變動配置策略--在行程執行的過程中，變更它所分配到的頁框。 工作集 工作集是以WS(t, Δ)來定義，代表從行程執行的時間 t 開始往前計算的Δ個時間單位內，行程所參考到的頁面集合，而時間 t 最簡單的計算方式，則是將執行一個指令的時間算成一個時間單位。 分頁錯誤頻率 分頁錯誤頻率很高，表示所配置的頁框數目可能不足，如果分頁錯誤頻率太低，表示可能配置太多的頁框數目。藉由設定行程分頁錯誤頻率的上，下限，作業系統可以在超過上現時增加配置的頁框數，而低於下限時回收部份的頁框。 兩層式分頁表 當分頁表很大時，如果希望維持記憶體管理的彈性，避免配置完全連續的空間，則我們可以將分頁表本身也切割成與記憶體頁框相同大小的頁面，分別放入可用的頁框中。此時，我們必須另外建立一個表格，用來記錄分頁表的頁面位置，因此形成了兩層分頁表。 兩層式分頁 兩層式分頁表的位址轉換 反轉分頁表 如果可用的頁框數目，遠小於各行程的邏輯位址空間總和，則建立一個表格來記錄每個頁框目前的內容，遠比記錄每個行程的頁框資料要更節省空間。這樣的表格就稱為反轉分頁表。 反轉分頁表的位址轉換 * * 第五章 虛擬記憶體 朱肇明 資管系 講師 大華技術學院 發生分頁錯誤 終止行程 取出一個空頁框 非法記憶體存取 是否有空頁框 將要移入的頁面 寫入選擇的頁框 修改分業表 重新啟動因分頁錯誤而被中斷的指令 找出要移出的頁面 視需要將要移出的頁面內容寫入磁碟 是 是 否 否 頁框 一共發生6次的分頁錯誤 5 5 5 5 5 5 5 5 5 3 2 2 2 2 2 2 2 2 2 2 2 1 1 1 0 0 0 1 1 1 1 1 1 1 5 1 2 5 0 1 5 3 1 2 1 參考頁面編號 頁框 一共發生9次的分頁錯誤 1 0 0 0 0 0 3 3 3 5 5 1 1 1 1 1 2 2 2 2 2 2 2 2 5 5 5 5 1 1 1 1 1 5 1 2 5 0 1 5 3 1 2 1 參考頁面編號 頁框 一共發生7次的分頁錯誤 1 1 1 0 0 0 3 3 3 5 5 5