模拟请求分页式存储管理 ---4种置换算法
請(qǐng)求調(diào)頁(yè)+頁(yè)面置換
1.虛擬存儲(chǔ)系統(tǒng)
操作系統(tǒng)中，為了提高內(nèi)存利用率，提供了內(nèi)外存進(jìn)程對(duì)換機(jī)制；內(nèi)存空間的分配和回收均以頁(yè)為單位進(jìn)行；一個(gè)進(jìn)程只需將其一部分（段或頁(yè)）調(diào)入內(nèi)存便可運(yùn)行；還支持請(qǐng)求調(diào)頁(yè)的存儲(chǔ)管理方式。
當(dāng)進(jìn)程在運(yùn)行中需要訪問(wèn)某部分程序和數(shù)據(jù)時(shí)，發(fā)現(xiàn)其所在頁(yè)面不在內(nèi)存，就立即提出請(qǐng)求（向CPU發(fā)出缺中斷），由系統(tǒng)將其所需頁(yè)面調(diào)入內(nèi)存。這種頁(yè)面調(diào)入方式叫請(qǐng)求調(diào)頁(yè)。
?
2. 頁(yè)面置換過(guò)程
當(dāng)CPU接收到缺頁(yè)中斷信號(hào)，中斷處理程序先保存現(xiàn)場(chǎng)，分析中斷原因，轉(zhuǎn)入缺頁(yè)中斷處理程序。該程序通過(guò)查找頁(yè)表，得到該頁(yè)所在外存的物理塊號(hào)。如果此時(shí)內(nèi)存未滿，能容納新頁(yè)，則啟動(dòng)磁盤I/O將所缺之頁(yè)調(diào)入內(nèi)存，然后修改頁(yè)表。如果內(nèi)存已滿，則須按某種置換算法從內(nèi)存中選出一頁(yè)準(zhǔn)備換出，是否重新寫盤由頁(yè)表的修改位決定，然后將缺頁(yè)調(diào)入，修改頁(yè)表。利用修改后的頁(yè)表，去形成所要訪問(wèn)數(shù)據(jù)的物理地址，再去訪問(wèn)內(nèi)存數(shù)據(jù)。整個(gè)頁(yè)面的調(diào)入過(guò)程對(duì)用戶是透明的。
?
(1)?? 頁(yè)表：放在系統(tǒng)空間的頁(yè)表區(qū)，存放邏輯頁(yè)與物理頁(yè)幀的對(duì)應(yīng)關(guān)系。 每一個(gè)進(jìn)程都擁有一個(gè)自己的頁(yè)表，PCB表中有指針指向頁(yè)表。
(2)?? 頁(yè)框：RAM塊，來(lái)描述物理內(nèi)存空間，由操作系統(tǒng)實(shí)現(xiàn)從邏輯頁(yè)到物理頁(yè)框的頁(yè)面映射，同時(shí)負(fù)責(zé)對(duì)所有頁(yè)的管理和進(jìn)程運(yùn)行的控制。模擬時(shí)對(duì)于頁(yè)框的分配數(shù)量自主設(shè)定。
(3)?? 訪問(wèn)位：不論是讀還是寫（get or set），系統(tǒng)都會(huì)設(shè)置該頁(yè)的訪問(wèn)位，記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)，或最近已有多長(zhǎng)時(shí)間未被訪問(wèn)，它的值用來(lái)幫助操作系統(tǒng)在發(fā)生缺頁(yè)中斷時(shí)選擇要被淘汰的頁(yè)，即用于頁(yè)面置換。
(4)?? 修改位（臟位）：用于頁(yè)面的換出，如果某個(gè)頁(yè)面被修改過(guò)（即為臟），在淘汰該頁(yè)時(shí)，必須將其寫回磁盤，反之，可以直接丟棄該頁(yè)。
(5) 有效位（駐留位、中斷位）：表示該頁(yè)是內(nèi)存還是磁盤。
(6) 保護(hù)位：存取控制位，用于指出該頁(yè)允許什么類型的訪問(wèn)，如果用一位來(lái)標(biāo)識(shí)的話：1表示只讀，0表示讀寫。
?
1.LRU
least recently used 最近時(shí)間內(nèi) 最久未被使用的頁(yè)面被置換
如果一個(gè)數(shù)據(jù)在最近一段時(shí)間沒(méi)有被訪問(wèn)到，那么在將來(lái)它被訪問(wèn)的可能性也很小,拿“最近的過(guò)去”預(yù)測(cè)“最近的未來(lái)”。
LRU算法的硬件支持
LRU算法雖然是一種比較好的算法，但是要求系統(tǒng)有較多的支持硬件。為了了解一個(gè)進(jìn)程在內(nèi)存中的各個(gè)頁(yè)面各有多少時(shí)間未被進(jìn)程訪問(wèn)，以及如何快速得知道哪一頁(yè)是最近最久未使用的頁(yè)面，須有寄存器和棧兩類硬件之一的支持。?
1）寄存器?
為了記錄某進(jìn)程在內(nèi)存中各頁(yè)的使用情況，須為每個(gè)內(nèi)存中的頁(yè)面配置一個(gè)移位寄存器，可表示為?
當(dāng)進(jìn)程訪問(wèn)某物理塊時(shí)，要將相應(yīng)的寄存器的Rn?1位置成1。此時(shí)，定時(shí)信號(hào)將每隔一定時(shí)間將寄存器右移一位。如果我們把n位寄存器的數(shù)看作是一個(gè)整數(shù)，那么，具有最小數(shù)值的寄存器所對(duì)應(yīng)的頁(yè)面，就是最近最久未使用的頁(yè)面。 （e.g. 每100ms右移一位，最高位補(bǔ)0還是補(bǔ)1的問(wèn)題）
2）棧?
可利用一個(gè)特殊的棧保持當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)。每當(dāng)進(jìn)程訪問(wèn)某頁(yè)面是，便將該頁(yè)面的頁(yè)面號(hào)從棧中移出，將它壓入棧頂。因此，棧頂始終是最近最久未使用頁(yè)面的頁(yè)面號(hào)。
模擬實(shí)現(xiàn)2：
采用雙向鏈表+heapmap配合實(shí)現(xiàn)，靠近鏈表頭部的越是最近訪問(wèn)過(guò)得，鏈表尾部是最久未被訪問(wèn)的，從而體現(xiàn)使用的時(shí)間順序，heapmap記錄表項(xiàng)地址。
過(guò)程：
要操作頁(yè)面K
?????? 未在內(nèi)存 1.內(nèi)存未滿->直接插入鏈表頭部，記錄地址
???????????????????? ? 2.內(nèi)存已滿->先刪除鏈表尾部節(jié)點(diǎn),再插入新節(jié)點(diǎn)到鏈表頭部,并且更新map中增加該節(jié)點(diǎn)
?????? 已在內(nèi)存：更新節(jié)點(diǎn)的值，把當(dāng)前訪問(wèn)的節(jié)點(diǎn)移到鏈表頭部,并且更新map中該節(jié)點(diǎn)的地址。
class LRUBlock{ public:LRUBlock(int capacity) {size = capacity;}/**操作頁(yè)面k*/void set(int blockId,int k) {///未在內(nèi)存if(blockMap.find(k) == blockMap.end()){if(blockList.size() == size){///刪除鏈表尾部節(jié)點(diǎn)（最少訪問(wèn)的節(jié)點(diǎn)） blockMap.erase(blockList.back().pageId);blockList.pop_back();}///插入新節(jié)點(diǎn)到鏈表頭部,并且更新map中增加該節(jié)點(diǎn) blockList.push_front(BlockNode(blockId,k));blockMap[k] = blockList.begin();}///已在內(nèi)存else{///更新節(jié)點(diǎn)的值，把當(dāng)前訪問(wèn)的節(jié)點(diǎn)移到鏈表頭部,并且更新map中該節(jié)點(diǎn)的地址 blockList.splice(blockList.begin(), blockList, blockMap[k]);blockMap[k] = blockList.begin();}}list<BlockNode> getList(){return this->blockList;} private:list<BlockNode> blockList;unordered_map<int, list<BlockNode>::iterator> blockMap;///記錄結(jié)點(diǎn)地址int size; };?
void LRU(LRUBlock&lru,int address,map<int,TableEntry>&pageTable,map<int,int>&memoryBlock) {int pageNum=address/unitBlockSize;if(pageTable[pageNum].entryStatus==1){cout<<"頁(yè)面已在內(nèi)存中\(zhòng)n";lru.set(pageTable[pageNum].blockId,pageNum);}else{int s=memoryBlock.size();if(memoryBlock[s-1]==1){///直接分cout<<"所分配內(nèi)存塊還未用完\n";int i=s-1;for(;i>=0;i--){if(memoryBlock[i]==0)break;}memoryBlock[i+1]=0;pageTable[pageNum].entryStatus=1;pageTable[pageNum].blockId=i+1;lru.set(i+1,pageNum);}else///先swap再分 {cout<<"所分配內(nèi)存塊全被占用，需要置換操作\n";BlockNode blockNode=lru.getList().back();cout<<"置換出"<<blockNode.pageId<<"\t置換入"<<pageNum<<endl;///搶pageTable[blockNode.pageId].entryStatus=0;pageTable[blockNode.pageId].blockId=-1;pageTable[pageNum].entryStatus=1;pageTable[pageNum].blockId=blockNode.blockId;lru.set(blockNode.blockId,pageNum);}pageBreak++;}total++; }?
2.LFU：
least frequently used 最少使用置換
如果一個(gè)數(shù)據(jù)在最近一段時(shí)間內(nèi)使用次數(shù)很少，那么在將來(lái)一段時(shí)間內(nèi)被使用的可能性也很小，LRU的淘汰規(guī)則是基于訪問(wèn)時(shí)間，而LFU是基于訪問(wèn)次數(shù)的。
注意：
一般情況下，LFU效率要優(yōu)于LRU，且能夠避免周期性或者偶發(fā)性的操作導(dǎo)致緩存命中率下降的問(wèn)題。但LFU需要記錄數(shù)據(jù)的歷史訪問(wèn)記錄，一旦數(shù)據(jù)訪問(wèn)模式改變，LFU需要更長(zhǎng)時(shí)間來(lái)適用新的訪問(wèn)模式，即：LFU存在歷史數(shù)據(jù)影響將來(lái)數(shù)據(jù)的“緩存污染”效用。
實(shí)現(xiàn)：
用數(shù)組存儲(chǔ)內(nèi)存中表項(xiàng)情況，通過(guò)遍歷查找最小值。
過(guò)程：
要操作頁(yè)面K
?????? 未在內(nèi)存 1.內(nèi)存未滿：更新頁(yè)表，表項(xiàng)放入數(shù)組。
???????????????????? ? 2.內(nèi)存已滿：更新頁(yè)表，數(shù)組刪除要淘汰的表項(xiàng)，加入新表項(xiàng)。
?????? 已在內(nèi)存：更新頁(yè)表，表項(xiàng)重新放入數(shù)組。
3.FIFO
first in first out 最早出現(xiàn)置換
隊(duì)列實(shí)現(xiàn)
過(guò)程：
已在內(nèi)存：none
不在內(nèi)存：
內(nèi)存未滿：表項(xiàng)加入隊(duì)尾
內(nèi)存已滿：pop隊(duì)首，新表項(xiàng)加入隊(duì)尾
4.CLOCK
NRU---Not Recently Used
用數(shù)組存儲(chǔ)內(nèi)存中表項(xiàng)情況，修改數(shù)組中表項(xiàng)訪問(wèn)情況選擇置出頁(yè)面。
置換策略：依次訪問(wèn)數(shù)組中的表項(xiàng)，遇到status=1的置為0，再給一次駐留內(nèi)存的機(jī)會(huì)，遇到status=0的換出。
過(guò)程：
已在內(nèi)存：none
不在內(nèi)存：
內(nèi)存未滿：表項(xiàng)加入數(shù)組
內(nèi)存已滿：拿新來(lái)表項(xiàng)替換置出表項(xiàng)
?
?
?
轉(zhuǎn)載于:https://www.cnblogs.com/kimsimple/p/7065929.html
總結(jié)
以上是生活随笔為你收集整理的模拟请求分页式存储管理 ---4种置换算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 洛谷 P2046 BZOJ 2007 海
- 下一篇： 1191 数轴染色