（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<time.h>

#define INSTRUCTION_NUM 320 // 指令总数
#define PAGE_SIZE 1024 // 页面大小
#define USER_MEMORY_MIN 4 // 用户内存最小页数
#define USER_MEMORY_MAX 32 // 用户内存最大页数
#define USER_VIRT_MEM_SIZE 32 * 1024 // 用户虚存容量
#define INSTRUCTION_PER_PAGE 10 // 每页存放的指令数

// 页面结构体
typedef struct page {
    int page_num; // 页面编号
    int loaded; // 页面是否被加载，1表示已加载，0表示未加载
    int loaded_time; // 页面加载时间
    int last_access_time; // 页面上次访问时间
    int accessed; // 页面是否被访问，1表示已访问，0表示未访问
} Page;

// 指令结构体
typedef struct instruction {
    int page_num; // 指令所在页面编号
    int offset; // 指令在页面内的偏移量
} Instruction;

// 根据指令地址生成指令序列
void generate_instruction_sequence(int *instruction_sequence) {
    int i, m, m1, m2;
    int addr[INSTRUCTION_NUM];
    int count = 0;

    // 生成初始地址序列
    for (i = 0; i < INSTRUCTION_NUM; i++) {
        addr[i] = i;
    }

    // 执行320条指令
    for (i = 0; i < INSTRUCTION_NUM; i++) {
        // 50%的概率顺序执行一条指令
        if (rand() % 2 == 0) {
            m = addr[i];
        }
        // 25%的概率从前半部分随机选取一条指令并执行
        else if (rand() % 2 == 0) {
            m1 = rand() % (i + 1);
            m = addr[m1];
        }
        // 25%的概率从后半部分随机选取一条指令并执行
        else {
            m2 = rand() % (INSTRUCTION_NUM - i - 1) + i + 1;
            m = addr[m2];
        }
        instruction_sequence[count++] = m;
    }
}

// 将指令序列转换为页地址流
void generate_page_address_sequence(int *instruction_sequence, Instruction *page_address_sequence, int *page_access_counts, int user_memory_size) {
    int i, j, k, page_num;
    int page_count = 0;
    int page_offset = 0;
    int page_table_size = USER_VIRT_MEM_SIZE / PAGE_SIZE; // 页面表大小
    Page *page_table = (Page *)malloc(page_table_size * sizeof(Page)); // 页面表
    int *loaded_pages = (int *)malloc(user_memory_size * sizeof(int)); // 已加载的页面
    int loaded_page_count = 0; // 已加载的页面数
    int page_to_load; // 需要加载的页面
    int page_to_replace; // 需要替换的页面
    int access_time = 0; // 访问时间计数器
    int hit_count = 0; // 命中次数

    // 初始化页面表
    for (i = 0; i < page_table_size; i++) {
        page_table[i].page_num = i;
        page_table[i].loaded = 0;
        page_table[i].loaded_time = -1;
        page_table[i].last_access_time = -1;
        page_table[i].accessed = 0;
    }

    // 初始化已加载的页面
    for (i = 0; i < user_memory_size; i++) {
        loaded_pages[i] = -1;
    }

    // 逐条指令生成页地址流
    for (i = 0; i < INSTRUCTION_NUM; i++) {
        page_num = instruction_sequence[i] / PAGE_SIZE;
        page_offset = instruction_sequence[i] % PAGE_SIZE;

        // 查找页面是否已被加载
        for (j = 0; j < loaded_page_count; j++) {
            if (loaded_pages[j] == page_num) {
                page_table[page_num].last_access_time = access_time;
                page_table[page_num].accessed = 1;
                hit_count++;
                break;
            }
        }

        // 页面未被加载
        if (j == loaded_page_count) {
            // 用户内存未满，直接加载
            if (loaded_page_count < user_memory_size) {
                loaded_pages[loaded_page_count] = page_num;
                loaded_page_count++;
                page_table[page_num].loaded = 1;
                page_table[page_num].loaded_time = access_time;
                page_table[page_num].last_access_time = access_time;
                page_table[page_num].accessed = 1;
            }
            // 用户内存已满，需要进行页面替换
            else {
                // 选择需要替换的页面
                switch (k) {
                    // FIFO算法
                    case 0:
                        page_to_replace = loaded_pages[0];
                        for (j = 1; j < user_memory_size; j++) {
                            if (page_table[loaded_pages[j]].loaded_time < page_table[page_to_replace].loaded_time) {
                                page_to_replace = loaded_pages[j];
                            }
                        }
                        break;
                    // LRU算法
                    case 1:
                        page_to_replace = loaded_pages[0];
                        for (j = 1; j < user_memory_size; j++) {
                            if (page_table[loaded_pages[j]].last_access_time < page_table[page_to_replace].last_access_time) {
                                page_to_replace = loaded_pages[j];
                            }
                        }
                        break;
                    // OPT算法
                    case 2:
                        page_to_replace = loaded_pages[0];
                        for (j = 1; j < user_memory_size; j++) {
                            if (page_access_counts[loaded_pages[j]] < page_access_counts[page_to_replace]) {
                                page_to_replace = loaded_pages[j];
                            }
                        }
                        break;
                    // LFU算法
                    case 3:
                        page_to_replace = loaded_pages[0];
                        for (j = 1; j < user_memory_size; j++) {
                            if (page_access_counts[loaded_pages[j]] < page_access_counts[page_to_replace]) {
                                page_to_replace = loaded_pages[j];
                            }
                        }
                        break;
                    // NUR算法
                    case 4:
                        while (1) {
                            page_to_replace = loaded_pages[0];
                            for (j = 1; j < user_memory_size; j++) {
                                // 选择未被访问过的页面
                                if (page_table[loaded_pages[j]].accessed == 0) {
                                    page_to_replace = loaded_pages[j];
                                    break;
                                }
                                // 选择最久未被访问的页面
                                else if (page_table[loaded_pages[j]].last_access_time < page_table[page_to_replace].last_access_time) {
                                    page_to_replace = loaded_pages[j];
                                }
                            }
                            // 如果选择的页面被访问过，清除其访问标记，重新选择
                            if (page_table[page_to_replace].accessed == 1) {
                                page_table[page_to_replace].accessed = 0;
                            }
                            else {
                                break;
                            }
                        }
                        break;
                }

                // 替换页面
                loaded_pages[j] = page_num;
                page_table[page_to_replace].loaded = 0;
                page_table[page_to_replace].loaded_time = -1;
                page_table[page_to_replace].last_access_time = -1;
                page_table[page_to_replace].accessed = 0;
                page_table[page_num].loaded = 1;
                page_table[page_num].loaded_time = access_time;
                page_table[page_num].last_access_time = access_time;
                page_table[page_num].accessed = 1;
            }
        }

        // 统计各页面的访问次数
        page_access_counts[page_num]++;

        // 如果指令是页内第1条，则将整页加入页地址流
        if (page_offset == 0) {
            page_address_sequence[page_count].page_num = page_num;
            page_address_sequence[page_count].offset = page_offset;
            page_count++;
        }

        access_time++;
    }

    free(page_table);
    free(loaded_pages);

    // 计算命中率
    double hit_rate = (double)hit_count / INSTRUCTION_NUM;
    printf("内存容量为%d页时，", user_memory_size);
    printf("FIFO命中率：%f，", hit_rate);
}

int main() {
    int i, j;
    int instruction_sequence[INSTRUCTION_NUM]; // 指令序列
    Instruction page_address_sequence[INSTRUCTION_NUM / INSTRUCTION_PER_PAGE]; // 页地址流
    int page_access_counts[USER_VIRT_MEM_SIZE / PAGE_SIZE]; // 各页面的访问次数

    // 初始化随机数种子
    srand(time(NULL));

    // 生成指令序列
    generate_instruction_sequence(instruction_sequence);

    // 将指令序列转换为页地址流，并计算命中率
    for (i = USER_MEMORY_MIN; i <= USER_MEMORY_MAX; i++) {
        for (j = 0; j < USER_VIRT_MEM_SIZE / PAGE_SIZE; j++) {
            page_access_counts[j] = 0;
        }
        generate_page_address_sequence(instruction_sequence, page_address_sequence, page_access_counts, i);
    }

    return 0;
}