虚拟内存页面置换算法（操作系统）-Toy模板网

这篇具有很好参考价值的文章主要介绍了虚拟内存页面置换算法（操作系统）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

虚拟内存页面置换算法

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

void initial(){ 
    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））。

void FIFO(){
	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））。

void OPI(){
	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++;
                    else
                        break;
                }
                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））。

void LRU(){
	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.首先输入物理块数，页面个数和页面序列，之后程序输出对应的数据验证，并提示选择算法
页面置换算法模拟实验内容和步骤,操作系统,算法,数据结构,windows,经验分享,c++

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

页面置换算法模拟实验内容和步骤,操作系统,算法,数据结构,windows,经验分享,c++

5.程序源码

#include <iostream>
#include <fstream>
#include <iomanip>
#include <stdlib.h>
using namespace std;
 
#define MaxNumber 100
int 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;

void input();  //输入
void initial();  //初始化物理块
void FIFO();    
void OPI();     
void LRU();   
void chooseAlgorithm();//选择算法
void output(); //输出 


int main(){
    input();
   	chooseAlgorithm();
    return 0;
}
 
void input(){
 	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;
}
 
void initial(){//初始化 
    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;
           }
    }
}
 
void FIFO(){
	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;
}

void OPI(){
	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++;
                    else
                        break;
                }
                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;
}
 
void LRU(){
	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++){//其余页面对应的时间要+1
                if (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++){//其余页面对应的时间要+1
                if (memoryPage[s] != PageOrder[i])
                    timeOfLRU[s]++;
                else
                    timeOfLRU[s] = 0;
            }
        }
    }
    output();
 
    LackPageRate = (LackNum*1.0)/PageNum;
    cout<<"缺页数：: "<<LackNum<<endl;
    cout<<"缺页率：: "<<LackPageRate<<endl;
}
 
void chooseAlgorithm()
{
	cout<<"请选择算法“1-先进先出(FIFO)页面置换算法，2-最佳(Optimal)置换算法，3-最近最久未使用(LRU)页面置换算法，0-结束”"<<endl;
	cin>>choose;
	cout<<endl;
	if (choose==1)
	{
		FIFO();
		chooseAlgorithm();
	}
		else if(choose==2)
		{
			OPI();
			chooseAlgorithm();
		}
		else if(choose==3){
            LRU();
            chooseAlgorithm();
		}
 
		else if(choose==0){
          exit(0);
		}
	else
	{
		cout<<"输入错误“1-首次适应算法FF，2-循环首次适应算法NF，3-最佳适应算法BF，4-最坏适应算法WF，0-退出”"<<endl;
		chooseAlgorithm();  
	}
}

void output(){
    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;
    }
}

输入数据格式文章来源地址https://www.toymoban.com/news/detail-764422.html

3
20
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

到了这里，关于虚拟内存页面置换算法（操作系统）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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