（1）通过随机数产生一个指令序列，共320条指令。其地址按下述原则生成： ①50%的指令是顺序执行的； ②25%的指令是均匀分布在前地址部分； ③25%的指令是均匀分布在后地址部分； 具体的实施方法是： ① 在[0，319]的指令地址之间随机选取一起点m; ② 顺序执行一条指令，即执行地址为m+1的指令； ③ 在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’; ④ 顺序执行一条指令，其地址为m’+1； ⑤ 在后地址[m’+2，319]中随机选取一条指令并执行； ⑥ 重复①-⑤，直到执行320次指令。 （2）将指令序列变换成页地址流，设： ①页面大小为1K； ②用户内存容量为4页到32页； ③用户虚存容量为32K。 在用户虚存中，按每页存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为： 第0条—第9条指令为第0页（对应虚存地址为[0，9]）； 第10条—第19条指令为第1页（对应虚存地址为[10，19]）； 。。。。。。。。。。。。。。。。。。。。。 第310条—第319条指令为第31页（对应虚存地址为[310，319]）； 按以上方式，用户指令可组成32页。 （3）计算并输出下述各种算法在不同内存容量下的命中率。 ①FIFO先进先出的页面淘汰算法 ②LRU最近最少使用页面淘汰算法 ③OPT最佳页面淘汰算法 ④LFU最不经常使用页面淘汰算法 ⑤NUR最近没有使用页面淘汰算法。 按上述要求编写C语言代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define INSTRUCTION_NUM 320
#define PAGE_SIZE 1024
#define MIN_PAGE_NUM 4
#define MAX_PAGE_NUM 32
#define VIRTUAL_SIZE (PAGE_SIZE * MAX_PAGE_NUM)

// 生成随机指令序列
void generateInstructions(int* instructions) {
    // 初始化指令序列
    for (int i = 0; i < INSTRUCTION_NUM; i++) {
        instructions[i] = i;
    }

    // 按要求打乱指令序列
    for (int i = 0; i < INSTRUCTION_NUM; i++) {
        int j = rand() % INSTRUCTION_NUM;
        int temp = instructions[i];
        instructions[i] = instructions[j];
        instructions[j] = temp;
    }
}

// 将指令序列转换为页地址流
void generatePageStream(int* instructions, int* pageStream, int pageTable[][2]) {
    int nextPage = 0; // 下一页的页号
    int instructionCount = 0; // 当前已经生成的指令数

    // 将指令序列分页
    while (instructionCount < INSTRUCTION_NUM) {
        // 计算当前指令所在页的页号
        int currentPage = nextPage;
        nextPage = (nextPage + 1) % MAX_PAGE_NUM;

        // 将当前页号与页表的映射存储起来
        pageTable[currentPage][0] = instructionCount / 10;
        pageTable[currentPage][1] = instructionCount % 10;

        // 将当前页的指令加入页地址流中
        for (int i = 0; i < 10 && instructionCount < INSTRUCTION_NUM; i++) {
            pageStream[instructionCount] = currentPage;
            instructionCount++;
        }
    }
}

// FIFO算法
int FIFO(int* pageStream, int pageTable[][2], int pageFrameNum) {
    int hitCount = 0; // 命中次数
    int currentFrame = 0; // 当前指令所在帧的下标
    int* pageFrames = (int*)malloc(sizeof(int) * pageFrameNum); // 物理内存中的页帧

    // 初始化页帧
    for (int i = 0; i < pageFrameNum; i++) {
        pageFrames[i] = -1; // -1表示帧为空
    }

    // 逐条执行指令
    for (int i = 0; i < INSTRUCTION_NUM; i++) {
        int currentPage = pageStream[i];
        bool isHit = false; // 当前指令是否命中

        // 在页帧中查找当前页是否已经存在
        for (int j = 0; j < pageFrameNum; j++) {
            if (pageFrames[j] == currentPage) {
                isHit = true;
                break;
            }
        }

        // 如果未命中，则将当前页替换到物理内存中的一页帧中
        if (!isHit) {
            pageFrames[currentFrame % pageFrameNum] = currentPage;
            currentFrame++;
        } else {
            hitCount++;
        }
    }

    free(pageFrames);

    return hitCount;
}

// LRU算法
int LRU(int* pageStream, int pageTable[][2], int pageFrameNum) {
    int hitCount = 0; // 命中次数
    int currentFrame = 0; // 当前指令所在帧的下标
    int* pageFrames = (int*)malloc(sizeof(int) * pageFrameNum); // 物理内存中的页帧
    int* lastAccessTime = (int*)malloc(sizeof(int) * MAX_PAGE_NUM); // 记录每个页最近访问时间

    // 初始化页帧和最近访问时间
    for (int i = 0; i < pageFrameNum; i++) {
        pageFrames[i] = -1;
        lastAccessTime[i] = -1;
    }

    // 逐条执行指令
    for (int i = 0; i < INSTRUCTION_NUM; i++) {
        int currentPage = pageStream[i];
        bool isHit = false; // 当前指令是否命中

        // 在页帧中查找当前页是否已经存在，同时更新最近访问时间
        for (int j = 0; j < pageFrameNum; j++) {
            if (pageFrames[j] == currentPage) {
                isHit = true;
                lastAccessTime[currentPage] = i;
                break;
            }
        }

        // 如果未命中，则将最近最少使用的页替换到物理内存中的一页帧中
        if (!isHit) {
            int minAccessTime = INSTRUCTION_NUM;
            int minAccessIndex = -1;

            // 在页帧中查找最近最少使用的页
            for (int j = 0; j < pageFrameNum; j++) {
                if (lastAccessTime[pageFrames[j]] < minAccessTime) {
                    minAccessTime = lastAccessTime[pageFrames[j]];
                    minAccessIndex = j;
                }
            }

            pageFrames[minAccessIndex] = currentPage;
            lastAccessTime[currentPage] = i;
        } else {
            hitCount++;
        }
    }

    free(pageFrames);
    free(lastAccessTime);

    return hitCount;
}

// OPT算法
int OPT(int* pageStream, int pageTable[][2], int pageFrameNum) {
    int hitCount = 0; // 命中次数
    int currentFrame = 0; // 当前指令所在帧的下标
    int* pageFrames = (int*)malloc(sizeof(int) * pageFrameNum); // 物理内存中的页帧
    int* nextUseTime = (int*)malloc(sizeof(int) * MAX_PAGE_NUM); // 记录每个页下一次使用的时间

    // 初始化页帧和下一次使用时间
    for (int i = 0; i < pageFrameNum; i++) {
        pageFrames[i] = -1;
        nextUseTime[i] = INSTRUCTION_NUM; // 初始设为最大值，表示未来不再使用
    }

    // 预先计算所有页的下一次使用时间
    for (int i = 0; i < INSTRUCTION_NUM; i++) {
        int nextPage = pageStream[i + 1]; // 下一条指令所在页

        if (nextUseTime[nextPage] == INSTRUCTION_NUM) {
            nextUseTime[nextPage] = i + 1;
        }
    }

    // 逐条执行指令
    for (int i = 0; i < INSTRUCTION_NUM; i++) {
        int currentPage = pageStream[i];
        bool isHit = false; // 当前指令是否命中

        // 在页帧中查找当前页是否已经存在，同时更新下一次使用时间
        for (int j = 0; j < pageFrameNum; j++) {
            if (pageFrames[j] == currentPage) {
                isHit = true;
                nextUseTime[currentPage] = INSTRUCTION_NUM; // 设置为未来不再使用
                break;
            }
        }

        // 如果未命中，则将下一次不再使用的页替换到物理内存中的一页帧中
        if (!isHit) {
            int maxNextUseTime = -1;
            int maxNextUseIndex = -1;

            // 在页帧中查找下一次不再使用的页
            for (int j = 0; j < pageFrameNum; j++) {
                if (nextUseTime[pageFrames[j]] > maxNextUseTime) {
                    maxNextUseTime = nextUseTime[pageFrames[j]];
                    maxNextUseIndex = j;
                }
            }

            pageFrames[maxNextUseIndex] = currentPage;
            nextUseTime[currentPage] = INSTRUCTION_NUM; // 设置为未来不再使用
        } else {
            hitCount++;
        }
    }

    free(pageFrames);
    free(nextUseTime);

    return hitCount;
}

// LFU算法
int LFU(int* pageStream, int pageTable[][2], int pageFrameNum) {
    int hitCount = 0; // 命中次数
    int currentFrame = 0; // 当前指令所在帧的下标
    int* pageFrames = (int*)malloc(sizeof(int) * pageFrameNum); // 物理内存中的页帧
    int* accessCount = (int*)malloc(sizeof(int) * MAX_PAGE_NUM); // 记录每个页的访问次数

    // 初始化页帧和访问次数
    for (int i = 0; i < pageFrameNum; i++) {
        pageFrames[i] = -1;
        accessCount[i] = 0;
    }

    // 逐条执行指令
    for (int i = 0; i < INSTRUCTION_NUM; i++) {
        int currentPage = pageStream[i];
        bool isHit = false; // 当前指令是否命中

        // 在页帧中查找当前页是否已经存在，同时更新访问次数
        for (int j = 0; j < pageFrameNum; j++) {
            if (pageFrames[j] == currentPage) {
                isHit = true;
                accessCount[currentPage]++;
                break;
            }
        }

        // 如果未命中，则将访问次数最少的页替换到物理内存中的一页帧中
        if (!isHit) {
            int minAccessCount = INSTRUCTION_NUM;
            int minAccessIndex = -1;

            // 在页帧中查找访问次数最少的页
            for (int j = 0; j < pageFrameNum; j++) {
                if (accessCount[pageFrames[j]] < minAccessCount) {
                    minAccessCount = accessCount[pageFrames[j]];
                    minAccessIndex = j;
                }
            }

            pageFrames[minAccessIndex] = currentPage;
            accessCount[currentPage] = 1;
        } else {
            hitCount++;
        }
    }

    free(pageFrames);
    free(accessCount);

    return hitCount;
}

// NUR算法
int NUR(int* pageStream, int pageTable[][2], int pageFrameNum) {
    int hitCount = 0; // 命中次数
    int currentFrame = 0; // 当前指令所在帧的下标
    int* pageFrames = (int*)malloc(sizeof(int) * pageFrameNum); // 物理内存中的页帧
    int* useFlag = (int*)malloc(sizeof(int) * MAX_PAGE_NUM); // 记录每个页是否被访问过

    // 初始化页帧和使用标志
    for (int i = 0; i < pageFrameNum; i++) {
        pageFrames[i] = -1;
        useFlag[i] = 0;
    }

    // 逐条执行指令
    for (int i = 0; i < INSTRUCTION_NUM; i++) {
        int currentPage = pageStream[i];
        bool isHit = false; // 当前指令是否命中

        // 在页帧中查找当前页是否已经存在，同时更新使用标志
        for (int j = 0; j < pageFrameNum; j++) {
            if (pageFrames[j] == currentPage) {
                isHit = true;
                useFlag[currentPage] = 1;
                break;
            }
        }

        // 如果未命中，则将最近没有使用的页替换到物理内存中的一页帧中
        if (!isHit) {
            int minUseFlag = INSTRUCTION_NUM;
            int minUseIndex = -1;

            // 在页帧中查找最近没有使用的页
            for (int j = 0; j < pageFrameNum; j++) {
                if (useFlag[pageFrames[j]] < minUseFlag) {
                    minUseFlag = useFlag[pageFrames[j]];
                    minUseIndex = j;
                }
            }

            pageFrames[minUseIndex] = currentPage;
            useFlag[currentPage] = 1;
        } else {
            hitCount++;
        }

        // 每5次指令更新一次使用标志
        if (i % 5 == 4) {
            for (int j = 0; j < pageFrameNum; j++) {
                useFlag[pageFrames[j]] >>= 1; // 右移1位相当于除以2
            }
        }
    }

    free(pageFrames);
    free(useFlag);

    return hitCount;
}

int main() {
    int instructions[INSTRUCTION_NUM];
    int pageStream[INSTRUCTION_NUM];
    int pageTable[MAX_PAGE_NUM][2];

    // 生成随机指令序列
    generateInstructions(instructions);

    // 将指令序列转换为页地址流
    generatePageStream(instructions, pageStream, pageTable);

    // 遍历不同内存容量
    for (int pageFrameNum = MIN_PAGE_NUM; pageFrameNum <= MAX_PAGE_NUM; pageFrameNum++) {
        printf("内存容量为%d页:\n", pageFrameNum);

        // 计算FIFO算法的命中率
        int fifoHitCount = FIFO(pageStream, pageTable, pageFrameNum);
        printf("FIFO算法的命中率为%.2f%%\n", (fifoHitCount * 100.0 / INSTRUCTION_NUM));

        // 计算LRU算法的命中率
        int lruHitCount = LRU(pageStream, pageTable, pageFrameNum);
        printf("LRU算法的命中率为%.2f%%\n", (lruHitCount * 100.0 / INSTRUCTION_NUM));

        // 计算OPT算法的命中率
        int optHitCount = OPT(pageStream, pageTable, pageFrameNum);
        printf("OPT算法的命中率为%.2f%%\n", (optHitCount * 100.0 / INSTRUCTION_NUM));

        // 计算LFU算法的命中率
        int lfuHitCount = LFU(pageStream, pageTable, pageFrameNum);
        printf("LFU算法的命中率为%.2f%%\n", (lfuHitCount * 100.0 / INSTRUCTION_NUM));

        // 计算NUR算法的命中率
        int nurHitCount = NUR(pageStream, pageTable, pageFrameNum);
        printf("NUR算法的命中率为%.2f%%\n", (nurHitCount * 100.0 / INSTRUCTION_NUM));

        printf("\n");
    }

    return 0;
}