操作系统课程设计:常用页面置换算法(OPT、FIFO、LRU)的实现及缺页率的计算(C语言)

本文主要是介绍操作系统课程设计:常用页面置换算法(OPT、FIFO、LRU)的实现及缺页率的计算(C语言),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

名人说:莫听穿林打叶声,何妨吟啸且徐行。—— 苏轼《定风波·莫听穿林打叶声》
Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder)

目录

      • 一、效果图
      • 二、代码(带注释)
      • 三、说明

一、效果图

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

二、代码(带注释)

//创作者:Code_流苏(CSDN)
//未经允许,禁止转载发布,可自己学习使用
//代码实现时期:大二操作系统期末
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#define N 320 //指令数
#define M 32 //页数
#define P 4 //内存块数
#define Q 10 //每页指令数
int i, m, m1, m2, choice;
int order[N]; //指令序列数组//OPT算法
void OPT(int order[])
{int i, j, k, max, index, count = 0;int memory[P]; //内存块数组int flag[M]; //标记数组,记录每个页面是否在内存中int next[M]; //记录每个页面下一次出现的位置//初始化内存块和标记数组for (i = 0; i < P; i++)memory[i] = -1;for (i = 0; i < M; i++)flag[i] = 0;//遍历指令序列for (i = 0; i < N; i++){int page = order[i] / Q; //计算当前指令所在的页面号if (flag[page] == 1) //如果页面已经在内存中,显示物理地址{printf("指令%d的物理地址为%d\n", order[i], memory[page] * Q + order[i] % Q);}else //如果页面不在内存中,发生缺页{count++; //缺页次数加一int empty = -1; //记录是否有空闲的内存块for (j = 0; j < P; j++){if (memory[j] == -1) //找到空闲的内存块{empty = j;break;}}if (empty != -1) //如果有空闲的内存块,直接调入页面{memory[empty] = page;flag[page] = 1;printf("指令%d的物理地址为%d\n", order[i], empty * Q + order[i] % Q);}else //如果没有空闲的内存块,需要进行页面置换{//计算每个页面下一次出现的位置for (j = 0; j < M; j++){next[j] = N + 1; //默认为无穷大for (k = i + 1; k < N; k++){if (order[k] / Q == j) //找到下一次出现的位置{next[j] = k;break;}}}//找到下一次出现最晚的页面,即最佳置换页面max = next[memory[0]];index = 0;for (j = 1; j < P; j++){if (next[memory[j]] > max){max = next[memory[j]];index = j;}}//置换该页面,并显示物理地址flag[memory[index]] = 0;memory[index] = page;flag[page] = 1;printf("指令%d的物理地址为%d\n", order[i], index * Q + order[i] % Q);}}}printf("OPT算法的缺页率为%.2f%%\n", count * 100.0 / N); //显示缺页率
}//FIFO算法
void FIFO(int order[])
{int i, j,  index, count = 0;int memory[P]; //内存块数组int flag[M]; //标记数组,记录每个页面是否在内存中int queue[P]; //队列数组,记录每个内存块中的页面进入的先后顺序//初始化内存块、标记数组和队列数组for (i = 0; i < P; i++)memory[i] = -1;for (i = 0; i < M; i++)flag[i] = 0;for (i = 0; i < P; i++)queue[i] = -1;//遍历指令序列for (i = 0; i < N; i++){int page = order[i] / Q; //计算当前指令所在的页面号if (flag[page] == 1) //如果页面已经在内存中,显示物理地址{printf("指令%d的物理地址为%d\n", order[i], memory[page] * Q + order[i] % Q);}else //如果页面不在内存中,发生缺页{count++; //缺页次数加一int empty = -1; //记录是否有空闲的内存块for (j = 0; j < P; j++){if (memory[j] == -1) //找到空闲的内存块{empty = j;break;}}if (empty != -1) //如果有空闲的内存块,直接调入页面,并更新队列{memory[empty] = page;flag[page] = 1;printf("指令%d的物理地址为%d\n", order[i], empty * Q + order[i] % Q);for (j = 0; j < P; j++){if (queue[j] == -1){queue[j] = empty;break;}}}else //如果没有空闲的内存块,需要进行页面置换{//找到队列头部的内存块,即最先进入的内存块,作为置换对象index = queue[0];//置换该内存块中的页面,并显示物理地址flag[memory[index]] = 0;memory[index] = page;flag[page] = 1;printf("指令%d的物理地址为%d\n", order[i], index * Q + order[i] % Q);//更新队列,将队列头部的元素移到队尾for (j = 0; j < P - 1; j++)queue[j] = queue[j + 1];queue[P - 1] = index;}}}printf("FIFO算法的缺页率为%.2f%%\n", count * 100.0 / N); //显示缺页率
}//LRU算法
void LRU(int order[])
{int i, j, min, index, count = 0;int memory[P]; //内存块数组int flag[M]; //标记数组,记录每个页面是否在内存中int last[M]; //记录每个页面最近一次出现的位置//初始化内存块和标记数组for (i = 0; i < P; i++)memory[i] = -1;for (i = 0; i < M; i++)flag[i] = 0;//遍历指令序列for (i = 0; i < N; i++){int page = order[i] / Q; //计算当前指令所在的页面号if (flag[page] == 1) //如果页面已经在内存中,显示物理地址,并更新最近一次出现的位置{printf("指令%d的物理地址为%d\n", order[i], memory[page] * Q + order[i] % Q);last[page] = i;}else //如果页面不在内存中,发生缺页{count++; //缺页次数加一int empty = -1; //记录是否有空闲的//内存块for (j = 0; j < P; j++){if (memory[j] == -1) //找到空闲的内存块{empty = j;break;}}if (empty != -1) //如果有空闲的内存块,直接调入页面,并更新最近一次出现的位置{memory[empty] = page;flag[page] = 1;printf("指令%d的物理地址为%d\n", order[i], empty * Q + order[i] % Q);last[page] = i;}else //如果没有空闲的内存块,需要进行页面置换{//找到最近一次出现最早的页面,即最近最久未使用的页面,作为置换对象min = last[memory[0]];index = 0;for (j = 1; j < P; j++){if (last[memory[j]] < min){min = last[memory[j]];index = j;}}//置换该页面,并显示物理地址,并更新最近一次出现的位置flag[memory[index]] = 0;memory[index] = page;flag[page] = 1;printf("指令%d的物理地址为%d\n", order[i], index * Q + order[i] % Q);last[page] = i;}}}printf("LRU算法的缺页率为%.2f%%\n", count * 100.0 / N); //显示缺页率
}void menu()
{while (1) //使用一个循环,让用户可以多次选择算法{system("cls");printf("请选择使用哪种算法:\n");printf("1. OPT算法\n");printf("2. FIFO算法\n");printf("3. LRU算法\n");printf("0. 退出程序\n");printf("我的选择是:");scanf("%d", &choice); //输入选择switch (choice) //根据选择调用相应的算法{case 1:printf("使用OPT算法:\n");OPT(order);break;case 2:printf("使用FIFO算法:\n");FIFO(order);break;case 3:printf("使用LRU算法:\n");LRU(order);break;case 0:printf("已退出程序,感谢您的使用!\n");return ; //退出程序default:printf("输入错误,请重新输入\n");break;}printf("按任意键回到菜单页\n");system("pause");Sleep(100);}
}//主函数
int main()
{int flag=0;srand(time(NULL)); //设置随机数种子//生成指令序列m = rand() % N; //随机选取一条起始执行指令,其序号为morder[0] = m; //将其放入指令序列数组中for (i = 1; i < N; i++){if (i % 4 == 1) //顺序执行下一条指令,即序号为m+1的指令{m++;order[i] = m;}else if (i % 4 == 2) //通过随机数,跳转到前地址部分[0,m-1]中的某条指令处,其序号为m1{m1 = rand() % m;order[i] = m1;}else if (i % 4 == 3) //顺序执行下一条指令,即序号为m1+1的指令{m1++;order[i] = m1;}else //通过随机数,跳转到后地址部分[m1+2,319]中的某条指令处,其序号为m2{m2 = rand() % (N - m1 - 2) + m1 + 2;order[i] = m2;}}printf("指令序列为:\n");for (i = 0; i < N; i++)printf("%d ", order[i]);printf("\n");printf("是否进入菜单?(1代表是,0代表否)\n");printf("请输入您的选择:");scanf("%d",&flag);if(flag==1){menu();}return 0;
}

三、说明

上述代码实现的是一个模拟操作系统页面置换算法的程序。主要实现了三种页面置换算法:最佳置换(OPT)、先进先出(FIFO)和最近最久未使用(LRU)。此外,还包含一个生成指令序列的部分和一个简单的用户界面来选择不同的置换算法。下面是对代码主要部分的解释:

  1. 程序流程

    • 首先,程序使用随机数生成器生成一个模拟的指令序列。
    • 接着,程序提供了一个菜单,让用户选择要使用的页面置换算法。
    • 根据用户的选择,程序将展示所选算法的页面置换过程和缺页率。
  2. 页面置换算法的实现

    • OPT算法:在页面置换时,选择将来最长时间内不会被访问的页面进行置换。
    • FIFO算法:按照页面进入内存的顺序进行置换,最先进入的页面最先被置换。
    • LRU算法:在页面置换时,选择最长时间没有被访问的页面进行置换。
  3. 关键变量

    • N:指令数。
    • M:页数。
    • P:内存块数。
    • Q:每页指令数。
    • order[]:存储指令序列的数组。
    • memory[]:表示内存块的数组,存储当前各内存块中的页面。
    • flag[]:标记数组,记录每个页面是否在内存中。
  4. 生成指令序列

    • 指令序列生成遵循一定的规则,以模拟程序的执行过程。
  5. 用户交互

    • 程序通过打印菜单和接收用户输入来控制算法的选择和程序的流程。
  6. 输出

    • 对于每一条指令,程序将输出其物理地址。
    • 在算法执行完毕后,程序将输出该算法的缺页率。

这个程序通过实际的模拟和数据,可以更好帮助我们理解各种页面置换算法的工作原理和性能差异。

Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder)
点赞加关注,收藏不迷路!本篇文章对你有帮助的话,还请多多点赞支持!

这篇关于操作系统课程设计:常用页面置换算法(OPT、FIFO、LRU)的实现及缺页率的计算(C语言)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/595608

相关文章

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

一文详解如何使用Java获取PDF页面信息

《一文详解如何使用Java获取PDF页面信息》了解PDF页面属性是我们在处理文档、内容提取、打印设置或页面重组等任务时不可或缺的一环,下面我们就来看看如何使用Java语言获取这些信息吧... 目录引言一、安装和引入PDF处理库引入依赖二、获取 PDF 页数三、获取页面尺寸(宽高)四、获取页面旋转角度五、判断

Spring StateMachine实现状态机使用示例详解

《SpringStateMachine实现状态机使用示例详解》本文介绍SpringStateMachine实现状态机的步骤,包括依赖导入、枚举定义、状态转移规则配置、上下文管理及服务调用示例,重点解... 目录什么是状态机使用示例什么是状态机状态机是计算机科学中的​​核心建模工具​​,用于描述对象在其生命

Spring Boot 结合 WxJava 实现文章上传微信公众号草稿箱与群发

《SpringBoot结合WxJava实现文章上传微信公众号草稿箱与群发》本文将详细介绍如何使用SpringBoot框架结合WxJava开发工具包,实现文章上传到微信公众号草稿箱以及群发功能,... 目录一、项目环境准备1.1 开发环境1.2 微信公众号准备二、Spring Boot 项目搭建2.1 创建

IntelliJ IDEA2025创建SpringBoot项目的实现步骤

《IntelliJIDEA2025创建SpringBoot项目的实现步骤》本文主要介绍了IntelliJIDEA2025创建SpringBoot项目的实现步骤,文中通过示例代码介绍的非常详细,对大家... 目录一、创建 Spring Boot 项目1. 新建项目2. 基础配置3. 选择依赖4. 生成项目5.

深入理解Go语言中二维切片的使用

《深入理解Go语言中二维切片的使用》本文深入讲解了Go语言中二维切片的概念与应用,用于表示矩阵、表格等二维数据结构,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录引言二维切片的基本概念定义创建二维切片二维切片的操作访问元素修改元素遍历二维切片二维切片的动态调整追加行动态

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》:本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录

SpringBoot+EasyExcel实现自定义复杂样式导入导出

《SpringBoot+EasyExcel实现自定义复杂样式导入导出》这篇文章主要为大家详细介绍了SpringBoot如何结果EasyExcel实现自定义复杂样式导入导出功能,文中的示例代码讲解详细,... 目录安装处理自定义导出复杂场景1、列不固定,动态列2、动态下拉3、自定义锁定行/列,添加密码4、合并