操作系统页面置换算法c++代码

以下是常见的三种操作系统页面置换算法的 C++ 代码实现：

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

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> fifo; // 存放页面的队列
    int page_num, frame_num, page_fault = 0; // 页面数、帧数、页面失效次数
    cin >> page_num >> frame_num;
    int* pages = new int[page_num]; // 存放页面的数组
    for (int i = 0; i < page_num; ++i) {
        cin >> pages[i];
    }

    for (int i = 0; i < page_num; ++i) {
        int page = pages[i];
        if (fifo.size() < frame_num) {
            // 如果队列未满，直接加入队尾
            fifo.push(page);
            ++page_fault;
        } else {
            // 如果队列已满，弹出队头，再加入队尾
            int front_page = fifo.front();
            if (front_page != page) {
                fifo.pop();
                fifo.push(page);
                ++page_fault;
            }
        }
    }

    cout << "FIFO: " << page_fault << endl;

    delete[] pages;
    return 0;
}

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

#include <iostream>
#include <list>
#include <unordered_map>

using namespace std;

int main() {
    list<int> lru; // 存放页面的双向链表
    unordered_map<int, list<int>::iterator> map; // 存放页面和其在链表中的迭代器
    int page_num, frame_num, page_fault = 0; // 页面数、帧数、页面失效次数
    cin >> page_num >> frame_num;
    int* pages = new int[page_num]; // 存放页面的数组
    for (int i = 0; i < page_num; ++i) {
        cin >> pages[i];
    }

    for (int i = 0; i < page_num; ++i) {
        int page = pages[i];
        auto iter = map.find(page);
        if (iter != map.end()) {
            // 如果页面已在链表中，先删除再插入到链表尾部
            lru.erase(iter->second);
            map.erase(iter);
        }
        if (lru.size() == frame_num) {
            // 如果链表已满，删除链表头部（最近最久未使用的页面）
            int front_page = lru.front();
            lru.pop_front();
            map.erase(front_page);
        }
        // 将新页面插入链表尾部，并在 map 中记录迭代器
        lru.push_back(page);
        map[page] = --lru.end();
        ++page_fault;
    }

    cout << "LRU: " << page_fault << endl;

    delete[] pages;
    return 0;
}

3. 时钟页面置换算法：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> clock; // 存放页面的数组
    vector<bool> ref; // 存放页面的引用位
    int page_num, frame_num, page_fault = 0; // 页面数、帧数、页面失效次数
    cin >> page_num >> frame_num;
    int* pages = new int[page_num]; // 存放页面的数组
    for (int i = 0; i < page_num; ++i) {
        cin >> pages[i];
    }

    for (int i = 0; i < page_num; ++i) {
        int page = pages[i];
        bool found = false;
        for (int j = 0; j < clock.size(); ++j) {
            if (clock[j] == page) {
                // 如果页面已在数组中，将其引用位设置为 true
                ref[j] = true;
                found = true;
                break;
            }
        }
        if (!found) {
            // 如果页面不在数组中，寻找第一个引用位为 false 的页面
            while (true) {
                if (!ref[0]) {
                    // 如果找到了，将其替换为新页面
                    clock[0] = page;
                    ref[0] = true;
                    break;
                } else {
                    // 如果没找到，将所有页面的引用位都设为 false
                    ref[0] = false;
                    clock.push_back(clock[0]);
                    ref.push_back(false);
                    clock.erase(clock.begin());
                    ref.erase(ref.begin());
                }
            }
            ++page_fault;
        }
    }

    cout << "Clock: " << page_fault << endl;

    delete[] pages;
    return 0;
}