虚拟页式存储管理中常用页面置换算法的实现代码c++

以下是几种常用的页面置换算法的实现代码，包括FIFO、LRU、Clock和OPT：

FIFO：

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

int fifo(int pages[], int n, int frameSize) {
    queue<int> q;
    unordered_set<int> s;
    int pageFaults = 0;
    for(int i=0; i<n; i++) {
        if(s.find(pages[i]) == s.end()) {
            pageFaults++;
            if(q.size() == frameSize) {
                s.erase(q.front());
                q.pop();
            }
            q.push(pages[i]);
            s.insert(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 frameSize = 3;
    cout<<"FIFO: "<<fifo(pages, n, frameSize)<<endl;
    return 0;
}

LRU：

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

int lru(int pages[], int n, int frameSize) {
    list<int> l;
    unordered_map<int, list<int>::iterator> m;
    int pageFaults = 0;
    for(int i=0; i<n; i++) {
        if(m.find(pages[i]) == m.end()) {
            pageFaults++;
            if(l.size() == frameSize) {
                m.erase(l.back());
                l.pop_back();
            }
            l.push_front(pages[i]);
            m[pages[i]] = l.begin();
        } else {
            l.erase(m[pages[i]]);
            l.push_front(pages[i]);
            m[pages[i]] = l.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 frameSize = 3;
    cout<<"LRU: "<<lru(pages, n, frameSize)<<endl;
    return 0;
}

Clock：

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

int clock(int pages[], int n, int frameSize) {
    vector<int> v(frameSize, -1);
    unordered_map<int, int> m;
    int pageFaults = 0;
    int hand = 0;
    for(int i=0; i<n; i++) {
        if(m.find(pages[i]) == m.end()) {
            pageFaults++;
            while(v[hand] != -1 && m[v[hand]] == 1) {
                m[v[hand]] = 0;
                hand = (hand+1)%frameSize;
            }
            if(v[hand] != -1) {
                m[v[hand]] = 0;
            }
            v[hand] = pages[i];
            m[pages[i]] = 1;
            hand = (hand+1)%frameSize;
        } else {
            m[pages[i]] = 1;
        }
    }
    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 frameSize = 3;
    cout<<"Clock: "<<clock(pages, n, frameSize)<<endl;
    return 0;
}

OPT：

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

int opt(int pages[], int n, int frameSize) {
    vector<int> v(frameSize, -1);
    unordered_map<int, int> m;
    int pageFaults = 0;
    for(int i=0; i<n; i++) {
        if(m.find(pages[i]) == m.end()) {
            pageFaults++;
            int idx = -1;
            for(int j=0; j<v.size(); j++) {
                if(m.find(v[j]) == m.end()) {
                    idx = j;
                    break;
                }
                int farthest = -1;
                for(int k=i+1; k<n; k++) {
                    if(pages[k] == v[j]) {
                        farthest = k;
                        break;
                    }
                }
                if(farthest == -1) {
                    idx = j;
                    break;
                }
                if(farthest > idx) {
                    idx = j;
                }
            }
            v[idx] = pages[i];
            m[pages[i]] = 1;
        }
    }
    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 frameSize = 3;
    cout<<"OPT: "<<opt(pages, n, frameSize)<<endl;
    return 0;
}