操作系统：页面置换算法_页面置换算法代码

作者：IT小白 | 2024-02-29 03:59:52

踩

页面置换算法代码

（一）实验目的

编写一个程序，实现第九章所述的FIFO、OPT和LRU页面置换算法。

（二）实验要求及内容

首先，生成一个随机的页面引用串，其中页码的范围为0~9。
将这个随机页面引用串应用到每个算法，记录每个算法引起的缺页次数，列出每次页面置换的换出页序号，计算缺页率。
系统分配给用户的页面帧的数量可选：3~7，具体分配策略可自行定义。
假设采用请求分页（按需调页）。

（三）代码：直接运行可能会报错，如果报错，可参考（五）的解决方案


#include <stdio.h>
#include<time.h>
#include <stdlib.h>
//初始化队列
void initializeList(int list[], int number) {
    for (int i = 0; i < number; i++) {
        list[i] = -1;
    }
}
//展示队列状态
void showList(int list[], int number) {
    for (int i = 0; i < number; i++) {
        printf("%2d", list[i]);
    }
    printf("\n");
}
 
//展示当前内存状态
void showMemoryList(int list[], int phyBlockNum) {
    for (int i = 0; i < phyBlockNum; i++) {
        if (list[i] == -1) {
            break;
        }
        printf(" |%d|", list[i]);
    }
    printf("\n");
}
 
void informationCount(int missingCount, int replaceCount, int pageNum) {
    printf("\n缺页次数:%d   缺页率:%d/%d\n", missingCount, missingCount, pageNum);
    double result = (double)(pageNum - missingCount) / (double)pageNum;
    printf("置换次数:%d  命中率:%.2f\n\n", replaceCount, result);
}
 
//找到该页面下次要访问的位置
int getNextPosition(int currentPage, int currentPosition, int strList[], int pageNum) {
 
    for (int i = currentPosition + 1; i < pageNum; i++) {
        if (strList[i] == currentPage) {
            return i;
        }
    }
 
    return 100;
}
 
//最佳置换算法
void replacePageByOPT(int memoryList[], int phyBlockNum, int strList[], int pageNum) {
 
    //置换次数
    int replaceCount = 0;
    //缺页次数
    int missingCount = 0;
 
    //记录在内存的物理块的下一次访问位置
    int nextPosition[7];
    //初始化
    initializeList(nextPosition, phyBlockNum);
 
    //记录当前页面的访问情况: 0 未访问
    int isVisited;
 
    for (int i = 0; i < pageNum; i++) {
        isVisited = 0;
        //判断是否需要置换->内存已满且需要访问的页面不在内存中
        for (int j = 0; j < phyBlockNum; j++) {
            if (memoryList[j] == strList[i]) {
                //该页面已经存在内存中
                //记录下一次访问它的位置
                nextPosition[j] = getNextPosition(memoryList[j], i, strList, pageNum);
 
                //修改访问情况
                isVisited = 1;
 
                //展示
                printf("%d\n", strList[i]);
                break;
            }
            if (memoryList[j] == -1) {
                //页面不在内存中且内存未满->直接存入
                memoryList[j] = strList[i];
                nextPosition[j] = getNextPosition(memoryList[j], i, strList, pageNum);
 
                missingCount++;
 
                //修改访问情况
                isVisited = 1;
 
                //展示
                printf("%d\n\n", strList[i]);
                showMemoryList(memoryList, phyBlockNum);
                printf("\n\n");
                break;
            }
        }
 
        if (!isVisited) {
 
            //当前页面还没访问过
            //内存已满且当前访问不在内存中->进行置换
            //1.寻找到最晚才被访问到的页面
            int max = 0;
            for (int k = 1; k < phyBlockNum; k++) {
                if (nextPosition[max] < nextPosition[k]) {
                    max = k;
                }
            }
 
 
            //2.将该位置的页面换出
            printf("被置换的页面号是：%d\n", memoryList[max]);//打印被调出内存的页号
            memoryList[max] = strList[i];
            nextPosition[max] = getNextPosition(memoryList[max], i, strList, pageNum);
 
            missingCount++;
            replaceCount++;
 
            //展示
            printf("%d\n", strList[i]);
            showMemoryList(memoryList, phyBlockNum);
            printf("\n\n");
        }
    }
    informationCount(missingCount, replaceCount, pageNum);
}
//先进先出置换算法
void replacePageByFIFO(int memoryList[], int phyBlockNum, int strList[], int pageNum) {
 
    //置换次数
    int replaceCount = 0;
    //缺页次数
    int missingCount = 0;
 
    //记录当前最早进入内存的下标
    int pointer = 0;
 
    //记录当前页面的访问情况: 0 未访问
    int isVisited = 0;
    for (int i = 0; i < pageNum; i++) {
        isVisited = 0;
 
        //判断是否需要置换->内存已满且需要访问的页面不在内存中
        for (int j = 0; j < phyBlockNum; j++) {
            if (memoryList[j] == strList[i]) {
                //该页面已经存在内存中
                //修改访问情况
                isVisited = 1;
                //修改访问时间
                //展示
                printf("%d\n\n", strList[i]);
                break;
            }
            if (memoryList[j] == -1) {
                //页面不在内存中且内存未满->直接存入
                memoryList[j] = strList[i];
                //修改访问情况
                isVisited = 1;
                missingCount++;
                //展示
                printf("%d\n", strList[i]);
                showMemoryList(memoryList, phyBlockNum);
                printf("\n\n");
                break;
            }
        }
 
        if (!isVisited) {
            //当前页面还未被访问过->需要进行页面置换
            //直接把这个页面存到所记录的下标中
            printf("被置换的页面号是：%d\n", memoryList[pointer]);//打印被调出内存的页号
            memoryList[pointer] = strList[i];
 
            //下标指向下一个
            pointer++;
 
            //如果到了最后一个，将下标归零
            if (pointer > phyBlockNum - 1) {
                pointer = 0;
            }
 
 
            missingCount++;
            replaceCount++;
 
            //展示
            printf("%d\n", strList[i]);
            showMemoryList(memoryList, phyBlockNum);
            printf("\n\n");
        }
    }
    informationCount(missingCount, replaceCount, pageNum);
}
 
//最近最久未使用置换算法
void replacePageByLRU(int memoryList[], int phyNum, int strList[], int pageNum) {
 
    //置换次数
    int replaceCount = 0;
    //缺页次数
    int missingCount = 0;
 
    //记录内存中最近一次访问至今的时间
    int timeRecord[7];
    //初始化
    initializeList(timeRecord, phyNum);
 
    //记录当前页面的访问情况: 0 未访问
    int isVisited = 0;
 
    //记录已经在内存中的页面数量
    int pageCount = 0;
    for (int i = 0; i < pageNum; i++) {
        isVisited = 0;
 
        //时间加一
        for (int p = 0; p < pageCount; p++) {
            if (memoryList[p] != -1) {
                timeRecord[p] ++;
            }
        }
 
        //是否需要置换
        for (int j = 0; j < phyNum; j++) {
            if (memoryList[j] != -1) {
                timeRecord[j] ++;
            }
            if (memoryList[j] == strList[i]) {
                //该页面已经存在内存中
                //修改访问情况
                isVisited = 1;
                //重置访问时间
                timeRecord[j] = -1;
                //展示
                printf("%d\n\n", strList[i]);
                break;
            }
            if (memoryList[j] == -1) {
                //页面不在内存中且内存未满->直接存入
                memoryList[j] = strList[i];
                pageCount++;
                //修改访问情况
                isVisited = 1;
                //修改访问时间
                timeRecord[j] ++;
 
                missingCount++;
                //展示
                printf("%d\n", strList[i]);
                showMemoryList(memoryList, phyNum);
                printf("\n\n");
                break;
            }
        }
 
        if (!isVisited) {
            //需要置换
            //1.遍历时间记录表，寻找最久未访问的页面所在的内存下标
            int max = 0;
            for (int k = 0; k < phyNum; k++) {
                if (timeRecord[max] < timeRecord[k]) {
                    max = k;
                }
            }
            printf("被置换的页面号是：%d\n", memoryList[max]);//打印被调出内存的页号
            //2.将该位置的页面换出
            memoryList[max] = strList[i];
            timeRecord[max] = -1;
 
            missingCount++;
            replaceCount++;
 
            //展示
            printf("%d\n", strList[i]);
            showMemoryList(memoryList, phyNum);
            printf("\n\n");
 
        }
    }
    informationCount(missingCount, replaceCount, pageNum);
}
 
int main(int argc, const char* argv[]) {
 
    //物理块的数量
    int phyBlockNum;
    printf("请输入物理块数量:\n");
    scanf("%d", &phyBlockNum);
 
    //生成内存队列
    int memoryList[7];
    //初始化内存状态
    initializeList(memoryList, phyBlockNum);//未使用的内存块标记为-1；
    //showMemoryList(memoryList,phyBlockNum);
 
    //页面数量
    int pageNum;
    printf("请输入要访问的页面总数:\n");
    scanf("%d", &pageNum);
 
    //保存页面号引用串
    int pageNumStrList[100];
    int a;
    srand((unsigned)time(NULL));
    for (int i = 0; i < pageNum; i++) {
 
        a = rand() % 10;
        pageNumStrList[i] = a;
    }
 
    int chose;
    while (1) {
        printf("请选择所需的置换算法:\n");
        printf("1.OPT 2.FIFO 3.LRU 4.退出\n");
        printf("你选择的置换算法是:", pageNum);
        scanf("%d", &chose);
        printf("\n");
        switch (chose) {
        case 1:
            printf("生成的%d个页面号:\n", pageNum);
            showList(pageNumStrList, pageNum);
            replacePageByOPT(memoryList, phyBlockNum, pageNumStrList, pageNum);
            //重新初始化内存
            initializeList(memoryList, phyBlockNum);
            break;
        case 2:
            printf("生成的%d个页面号:\n", pageNum);
            showList(pageNumStrList, pageNum);
            replacePageByFIFO(memoryList, phyBlockNum, pageNumStrList, pageNum);
            //重新初始化内存
            initializeList(memoryList, phyBlockNum);
            break;
        case 3:
            printf("生成的%d个页面号:\n", pageNum);
            showList(pageNumStrList, pageNum);
            replacePageByLRU(memoryList, phyBlockNum, pageNumStrList, pageNum);
            //重新初始化内存
            initializeList(memoryList, phyBlockNum);
            break;
        default:
            return 0;
            break;
        }
    }
 
    return 0;
}

（四）实验截图

（五）温馨提示：直接将代码放在visual studio运行可能发生以下错误：

解决方案：

1）右击当前代码文件--->>属性

2）C/C++ ----->> 常规------>>双击“SDL检查”后面的文本框，使其改变为“否”------->>"确定"

3）做好以上修改，就可正常运行代码

仅供参考，如有不足，请指出！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/163604