前言

??上文說到糖赔，請求分頁管理方式中慌洪，當(dāng)需要調(diào)入頁面到內(nèi)存中，但此時內(nèi)存已滿庇麦，就需要從內(nèi)存中按照一定的置換算法決定將哪個頁面取出將內(nèi)存給調(diào)入的頁面。本文將介紹幾種頁面置換算方法喜德。
??本文內(nèi)容

1 最佳置換算法（OPT山橄，Optimal）

??算法思想：每次選擇淘汰的頁面將是以后永不使用，或者在最長時間內(nèi)不再被訪問的頁面舍悯，這樣可以保證最低的缺頁率航棱。
??舉例說明，假設(shè)系統(tǒng)為進(jìn)程分配了三個內(nèi)存塊萌衬，并考慮到有以下頁面號引用串（會依次訪問這些頁面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

第一個訪問的是7號頁饮醇，內(nèi)存中沒有此頁，由缺頁中斷機(jī)構(gòu)將7號頁調(diào)入內(nèi)存秕豫。此時有三個可用的內(nèi)存塊朴艰，不需要置換。即第一次(7) ：7

同理馁蒂，第二個訪問的是0號頁呵晚，和第一次一樣，第三次訪問的是1號頁沫屡，同樣1號頁也會被調(diào)入內(nèi)存饵隙，1號內(nèi)被調(diào)入內(nèi)存后，此時分配給該進(jìn)程內(nèi)存空間已占滿沮脖。
第二次(0)：7 0
第三次(1)：7 0 1

第四個訪問的頁是2號頁金矛，此時內(nèi)存已經(jīng)用完芯急，需要將一個頁調(diào)出內(nèi)存，根據(jù)最佳置換算法驶俊，淘汰一個以后永不使用或最長時間不使用的娶耍，此時內(nèi)存中的頁有7、0饼酿、1榕酒，查看待訪問頁號序列中這三個頁號的先后位置，下圖可以看到故俐，0號頁和1號頁在不久又會被訪問到想鹰，而7號頁需要被訪問的時間最久。所以該算法會淘汰7號頁药版。

第一次(7) ：7
第二次(0)：7 0
第三次(1)：7 0 1
第四次(2)：0 1 2

??....按照此算法依次執(zhí)行辑舷，最后的結(jié)果如下

第一次(7) ：7
第二次(0)：7 0
第三次(1)：7 0 1
第四次(2)：0 1 2
第五次(0)：0 1 2（命中）
第六次(3) ：0 3 1
第七次(0) ：0 3 1（命中）
第八次(4) ：3 2 4
第九次(2) ：3 2 4（命中）
第十次(3) ：3 2 4（命中）
第十一次(0) ：3 2 0
第十二次(3) ：3 2 0（命中）
.....

??結(jié)果圖

??整個過程缺頁中斷發(fā)生了9次，頁面置換發(fā)生了6次槽片。缺頁率 = 9 / 20 = 45%何缓。

??注：缺頁時未必發(fā)生頁面置換，若還有可用的空閑內(nèi)存空間就不用進(jìn)行頁面置換还栓。
??最佳置換算法可以保證最低的缺頁率碌廓，但是實際上，只有進(jìn)程執(zhí)行的過程中才能知道接下來會訪問到的是哪個頁面蝙云。操作系統(tǒng)無法提前預(yù)判頁面的訪問序列氓皱。因此，最佳置換算法是無法實現(xiàn)的勃刨。

2 先進(jìn)先出置換算法（FIFO）

??算法思想：每次選擇淘汰的頁面是最早進(jìn)入內(nèi)存的頁面波材。
??該算法很簡單，每次淘汰最在內(nèi)存中待時間最久的各個身隐，下面分別給出系統(tǒng)為進(jìn)程分為配三個內(nèi)存塊和四個內(nèi)存塊的執(zhí)行情況圖廷区。訪問序列為3,2,1,0,3,2,4,3,2,1,0,4
??分配三個內(nèi)存塊的情況：

第一次(3) ：3
第二次(2) ：3 2
第三次(1) ：3 2 1
第四次(0) ：2 1 0
第五次(3) ：1 0 3
第六次(2) ：0 3 2
第七次(4) ：3 2 4
第八次(3) ：3 2 4（命中）
第九次(2) ：3 2 4（命中）
第十次(1) ：2 4 1
第十一次(0) ：4 1 0
第十二次(4) ：4 1 0（命中）

??分配三個內(nèi)存塊時，缺頁次數(shù)：9次贾铝。

??分配四個內(nèi)存塊的情況：

第一次(3) ：3
第二次(2) ：3 2
第三次(1) ：3 2 1
第四次(0) ：3 2 1 0
第五次(3) ：3 2 1 0（命中）
第六次(2) ：3 2 1 0 （命中）
第七次(4) ：2 1 0 4
第八次(3) ：1 0 4 3
第九次(2) ：0 4 3 2
第十次(1) ：4 3 2 1
第十一次(0) ：3 2 1 0
第十二次(4) ：2 1 0 4

??分配四個內(nèi)存塊時隙轻，缺頁次數(shù)：10次。

??當(dāng)為進(jìn)程分配的物理塊數(shù)增大時垢揩，缺頁次數(shù)不減反增的異尘谅蹋現(xiàn)象稱為貝萊迪（Belay）異常。
??只有FIFO算法會產(chǎn)生Belay異常叁巨。另外斑匪，F(xiàn)IFO算法雖然實現(xiàn)簡單，但是該算法與進(jìn)程實際運(yùn)行時的規(guī)律不適應(yīng)锋勺。因為先進(jìn)入的頁面也有可能最經(jīng)常被訪問蚀瘸。因此狡蝶，算法性能差。

3 最近最久未使用置換算法（LRU贮勃，Least Recently Used）

??算法思想：每次淘汰的頁面是最近最久未使用的頁面贪惹。
??實現(xiàn)方法：賦予每個頁面對應(yīng)的頁表項中，用訪問字段記錄該頁面自上次被訪問以來所經(jīng)歷的時間t寂嘉。當(dāng)需要淘汰一個頁面時奏瞬，選擇現(xiàn)有頁面中t最大的頁面，即最近最久未使用垫释。

??舉例說明丝格，加入某系統(tǒng)為某進(jìn)程分配了四個內(nèi)存塊，并考慮到有以下頁面號引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
??這里先直接給出答案

第一次(1) ：1
第二次(8) ：1 8
第三次(1) ：8 1 （命中）（由于1號頁又被訪問過了棵譬，所以放到最后）
第四次(7) ：8 1 7
第五次(8) ：1 7 8（命中）
第六次(2) ：1 7 8 2
第七次(7) ：1 8 2 7（命中）
第八次(2) ：1 8 7 2（命中）
第九次(1) ：8 7 2 1（命中）
第十次(8) ：7 2 1 8（命中）
第十一次(3) ：2 1 8 3
第十二次(8) ：2 1 3 8（命中）
第十三次(2) ：1 3 8 2（命中）
第十四次(1) ：3 8 2 1（命中）
第十五次(3) ：8 2 1 3（命中）
第十六次(1) ：8 2 3 1（命中）
第十七次(7) ：2 3 1 7
....

這里前10次都1、8预伺、7订咸、2這四個頁，四個內(nèi)存塊號正好可以滿足酬诀，當(dāng)?shù)?1次要訪問的3號頁進(jìn)入內(nèi)存時脏嚷，需要從1、8瞒御、7父叙、2這四個頁淘汰一個頁，按照該算法肴裙，從頁號為3的開始趾唱，從右往左一次找到這4個頁第一次出現(xiàn)的地方，在最左邊的就是最近最少使用的頁蜻懦。如下圖所示甜癞，所以該算法最終淘汰的是7號頁。同時直接從第十次的訪問結(jié)果 7 2 1 8也可以直接看出宛乃，7號頁在最前面悠咱，是最久沒有被訪問過的，所以淘汰應(yīng)該是7號頁征炼。

??結(jié)果圖

4 時鐘置換算法

??最佳置換算法那性能最好析既，但無法實現(xiàn)。先進(jìn)先出置換算法實現(xiàn)簡單谆奥，但是算法性能差眼坏。最近最久未使用置換算法性能好，是最接近OPT算法性能的雄右，但是實現(xiàn)起來需要專門的硬件支持空骚，算法開銷大纺讲。時鐘置換算法是一種性能和開銷均平衡的算法。又稱CLOCK算法囤屹，或最近未用算法（NRU熬甚，Not Recently Used）
??簡單CLOCK算法算法思想：為每個頁面設(shè)置一個訪問位，再將內(nèi)存中的頁面都通過鏈接指針鏈接成一個循環(huán)隊列肋坚。當(dāng)某個頁被訪問時乡括，其訪問位置1.當(dāng)需要淘汰一個頁面時，只需檢查頁的訪問位智厌。如果是0诲泌，就選擇該頁換出；如果是1铣鹏，暫不換出敷扫，將訪問位改為0，繼續(xù)檢查下一個頁面诚卸，若第一輪掃描中所有的頁面都是1葵第，則將這些頁面的訪問位一次置為0后，再進(jìn)行第二輪掃描（第二輪掃描中一定會有訪問位為0的頁面合溺，因此簡單的CLOCK算法選擇一個淘汰頁面最多會經(jīng)過兩輪掃描）卒密。

此時頁面6需要進(jìn)入內(nèi)存睛约，那么需要從中淘汰一個頁面鼎俘，于是從循環(huán)隊列的隊首（1號頁）開始掃描，嘗試找到訪問位為0的頁面痰腮。經(jīng)過一輪掃描發(fā)現(xiàn)所有的訪問位都是1而芥，經(jīng)過一輪掃描后，需要將所有的頁面標(biāo)志位設(shè)置為0膀值，如下圖

之后進(jìn)行第二輪掃描棍丐，發(fā)現(xiàn)1號頁的訪問位為0，所以換出1號頁沧踏，同時指針指向下一頁歌逢，如下圖

接下來是訪問3號頁和4號頁，這兩個頁都在內(nèi)存中翘狱，直接訪問秘案，并將訪問位改為1。在訪問3號頁和4號頁時指針不需要動，指針只有在缺頁置換時才移動下一頁阱高。如下圖

最后赚导，訪問7號頁，此時從3號頁開始掃描循環(huán)隊列赤惊，掃描過程中將訪問位為1的頁的訪問位改為0吼旧，并找到第一個訪問位為0的頁，即2號頁未舟，將2號頁置換為7號頁圈暗，最后將指針指向7號頁的下一頁，即5號頁裕膀。如下圖

??這個算法指針在掃描的過程就像時鐘一樣轉(zhuǎn)圈员串，才被稱為時鐘置換算法。

5 改進(jìn)型的時鐘置換算法

??簡單的時鐘置換算法僅考慮到了一個頁面最近是否被訪問過昼扛。事實上寸齐，如果淘汰的頁面沒有被修改過，就不需要執(zhí)行I/O操作寫回外存野揪。只有淘汰的頁面被修改過時访忿，才需要寫回外存。
??因此斯稳，除了考慮一個頁面最近有沒有被訪問過之外，操作系統(tǒng)還需要考慮頁面有沒有被修改過迹恐。
??改進(jìn)型時鐘置換算法的算法思想：在其他在條件相同時挣惰，應(yīng)該優(yōu)先淘汰沒有被修改過的頁面，從而來避免I/O操作殴边。
??為了方便討論憎茂，用（訪問位，修改位）的形式表示各頁面的狀態(tài)锤岸。如（1,1）表示一個頁面近期被訪問過竖幔，且被修改過。
??算法規(guī)則：將所有可能被置換的頁面排成一個循環(huán)隊列

第一輪：從當(dāng)前位置開始掃描第一個（0,0）的頁用于替換是偷，本輪掃描不修改任何標(biāo)志位拳氢。
第二輪：若第一輪掃描失敗，則重新掃描蛋铆，查找第一個（0,1）的頁用于替換馋评。本輪將所有掃描的過的頁訪問位設(shè)為0。
第三輪：若第二輪掃描失敗刺啦，則重新掃描留特，查找第一個（0,0）的頁用于替換。本輪掃描不修改任何標(biāo)志位。
第四輪：若第三輪掃描失敗蜕青，則重新掃描苟蹈，查找第一個（0,1）的頁用于替換。

??由于第二輪已將所有的頁的訪問位都設(shè)為0右核，因此第三輪慧脱、第四輪掃描一定會選中一個頁，因此改進(jìn)型CLOCK置換算法最多會進(jìn)行四輪掃描蒙兰。

?? 5.1 第一輪就找到替換的頁的情況

??假設(shè)系統(tǒng)為進(jìn)程分配了5個內(nèi)存塊磷瘤，某時刻，各個頁的狀態(tài)如下圖

??如果此時有新的頁要進(jìn)入內(nèi)存搜变，開始第一輪掃描就找到了要替換的頁采缚，即最下面的狀態(tài)為（0,0）的頁。

?? 5.2 第二輪就找到替換的頁的情況

??某一時刻頁面狀態(tài)如下

??如果此時有新的頁要進(jìn)入內(nèi)存挠他，開始第一輪掃描就發(fā)現(xiàn)沒有狀態(tài)為（0扳抽，0）的頁，第一輪掃描后不修改任何標(biāo)志位殖侵。所以各個頁狀態(tài)和上圖一樣贸呢。
??然后開始第二輪掃描，嘗試找到狀態(tài)為（0,1）的頁拢军，并將掃描過后的頁的訪問位設(shè)為0楞陷，第二輪掃描找到了要替換的頁。

?? 5.3 第三輪就找到替換的頁的情況

??某一時刻頁面狀態(tài)如下

??第一輪掃描沒有找到狀態(tài)為（0,0）的頁茉唉，且第一輪掃描不修改任何標(biāo)志位固蛾，所以第一輪掃描后狀態(tài)和上圖一致。
??然后開始第二輪掃描度陆，嘗試找狀態(tài)為（0,1）的頁艾凯，也沒有找到，第二輪掃描需要將訪問位設(shè)為1懂傀，第二輪掃描后趾诗，狀態(tài)為下圖

?? 5.4 第四輪就找到替換的頁的情況

??某一時刻頁面狀態(tài)如下

??具體的掃描過程和上面相同悟泵，這里只給出最后的結(jié)果，如下圖

??所以闪水，改進(jìn)型的CLOCK置換算法最多需要四輪掃描確定要置換的頁糕非。從上面的分析可以看出蒙具，改進(jìn)型的CLOCK置換算法
??(1) 第一優(yōu)先級淘汰的是最近沒有訪問且沒有修改的頁面。
??(2) 第二優(yōu)先級淘汰的是最近沒有訪問但修改的頁面朽肥。
??(3) 第三優(yōu)先級淘汰的是最近訪問但沒有修改的頁面禁筏。
??(4) 第四優(yōu)先級淘汰的是最近訪問且修改的頁面。

第三衡招、四優(yōu)先級為什么是訪問過的篱昔？因為如果到了第三輪掃描，所有頁的訪問位都在第二輪掃描被設(shè)置為了0始腾，如果訪問位不是0的話州刽，也達(dá)到不了第三輪掃描，前兩輪就會被淘汰浪箭。所以到了第三輪穗椅，第四輪淘汰的頁都是最近被訪問過的。

6 小結(jié)

??本文完