0
0

虚拟内存页面置换算法（操作系统）

虚拟内存页面置换算法

1.实验目的

通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。

2.实验内容

问题描述：
设计程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。
程序要求：
1）利用先进先出FIFO、最佳置换OPI和最近最久未使用LRU三种页面置换算法模拟页面访问过程。
2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。
3）输入：最小物理块数m，页面个数n，页面访问序列P1, … ,Pn，算法选择1-FIFO，2-OPI，3-LRU。
4）输出：每种算法的缺页次数和缺页率。
实现提示：
用C++语言实现提示：
1）程序中变量定义参考（根据需要可添加）如下：
const int MaxNumber=100;
int PageOrder[MaxNumber];
int Simulate[MaxNumber][MaxNumber];
int PageCount[MaxNumber];
int PageNum,LackNum;
double LackPageRate;
bool found;
2）页面置换的实现过程如下：
变量初始化；
接收用户输入最小物理块数m，页面个数n，页面序列P1, … ,Pn，选择算法1-FIFO，2-OPI，3-LRU；
根据用户选择的算法进行页面的分配和置换，输出页面置换算法的模拟过程；
计算选择算法的缺页次数和缺页率；
输出选择算法的缺页次数和缺页率。

3.程序主要构成部分及其算法说明

1.初始化
先将后续用到的各种变量和数组进行初始化，之后开始为初始为空的物理块分配页面至物理块被填满，分配时先使用两个for循环判断页面是否已经在物理块内，如果已经存在，则直接遍历下一个页面（时间复杂度为O（n²）），如果不存在，将该页面加入物理块中，相应的变量进行改变（时间复杂度为O（n3）），直到物理块被填满。

  1. voidinitial(){int i,j,k;int z=0;bool found;
  2.     LackPageNum = BlockNum; 
  3.     LackPageRate =0.0;for(int i =0;i<PageNum;i++){
  4.         PageCount[i]=0; 
  5.         VirtualQueue[i]=-1;}for(int i=0;i<BlockNum;i++){for(int j=0;j<PageNum;j++){
  6.             Simulate[i][j]=-1;}}for(int i =0;i<PageNum;i++){ 
  7.         found =false;
  8.         timeOfLRU[i]=0;for(int j =0;j<BlockNum;j++){if(VirtualQueue[j]== PageOrder[i]){
  9.                 found =true;}}if(!found){ 
  10.             VirtualQueue[z]= PageOrder[i];for(int j=0;j<=z;j++){
  11.             Simulate[j][i]=VirtualQueue[j];}
  12.             z++;for(int k =0;k<i;k++){
  13.                 timeOfLRU[k]++;}}else{
  14.             timeOfLRU[i]=0;}if(z==BlockNum){break;}}}

2.FIFO
首先调用初始化方法将物理块填满，并设置一个指针point，使它总是指向最老的页面，然后从未分配的页面处开始分配，算法与初始化方法中的算法类似，如果已经存在，则直接遍历下一个页面（时间复杂度为O（n²）），如果不存在，缺页数+1，并且替换到物理块中最老的页面，改变point的值，使其指向新队列中最老的页面（时间复杂度为O（n3））。

  1. voidFIFO(){
  2.     cout<<"当前选择的算法:FIFO"<<endl;initial();int i,j,k;int point =0;for(int i = BlockNum;i<PageNum;i++){
  3.         found =false;for(int k =0;k<BlockNum;k++){if(VirtualQueue[k]== PageOrder[i]){ 
  4.                 found =true;}}if(!found){  
  5.             LackPageNum++; 
  6.             VirtualQueue[point]= PageOrder[i];for(int j=0;j<=BlockNum;j++){
  7.             Simulate[j][i]=VirtualQueue[j];}
  8.             point++;if(point == BlockNum) 
  9.                 point =0;}}output();
  10.     LackPageRate =(LackPageNum *1.0)/PageNum;
  11.     cout<<"LackPageNum: "<<LackPageNum<<endl;
  12.     cout<<"LackPageRate: "<<LackPageRate<<endl;}

3.OPI
首先调用初始化方法将物理块填满，并设置变量distance用于保存物理块内页面下次被访问的距离和一个指针point，使它指向最远距离的物理块页面，然后从未分配的页面处开始分配，算法与初始化方法中的算法类似，如果已经存在，则直接遍历下一个页面（时间复杂度为O（n²）），如果不存在，缺页数+1，分别计算每个物理块的距离，之后让point指向距离最远的页面，然后替换物理块中距离最远的页面（时间复杂度为O（n4））。

  1. voidOPI(){
  2.     cout<<"当前选择的算法:OPI"<<endl;int i,j,s,k,m,t;initial();int distance;int point;for(i = BlockNum;i<PageNum;i++){
  3.         found =false;for(k =0;k<BlockNum;k++){if(VirtualQueue[k]== PageOrder[i]){ 
  4.                 found =true;}}if(!found){
  5.             LackPageNum++;for(s =0;s < BlockNum;s++){
  6.                 distance =1;for(t = i;t<PageNum;t++){if(VirtualQueue[s]!= PageOrder[t])
  7.                         distance++;elsebreak;}
  8.                 PageCount[s]= distance;}
  9.             point =0;for(m =1;m < BlockNum;m++){if(PageCount[point]< PageCount[m])
  10.                     point = m;}
  11.             VirtualQueue[point]= PageOrder[i];for(j=0;j<=BlockNum;j++){
  12.             Simulate[j][i]=VirtualQueue[j];}}}output();
  13.     LackPageRate =(LackPageNum*1.0)/PageNum;
  14.     cout<<"LackPageNum: "<<LackPageNum<<endl;
  15.     cout<<"LackPageRate: "<<LackPageRate<<endl;}

4.LRU
首先调用初始化方法将物理块填满，设置一个指针point，使其指向最近最久未使用的页面。从未分配的页面处开始分配，算法与初始化方法中的算法类似，如果已经存在，命中的页面时间归0，其余页面时间+1，再遍历下一个页面（时间复杂度为O（n3）），如果不存在，缺页数+1，比较得到队列中最近最久未被访问的页面，让point指向该页面，再让其余的页面时间+1，再替换该页面，该页面时间为0（时间复杂度为O（n3））。

  1. voidLRU(){
  2.     cout<<"当前选择的算法:LRU"<<endl;int i,j,s,k;initial();int point;for(i = BlockNum;i<PageNum;i++){
  3.         found =false;for(k =0;k<BlockNum;k++){if(VirtualQueue[k]== PageOrder[i])   
  4.                   found =true;}if(!found){
  5.             LackPageNum++;
  6.             point =0;for(j =1;j<BlockNum;j++){if(timeOfLRU[point]<timeOfLRU[j])
  7.                     point = j;}for(s =0;s<BlockNum;s++){if(VirtualQueue[s]!= VirtualQueue[point])
  8.                     timeOfLRU[s]++;}
  9.             VirtualQueue[point]= PageOrder[i];for(j=0;j<=BlockNum;j++){
  10.             Simulate[j][i]=VirtualQueue[j];}
  11.             timeOfLRU[point]=0;}else{for(s =0;s<BlockNum;s++){if(VirtualQueue[s]!= PageOrder[i])
  12.                     timeOfLRU[s]++;else
  13.                     timeOfLRU[s]=0;}}}output();
  14.     LackPageRate =(LackPageNum*1.0)/PageNum;
  15.     cout<<"LackPageNum: "<<LackPageNum<<endl;
  16.     cout<<"LackPageRate: "<<LackPageRate<<endl;}

4.运行结果

1.首先输入物理块数，页面个数和页面序列，之后程序输出对应的数据验证，并提示选择算法
在这里插入图片描述

2.输入对应的数字程序执行对应的算法，并打印输出页面置换算法的模拟过程，输出选择算法的缺页数和缺页率。

在这里插入图片描述

5.程序源码

  1. #include<iostream>#include<fstream>#include<iomanip>#include<stdlib.h>usingnamespace std;#defineMaxNumber100int PageOrder[MaxNumber];//页面序列int Simulate[MaxNumber][MaxNumber];//存放输出的数组 int PageCount[MaxNumber];//当前内存距离下一次出现的距离int BlockNum;//物理块数int PageNum;//页面个数int LackNum;//缺页数 double  LackPageRate;//缺页率bool found;//页面是否命中 int timeOfLRU[MaxNumber];//记录物理块中各个页面最近使用时间 int memoryPage[MaxNumber];//虚拟队列int choose;voidinput();//输入voidinitial();//初始化物理块voidFIFO();voidOPI();voidLRU();voidchooseAlgorithm();//选择算法voidoutput();//输出 intmain(){input();chooseAlgorithm();return0;}voidinput(){
  2.      ifstream readData;
  3.     readData.open("data.txt");
  4.     readData>>BlockNum;
  5.     readData>>PageNum;for(int i=0;i<PageNum;i++){
  6.         readData>>PageOrder[i];}
  7.     
  8.     cout<<"最小物理块数 = "<<BlockNum<<endl;
  9.     cout<<"页面个数 = "<<PageNum<<endl;
  10.     cout<<"页面序列:"<<endl;for(int i =0;i<PageNum;i++){
  11.         cout<<PageOrder[i]<<" ";}
  12.     cout<<endl;}voidinitial(){//初始化 int i,j,k;int z=0;//判断初始化物理块是否填满bool found;
  13.     LackNum = BlockNum;//缺页数=物理块数+缺页次数
  14.     LackPageRate =0.0;for(int i =0;i<PageNum;i++){
  15.         PageCount[i]=0;//初始化距离
  16.         memoryPage[i]=-1;//初始化队列}for(int i=0;i<BlockNum;i++){for(int j=0;j<PageNum;j++){
  17.             Simulate[i][j]=-1;//初始化}}for(int i =0;i<PageNum;i++){//初始化物理块
  18.         found =false;
  19.         timeOfLRU[i]=0;for(int j =0;j<BlockNum;j++){if(memoryPage[j]== PageOrder[i])//页面命中{
  20.                 found =true;}}if(!found){//当有新的进程进入到队列时，便计算其对应的距离
  21.             memoryPage[z]= PageOrder[i];//小于物理块数时，页面顺序进入队列for(int j=0;j<=z;j++){
  22.             Simulate[j][i]=memoryPage[j];//保存当前序列的值}
  23.             z++;for(int k =0;k<i;k++){
  24.                 timeOfLRU[k]++;//之前的页面对应的时间+1}}else{
  25.             timeOfLRU[i]=0;//重新更新为0，表示最近刚刚使用}if(z==BlockNum){//物理块被填满，结束循环 break;}}}voidFIFO(){
  26.     cout<<"当前选择的算法:FIFO"<<endl;initial();int i,j,k;int point =0;//分配内存for(int i = BlockNum;i<PageNum;i++){
  27.         found =false;for(int k =0;k<BlockNum;k++){if(memoryPage[k]== PageOrder[i]){//页面命中
  28.                 found =true;}}if(!found){//如果页面不在队列中，则进行相应的处理
  29.             LackNum++;//缺页数加1
  30.             memoryPage[point]= PageOrder[i];//页面替换队列中最老的for(int j=0;j<=BlockNum;j++){
  31.             Simulate[j][i]=memoryPage[j];//保存当前序列的值}
  32.             point++;//后移if(point == BlockNum)//当指向队尾时后，重新指向队首
  33.                 point =0;}}output();//输出物理块状态
  34.     LackPageRate =(LackNum *1.0)/PageNum;
  35.     cout<<"缺页数：: "<<LackNum<<endl;
  36.     cout<<"缺页率：: "<<LackPageRate<<endl;}voidOPI(){
  37.     cout<<"当前选择的算法:OPI"<<endl;int i,j,s,k,m,t;initial();int distance;//表示队列每个值距离下一次访问的距离int point;//指向最长时间未被访问的下标for(i = BlockNum;i<PageNum;i++){
  38.         found =false;for(k =0;k<BlockNum;k++){if(memoryPage[k]== PageOrder[i]){//页面命中
  39.                 found =true;}}if(!found){
  40.             LackNum++;//计算当前队列每一页对应的下一次出现的距离for(s =0;s < BlockNum;s++){
  41.                 distance =1;for(t = i;t<PageNum;t++){//向后找离他最远的if(memoryPage[s]!= PageOrder[t])
  42.                         distance++;elsebreak;}
  43.                 PageCount[s]= distance;//当前内存距离下一次出现的距离}//向后比较队列内最长时间不被访问的并淘汰，置换页面
  44.             point =0;for(m =1;m < BlockNum;m++){if(PageCount[point]< PageCount[m])
  45.                     point = m;}
  46.             memoryPage[point]= PageOrder[i];for(j=0;j<=BlockNum;j++){
  47.             Simulate[j][i]=memoryPage[j];//保存当前序列的值}}}output();
  48.     LackPageRate =(LackNum*1.0)/PageNum;
  49.     cout<<"缺页数：: "<<LackNum<<endl;
  50.     cout<<"缺页率：: "<<LackPageRate<<endl;}voidLRU(){
  51.     cout<<"当前选择的算法:LRU"<<endl;int i,j,s,k;initial();int point;//指向最长时间未被访问的下标for(i = BlockNum;i<PageNum;i++){
  52.         found =false;for(k =0;k<BlockNum;k++){if(memoryPage[k]== PageOrder[i])//页面命中
  53.                   found =true;}if(!found){
  54.             LackNum++;//向前比较队列内最长时间不被访问的并淘汰，置换页面
  55.             point  =0;for(j =1;j<BlockNum;j++){if(timeOfLRU[point]<timeOfLRU[j])
  56.                     point = j;}for(s =0;s<BlockNum;s++){//其余页面对应的时间要+1if(memoryPage[s]!= memoryPage[point])
  57.                     timeOfLRU[s]++;}
  58.             
  59.             memoryPage[point]= PageOrder[i];for(j=0;j<=BlockNum;j++){
  60.             Simulate[j][i]=memoryPage[j];//保存当前序列的值}
  61.             timeOfLRU[point]=0;}else{//负责更新当前对应页面的时间for(s =0;s<BlockNum;s++){//其余页面对应的时间要+1if(memoryPage[s]!= PageOrder[i])
  62.                     timeOfLRU[s]++;else
  63.                     timeOfLRU[s]=0;}}}output();
  64.  
  65.     LackPageRate =(LackNum*1.0)/PageNum;
  66.     cout<<"缺页数：: "<<LackNum<<endl;
  67.     cout<<"缺页率：: "<<LackPageRate<<endl;}voidchooseAlgorithm(){
  68.     cout<<"请选择算法“1-先进先出(FIFO)页面置换算法，2-最佳(Optimal)置换算法，3-最近最久未使用(LRU)页面置换算法，0-结束”"<<endl;
  69.     cin>>choose;
  70.     cout<<endl;if(choose==1){FIFO();chooseAlgorithm();}elseif(choose==2){OPI();chooseAlgorithm();}elseif(choose==3){LRU();chooseAlgorithm();}elseif(choose==0){exit(0);}else{
  71.         cout<<"输入错误“1-首次适应算法FF，2-循环首次适应算法NF，3-最佳适应算法BF，4-最坏适应算法WF，0-退出”"<<endl;chooseAlgorithm();}}voidoutput(){int i,j;for(i=0;i<PageNum;i++){
  72.         cout<<PageOrder[i]<<"  ";}
  73.     cout<<endl;for(i=0;i<BlockNum;i++){for(j=0;j<PageNum;j++){if(Simulate[i][j]==-1){
  74.                     cout<<"   ";}else{
  75.             cout<<"  "<<Simulate[i][j];}}
  76.         cout<<endl;}}

输入数据格式

  1. 32070120304230321201701
标签： 算法 数据结构 windows
本文转载自: https://blog.csdn.net/weixin_51080803/article/details/129911917
版权归原作者 落灬枫 所有， 如有侵权，请联系我们删除。
登录后发布评论

“虚拟内存页面置换算法（操作系统）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？