页面置换算法FIFO、OPT、LRU

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;    
}