欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

页面置换算法FIFO、OPT、LRU

程序员文章站 2022-07-05 08:10:42
...

FIFO——先进先出置换算法
OPT——最佳置换算法
LRU——最近最久未使用算法

#include<iostream>
#include<cstdio>
#include<queue>
#define M 3

using namespace std;
void FIFO();
void OPT();
void LRU();
void printMemory();
int search();

struct page{
    int k;//页面号
    int i;//顺序
}memory[M+1];
page arr[1000000];//OPT算法中使用,存储后序节点
int n;
queue<int> q;
int flag=0;
int j=0;//1=<j<=M,记录当前内存中页面个数
int num=0;//次序
int cnt;//成功访问的次数

int main(){
    cout<<"输入页面访问顺序次数:";
    cin>>n;
    cout<<"输入页面访问顺序:";
    int x;
    for(int i = 1; i <=n; ++i)
    {
        cin>>x;
        q.push(x);
        arr[i].k=x;//记录页号
        arr[i].i=i;//记录次序
    }
    cout<<"选择页面置换算法: 1.FIFO算法  2.最佳置换OPI算法     3、LRU算法"<<endl;
    
    
    int which;
    cin>>which;
    cout<<"运行过程如下:"<<endl;
    switch(which){
        case 1:
            FIFO();
            break;
        case 2:
            OPT();
            break;
        case 3:
            LRU();
            break;
    }
    cout<<"缺页率为:"<<(n-cnt)*100/n<<"%"<<endl;
    return 0;
}
void FIFO(){
    while(q.size()){
        num++;
        int t=q.front();
        q.pop();
        cout<<"------------------正在请求页面"<<t<<"...------------------"<<endl;
        for(int i=1;i<=j;i++){
            if(memory[i].k==t){
                flag=1;//页面在内存中
                cnt++;
                cout<<"---页面"<<t<<"在内存中,成功访问"<<endl;
                break;
            }
        }
        if(!flag && j==M){//需要置换
            int minx=1;//存储最早来的节点的下标
            for(int i=2;i<=j;i++){
                if(memory[i].i<memory[minx].i)
                    minx=i;
            }
            cout<<"---正在将页面"<<memory[minx].k<<"移出内存..."<<endl;
            memory[minx].k=t;
            memory[minx].i=num;
            cout<<"---正在将页面"<<t<<"装入内存..."<<endl;
        }
        if(!flag && j<M){//直接放入内存
            j++;
            memory[j].k=t;
            memory[j].i=num;
            cout<<"---正在将页面"<<t<<"装入内存..."<<endl;
        }

        flag=0;
        printMemory();
    }

}
void OPT(){
    while(q.size()){
        num++;
        int t=q.front();
        q.pop();

        cout<<"------------------正在请求页面"<<t<<"...------------------"<<endl;
        for(int i=1;i<=j;i++){
            if(memory[i].k==t){
                flag=1;//页面在内存中
                cnt++;
                cout<<"---页面"<<t<<"在内存中,成功访问"<<endl;
                break;
            }
        }
        if(!flag && j==M){//需要置换
            int index= search();//调用搜索函数,找到符合条件的节点的下标
            cout<<"---正在将页面"<<memory[index].k<<"移出内存..."<<endl;
            memory[index].k=t;
            cout<<"---正在将页面"<<t<<"装入内存..."<<endl;
        }
        if(!flag && j<M){//直接放入内存
            j++;
            memory[j].k=t;
            cout<<"---正在将页面"<<t<<"装入内存..."<<endl;
        }

        flag=0;
        printMemory();
    }
}
void LRU(){
    
    while(q.size()){
        num++;
        int t=q.front();
        q.pop();

        cout<<"------------------正在请求页面"<<t<<"...------------------"<<endl;
        for(int i=1;i<=j;i++){
            if(memory[i].k==t){
                flag=1;//页面在内存中
                cnt++;
                memory[i].i=num;//更新顺序
                cout<<"---页面"<<t<<"在内存中,成功访问"<<endl;
                break;
            }
        }
        if(!flag && j==M){//需要置换
                int longx=1;//存储最近最久没有被访问的节点的下标
                for(int i=2;i<=j;i++){
                    if(memory[i].i<memory[longx].i)
                        longx=i;
                }
                cout<<"---正在将页面"<<memory[longx].k<<"移出内存..."<<endl;
                memory[longx].k=t;
                memory[longx].i=num;
                cout<<"---正在将页面"<<t<<"装入内存..."<<endl;
        }
        if(!flag && j<M){//直接放入内存
            j++;
            memory[j].k=t;
            memory[j].i=num;
            cout<<"---正在将页面"<<t<<"装入内存..."<<endl;
        }
        flag=0;
        printMemory();
    }
    
}

void printMemory(){
    for(int i=1;i<=j;i++){
        cout<<"页面"<<memory[i].k;
    }
    cout<<endl;
}
//用于OPT算法中找到最长时间内不再被访问的页面
int search(){
    int index=1;
    int temp[M+1];
    for(int i=1;i<=j;i++){
        for(int m=num+1;m<=n;m++){
            if(memory[i].k==arr[m].k){
                temp[i]=m;//将内存中各个页面在未来第一次出现时的下标记录下来
                break;
            }
            else
                temp[i]=INT_MAX;
        }    
    }
    for(int i=2;i<=j;i++){
        if(temp[i]>temp[index]){
            index=i;
        }
    }
    return index;    
}
相关标签: 算法 操作系统