先进先出(FIFO)页面置换算法C语言实现、最近最久未使用(LRU)页面置换算法C语言实现
2021/12/31 20:39:12
本文主要是介绍先进先出(FIFO)页面置换算法C语言实现、最近最久未使用(LRU)页面置换算法C语言实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1. 实现效果
2. 源代码
#include<iostream> #include<process.h> #include<stdlib.h> #include<ctime> #include<conio.h> #include<stdio.h> #include<string.h> using namespace std; #define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")/*表格控制*/ #define bsize 4 //物理块大小 #define psize 16 //进程大小 void chushihua();//初始化函数 void ymzh(); void yemianzhihuan (); void changeaddr(struct Page p[], int logaddr); void dizhizhuanhuan(); void menu(); int wang(); int yemianliu[32]={0};//全局变量数组,地址流 int p; struct Page { int pno;//页号 int flag;//标志位 int cno;//主存号 int modf;//修改位 int addr;//外存地址 }Page; //全局变量p是一共有多少地址流 typedef struct pagel { int num; /*记录页面号*/ int time; /*记录调入内存时间*/ }Pagel; /*页面逻辑结构,方便算法实现*/ Pagel b[bsize]; /*内存单元数*/ int c[bsize][psize];/*保存内存当前的状态:缓冲区*/ int queue[100];/*记录调入队列*/ int k;/*调入队列计数变量*/ int phb[bsize]={0};//物理块标号 int pro[psize]={0};//进程序列号 int flag[bsize]={0};//进程等待次数(存放最久未被使用的进程标志)*/ int i=0,j=0;//i表示进程序列号,j表示物理块号*/ int m =-1,n =-1;//物理块空闲和进程是否相同判断标志*/ int mmax=-1, maxflag=0;//标记替换物理块进程下标*/ int count =0; //统计页面缺页次数 void chushihua() //初始化函数 { int t; srand(time(0));//随机产生指令序列 p=12+rand()%32; cout<<"地址流序列:"; cout<<endl; for(i=0; i<p; i++) { t=1+rand()%9; yemianliu[i]=t;//将随机产生的指令数存入页面流 } for (i=p-1;i>=0;i--) { cout<<yemianliu[i]<<" "; } cout<<endl; } void ymzh() { chushihua(); yemianzhihuan(); } void yemianzhihuan() { int a; printf("----------------------------------\n"); printf("☆☆欢迎使用分页模拟实验系统☆☆\n"); printf("----------------------------------"); printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); printf("☆☆1.进入硬件地址变换算法 ☆☆\n"); printf("☆☆------------------------☆☆\n"); printf("☆☆2.进入页面置换算法 ☆☆\n"); printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); printf("请输入您的选择:"); switch(a) { case 1: ymzh(); break; case 2: wang(); break; default: cout<<"输入有误,请重新输入!"<<endl; break; } } void changeaddr(struct Page p[], int logaddr){//地址变换 int j=logaddr/64;//对应的块号 int k=logaddr%64; //对应的偏移量 int flag=0; int addr; for(int i=0;i<8;i++) { if(p[i].pno==j)//找到对应的页号 { if(p[i].flag==1)//页面标志为1 { addr=p[i].cno*64+k; cout<<"物理地址为:"<<addr<<endl; cout<<"详细信息:"<<"\t页面号:"<<p[i].pno<<"\t 主存号:"<<p[i].cno<<"\t偏移量:"<<k<<endl; flag=1; break; } } } if(flag==0) cout<<"该页不在主存,产生缺页中断"<<endl; } void dizhizhuanhuan() { int a; int ins;//指令逻辑地址 struct Page p[8]; p[0].pno=0;p[0].flag=1;p[0].cno=5;p[0].modf=1;p[0].addr=011; p[1].pno=1;p[1].flag=1;p[1].cno=8;p[1].modf=1;p[1].addr=012; p[2].pno=2;p[2].flag=1;p[2].cno=9;p[2].modf=0;p[2].addr=013; p[3].pno=3;p[3].flag=1;p[3].cno=10;p[3].modf=0;p[3].addr=015; p[4].pno=4;p[4].flag=0;p[4].addr=017; p[5].pno=5;p[5].flag=0;p[5].addr=025; p[6].pno=6;p[6].flag=0;p[6].addr=212; p[7].pno=7;p[7].flag=0;p[7].addr=213; printf("\t\t\t--------------------------------\n"); printf("\t\t\t☆☆欢迎使用分页模拟实验系统☆☆\n"); printf("\t\t\t---------------------------------\n"); printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); printf("\t\t\t☆☆1.输入指令 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆2.进入页面置换算法 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆0.EXIT ☆☆\n"); printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); while(a!=0) { cout<<endl<<"请输入您的选择:"; cin>>a; cout<<"页号"<<"标记位"<<"外存地址"<<"主存号"<<endl; for(int i=0;i<8;i++) { cout<<p[i].pno<<"\t"<<p[i].flag<<"\t"<<p[i].addr<<"\t"; if(p[i].flag) cout<<p[i].cno; cout<<endl; } switch(a) { case 0:printf("\t\t\t再见!\t\t\t\n"); break; case 1: cout<<"请输入指令的逻辑地址:"; cin>>ins; changeaddr(p, ins);break; case 2: system("CLS"); a=wang();break; default:cout<<"输入有误,请重新输入!"<<endl;break; } } } void menu() { int a; printf("\t\t\t--------------------------------\n"); printf("\t\t\t☆☆欢迎使用分页模拟实验系统☆☆\n"); printf("\t\t\t---------------------------------\n"); printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); printf("\t\t\t☆☆1.输入指令 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆2.进入页面置换算法 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆0.EXIT ☆☆\n"); printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); printf("请选择所要执行的操作:"); scanf("%d",&a); switch(a) { case 0: printf("\t\t\t-再见!-\t\t\t\n");break; case 1: dizhizhuanhuan (); break; case 2: wang (); break; default:cout<<"输入有误,请重新输入!"<<endl;break; } } int main() { menu(); } //****************随机产生序列号函数 int* build() { printf("随机产生一个进程序列号为:\n"); int i=0; for(i=0; i<psize; i++) { pro[i]=10*rand()/(RAND_MAX+1)+1; printf("%d ", pro[i]); } printf("\n"); return(pro); } //***************************************查找空闲物理块 int searchpb() { for (j=0;j<bsize; j++) { if(phb[j] == 0) { m=j; return m; break; } } return -1; } //************************************查找相同进程 int searchpro() { for(j=0;j< bsize;j++) { if(phb[j] =pro[i]) { n=j; return j; } } return -1; } //*************************初始化内存 void empty() { for(i=0;i<bsize;i++) phb[i]=0; count=0; //计数器置零 } //******先进先出页面置换算法 void FIFO() { for( i=0; i<psize; i++) { // m=searchpb(); // n=searchpro(); //找到第一个空闲的物理快 for(j=0;j<bsize;j++) { if(phb[j] == 0){ m=j; break; } } //找与进程相同的标号 for(j=0;j<bsize;j++) { if(phb[j] == pro[i]){ n=j; } } //找flag值最大的 for(j=0;j<bsize;j++) { if(flag[j]>maxflag) { maxflag = flag[j]; mmax = j; } } if(n == -1)//不存在相同进程 { if(m != -1)//存在空闲物理块 { phb[m]=pro[i];//进程号填入该空闲物理块 // count++; flag[m]=0; for (j=0;j<=m; j++) { flag[j]++; } m=-1; } else//不存在空闲物理块 { phb[mmax] =pro[i]; flag[mmax] =0; for (j=0;j<bsize;j++) { flag[j]++; } mmax = -1; maxflag = 0; count++; } } else//存在相同的进程 { phb[n] = pro[i]; for(j=0;j<bsize;j++) { flag[j]++; } n=-1; } for(j=0;j < bsize;j++) { printf("%d ", phb[j]); } printf("\n"); } printf("缺页次数为:%d\n",count); printf("缺页率 :%16. 6f",(float)count/psize); printf("\n"); } /*初始化内存单元、缓冲区*/ void Init(Pagel *b,int c[bsize][psize]) { int i,j; for (i=0;i<psize;i++) { b[i].num=-1; b[i].time=psize-i-1; } for(i=0;i<bsize;i++) for(j=0;j<psize;j++) c[i][j]=-1; } /*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/ int GetMax(Pagel *b) { int i; int max=-1; int tag=0; for(i=0;i<bsize;i++) { if(b[i].time>max) { max=b[i].time; tag= i; } } return tag; } /*判断页面是否已在内存中*/ int Equation(int fold, Pagel *b) { int i; for(i=0;i<bsize;i++) { if(fold==b[i]. num) return i; } return -1; } /*LRU核心部分*/ void Lruu(int fold, Pagel *b) { int i; int val; val=Equation(fold, b); if (val>=0) { b[val].time=0; for(i=0;i<bsize;i++) if (i!=val) b[i].time++; } else { queue[++k]=fold;/*记录调入页面*/ val=GetMax(b); b[val].num=fold; b[val].time=0; for (i=0;i<bsize;i++){ // URLcount++; if (i!=val) b[i].time++; } } } void LRU() { int i,j; k=0; Init(b, c); for(i=0; i<psize; i++) { Lruu(pro[i],b); c[0][i]=pro[i]; /*记录当前的内存单元中的页面*/ for(j=0;j<bsize;j++) c[j][i]=b[j].num; } /*结果输出*/ printf("内存状态为:\n"); Myprintf; for(j=0;j<psize;j++) printf("|%2d", pro[j]); printf("|\n"); Myprintf; for(i=0;i<bsize;i++) { for(j=0; j<psize; j++) { if(c[i][j]==-1) printf("|%2c",32); else printf("|%2d",c[i][j]); } printf("|\n"); } Myprintf; // printf("\n调入队列为:"); // for(i=0;i<k;i++) // printf("%3d", queue[i]); printf("\n缺页次数为:%6d\n 缺页率 :%16. 6f", k+1,(float)(k+1)/psize); } //********主函数 int wang() { int sel; do{ printf("\t\t\t--------------------------------\n"); printf("\t\t\t☆☆欢迎使用分页模拟实验系统☆☆\n"); printf("\t\t\t---------------------------------\n"); printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); printf("\t\t\t☆☆ 虚拟内存 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆1.产生随机序列 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆2.最近最久未使用 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆3.先进先出 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆0.退出 ☆☆\n"); printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); printf("请选择所要执行的操作:"); scanf("%d",&sel); switch(sel) { case 0: printf("\t\t\t再见!t\t\t\n"); break; case 1: build(); break; case 2: printf("最近最久未使用\n"); LRU();empty(); printf("\n");break; case 3: printf("先进先出算法\n"); FIFO();empty();printf("\n");break; default:printf("请输入正确的选项号!");printf("\n\n");break; } }while(sel !=0 ); return sel; }
这篇关于先进先出(FIFO)页面置换算法C语言实现、最近最久未使用(LRU)页面置换算法C语言实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01lip-sync公司指南:一文读懂主要玩家和技术
- 2024-11-01Anthropic的新RAG方法——提升大型语言模型在特定领域的表现
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享