C++实现虚拟内存页面置换算法（FIFO， OPT， LRU）

妖狐艹你老母 2022-12-23 00:42 448阅读 0赞

## 虚拟内存页面置换算法（FIFO， OPT， LRU） ##

## 0x01 FIFO ##

*  置换策略：置换掉先来的页面(FIFO队列首元素)
 *  优点： 简单易理解且易实现
 *  缺点： 性能不理想，会发生**Belady异常**（页框（帧）增加缺页率也增加）

## 0x02 OPT ##

最优页面置换算法（optimal page-replacement algorithm）

*  置换策略：根据以后使用情况置换:  
    置换掉以后不再用；如果没有不再使用的，置换掉相对最迟使用的。
 *  优点：它是**最优**的页面置换算法，不会发生Belady异常
 *  缺点：需要知道以后页面使用情况，实现起来困难

## 0x03 LRU ##

最近最少使用算法（Least-Recent-Used algorithm）

*  置换策略：根据最近使用情况（上次使用时间）置换：置换掉相对当前时刻最长时间没有使用的页面  
    （相对而言，最近刚用的不置换）
 *  优点：近似最优，没有Belady异常
 *  缺点：可能需要重要的硬件辅助，实现上比较困难

## 代码 ##

> 以下根据个人思路所写,仅供参考

#include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    const int MAX_SIZE = 1e3+5;
    const  int INF = 0x3f3f3f3f;
    int pg_last[MAX_SIZE]; //last time of using page
    bool vis[MAX_SIZE]; //marked in queue
    
    class Node
    {
        
    public:
        int node[MAX_SIZE];
        int iSize;
        int cur;
        bool isFull();
        bool exist(int x);
        Node()
        {
        
            cur = 0;
        }
        Node(int sz)
        {
        
            iSize = sz;
            cur = 0;
        }
    };
    
    // struct Pair 辅助OPT
    struct Pair
    {
        
        int pos;
        int id;
        bool operator<(const Pair x)const
        {
        
            return id > x.id;
        }
    } op[MAX_SIZE];
    
    
    bool Node::isFull()
    {
        
        return cur == iSize;
    }
    
    void createPages(int n,Node &pg)
    {
        
        cout<<"请输入长度为"<<n<<"的页面访问序列：";
        pg.iSize = n;
        for(int i = 0; i < n; ++i)
        {
        
            cin>>pg.node[i];
        }
    }
    
    void printResult(int n,int fail_cnt,int replace_cnt)
    {
        
        double fail_rate = fail_cnt / double(n) * 100;
        cout<<" fail times: "<<fail_cnt<<" fail_rate: "<<fail_rate<<"%"<<endl;
        cout<<" replace times: "<<replace_cnt<<endl;
        cout<<"--------------------------------------"<<endl;
    }
    
    bool Node::exist(int x)
    {
        
        for(int i = 0; i < cur; ++i)
        {
        
            if(x == node[i])
            {
        
                return true;
            }
        }
        return false;
    }
    
    void FIFO(int m,Node pg)
    {
        
        Node st(m); // storage
        int fail_cnt = 0;
        int replace_cnt = 0;
        queue<int>q;
        memset(vis,false,sizeof(vis));
        for(int i = 0; i < pg.iSize; ++i)
        {
        
            if(vis[pg.node[i]]) continue;
            if(int(q.size()) < m)
            {
        
                q.push(pg.node[i]);
                vis[pg.node[i]] = true;
                fail_cnt++;
            }
            else
            {
        
                int aim = q.front();
                q.pop();
                vis[aim] = false;
                q.push(pg.node[i]);
                vis[pg.node[i]] = true;
                fail_cnt++;
                replace_cnt++;
            }
        }
        cout<<"-------------FIFO Result--------------"<<endl;
        printResult(pg.iSize,fail_cnt,replace_cnt);
    }
    
    int findRepOPT(int s,Node st,Node pg)
    {
        
        int k = 0;
        bool flag; // 标记以后是否会使用
        for(int i = 0; i < st.iSize; ++i)
        {
        
            flag = false;
            for(int j = s; j < pg.iSize; ++j)
            {
        
                if(st.node[i] == pg.node[j])
                {
        
                    flag = true;
                    op[k].id = j;
                    op[k++].pos = i;
                    break;
                }
            }
            if(!flag)
            {
        
                return i;
            }
        }
        sort(op,op+k);
        return op[0].pos;
    }
    
    void OPT(int m,Node pg)
    {
        
        Node st(m); // storage
        int fail_cnt = 0;
        int replace_cnt = 0;
        for(int i = 0; i < pg.iSize; ++i)
        {
        
            if(st.exist(pg.node[i])) continue;
            if(!st.isFull())
            {
        
                st.node[st.cur++] = pg.node[i];
                fail_cnt++;
            }
            else
            {
        
                int pos = findRepOPT(i,st,pg);
                st.node[pos] = pg.node[i];
                fail_cnt++;
                replace_cnt++;
            }
        }
        cout<<"-------------OPT Result--------------"<<endl;
        printResult(pg.iSize,fail_cnt,replace_cnt);
    }
    
    int findRepLRU(Node st)
    {
        
        int minx = INF,pos = 0;
        for(int i = 0; i < st.iSize; ++i)
        {
        
            if(pg_last[st.node[i]] < minx)
            {
        
                minx = pg_last[st.node[i]];
                pos = i;
            }
        }
        return pos;
    }
    
    void LRU(int m,Node pg)
    {
        
        Node st(m); // storage
        int fail_cnt = 0;
        int replace_cnt = 0;
        for(int i = 0; i < pg.iSize; ++i)
        {
        
            pg_last[pg.node[i]] = i;
            if(st.exist(pg.node[i])) continue;
            if(!st.isFull())
            {
        
                st.node[st.cur++] = pg.node[i];
                fail_cnt++;
            }
            else
            {
        
                int pos = findRepLRU(st);
                st.node[pos] = pg.node[i];
                fail_cnt++;
                replace_cnt++;
            }
        }
        cout<<"-------------LRU Result--------------"<<endl;
        printResult(pg.iSize,fail_cnt,replace_cnt);
    
    }
    
    
    int main()
    {
        
        /*
        3 12
        2 3 2 1 5 2 4 5 3 2 5 2
        */
        /*
        3 20
        7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
        */
        int m,n;
        cout<<"请输入分配给进程的页框数 和 进程页面数:";
        cin>>m>>n;
        Node pg;
        createPages(n,pg);
        cout<<"-------------选择页面置换算法---------------"<<endl;
        cout<<"-------------1.FIFO---------------"<<endl;
        cout<<"-------------2.OPT---------------"<<endl;
        cout<<"-------------3.LRU---------------"<<endl;
        cout<<"-------------0.退出---------------"<<endl;
        int op;
        while(cin>>op)
        {
        
            switch(op)
            {
        
            case 1:
                FIFO(m,pg);
                break;
            case 2:
                OPT(m,pg);
                break;
            case 3:
                LRU(m,pg);
                break;
            case 0:
                exit(0);
            }
        }
    
        return 0;
    }

## 运行实例 ##

3 12
     2 3 2 1 5 2 4 5 3 2 5 2

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70_pic_center]

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/4ef81c2d3cdc48e7b18cea383c9c567d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/62dc73bf568f48daaf9b37f5417c8d03.png