c++编写一个模拟的动态页式存储管理程序,实现对动态页式存储的淘汰算法的模拟(包括先进先出淘汰算法、最近最少使用淘汰算法、最不经常使用淘汰算法三种算法均进行模拟)并计算各个算法的缺页率
时间: 2023-07-26 18:26:52 浏览: 162
好的,我了解了您的要求。下面是一个简单的C++动态页式存储管理程序,实现了三种淘汰算法(先进先出、最近最少使用、最不经常使用)的模拟,并计算了各个算法的缺页率。
```c++
#include<iostream>
#include<queue>
#include<unordered_map>
#include<algorithm>
using namespace std;
//页面结构体
struct Page {
int num;
int time;
};
//先进先出算法
double FIFO(int page_num, int frame_num, vector<int>& pages) {
double miss_count = 0; //缺页次数
queue<int> frame; //页面帧队列
for(int i=0; i<pages.size(); i++) {
//如果页面帧队列未满,直接将页面添加到队列中
if(frame.size() < frame_num) {
frame.push(pages[i]);
miss_count++;
}
//如果页面帧队列已满
else {
//如果页面已在队列中,跳过
bool flag = false;
for(int j=0; j<frame.size(); j++) {
if(frame.front() == pages[i]) {
flag = true;
break;
}
frame.push(frame.front());
frame.pop();
}
if(flag) continue;
//如果页面未在队列中,弹出队首页面,将新页面添加到队列末尾
frame.pop();
frame.push(pages[i]);
miss_count++;
}
}
return miss_count / page_num;
}
//最近最少使用算法
double LRU(int page_num, int frame_num, vector<int>& pages) {
double miss_count = 0; //缺页次数
int time_count = 0; //时间计数器
unordered_map<int, int> time_map; //页面时间戳哈希表
vector<Page> frame(frame_num); //页面帧数组
for(int i=0; i<pages.size(); i++) {
//如果页面已在页面帧数组中,更新时间戳
bool flag = false;
for(int j=0; j<frame.size(); j++) {
if(frame[j].num == pages[i]) {
flag = true;
frame[j].time = time_count++;
break;
}
}
if(flag) continue;
//如果页面未在页面帧数组中,查找时间戳最小的页面,替换为新页面
int min_time = frame[0].time, min_index = 0;
for(int j=1; j<frame.size(); j++) {
if(frame[j].time < min_time) {
min_time = frame[j].time;
min_index = j;
}
}
frame[min_index].num = pages[i];
frame[min_index].time = time_count++;
miss_count++;
}
return miss_count / page_num;
}
//最不经常使用算法
double LFU(int page_num, int frame_num, vector<int>& pages) {
double miss_count = 0; //缺页次数
int time_count = 0; //时间计数器
unordered_map<int, int> freq_map; //页面访问次数哈希表
vector<Page> frame(frame_num); //页面帧数组
for(int i=0; i<pages.size(); i++) {
//如果页面已在页面帧数组中,更新访问次数
bool flag = false;
for(int j=0; j<frame.size(); j++) {
if(frame[j].num == pages[i]) {
flag = true;
freq_map[pages[i]]++;
frame[j].time = time_count++;
break;
}
}
if(flag) continue;
//如果页面未在页面帧数组中,查找访问次数最小的页面,替换为新页面
int min_freq = freq_map[frame[0].num], min_index = 0;
for(int j=1; j<frame.size(); j++) {
if(freq_map[frame[j].num] < min_freq) {
min_freq = freq_map[frame[j].num];
min_index = j;
}
}
frame[min_index].num = pages[i];
freq_map[pages[i]] = 1;
frame[min_index].time = time_count++;
miss_count++;
}
return miss_count / page_num;
}
int main() {
int page_num = 20; //页面数目
int frame_num = 3; //页面帧数目
vector<int> pages(page_num); //页面序列
for(int i=0; i<page_num; i++) {
pages[i] = rand() % 10;
}
cout << "页面序列: ";
for(int i=0; i<page_num; i++) {
cout << pages[i] << " ";
}
cout << endl;
cout << "先进先出算法缺页率: " << FIFO(page_num, frame_num, pages) << endl;
cout << "最近最少使用算法缺页率: " << LRU(page_num, frame_num, pages) << endl;
cout << "最不经常使用算法缺页率: " << LFU(page_num, frame_num, pages) << endl;
return 0;
}
```
这个程序使用了随机生成的页面序列,包括了三种淘汰算法的实现和缺页率的计算。您可以根据需要修改页面数目、页面帧数目和页面序列来进行测试。
阅读全文