用C语言编写,不用for循环一个页面时管理系统使用FIFO、ORT、LRU页面置换算法，如果一个作业的页面走向为：2,3,2,1,5,2,4,5,3,2,5,2,。当分配给改作业的物理页框数为3时，计算访问过程中发生的缺页中断次数和缺页中断率。 要求编程实现求解。在理解三种页面置换算法的原理后不难实现，在此给出实现代码，为了避免代码太乱，在此分为三个程序：

程序一：FIFO页面置换算法的实现

#include <stdio.h>

#define MAX_PAGE_FRAMES 3   // 物理页框数
#define MAX_PAGE_NUM 6      // 页面数
#define EMPTY -1            // 空页框标记

// FIFO页面置换算法
void FIFO(int page_seq[], int page_frames[]) {
    int i, j, k;
    int page_faults = 0;    // 缺页中断次数
    int first_in = 0;       // 首次调入页框下标

    for (i = 0; i < MAX_PAGE_NUM; i++) {
        int page_num = page_seq[i];     // 当前访问的页号
        int is_hit = 0;                 // 是否命中标记

        // 查找页号是否在页框中
        for (j = 0; j < MAX_PAGE_FRAMES; j++) {
            if (page_frames[j] == page_num) {
                is_hit = 1;
                break;
            }
        }

        // 如果没有命中，则发生缺页中断
        if (!is_hit) {
            page_faults++;

            // 如果有空页框，则直接使用
            for (j = 0; j < MAX_PAGE_FRAMES; j++) {
                if (page_frames[j] == EMPTY) {
                    page_frames[j] = page_num;
                    is_hit = 1;
                    break;
                }
            }

            // 如果没有空页框，则替换最早调入的页框
            if (!is_hit) {
                page_frames[first_in] = page_num;
                first_in = (first_in + 1) % MAX_PAGE_FRAMES;
            }
        }

        // 输出当前页框状态
        printf("[%d]:\t", page_num);
        for (k = 0; k < MAX_PAGE_FRAMES; k++) {
            if (page_frames[k] == EMPTY) {
                printf("-\t");
            } else {
                printf("%d\t", page_frames[k]);
            }
        }
        printf("\n");
    }

    // 输出缺页中断率
    printf("FIFO缺页中断次数：%d\n", page_faults);
    printf("FIFO缺页中断率：%.2f%%\n", (float)page_faults / MAX_PAGE_NUM * 100);
}

int main() {
    int page_seq[MAX_PAGE_NUM] = {2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2};   // 页面访问序列
    int page_frames[MAX_PAGE_FRAMES] = {EMPTY};                        // 初始化为空页框

    printf("FIFO页面置换算法：\n");
    FIFO(page_seq, page_frames);

    return 0;
}

程序二：OPT页面置换算法的实现

#include <stdio.h>

#define MAX_PAGE_FRAMES 3   // 物理页框数
#define MAX_PAGE_NUM 6      // 页面数
#define EMPTY -1            // 空页框标记

// OPT页面置换算法
void OPT(int page_seq[], int page_frames[]) {
    int i, j, k;
    int page_faults = 0;    // 缺页中断次数
    int max_distance;       // 最大距离
    int max_distance_page;  // 最大距离的页号

    for (i = 0; i < MAX_PAGE_NUM; i++) {
        int page_num = page_seq[i];     // 当前访问的页号
        int is_hit = 0;                 // 是否命中标记

        // 查找页号是否在页框中
        for (j = 0; j < MAX_PAGE_FRAMES; j++) {
            if (page_frames[j] == page_num) {
                is_hit = 1;
                break;
            }
        }

        // 如果没有命中，则发生缺页中断
        if (!is_hit) {
            page_faults++;

            // 如果有空页框，则直接使用
            for (j = 0; j < MAX_PAGE_FRAMES; j++) {
                if (page_frames[j] == EMPTY) {
                    page_frames[j] = page_num;
                    is_hit = 1;
                    break;
                }
            }

            // 如果没有空页框，则替换访问距离最远的页框
            if (!is_hit) {
                max_distance = 0;
                max_distance_page = EMPTY;

                // 查找每个页框下一次出现的位置，计算距离
                for (j = 0; j < MAX_PAGE_FRAMES; j++) {
                    int distance = 0;
                    for (k = i + 1; k < MAX_PAGE_NUM; k++) {
                        if (page_frames[j] == page_seq[k]) {
                            distance = k - i;
                            break;
                        }
                    }

                    // 如果找到了下一次出现的位置，则比较距离
                    if (distance > 0 && distance > max_distance) {
                        max_distance = distance;
                        max_distance_page = j;
                    }
                }

                // 如果找到了距离最远的页框，则替换
                if (max_distance_page != EMPTY) {
                    page_frames[max_distance_page] = page_num;
                }
            }
        }

        // 输出当前页框状态
        printf("[%d]:\t", page_num);
        for (k = 0; k < MAX_PAGE_FRAMES; k++) {
            if (page_frames[k] == EMPTY) {
                printf("-\t");
            } else {
                printf("%d\t", page_frames[k]);
            }
        }
        printf("\n");
    }

    // 输出缺页中断率
    printf("OPT缺页中断次数：%d\n", page_faults);
    printf("OPT缺页中断率：%.2f%%\n", (float)page_faults / MAX_PAGE_NUM * 100);
}

int main() {
    int page_seq[MAX_PAGE_NUM] = {2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2};   // 页面访问序列
    int page_frames[MAX_PAGE_FRAMES] = {EMPTY};                        // 初始化为空页框

    printf("OPT页面置换算法：\n");
    OPT(page_seq, page_frames);

    return 0;
}

程序三：LRU页面置换算法的实现

#include <stdio.h>

#define MAX_PAGE_FRAMES 3   // 物理页框数
#define MAX_PAGE_NUM 6      // 页面数
#define EMPTY -1            // 空页框标记

// LRU页面置换算法
void LRU(int page_seq[], int page_frames[]) {
    int i, j, k, m;
    int page_faults = 0;    // 缺页中断次数
    int last_use_time[MAX_PAGE_FRAMES] = {0};  // 最近使用时间

    for (i = 0; i < MAX_PAGE_NUM; i++) {
        int page_num = page_seq[i];     // 当前访问的页号
        int is_hit = 0;                 // 是否命中标记

        // 查找页号是否在页框中
        for (j = 0; j < MAX_PAGE_FRAMES; j++) {
            if (page_frames[j] == page_num) {
                is_hit = 1;

                // 更新最近使用时间
                for (m = 0; m < MAX_PAGE_FRAMES; m++) {
                    if (page_frames[m] != EMPTY) {
                        last_use_time[m]++;
                    }
                }
                last_use_time[j] = 0;

                break;
            }
        }

        // 如果没有命中，则发生缺页中断
        if (!is_hit) {
            page_faults++;

            // 如果有空页框，则直接使用
            for (j = 0; j < MAX_PAGE_FRAMES; j++) {
                if (page_frames[j] == EMPTY) {
                    page_frames[j] = page_num;

                    // 更新最近使用时间
                    for (m = 0; m < MAX_PAGE_FRAMES; m++) {
                        if (page_frames[m] != EMPTY) {
                            last_use_time[m]++;
                        }
                    }
                    last_use_time[j] = 0;

                    is_hit = 1;
                    break;
                }
            }

            // 如果没有空页框，则替换最近最久未使用的页框
            if (!is_hit) {
                int max_time = last_use_time[0];
                int max_time_frame = 0;

                for (j = 1; j < MAX_PAGE_FRAMES; j++) {
                    if (last_use_time[j] > max_time) {
                        max_time = last_use_time[j];
                        max_time_frame = j;
                    }
                }

                page_frames[max_time_frame] = page_num;

                // 更新最近使用时间
                for (m = 0; m < MAX_PAGE_FRAMES; m++) {
                    if (page_frames[m] != EMPTY) {
                        last_use_time[m]++;
                    }
                }
                last_use_time[max_time_frame] = 0;
            }
        }

        // 输出当前页框状态
        printf("[%d]:\t", page_num);
        for (k = 0; k < MAX_PAGE_FRAMES; k++) {
            if (page_frames[k] == EMPTY) {
                printf("-\t");
            } else {
                printf("%d\t", page_frames[k]);
            }
        }
        printf("\n");
    }

    // 输出缺页中断率
    printf("LRU缺页中断次数：%d\n", page_faults);
    printf("LRU缺页中断率：%.2f%%\n", (float)page_faults / MAX_PAGE_NUM * 100);
}

int main() {
    int page_seq[MAX_PAGE_NUM] = {2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2};   // 页面访问序列
    int page_frames[MAX_PAGE_FRAMES] = {EMPTY};                        // 初始化为空页框

    printf("LRU页面置换算法：\n");
    LRU(page_seq, page_frames);

    return 0;
}