页面置换实验报告

计算机科学系实验报告书课程名： 操 作 系 统 题 目： 虚拟存储器管理 页面置换算法模拟实验 班 级： 学 号： 姓 名： 评语：成绩： 指导教师： 批阅时间： 年 月 日一、实验目的与要求1. 目的：请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。2. 要求：本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。二、实验说明1设计中虚页和实页的表示本设计利用C语言的结构体来描述虚页和实页的结构。pnpfntimepnpfnnext 虚页结构 实页结构在虚页结构中，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项值设置为增值后的当前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值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。三、程序流程图 （要求画出非常详细的流程图）四、主要程序清单源代码：/ 动态指定实页个数的页面置换算法,包括FIFO和LRU两个算法。#include#include#include#include #define M 10 /10个虚页#define N 20 /20个页面的访问序列#define L 10 /最大10个实页。/定义虚页的结构typedef struct VirtualPageint pn;int pfn; int time; VirtualPage; /定义实页的结构typedef struct Page int pn;int pfn; struct Page* next; Page; struct Page ppM; /定义一个存放10个实页的数组 ，在底下还要将其串成链表 struct VirtualPage vpM; / 定义存放10个虚页的数组int queueN; /定义一个数组，存放随机生成的20个数，表示访问虚页的次序，里面的数值不能超过9 int count; /存放缺页次数， 用来统计缺页率。本算法没有考虑预调页，只要该页不在内存，就认为缺页一次。int countime; /用于LRU算法中，找出要淘汰的页。每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前countime值int MemoryStatusLN; /记录当访问每一个虚页时，内存中的5个实页的详细信息。int NotInMemoryN; /表示每次虚页访问是否在内存struct Page *Free,*Free_head,*Free_tail,*Busy,*Busy_tail,*Busy_head,*temp,*temp_small; void FIFO() /先入先出算法的具体实现。 int i,j,k,currentpage; /一些临时变量for(i=0;iN;i+) /这是主循环，每次处理一个虚页访问。直到把20个虚页处理完为止。 /当前访问的虚页是哪一页？ 由数组queuei中的值表示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链表为空，需要置换一页出去。由于采用FIFO算法，故取busy链表的队首元素，将其置换出去，修改信息后插入队尾。 /将Busy首元素取出，赋给temp temp=Busy; Busy_head=Busy-next; Busy=Busy_head; /将当前虚页currentpage装入temp指向的实页，修改其信息 vptemp-pn.pfn=-1; /该页被置换出去了，所以其pfn字段要设置成-1，表示其已经不再内存。 vpcurrentpage.pfn=temp-pfn; /currentpage被装入内存，更新其pfn字段为temp指向的实页。 temp-pn=currentpage; /temp指向的实页，装入了currentpage虚页 /将temp指向的实页插入Busy链表的末尾,此时不用再考虑Busy是否为空了。 temp-next=NULL; Busy_tail-next=temp; Busy_tail=temp; /修改内存状态 for(k=0;kpfni=currentpage; /虚页currentpage装入了temp-pfn表示的那个实页里 void LRU() int i,j,k,currentpage; /一些临时变量for(i=0;iN;i+) /这是主循环，每次处理一个虚页访问。直到把20个虚页处理完为止。 /当前访问的虚页是哪一页？ 由数组queuei中的值表示currentpage=queuei;countime=countime+1; /每次访问一个虚页，将该变量值加1vpcurrentpage.time=countime; /设置当前访问的虚页的time值 /判断该虚页是否已经调入内存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链表为空，需要置换一页出去。由于采用LRU算法，在busy链表中查找到time值最小的那个元素，置换到链表尾部 /查找time值最小的元素，找到后用temp_small指针表示 temp=Busy_head; temp_small=Busy_head; while(temp-next!=NULL) if(vptemp_small-pn.timevptemp-next-pn.time) /若当前元素的time值比下一个元素的time值大，则更新temp_small为指向下一元素 temp_small=temp-next; temp=temp-next; /将当前虚页currentpage装入temp_small指向的实页，修改其信息 vptemp_small-pn.pfn=-1; /该页被置换出去了，所以其pfn字段要设置成-1，表示其已经不再内存。 vpcurrentpage.pfn=temp_small-pfn; /currentpage被装入内存，更新其pfn字段为temp_small指向的实页。 temp_small-pn=currentpage; /temp_small指向的实页，装入了currentpage虚页 /将temp_small指向的实页插入Busy链表的末尾 if(temp_small!=Busy_tail) /如果temp_small指向的那个元素就是Busy链表的最后一个，则不用做任何操作。 if(temp_small=Busy_head) /如果temp_small指向的那个元素是Busy链表的第一个元素，则直接插入链表尾部 Busy=Busy_head-next;Busy_head=Busy;temp_small-next=NULL;Busy_tail-next=temp_small;Busy_tail=temp_small; else /如果temp_small指向的那个元素恰好在Busy链表的中间 /首先定位到temp_small的前一个元素 temp=Busy_head; while(temp-next!=temp_small) temp=temp-next; /然后将temp_small的前一个元素的next指针 指向 temp_small指向的下一个元素 temp-next=temp_small-next; /最后插入尾部，并更新Busy_tail指针 temp_small-next=NULL; Busy_tail-next=temp_small; Busy_tail=temp_small; /修改内存状态 for(k=0;kpfni=currentpage; /虚页currentpage装入了temp-pfn表示的那个实页里 void main()int i,j,ppCount; /由键盘输入实页的个数，并形成Free链表printf(请输入系统能提供的物理块（即实页）的个数，数值为2-10之间：t);scanf(%d,&ppCount);if(ppCount10|ppCount2) printf(nn！输入的数值不合法，程序终止！);elsecount=0;countime=0;/初始化10个虚页for(i=0;ipn=-1;Free_head-pfn=0;Free_head-next=NULL;/用一个循环生成后续的元素，并初始化后，链接成链表for(i=1;ipn=-1;temp-pfn=i;temp-next=NULL;Free_tail-next=temp;Free_tail=temp;/初始化Busy链表Busy=NULL;Busy_head=NULL;Busy_tail=NULL;/初始化MemoryStatus数组for(i=0;iL;i+)for(j=0;jN;j+) MemoryStatusij=-1;/初始化NotInMemory数组for(i=0;iN;i+) No