淮海工学院计算机科学系实 验 报 告 书课 程 名 ： 操作系统原理题目：虚拟存储器管理页面置换算法模拟实验班级：学号：姓名：评语：成绩：指导教师：批阅时间：年月日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 15 页 - - - - - - - - - 操作系统原理实验报告- 1 - 一、实验目的与要求1.目的：请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。2.要求：本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO 和 LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10 个） ，对这些虚页访问的页地址流（其长度可以事先给定，例如20 次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。二、实验说明1设计中虚页和实页的表示本设计利用C语言的结构体来描述虚页和实页的结构。pn pfn time 虚页结构实页结构在虚页结构中，pn 代表虚页号，因为共10 个虚页，所以pn 的取值范围是09。pfn 代表实页号，当一虚页未装入实页时，此项值为-1 ；当该虚页已装入某一实页时，此项值为所装入的实页的实页号 pfn 。 time 项在 FIFO 算法中不使用，在LRU中用来存放对该虚页的最近访问时间。在实页结构中中， pn 代表虚页号， 表示 pn 所代表的虚页目前正放在此实页中。pfn 代表实页号，取值范围（ 0n-1 ）由动态指派的实页数n 所决定。 next 是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4 点。2关于缺页次数的统计为计算命中率， 需要统计在 20 次的虚页访问中命中的次数。为此，程序应设置一个计数器count ，来统计虚页命中发生的次数。每当所访问的虚页的pfn 项值不为 -1 ，表示此虚页已被装入某实页内，此虚页被命中，count 加 1。最终命中率 =count/20*100% 。3LRU算法中“最近最久未用”页面的确定为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime ，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前pn pfn next 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 15 页 - - - - - - - - - 操作系统原理实验报告- 2 - countime 值，表示该虚页的最后一次被访问时间。当LRU算法需要置换时，从所有已分配实页的虚页中找出 time 值为最小的虚页就是“最近最久未用”的虚页面，应该将它置换出去。4算法中实页的组织因为能分配的实页数n 是在程序运行时由用户动态指派的，所以应使用链表组织动态产生的多个实页。为了调度算法实现的方便，可以考虑引入free 和 busy 两个链表： free链表用于组织未分配出去的实页， 首指针为 free_head ，初始时 n 个实页都处于free链表中； busy 链表用于组织已分配出去的实页，首指针为busy_head ，尾指针为busy_tail，初始值都为null 。当所要访问的一个虚页不在实页中时， 将产生缺页中断。此时若 free链表不为空， 就取下链表首指针所指的实页，并分配给该虚页。若free链表为空，则说明n 个实页已全部分配出去，此时应进行页面置换：对于FIFO算法要将 busy_head 所指的实页从busy 链表中取下，分配给该虚页，然后再将该实页插入到busy链表尾部； 对于 LRU算法则要从所有已分配实页的虚页中找出time 值为最小的虚页， 将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。三、程序流程图1.FIFO 算法开始判断该虚页是否已经调入内存直接访问请求调页记录缺页数判断Free 链表是否为空调入空闲块置换出最先进去的页面修改内存状态i+i=0输出算法结果结束YYYNNi20N名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 15 页 - - - - - - - - - 操作系统原理实验报告- 3 - 2.LRU 算法开始判断该虚页是否已经调入内存直接访问请求调页记录缺页数判断 Free链表是否为空调入空闲块将countime 值最大的页面置换出去修改内存状态i+i=0输出算法结果结束YYYNNi20N四、主要程序清单#include #include #include #include #include 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 15 页 - - - - - - - - - 操作系统原理实验报告- 4 - #define M 10 /10 个虚页#define N 20 /20 个页面的访问序列#define S 100 /实页个数/定义虚页的结构typedef struct VirtualPage int pn; int pfn; int time; VirtualPage; /定义实页的结构typedef struct Page int pn; int pfn; struct Page* next; Page; struct Page ppS; /定义一个存放5 个实页的数组，在底下还要将其串成链表struct VirtualPage vpM; / 定义存放 10 个虚页的数组int queueN; /定义一个数组，存放随机生成的20 个数，表示访问虚页的次序，里面的数值不能超过 9 int count; /存放缺页次数，用来统计缺页率。本算法没有考虑预调页，只要该页不在内存，就认为缺页一次。int countime; / 用于 LRU 算法中，找出要淘汰的页。每当要访问一个虚页面时，countime 的值加 1，然后将所要访问的虚页的time 项值设置为增值后的当前countime 值int MemoryStatusSN; /记录当访问每一个虚页时，内存中的5 个实页的详细信息。int NotInMemoryN; /表示每次虚页访问是否在内存struct Page *Free,*Free_head,*Busy,*Busy_tail,*Busy_head,*temp; int sn; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 15 页 - - - - - - - - - 操作系统原理实验报告- 5 - void init() int i,j; count=0; countime=0; /初始化 10 个虚页for(i=0;iM;i+) vpi.pn=i; vpi.pfn=-1; vpi.time=0; /初始化 5 个实页，并将其串成链表形式for(i=0;isn;i+) ppi.pn=-1; ppi.pfn=i; ppi.next=NULL; /将 5 个实页依次相连，形成Free 链表Free=&pp0; for(i=0;isn-1;i+) ppi.next=&ppi+1; ppsn-1.next=NULL; Free_head=Free; /初始化 Busy 链表Busy=NULL; Busy_head=NULL; Busy_tail=NULL; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 15 页 - - - - - - - - - 操作系统原理实验报告- 6 - /初始化 MemoryStatus 数组for(i=0;isn;i+) for(j=0;jN;j+) MemoryStatusij=-1; /初始化 NotInMemory 数组for(i=0;iN;i+) NotInMemoryi=1;/表示不再内存 void FIFO() int i,j,k,currentpage; for(i=0;iN;i+) /这是主循环，每次处理一个虚页访问。直到把20 个虚页处理完为止。 currentpage=queuei; /判断该虚页是否已经调入内存if(vpcurrentpage.pfn!=-1) /表示该页已经在内存中，可以直接访问。同时记录访问该页时对应的实页信息（和前一页相同） for(j=0;jnext; Free=Free_head; /将虚页 currentpage 装入 temp 指向的实页，该实页的编号为temp-pfn vpcurrentpage.pfn=temp-pfn; temp-pn=currentpage; /将 temp 指向的实页插入Busy 链表的末尾temp-next=NULL; if(Busy=NULL) /如果是第一次把虚页装入实页，则 temp 就是 Busy 链表的第一个元素。 Busy=temp; Busy_head=Busy; Busy_tail=Busy; else /如果不是第一次把虚页装入实页，则将temp 插入 Busy 链表的队尾。 Busy_tail-next=temp; Busy_tail=temp; /修改内存状态for(k=0;kpfni=currentpage; /虚页 currentpage装入了 temp-pfn 表示的那个实页里 else /如果 Free 链表为空，需要置换一页出去 /将 Busy 首元素取出，赋给temp temp=Busy; Busy_head=Busy-next; Busy=Busy_head; /将当前虚页currentpage 装入 temp 指向的实页，修改其信息vptemp-pn.pfn=-1; vpcurrentpage.pfn=temp-pfn; temp-pn=currentpage; temp-next=NULL; Busy_tail-next=temp; Busy_tail=temp; /修改内存状态for(k=0;kpfni=currentpage; /虚页 currentpage装入了 temp-pfn 表示的那个实页里 void LRU() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 15 页 - - - - - - - - - 操作系统原理实验报告- 9 - int i,j,k,currentpage; for(i=0;iN;i+) currentpage=queuei; if(vpcurrentpage.pfn!=-1) /该虚页已经在内存 for(j=0;jnext; Free=Free_head; vpcurrentpage.pfn=temp-pfn; temp-pn=currentpage; temp-next=NULL; if(Busy=NULL) Busy=temp; Busy_head=Busy; Busy_tail=Busy; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 15 页 - - - - - - - - - 操作系统原理实验报告- 10 - Busy_tail-next=temp; Busy_tail=temp; for(k=0;kpfni=currentpage; else int min=vppp0.pn.time; temp=&pp0; for(int k=1;ksn;k+) if(vpppk.pn.timepn.pfn=-1; vpcurrentpage.pfn=temp-pfn; temp-pn=currentpage; for(k=0;kpfni=currentpage; countime+; vpcurrentpage.time=countime; void main() int i,j,f=1; while(f) cout$页面置换算法程序$endl; cout 请输入实页数：sn; init(); coutFIFO 算法结果为： endl; for(i=0;iN;i+) queuei=rand()%10; printf(|%3d,queuei); printf(n); FIFO(); /显示依次访问20 个虚页时对应的内存状态，即MemoryStatus 数组的值。for(i=0;isn;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 15 页 - - - - - - - - - 操作系统原理实验报告- 12 - for(j=0;jN;j+) if(NotInMemoryj=1) /当访问的这个虚页不在内存时，显示将其调入内存后的详细内存信息printf(|%3d,MemoryStatusij); else printf(|%3c,32); /当访问的这个虚页在内存时，内存状态未发生改变，故无需再显示一遍 printf(n 缺页数为： %3dn,count); float qyl=count/(float)N; cout 缺页率为： qyl*100.0%endl; qyl=0; init(); coutendl; coutLRU算法结果为： endl; for(i=0;iN;i+) printf(|%3d,queuei); printf(n); LRU(); for(i=0;isn;i+) for(j=0;jN;j+) if(NotInMemoryj=1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 15 页 - - - - - - - - - 操作系统原理实验报告- 13 - printf(|%3d,MemoryStatusij); else printf(|%3c,32); printf(n 缺页数为： %3dn,count); qyl=count/(float)N; cout 缺页率为： qyl*100.0%endl；int t; coutendl*是否还要继续改变实页数sn，若是则输入1，否则输入0，结束本次操作！ *t; f=t; cout 已退出，谢谢使用！endl; 五、程序运行结果名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 15 页 - - - - - - - - - 操作系统原理实验报告- 14 - 六、实验体会名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 15 页 - - - - - - - - -