虚拟存储器管理 页面置换算法模拟实验.docx

虚拟存储器管理 页面置换算法模拟实验淮海工学院计算机工程学院 实验报告书 课程名： 操作系统原理A 题 目： 虚拟存储器管理 页面置换算法模拟实验 班 级： 软件* 学 号： 20*1228* 姓 名： * 评语： 成绩： 指导教师： 批阅时间： 年 月 日 操作系统原理A 实验报告 - 1 - 一、实验目的与要求 1. 目的： 请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。 2. 要求： 本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定，对这些虚页访问的页地址流可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。 二、实验说明 1设计中虚页和实页的表示 本设计利用C语言的结构体来描述虚页和实页的结构。 pn pfn time pn pfn next 虚页结构 实页结构 在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是09。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。 在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。 2关于缺页次数的统计 为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内，此虚页被命中，count加1。最终命中率=count/20*100%。 3LRU算法中“最近最久未用”页面的确定 为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前 操作系统原理A 实验报告 - 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值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。 三、程序流程图 开始初始化数据指向下一个页面页面是否存在YNY输出当前页Y物理块是否有空闲N选择最先进入的页面作为淘汰页将页面放到空闲的物理页处i+i<页面长度N计算缺页率，并输出数据结束 FIFO算法 操作系统原理A 实验报告 开始- 3 - 初始化数据指向下一个页面页面是否存在YNY输出当前页Y物理块是否有空闲N选择最近最久页面作为淘汰页将页面放到空闲的物理页处i+i<页面长度N计算缺页率，并输出数据结束 LRU算法 四、主要程序清单 #include<stdlib.h> #include<stdio.h> #include<conio.h> #include <time.h> #define M 10 /10个虚页 #define N 20 /20个页面的访问序列 /定义虚页的结构 typedef struct VirtualPage int pn; int pfn; int time; 操作系统原理A 实验报告 - 4 - VirtualPage; /定义实页的结构 typedef struct Page int pn; int pfn; struct Page* next; Page; struct VirtualPage vpM; / 定义存放10个虚页的数组 int queueN; /定义一个数组，存放随机生成的20个数，表示访问虚页的次序，里面的数值不能超过9 int count; /存放缺页次数， 用来统计缺页率。本算法没有考虑预调页，只要该页不在内存，就认为缺页一次。 int countime; /用于LRU算法中，找出要淘汰的页。每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前countime值 int NotInMemoryN; /表示每次虚页访问是否在内存 struct Page *Free,*Free_head,*Busy,*Busy_tail,*Busy_head,*temp; void init(Page pp,int MemoryStatusN,int L) count=0; countime=0; /初始化10个虚页 int i,j; for(i=0;i<M;i+) vpi.pn=i; vpi.pfn=-1; vpi.time=0; 操作系统原理A 实验报告 - 5 - /初始化5个实页，并将其串成链表形式 for(i=0;i<L;i+) ppi.pn=-1; ppi.pfn=i; ppi.next=NULL; /将5个实页依次相连，形成Free链表 Free=&pp0; for(i=0;i<L-1;i+) ppL-1.next=NULL; Free_head=Free; /初始化Busy链表 Busy=NULL; Busy_head=NULL; Busy_tail=NULL; ppi.next=&ppi+1; /初始化MemoryStatus数组 for(i=0;i<L;i+) for(j=0;j<N;j+) MemoryStatusij=-1; /初始化NotInMemory数组 操作系统原理A 实验报告 - 6 - for(i=0;i<N;i+) NotInMemoryi=1; void FIFO(int L,int MemoryStatusN) /先入先出算法的具体实现。 count=0; int 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 /该页不在内存，需要请求调页 count=count+1; /缺页数加1 if(Free!=NULL) /如果Free链表不为空，表示内存中还有空的实页，故从Free链表中取队首元素，装入该虚页，并修改相关信息。 操作系统原理A 实验报告 - 7 - temp=Free_head; /本程序中用Free表示链表的起始地址，Free_head表示链表中的第一个元素地址。实际上两者的值永远相等。 /将temp指向的实页插入Busy链表的末尾 temp->next=NULL; if(Busy=NULL) /如果是第一次把虚页装入实页，则temp就是Busy链表的第一 /将虚页currentpage装入temp指向的实页，该实页的编号为temp->pfn vpcurrentpage.pfn=temp->pfn; temp->pn=currentpage; Free_head=Free_head->next; Free=Free_head; 个元素。 Busy=temp; Busy_head=Busy; Busy_tail=Busy; else /如果不是第一次把虚页装入实页，则将temp插入Busy链表的队尾。 Busy_tail->next=temp; Busy_tail=temp; /修改内存状态 for(k=0;k<L;k+) /复制访问前一页时的内存状态 MemoryStatuski=MemoryStatuski-1; MemoryStatustemp->pfni=currentpage; /虚页currentpage装入了temp->pfn表示的那个实页里 操作系统原理A 实验报告 - 8 - 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指向的实页插入Busy链表的末尾,此时不用再考虑Busy是否为空了。 temp->next=NULL; Busy_tail->next=temp; Busy_tail=temp; /修改内存状态 temp->pn=currentpage; /temp指向的实页，装入了currentpage for(k=0;k<L;k+) /复制访问前一页时的内存状态 MemoryStatuski=MemoryStatuski-1; MemoryStatustemp->pfni=currentpage; /虚页currentpage装入了temp->pfn表示的那个实页里 操作系统原理A 实验报告 - 9 - 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) else count=count+1; if(Free!=NULL) temp=Free_head; for(j=0;j<L;j+) NotInMemoryi=0; MemoryStatusji=MemoryStatusji-1; Free_head=Free_head->next; Free=Free_head; vpcurrentpage.pfn=temp->pfn; temp->pn=currentpage; temp->next=NULL; if(Busy=NULL) Busy=temp; 操作系统原理A 实验报告 - 10 - Busy_head=Busy; Busy_tail=Busy; else Busy_tail->next=temp; Busy_tail=temp; for(k=0;k<L;k+) /复制访问前一页时的内存状态 MemoryStatuski=MemoryStatuski-1; else int min=vppp0.pn.time; temp=&pp0; for(k=1;k<L;k+) vptemp->pn.pfn=-1; vpcurrentpage.pfn=temp->pfn; temp->pn=currentpage; if(vpppk.pn.time<min) min=vpppk.pn.time; temp=&ppk; MemoryStatustemp->pfni=currentpage; for(k=0;k<L;k+) 操作系统原理A 实验报告 - 11 - MemoryStatustemp->pfni=currentpage; MemoryStatuski=MemoryStatuski-1; countime+; vpcurrentpage.time=countime; int main int i,j,flag=1,L; while(flag) printf("请输入实页的个数:"); scanf("%d",&L); struct Page ppL; /定义一个存放5个实页的数组 ，在底下还要将其串成链表 int MemoryStatusLN; init(pp,MemoryStatus,L); printf("FIFO算法：n"); srand(time(0); for(i=0;i<N;i+) printf("n"); FIFO(L,MemoryStatus); /运行 FIFO 算法 queuei=rand%10; printf("|%3d",queuei); /显示依次访问20个虚页时对应的内存状态，即MemoryStatus数组的值。 操作系统原理A 实验报告 - 12 - for(i=0;i<L;i+) for(j=0;j<N;j+) if(NotInMemoryj=1) /当访问的这个虚页不在内存时，显示将其调入内存后的详细内存信息 printf("|%3d",MemoryStatusij); else printf("|%3c",32); /当访问的这个虚页在内存时，内存状态未发生改变，故无需再显示一遍。本例用空格代替，其中 32 是空格的ASCII码 rate=0; init(pp,MemoryStatus,L); printf("n"); printf("LRU算法：n"); for(i=0;i<N;i+) printf("|%3d",queuei); printf("n 缺页数为:%3d",count); float rate=count/(float)N*100; printf("缺页率为：%g%n",rate); printf("n"); LRU(pp,MemoryStatus,L); for(i=0;i<L;i+) for(j=0;j<N;j+) if(NotInMemoryj=1) /当访问的这个虚页不在内存时，显示将其调入内存后的详细内存信息 printf("|%3d",MemoryStatusij); 操作系统原理A 实验报告 - 13 - else printf("|%3c",32); /当访问的这个虚页在内存时，内存状态未发生改变，故无需再显示一遍。本例用空格代替，其中 32 是空格的ASCII码 printf("n 缺页数为:%3d",count); rate=count/(float)N*100; printf("缺页率为：%g%n",rate); printf("继续操作? 1->继续 0->停止n"); scanf("%d",&flag); printf("n"); return 0; 五、程序运行结果 六、实验体会 本次实验是为了熟悉页面调度的两种算法即FIFO算法和LRU算法，首先老师已经给出了FIFO算法,要求我们给出LRU算法，并将程序中的实页数改为由用户自行输入的为准，这就有两种方式，其一：是将L作为全局变量，将其大小设为100，使其满足输入的输入的数字，这样做的缺点是浪费空间，但在编程实现上十分便利，其二，将L改有键盘输入，之后再分配相应的空间，这样做的优点是节约空间，但在编程时比较麻烦。 总体来说，由于老师已经将FIFO算法实现，所以本次试验比较简单，相对容易实现。