页面置换算法FIFO、OPT、LRU
程序员文章站
2022-07-05 08:10:42
...
FIFO——先进先出置换算法
OPT——最佳置换算法
LRU——最近最久未使用算法
#include<iostream>
#include<cstdio>
#include<queue>
#define M 3
using namespace std;
void FIFO();
void OPT();
void LRU();
void printMemory();
int search();
struct page{
int k;//页面号
int i;//顺序
}memory[M+1];
page arr[1000000];//OPT算法中使用,存储后序节点
int n;
queue<int> q;
int flag=0;
int j=0;//1=<j<=M,记录当前内存中页面个数
int num=0;//次序
int cnt;//成功访问的次数
int main(){
cout<<"输入页面访问顺序次数:";
cin>>n;
cout<<"输入页面访问顺序:";
int x;
for(int i = 1; i <=n; ++i)
{
cin>>x;
q.push(x);
arr[i].k=x;//记录页号
arr[i].i=i;//记录次序
}
cout<<"选择页面置换算法: 1.FIFO算法 2.最佳置换OPI算法 3、LRU算法"<<endl;
int which;
cin>>which;
cout<<"运行过程如下:"<<endl;
switch(which){
case 1:
FIFO();
break;
case 2:
OPT();
break;
case 3:
LRU();
break;
}
cout<<"缺页率为:"<<(n-cnt)*100/n<<"%"<<endl;
return 0;
}
void FIFO(){
while(q.size()){
num++;
int t=q.front();
q.pop();
cout<<"------------------正在请求页面"<<t<<"...------------------"<<endl;
for(int i=1;i<=j;i++){
if(memory[i].k==t){
flag=1;//页面在内存中
cnt++;
cout<<"---页面"<<t<<"在内存中,成功访问"<<endl;
break;
}
}
if(!flag && j==M){//需要置换
int minx=1;//存储最早来的节点的下标
for(int i=2;i<=j;i++){
if(memory[i].i<memory[minx].i)
minx=i;
}
cout<<"---正在将页面"<<memory[minx].k<<"移出内存..."<<endl;
memory[minx].k=t;
memory[minx].i=num;
cout<<"---正在将页面"<<t<<"装入内存..."<<endl;
}
if(!flag && j<M){//直接放入内存
j++;
memory[j].k=t;
memory[j].i=num;
cout<<"---正在将页面"<<t<<"装入内存..."<<endl;
}
flag=0;
printMemory();
}
}
void OPT(){
while(q.size()){
num++;
int t=q.front();
q.pop();
cout<<"------------------正在请求页面"<<t<<"...------------------"<<endl;
for(int i=1;i<=j;i++){
if(memory[i].k==t){
flag=1;//页面在内存中
cnt++;
cout<<"---页面"<<t<<"在内存中,成功访问"<<endl;
break;
}
}
if(!flag && j==M){//需要置换
int index= search();//调用搜索函数,找到符合条件的节点的下标
cout<<"---正在将页面"<<memory[index].k<<"移出内存..."<<endl;
memory[index].k=t;
cout<<"---正在将页面"<<t<<"装入内存..."<<endl;
}
if(!flag && j<M){//直接放入内存
j++;
memory[j].k=t;
cout<<"---正在将页面"<<t<<"装入内存..."<<endl;
}
flag=0;
printMemory();
}
}
void LRU(){
while(q.size()){
num++;
int t=q.front();
q.pop();
cout<<"------------------正在请求页面"<<t<<"...------------------"<<endl;
for(int i=1;i<=j;i++){
if(memory[i].k==t){
flag=1;//页面在内存中
cnt++;
memory[i].i=num;//更新顺序
cout<<"---页面"<<t<<"在内存中,成功访问"<<endl;
break;
}
}
if(!flag && j==M){//需要置换
int longx=1;//存储最近最久没有被访问的节点的下标
for(int i=2;i<=j;i++){
if(memory[i].i<memory[longx].i)
longx=i;
}
cout<<"---正在将页面"<<memory[longx].k<<"移出内存..."<<endl;
memory[longx].k=t;
memory[longx].i=num;
cout<<"---正在将页面"<<t<<"装入内存..."<<endl;
}
if(!flag && j<M){//直接放入内存
j++;
memory[j].k=t;
memory[j].i=num;
cout<<"---正在将页面"<<t<<"装入内存..."<<endl;
}
flag=0;
printMemory();
}
}
void printMemory(){
for(int i=1;i<=j;i++){
cout<<"页面"<<memory[i].k;
}
cout<<endl;
}
//用于OPT算法中找到最长时间内不再被访问的页面
int search(){
int index=1;
int temp[M+1];
for(int i=1;i<=j;i++){
for(int m=num+1;m<=n;m++){
if(memory[i].k==arr[m].k){
temp[i]=m;//将内存中各个页面在未来第一次出现时的下标记录下来
break;
}
else
temp[i]=INT_MAX;
}
}
for(int i=2;i<=j;i++){
if(temp[i]>temp[index]){
index=i;
}
}
return index;
}
上一篇: 从每天需要抠鼻屎的次数就看出来了