虚拟存储器管理-面置换算法模拟试验

1、淮海工学院计算机工程学院实验报告书课程名： 操作系统原理A题目:虚拟存储器管理页面置换算法模拟实验班级：软件*学号：20*1228*姓名：*评语:成绩： 指导教师： 批阅时间:一、实验目的与要求1. 目的：请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的 理解。2. 要求：本实验要求使用 C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（

2、其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程 中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数， 来比较两种置换算法的稳定性。二、实验说明1 .设计中虚页和实页的表示本设计利用C语言的结构体来描述虚页和实页的结构。在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是09。pfn代表实页号，当一虚页未装入实页时，此项值为-1 ;当该虚页已装入某一实页时，此项值为所装入的实页 的实页号pfn。time项在FIFO算法中不使用，在 LRU中用来存放对该虚页的最近访问时间。在实页结

3、构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号,取值范围（0n-1 ）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点02 .关于缺页次数的统计为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器 count ,来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1 ,表示此虚页已被装入某实页内，此虚页被命中，count力口 1。最终命中率 =count/20*100%。3. LRU算法中“最近最久未用”页面的确定为了能找到“最近最久未用”的虚页

4、面，程序中可引入一个时间计数器countime，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前countime值，表示该虚页的最后一次被访问时间。当LRU算法需要置换时，从所有已分配实页的虚页中找出time值为最小的虚页就是“最近最久未用”的虚页面，应该将它置换出去。4 算法中实页的组织因为能分配的实页数 n是在程序运行时由用户动态指派的，所以应使用链表组织动态产生的多个实页。为了调度算法实现的方便，可以考虑引入free和busy两个链表：free链表用于组织未分配出去的实页，首指针为free_head ,初始时n个实页都处于free链表

5、中；busy链表用于组织已分配出 去的实页，首指针为 busy_head，尾指针为busy_tail ，初始值都为null。当所要访问的一个虚页 不在实页中时，将产生缺页中断。此时若free链表不为空，就取下链表首指针所指的实页，并分配给该虚页。若free链表为空，则说明 n个实页已全部分配出去，此时应进行页面置换：对于FIFO算法要将busy_head所指的实页从busy链表中取下，分配给该虚页，然后再将该实页插入到busy链表尾部；对于LRU算法则要从所有已分配实页的虚页中找出time值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。三、程序流程图开

6、始结束FIFO算法开始结束LRU算法四、主要程序清单#in clude<stdlib.h>#in clude<stdio.h>#in clude<c oni o.h>#in clude <time.h>个虚页个页面的访问序列#defi ne M 1010#defi ne N 2020/定义虚页的结构typedef struct VirtualPageint pn;int pfn;int time;VirtualPage;/ 定义实页的结构typedef struct Pageint pn;int pfn;struct Page* next;Pag

7、e;struct VirtualPage vpM; / 定义存放 10 个虚页的数组int queueN; / 定义一个数组，存放随机生成的 20 个数，表示访问虚页的次序，里面的数值不能 超过 9int count; / 存放缺页次数， 用来统计缺页率。本算法没有考虑预调页，只要该页不在内存，就 认为缺页一次。int countime; /用于LRU算法中，找出要淘汰的页。每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的 time 项值设置为增值后的当前 countime 值int NotInMemoryN; / 表示每次虚页访问是否在内存struct Page *F

8、ree,*Free_head,*Busy,*Busy_tail,*Busy_head,*temp;void init(Page pp,int MemoryStatusN,int L)int i,j;count=0;countime=0;/ 初始化 10 个虚页for(i=0;i<M;i+)vpi.pn=i;vpi.pfn=-1;vpi.time=0;/ 初始化 5 个实页，并将其串成链表形式for(i=0;i<L;i+)ppi.pn=-1;ppi.pfn=i;ppi.next=NULL;/ 将 5 个实页依次相连，形成 Free 链表Free=&pp0;for(i=0;i&

9、lt;L-1;i+)ppi.next=&ppi+1;ppL-1.next=NULL;Free_head=Free;/ 初始化 Busy 链表Busy=NULL;Busy_head=NULL;Busy_tail=NULL;/ 初始化 MemoryStatus 数组for(i=0;i<L;i+)for(j=0;j<N;j+)MemoryStatusij=-1;/ 初始化 NotInMemory 数组for(i=0;i<N;i+)NotInMemoryi=1;void FIFO(int L,int MemoryStatusN) / 先入先出算法的具体实现。count=0;i

10、nt i,j,k,currentpage; /一些临时变量for(i=0;i<N;i+) / 这是主循环，每次处理一个虚页访问。直到把 20 个虚页处理完为止。/ 当前访问的虚页是哪一页？ 由数组 queuei 中的值表示currentpage=queuei;/ 判断该虚页是否已经调入内存if(vpcurrentpage.pfn!=-1) / 表示该页已经在内存中， 可以直接访问。 同时记录访问 该页时对应的实页信息(和前一页相同)for(j=0;j<L;j+)MemoryStatusji=MemoryStatusji-1;NotInMemoryi=0;else / 该页不在内存，

11、需要请求调页count=count+1; /缺页数加 1if(Free!=NULL) /如果 Free 链表不为空，表示内存中还有空的实页，故从Free 链表中取队首元素，装入该虚页，并修改相关信息。temp=Free_head; / 本程序中用 Free 表示链表的起始地址， Free_head 表示链表 中的第一个元素地址。实际上两者的值永远相等。Free_head=Free_head->next;Free=Free_head;/ 将虚页 currentpage 装入 temp 指向的实页，该实页的编号为 temp->pfn vpcurrentpage.pfn=temp->

12、;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;k<L;k+) / 复制访问前一页时的内存状态Memo

13、ryStatuski=MemoryStatuski-1;MemoryStatustemp->pfni=currentpage; / 虚 页 currentpage 装 入 了 temp->pfn 表示的那个实页里FIFO 算法，故取 busy 链else / 如果 Free 链表为空，需要置换一页出去。由于采用 表的队首元素，将其置换出去，修改信息后插入队尾。/ 将 Busy 首元素取出，赋给 temp temp=Busy;Busy_head=Busy->next;Busy=Busy_head;/ 将当前虚页 currentpage 装入 temp 指向的实页，修改其信息vp

14、temp->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;/

15、修改内存状态for(k=0;k<L;k+) / 复制访问前一页时的内存状态 MemoryStatuski=MemoryStatuski-1;MemoryStatustemp->pfni=currentpage; / 虚 页 currentpage 装 入 了 temp->pfn 表示的那个实页里void LRU(Page pp,int MemoryStatusN,int L)int i,j,k,currentpage;for(i=0;i<N;i+)currentpage=queuei;if(vpcurrentpage.pfn!=-1)for(j=0;j<L;j+)

16、MemoryStatusji=MemoryStatusji-1;NotInMemoryi=0;elsecount=count+1;if(Free!=NULL)temp=Free_head;Free_head=Free_head->next;Free=Free_head;vpcurrentpage.pfn=temp->pfn;temp->pn=currentpage; temp->next=NULL;if(Busy=NULL)Busy=temp;Busy_head=Busy;Busy_tail=Busy;elseBusy_tail->next=temp;Busy_t

17、ail=temp;for(k=0;k<L;k+) / 复制访问前一页时的内存状态 MemoryStatuski=MemoryStatuski-1;MemoryStatustemp->pfni=currentpage;elseint min=vppp0.pn.time;temp=&pp0;for(k=1;k<L;k+)if(vpppk.pn.time<min)min=vpppk.pn.time; temp=&ppk;vptemp->pn.pfn=-1; vpcurrentpage.pfn=temp->pfn; temp->pn=curre

18、ntpage;for(k=0;k<L;k+)MemoryStatuski=MemoryStatuski-1;MemoryStatustemp->pfni=currentpage;countime+; vpcurrentpage.time=countime;int main()int i,j,flag=1,L;while(flag)printf(" 请输入实页的个数 :");scanf("%d",&L);，在底下还要将其串成链表struct Page ppL; / 定义一个存放 5 个实页的数组 int MemoryStatusLN;i

19、nit(pp,MemoryStatus,L);printf("FIFO 算法： n");srand(time(0);for(i=0;i<N;i+)queuei=rand()%10;printf("|%3d",queuei);printf("n");FIFO(L,MemoryStatus); / 运行 FIFO() 算法/ 显示依次访问 20 个虚页时对应的内存状态，即 MemoryStatus 数组的值。for(i=0;i<L;i+)for(j=0;j<N;j+)if(NotInMemoryj=1) / 其调入内存后

20、的详细内存信息printf("|%3d",MemoryStatusij); elseprintf("|%3c",32); / 发生改变，故无需再显示一遍。本例用空格代替，其中printf("n 缺页数为 :%3d",count);float rate=count/(float)N*100; printf(" 缺页率为： %g%n",rate);rate=0;init(pp,MemoryStatus,L);printf("n");printf("LRU 算法： n");for(i=0;i<N;i+) printf("|%3d",queuei); printf("n");LRU(pp,MemoryStatus,L);for(i=0;i<L;i+)for(j=0;j<N;j+)if(NotInMemoryj=1) / 其调入内存后的详细内存信息printf("|%3d",MemoryStatusij);当访问的这个虚页不在内存时，显示将当访问的这个虚页在内存时， 内存状态未32 是空格的 ASCII 码当访问的这个虚页不在内存