虚拟存储器管理实验先进先出置换算法代码和最久最近未使用算法代码

虚拟存储器管理中常用的页面置换算法有很多种，其中包括先进先出（FIFO）算法和最久最近未使用（LRU）算法。下面分别给出它们的示例代码。

先进先出（FIFO）算法示例代码：

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

const int PAGE_NUM = 3;  // 物理块个数
const int PAGE_SIZE = 4; // 页面大小
const int PAGE_REF[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}; // 页面访问序列

struct Page {
    int id; // 页面号
    int time; // 进入时间
    Page(int id, int time):id(id), time(time) {}
    bool operator < (const Page &p) const {
        return time > p.time; // 时间越早，优先级越高
    }
};

int fifo() {
    int page_fault = 0;
    queue<int> q; // 物理块队列
    unordered_set<int> s; // 物理块集合，用于判断页面是否在内存中
    for (int i = 0; i < sizeof(PAGE_REF) / sizeof(int); i++) {
        int page_id = PAGE_REF[i] / PAGE_SIZE;
        if (s.find(page_id) == s.end()) { // 页面不在内存中
            page_fault++;
            if (q.size() == PAGE_NUM) { // 物理块队列已满，需要进行页面置换
                int page_to_remove = q.front();
                q.pop();
                s.erase(page_to_remove);
            }
            q.push(page_id);
            s.insert(page_id);
        }
    }
    return page_fault;
}

int main() {
    int page_fault = fifo();
    cout << "先进先出算法：页面置换次数为 " << page_fault << endl;
    return 0;
}

最久最近未使用（LRU）算法示例代码：

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

const int PAGE_NUM = 3;  // 物理块个数
const int PAGE_SIZE = 4; // 页面大小
const int PAGE_REF[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}; // 页面访问序列

int lru() {
    int page_fault = 0;
    list<int> l; // 物理块链表
    unordered_map<int, list<int>::iterator> m; // 页面对应的链表迭代器
    for (int i = 0; i < sizeof(PAGE_REF) / sizeof(int); i++) {
        int page_id = PAGE_REF[i] / PAGE_SIZE;
        if (m.find(page_id) == m.end()) { // 页面不在内存中
            page_fault++;
            if (l.size() == PAGE_NUM) { // 物理块链表已满，需要进行页面置换
                int page_to_remove = l.back(); // 链表尾部是最久未使用的页面
                l.pop_back();
                m.erase(page_to_remove);
            }
            l.push_front(page_id);
            m[page_id] = l.begin();
        } else { // 页面在内存中
            l.erase(m[page_id]); // 将页面移到链表头部，表示最近访问过
            l.push_front(page_id);
            m[page_id] = l.begin();
        }
    }
    return page_fault;
}

int main() {
    int page_fault = lru();
    cout << "最久最近未使用算法：页面置换次数为 " << page_fault << endl;
    return 0;
}

以上是先进先出算法和最久最近未使用算法的示例代码，希望对您有所帮助。