【正文】 引起的。 ? 什么是抖動？當(dāng)需要將一個新頁面調(diào)入內(nèi)存時，因內(nèi)存空間緊張，不得不將一個老頁面置換出去，而剛剛置換出去的老頁面可能又要被使用，需要重新將它調(diào)入。若一個進(jìn)程頻繁地進(jìn)行頁面調(diào)入調(diào)出，使系統(tǒng)效率降低，通常稱這種現(xiàn)象為該進(jìn)程發(fā)生了抖動。 ? 產(chǎn)生抖動的原因： ? 系統(tǒng)內(nèi)的進(jìn)程數(shù)太多，致使一個進(jìn)程分得的內(nèi)存塊過少； ? 系統(tǒng)采用的頁面置換算法不合理。 ? 頁面置換算法的目標(biāo)： ? 最小化頁面更換頻率或缺頁率 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 68 置換策略 ? 頁面置換策略也可用于段置換、 TLB置換 ? 置換策略的分類 ?最優(yōu)置換策略（ OPT） ? 無法實(shí)現(xiàn)的最優(yōu)策略 ?先進(jìn)先出策略（ FIFO） ? 最直觀也是效果最差的策略 ?最近最舊未使用策略（ LRU） ? 可行的最優(yōu)策略，但硬件代價高 ?時鐘策略（ CLOCK） ? LRU的簡化版本 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 69 最優(yōu)置換策略（ OPT） ? 選擇未來最長時間內(nèi)不再使用的頁面來置換 ? 理論上缺頁率最低的算法 ? 需要 OS能預(yù)知將來需要讀取的頁面，因而該算法基本不可能實(shí)現(xiàn) ? 作用是最為標(biāo)準(zhǔn)來衡量其它算法的性能 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 70 【 例 】 假定系統(tǒng)為某進(jìn)程分配了 3個頁框， 并考慮以下的頁面引用串 ： 7， 0， 1， 2， 0， 3， 0， 4， 2， 3， 0， 3， 2， 1， 2， 0， 1， 7， 0， 1 引用串 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 1 1 1 0 0 0 0 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7 √ √ √ √ √ √ √ √ √ 發(fā)生缺頁頁框 共發(fā)生了 9次缺頁中斷，其中 6次 有 頁面 置換 先進(jìn)先出策略（ FIFO） ? 先進(jìn)入內(nèi)存的頁，先退出內(nèi)存。 ? 實(shí)質(zhì)上是淘汰在內(nèi)存駐留時間最長的頁。 ? 其理由是：最早調(diào)入內(nèi)存的頁，不再被使用的可能性比近期調(diào)入內(nèi)存的大。 ? 實(shí)現(xiàn)：內(nèi)存中頁面按先后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。 ? 特點(diǎn)：這種算法簡單，實(shí)現(xiàn)容易。問題是有些頁面經(jīng)常會被訪問，可能先被淘汰。 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 71 引用串 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 1 0 7 2 2 2 1 0 0 0 3 2 4 0 3 2 2 1 0 7 2 1 1 1 0 3 3 3 2 4 0 3 2 1 1 0 0 7 2 1 0 0 0 3 2 2 2 4 0 3 2 1 0 0 7 7 7 √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ 發(fā)生缺頁 頁框 最近最久未使用策略（ LRU） ? LRU(Least Recently Used)：選擇最近最久未使用的頁面進(jìn)行淘汰 ? 用 ―最近的過去 ‖作為 ―最近的將來 ‖的近似 ? 這種算法需要對每一頁的使用情況跟蹤記錄，系統(tǒng)開銷較大 ? LRU頁面置換算法的演算過程可以借助 ―棧 ‖來完成：棧頂始終是最新的，棧底是最近最久未使用的頁面號。 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 72 引用串 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 1 0 2 1 3 3 0 2 2 4 0 3 2 2 1 1 7 0 7 1 0 2 1 2 3 0 3 2 4 0 3 0 2 0 0 7 1 0 7 1 0 2 1 2 3 0 3 2 4 0 3 0 2 1 0 7 發(fā)生缺頁 頁框 √ √ √ √ √ √ √ √ √ √ √ √ LRU的問題 ? LRU在理論上是可以實(shí)現(xiàn)的，但代價太高。 ? 為了實(shí)現(xiàn) LRU，需要維護(hù)一個特殊的隊列，該隊列中存放當(dāng)前在內(nèi)存中的頁號，每訪問一頁時就調(diào)整一次隊列，使最近訪問的頁面在表尾，最近最少使用的頁面在表頭。發(fā)生缺頁中斷時，總是淘汰隊頭的頁；而執(zhí)行一次頁面訪問，需要將該頁調(diào)整到隊尾。在鏈表中找到被訪問的頁，將它移到表尾是一個非常費(fèi)時的操作，即使用硬件實(shí)現(xiàn)也是一樣 (假設(shè)有這樣的硬件的話 )。 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 73 時鐘策略（ CLOCK） ? 簡單的 Clock置換算法 ?引入： LRU算法有較多的硬件支持，成本高 ?當(dāng)采用簡單的 Clock算法時，只需為每頁設(shè)置一位訪問位，再將內(nèi)存中的所有頁面都通過鏈接指針鏈接成一個循環(huán)隊列 ?當(dāng)某頁被訪問時，其訪問位被置 1 ?置換算法在選擇一頁淘汰時，只需檢查頁的訪問位 ?由于該算法是循環(huán)地檢查各頁面的訪問情況，故稱為Clock算法，又稱為最近未用算法 NRU(Not Recently Used) USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 74 時鐘策略（ CLOCK） USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 75 A B C D E F G H I J K H ? 當(dāng)發(fā)生缺頁中斷時 ， 首先檢查指針?biāo)傅捻撁?， 若它的 A位是 0就淘汰該頁面 ， 并把新頁面插入這個位置， 指針前移一個位置到 C頁； ? 若 A位是 1， 就清除 A位 ， 并把指針前移一個位置；重復(fù)這個過程 ， 直到找到一個 A位是 0的頁面為止 。 引用串 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 1* 2 2 2* 2* 2* 0 0* 0* 0* 3* 3 3 3* 3* 1 1 1* 7* 7* 7* 1* 1* 1* 1* 2* 2 2 2* 2* 0 0* 0 0* 0 0* 0* 0* 0* 0 0* 0* 3 3 3* 3* 4 4* 4* 4* 2* 2* 2* 2* 7* 7* 7* 發(fā)生缺頁 頁框 藍(lán)色 為指針位置， *為訪問標(biāo)志 √ √ √ √ √ √ √ √ √ √ √ √ √ √ 改進(jìn)型 Clock置換算法 ? 淘汰被修改過的頁面時，需將其寫回磁盤 (置換代價高 )，因此應(yīng)淘汰既未被訪問又未被修改的頁面。為此，每個頁面除了有訪問位 A外，還增加一個修改位 M。 ? 由訪問位 A與修改位 M可以組成下面 4種類型的頁面： ? 1類 (A=0,M=0) ? 表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁 ? 2類 (A=0,M=1) ? 該頁最近未被訪問，但已被修改，并不是很好的淘汰頁 ? 3類 (A=1,M=0) ? 最近已被訪問，但未被修改，該頁有可能再被訪問 ? 4類 (A=1,M=1) ? 最近被訪問且被修改過的頁，最不應(yīng)該淘汰。 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 76 改進(jìn)型 Clock置換算法 ? 其執(zhí)行過程可分成以下三步： ? 第一步：從指針?biāo)甘镜漠?dāng)前位置開始，掃描循環(huán)隊列，尋找A=0且 M=0的第一類頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位 A ? 第二步：如果第一步失敗，即查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找 A=0且 M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置 0 ? 第三步：如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復(fù) 0。然后重復(fù)第一步，如果仍失敗，必要時再重復(fù)第二步，此時就一定能找到被淘汰的頁 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 77 Performance Comparison ? Comparison of FixedAllocation, Local Page Replacement Algorithms USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 78 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 79 After the class… ? Reading: ? 教材第 7章：內(nèi)存管理（ ） ? 教材第 8章：虛擬內(nèi)存（ ） ? Homework ? P333: Problems , , (7th Edition) ? P391: Problems , , (7th Edition)