第12講 虛擬存儲：置換算法

1、第第1212講講 虛擬存儲：置換算法虛擬存儲：置換算法授課教師：馬立平授課教師：馬立平聯(lián)系方式：聯(lián)系方式：Southwest University of Science and Technology虛擬存儲概念 虛擬存儲的需求背景 覆蓋技術(shù) 交換技術(shù) 局部性原理 虛擬存儲概念 虛擬頁式存儲 缺頁異常提綱頁面置換算法的概念 全局頁面置換算法局部頁面置換算法置換算法的功能和目標功能當出現(xiàn)缺頁異常，需調(diào)入新頁面而內(nèi)存已滿時，置換算法選擇被置換的物理頁面設(shè)計目標盡可能減少頁面的調(diào)入調(diào)出次數(shù)把未來不再訪問或短期內(nèi)不訪問的頁面調(diào)出頁面鎖定(frame locking)描述必須常駐內(nèi)存的邏輯頁面操作系統(tǒng)的關(guān)

2、鍵部分要求響應(yīng)速度的代碼和數(shù)據(jù)頁表中的鎖定標志位(lock bit)置換算法的評價方法記錄進程訪問內(nèi)存的頁面軌跡舉例: 虛擬地址訪問用(頁號, 位移)表示(3,0), (1,9), (4,1), (2,1), (5,3), (2,0), (1,9), (2,4), (3,1), (4,8)對應(yīng)的頁面軌跡3, 1, 4, 2, 5, 2, 1, 2, 3, 4替換如 c, a, d, b, e, b, a, b, c, d評價方法模擬頁面置換行為，記錄產(chǎn)生缺頁的次數(shù)更少的缺頁, 更好的性能頁面置換算法分類 局部頁面置換算法 全局頁面置換算法置換頁面的選擇范圍僅限于當前進程占用的物理頁面內(nèi)最優(yōu)算法

3、、先進先出算法、最近最久未使用算法時鐘算法、最不常用算法置換頁面的選擇范圍是所有可換出的物理頁面工作集算法、缺頁率算法提綱頁面置換算法的概念局部頁面置換算法最優(yōu)頁面置換算法 (OPT, optimal)先進先出算法 (FIFO)最近最久未使用算法 (LRU, Least Recently Used)Belady現(xiàn)象LRU、FIFO和Clock的比較時鐘頁面置換算法 (Clock)最不常用算法 (LFU, Least Frequently Used) 全局頁面置換算法最優(yōu)頁面置換算法(OPT, optimal)缺頁最少，是理想情況實際系統(tǒng)中無法實現(xiàn)無法預知每個頁面在下次訪問前的等待時間缺頁時，計

4、算內(nèi)存中每個邏輯頁面的下一次訪問時間選擇未來最長時間不訪問的頁面置換在未來最長時間不訪問的頁面算法特征算法實現(xiàn)基本思路在模擬器上運行某個程序，并記錄每一次的頁面訪問情況第二遍運行時使用最優(yōu)算法作為置換算法的性能評價依據(jù)最優(yōu)頁面置換算法示例10987654321dcbabebdacabceabceabceabceabcdabcdabcd0123abcd0訪問請求時間缺頁狀態(tài)每頁的下次訪問時間a=7b=6 c=9d=10abce物理幀號cadb769d=1010babca=?b=?c=?d=?先進先出算法（First-In First-Out, FIFO）思路選擇在內(nèi)存駐留時間最長的頁面進行置換實

5、現(xiàn)維護一個記錄所有位于內(nèi)存中的邏輯頁面鏈表鏈表元素按駐留內(nèi)存的時間排序，鏈首最長，鏈尾最短出現(xiàn)缺頁時，選擇鏈首頁面進行置換，新頁面加到鏈尾很少單獨使用特征實現(xiàn)簡單性能較差，調(diào)出的頁面可能是經(jīng)常訪問的進程分配物理頁面數(shù)增加時，缺頁并不一定減少(Belady現(xiàn)象)FIFO在4個頁幀中執(zhí)行：假定初始a-b-c-d順序bac訪問頁面鏈表109654321dcbabebdac0123abcd0訪問請求時間缺頁狀態(tài)物理幀號78進程占用物理內(nèi)存abcdabcdabcdabcdebedebcdeacddabceabdeabccadbb最近最久未使用算法 (Least Recently Used, LRU)特征

6、最優(yōu)置換算法的一種近似思路選擇最長時間沒有被引用的頁面進行置換如某些頁面長時間未被訪問，則它們在將來還可能會長時間不會訪問實現(xiàn)缺頁時，計算內(nèi)存中每個邏輯頁面的上一次訪問時間選擇上一次使用到當前時間最長的頁面最近最未被使用算法(LRU) 置換的頁面是最長時間沒有被引用的10987654321dcbabebdacabedabedabedabcdabcdabcdabcd0123abcd0訪問請求時間缺頁狀態(tài)每頁的下次訪問時間a=2b=4 c=1d=3abed物理幀號abdcabeca=7b=8 e=5d=3a=7b=8 e=5c=9cadb24 c=113bab78d=3537 e=5859LRU算

7、法的可能實現(xiàn)方法活動頁面棧訪問頁面時，將此頁號壓入棧頂，并棧內(nèi)相同的頁號抽出缺頁時，置換棧底的頁面特征開銷比較大頁面鏈表缺頁時，置換鏈表尾節(jié)點的頁面系統(tǒng)維護一個按最近一次訪問時間排序的頁面鏈表鏈表首節(jié)點是最近剛剛使用過的頁面鏈表尾節(jié)點是最久未使用的頁面訪問內(nèi)存時，找到相應(yīng)頁面，并把它移到鏈表之首用棧實現(xiàn)LRU算法109654321dcbabebdacabedabedabedabcdabcdabcdabcd0123abcd0訪問請求時間缺頁狀態(tài)abed物理幀號abbcabec78保持一個最近使用頁面的“?！痹L問頁面棧被置換頁面ccaccaca dacdbdacbdacbdac adbecadbe

8、adbebbedabaedabedabaedcbaedcbaedcbaebbeda提綱頁面置換算法的概念局部頁面置換算法最優(yōu)頁面置換算法 (OPT, optimal)先進先出算法 (FIFO)最近最久未使用算法 (LRU, Least Recently Used)Belady現(xiàn)象LRU、FIFO和Clock的比較時鐘頁面置換算法 (Clock)最不常用算法 (LFU, Least Frequently Used) 全局頁面置換算法時鐘置換算法（Clock）算法訪問頁面時，在頁表項記錄頁面訪問情況缺頁時，從指針處開始順序查找未被訪問的頁面進行置換思路僅對頁面的訪問情況進行大致統(tǒng)計數(shù)據(jù)結(jié)構(gòu)在頁表項

9、中增加訪問位，描述頁面在過去一段時間的內(nèi)訪問情況各頁面組織成環(huán)形鏈表指針指向最先調(diào)入的頁面時鐘算法是LRU和FIFO的折中特征時鐘置換算法的實現(xiàn) 頁面裝入內(nèi)存時，訪問位初始化為0 訪問頁面（讀/寫)時，訪問位置1 缺頁時，從指針當前位置順序檢查環(huán)形鏈表訪問位為0，則置換該頁訪問位為1，則訪問位置0，并指針移動到下一個頁面，直到找到可置換的頁面時鐘置換算法圖示駐留位01頁號7:150頁號1:130頁號4:141頁號0:111頁號3:1訪問位幀號5100067時鐘頁面置換示例10965432101230訪問請求時間缺頁狀態(tài)物理幀號78駐留頁面的頁表項abcdabcdabcdabcdabcdebcd

10、ebadcadbebabcdcadb0000abcd0010abcd1010abcd1011abcd1111abcd0111abcd0011abcd0001abcd0000abcd0000abcd0a1e1000ebcdebcd1100ebcdb1000ebcd1000ebcd0 c1010ebad1110ebadebadb0 d1111ebac0111ebacebacdbac0011ebac0001ebac0000ebac0000ebac0e1000dbac1000ebcd1010ebad1111ebac改進的Clock算法駐留位訪問位修改位幀號0頁號7:150頁號1:130頁號 4:14頁

11、號0:19頁號3:110011011算法在頁面中增加修改位，并在訪問時進行相應(yīng)修改缺頁時，修改頁面標志位，以跳過有修改的頁面思路減少修改頁的缺頁處理開銷指針掃過前指針掃過后使用位 修改位00110101000001 置換使用位修改位10016007改進的Clock算法1096543210訪問請求時間缺頁狀態(tài)物理幀號78abedabedcawdbwebawbcdabed駐留頁面的頁表項abedabecadec0123abcdabcdabcdabcdabcdcadb00000000abcd00001000abcd11001000abcd11001010abcd11111010abcd0111101

12、0abcd01011010abcd01010010abcd01010000abcd00010000a*bcd00000000a*b*cd00000000a*b*cd00c00001000a*b*ed00001000abedb00101000abed11101000abeda11101000abedb00d11101010abec11101010abec01101010abec01001010abec01000010abec01000000abec00000000a*bec00000000a*bec00b00100000a*dec最不常用算法（Least Frequently Used, LFU

13、）缺頁時，置換訪問次數(shù)最少的頁面思路實現(xiàn)每個頁面設(shè)置一個訪問計數(shù)訪問頁面時，訪問計數(shù)加1缺頁時，置換計數(shù)最小的頁面特征算法開銷大開始時頻繁使用，但以后不使用的頁面很難置換解決方法：計數(shù)定期右移LRU和LFU的區(qū)別LRU關(guān)注多久未訪問,時間越短越好LFU關(guān)注訪問次數(shù)，次數(shù)越多越好LFU算法示例109654321d17c20b20a19b1e18b5d14a1c70123a8b5c6d20訪問請求時間缺頁狀態(tài)物理幀號執(zhí)行在4個頁幀中：假定最初的訪問次數(shù)a-8 b-5 c-6 d-278a8b5d2c13a9b5d2c13a9b5d16c13a9b10d16c13e18b11d16c13c13a9d

14、16b10e18b10d16c13b11e18d16c13a19e18d16a19b20e18a19b20c20a19b20c20d17提綱頁面置換算法的概念局部頁面置換算法最優(yōu)頁面置換算法 (OPT, optimal)先進先出算法 (FIFO)最近最久未使用算法 (LRU, Least Recently Used)Belady現(xiàn)象LRU、FIFO和Clock的比較時鐘頁面置換算法 (Clock)最不常用算法 (LFU, Least Frequently Used) 全局頁面置換算法Belady現(xiàn)象思考哪些置換算法沒有Belady現(xiàn)象？原因FIFO算法的置換特征與進程訪問內(nèi)存的動態(tài)特征矛盾被它

15、置換出去的頁面并不一定是進程近期不會訪問的現(xiàn)象采用FIFO等算法時，可能出現(xiàn)分配的物理頁面數(shù)增加，缺頁次數(shù)反而升高的異?，F(xiàn)象FIFO算法有Belady現(xiàn)象FIFO23412512345521521435頭缺頁狀態(tài)1訪問順序 : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5物理頁面數(shù): 3尾頭頭121321432143214521352435缺頁次數(shù): 9FIFO23412512345尾缺頁狀態(tài)1訪問順序 : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5物理頁面數(shù): 4頭43214321頭頭頭缺頁次數(shù): 1012132143215432154321

16、54321543215432FIFO算法有Belady現(xiàn)象LRU算法沒有Belady 現(xiàn)象物理頁面數(shù): 3物理頁面數(shù): 4時鐘/改進的時鐘頁面置換是否有Belady現(xiàn)象？為什么LRU頁面置換算法沒有Belady現(xiàn)象？1 2 3 4 1 2 5 1 2 3 4 51 1 1 2 3 4 1 2 5 1 2 3 2 2 3 4 1 2 5 1 2 3 4 3 4 1 2 5 1 2 3 4 51 2 3 4 1 2 5 1 2 3 4 51 1 1 1 2 3 4 4 4 5 1 2 2 2 2 3 4 1 2 5 1 2 3 3 3 4 1 2 5 1 2 3 4 4 1 2 5 1 2 3 4

17、 5缺頁次數(shù): 10缺頁次數(shù): 8LRU、FIFO和Clock的比較例如：給進程分配3個物理頁面，邏輯頁面的訪問順序為1、2、3、4、5、6、1、2、3如頁面進入內(nèi)存后沒有被訪問，最近訪問時間與進入內(nèi)存的時間相同F(xiàn)IFO依據(jù)頁面進入內(nèi)存的時間排序LRU需要動態(tài)地調(diào)整順序LRU依據(jù)頁面的最近訪問時間排序LRU可退化成FIFOLRU算法和FIFO本質(zhì)上都是先進先出的思路FIFO的頁面進入時間是固定不變的LRU、FIFO和Clock的比較缺頁時，再把它移動到鏈表末尾頁面訪問時，不動態(tài)調(diào)整頁面在鏈表中的順序，僅做標記對于未被訪問的頁面，Clock和LRU算法的表現(xiàn)一樣好LRU算法性能較好，但系統(tǒng)開銷較

18、大FIFO算法系統(tǒng)開銷較小，會發(fā)生Belady現(xiàn)象Clock算法是它們的折衷對于被訪問過的頁面，Clock算法不能記錄準確訪問順序，而LRU算法可以提綱頁面置換算法的概念 全局頁面置換算法工作集置換算法缺頁率置換算法局部頁面置換算法抖動和負載控制局部置換算法沒有考慮進程訪存差異FIFO 頁面置換算法: 假設(shè)初始順序 a-b-c 1211109876543210dcbadcbadcba時間訪問頁面aaaaa0ccccc2d-3bbbbb1acdbacdbacdbacdbacdbacdbacdbacdb缺頁狀態(tài)物理幀號bbbcccdddaaaa0daaabbbcccccc2ccdddaaabbbb

19、b1缺頁狀態(tài)物理幀號物理頁面數(shù): 3缺頁次數(shù): 9物理頁面數(shù): 4缺頁次數(shù): 1全局置換算法全局置換算法要解決的問題全局置換算法需要確定分配給進程的物理頁面數(shù)分配給進程的內(nèi)存也需要在不同階段有所變化進程在不同階段的內(nèi)存需求是變化的 思路 全局置換算法為進程分配可變數(shù)目的物理頁面CPU利用率與并發(fā)進程數(shù)的關(guān)系 CPU利用率與并發(fā)進程數(shù)存在相互促進和制約的關(guān)系進程數(shù)少時，提高并發(fā)進程數(shù)，可提高CPU利用率并發(fā)進程導致內(nèi)存訪問增加并發(fā)進程的內(nèi)存訪問會降低了訪存的局部性特征局部性特征的下降會導致缺頁率上升和CPU利用率下降并發(fā)進程數(shù)CPU利用率抖動工作集一個進程當前正在使用的邏輯頁面集合，可表示為二元

20、函數(shù)W(t, )t是當前的執(zhí)行時刻 稱為工作集窗口（working-set window ），即一個定長的頁面訪問時間窗口W(t, )是指在當前時刻 t 前的 時間窗口中的所有訪問頁面所組成的集合| W(t, ) | 指工作集的大小，即頁面數(shù)目進程的工作集示例2 6 1 5 7 7 7 7 5 1 6 2 3 4 1 2 3 4 4 4 3 4 3 4 4 4 1 3 2 7 頁面訪問順序：如果 時間窗口的長度為10，那么：t W(t1, ) = 1, 2, 5, 6, 7W(t2, ) = 3, 41, 2, 5, 6, 7 1, 5, 6, 7 1, 2, 5, 6, 7 1, 2, 3,

21、 5, 6, 7 1, 2, 3, 4, 5, 6, 7 1, 2, 3, 4, 5, 6 1, 2, 3, 4, 6 1, 2, 3, 4 2, 3, 4 3, 4 W(t, ) =t1t2工作集的變化 進程開始執(zhí)行后，隨著訪問新頁面逐步建立較穩(wěn)定的工作集 當內(nèi)存訪問的局部性區(qū)域的位置大致穩(wěn)定時，工作集大小也大致穩(wěn)定 局部性區(qū)域的位置改變時，工作集快速擴張和收縮過渡到下一個穩(wěn)定值 工作集大小過渡階段穩(wěn)定階段時間常駐集在當前時刻，進程實際駐留在內(nèi)存當中的頁面集合工作集與常駐集的關(guān)系工作集是進程在運行過程中固有的性質(zhì)常駐集取決于系統(tǒng)分配給進程的物理頁面數(shù)目和頁面置換算法缺頁率與常駐集的關(guān)系常駐集

22、 工作集時，缺頁較少工作集發(fā)生劇烈變動（過渡）時，缺頁較多進程常駐集大小達到一定數(shù)目后，缺頁率也不會明顯下降工作集置換算法當前時刻前個內(nèi)存訪問的頁引用是工作集，被稱為窗口大小窗口大小 實現(xiàn)方法訪存鏈表：維護窗口內(nèi)的訪存頁面鏈表訪存時，換出不在工作集的頁面；更新訪存鏈表缺頁時，換入頁面；更新訪存鏈表 思路 換出不在工作集中的頁面工作集置換算法109876543210時間訪問頁面缺頁狀態(tài)daececbdcc頁面a頁面b頁面d頁面e頁面c邏輯面頁狀態(tài)t=0t=-1t=-2 = 4提綱頁面置換算法的概念 全局頁面置換算法工作集置換算法缺頁率置換算法局部頁面置換算法抖動和負載控制缺頁率(page fault rate)缺頁次數(shù) / 內(nèi)存訪問次數(shù) 或 缺頁平均時間間隔的倒數(shù)頁面置換算法 影響缺頁率的因素分配給進程的物理頁面數(shù)目頁面大小程序的編寫方法缺頁率置換算法（PFF