页面置换算法！！！ FIFO LRU OPT

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <random>
using namespace std;

// 页面置换算法基类
class PageReplacementAlgorithm {
protected:
    int frameCount;         // 物理块数
    vector<int> frames;     // 物理块
    int pageFaults;         // 缺页次数
    int totalReferences;    // 总引用次数

public:
    PageReplacementAlgorithm(int frameCount) 
        : frameCount(frameCount), pageFaults(0), totalReferences(0) {
        frames.resize(frameCount, -1); // -1表示物理块为空
    }

    virtual ~PageReplacementAlgorithm() {}

    // 处理页面访问
    virtual void accessPage(int page) = 0;

    // 获取缺页率
    double getPageFaultRate() const {
        return static_cast<double>(pageFaults) / totalReferences * 100.0;
    }

    // 获取缺页次数
    int getPageFaults() const {
        return pageFaults;
    }

    // 获取总访问序列
    int getTotalReferences() const {
        return totalReferences;
    }

    // 显示当前物理块状态
    void displayFrames() const {
        cout << "物理块状态: ";
        for (int frame : frames) {
            if (frame == -1) {
                cout << "[空] ";
            } else {
                cout << "[" << frame << "] ";
            }
        }
        cout << endl;
    }
};

// FIFO页面置换算法
class FIFO : public PageReplacementAlgorithm {
private:
    int nextReplaceIndex;   // 下一个要替换的页面索引

public:
    FIFO(int frameCount) : PageReplacementAlgorithm(frameCount), nextReplaceIndex(0) {}

    void accessPage(int page) override {
        totalReferences++;
        cout << "访问页面 " << page << ": ";
        
        // 检查页面是否已在内存中
        auto it = find(frames.begin(), frames.end(), page);
        if (it != frames.end()) {
            // 页面已在内存中，不发生缺页
            cout << "命中" << endl;
            displayFrames();
            return;
        }

        // 发生缺页
        pageFaults++;
        cout << "缺页";

        // 如果有空闲物理块
        for (int i = 0; i < frameCount; i++) {
            if (frames[i] == -1) {
                frames[i] = page;
                nextReplaceIndex = (i + 1) % frameCount;
                cout << " - 放入空闲物理块 " << i << endl;
                displayFrames();
                return;
            }
        }

        // 没有空闲物理块，使用FIFO算法替换页面
        int replacedPage = frames[nextReplaceIndex];
        frames[nextReplaceIndex] = page;
        cout << " - 置换页面 " << replacedPage << " （物理块 " << nextReplaceIndex << "）" << endl;
        nextReplaceIndex = (nextReplaceIndex + 1) % frameCount;
        displayFrames();
    }
};

// LRU页面置换算法
class LRU : public PageReplacementAlgorithm {
private:
    vector<int> lastUsed;   // 记录每个页面最后一次使用的时间

public:
    LRU(int frameCount) : PageReplacementAlgorithm(frameCount) {
        lastUsed.resize(frameCount, -1); // -1表示物理块为空
    }

    void accessPage(int page) override {
        totalReferences++;
        cout << "访问页面 " << page << ": ";
        
        // 检查页面是否已在内存中
        auto it = find(frames.begin(), frames.end(), page);
        if (it != frames.end()) {
            // 页面已在内存中，更新最后使用时间
            int index = it - frames.begin();
            lastUsed[index] = totalReferences;
            cout << "命中" << endl;
            displayFrames();
            return;
        }

        // 发生缺页
        pageFaults++;
        cout << "缺页";

        // 如果有空闲物理块
        for (int i = 0; i < frameCount; i++) {
            if (frames[i] == -1) {
                frames[i] = page;
                lastUsed[i] = totalReferences;
                cout << " - 放入空闲物理块 " << i << endl;
                displayFrames();
                return;
            }
        }

        // 没有空闲物理块，使用LRU算法替换页面
        int lruIndex = 0;
        for (int i = 1; i < frameCount; i++) {
            if (lastUsed[i] < lastUsed[lruIndex]) {
                lruIndex = i;
            }
        }

        int replacedPage = frames[lruIndex];
        frames[lruIndex] = page;
        lastUsed[lruIndex] = totalReferences;
        cout << " - 置换页面 " << replacedPage << " （物理块 " << lruIndex << "）" << endl;
        displayFrames();
    }
};

// OPT页面置换算法
class OPT : public PageReplacementAlgorithm {
private:
    const vector<int>& pageSequence;  // 页面访问序列
    int currentPosition;             // 当前在页面访问序列中的位置

public:
    OPT(int frameCount, const vector<int>& pageSequence) 
        : PageReplacementAlgorithm(frameCount), pageSequence(pageSequence), currentPosition(0) {}

    void accessPage(int page) override {
        totalReferences++;
        currentPosition++;
        cout << "访问页面 " << page << ": ";
        
        // 检查页面是否已在内存中
        auto it = find(frames.begin(), frames.end(), page);
        if (it != frames.end()) {
            // 页面已在内存中，不发生缺页
            cout << "命中" << endl;
            displayFrames();
            return;
        }

        // 发生缺页
        pageFaults++;
        cout << "缺页";

        // 如果有空闲物理块
        for (int i = 0; i < frameCount; i++) {
            if (frames[i] == -1) {
                frames[i] = page;
                cout << " - 放入空闲物理块 " << i << endl;
                displayFrames();
                return;
            }
        }

        // 没有空闲物理块，使用OPT算法替换页面
        int replaceIndex = 0;
        int farthest = -1;

        for (int i = 0; i < frameCount; i++) {
            int nextUse = INT_MAX;

            // 查找页面在未来的使用位置
            for (int j = currentPosition; j < pageSequence.size(); j++) {
                if (frames[i] == pageSequence[j]) {
                    nextUse = j;
                    break;
                }
            }

            // 如果某个页面在未来不会被使用，直接替换它
            if (nextUse == INT_MAX) {
                replaceIndex = i;
                break;
            }

            // 找到最远不会被使用的页面
            if (nextUse > farthest) {
                farthest = nextUse;
                replaceIndex = i;
            }
        }

        int replacedPage = frames[replaceIndex];
        frames[replaceIndex] = page;
        cout << " - 置换页面 " << replacedPage << " （物理块 " << replaceIndex << "）";
        if (farthest != INT_MAX) {
            cout << "（未来第 " << farthest - currentPosition + 1 << " 次访问）";
        } else {
            cout << "（未来不再使用）";
        }
        cout << endl;
        displayFrames();
    }
};

// 生成随机页面访问序列
vector<int> generateRandomPageSequence(int length, int maxPageNumber) {
    vector<int> sequence(length);
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, maxPageNumber - 1);

    for (int i = 0; i < length; i++) {
        sequence[i] = dis(gen);
    }

    return sequence;
}

int main() {
    int frameCount;
    cout << "请输入物理块数 (3或4): ";
    cin >> frameCount;

    // 检查输入是否有效
    if (frameCount != 3 && frameCount != 4) {
        cout << "无效的物理块数，必须是3或4。" << endl;
        return 1;
    }

    int choice;
    vector<int> pageSequence;

    cout << "请选择页面访问序列生成方式:" << endl;
    cout << "1. 手动输入" << endl;
    cout << "2. 随机生成" << endl;
    cin >> choice;

    if (choice == 1) {
        int n;
        cout << "请输入页面访问序列的长度: ";
        cin >> n;

        pageSequence.resize(n);
        cout << "请输入页面访问序列（整数，用空格分隔）: ";
        for (int i = 0; i < n; i++) {
            cin >> pageSequence[i];
        }
    } else if (choice == 2) {
        int length, maxPageNumber;
        cout << "请输入页面访问序列的长度: ";
        cin >> length;
        cout << "请输入最大页面号: ";
        cin >> maxPageNumber;

        pageSequence = generateRandomPageSequence(length, maxPageNumber);

        cout << "生成的随机页面访问序列: ";
        for (int page : pageSequence) {
            cout << page << " ";
        }
        cout << endl;
    } else {
        cout << "无效的选择" << endl;
        return 1;
    }

    cout << "\n===== 页面置换过程 =====" << endl;
    cout << "页面序列: ";
    for (int page : pageSequence) {
        cout << page << " ";
    }
    cout << endl << endl;

    // 运行FIFO算法
    cout << "===== FIFO算法 =====" << endl;
    FIFO fifo(frameCount);
    for (int page : pageSequence) {
        fifo.accessPage(page);
    }
    cout << "FIFO缺页次数: " << fifo.getPageFaults() << endl;
    cout << "FIFO缺页率: " << fifo.getPageFaultRate() << "%" << endl << endl;

    // 运行LRU算法
    cout << "===== LRU算法 =====" << endl;
    LRU lru(frameCount);
    for (int page : pageSequence) {
        lru.accessPage(page);
    }
    cout << "LRU缺页次数: " << lru.getPageFaults() << endl;
    cout << "LRU缺页率: " << lru.getPageFaultRate() << "%" << endl << endl;

    // 运行OPT算法
    cout << "===== OPT算法 =====" << endl;
    OPT opt(frameCount, pageSequence);
    for (int page : pageSequence) {
        opt.accessPage(page);
    }
    cout << "OPT缺页次数: " << opt.getPageFaults() << endl;
    cout << "OPT缺页率: " << opt.getPageFaultRate() << "%" << endl << endl;

    // 比较算法性能
    cout << "===== 算法性能比较 =====" << endl;
    cout << "FIFO缺页次数: " << fifo.getPageFaults() << endl;
    cout << "LRU缺页次数: " << lru.getPageFaults() << endl;
    cout << "OPT缺页次数: " << opt.getPageFaults() << endl;

    return 0;
}