《虛擬記憶體》由会员分享，可在线阅读，更多相关《虛擬記憶體（51页珍藏版）》请在金锄头文库上搜索。
1、9.1虛擬記憶體n背景資料n頁需求(Demand Paging)n行程產生(Process Creation)n頁置換(Page Replacement)n框架的配置(Allocation of Frames)nThrashingn作業系統範例(Operating System Examples)9.2背景資料n虛擬記憶體 經使用者的邏輯記憶體與實體記憶 體分開.F只需將程式的部分放到記憶體來執行.F因此邏輯位址空間可以比實體位址空間大很多.F允許位址空間被一些行程共享.F允許更多有效的行程產生.n虛擬記憶體經由下列方式完成:F頁需求F分段需求9.3虛擬記憶體大於實際記憶體9.4頁需求(Dem
2、and Paging)n只有在頁被需要時，會將頁放入到記憶體內.F需要較少的I/OF需要較少的記憶體F較快回應F更多使用者n頁被需要時 參考到這個頁F無效參考 放棄F如果不在記憶體內放入記憶體9.5一個支援頁的記憶體系統與連續磁碟 空間的轉換9.6有效及無效位元 Valid-Invalid Bitn在每一個頁表格元素中有一個validinvalid bit (1 in-memory, 0 not-in-memory) n表格一開始的所有validinvalid 位元都設定為0. n某一個頁表格的即時狀態.n在位址轉換的時期, 假使碰到的頁表格的validinvalid bit 是0 頁失誤 (
3、page fault).1 1 1 1 00 0Frame #valid-invalid bitpage table9.7當某些頁不在記憶體時的頁表格9.8頁失誤(Page Fault)處理範例1.假使有參考到一個頁, 第一次的參考會跳到 OS page fault 2.作業系統在另一個表格來決定:F無效的參考 abort. F只是不在記憶體內. 3.獲得一個空的框架. 4.將該頁置換到框架. 5.重設表格, 有效位元 = 1. 6.重新啟動指令: 最少最近使用(Least Recently Used)F區塊移動(block move)F自動增加與減少的位址(auto increment/de
4、crement location)9.9處理頁失誤的步驟9.10假使沒有可用的框架怎麼辦?n頁取代(Page replacement )找某個在記憶體的 頁, 而這個頁是沒有正在用的，然後將它swap out.F演算法F效能 需要一個演算法將導致最小頁失誤的產生數目.n相同頁可能將被帶入記憶體好幾次.9.11頁需求的效能n頁失誤率 0 p 1.0Fif p = 0 沒有頁失誤Fif p = 1, 每次的參考是一個失誤n有效存取時間 (EAT) EAT = (1 p) x 記憶存取 + p (頁失誤負擔 + 將頁置換出 + 將頁置換入 + 重新啟動的負擔)9.12頁需求範例n記憶體存取時間 =
5、1 microsecondn一個正被取代的頁已經被修改, 所以要被置換出 記憶體到磁碟, 而花去的時間是將頁置換時間的 50%.n將頁置換的時間= 10 msec = 10,000 microsec EAT = (1 p) x 1 + p (15000) 1 + 15000p (in microsec)9.13行程產生n虛擬記憶體在行程產生時可以會有下列的優點:- Copy-on-Write- Memory-Mapped Files9.14Copy-on-WritenCopy-on-Write (COW)允許父子行程一開始可分 享記憶體的相同的幾個頁.假使其中一個行程變更一個共享的頁, 只有當
6、時 會產生這個頁的副本.n因為變更的頁會產生副本, 使得COW允許更有效 的行程產生.n可用的頁可以從一個已被清為0的連續頁空間獲 得配置(a pool of zeroed-out pages).9.15記憶體對應檔 Memory-Mapped Filesn記憶體對應檔的I/O經由將一磁碟區塊對應到記 憶體的一個頁, 可以允許檔案I/O當作例行的記憶 體存取.n一個檔案使用頁需求來啟動讀的動作. 一個與頁 大小相同的檔案區塊從檔案系統讀入到實體記憶 體的頁. 連續的從檔案讀與寫到檔案的動作被當 作是一般記憶體的存取.n將檔案的I/O經由記憶體而不僅是read() write()的 系統呼叫.n
7、經由記憶體中的頁分享也可以讓幾個行程參考到 相同的檔案.9.16Memory Mapped Files9.17頁取代(Page Replacement)n將頁取代機制加入到頁失誤服務程式來避免記憶 體過渡配置的狀況發生.n利用變更位元(dirty bit)來減少頁傳輸的負擔 只 有被變更過的頁才需要寫回至磁碟.n頁取代完成了邏輯記憶體與實際記憶體的獨立區 隔F大的虛擬記憶體可以在實際記憶體空間比較小的狀況 下實踐.9.18頁取代的需要動作9.19頁取代的基本機制n找到磁碟上需要的頁的位址.n找一個可用的框架:F假使有一個空的框架, 就用它. F如果沒有, 就利用頁取代演算法找出一個被犧牲的框
8、架.n將需要的頁讀進這個可用的框架、更新這個頁及 框架的相關表格.n重新啟動這個行程.9.20頁取代9.21頁取代演算法n需要提供最低頁失誤率.n經由執行在一個特定記憶體參考的串列(參考串 列)及計算字串所造成的頁失誤數目來評估該演 算法的效能.n在我們所有的範例, 都使用下列的參考串列 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.9.22頁失誤與框架數目的對應圖9.23先進先出 (FIFO)演算法n參考串列: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 n三個框架(每個行程可以同時有三個框架在記憶體)n四個框架nFIFO 取代演算法 Bel
9、adys Anomaly(不正常現象)Fmore frames less page faults1231234125349 page faults1231235124510 page faults4439.24FIFO頁取代9.25FIFO 會造成Beladys Anomaly 現象的範例9.26最佳化演算法n取代一個在最長時間內不會被使用的頁. n4 frames example1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5n但是如何知道這一點? n可以被用來測量你的演算法效能有多好.12346 page faults459.27最佳化頁取代 Optimal Page
10、Replacement9.28最少最近使用演算法 (LRU)n參考串列: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5n計數器的製作F每個頁有一個計數器, 當每次這個頁被參考時, 會將時間複製到計 數器.F當一個頁需要被變更時, 檢查所有頁的計數器來決定那個頁要被 改變.123544359.29LRU頁取代9.30LRU演算法(Cont.)n堆疊方式的製作(Stack implementation) 以雙向 鏈所形成的堆疊將頁號碼保存:F所參考的頁:4置入堆疊頂端4需要變更6個指標F頁取代方式不需要搜尋.9.31利用堆疊來記錄最近曾被參考的頁參考9.32LRU近似演算法
11、n參考位元(reference bit)F每個頁會有一個位元, 起始值為0.F當頁被參考到時頁, 位元會設定為1.F取代位元為0的頁(假使有存在).F問題就是我們卻不知道過去發生參考的順序.n第二次機會F需要參考位元.F經由時間置換.F假使被取代的頁(以時間順序)有參考位元為1. 然後:4將參考位元設定為 0.4將頁留在記憶體中.4取代下一頁 (以時間順序), 按照同樣的規定操作.9.33第二次機會(時間)頁取代演算法9.34計數演算法n保持每一個頁已經被參考次數.nLFU演算法: 取代有最小值的頁.nMFU演算法:基於擁有最小計數值的頁有可能剛 剛才被讀入而且馬上就要被用到的觀點下.9.35
12、框架的配置n每個行程需要的最小頁數目.n範例: IBM 370 需要6 頁來處理SS MOVE指令 :F指令是6位元組, 參考範圍可能需要2頁.F需要2頁來處理來自其它的參考.F需要2頁來處理參考到其他的.n兩種主要的配置機制.F固定配置F優先權配置9.36固定配置n相同配置 e.g., 假使有100 框架與5個行程, 每 個行程有20頁.n比例配置 有行程大小來配置.9.37優先權的配置n不考量大小而是用優先權來使用比例配置機制.n假使行程Pi 產生一個頁失誤,F為頁取代來選擇框架中的一個.F為頁取代從擁有最低優先權號碼的行程中選擇一個框 架.9.38全域與區域取代n全域取代 行程從所有的框
13、架的集合中來取代; 一個行程可以從另一個行程中取得框架.n區域取代 每一個行程只從自己所配置到的框架 集合中取得框架.9.39Thrashingn假使一個行程沒有足夠的頁, 頁失誤率非常高. 將會造成:F低CPU使用率.F作業系統認為他需要增加多程式化的程度.F另外一個行程加入到系統.nThrashing 一個行程大部分的時間都在忙著把 置換頁進入或者是頁換出(程式真正被CPU執行 的時間很少).9.40Thrashing n為甚麼頁機制可以成功? 區域性模型(Locality model)F行程會從一個區域到另一個區域移動. F區域性可以重複. n為甚麼thrashing會發生? size
14、of locality total memory size9.41記憶體參考的區域性-參考模式9.42工作集合模型n 工作集合視窗 一個固定的頁參考數目 Example: 10,000 instructionnWSSi (行程Pi的工作集合) = 在最多最近參考過的頁總數 (會隨著時間變動)F假使 太小將無法掌握整個區域性.F假使 太大將可包含幾個區域性.F假使 = 將包含所有程式.nD = WSSi 所有需求的框架 n假使D m Thrashingn解決方案：假使D m, 就暫停某一個行程.9.43工作集合模型9.44追蹤工作集合演算法n可以利用區間計時器與一個參考位元來求近似效 果n範例:
15、 = 10,000個參考F在每5000個參考後就產生插斷.F為每一頁保持2個參考位元在記憶體內.F每次計時插斷發生, 複製與設定所有參考位元值為0.F假使記憶體中的一個位元為1 在工作集合中的頁.n為甚麼這樣的方式不一定完全正確?n改善方式 = 10個位元而且每1000個時間單位產 生插斷.9.45頁失誤頻率機制n建立 可接受(“acceptable”)頁失誤頻率.F假使實際的頻率太小, 行程可減少框架數目.F假使實際的頻率太大, 行程要增加框架.9.46其他考量n預先載入頁,Prepaging F減少行程初始啟動時可能發生頁失誤的次數F預先載入可能要被參考到的頁.F但是被預先載入的頁卻沒有用
16、到, 將會浪費I/O 傳輸 時間及記憶體空間.n頁大小的選擇F碎片(fragmentation)F表格大小 FI/O負擔F區域性9.47其他考量 (Cont.)nTLB Reach 可以從TLB所獲致的記憶體存取容 量.nTLB Reach = (TLB Size) X (Page Size)n理想來說, 每個行程的工作集合存在TLB. 否則 將會有高頁失誤.9.48Increasing the Size of the PagenIncrease the Page Size.F將導致碎片的增加，因為不是所有的行程需要大空間 的頁.FProvide Multiple Page Sizes. 4這樣允許需要大空間頁的應用程式可以在不會增加碎片的機 會下獲致頁.9.49其他考量 (Cont.)n程式結構Fint A = new int10241024;F每一列存放在一
