实验三页面置换算法模拟实验

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

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

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

4、20*100% 。3LRU算法中“最近最久未用”页面的确定为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime ，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前标准文档实用文案countime 值，表示该虚页的最后一次被访问时间。当LRU算法需要置换时，从所有已分配实页的虚页中找出time 值为最小的虚页就是“最近最久未用”的虚页面，应该将它置换出去。4算法中实页的组织因为能分配的实页数n 是在程序运行时由用户动态指派的，所以应使用链表组织动态产生的多个实页。为了调度算法实现的方便，可以考虑引入free 和 bu

5、sy 两个链表： free链表用于组织未分配出去的实页， 首指针为free_head ，初始时 n 个实页都处于free链表中； busy 链表用于组织已分配出去的实页，首指针为busy_head ，尾指针为busy_tail，初始值都为null 。当所要访问的一个虚页不在实页中时，将产生缺页中断。此时若 free链表不为空， 就取下链表首指针所指的实页，并分配给该虚页。若free链表为空，则说明n 个实页已全部分配出去，此时应进行页面置换：对于FIFO算法要将busy_head 所指的实页从busy 链表中取下， 分配给该虚页，然后再将该实页插入到busy链表尾部； 对于 LRU算法则要从所

6、有已分配实页的虚页中找出time 值为最小的虚页， 将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。三、程序流程图（要求画出非常详细的流程图）开始输入实页数No输入选项NoFIFO法LRO法虚页顺序退出重置实页数输入访问次重新输是否已输入虚页数，和是否已输入虚页入实页顺序访问顺数顺序序YESYES输出实页置换情况，命中概率标准文档实用文案四、主要程序清单 /动态指定实页个数的页面置换算法, 包括 FIFO 和 LRU两个算法。#include<stdlib.h>#include<stdio.h>#include<conio.h>#i

7、nclude <time.h>#define M 10/10个虚页#define N 20/20个页面的访问序列#define L 10/最大 10 个实页。/ 定义虚页的结构typedef struct VirtualPageint pn;int pfn;int time;VirtualPage;/ 定义实页的结构typedef struct Pageint pn;int pfn;struct Page* next;Page;struct Page ppM;/定义一个存放10 个实页的数组，在底下还要将其串成链表struct VirtualPage vpM; /定义存放 10 个

8、虚页的数组intqueueN;/ 定义一个数组，存放随机生成的20 个数，表示访问虚页的次序，里面的数值不能超过 9int count; / 存放缺页次数， 用来统计缺页率。本算法没有考虑预调页，只要该页不在内存，就认为缺页一次。intcountime;/ 用于 LRU算法中，找出要淘汰的页。每当要访问一个虚页面时，countime 的值加1，然后将所要访问的虚页的time 项值设置为增值后的当前countime 值标准文档实用文案int MemoryStatusLN; /记录当访问每一个虚页时，内存中的5 个实页的详细信息。int NotInMemoryN;/表示每次虚页访问是否在内存str

9、uct Page *Free,*Free_head,*Free_tail,*Busy,*Busy_tail,*Busy_head,*temp,*temp_small;void FIFO() /先入先出算法的具体实现。int i,j,k,currentpage; /一些临时变量for(i=0;i<N;i+)/这是主循环，每次处理一个虚页访问。直到把20 个虚页处理完为止。/ 当前访问的虚页是哪一页？由数组 queuei 中的值表示currentpage=queuei;/ 判断该虚页是否已经调入内存if(vpcurrentpage.pfn!=-1) /表示该页已经在内存中，可以直接访问。 同

10、时记录访问该页时对应的实页信息（和前一页相同）for(j=0;j<L;j+)MemoryStatusji=MemoryStatusji-1;NotInMemoryi=0;else /该页不在内存，需要请求调页count=count+1; /缺页数加1if(Free!=NULL) /如果 Free 链表不为空，表示内存中还有空的实页，故从Free 链表中取队首元素，装入该虚页，并修改相关信息。temp=Free_head; /本程序中用Free 表示链表的起始地址，Free_head 表示链表中的第一个元素地址。实际上两者的值永远相等。Free_head=Free_head->nex

11、t;Free=Free_head;标准文档实用文案/将虚页 currentpage装入 temp 指向的实页，该实页的编号为temp->pfnvpcurrentpage.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 插入 Bus

12、y 链表的队尾。Busy_tail->next=temp;Busy_tail=temp;/修改内存状态for(k=0;k<L;k+) /复制访问前一页时的内存状态MemoryStatuski=MemoryStatuski-1;MemoryStatustemp->pfni=currentpage;/虚 页currentpage装 入 了temp->pfn表示的那个实页里else /如果 Free 链表为空，需要置换一页出去。由于采用FIFO 算法，故取busy 链表的队首元素，将其置换出去，修改信息后插入队尾。/将 Busy 首元素取出，赋给temptemp=Busy;B

13、usy_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 链表的末尾 , 此时不用

14、再考虑Busy 是否为空了。temp->next=NULL;Busy_tail->next=temp;Busy_tail=temp;/ 修改内存状态for(k=0;k<L;k+) /复制访问前一页时的内存状态MemoryStatuski=MemoryStatuski-1;MemoryStatustemp->pfni=currentpage;/虚 页currentpage装 入 了temp->pfn表示的那个实页里void LRU()int i,j,k,currentpage; /一些临时变量for(i=0;i<N;i+)/这是主循环，每次处理一个虚页访问。直

15、到把20 个虚页处理完为止。/ 当前访问的虚页是哪一页？由数组 queuei 中的值表示currentpage=queuei;标准文档实用文案countime=countime+1;/每次访问一个虚页，将该变量值加1vpcurrentpage.time=countime;/设置当前访问的虚页的time 值/判断该虚页是否已经调入内存if(vpcurrentpage.pfn!=-1) /表示该页已经在内存中，可以直接访问。 同时记录访问该页时对应的实页信息（和前一页相同）for(j=0;j<L;j+)MemoryStatusji=MemoryStatusji-1;NotInMemoryi=

16、0;else /该页不在内存，需要请求调页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->pfnvpcurrentpage.pfn=te

17、mp->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+) /复制访问前一页时的内存状

18、态MemoryStatuski=MemoryStatuski-1;MemoryStatustemp->pfni=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-

19、>pn.time>vptemp->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;/currentpa

20、ge被装入内存， 更新其 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;Bu

21、sy_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->ne

22、xt;/ 最后插入尾部，并更新 Busy_tail 指针temp_small->next=NULL;Busy_tail->next=temp_small;标准文档实用文案Busy_tail=temp_small;/ 修改内存状态for(k=0;k<L;k+) /复制访问前一页时的内存状态MemoryStatuski=MemoryStatuski-1;MemoryStatustemp_small->pfni=currentpage;/虚页 currentpage装入了 temp->pfn 表示的那个实页里void main()int i,j,ppCount;/ 由键

23、盘输入实页的个数，并形成Free 链表printf("请输入系统能提供的物理块（即实页）的个数，数值为2-10 之间： t");scanf("%d",&ppCount);if(ppCount>10|ppCount<2)printf("nn！输入的数值不合法，程序终止！");elsecount=0;countime=0;标准文档实用文案/ 初始化 10 个虚页for(i=0;i<M;i+)vpi.pn=i;vpi.pfn=-1;vpi.time=0;/ 初始化这些实页，并将其串成链表/ 首先生成第一个元素，并初

24、始化Free_head=malloc(sizeof(Page);Free=Free_head;Free_tail=Free;Free_head->pn=-1;Free_head->pfn=0;Free_head->next=NULL;/ 用一个循环生成后续的元素，并初始化后，链接成链表for(i=1;i<ppCount;i+)temp=malloc(sizeof(Page);temp->pn=-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;i<L;i+)for(j=0;j<N;j+)MemoryStatusij=-1;/ 初始化 NotInMemory