目录

前言

本实验的目的是通过编程模拟不同的页面替换算法，比较它们的缺页率和命中率，加深对操作系统内存管理的理解。 本实验用C语言编写，实现了最优替换算法（OPT）、先进先出替换算法（FIFO）和最近未使用算法（LRU）。 实验中，从文本文件中读取页号引用字符串，输出每次访问页面时内存中的页面状态，以及最终的缺页次数、缺页率和命中率。 本文档将介绍实验的设计思路、流程图、代码和运行结果。

目的

(1)了解虚拟内存的内存分页管理策略，掌握请求调度和替换的工作过程。

（2）掌握常用页面替换算法的思想，编译程序，在计算机屏幕上显示调试结果，检测计算机计算与书面计算的一致性。

(3)了解页面大小和实际内存容量对命中率的影响。

实验内容

(1)编程实现最优替换算法(OPT)算法

(2) 编程实现先进先出(FIFO)算法

(3) 编程实现最近未使用（LRU）算法

基本要求：

(1) 选择以上两种算法中的任意一种来实现。

(2)根据给定的参考字符串和物理块的数量，可以在屏幕上输出算法对应的位移图，以及缺页次数和缺页率。

实验过程最优替换算法

最优替换算法（Page）是一种理论上的页面替换算法，通过选择将不再使用或最长一段时间内不会被访问的页面进行替换，以达到最低的页面错误率。

根据我的理解，最优替换算法是一种理想的算法。 它通过预测将来将访问的页面来替换页面。 毫无疑问，这将充分利用资源。 毕竟，我们都知道未来会发生什么。 当然，我们可以对事情做出最好的选择。 不幸的是，世界上的一切怎么可能都按计划进行呢？ 因此，至少目前来看，它仍然只是一个理想的算法。

代码

#include 
#include 
#include 
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 l = findOptimal(pages, n, i + 1, frame, f);
            frame[l] = pages[i];
        }
        printf("\n");
        for (int k = 0; k < f; k++)
            printf("%d ", frame[k]);
    }
    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;
}

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

设计理念

其想法是替换不再使用或最长一段时间不会被访问的页面，以实现最低的页面错误率。 最优替换算法是一种理论算法，因为它需要提前知道参考字符串。 页面中的每个页面将来被访问的时间在实际应用中是不可能实现的。 然而，它可以作为其他页面替换算法的性能评估标准。

运算结果

上面的输出显示了最优替换算法在每个时刻的帧阵列状态，以及最终的缺页次数和缺页率。 使用参考字符串{7,0,1,2,0,3,0,4,2,3,0,3}和物理块号4来演示最佳替换算法。

先进先出算法

先进先出算法是一种简单的页面替换算法。 它通过选择最早进入内存的页面进行替换来达到页面替换的目的。

一个比较简单的想法

代码

#include 
#include 
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;
    for (int i = 0; i < n; i++) {
        bool allocated = false;
        for (int j = 0; j < f; j++)
            if (frame[j] == pages[i]) {
                hit++;
                allocated = true;
                break;
            }
        if (!allocated) {
            frame[pointer] = pages[i];
            pointer = (pointer + 1) % f;
        }
        printf("\n");
        for (int k = 0; k < f; k++)
            printf("%d ", frame[k]);
    }
    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和4，直到遍历完引用字符串中的所有页面。 计算缺页次数和缺页率。流程图

流程图是一样的，只是页面替换不同。 替换时，选择最早进入内存的页进行替换。

设计理念

其思想是通过选择最早进入内存的页面进行替换，从而达到页面替换的目的。 先进先出算法是一种简单且易于实现的页面替换算法，但它并不能保证最低的页面错误率。 在某些情况下，它甚至可能导致比其他算法更高的页面错误率。

运算结果

上面的输出显示了每个时刻先进先出算法的帧数组状态，以及最终的缺页次数和缺页率。 ，它使用参考字符串 {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3} 和物理块号 4 来演示先进先出 (FIFO)算法。

最近未使用的算法

最近使用的算法是常用的页面替换算法。 它通过选择最长时间未被访问的页面来达到页面替换的目的。

代码

#include 
#include 
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;
    for (int i = 0; i < n; i++) {
        bool allocated = false;
        for (int j = 0; j < f; j++)
            if (frame[j] == pages[i]) {
                hit++;
                time[j] = i + 1;
                allocated = true;
                break;
            }
        if (!allocated) {
            int lru = findLRU(time, f);
            frame[lru] = pages[i];
            time[lru] = i + 1;
        }
        printf("\n");
        for (int k = 0; k < f; k++)
            printf("%d ", frame[k]);
    }
    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;
}

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

初始化一个额外的时间数组来记录每个页面最后一次被访问的时间。 替换时，选择时间数组中值最小的页面进行替换，并更新时间数组中该页面对应的值。

设计理念

设计思路是通过选择最近、最长时间没有访问过的页面来达到页面替换的目的。 最近使用的算法是一种常用且有效的页面替换算法，在很多情况下可以实现较低的页面错误率。 然而，它需要额外的空间来存储每个页面的最后一次访问时间，并且每次访问都需要更新时间数组，这增加了算法的时间复杂度。

运算结果

上面的输出显示了每个时刻最近未使用的算法的帧阵列状态，以及最终的缺页次数和缺页率。 它使用参考字符串 {7, 0, 1, 2, 0, 3, 0 , 4, 2, 3, 0, 3} 和物理块的数量 4 来演示最近未使用 (LRU) 算法。

总结

本文总结了计算机操作系统实验中的三种页面替换算法：最优替换算法（OPT）、先进先出替换算法（FIFO）和最近最少使用替换算法（LRU）。 页替换算法是当内存已满且需要访问的页不在内存中时，选择内存中的一页进行换出的方法。 不同的算法有不同的选择标准和效率。 最好的替换算法是选择未来最长时间不再被访问的页面进行换出。 它可以保证最低的页面错误率和替换率，但这是不可能实现的，因为我们无法预测未来的页面访问情况。 先进先出替换算法选择最先进入内存的页面并将其换出。 实现简单，但效率不高，可能会导致频繁访问的页面被频繁换出。 最近未使用的替换算法选择最长时间没有被访问的页面并将其换出。 它根据过去的页面访问来预测未来的访问。 不过这种预测不一定准确，所以它的效率也不是很高。 。 本文通过C语言编写程序实现了这三种算法，并对它们进行了比较和分析。