虚拟存储器管理方案试验报告

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

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

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

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

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

6、参数输入模块开 始是*打开w accept窗口关闭w input窗口算法实现模块始开击取消按打开w input窗口关闭w accept窗口否用FCFS算用SSTF算用SCAN算用CSCAN算调用FCFS算法显不结果是 调用SSTF算法,显示结果是 调用SCAN算法”显示结果是 调用CSCAN法显示结果四、主要程序清单模块之间的调用关系登录模块点击确定按参数输入模块IF*1 町、算法实现模块F点击返回按锚I点击确定按钮#include#include#includeint producerand(int remainder);void initprocess();void chosedispla

7、ce();struct linknode * fifo(struct linknode *head,int randcount);void Optimal(struct linknode*head,int randprocess);struct linknode* LRU(struct linknode *head,int randprocess);struct linknode* initlink();void choicestey();int allotment(struct linknode *head);bool checkfifooptimal(struct linknode* he

8、ad,int checkpage);void recover(struct linknode *head,int randprocess);void recovermemory();int process1020;/数组的横坐标为进程序列，纵坐标为每个进程的页号int processallotment6;/存储每个进程已经分配的块数int finishp6;/标志进程是否完成(1完成0不完成)int finishprocess=0;/进程完成的个数int findpage6;/每个进程命中的个数struct linknode *plinkhead6;struct linknode *plink

9、6;int memoryallotment6;int stey=0;struct linknode(struct linknode *linkper;/ 空链表的前驱指针int page;int processpage;int used;int memorypage;struct linknode *linknext; 空链表的后继指针struct linknode *processper;/ 进程的前去指针struct linknode *processnext; 进程的后继指针;int main()(struct linknode *head=initlink();initprocess(

10、);choicestey();int re=allotment(head);if(re=0)printf(内存分配出现问题。);system(pause);chosedisplace();recovermemory();system(pause);void recovermemory()int n=0;printf(是否回收全部已分配的内存空间？n回收输入1,不回收输入2n);scanf(%d,&n);if(n=1)for(int i=1;iused=0;head=head-processnext;void choicestey()printf(请选择置换算法n);printf(1 表示 FI

11、FOn2 表示 Optimaln3 表示 LRUn);bool flag=true;while(flag)scanf(%d,&stey);switch(stey)(case 1:printf(您选择的是 FIFO 替换算法 n);flag=false; break;case 2:printf(您选择的是 Optimal 替换算法 n);flag=false;break;case 3:printf(您选择的是 LRU 替换算法 n);flag=false;break; default :printf(输入错误，t#重新输入 n);void chosedisplace() 选择置换算法struct

12、 linknode *head;int randcount;/ 进程序号bool find;while(finishprocess5)randcount=producerand(5);while(processallotmentrandcountprocessrandcount0)find=false;head=plinkheadrandcount;if(stey=1|stey=2)find=checkfifooptimal(head,processrandcountprocessallotmentrandcount+1);if(find=true)findpagerandcount+;)if

13、(find=false)/如果在链表中没找到当前的页数(switch(stey)(case 1:(plinkheadrandcount=fifo(plinkheadrandcount,randcount);break;)case 2:Optimal(plinkheadrandcount,randcount);break;)case 3:plinkheadrandcount=LRU(plinkheadrandcount,randcount);break;)processallotmentrandcount+;)if(finishprandcount=0)finishprocess+;finish

14、prandcount=1;)struct linknode *p;printf(进程执行完后内存分配情况：n);for(int i=1;imemorypage,p-processpage,p-page);p=p-processnext;)for(int i=1;ipage=checkpage)return true;else(head=head-processnext;)return false;)struct linknode* LRU(struct linknode *head,int randprocess) (struct linknode *bhead;bhead=head;whil

15、e(head-processnext!=0)(if(head-page=processrandprocessprocessallotmentrandprocess+1) break;else head=head-processnext;)if(head-page!=processrandprocessprocessallotmentrandprocess+1) 没找至U(bhead-page=processrandprocessprocessallotmentrandprocess+1;head-processnext=bhead;bhead-processper=head;bhead=bhe

16、ad-processnext;bhead-processper=0;head=head-processnext;head-processnext=0;plinkrandprocess=plinkrandprocess-processnext;return bhead;)else/俄到了 if(head=bhead)/ 头head-processper=plinkrandprocess;plinkrandprocess-processnext=head;plinkrandprocess=plinkrandprocess-processnext;head=head-processnext;head

17、-processper=0;plinkrandprocess-processnext=0;findpagerandprocess+;return head;)elseif(head-processnext=0)/ 尾findpagerandprocess+;return bhead;)else/中间head-processnext-processper=head-processper;head-processper-processnext=head-processnext;head-processnext=0;head-processper=plinkrandprocess;plinkrand

18、process-processnext=head;plinkrandprocess=plinkrandprocess-processnext;findpagerandprocess+;return bhead;void Optimal(struct linknode*head,int randprocess)struct linknode *maxp;maxp=head;int max=1,i;while(head!=0)for(i=processallotmentrandprocess+1;ipage)break;if(imax)max=i;maxp=head;)head=head-proc

19、essnext;)maxp-page=processrandprocessprocessallotmentrandprocess+1;)struct linknode* fifo(struct linknode*head,int randprocess)struct linknode*phead;/ 改变后的头指针phead=head;head-page=processrandprocessprocessallotmentrandprocess+1;while(head-processnext!=0)head=head-processnext;)head-processnext=phead;p

20、head-processper=head;phead=phead-processnext;head=head-processnext;head-processnext=0;phead-processper=0;return phead;)int allotment(struct linknode *head)/ 为进程分配内存int allotsum=0;/已经分配完进程的个数int randprocess;/当前要分配内存的进程标号bool boolallot6;for(int i=1;i6;i+)(processallotmenti=0;boolalloti=false;memoryall

21、otmenti=0;while(allotsumused=0)(if(processallotmentrandprocess=0)(plinkheadrandprocess=head;plinkrandprocess=head;plinkrandprocess-processper=0;plinkrandprocess-processnext=0;head-processpage=randprocess;plinkrandprocess-page=processrandprocess1;head-used=1;printf( 内 存 块 号： %dt 进 程 号： dt 页号：dn,head-

22、memorypage,head-processpage,head-page);head=head- linknext;memoryallotmentrandprocess+;findpagerandprocess+;elseboolchecksame=checkfifooptimal(plinkheadrandprocess,processrandprocessprocessallotmentrandprocess+1);if(checksame=false)head-used=1;head-processnext=0;head-processper=plinkrandprocess;plin

23、krandprocess- processnext=head;head-processpage=randprocess;head-page=processrandprocessprocessallotmentrandprocess+1;plinkrandprocess=plinkrandprocess-processnext;%dt 页printf( 内 存 块 号： %dt 进 程 号： 号：dn,head-memorypage,head-processpage,head-page);head=head-linknext;memoryallotmentrandprocess+;findpag

24、erandprocess+;elseif(stey=3) plinkheadrandprocess=LRU(plinkheadrandprocess,randprocess);else findpagerandprocess+;)processallotmentrandprocess+;)else(printf(进程 %d 分配失败 n,randprocess);return 0;)if(head=0)(printf(进程 %d 分配失败 n,randprocess);return 0;)if(processallotmentrandprocess=processrandprocess0)(p

25、rintf(进程 %d 分配成功 n,randprocess);allotsum+;boolallotrandprocess=true;finishprocess+;finishprandprocess=1;)elseif(memoryallotmentrandprocess=4)allotsum+;boolallotrandprocess=true;printf(进程 %d 分配成功 n,randprocess);)struct linknode *p;printf(初始内存分配情况：n);for(int i=1;imemorypage,p-processpage,p-page);p=p-p

26、rocessnext;)return 1;)void initprocess()int perrandcount;for(int i=1;i=5;i+)/ 假设有 5 个进程perrandcount=producerand(10);/每个进程产生的页面个数processi0=perrandcount;for(int j=1;j=perrandcount;j+)processij=producerand(20);/为第i个进程产生0至U 19之间的页面顺序)for(int i=1;i=5;i+)printf(进程序列 d,i);printf(该进程的调用页号顺序)；for(int j=1;j=p

27、rocessi0;j+)printf(%d ,processij);printf(n);)for(int i=1;iused=0;p-processnext=NULL;p-processper=NULL;p-linkper=q;p-linknext=NULL;p-memorypage=1;p-page=-1;for(int i=1;iused=0;p-processnext=NULL;p-processper=NULL;p-linkper=q;q-linknext=p;p-linknext=NULL;p-page=-1;p-memorypage=i+1;q=q-linknext;return

28、head;int producerand(int remainder)/ 产生随机数(int randcount;randcount=(rand()+(unsigned)time(NULL)%remainder+1;return randcount;五、程序运行结果负C：D octi menti and Settings Md min istratortgl面匕uoycl桌面1131由咨表实廉的存禽管整+先出项面看A251-3 I346 6 11S 3213 529 21 180 9 78 112 1向Is恢RE用用用用用mm 一E1 二Irt，JTT b/Vt US fifififi进注工 、tB-1-t、Tl- V r V 171 该该该该该算ria 12315 羽Fotiu 冽列列列7J置FIFoptLRU 示示示 程程程程程选表表a胜芹请L21