操作系统——模拟页⾯置换算法（FIFO——先⼊先出、LRU——最近最少 使⽤、LFU——最近。。。
操作系统——模拟页⾯置换算法（FIFO——先⼊先出、LRU——最近最少使⽤、LFU——最近最不常使⽤），计算置换率（包含程序框图）
导语：
1. FIFO页⾯置换算法：最简单的页⾯置换算法。这种算法的基本思想是：当需要淘汰⼀个页⾯时，总是选择驻留主存时间最长的页⾯进⾏淘汰，即先进⼊主存的页⾯先淘汰。(看时间)
2. LRU页⾯置换算法：最近最少使⽤，简单来说就是将数据块中，每次使⽤过的数据放在数据块的最前端，然后将存在的时间最长的，也就是数据块的末端的数据置换掉。(看时间)
3. LFU页⾯置换算法：近期最少使⽤算法，选择近期最少访问的页⾯作为被替换的页⾯，如果⼀个数据在最近⼀段时间内使⽤次数很少，那么在将来⼀段时间内被使⽤的可能性也很⼩。(看次数)
4. 置换率与与缺页率不同。置换率⽤置换次数算，缺页率⽤缺页中断次数算。
FIFO页⾯置换算法：
Linux效果图（采⽤UOS + VScode + g++）
程序框图
C++代码(FIFO)：
#include<iostream>
using namespace std;
static int mnum;
static int pnum;
//页⾯⾛向
static int count=0;
//页⾯置换次数
织物密度镜static int *analogblock;
//模拟物理块
static int *block;
//物理块
static int *process;
//随机页⾯访问序列
int judge(int a[],int n,int x) //判断数组中是否已有x，若有返回其下标值，没有则返回-1 { int i;
for (i=0;i<n;i++)
if(x==a[i])
return i;
return -1;
}
管串void replace(int y,int mnum,int x)//⽤于物理块页⾯置换，y是⽤来置换的页⾯，x是被置换的页⾯ {
int i;
for (i=0;i<mnum;i++)
if(x==block[i])
block[i]=y;
接菜}
int main() {
int i;
int maxanalogblock=-1;
//模仿队列的定义
int x;
cout<<"请输⼊页框⼤⼩物理块数：\n";
cin>>mnum;
if(mnum>999999) {静电接地控制器
cout<<"输⼊超出控制⼤⼩！"<<endl;
return 0;
}
cout<<"⾃动⽣成的内存块需求序列个数：\n";
cin>>pnum;
if(pnum>999999) {
cout<<"输⼊超出控制⼤⼩！"<<endl;
return 0;
}
analogblock=new int[mnum];
block=new int[mnum];
process=new int[pnum];
for (i=0;i<mnum;i++) analogblock[i]=-1;
for (i=0;i<mnum;i++) block[i]=-1;
/////////////////////
/
/随机产⽣页⾯⾛向序列
cout<<"产⽣随机序列如下：\n";
srand( (unsigned)time( NULL ) );
//以time函数值（即当前时间）作为种⼦数，保证两次产⽣序列的随机性
for (i=0; i<pnum; i++) {
process[i] = rand()%10;
cout<<process[i]<<" ";
}
cout<<endl;
//////////////////////
cout<<"先进先出(FIFO)页⾯置换算法，结果： \n\n";
/
/////////////////////
for (x=0;x<pnum;x++) //⾃动读数 {
cout<<"真实物理块情况：";
for (i=0;i<mnum;i++) {
if(block[i]!=-1)
cout<<block[i]<<" ";
}
cout<<"模拟物理块情况：";
for (i=0;i<mnum;i++) {
if(analogblock[i]!=-1)
cout<<analogblock[i]<<" ";
}
//////////////////////////
maxanalogblock++;
//读数后maxanalogblock⾃动+1
if(maxanalogblock<mnum) //若在物理块范围内 {
if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {
analogblock[maxanalogblock]=process[x];
//新元素从尾部插⼊
block[maxanalogblock]=process[x];
//新元素从尾部插⼊
cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 缺页中断调⼊页⾯"<<process[x]<<endl;
} else //若数组中存在待插⼊元素 {
maxanalogblock--;
//因为没有插⼊新元素，回滚maxanalogblock值
cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 已存在直接访问"<<endl;
}
} else //超过物理块数的元素 {
if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {
//队列法插⼊(尾部元素出，新元素从头部⼊)
cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 缺页中断页⾯"<<process[x]<<"置换出页⾯"<<analogblock[0]<<endl; replace(process[x],mnum,analogblock[0]);
//置换物理块中页⾯
for (i=0;i<mnum-1;i++)
LRU 页⾯置换算法：
Linux 效果图（采⽤UOS + VScode + g++
）
程序框图
C++代码(LRU)： analogblock[i]=analogblock[i+1];
analogblock[mnum-1]=process[x];
//////////////////
maxanalogblock--;
/
/因为没有插⼊新元素，回滚maxanalogblock 值
count++;
} else //若数组中存在待插⼊元素 {
maxanalogblock--;
//因为没有插⼊新元素，回滚maxanalogblock 值
cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 已存在 直接访问"<<endl;
}
}
}
//读⼀个序列号，输出当前数组元素
cout<<"真实物理块情况：";
for (i=0;i<mnum;i++) {
if(block[i]!=-1) cout<<block[i]<<" ";
}
cout<<"模拟物理块情况：";
for (i=0;i<mnum;i++) {
if(analogblock[i]!=-1)
cout<<analogblock[i]<<" ";
}
cout<<endl<<"页⾯换算次数为："<<count<<endl;
cout<<"置换率为："<<(float)count/pnum<<endl;
return 0;
}
//g++ test71.cpp -o test71 -lpthread&&./test71
#include<iostream>
using namespace std;
static int mnum;
//物理块数
static int pnum;
//页⾯⾛向
static int count=0;
//页⾯置换次数
static int *analogblock;
/
/模拟物理块
static int *block;
//物理块
static int *process;
//随机页⾯访问序列
int judge(int a[],int n,int x) //判断数组中是否已有x ，若有返回其下标值，没有则返回-1 {
int i;
for (i=0;i<n;i++)
if(x==a[i])
return i;
return -1;
}
void replace(int y,int mnum,int x)//⽤于物理块页⾯置换，y是⽤来置换的页⾯，x是被置换的页⾯ { int i;
for (i=0;i<mnum;i++)
if(x==block[i])
block[i]=y;
}
void move(int a[],int n,int i) //移动下标为i的元素到尾部 {
int j;
int m=a[i];
for (j=i;j<n-1;j++)
a[j]=a[j+1];
a[n-1]=m;
}
int main() {
int i;
int maxanalogblock=-1;
//模仿栈的定义
int x;
cout<<"请输⼊页框⼤⼩物理块数：\n";
cin>>mnum;
if(mnum>999999) {
cout<<"输⼊超出控制⼤⼩！"<<endl;
return 0;
}
cout<<"⾃动⽣成的内存块需求序列个数：\n";
cin>>pnum;
if(pnum>999999) {
cout<<"输⼊超出控制⼤⼩！"<<endl;
return 0;
}
analogblock=new int[mnum];
block=new int[mnum];
process=new int[pnum];
for (i=0;i<mnum;i++) analogblock[i]=-1;
/////////////////////
//随机产⽣页⾯⾛向序列
cout<<"产⽣随机序列如下：\n";
srand( (unsigned)time( NULL ) );
//以time函数值（即当前时间）作为种⼦数，保证两次产⽣序列的随机性
for (i=0; i<pnum; i++) {
process[i] = rand()%10;
cout<<process[i]<<" ";
}
cout<<endl;
/
/////////////////////
cout<<"最近最少使⽤(LRU)页⾯置换算法，结果： \n\n";气泵接头
//////////////////////
for (x=0;x<pnum;x++) //⾃动读数 {
//读⼀个序列号，输出当前数组元素
cout<<"真实物理块情况：";
for (i=0;i<mnum;i++) {
if(block[i]!=-1)
cout<<block[i]<<" ";
}
cout<<"模拟物理块情况：";
for (i=0;i<mnum;i++) {
if(analogblock[i]!=-1)
cout<<analogblock[i]<<" ";
}
//////////////////////////
maxanalogblock++;
//读数后maxanalogblock⾃动+1
LFU 页⾯置换算法：
Linux 效果图（采⽤UOS + VScode + g++
）
程序框图 if(maxanalogblock<mnum) //若在物理块范围内 {
if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {
analogblock[maxanalogblock]=process[x];
//新元素从尾部插⼊
block[maxanalogblock]=process[x];
//新元素从尾部插⼊
cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 缺页中断 调⼊页⾯"<<process[x]<<endl;
} else //若数组中存在待插⼊元素 {
move(analogblock,maxanalogblock,judge(analogblock,mnum,process[x]));
//移动下标为i 的元素到尾部
maxanalogblock--;
/
/因为没有插⼊新元素，回滚maxanalogblock 值
空气中取水
cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 已存在 直接访问"<<endl;
}
} else //超过物理块数的元素 {
if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {
//栈法插⼊(第⼀个元素出，后⾯元素前移，新元素从尾部⼊)
cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 缺页中断 页⾯"<<process[x]<<"置换出页⾯"<<analogblock[0]<<endl; replace(process[x],mnum,analogblock[0]);
//物理块中页⾯置换
for (i=0;i<mnum-1;i++)
analogblock[i]=analogblock[i+1];
analogblock[mnum-1]=process[x];
//////////////////
maxanalogblock--;
//因为没有插⼊新元素，回滚maxanalogblock 值
count++;
} else //若数组中存在待插⼊元素 {
move(analogblock,mnum,judge(analogblock,mnum,process[x]));
//移动下标为i 的元素到尾部
maxanalogblock--;
//因为没有插⼊新元素，回滚maxanalogblock 值
cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 已存在 直接访问"<<endl;
}
}
}
//读⼀个序列号，输出当前数组元素
cout<<"真实物理块情况：";
for (i=0;i<mnum;i++) {
if(block[i]!=-1)
cout<<block[i]<<" ";
}
cout<<"模拟物理块情况：";
for (i=0;i<mnum;i++) {
if(analogblock[i]!=-1)
cout<<analogblock[i]<<" ";
}
cout<<endl<<"页⾯换算次数为："<<count<<endl;
cout<<"置换率为："<<(float)count/pnum<<endl;
return 0;
}
//g++ test72.cpp -o test72 -lpthread&&./test72
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议