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

下面是三种页面置换算法（OPT, FIFO, LRU）的C++实现示例代码：

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

using namespace std;

// OPT算法
int OPT(vector<int>& pages, int n, int frameSize) {
    int pageFaults = 0;
    vector<int> frames(frameSize, -1);
    for (int i = 0; i < n; i++) {
        bool found = false;
        for (int j = 0; j < frameSize; j++) {
            if (frames[j] == pages[i]) {
                found = true;
                break;
            }
        }
        if (!found) {
            int index = -1;
            int farthest = -1;
            for (int j = 0; j < frameSize; j++) {
                bool nextUseFound = false;
                for (int k = i + 1; k < n; k++) {
                    if (frames[j] == pages[k]) {
                        nextUseFound = true;
                        if (k > farthest) {
                            farthest = k;
                            index = j;
                        }
                        break;
                    }
                }
                if (!nextUseFound) {
                    index = j;
                    break;
                }
            }
            frames[index] = pages[i];
            pageFaults++;
        }
    }
    return pageFaults;
}

// FIFO算法
int FIFO(vector<int>& pages, int n, int frameSize) {
    int pageFaults = 0;
    queue<int> q;
    vector<int> frames(frameSize, -1);
    for (int i = 0; i < n; i++) {
        bool found = false;
        for (int j = 0; j < frameSize; j++) {
            if (frames[j] == pages[i]) {
                found = true;
                break;
            }
        }
        if (!found) {
            if (q.size() == frameSize) {
                int frontPage = q.front();
                q.pop();
                for (int j = 0; j < frameSize; j++) {
                    if (frames[j] == frontPage) {
                        frames[j] = pages[i];
                        break;
                    }
                }
            } else {
                frames[q.size()] = pages[i];
            }
            q.push(pages[i]);
            pageFaults++;
        }
    }
    return pageFaults;
}

// LRU算法
int LRU(vector<int>& pages, int n, int frameSize) {
    int pageFaults = 0;
    vector<int> frames(frameSize, -1);
    vector<int> counter(frameSize, 0);
    for (int i = 0; i < n; i++) {
        bool found = false;
        for (int j = 0; j < frameSize; j++) {
            if (frames[j] == pages[i]) {
                found = true;
                counter[j] = 0;
                break;
            }
        }
        if (!found) {
            int index = max_element(counter.begin(), counter.end()) - counter.begin();
            frames[index] = pages[i];
            counter[index] = 0;
            pageFaults++;
        }
        for (int j = 0; j < frameSize; j++) {
            if (frames[j] != -1) {
                counter[j]++;
            }
        }
    }
    return pageFaults;
}

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

    cout << "OPT算法页面错误次数：" << OPT(pages, n, frameSize) << endl;
    cout << "FIFO算法页面错误次数：" << FIFO(pages, n, frameSize) << endl;
    cout << "LRU算法页面错误次数：" << LRU(pages, n, frameSize) << endl;

    return 0;
}

上述代码中，`pages`数组表示虚拟内存页面序列，`n`表示虚拟内存页面数量，`frameSize`表示物理内存帧数。`OPT()`函数实现了OPT算法，`FIFO()`函数实现了FIFO算法，`LRU()`函数实现了LRU算法。程序输出每种算法的页面错误次数。