页面置换算法代码
时间: 2023-08-06 16:17:46 浏览: 56
以下是一个简单的页面置换算法的代码实现,采用了最近最少使用(LRU)算法:
```
#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;
class PageCache {
private:
list<int> cache; // 存储页号的双向链表
unordered_map<int, list<int>::iterator> cacheMap; // 存储页号对应的迭代器
int capacity; // 缓存容量
public:
PageCache(int capacity) {
this->capacity = capacity;
}
void refer(int page) {
// 如果页号已经在缓存中
if (cacheMap.find(page) != cacheMap.end()) {
// 将该页号移到链表头部
cache.erase(cacheMap[page]);
cache.push_front(page);
cacheMap[page] = cache.begin();
} else {
// 如果缓存已满,删除链表尾部的页号
if (cache.size() == capacity) {
int lastPage = cache.back();
cache.pop_back();
cacheMap.erase(lastPage);
}
// 将新页号插入链表头部
cache.push_front(page);
cacheMap[page] = cache.begin();
}
}
void display() {
for (auto it = cache.begin(); it != cache.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
};
int main() {
PageCache cache(3);
cache.refer(1);
cache.display();
cache.refer(2);
cache.display();
cache.refer(3);
cache.display();
cache.refer(4);
cache.display();
cache.refer(3);
cache.display();
cache.refer(1);
cache.display();
cache.refer(4);
cache.display();
return 0;
}
```
在此代码中,`PageCache` 类维护了一个双向链表 `cache` 和一个哈希表 `cacheMap`。`cache` 存储了当前缓存中的所有页号,而 `cacheMap` 存储了每个页号在 `cache` 中的迭代器。`refer` 函数用于向缓存中添加或删除页号,`display` 函数用于显示当前缓存中的所有页号。