虚拟页面置换算法FIFO、LRU、OPT(2020-12-07)

#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

const int N = 50;
int buff[N];//从下标1开始
int time_who[N];    //time_who[i] 用于标记页面i的最久未使用时间，值越大，说明最久没有使用
bool flag = true, flag2 = true, book = false;
int memory[4]; //1~3
bool exist[4];  //1~3
int memory_where[4]; //1~3
int n;

queue<int> q, memory_q, swap_q;
void fifo(); //先来先出
void lru();//最近最久未使用
void opt(); //理想型置换算法

int ans, sum;


int main()
{
    cout<<"输入页面访问顺序次数：";
    cin>>n;
    sum = n;
    cout<<"输入页面访问顺序：";
    for(int i = 1; i <= n; ++i)
    {
        cin>>buff[i];
        q.push(buff[i]);
    }
    cout<<"选择页面置换算法： 1.FIFO算法       2、LRU算法     3、OPT算法"<<endl;
    int which;
    cin>>which;
    switch(which)
    {
        case 1:
            fifo();
            break;
        case 2:
            lru();
            break;
        case 3:
            opt();
            break;
    }
    return 0;
}

void fifo()
{
    while(q.size())
    {
        int t = q.front();
        q.pop();
        flag = false;
        while(memory_q.size())
        {
            if(memory_q.front() == t)
            {
                flag = true;                //三个页框存在该页面
                ans++;
                
            }
            int x = memory_q.front();
            
            swap_q.push(x);
            memory_q.pop();
        }
        if(swap_q.size() != 0)
            cout<<"------>>>>>页框中已经存在页面：";
        while(swap_q.size())
        {
            int x = swap_q.front();
            cout<<x<<" ";
            memory_q.push(x);
            swap_q.pop();
        }
        
        if(memory_q.size() != 0)
            cout<<"<<<<<------"<<endl;
        if((memory_q.size() == 3) && !flag)
        {
            int front = memory_q.front();
            cout<<"正在将页面:"<<front<<"换出";
            book = true;
            memory_q.pop();
        }
        if(!flag)
        {
            if(book)
            {
                book = false;
                cout<<",同时正在将页面:"<<t<<"调入内存"<<endl;
            }
            else
            {
                cout<<"准备将页面"<<t<<"调入内存"<<endl;
            }
            memory_q.push(t);
        }
        else
        {
            cout<<"[------页框中已经存在页面:"<<t<<"------]"<<endl;
        }
    }
    while(memory_q.size())
    {
        int x = memory_q.front();
        swap_q.push(x);
        memory_q.pop();
    }
    if(swap_q.size() != 0)
        cout<<"------>>>>>页框中已经存在页面：";
    while(swap_q.size())
    {
        int x = swap_q.front();
        cout<<x<<" ";
        memory_q.push(x);
        swap_q.pop();
    }
    if(memory_q.size() != 0)
        cout<<"<<<<<------"<<endl;
    
    printf("缺页率为：%.2f%%\n", (sum-ans)*100.0/sum);
    return ;
}

void lru()
{
    while(q.size())
    {
        int t = q.front();
        q.pop();
        flag = false;
        flag2 = false;
        while(memory_q.size())
        {
            if(memory_q.front() == t)
            {
                ans++;
                time_who[t] = 0;
                flag = true;                //???
                flag2 = true;
            }
            int x = memory_q.front();
            
            if(!flag2)
            {
                time_who[x]++;
            }
            else
            {
                flag2 = false;
            }
            swap_q.push(x);
            memory_q.pop();
        }
        
        if(swap_q.size() != 0)
            cout<<"------>>>>>页框中已经存在页面：";
        while(swap_q.size())
        {
            int x = swap_q.front();
            cout<<x<<" ";
            memory_q.push(x);
            swap_q.pop();
        }
        
        if(memory_q.size() != 0)
            cout<<"<<<<<------"<<endl;
        
        int max_time = -1, cnt = 1;
        for(int i = 0; i < 10; ++i)
        {
//            cout<<"i :"<<i<<"   time:"<<time_who[i]<<endl;
            if(max_time < time_who[i])
            {
                max_time = time_who[i];
                cnt = i;
            }
        }
//        cout<<"cnt: "<<cnt<<"    max: "<<time_who[cnt]<<endl;
        if((memory_q.size() == 3) && !flag)
        {
            while(memory_q.size())
            {
                if(memory_q.front() == cnt)
                {
                    cout<<"正在将页面："<<memory_q.front()<<"换出";
                    time_who[cnt] = 0;
                    memory_q.pop();
                    continue;
                }
                int x = memory_q.front();
                swap_q.push(x);
                memory_q.pop();
            }
            while(swap_q.size())
            {
                int x = swap_q.front();
                memory_q.push(x);
                swap_q.pop();
            }
            book = true;            //发生了置换操作
        }
        if(!flag)
        {
            if(book)
            {
                book = false;
                cout<<",同时正在将页面:"<<t<<"调入内存"<<endl;
            }
            else
            {
                cout<<"准备将页面"<<t<<"调入内存"<<endl;
            }
            memory_q.push(t);
        }
        else
        {
            cout<<"[------页框中已经存在页面:"<<t<<"------]"<<endl;
        }
    }
    while(memory_q.size())
    {
        int x = memory_q.front();
        swap_q.push(x);
        memory_q.pop();
    }
    if(swap_q.size() != 0)
        cout<<"------>>>>>页框中已经存在页面：";
    while(swap_q.size())
    {
        int x = swap_q.front();
        cout<<x<<" ";
        memory_q.push(x);
        swap_q.pop();
    }
    if(memory_q.size() != 0)
        cout<<"<<<<<------"<<endl;
    
    printf("缺页率为：%.2f%%\n", (sum-ans)*100.0/sum);
    return ;
}

void opt()
{
    int which_buff = 1;  //下标
    memory[1] = buff[which_buff++];
    ans = 1;
    cout<<"------>>>>>页框中已经存在页面："<<memory[1]<<"<<<<<------"<<endl;
    for(int i = 2; i <= 3;)
    {
        book = false;
        for(int k = 1; k < i; ++k)
        {
            if(memory[k] == buff[which_buff])
            {
                ans++;
                book = true;
                cout<<"[------页框中已经存在页面:"<<buff[which_buff]<<"------]"<<endl;
                break;
            }
        }
        if(book)
        {
            which_buff++;
            
            continue;
        }
        else
        {
            memory[i] = buff[which_buff];
            which_buff++;
            i++;
        }
        cout<<"------>>>>>页框中已经存在页面：";
        for(int j = 1; j < i; ++j)
        {
            cout<<memory[j]<<" ";
        }
        cout<<"<<<<<------"<<endl;
    }

    
//    cout<<which_buff<<endl;
    while(which_buff != n+1)
    {
        
        for(int i = 1; i <= 3; ++i)
        {
            if(memory[i] == buff[which_buff])
            {
                ans++;
                cout<<"[------页框中已经存在页面:"<<buff[which_buff]<<"------]"<<endl;;
                which_buff++;
                flag = false;
                break;
            }
        }
        if(!flag)
        {
            flag = true;
            continue;
        }
        if(which_buff == n)
        {
            memory[1] = buff[which_buff];
            cout<<"------>>>>>页框中已经存在页面：";
            for(int i = 1; i <= 3; ++i)
            {
                cout<<memory[i]<<" ";
            }
            cout<<"<<<<<------"<<endl;
            which_buff++;
            
            continue;
        }
        
        for(int i = 1; i <= 3; ++i)
        {
            exist[i] = false;
        }
        for(int i = 1; i <= 3; ++i)
        {
            for(int j = which_buff+1; j <= n; ++j)
            {
                if(memory[i] == buff[j])
                {
                    exist[i] = true;
                    memory_where[i] = j;  //内存中第i的页面在以后第一次出现是第j次
//                    cout<<memory[i]<<"此后第一次出现的位置是："<<memory_where[i]<<endl;
                    break;
                }
            }
            if(!exist[i])  //如果内存中的此页面在以后没有出现，则替换此页面
            {
                cout<<"*****页面："<<memory[i]<<"此后不会再出现了*****";
                cout<<"正在将页面:"<<memory[i]<<"换出";
                memory[i] = buff[which_buff];
                cout<<",同时正在将页面:"<<buff[which_buff]<<"调入内存"<<endl;
                break;
            }
            else if(i == 3)  //说明同时内存中的页面在以后的都再次出现，则要找哪个页面最后出现，即哪个memory_where[i]最大
            {
                int cnt = 1, max_co = -1;
                for(int k = 1; k <= 3; ++k)
                {
                    if(max_co < memory_where[k])
                    {
                        max_co = memory_where[k];
                        cnt = k;
                    }
                }
                exist[cnt] = false;
                cout<<"正在将页面:"<<memory[cnt]<<"换出";
                memory[cnt] = buff[which_buff];
                cout<<",同时正在将页面:"<<buff[which_buff]<<"调入内存"<<endl;
                break;
            }
        }
        cout<<"------>>>>>更新后存在的页面为：";
        for(int i = 1; i <= 3; ++i)
        {
            cout<<memory[i]<<" ";
        }
        cout<<"<<<<<------"<<endl;
        which_buff++;
    }
//    cout<<ans<<endl;
    ans--;
    printf("缺页率为：%.2f%%\n", (sum-ans)*100.0/sum);
    return ;
}