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）），直到物理块被填满。

voidinitial(){int i,j,k;int z=0;bool found;
    LackPageNum = BlockNum; 
    LackPageRate =0.0;for(int i =0;i<PageNum;i++){
        PageCount[i]=0; 
        VirtualQueue[i]=-1;}for(int i=0;i<BlockNum;i++){for(int j=0;j<PageNum;j++){
            Simulate[i][j]=-1;}}for(int i =0;i<PageNum;i++){ 
        found =false;
        timeOfLRU[i]=0;for(int j =0;j<BlockNum;j++){if(VirtualQueue[j]== PageOrder[i]){
                found =true;}}if(!found){ 
            VirtualQueue[z]= PageOrder[i];for(int j=0;j<=z;j++){
            Simulate[j][i]=VirtualQueue[j];}
            z++;for(int k =0;k<i;k++){
                timeOfLRU[k]++;}}else{
            timeOfLRU[i]=0;}if(z==BlockNum){break;}}}

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

voidFIFO(){
    cout<<"当前选择的算法:FIFO"<<endl;initial();int i,j,k;int point =0;for(int i = BlockNum;i<PageNum;i++){
        found =false;for(int k =0;k<BlockNum;k++){if(VirtualQueue[k]== PageOrder[i]){ 
                found =true;}}if(!found){  
            LackPageNum++; 
            VirtualQueue[point]= PageOrder[i];for(int j=0;j<=BlockNum;j++){
            Simulate[j][i]=VirtualQueue[j];}
            point++;if(point == BlockNum) 
                point =0;}}output();
    LackPageRate =(LackPageNum *1.0)/PageNum;
    cout<<"LackPageNum: "<<LackPageNum<<endl;
    cout<<"LackPageRate: "<<LackPageRate<<endl;}

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

voidOPI(){
    cout<<"当前选择的算法:OPI"<<endl;int i,j,s,k,m,t;initial();int distance;int point;for(i = BlockNum;i<PageNum;i++){
        found =false;for(k =0;k<BlockNum;k++){if(VirtualQueue[k]== PageOrder[i]){ 
                found =true;}}if(!found){
            LackPageNum++;for(s =0;s < BlockNum;s++){
                distance =1;for(t = i;t<PageNum;t++){if(VirtualQueue[s]!= PageOrder[t])
                        distance++;elsebreak;}
                PageCount[s]= distance;}
            point =0;for(m =1;m < BlockNum;m++){if(PageCount[point]< PageCount[m])
                    point = m;}
            VirtualQueue[point]= PageOrder[i];for(j=0;j<=BlockNum;j++){
            Simulate[j][i]=VirtualQueue[j];}}}output();
    LackPageRate =(LackPageNum*1.0)/PageNum;
    cout<<"LackPageNum: "<<LackPageNum<<endl;
    cout<<"LackPageRate: "<<LackPageRate<<endl;}

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

voidLRU(){
    cout<<"当前选择的算法:LRU"<<endl;int i,j,s,k;initial();int point;for(i = BlockNum;i<PageNum;i++){
        found =false;for(k =0;k<BlockNum;k++){if(VirtualQueue[k]== PageOrder[i])   
                  found =true;}if(!found){
            LackPageNum++;
            point =0;for(j =1;j<BlockNum;j++){if(timeOfLRU[point]<timeOfLRU[j])
                    point = j;}for(s =0;s<BlockNum;s++){if(VirtualQueue[s]!= VirtualQueue[point])
                    timeOfLRU[s]++;}
            VirtualQueue[point]= PageOrder[i];for(j=0;j<=BlockNum;j++){
            Simulate[j][i]=VirtualQueue[j];}
            timeOfLRU[point]=0;}else{for(s =0;s<BlockNum;s++){if(VirtualQueue[s]!= PageOrder[i])
                    timeOfLRU[s]++;else
                    timeOfLRU[s]=0;}}}output();
    LackPageRate =(LackPageNum*1.0)/PageNum;
    cout<<"LackPageNum: "<<LackPageNum<<endl;
    cout<<"LackPageRate: "<<LackPageRate<<endl;}

4.运行结果

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

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

在这里插入图片描述

5.程序源码

#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(){
     ifstream readData;
    readData.open("data.txt");
    readData>>BlockNum;
    readData>>PageNum;for(int i=0;i<PageNum;i++){
        readData>>PageOrder[i];}
    
    cout<<"最小物理块数 = "<<BlockNum<<endl;
    cout<<"页面个数 = "<<PageNum<<endl;
    cout<<"页面序列:"<<endl;for(int i =0;i<PageNum;i++){
        cout<<PageOrder[i]<<" ";}
    cout<<endl;}voidinitial(){//初始化 int i,j,k;int z=0;//判断初始化物理块是否填满bool found;
    LackNum = BlockNum;//缺页数=物理块数+缺页次数
    LackPageRate =0.0;for(int i =0;i<PageNum;i++){
        PageCount[i]=0;//初始化距离
        memoryPage[i]=-1;//初始化队列}for(int i=0;i<BlockNum;i++){for(int j=0;j<PageNum;j++){
            Simulate[i][j]=-1;//初始化}}for(int i =0;i<PageNum;i++){//初始化物理块
        found =false;
        timeOfLRU[i]=0;for(int j =0;j<BlockNum;j++){if(memoryPage[j]== PageOrder[i])//页面命中{
                found =true;}}if(!found){//当有新的进程进入到队列时，便计算其对应的距离
            memoryPage[z]= PageOrder[i];//小于物理块数时，页面顺序进入队列for(int j=0;j<=z;j++){
            Simulate[j][i]=memoryPage[j];//保存当前序列的值}
            z++;for(int k =0;k<i;k++){
                timeOfLRU[k]++;//之前的页面对应的时间+1}}else{
            timeOfLRU[i]=0;//重新更新为0，表示最近刚刚使用}if(z==BlockNum){//物理块被填满，结束循环 break;}}}voidFIFO(){
    cout<<"当前选择的算法:FIFO"<<endl;initial();int i,j,k;int point =0;//分配内存for(int i = BlockNum;i<PageNum;i++){
        found =false;for(int k =0;k<BlockNum;k++){if(memoryPage[k]== PageOrder[i]){//页面命中
                found =true;}}if(!found){//如果页面不在队列中，则进行相应的处理
            LackNum++;//缺页数加1
            memoryPage[point]= PageOrder[i];//页面替换队列中最老的for(int j=0;j<=BlockNum;j++){
            Simulate[j][i]=memoryPage[j];//保存当前序列的值}
            point++;//后移if(point == BlockNum)//当指向队尾时后，重新指向队首
                point =0;}}output();//输出物理块状态
    LackPageRate =(LackNum *1.0)/PageNum;
    cout<<"缺页数：: "<<LackNum<<endl;
    cout<<"缺页率：: "<<LackPageRate<<endl;}voidOPI(){
    cout<<"当前选择的算法:OPI"<<endl;int i,j,s,k,m,t;initial();int distance;//表示队列每个值距离下一次访问的距离int point;//指向最长时间未被访问的下标for(i = BlockNum;i<PageNum;i++){
        found =false;for(k =0;k<BlockNum;k++){if(memoryPage[k]== PageOrder[i]){//页面命中
                found =true;}}if(!found){
            LackNum++;//计算当前队列每一页对应的下一次出现的距离for(s =0;s < BlockNum;s++){
                distance =1;for(t = i;t<PageNum;t++){//向后找离他最远的if(memoryPage[s]!= PageOrder[t])
                        distance++;elsebreak;}
                PageCount[s]= distance;//当前内存距离下一次出现的距离}//向后比较队列内最长时间不被访问的并淘汰，置换页面
            point =0;for(m =1;m < BlockNum;m++){if(PageCount[point]< PageCount[m])
                    point = m;}
            memoryPage[point]= PageOrder[i];for(j=0;j<=BlockNum;j++){
            Simulate[j][i]=memoryPage[j];//保存当前序列的值}}}output();
    LackPageRate =(LackNum*1.0)/PageNum;
    cout<<"缺页数：: "<<LackNum<<endl;
    cout<<"缺页率：: "<<LackPageRate<<endl;}voidLRU(){
    cout<<"当前选择的算法:LRU"<<endl;int i,j,s,k;initial();int point;//指向最长时间未被访问的下标for(i = BlockNum;i<PageNum;i++){
        found =false;for(k =0;k<BlockNum;k++){if(memoryPage[k]== PageOrder[i])//页面命中
                  found =true;}if(!found){
            LackNum++;//向前比较队列内最长时间不被访问的并淘汰，置换页面
            point  =0;for(j =1;j<BlockNum;j++){if(timeOfLRU[point]<timeOfLRU[j])
                    point = j;}for(s =0;s<BlockNum;s++){//其余页面对应的时间要+1if(memoryPage[s]!= memoryPage[point])
                    timeOfLRU[s]++;}
            
            memoryPage[point]= PageOrder[i];for(j=0;j<=BlockNum;j++){
            Simulate[j][i]=memoryPage[j];//保存当前序列的值}
            timeOfLRU[point]=0;}else{//负责更新当前对应页面的时间for(s =0;s<BlockNum;s++){//其余页面对应的时间要+1if(memoryPage[s]!= PageOrder[i])
                    timeOfLRU[s]++;else
                    timeOfLRU[s]=0;}}}output();
 
    LackPageRate =(LackNum*1.0)/PageNum;
    cout<<"缺页数：: "<<LackNum<<endl;
    cout<<"缺页率：: "<<LackPageRate<<endl;}voidchooseAlgorithm(){
    cout<<"请选择算法“1-先进先出(FIFO)页面置换算法，2-最佳(Optimal)置换算法，3-最近最久未使用(LRU)页面置换算法，0-结束”"<<endl;
    cin>>choose;
    cout<<endl;if(choose==1){FIFO();chooseAlgorithm();}elseif(choose==2){OPI();chooseAlgorithm();}elseif(choose==3){LRU();chooseAlgorithm();}elseif(choose==0){exit(0);}else{
        cout<<"输入错误“1-首次适应算法FF，2-循环首次适应算法NF，3-最佳适应算法BF，4-最坏适应算法WF，0-退出”"<<endl;chooseAlgorithm();}}voidoutput(){int i,j;for(i=0;i<PageNum;i++){
        cout<<PageOrder[i]<<"  ";}
    cout<<endl;for(i=0;i<BlockNum;i++){for(j=0;j<PageNum;j++){if(Simulate[i][j]==-1){
                    cout<<"   ";}else{
            cout<<"  "<<Simulate[i][j];}}
        cout<<endl;}}

输入数据格式

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

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

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

249基于java ssm springboot安全生产培训管理系统学习课件（源码+文档+运行视频+讲解视频）

【Linux庖丁解牛】—软件安装&vim！

【花雕学编程】Arduino LVGL 之在不同平台创建相同的用户界面

基于电商大数据的商品推荐系统

UE5.4像素流及前端接入

Unity中接入讯飞语音（实时语音转写）WebAPI（非SDK）

springboot实现获取客户端IP地址

文章导航