最佳置换算法C代码如何实现？

什么是最佳置换算法？

最佳置换算法是一种页面置换算法，其核心思想是：当需要淘汰一个页面时，选择在未来最长时间内不会被访问的页面进行置换。

这个算法提供了一个理论上的最优性能上限，因为它的决策总是“最好”的，它有一个致命的缺点：它需要预知未来的页面访问序列，这在实际操作系统中是无法实现的，它更多地被用作一个衡量其他实用算法（如 LRU, FIFO）性能的基准。

算法实现思路

1. 数据结构：

   • 我们需要一个数组来表示物理内存中的页面帧（frames[]）。
   • 我们需要一个数组来存储未来的页面访问序列（page_sequence[]）。
   • 我们需要一个变量 page_faults 来统计缺页中断的次数。

2. 核心逻辑：

   • 遍历页面访问序列中的每一个页面 page。
   • 检查 page 是否已在内存中：
     • 如果在,则继续处理下一个页面。
     • 如果不在，则发生一次缺页中断 (page_faults++)。
   • 处理缺页中断：
     • 内存有空闲帧：直接将新页面 page 放入一个空闲的帧中。
     • 内存已满：这是算法的关键。
       1. 遍历当前内存中的所有页面。
       2. 对于内存中的每一个页面，查找它在未来页面序列中下一次出现的位置。
       3. 找到内存中所有页面中，下一次出现位置最远的那个页面。
       4. 用当前需要访问的新页面 page 替换掉这个“最远”的页面。

C 语言代码实现

下面是一个完整的、可运行的 C 语言程序。

#include <stdio.h>
#include <limits.h> // 用于 INT_MAX
#include <stdbool.h> // 用于 bool 类型
// 函数声明
void optimalPageReplacement(int pages[], int n, int capacity);
int findOptimalPage(int pages[], int n, int frames[], int capacity, int current_index);
int main() {
    // 页面访问序列
    int pages[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
    int n = sizeof(pages) / sizeof(pages[0]);
    // 内存中的页面帧数量
    int capacity = 4;
    printf("最佳置换算法 实现\n");
    printf("页面访问序列: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", pages[i]);
    }
    printf("\n");
    printf("内存帧容量: %d\n", capacity);
    printf("----------------------------------------\n");
    optimalPageReplacement(pages, n, capacity);
    return 0;
}
/**
 * @brief 执行最佳置换算法
 * @param pages 页面访问序列
 * @param n 序列长度
 * @param capacity 内存帧容量
 */
void optimalPageReplacement(int pages[], int n, int capacity) {
    int frames[capacity]; // 存储当前内存中的页面
    int page_faults = 0;  // 缺页中断计数器
    int hits = 0;         // 命中计数器
    // 初始化帧数组，-1 表示空闲
    for (int i = 0; i < capacity; i++) {
        frames[i] = -1;
    }
    printf("访问\t\t帧内容\t\t缺页/命中\n");
    printf("----------------------------------------\n");
    for (int i = 0; i < n; i++) {
        int page = pages[i];
        bool found = false;
        // 检查当前页面是否已在内存中 (命中)
        for (int j = 0; j < capacity; j++) {
            if (frames[j] == page) {
                found = true;
                hits++;
                break;
            }
        }
        // 如果命中，打印信息并继续
        if (found) {
            printf("%d\t\t", page);
            for (int j = 0; j < capacity; j++) {
                printf("%d ", frames[j]);
            }
            printf("\t\t命中\n");
            continue;
        }
        // 如果未命中，发生缺页中断
        page_faults++;
        printf("%d\t\t", page);
        // 检查是否有空闲帧
        bool has_free_frame = false;
        for (int j = 0; j < capacity; j++) {
            if (frames[j] == -1) {
                frames[j] = page; // 将页面放入空闲帧
                has_free_frame = true;
                break;
            }
        }
        // 如果有空闲帧，打印信息并继续
        if (has_free_frame) {
            for (int j = 0; j < capacity; j++) {
                printf("%d ", frames[j]);
            }
            printf("\t\t缺页 (放入空闲帧)\n");
            continue;
        }
        // 如果没有空闲帧，需要置换页面
        int page_to_replace = findOptimalPage(pages, n, frames, capacity, i);
        // 找到要替换的页面在 frames 数组中的索引
        int replace_index = -1;
        for (int j = 0; j < capacity; j++) {
            if (frames[j] == page_to_replace) {
                replace_index = j;
                break;
            }
        }
        // 执行替换
        frames[replace_index] = page;
        // 打印信息
        for (int j = 0; j < capacity; j++) {
            printf("%d ", frames[j]);
        }
        printf("\t\t缺页 (替换 %d)\n", page_to_replace);
    }
    printf("----------------------------------------\n");
    printf("总缺页中断次数: %d\n", page_faults);
    printf("总命中次数: %d\n", hits);
    printf("缺页率: %.2f%%\n", (float)page_faults / n * 100);
}
/**
 * @brief 在需要置换时，找到未来最长时间不会被访问的页面
 * @param pages 页面访问序列
 * @param n 序列长度
 * @param frames 当前内存中的页面
 * @param capacity 内存帧容量
 * @param current_index 当前访问的页面在序列中的索引
 * @return int 需要被替换的页面号
 */
int findOptimalPage(int pages[], int n, int frames[], int capacity, int current_index) {
    int farthest = current_index; // 记录最远出现的位置
    int result = -1;            // 记录要替换的页面
    for (int i = 0; i < capacity; i++) {
        int page = frames[i];
        int next_use = n; // 默认为序列末尾之后，即“永不使用”
        // 在未来的序列中查找该页面下一次出现的位置
        for (int j = current_index + 1; j < n; j++) {
            if (pages[j] == page) {
                next_use = j;
                break;
            }
        }
        // 如果这个页面在未来不会被再次使用，直接返回它
        if (next_use == n) {
            return page;
        }
        // 更新“最远”的页面
        if (next_use > farthest) {
            farthest = next_use;
            result = page;
        }
    }
    return result;
}

代码解释

1. main() 函数:

   • 定义了页面访问序列 pages[] 和内存容量 capacity。
   • 调用 optimalPageReplacement() 函数来执行算法。
   • 最后打印出总缺页次数、命中次数和缺页率。

2. optimalPageReplacement() 函数:

   • 初始化 frames 数组（内存帧），用 -1 表示空闲。
   • 遍历每个 page：
     • 命中检查：遍历 frames，page 已存在，则 hit++,跳过后续操作。
     • 缺页处理：
       • 有空闲帧：找到 frames 中值为 -1 的位置，将 page 放入。
       • 无空闲帧：调用 findOptimalPage() 函数，找到需要被替换的页面,然后进行替换。
   • 在每一步都打印当前访问的页面、内存帧的状态以及是“命中”还是“缺页”。

3. findOptimalPage() 函数:

   • 这是算法的核心，它接收当前内存中的页面列表 frames 和当前访问的位置 current_index。
   • 遍历 frames 中的每一个页面。
   • 对于每个页面，它在 pages 序列的 current_index 之后搜索，找到它下一次出现的位置 next_use。
   • 如果一个页面在 current_index 之后再也没有出现（即 next_use 一直没找到，循环到末尾），那么这个页面就是最佳置换候选,直接返回它。
   • 如果所有页面未来都会被使用，就选择其中下一次出现位置最远的那个页面进行置换，通过比较 next_use 和 farthest 来实现。

示例运行结果

使用给定的页面序列 {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2} 和容量 4,程序运行结果如下：

最佳置换算法 实现
页面访问序列: 7 0 1 2 0 3 0 4 2 3 0 3 2 
内存帧容量: 4
----------------------------------------
访问            帧内容            缺页/命中
----------------------------------------
7               7 -1 -1 -1         缺页 (放入空闲帧)
0               7 0 -1 -1          缺页 (放入空闲帧)
1               7 0 1 -1           缺页 (放入空闲帧)
2               7 0 1 2            缺页 (放入空闲帧)
0               7 0 1 2            命中
3               7 0 1 3            缺页 (替换 2)
0               7 0 1 3            命中
4               7 0 4 3            缺页 (替换 1)
2               7 0 4 2            缺页 (替换 3)
3               7 0 4 3            缺页 (替换 2)
0               7 0 4 3            命中
3               7 0 4 3            命中
2               7 0 4 2            缺页 (替换 3)
----------------------------------------
总缺页中断次数: 9
总命中次数: 3
缺页率: 69.23%

这个结果清晰地展示了算法每一步的决策过程,帮助理解最佳置换算法是如何工作的。