• 日期: 2027-11-16
  • 标签: 常规

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

#define INSTRUCTION_NUM 320 // 指令总数 #define PAGE_SIZE 1024 // 页面大小 #define MEM_SIZE_MAX 32 // 用户内存最大页数 #define VIRT_MEM_SIZE 32768 // 用户虚存容量32KB

// 虚存中每一页对应指令序列的开始和结束指令下标 struct page_table_entry { int start_instruction; int end_instruction; };

struct page_table_entry page_table[MEM_SIZE_MAX]; // 页面表

// 模拟内存 int memory[MEM_SIZE_MAX][PAGE_SIZE / sizeof(int)];

// 初始化页面表 void init_page_table() { int i, start_instruction = 0, end_instruction = -1; for (i = 0; i < MEM_SIZE_MAX; i++) { start_instruction = end_instruction + 1; end_instruction = start_instruction + 9; page_table[i].start_instruction = start_instruction; page_table[i].end_instruction = end_instruction; } }

// 模拟物理内存，以整形数组形式表示 int physical_mem[MEM_SIZE_MAX * PAGE_SIZE / sizeof(int)];

// 置换算法：最佳置换算法（OPT） int opt_replace() { int i, j, k, max_distance, replace_index;

// 找到最后一个未使用的页
for (k = MEM_SIZE_MAX - 1; k >= 0; k--) {
    if (physical_mem[k * PAGE_SIZE] != -1) {
        break;
    }
}

// 如果内存未满，直接返回空闲物理页面的下标
if (k < MEM_SIZE_MAX - 1) {
    return k + 1;
}

// 找到最长时间未使用的页面，并用新页面替换它
replace_index = 0;
max_distance = page_table[0].end_instruction - page_table[0].start_instruction;
for (i = 1; i < MEM_SIZE_MAX; i++) {
    // 找到该页最后一次被访问的指令
    for (j = page_table[i].end_instruction; j >= page_table[i].start_instruction; j--) {
        if (physical_mem[i * PAGE_SIZE + j % 10] != -1) {
            break;
        }
    }
    int distance = j - page_table[i].start_instruction;
    if (distance > max_distance) {
        replace_index = i;
        max_distance = distance;
    }
}
return replace_index;

}

// 置换算法：先进先出算法（FIFO） int fifo_replace(int *used_index, int used_num) { int i, replace_index = 0, min_time_stamp = physical_mem[0]; // 找到最早进入内存的页面，将其替换出去 for (i = 1; i < MEM_SIZE_MAX; i++) { if (physical_mem[i * PAGE_SIZE] == -1) { return i; } if (physical_mem[i * PAGE_SIZE] < min_time_stamp) { replace_index = i; min_time_stamp = physical_mem[i * PAGE_SIZE]; } } return replace_index; }

// 置换算法：最近最久未使用算法（LRU） int lru_replace() { int i, j, replace_index = 0, min_time_stamp = physical_mem[0]; for (i = 1; i < MEM_SIZE_MAX; i++) { if (physical_mem[i * PAGE_SIZE] == -1) { return i; } // 找到该页最后一次被访问的指令 for (j = page_table[i].end_instruction; j >= page_table[i].start_instruction; j--) { if (physical_mem[i * PAGE_SIZE + j % 10] != -1) { break; } } int time_stamp = physical_mem[i * PAGE_SIZE] + j; if (time_stamp < min_time_stamp) { replace_index = i; min_time_stamp = time_stamp; } } return replace_index; }

// 置换算法：最不经常使用算法（LFU） int lfu_replace(int *used_index, int used_num) { int i, replace_index = 0, min_count = physical_mem[0]; // 找到使用次数最少的页面，并将其替换出去 for (i = 1; i < MEM_SIZE_MAX; i++) { if (physical_mem[i * PAGE_SIZE] == -1) { return i; } int j; int count = 0; for (j = 0; j < used_num; j++) { if (used_index[j] >= page_table[i].start_instruction && used_index[j] <= page_table[i].end_instruction) { count++; } } if (count < min_count) { replace_index = i; min_count = count; } } return replace_index; }

// 置换算法：最近未使用算法（NUR） int nur_replace() { int i, replace_index = 0, min_distance = 4; // 找到距离上次访问最远的页面，并将其替换出去 for (i = 0; i < MEM_SIZE_MAX; i++) { if (physical_mem[i * PAGE_SIZE] == -1) { return i; } int j; int distance = 4; for (j = page_table[i].start_instruction; j <= page_table[i].end_instruction; j++) { if (physical_mem[i * PAGE_SIZE + j % 10] != -1) { int d = used_index[j] - physical_mem[i * PAGE_SIZE + j % 10]; if (d < distance) { distance = d; } } } if (distance > min_distance) { replace_index = i; min_distance = distance; } } return replace_index; }

// 计算指令序列对应的页地址流 int get_page_sequence(int *instruction_sequence, int *page_sequence, int sequence_size) { int i, j; for (i = 0; i < sequence_size; i++) { page_sequence[i] = instruction_sequence[i] / PAGE_SIZE; }

// 删除相邻重复页号，即合并连续的相同页
j = 1;
for (i = 1; i < sequence_size; i++) {
    if (page_sequence[i] != page_sequence[i - 1]) {
        page_sequence[j++] = page_sequence[i];
    }
}
return j;

}

// 计算页面失效次数 int calculate_page_faults(int *page_sequence, int sequence_size, int mem_size, int (*replace)(int *, int)) { int page_faults = 0, i, j; int used_index[MEM_SIZE_MAX * PAGE_SIZE / sizeof(int)]; int used_num = 0;

for (i = 0; i < MEM_SIZE_MAX; i++) {
    for (j = 0; j < PAGE_SIZE / sizeof(int); j++) {
        physical_mem[i * PAGE_SIZE + j] = -1;
    }
}

for (i = 0; i < sequence_size; i++) {
    // 如果该页已经在内存中，则更新该页的最近访问时间，并记录该指令序列的下标
    int page_num = page_sequence[i];
    int start_instruction = page_table[page_num].start_instruction;
    if (physical_mem[page_num * PAGE_SIZE] != -1) {
        physical_mem[page_num * PAGE_SIZE + i % 10] = i;
        used_index[used_num++] = i;
        continue;
    }

    // 如果该页不在内存中，则进行页面置换操作
    int replace_index = replace(used_index, used_num);
    used_num = 0;
    page_faults++;
    int k;
    for (k = 0; k < PAGE_SIZE / sizeof(int); k++) {
        memory[page_num][k] = rand() % 10000;
        physical_mem[replace_index * PAGE_SIZE + k] = i;
        physical_mem[replace_index * PAGE_SIZE + PAGE_SIZE / sizeof(int) + k] = memory[page_num][k];
    }
}
return page_faults;

}

int main() { srand(time(0)); int instruction_sequence[INSTRUCTION_NUM]; int page_sequence[INSTRUCTION_NUM / (PAGE_SIZE / sizeof(int))]; int i, j;

// 产生指令序列
int m = rand() % 320;
instruction_sequence[0] = m;
for (i = 1; i < INSTRUCTION_NUM; i++) {
    int r = rand() % 4;
    if (r == 0 && m < 319) { // 50%的指令顺序执行
        m++;
    } else if (r == 1 && m > 0) { // 25%的指令分布在前地址部分
        m--;
    } else if (r == 2 && m < 310) { // 25%的指令分布在后地址部分
        m++;
    } else {
        m = rand() % 320;
    }
    instruction_sequence[i] = m;
}

// 计算指令序列对应的页地址流
int page_num = get_page_sequence(instruction_sequence, page_sequence, INSTRUCTION_NUM);

printf("Instruction sequence:\n");
for (i = 0; i < INSTRUCTION_NUM; i++) {
    printf("%d ", instruction_sequence[i]);
    if (i % 10 == 9) {
        printf("\n");
    }
}

printf("\nPage sequence:\n");
for (i = 0; i < page_num; i++) {
    printf("%d ", page_sequence[i]);
    if (i % 10 == 9) {
        printf("\n");
    }
}

// 初始化页面表
init_page_table();

// 计算各种置换算法的命中率
int page_faults_opt = calculate_page_faults(page_sequence, page_num, MEM_SIZE_MAX, opt_replace);
int page_faults_fifo = calculate_page_faults(page_sequence, page_num, MEM_SIZE_MAX, fifo_replace);
int page_faults_lru = calculate_page_faults(page_sequence, page_num, MEM_SIZE_MAX, lru_replace);
int page_faults_lfu = calculate_page_faults(page_sequence, page_num, MEM_SIZE_MAX, lfu_replace);
int page_faults_nur = calculate_page_faults(page_sequence, page_num, MEM_SIZE_MAX, nur_replace);

double hit_rate_opt = 1.0 - (double)page_faults_opt / page_num;
double hit_rate_fifo = 1.0 - (double)page_faults_fifo / page_num;
double hit_rate_lru = 1.0 - (double)page_faults_lru / page_num;
double hit_rate_lfu = 1.0 - (double)page_faults_lfu / page_num;
double hit_rate_nur = 1.0 - (double)page_faults_nur / page_num;

printf("\nOptimal Replacement Algorithm: Hit rate = %.2f%%\n", hit_rate_opt * 100);
printf("FIFO Replacement Algorithm: Hit rate = %.2f%%\n", hit_rate_fifo * 100);
printf("LRU Replacement Algorithm: Hit rate = %.2f%%\n", hit_rate_lru * 100);
printf("LFU Replacement Algorithm: Hit rate = %.2f%%\n", hit_rate_lfu * 100);
printf("NUR Replacement Algorithm: Hit rate = %.2f%%\n", hit_rate_nur * 100);

return 0;

}

页面置换算法模拟：OPT、FIFO、LRU、LFU、NUR

原文地址: https://www.cveoy.top/t/topic/nWg0 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录