15存儲管理4虛擬存儲請求頁式管理1(已改無錯字)
2023-03-17 02:15:52 本頁面
【正文】 可能引起 異常 。59先進先出置換算法的一個異常現(xiàn)象：對于一些特定的頁面訪問序列，先進先出置換算法有隨著分給的頁架數(shù)增加，缺頁頻率也增加的異?，F(xiàn)象。A B C D A B E E E C D D A B C D A B B B E C C A B C D A A A B E E+ + + + + + + + + 頁面訪問序列 A B C D A B E A B C D E九次缺頁三個頁面A B C D D D E A B C D E A B C C C D E A B C D A B B B C D E A B C A A A B C D E A B+ + + + + + + + + + 頁面訪問序列 十次缺頁四個頁面60 最近最久未使用最近最久未使用 LRU置換算法置換算法 LRU（ Least Recently Used）算法的描述 基本思想：基于程序的 局部性原理 ，在前面幾條指令中使用頻繁的頁面很可能在后面的幾條指令中頻繁使用，反之， 已經(jīng)很久沒有使用的頁面很有可能在未來較長一段時間內(nèi)不會使用 ；因此，在缺頁發(fā)生時，淘汰掉 最久未使用 的頁；選擇淘汰的頁面是最近最久未使用61 我們用 “最近的過去 ”來直接推斷 “最近的將來 ”。 770700711 21200 3 002340432024324300322 132132012011 7 01017發(fā)生了 9次頁面置換。 標(biāo)明訪問時間 1 2 3 4 5 6 7 8 9 1011121314151617181920237 0 1 2 0 3 0 4 2 3 0 3 12 2 0 1 1 7 1062 LRU算法的硬件支持為了實現(xiàn) LRU算法必須解決： （ 1）一個進程在內(nèi)存中的各個頁面 各有多久時間未被進程訪問； （ 2）如何快速地知道哪一頁是 最近最久 未使用的頁面。 63寄存器 為每個在內(nèi)存中的頁面配置一個 移位寄存器，表示為： R=Rn1Rn2Rn3…R 1R2R0 當(dāng)進程訪問某物理塊時，要將相應(yīng)的寄存器的Rn1位置為 1。 定時信號將每隔一定時間將寄存器 右移一次 ，把 n位寄存器的數(shù)看作是一個無符號的整數(shù)，最近最久未使用的頁面就對應(yīng)著具有最小數(shù)值的寄存器 。用于記錄某進程在內(nèi)存中各頁的使用情況。64棧 LRU置換算法可用堆棧的方法來實現(xiàn)。 棧中存放當(dāng)前內(nèi)存中的頁面號，每當(dāng)訪問一頁時就調(diào)整一次堆棧，總是 使最近訪問的那頁的頁面號保持在棧頂 ，然后根據(jù)當(dāng)前被訪問時間的近遠，依次排列， 棧底 總是最近最久未使用的那頁的頁面號。 淘汰651 121231234 214312431 2 3 4 2 1 5 6 2 1 2 3 7 65124125612561256126512631327 6327作業(yè)固定占用 4塊主存 例如，某作業(yè)按下列頁號訪問： 66 作作 業(yè)業(yè) 某程序在內(nèi)存中分配三個頁面，初始為空，頁面走向為 4， 3， 2， 1， 4， 3， 5， 4， 3， 2， 1， 5。請分別用 FIFO,LRU和 OPT算法計算缺頁中斷次數(shù)。67 CLock置換算法置換算法 CLock算法就是用得較多的一種 LRU近似算法。 68簡單的、簡單的 CLock置換算法置換算法 這種算法的實質(zhì)是：當(dāng)需要置換一頁時，選擇在最近一段時間內(nèi) 最久未用 的頁予以淘汰，因此稱為 最近未用 的算法 NRU（Not Recently Used）。69 這種近似算法，要求為每一頁設(shè)置一位訪問位，再將內(nèi)存中的所有頁面都通過指針按 FIFO鏈成一個循環(huán)隊列。 當(dāng)某頁被訪問時，訪問位由硬件自動置 “1”。我們可以根據(jù)訪問位的狀態(tài)來判斷各個頁面最近使用的情況。如果是 “0”，就選擇該頁換出；若為 1，則重新將它置為 0，再按照 FIFO算法檢查下一個頁面。 該算法是對 FIFO算法的改進，考慮到頁面是否被訪問。70塊號 頁號 訪問位 指針012 4 034 2 156 5 07 1 1替換指針總是指向最近被替換的頁所在的存儲塊，缺頁時從其后一塊開始。71改進型、改進型 CLock置換算法置換算法 1類 （ A=0， M=0），最近既未被訪問，又未被修改，是 最佳淘汰頁 。 2類 （ A=0， M=1），最近未被訪問，但已被修改，不是很好的淘汰頁。 3類 （ A=1， M=0），最近已被訪問，但未被修改，可能再被訪問。 既要考慮到頁面的使用情況，還要考慮置換代價 4類 （ A=1，
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1