1. 实验目的

1. 通过软件模拟页面置换过程，加深对请求页式存储管理实现原理的理解。
2. 理解和掌握 OPT、FIFO 和 LRU 三种页面置换算法，深入分析三者之间的优缺点。

2. 实验内容

2.1 实验代码

▶

Code

/*
 * 页面置换算法模拟程序
 *
 * 系统为作业分配 PM_PAGE 个物理块, 用三种经典页面置换算法模拟访问过程并统计缺页/置换情况:
 *
 *   FIFO 先进先出    : 淘汰最早装入的页面(命中不改变装入次序);
 *   LRU  最近最久未用: 淘汰最久未被访问的页面(命中刷新其最近访问时刻);
 *   OPT  最佳置换    : 淘汰"将来最晚才会再次使用(或不再使用)"的页面;
 */
#include <stdio.h>
#include <stdlib.h>

#define VM_PAGE 7    // 访问序列中出现的虚页数
#define PM_PAGE 4    // 分配给作业的物理块数
#define REF_NUM 18   // 页面访问序列长度
#define NO_FRAME -1  // 空物理块标记
#define NO_PICK -1   // 淘汰策略找不到对象时的返回值

/* 单个物理块(页框)的状态 */
typedef struct frame_s {
    int vpage;      // 当前装入的虚页号, NO_FRAME 表示该块空闲
    int last_use;   // 最近访问时刻: LRU 依此判断谁最久未被使用
    int load_time;  // 装入时刻: FIFO 依此判断谁先进入
} frame_t;

/* 一次页面置换模拟的统计结果 */
typedef struct stat_s {
    int fault;    // 缺页次数
    int replace;  // 置换(换页)次数
} page_stat_t;

typedef int (*replace_policy)(const frame_t frames[], int count, const int refs[], int pos, int total);

// 固定的页面访问序列, 作为只读基准数据供所有算法使用
static const int g_refs[REF_NUM] = {1, 2, 3, 4, 2, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6};

/**
 * @brief 打印页面访问序列
 */
static void print_ref_data()
{
    printf("页面访问序列\r\n");
    printf("---------------------------------------------------------------------\r\n");
    printf("\t步号\t\t访问页\r\n");
    for (int i = 0; i < REF_NUM; i++) {
        printf("\t%-8d\t%-8d\r\n", i + 1, g_refs[i]);
    }
}

/**
 * @brief 将物理块数组格式化为字符串, 如 "[1][2][-][-]"
 *
 * @param frames 物理块数组
 * @param count  物理块个数
 * @param buf    输出缓冲区, 长度需不小于 4 * count + 1
 */
static void format_frames(const frame_t frames[], int count, char *buf)
{
    char *p = buf;
    for (int i = 0; i < count; i++) {
        p += sprintf(p, frames[i].vpage == NO_FRAME ? "[-]" : "[%d]", frames[i].vpage);
    }
    *p = '\0';
}

/**
 * @brief FIFO 淘汰策略: 换出最早装入的页面
 *
 * @param frames 物理块数组
 * @param count  物理块个数
 * @param refs   页面访问序列
 * @param pos    当前访问位置
 * @param total  序列长度
 * @return int 被淘汰的物理块下标
 */
static int pick_fifo(const frame_t frames[], int count, const int refs[], int pos, int total)
{
    int best = NO_PICK;
    for (int i = 0; i < count; i++) {
        if (frames[i].vpage == NO_FRAME) {
            continue;
        }
        if (best == NO_PICK || frames[i].load_time < frames[best].load_time) {
            best = i;
        }
    }
    return best;
}

/**
 * @brief LRU 淘汰策略: 换出最久未被访问的页面
 * 依赖框架在每次命中时刷新 last_use, 因此换出的始终是最近最久未用的页面.
 *
 * @param frames 物理块数组
 * @param count  物理块个数
 * @param refs   页面访问序列
 * @param pos    当前访问位置
 * @param total  序列长度
 * @return int 被淘汰的物理块下标
 */
static int pick_lru(const frame_t frames[], int count, const int refs[], int pos, int total)
{
    int best = NO_PICK;
    for (int i = 0; i < count; i++) {
        if (frames[i].vpage == NO_FRAME) {
            continue;
        }
        if (best == NO_PICK || frames[i].last_use < frames[best].last_use) {
            best = i;
        }
    }
    return best;
}

/**
 * @brief OPT 淘汰策略: 换出将来最晚才会被再次使用(或不再使用)的页面
 * 逐个计算当前各驻留页面在当前位置之后首次出现的下标, 取最远者淘汰;
 * 将来不再出现的页面视为最远, 会被优先淘汰.
 *
 * @param frames 物理块数组
 * @param count  物理块个数
 * @param refs   页面访问序列
 * @param pos    当前访问位置
 * @param total  序列长度
 * @return int 被淘汰的物理块下标
 */
static int pick_opt(const frame_t frames[], int count, const int refs[], int pos, int total)
{
    int best      = NO_PICK;
    int best_next = -1;  // 记录当前"下次使用最晚"对应的下一次出现位置
    for (int i = 0; i < count; i++) {
        if (frames[i].vpage == NO_FRAME) {
            continue;
        }
        int next = total;  // 将来不再使用视为最晚
        for (int j = pos + 1; j < total; j++) {
            if (refs[j] == frames[i].vpage) {
                next = j;
                break;
            }
        }
        if (best == NO_PICK || next > best_next) {
            best      = i;
            best_next = next;
        }
    }
    return best;
}

/**
 * @brief 在全新的物理块副本上, 按给定淘汰策略模拟整条页面访问序列
 *
 * @param algo_name 算法名称
 * @param pick      缺页淘汰策略
 * @return page_stat_t 该算法下的缺页次数与置换次数
 */
static page_stat_t run_page_sim(const char *algo_name, replace_policy pick)
{
    // 每个算法都从空的物理块副本开始, 互不影响
    frame_t frames[PM_PAGE];
    for (int i = 0; i < PM_PAGE; i++) {
        frames[i].vpage     = NO_FRAME;
        frames[i].load_time = -1;
        frames[i].last_use  = -1;
    }

    int fault   = 0;  // 累计缺页次数
    int replace = 0;  // 累计置换次数

    printf("\r\n%s 算法执行过程\r\n", algo_name);
    printf("---------------------------------------------------------------------\r\n");
    printf("\t步号\t\t访问页\t\t结果\t累计缺页\t物理块内容\r\n");
    for (int pos = 0; pos < REF_NUM; pos++) {
        int page = g_refs[pos];

        // 查找本次访问的页面是否已驻留在某个物理块中
        int hit = NO_PICK;
        for (int i = 0; i < PM_PAGE; i++) {
            if (frames[i].vpage == page) {
                hit = i;
                break;
            }
        }

        const char *result;
        if (hit != NO_PICK) {
            // 命中: 刷新最近访问时刻, 供 LRU 判断"最近最久未用"
            frames[hit].last_use = pos;
            result               = "命中";
        } else {
            // 缺页
            fault++;
            result = "缺页";

            // 先寻找空闲物理块直接装入
            int free_slot = NO_PICK;
            for (int i = 0; i < PM_PAGE; i++) {
                if (frames[i].vpage == NO_FRAME) {
                    free_slot = i;
                    break;
                }
            }
            if (free_slot != NO_PICK) {
                frames[free_slot].vpage     = page;
                frames[free_slot].load_time = pos;
                frames[free_slot].last_use  = pos;
            } else {
                // 物理块已满, 按策略淘汰一页后再装入
                int victim               = pick(frames, PM_PAGE, g_refs, pos, REF_NUM);
                frames[victim].vpage     = page;
                frames[victim].load_time = pos;
                frames[victim].last_use  = pos;
                replace++;
            }
        }

        char buf[32];
        format_frames(frames, PM_PAGE, buf);
        printf("\t%-8d\t%-8d\t%-8s\t%-8d\t%s\r\n", pos + 1, page, result, fault, buf);
    }
    printf("---------------------------------------------------------------------\r\n");
    printf("\t缺页次数:%d\t缺页率:%.4f\t置换次数:%d\t置换率:%.4f\r\n", fault, (float)fault / REF_NUM, replace,
           (float)replace / REF_NUM);

    page_stat_t st;
    st.fault   = fault;
    st.replace = replace;
    return st;
}

/**
 * @brief 打印一行算法结果对比
 *
 * @param name 算法名称
 * @param st   统计结果
 */
static void print_stat_row(const char *name, page_stat_t st)
{
    printf("\t%-16s\t%-8d\t%-8.4f\t%-8d\t%-8.4f\r\n", name, st.fault, (float)st.fault / REF_NUM, st.replace,
           (float)st.replace / REF_NUM);
}

int main()
{
    print_ref_data();

    // 依次在各自独立的物理块副本上运行三种置换算法
    page_stat_t fifo = run_page_sim("FIFO 先进先出", pick_fifo);
    page_stat_t lru  = run_page_sim("LRU 最近最久未用", pick_lru);
    page_stat_t opt  = run_page_sim("OPT 最佳置换", pick_opt);

    // 汇总三种算法的统计结果便于对比
    printf("\r\n算法结果对比\r\n");
    printf("---------------------------------------------------------------------\r\n");
    printf("\t算法\t\t\t缺页次数\t缺页率\t\t置换次数\t置换率\r\n");
    print_stat_row("FIFO", fifo);
    print_stat_row("LRU", lru);
    print_stat_row("OPT", opt);
    printf("---------------------------------------------------------------------\r\n");
    return EXIT_SUCCESS;
}

3. 分析与思考

1. 分析实验结果产生的原因，总结从实验观察到的结果。分析三种置换算法的缺页率的差异。

FIFO 算法每次先替换最先进入的页面，LRU 算法每次先替换最近最久未使用的页面，OPT 算法每次先替换将来最长时间内不再被访问的页面。通过计算得到，FIFO 算法缺页 13 次，置换 9 次；LRU 算法缺页 10 次，置换 6 次；OPT 算法缺页 7 次，置换 3 次。

2. 结合操作系统课程中讲授的原理，写出本次实验的心得体会。

FIFO 算法、LRU 算法和 OPT 算法是操作系统中用来管理内存的置换算法，用于决定哪些页应该被从内存中交换出去，以便为正在运行的进程腾出空间。其中：

• FIFO 算法是选择在内存中驻留时间最久的页面予以替换，实现简单，要求的硬件支持较少。但是，它所依据的条件是各个页面调入内存的时间，而页面调入内存的先后并不能反映页面的使用情况。

• LRU 算法是选择过去最长时间未被访问的页面予以替换，利用“最近的过去”代替“最近的将来”，以此模拟 Optimal 算法，是实际应用中缺页率最低的算法。但是，其实际应用时要求较多的硬件支持，因而多采用近似算法。

• OPT 算法是选择永不使用或在未来最长时间内不再被访问的页面予以替换。它可保证获得最低的缺页率，并且可以用来评价其他算法。但是，目前该算法是无法实现的。