页面置换算法c++实现

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

1. 先进先出（FIFO）页面置换算法

#include <iostream>
#include <queue>
using namespace std;

int FIFO(int pages[], int n, int capacity) {
    queue<int> q;
    int pageFaults = 0;
    for (int i = 0; i < n; i++) {
        if (q.size() < capacity) {
            if (!q.empty() && find(q.front(), q.back(), pages[i]) == q.end()) {
                pageFaults++;
                q.push(pages[i]);
            }
            else if (q.empty()) {
                pageFaults++;
                q.push(pages[i]);
            }
        }
        else {
            if (find(q.front(), q.back(), pages[i]) == q.end()) {
                pageFaults++;
                q.pop();
                q.push(pages[i]);
            }
        }
    }
    return pageFaults;
}

int main() {
    int pages[] = { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 };
    int n = sizeof(pages) / sizeof(pages[0]);
    int capacity = 3;
    cout << "FIFO Page Faults: " << FIFO(pages, n, capacity) << endl;
    return 0;
}

2. 最近最久未使用（LRU）页面置换算法

#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;

int LRU(int pages[], int n, int capacity) {
    list<int> dq;
    unordered_map<int, list<int>::iterator> mp;
    int pageFaults = 0;
    for (int i = 0; i < n; i++) {
        if (mp.find(pages[i]) == mp.end()) {
            pageFaults++;
            if (dq.size() == capacity) {
                int last = dq.back();
                dq.pop_back();
                mp.erase(last);
            }
        }
        else {
            dq.erase(mp[pages[i]]);
        }
        dq.push_front(pages[i]);
        mp[pages[i]] = dq.begin();
    }
    return pageFaults;
}

int main() {
    int pages[] = { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 };
    int n = sizeof(pages) / sizeof(pages[0]);
    int capacity = 3;
    cout << "LRU Page Faults: " << LRU(pages, n, capacity) << endl;
    return 0;
}

3. 最不常用（LFU）页面置换算法

#include <iostream>
#include <unordered_map>
#include <set>
using namespace std;

struct Page {
    int id, freq, time;
    bool operator<(const Page& other) const {
        return freq == other.freq ? time < other.time : freq < other.freq;
    }
};

int LFU(int pages[], int n, int capacity) {
    unordered_map<int, Page> mp;
    set<Page> st;
    int pageFaults = 0, time = 0;
    for (int i = 0; i < n; i++) {
        if (mp.find(pages[i]) == mp.end()) {
            pageFaults++;
            if (st.size() == capacity) {
                mp.erase(st.begin()->id);
                st.erase(st.begin());
            }
            mp[pages[i]] = { pages[i], 1, time };
            st.insert(mp[pages[i]]);
        }
        else {
            auto it = mp.find(pages[i]);
            st.erase(it->second);
            it->second.freq++;
            it->second.time = time;
            st.insert(it->second);
        }
        time++;
    }
    return pageFaults;
}

int main() {
    int pages[] = { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 };
    int n = sizeof(pages) / sizeof(pages[0]);
    int capacity = 3;
    cout << "LFU Page Faults: " << LFU(pages, n, capacity) << endl;
    return 0;
}