时钟置换算法实现代码

时钟置换算法也叫最近未用算法（NRU），是一种页面置换算法。它试图在最近未使用的页面中选择一个牺牲页。下面是一个简单的 C++ 实现代码：

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

struct Page {
    int id; // 页面编号
    bool ref; // 是否被引用
};

int main() {
    int n, m, id, cnt = 0, fault = 0;
    cin >> n >> m; // n为物理块数，m为页面序列长度
    vector<Page> buffer(n); // 物理块缓冲区
    for (int i = 0; i < n; ++i) buffer[i].id = -1; // 初始化页面编号为-1
    for (int i = 0; i < m; ++i) {
        cin >> id; // 读入页面编号
        bool found = false;
        // 查找是否已经在物理块缓冲区中
        for (int j = 0; j < n; ++j) {
            if (buffer[j].id == id) {
                buffer[j].ref = true; // 标记为已引用
                found = true;
                break;
            }
        }
        if (!found) {
            int k = cnt % n; // 从当前位置开始顺时针查找
            while (buffer[k].ref) {
                buffer[k].ref = false; // 清除引用位
                k = (k + 1) % n;
            }
            buffer[k].id = id;
            buffer[k].ref = true;
            ++cnt; // 物理块缓冲区中页面数量加1
            ++fault; // 未命中次数加1
        }
    }
    cout << fault << endl; // 输出未命中次数
    return 0;
}

该算法的关键在于如何选择牺牲页。时钟置换算法使用了一个引用位（ref）来标记页面是否被引用过。在缺页发生时，算法从当前位置开始顺时针查找，找到第一个未被引用过的页面进行替换。如果当前位置的页面被引用过，则清除其引用位，继续查找下一个页面。这样一直查找下去，直到找到一个未被引用过的页面。