2023年操作系统七次实验报告常用页面置换算法模拟实验.docx

天道酬勤 操作系统,七次实验报告,常用页面置换算法模拟实验 操作系统课程第七次实验报告 姓名 学号 系 计算机 任课教师 指导教师 评阅教师 实验地点 综合楼B102 实验时间 2023-9-26 实验课表现 出勤和个人表现Q1(15+15〔组长评分〕=30分) 得分：实验 总分 (Q1+Q2+Q3+Q4) 实验完成情况Q2(45分(组长与教师评分的加权平均)) 得分：实验编号与实验名称：实验七、常用页面置换算法模拟实验 实验目的：通过模拟实现请求页式存储管理的几种根本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种根本页面置换算法的根本思想和实现过程，并比拟它们的效率。 实验内容及要求〔详见实验讲义与实验指导书〕：要求：1〕要求用你熟悉的程序设计语言编写和调试一个页面置换模拟程序；要求在主函数中测试。 2〕实验报告中必须包括：设计思想、数据定义〔包括详细说明〕、处理流程〔详细算法描述和算法流程图〕、源代码、运行结果、体会等局部。 3〕必须模拟本实验内容中提到的算法中的至少2种页面置换算法。 4〕比拟不同页面置换算法的效率 内容：编写一个程序，使用以下页面置换算法中的某2种分别模拟一个分页系统，并统计同一个页面访问序列情况下不同页面置换算法引发的缺页中断次数。 1、第二次时机算法〔Second Chance〕2、最近最少使用算法〔Least Recently Used，LRU 〕3、最不常用算法〔Not Frequently Used，NFU〕4、最近未使用算法〔Not Recently Used ，NRU〕5、时钟页面置换算法 6、老化算法〔aging〕页框的数量固定为4，虚拟页面数为8。实验输入为访问页面序列，比方0，1 ，3 ，2，7，1 实验用到的软件〔：〕DevC++,Visio 实验内容及关键步骤〔代码〕Q3〔15分〕得分：流程图：输入页面访问序列 取访问的页号 查页表 是否缺页？ 是 置缺页标志flag为’x’ 按算法不同淘汰一页面 调入所访问的页面 否 FIFO算法流程图 LRU算法流程图：函数关系解释图：实现结果：图1 图2 代码：#include <stdio.h> #include <stdlib.h> #define MEMORY_SIZE 4 /x物理块数x/ #define PROESS_SIZE 8 /x页面号引用串个数x/#include <stdio.h> #include <stdlib.h> /x全局变量x/ int mSIZE=4; int pSIZE=8; static int memery[4]={0}; /x物理块中的页号x/ static int page[8]={0}; /x页面号引用串x/ static int temp[8][4]={0}; /x辅助数组x/ /x置换算法函数x/ void FIFO(); void LRU(); void OPT(); void designBy(); /x辅助函数x/ void print(unsigned int t); /x主函数x/ int main() { int i,k,code; designBy(); system(“color 0A“); puts(“请依次输入页面号(8个)：“); for(i=0;i<pSIZE;i++) scanf(“%1d“,&page[i]); system(“cls“); system(“color 0E“); do{ puts(“输入的页面号引用串为：“); for(k=0;k<=(pSIZE-1)/20;k++) { for(i=20xk;(i<pSIZE)&&(i<20x(k+1));i++) { if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf(“%d＼n“,page[i]); else printf(“%d “,page[i]); } } printf(“x x x x x x x x x x x x x x x x x x x x x x x＼n“); printf(“x 请选择页面置换算法：＼t＼t＼t x＼n“); printf(“x ----------------------------------------- x＼n“); printf(“x 1.先进先出(FIFO) 2.最近最久未使用(LRU) x＼n“); printf(“x 3.退出 x＼n“); printf(“x x x x x x x x x x x x x x x x x x x x x x x＼n“); printf(“请选择操作：[ ]＼b＼b“); scanf(“%d“,&code); switch(code) { case 1: FIFO(); break; case 2: LRU(); break; case 3: system(“cls“); system(“color 0A“); exit(0); default: printf(“输入错误，请重新输入：“); } printf(“按任意键重新选择置换算法：>>>“); getch(); system(“cls“); }while (code!=3); getch(); } void print(unsigned int t) { int i,j,k,l; int flag; for(k=0;k<=(pSIZE-1)/20;k++) { for(i=20xk;(i<pSIZE)&&(i<20x(k+1));i++) { if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf(“%d＼n“,page[i]); else printf(“%d “,page[i]); } for(j=0;j<mSIZE;j++) { for(i=20xk;(i<mSIZE+20xk)&&(i<pSIZE);i++) { if(i>=j) printf(“ |%d|“,temp[i][j]); else printf(“ | |“); } for(i=mSIZE+20xk;(i<pSIZE)&&(i<20x(k+1));i++) { for(flag=0,l=0;l<mSIZE;l++) if(temp[i][l]==temp[i-1][l]) flag++; if(flag==mSIZE)/x页面在物理块中x/ printf(“ “); else printf(“ |%d|“,temp[i][j]); } /x每行显示20个x/ if(i%20==0) continue; printf(“＼n“); } } printf(“----------------------------------------＼n“); printf(“缺页次数：%d＼t＼t“,t+mSIZE); printf(“缺页率：%d/%d＼n“,t+mSIZE,pSIZE); printf(“置换次数：%d＼t＼t“,t); printf(“访问命中率：%d%%＼n“,(pSIZE-(t+mSIZE))x100/pSIZE); printf(“----------------------------------------＼n“); } /x先进先出页面置换算法x/ void FIFO() { int memery[10]={0}; int time[10]={0}; /x记录进入物理块的时间x/ int i,j,k,m; int max=0; /x记录换出页x/ int count=0; /x记录置换次数x/ /x前mSIZE个数直接放入x/ for(i=0;i<mSIZE;i++) { memery[i]=page[i]; time[i]=i; for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } for(i=mSIZE;i<pSIZE;i++) { /x判断新页面号是否在物理块中x/ for(j=0,k=0;j<mSIZE;j++) { if(memery[j]!=page[i]) k++; } if(k==mSIZE) /x如果不在物理块中x/ { count++; /x计算换出页x/ max=time[0]<time[1]0:1; for(m=2;m<mSIZE;m++) if(time[m]<time[max]) max=m; memery[max]=page[i]; time[max]=i; /x记录该页进入物理块的时间x/ for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } else { for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } } print(count); } /x最近最久未使用置换算法x/ void LRU() { int memery[10]={0}; int flag[10]={0}; /x记录页面的访问时间x/ int i,j,k,m; int max=0; /x记录换出页x/ int count=0; /x记录置换次数x/ /x前mSIZE个数直接放入x/ for(i=0;i<mSIZE;i++) { memery[i]=page[i]; flag[i]=i; for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } for(i=mSIZE;i<pSIZE;i++) { /x判断新页面号是否在物理块中x/ for(j=0,k=0;j<mSIZE;j++) { if(memery[j]!=page[i]) k++; else flag[j]=i; /x刷新该页的访问时间x/ } if(k==mSIZE) /x如果不在物理块中x/ { count++; /x计算换出页x/ max=flag[0]<flag[1]0:1; for(m=2;m<mSIZE;m++) if(flag[m]<flag[max]) max=m; memery[max]=page[i]; flag[max]=i; /x记录该页的访问时间x/ for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } else { for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } } // compute(); print(count); } /x显示设计者信息x/ void designBy() { printf(“┏━━━━━━━━━━━━━━━━━━━━━━━━━┓＼n“); printf(“┃㊣ 实验七：页面置换算法 ㊣┃＼n“); printf(“┃ 学号：1001010042 ┃＼n“); printf(“┃ 姓名：黄浩全 <Dev-C++ 4.9.9.0>┃＼n“); printf(“┣━━━━━━━━━━━━━━━━━━━━━━━━━┫＼n“); } 实验过程中遇到的问题解决方法与实验体会Q4〔需手写，10分〕得分：1、在FIFO算法可以很容易用数组实现，而LRU算法可以用数组实现，不过用结构体会更明显简单。结构体成员变量可以记录页号进入的时间，和最近使用的记录。相比照数组更容易理解和实现。 2:首先，FIFO〔先进先出〕算法和LRU〔最近未使用算法〕两者之间，FIFO算法明显会比LRU容易理解，而且比LRU算法较容易实现，但在性能方面，LRU确实在优化方面做的比拟理想。再且在考虑页框和页表号之间的问题用代码可以容易模拟，但是真是在物理内存块中是如何实现，那确实是很难以理解，需要真正理解到内存内部的知识才知道这两个算法是怎么实现的。 评阅教师特殊评语：评阅教师：日 期：