请求调页存储管理方式模拟

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

#define TOTAL_INSTRUCTIONS 320  // 总指令数
#define INSTRUCTIONS_PER_PAGE 10  // 每页包含的指令数
#define TOTAL_PAGES (TOTAL_INSTRUCTIONS / INSTRUCTIONS_PER_PAGE)  // 总页数
#define MEMORY_SIZE 4  // 内存块数

int instructions[TOTAL_INSTRUCTIONS];  // 指令数组
int memory[MEMORY_SIZE];  // 内存页数组
int memory_time[MEMORY_SIZE];  // 用于LRU算法记录时间戳
int page_faults = 0;  // 缺页次数

// 生成指令访问次序
void generate_instructions() {
    int m = rand() % TOTAL_INSTRUCTIONS;  // 随机生成起始指令
    instructions[0] = m;
    for (int i = 1; i < TOTAL_INSTRUCTIONS; i++) {
        int choice = rand() % 3;
        if (choice == 0) {
            instructions[i] = (instructions[i - 1] + 1) % TOTAL_INSTRUCTIONS;  // 顺序执行下一条指令
        } else if (choice == 1) {
            instructions[i] = rand() % instructions[i - 1];  // 跳转到前地址部分
        } else {
            instructions[i] = rand() % (TOTAL_INSTRUCTIONS - instructions[i - 1] - 1) + instructions[i - 1] + 1;  // 跳转到后地址部分
        }
        instructions[i] = instructions[i] % TOTAL_INSTRUCTIONS;  // 确保指令地址在合理范围内
    }
}

// 检查页面是否在内存中
int is_in_memory(int page) {
    for (int i = 0; i < MEMORY_SIZE; i++) {
        if (memory[i] == page) {
            return i;  // 返回页所在的内存块索引
        }
    }
    return -1;  // 页面不在内存中
}

// OPT置换算法
void replace_opt(int current_index) {
    int furthest_use[MEMORY_SIZE] = {0};  // 记录每个内存块中页面将来最远的使用时间
    int replace_index = 0;  // 需要被替换的页面索引

    // 查找内存中每个页面的下次使用时间
    for (int i = 0; i < MEMORY_SIZE; i++) {
        furthest_use[i] = TOTAL_INSTRUCTIONS;  // 初始化为最大值
        for (int j = current_index + 1; j < TOTAL_INSTRUCTIONS; j++) {
            if ((instructions[j] / INSTRUCTIONS_PER_PAGE) == memory[i]) {
                furthest_use[i] = j;  // 记录下次使用时间
                break;
            }
        }
        if (furthest_use[i] > furthest_use[replace_index]) {
            replace_index = i;  // 找到最远的使用时间
        }
    }
    memory[replace_index] = instructions[current_index] / INSTRUCTIONS_PER_PAGE;  // 替换页面
}

// FIFO置换算法
void replace_fifo(int current_index) {
    static int next_replace_index = 0;  // 下一个被替换的页面索引
    memory[next_replace_index] = instructions[current_index] / INSTRUCTIONS_PER_PAGE;  // 替换页面
    next_replace_index = (next_replace_index + 1) % MEMORY_SIZE;  // 循环更新替换索引
}

// LRU置换算法
void replace_lru(int current_index) {
    int lru_index = 0;  // 记录最近最少使用页面的索引
    int current_time = current_index;  // 当前时间

    // 查找最近最少使用的页面
    for (int i = 1; i < MEMORY_SIZE; i++) {
        if (memory_time[i] < memory_time[lru_index]) {
            lru_index = i;  // 找到最近最少使用的页面
        }
    }
    memory[lru_index] = instructions[current_index] / INSTRUCTIONS_PER_PAGE;  // 替换页面
    memory_time[lru_index] = current_time;  // 更新页面时间戳
}

// 运行模拟
void run_simulation(void (*replace_algorithm)(int), void (*update_time)(int, int)) {
    for (int i = 0; i < MEMORY_SIZE; i++) {
        memory[i] = -1;  // 初始化内存为空
    }
    page_faults = 0;  // 重置缺页次数

    for (int i = 0; i < TOTAL_INSTRUCTIONS; i++) {
        int page = instructions[i] / INSTRUCTIONS_PER_PAGE;  // 计算指令所在的页
        int offset = instructions[i] % INSTRUCTIONS_PER_PAGE;  // 计算页内偏移
        int index = is_in_memory(page);  // 检查页面是否在内存中

        // 打印当前内存页面状态
        printf("当前内存页面为：");
        for (int j = 0; j < MEMORY_SIZE; j++) {
            if (memory[j] != -1) {
                printf("%d ", memory[j]);
            } else {
                printf("- ");
            }
        }
        printf("\n");

        if (index == -1) {  // 缺页处理
            page_faults++;
            replace_algorithm(i);  // 执行页面置换算法
            index = is_in_memory(page);  // 更新页面所在的内存块索引
            printf("指令 %d: 缺页，物理地址 = 0x%08X\n", instructions[i], (index * INSTRUCTIONS_PER_PAGE + offset) * 4);  // 打印缺页信息
        } else {
            printf("指令 %d: 物理地址 = 0x%08X\n", instructions[i], (index * INSTRUCTIONS_PER_PAGE + offset) * 4);  // 打印物理地址
        }

        if (update_time) {
            update_time(index, i);  // 更新LRU算法中的时间戳
        }
    }
}

// 更新LRU算法中的时间戳
void update_lru_time(int index, int time) {
    memory_time[index] = time;
}

int main() {
    srand(time(0));  // 初始化随机数种子
    generate_instructions();  // 生成指令访问序列
    char choice[10];  // 用于存储用户输入

    while (1) {
        printf("请选择页面置换算法：\n");
        printf("1. OPT\n");
        printf("2. FIFO\n");
        printf("3. LRU\n");
        printf("输入你的选择（1/2/3），输入q退出程序：");
        scanf("%s", choice);  // 读取用户输入

        if (choice[0] == 'q' && choice[1] == '\0') {
            break;  // 退出程序
        }

        // 检查输入是否合法
        if (choice[1] != '\0' || (choice[0] != '1' && choice[0] != '2' && choice[0] != '3')) {
            printf("无效的选择，请重新输入\n");
            continue;  // 提示无效输入并重新输入
        }

        // 根据用户选择运行相应的页面置换算法
        switch (choice[0]) {
            case '1':
                run_simulation(replace_opt, NULL);  // 运行OPT算法模拟
                printf("OPT缺页次数: %d\n", page_faults);
                printf("OPT缺页率: %.2f%%\n", (page_faults / (float)TOTAL_INSTRUCTIONS) * 100);
                break;
            case '2':
                run_simulation(replace_fifo, NULL);  // 运行FIFO算法模拟
                printf("FIFO缺页次数: %d\n", page_faults);
                printf("FIFO缺页率: %.2f%%\n", (page_faults / (float)TOTAL_INSTRUCTIONS) * 100);
                break;
            case '3':
                run_simulation(replace_lru, update_lru_time);  // 运行LRU算法模拟
                printf("LRU缺页次数: %d\n", page_faults);
                printf("LRU缺页率: %.2f%%\n", (page_faults / (float)TOTAL_INSTRUCTIONS) * 100);
                break;
            default:
                printf("无效的选择\n");
                break;
        }
    }

    return 0;
}