作业系统 页面替换.ppt

班級：夜資科3A 姓名：969G049 葉軒緯 969G052 白淞尹 969G0 969G0 前言 分頁替換(Page replacement)是當所有的記憶空間都已被使用了，此時作業系統便會決定將記憶體內哪些目前並未使用的欄空出來，以便載入所需要的分頁，由不同的替算法中演算找出較好的方法。 頁面替換局部性原則 行程再某一時克所進行的記憶體存取，多半會聚集在幾個主要的位址附近，這種現象稱為局部性原則。 分頁錯誤的處理流程 發生分頁錯誤 非法的記憶體存取？ 取出一個空頁框 是否有空頁框 找出要移出的頁面 視需要將要移出頁面 的內容寫入磁碟 將要移入的頁面 寫入選擇的頁框 修改分頁表 重新啟動因為分頁 錯誤而被中斷的指令 終止行程 是 否 是 否 分頁錯誤的處理時間 記憶體存取時間：介於10ns到200ns之間。 假設記憶體的存取時間為m，當沒有發生分頁錯誤時，從記憶體中讀取所需字組的時間就是m。 如果發生分頁錯誤時，行程必須先等待作業系統將所需的頁面載入。 假設處理分頁錯誤的時間為t，則該字組的存取時間就變為t+m。 影響t的因素：處理因為中斷所造成的控制權移轉，搜尋頁框，進行磁碟讀取，以及重新開始執行等 ，大約需要25ms。 假設m=25ns，則主記憶體存取與輔助記憶體存取的時間比大約是1:1000000 。 如果在1000次記憶體存取中發生了1次分頁錯誤：t+m25。 則平均的存取時間就變成大約25微秒：25+25*999)/1000。 也就是單純記憶體存取的1000倍。 作業系統 頁面替換演算法  FIFO先進先出演算法 (First-in，First-out) 最簡單的頁替換演算法。 當要替換一頁時，我們就去選擇存在記憶體內最久的一個分頁，也就是最早被載入記憶體內的分頁，將它換掉，並載入所需求的分頁。可透過FIFO的佇列來掌握在記憶體中的所有頁。 參考頁面編號 1 2 1 3 5 1 0 5 2 1 5 1 1 1 1 1 5 5 5 5 2 2 2 2 2 2 2 2 1 1 1 1 1 5 5 3 3 3 0 0 0 0 0 1 一共發生9次的分頁錯誤 LRU最久未用演算法 (Least recently used replacement) 雖然 LRU 演算法的表現不錯，但是由於必須依靠特殊的硬體支援，很少系統能夠完整地實作。當要替換一頁時，把過去到現在最久時間未使用的那頁替換掉。 參考頁面編號 1 2 1 3 5 1 0 5 2 1 5 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 5 5 5 5 5 5 5 5 3 3 3 0 0 0 1 1 1 一共發生7次的分頁錯誤 LRU 近似換頁法 (LRU approximation replacement) 由於很少電腦能夠提供足夠的硬體來支援真正的LRU頁替換，而LRU近日換頁法是一種以「參考位元」的方式來執行分頁替換的方法，利用參考位元來記錄過去使用過哪些分頁；雖然無法知道被使用的先後次序，但知道哪些被使用過而哪些還沒被使用。這種部分排班資訊可使許多分頁替換演算法盡量接近LRU替換法。 最佳替換演算法 (Optimal replacement) 是所有演算法中分頁錯誤比率最低的一種。當要替換一頁時，把未來最長時間之內不會被用到的那一頁替換掉。 參考頁面編號 1 2 1 3 5 1 0 5 2 1 5 1 1 1 1 1 1 1 0 0 0 1 1 1 2 2 2 2 2 2 2 2 2 2 2 3 5 5 5 5 5 5 5 5 5 一共發生6次的分頁錯誤 頁面大小的選擇 在分頁存儲管理系統中，頁面大小的選擇非常重要。如果選擇的頁面較小，則可以使頁內碎片較小病減少內存碎片的總量，有利於提高內存利用率；但另一方面，也會使每個進程中包含的頁面數較多，從而導致頁表過長，占用大量內存空間，同時還會降低頁面換入/換出的效率。如果選擇的頁面較大，則可以減少頁表長度，提高頁面換入/換出的效率，但卻又使頁內碎片增大。因此，頁面大小應該選擇適中，通常為2的冪，一般在512B到8KB之間。 結論 FIFO算法的命中率最低，LRU算法的命中率與OPT算法很接近。 這一結論具有普遍意義。 因此，在實際使用中，LRU算法是一種比較好的算法。 目前，許多機器的虛擬存儲器都採用LRU算法。