opt,fifo,lru页面置换算法c++实现

以下是opt、fifo、lru页面置换算法的C++实现代码示例：

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

void simulate_FIFO() // FIFO页面置换算法
{
    int hh = 0, tt = -1;
    int cnt = 0;
    for (int i = 0; i < m; i++)
    {
        int x;
        scanf("%d", &x);
        bool flag = false;
        for (int j = hh; j <= tt; j++)
            if (q[j] == x)
            {
                flag = true;
                break;
            }
        if (flag) continue;
        if (tt - hh + 1 < n) q[++tt] = x;
        else q[hh++] = x;
        cnt++;
    }
    printf("FIFO缺页率：%.2lf%%\n", cnt * 100.0 / m);
}

void simulate_LRU() // LRU页面置换算法
{
    int hh = 0, tt = -1;
    int cnt = 0;
    for (int i = 0; i < m; i++)
    {
        int x;
        scanf("%d", &x);
        bool flag = false;
        for (int j = hh; j <= tt; j++)
            if (q[j] == x)
            {
                flag = true;
                for (int k = j; k < tt; k++)
                    q[k] = q[k + 1];
                q[tt--] = x;
                break;
            }
        if (flag) continue;
        if (tt - hh + 1 < n) q[++tt] = x;
        else q[hh++] = x;
        cnt++;
    }
    printf("LRU缺页率：%.2lf%%\n", cnt * 100.0 / m);
}

void simulate_OPT() // OPT页面置换算法
{
    int hh = 0, tt = -1;
    int cnt = 0;
    for (int i = 0; i < m; i++)
    {
        int x;
        scanf("%d", &x);
        bool flag = false;
        for (int j = hh; j <= tt; j++)
            if (q[j] == x)
            {
                flag = true;
                break;
            }
        if (flag) continue;
        if (tt - hh + 1 < n) q[++tt] = x;
        else
        {
            int pos = -1, maxd = -1;
            for (int j = hh; j <= tt; j++)
            {
                int d = 1e9;
                for (int k = i + 1; k < m; k++)
                    if (q[j] == q[k])
                    {
                        d = k - i;
                        break;
                    }
                if (d > maxd)
                {
                    maxd = d;
                    pos = j;
                }
            }
            q[pos] = x;
        }
        cnt++;
    }
    printf("OPT缺页率：%.2lf%%\n", cnt * 100.0 / m);
}

int main()
{
    scanf("%d%d", &n, &m);
    simulate_FIFO();
    simulate_LRU();
    simulate_OPT();
    return 0;
}

其中，输入的第一行为内存块数n和页面请求数m，接下来m行为每个页面的请求编号。在simulate_FIFO()函数中，我们使用一个队列来模拟FIFO页面置换算法；在simulate_LRU()函数中，我们也使用一个队列来模拟LRU页面置换算法；在simulate_OPT()函数中，我们使用了一个双重循环来计算每个页面在后面的请求中最晚出现的位置，从而找到最优的页面进行置换。最后输出每种算法的缺页率即可。