第12講 虛擬存儲(chǔ)：置換算法

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

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

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

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

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

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

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

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

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

10、ebadcadbebabcdcadb0000abcd0010abcd1010abcd1011abcd1111abcd0111abcd0011abcd0001abcd0000abcd0000abcd0a1e1000ebcdebcd1100ebcdb1000ebcd1000ebcd0 c1010ebad1110ebadebadb0 d1111ebac0111ebacebacdbac0011ebac0001ebac0000ebac0000ebac0e1000dbac1000ebcd1010ebad1111ebac改進(jìn)的Clock算法駐留位訪問(wèn)位修改位幀號(hào)0頁(yè)號(hào)7:150頁(yè)號(hào)1:130頁(yè)號(hào) 4:14頁(yè)

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

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

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

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

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

16、54321543215432FIFO算法有Belady現(xiàn)象LRU算法沒(méi)有Belady 現(xiàn)象物理頁(yè)面數(shù): 3物理頁(yè)面數(shù): 4時(shí)鐘/改進(jìn)的時(shí)鐘頁(yè)面置換是否有Belady現(xiàn)象？為什么LRU頁(yè)面置換算法沒(méi)有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缺頁(yè)次數(shù): 10缺頁(yè)次數(shù): 8LRU、FIFO和Clock的比較例如：給進(jìn)程分配3個(gè)物理頁(yè)面，邏輯頁(yè)面的訪問(wèn)順序?yàn)?、2、3、4、5、6、1、2、3如頁(yè)面進(jìn)入內(nèi)存后沒(méi)有被訪問(wèn)，最近訪問(wèn)時(shí)間與進(jìn)入內(nèi)存的時(shí)間相同F(xiàn)IFO依據(jù)頁(yè)面進(jìn)入內(nèi)存的時(shí)間排序LRU需要?jiǎng)討B(tài)地調(diào)整順序LRU依據(jù)頁(yè)面的最近訪問(wèn)時(shí)間排序LRU可退化成FIFOLRU算法和FIFO本質(zhì)上都是先進(jìn)先出的思路FIFO的頁(yè)面進(jìn)入時(shí)間是固定不變的LRU、FIFO和Clock的比較缺頁(yè)時(shí)，再把它移動(dòng)到鏈表末尾頁(yè)面訪問(wèn)時(shí)，不動(dòng)態(tài)調(diào)整頁(yè)面在鏈表中的順序，僅做標(biāo)記對(duì)于未被訪問(wèn)的頁(yè)面，Clock和LRU算法的表現(xiàn)一樣好LRU算法性能較好，但系統(tǒng)開(kāi)銷較

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

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

20、函數(shù)W(t, )t是當(dāng)前的執(zhí)行時(shí)刻 稱為工作集窗口（working-set window ），即一個(gè)定長(zhǎng)的頁(yè)面訪問(wèn)時(shí)間窗口W(t, )是指在當(dāng)前時(shí)刻 t 前的 時(shí)間窗口中的所有訪問(wèn)頁(yè)面所組成的集合| W(t, ) | 指工作集的大小，即頁(yè)面數(shù)目進(jìn)程的工作集示例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 頁(yè)面訪問(wèn)順序：如果 時(shí)間窗口的長(zhǎng)度為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工作集的變化 進(jìn)程開(kāi)始執(zhí)行后，隨著訪問(wèn)新頁(yè)面逐步建立較穩(wěn)定的工作集 當(dāng)內(nèi)存訪問(wèn)的局部性區(qū)域的位置大致穩(wěn)定時(shí)，工作集大小也大致穩(wěn)定 局部性區(qū)域的位置改變時(shí)，工作集快速擴(kuò)張和收縮過(guò)渡到下一個(gè)穩(wěn)定值 工作集大小過(guò)渡階段穩(wěn)定階段時(shí)間常駐集在當(dāng)前時(shí)刻，進(jìn)程實(shí)際駐留在內(nèi)存當(dāng)中的頁(yè)面集合工作集與常駐集的關(guān)系工作集是進(jìn)程在運(yùn)行過(guò)程中固有的性質(zhì)常駐集取決于系統(tǒng)分配給進(jìn)程的物理頁(yè)面數(shù)目和頁(yè)面置換算法缺頁(yè)率與常駐集的關(guān)系常駐集

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