页面置换算法——FIFO、LRU

#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 n;

queue<int> q, memory_q, swap_q;
void fifo(); //先来先出
void lru();//最近最久未使用
double ans, sum;


int main()
{
    cout<<"输入页面访问顺序次数：";
    cin>>n;
    sum = n;
    cout<<"输入页面访问顺序：";
    for(int i = 0; i < n; ++i)
    {
        cin>>buff[i];
        q.push(buff[i]);
    }
    cout<<"选择页面置换算法： 1.FIFO算法       2、LRU算法"<<endl;
    int which;
    cin>>which;
    switch(which)
    {
        case 1:
            fifo();
            break;
        case 2:
            lru();
            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;
    ans = (sum-ans)/sum;
    
    printf("缺页率为：%.4f\n", ans);
    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;
    ans = (sum-ans)/sum;
    
    printf("缺页率为：%.4f\n", ans);
    return ;
}