实验7-页面置换算法

Question

第1关：最佳置换算法
任务描述
本关任务：编程实现最佳置换算法（OPT）算法。

相关知识
为了完成本关任务，你需要掌握：1.最佳置换算法（OPT）算法原理。

最佳置换算法
最佳置换算法（Optimal Page Replacement Algorithm）是一种理论上的页面置换算法，它通过选择以后不再使用或者在最长时间内不再被访问的页面进行置换，从而达到最低的缺页率。
最佳置换算法是一种理想中的算法，它通过预测未来将会访问的页面进行页面置换，无疑，这将会最大程度的利用好资源，毕竟我们都已经知道未来会发生的事情，那自然可以做出 最好的选择，只是一种理想中的算法罢了。

算法流程
1.初始化一个大小为物理块数的帧数组，用于存储当前在内存中的页面。
2.遍历给定的引用串中的每个页面。
3.对于每个页面，检查它是否已经在帧数组中。如果是，则跳过该页面并继续遍历下一个页面。
4.如果该页面不在帧数组中，则需要进行页面置换。找到帧数组中以后不再使用或者在最长时间内不再被访问的页面，并用当前页面替换它。
5.重复步骤3和4，直到遍历完引用串中的所有页面。
6.计算缺页次数和缺页率。

编程要求
根据提示，在右侧编辑器补充代码，补全最佳置换算法（OPT）的核心代码。

测试说明
平台会对你编写的代码进行测试：

输出：
见预期输出

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

int findOptimal(int pages[], int n, int index, int frame[], int f) {
    int res = -1;
    int farthest = index;
    //请补充代码，大约14行
 
    return (res == -1) ? 0 : res;
}

void optimalPage(int pages[], int n, int f) {
    int frame[f];
    for (int i = 0; i < f; i++)
        frame[i] = -1;

    int hit = 0;
    //请补充代码，大约13行
  
    printf("\n\n缺页次数: %d", n - hit);
    printf("\n缺页率: %f\n", (n - hit) / (double)n);
}

int main() {
    int pages[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3};
    int n = sizeof(pages) / sizeof(pages[0]);
    int f = 4;

    optimalPage(pages, n, f);

    return 0;
}

第2关：先进先出置换算法
任务描述
本关任务：编写一个能实现先进先出置换算法（FIFO）的C程序。

相关知识
为了完成本关任务，你需要掌握：1.先进先出置换算法（FIFO）原理。

先进先出算法
先进先出算法是一种简单的页面置换算法，它通过选择最早进入内存的页面进行置换，从而达到页面置换的目的。
一种比较朴素的思想`

算法流程
1.初始化一个大小为物理块数的帧数组，用于存储当前在内存中的页面。
2.遍历给定的引用串中的每个页面。
3.对于每个页面，检查它是否已经在帧数组中。如果是，则跳过该页面并继续遍历下一个页面。
4.如果该页面不在帧数组中，则需要进行页面置换。选择最早进入内存的页面进行置换，并用当前页面替换它。
5.重复步骤3和4，直到遍历完引用串中的所有页面。
6.计算缺页次数和缺页率。

编程要求
根据提示，在右侧编辑器补充代码，完成先进先出置换算法（FIFO）并求出缺页参数。

测试说明
平台会对你编写的代码进行测试：

预期输出：

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

void fifoPage(int pages[], int n, int f) {
    int frame[f];
    for (int i = 0; i < f; i++)
        frame[i] = -1;

    int hit = 0;
    int pointer = 0;
   //请补充FIFO算法的代码，约18行
     
    printf("\n\n缺页次数: %d", n - hit);
    printf("\n缺页率: %f\n", (n - hit) / (double)n);
}

int main() {
    int pages[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3};
    int n = sizeof(pages) / sizeof(pages[0]);
    int f = 4;

    fifoPage(pages, n, f);

    return 0;
}

第3关：最近最久未使用置换算法
任务描述
本关任务：编写一个最近最久未使用算法的C程序。

相关知识
为了完成本关任务，你需要掌握：1.最近最久未使用（LRU）算法原理。

最近最久未使用算法
最近最久未使用算法是一种常用的页面置换算法，它通过选择最近最久未被访问的页面进行置换，从而达到页面置换的目的。

算法流程
1.初始化一个大小为物理块数的帧数组，用于存储当前在内存中的页面。
2.初始化一个大小为物理块数的时间数组，用于记录每个页面最近被访问的时间。
3.遍历给定的引用串中的每个页面。
4.对于每个页面，检查它是否已经在帧数组中。如果是，则更新该页面在时间数组中对应的值，并跳过该页面继续遍历下一个页面。
5.如果该页面不在帧数组中，则需要进行页面置换。选择时间数组中值最小的页面进行置换，并用当前页面替换它，同时更新该页面在时间数组中对应的值。
6.重复步骤4和5，直到遍历完引用串中的所有页面。
7.计算缺页次数和缺页率。

编程要求
根据提示，在右侧编辑器补充代码，实现最近最久未使用（LRU）算法并计算缺页参数。

测试说明
平台会对你编写的代码进行测试：

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

int findLRU(int time[], int f) {
    int min = time[0];
    int res = 0;
    for (int i = 1; i < f; i++) {
        if (time[i] < min) {
            min = time[i];
            res = i;
        }
    }
    return res;
}

void lruPage(int pages[], int n, int f) {
    int frame[f];
    for (int i = 0; i < f; i++)
        frame[i] = -1;

    int time[f];
    for (int i = 0; i < f; i++)
        time[i] = 0;

    int hit = 0;
   //请补充LRU算法的代码，约18行

    printf("\n\n缺页次数: %d", n - hit);
    printf("\n缺页率: %f\n", (n - hit) / (double)n);
}

int main() {
    int pages[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3};
    int n = sizeof(pages) / sizeof(pages[0]);
    int f = 4;

    lruPage(pages, n, f);

    return 0;
}

Answer 1

//最佳置换
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int findOptimal(int pages[], int n, int index, int frame[], int f) {
    int res = -1;
    int farthest = index;

    // 查找当前帧中不再使用的页面
    for (int i = 0; i < f; i++) {
        int j;
        for (j = index; j < n; j++) {
            if (frame[i] == pages[j]) {
                // 找到页面在未来的使用位置
                if (j > farthest) {
                    farthest = j;
                    res = i; // 更新要替换的页面索引
                }
                break;
            }
        }
        // 如果页面在后续中没有出现，直接替换
        if (j == n) {
            return i; // 返回当前帧中未使用的页面
        }
    }
    return (res == -1) ? 0 : res; // 返回要替换的页面索引
}

void optimalPage(int pages[], int n, int f) {
    int frame[f];
    for (int i = 0; i < f; i++)
        frame[i] = -1;

    int hit = 0;
    for (int i = 0; i < n; i++) {
        int j;
        // 检查页面是否在帧中
        for (j = 0; j < f; j++) {
            if (frame[j] == pages[i]) {
                hit++; // 页面命中
                break;
            }
        }

        // 如果页面不在帧中，进行替换
        if (j == f) {
            int optimalIndex = findOptimal(pages, n, i + 1, frame, f);
            frame[optimalIndex] = pages[i]; // 替换页面
        }
    }

    printf("\n\n缺页次数: %d", n - hit);
    printf("\n缺页率: %f\n", (n - hit) / (double)n);
}

int main() {
    int pages[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3};
    int n = sizeof(pages) / sizeof(pages[0]);
    int f = 4;

    optimalPage(pages, n, f);

    return 0;
}