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

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

1. OPT 页面置换算法：

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

void OPT(vector<int>& page_sequence, int frame_size) {
    int page_faults = 0;
    unordered_map<int, int> next_occurrence;
    vector<int> frames(frame_size, -1);

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

        if (next_occurrence.find(page) == next_occurrence.end()) {
            for (int j = i + 1; j < page_sequence.size(); ++j) {
                if (frames.size() == frame_size) {
                    break;
                }
                if (page_sequence[j] == page) {
                    next_occurrence[page] = j;
                    break;
                }
            }
        }

        if (find(frames.begin(), frames.end(), page) == frames.end()) {
            int farthest = -1, farthest_page;
            for (int j = 0; j < frames.size(); ++j) {
                if (next_occurrence.find(frames[j]) == next_occurrence.end()) {
                    farthest_page = frames[j];
                    break;
                }
                else if (next_occurrence[frames[j]] > farthest) {
                    farthest = next_occurrence[frames[j]];
                    farthest_page = frames[j];
                }
            }
            for (int j = 0; j < frames.size(); ++j) {
                if (frames[j] == farthest_page) {
                    frames[j] = page;
                    next_occurrence[page] = i + 1;
                    ++page_faults;
                    break;
                }
            }
        }
    }

    cout << "Page faults: " << page_faults << endl;
}

int main() {
    vector<int> page_sequence = { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 };
    int frame_size = 3;
    OPT(page_sequence, frame_size);
    return 0;
}

2. FIFO 页面置换算法：

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

using namespace std;

void FIFO(vector<int>& page_sequence, int frame_size) {
    int page_faults = 0;
    deque<int> frames;

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

        if (find(frames.begin(), frames.end(), page) == frames.end()) {
            if (frames.size() == frame_size) {
                frames.pop_front();
            }
            frames.push_back(page);
            ++page_faults;
        }
    }

    cout << "Page faults: " << page_faults << endl;
}

int main() {
    vector<int> page_sequence = { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 };
    int frame_size = 3;
    FIFO(page_sequence, frame_size);
    return 0;
}

3. LRU 页面置换算法：

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

using namespace std;

void LRU(vector<int>& page_sequence, int frame_size) {
    int page_faults = 0;
    unordered_map<int, int> frame_to_index;
    vector<int> frames;

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

        if (frame_to_index.find(page) == frame_to_index.end()) {
            if (frames.size() == frame_size) {
                int lru_page = frames.back();
                frame_to_index.erase(lru_page);
                frames.pop_back();
            }
            frames.insert(frames.begin(), page);
            frame_to_index[page] = 0;
            ++page_faults;
        }
        else {
            frames.erase(frames.begin() + frame_to_index[page]);
            frames.insert(frames.begin(), page);
            for (int j = 0; j < frames.size(); ++j) {
                frame_to_index[frames[j]] = j;
            }
        }
    }

    cout << "Page faults: " << page_faults << endl;
}

int main() {
    vector<int> page_sequence = { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 };
    int frame_size = 3;
    LRU(page_sequence, frame_size);
    return 0;
}

以上是三种页面置换算法的 C++ 实现，分别是 OPT、FIFO 和 LRU。