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

以下是基于 C++ 的 OPT, FIFO, LRU 页面置换算法的实现代码：

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>

using namespace std;

// OPT 页面置换算法
int OPT(vector<int> pages, int frameSize) {
    int pageFaults = 0;
    unordered_map<int, int> nextUse;
    vector<int> frames(frameSize, -1);

    for(int i = 0; i < pages.size(); i++) {
        int page = pages[i];

        if(find(frames.begin(), frames.end(), page) != frames.end()) {
            continue;
        }

        if(frames[frames.size() - 1] == -1) {
            frames[pageFaults] = page;
            pageFaults++;
        } else {
            for(int j = 0; j < frames.size(); j++) {
                int frame = frames[j];
                if(nextUse.find(frame) == nextUse.end()) {
                    nextUse[frame] = i;
                } else {
                    if(nextUse[frame] < nextUse[frames[j]]) {
                        nextUse[frame] = i;
                    }
                }
            }

            int maxNextUse = -1;
            int pageToReplace = -1;

            for(int j = 0; j < frames.size(); j++) {
                int frame = frames[j];
                if(nextUse[frame] > maxNextUse) {
                    maxNextUse = nextUse[frame];
                    pageToReplace = frame;
                }
            }

            replace(frames.begin(), frames.end(), pageToReplace, page);
            pageFaults++;
        }
    }

    return pageFaults;
}

// FIFO 页面置换算法
int FIFO(vector<int> pages, int frameSize) {
    int pageFaults = 0;
    queue<int> frames;

    for(int i = 0; i < pages.size(); i++) {
        int page = pages[i];

        if(find(frames.front(), frames.back(), page) != frames.back()) {
            if(frames.size() == frameSize) {
                frames.pop();
            }

            frames.push(page);
            pageFaults++;
        }
    }

    return pageFaults;
}

// LRU 页面置换算法
int LRU(vector<int> pages, int frameSize) {
    int pageFaults = 0;
    unordered_map<int, int> lastUse;
    vector<int> frames(frameSize, -1);

    for(int i = 0; i < pages.size(); i++) {
        int page = pages[i];

        if(find(frames.begin(), frames.end(), page) != frames.end()) {
            lastUse[page] = i;
            continue;
        }

        if(frames[frames.size() - 1] == -1) {
            frames[pageFaults] = page;
            lastUse[page] = i;
            pageFaults++;
        } else {
            int minLastUse = INT_MAX;
            int pageToReplace = -1;

            for(int j = 0; j < frames.size(); j++) {
                int frame = frames[j];
                if(lastUse[frame] < minLastUse) {
                    minLastUse = lastUse[frame];
                    pageToReplace = frame;
                }
            }

            replace(frames.begin(), frames.end(), pageToReplace, page);
            lastUse[page] = i;
            pageFaults++;
        }
    }

    return pageFaults;
}

int main() {
    vector<int> pages = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
    int frameSize = 3;

    cout << "OPT 页面置换算法: " << OPT(pages, frameSize) << endl;
    cout << "FIFO 页面置换算法: " << FIFO(pages, frameSize) << endl;
    cout << "LRU 页面置换算法: " << LRU(pages, frameSize) << endl;

    return 0;
}

在这个代码中，我们定义了三个函数 `OPT`, `FIFO`, 和 `LRU`，分别实现了 OPT, FIFO, 和 LRU 页面置换算法。每个函数都接受一个整数数组 `pages` 和一个整数 `frameSize`，其中 `pages` 表示页面序列，`frameSize` 表示内存中页面框的数量。每个函数都返回页面缺页次数。

在 `OPT` 函数中，我们使用了一个哈希表 `nextUse` 来记录每个页面下一次使用的位置。当需要替换页面时，我们选择下一次使用最远的页面进行替换。

在 `FIFO` 函数中，我们使用了一个队列来记录页面。当需要替换页面时，我们选择队列中最早进入的页面进行替换。

在 `LRU` 函数中，我们使用了一个哈希表 `lastUse` 来记录每个页面上一次使用的位置。当需要替换页面时，我们选择上一次使用时间最早的页面进行替换。

注意，以上实现代码仅供参考。实际使用中，还需要考虑到多种情况，比如页面访问的顺序、页面分布的情况等等。