opt,fifo,lru页面置换算法（c++编码）

以下是C++代码实现三种页面置换算法：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 全局变量
vector<int> pages; // 页面序列
int pageFaults; // 页面故障数

// OPT 页面置换算法
int opt(vector<int>& frames, int index) {
    int res = -1, farthest = -1;
    for (int i = 0; i < frames.size(); i++) {
        int j = index + 1;
        for (; j < pages.size(); j++) {
            if (frames[i] == pages[j]) {
                if (j > farthest) {
                    farthest = j;
                    res = i;
                }
                break;
            }
        }
        if (j == pages.size()) {
            return i;
        }
    }
    return res == -1 ? 0 : res;
}

// FIFO 页面置换算法
int fifo(vector<int>& frames) {
    int res = -1;
    for (int i = 0; i < frames.size(); i++) {
        if (frames[i] == -1) {
            return i;
        }
        if (i == 0 || frames[i] < frames[res]) {
            res = i;
        }
    }
    return res;
}

// LRU 页面置换算法
int lru(vector<int>& frames, int index) {
    int res = -1, farthest = -1;
    for (int i = 0; i < frames.size(); i++) {
        int j = index - 1;
        for (; j >= 0; j--) {
            if (frames[i] == pages[j]) {
                if (j > farthest) {
                    farthest = j;
                    res = i;
                }
                break;
            }
        }
        if (j == -1) {
            return i;
        }
    }
    return res == -1 ? 0 : res;
}

// 页面置换函数
void pageReplacement(int numFrames, int algorithm) {
    vector<int> frames(numFrames, -1);
    pageFaults = 0;

    for (int i = 0; i < pages.size(); i++) {
        int index;
        if (find(frames.begin(), frames.end(), pages[i]) == frames.end()) {
            pageFaults++;
            switch (algorithm) {
            case 1:
                index = fifo(frames);
                break;
            case 2:
                index = opt(frames, i);
                break;
            case 3:
                index = lru(frames, i);
                break;
            default:
                break;
            }
            frames[index] = pages[i];
        }
    }
}

int main() {
    int numPages, numFrames, algorithm;
    cout << "请输入页面序列的长度：";
    cin >> numPages;
    cout << "请输入物理内存的大小：";
    cin >> numFrames;
    cout << "请选择页面置换算法（1.FIFO, 2.OPT, 3.LRU）：";
    cin >> algorithm;

    cout << "请输入页面序列：" << endl;
    for (int i = 0; i < numPages; i++) {
        int page;
        cin >> page;
        pages.push_back(page);
    }

    pageReplacement(numFrames, algorithm);

    cout << "页面故障数：" << pageFaults << endl;

    return 0;
}

其中，函数 `opt()` 为 OPT 页面置换算法，`fifo()` 为 FIFO 页面置换算法，`lru()` 为 LRU 页面置换算法。在 `pageReplacement()` 函数中根据选择的算法调用相应的页面置换函数，并统计页面故障数。最后输出页面故障数即可。