操作系统课程设计之请求式面页管理

1、一、目的与要求1、目的近年来，由于大规模集成电路（LSI）和超大规模集成电路（VLSI）技术的发展，使存储器的容量不断扩大，价格大幅度下降。但从使用角度看，存储器的容量和成本总受到一定的限制。所以，提高存储器的效率始终是操作系统研究的重要课题之一。虚拟存储技术是用来扩大内存容量的一种重要方法。学生应独立地用高级语言编写几个常用的存储分配算法，并设计一个存储管理的模拟程序，对各种算法进行分析比较，评测其性能优劣，从而加深对这些算法的了解。任务三采用最佳淘汰算法(OPT)实现，任务四采用最近最少使用页淘汰算法(LRU)实现。2、 要求为了比较真实地模拟存储管理，可预先生成一个大致符合实际情况的指令

2、地址流。然后模拟这样一种指令序列的执行来计算和分析各种算法的访问命中率。二、示例1、题目 本示例是采用页式分配存储管理方案，并通过分析计算不同页面淘汰算法情况下的访问命中率来比较各种算法的优劣。另外也考虑到改变页面大小和实际存储器容量对计算结果的影响，从而可为算则好的算法、合适的页面尺寸和实存容量提供依据。本程序是按下述原则生成指令序列的：（1） 50%的指令是顺序执行的。（2） 25%的指令均匀散布在前地址部分。（3） 25%的指令均匀散布在后地址部分。示例中选用最佳淘汰算法（OPT）和最近最少使用页面淘汰算法（LRU）计算页面命中率。公式为假定虚存容量为32K，页面尺寸从1K至8K，实存容

3、量从4页至32页。2、 算法与框图（1） 最佳淘汰算法(OPT)。这是一种理想的算法，可用来作为衡量其他算法优劣的依据，在实际系统中是难以实现的，因为它必须先知道指令的全部地址流。由于本示例中已预先生成了全部的指令地址流，故可计算出最佳命中率。该算法的准则是淘汰已满页表中不再访问或是最迟访问的的页。这就要求将页表中的页逐个与后继指令访问的所有页比较，如后继指令不在访问该页，则把此页淘汰，不然得找出后继指令中最迟访问的页面淘汰。可见最佳淘汰算法要花费较长的运算时间。（2） 最近最少使用页淘汰算法(LRU)。这是一种经常使用的方法，有各种不同的实施方案，这里采用的是不断调整页表链的方法，即总是淘汰

4、页表链链首的页，而把新访问的页插入链尾。如果当前调用页已在页表内，则把它再次调整到链尾。这样就能保证最近使用的页，总是处于靠近链尾部分，而不常使用的页就移到链首，逐个被淘汰，在页表较大时，调整页表链的代价也是不小的。（3） 程序框图如下图2所示。图2 计算页面命中率框图3、程序运行结果格式(1) 程序运行结果格式THE VIRTUAL ADDRESS STREAM AS FOLLOWS:a0 =16895 a1=16896 a2=16897 a3=16302a4=25403 a5=13941 a6=13942 a7=8767A252=23583 a253=20265 a254=20266 a2

5、55=20267= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =The algorithm is:optPAGE NUMBER WITH SIZE 1k FOR EACH ADDRESS IS:pageno0=17pageno1=17 pageno2=17 pageno3=16pageno4=25 pageno5=14 pageno6=14 pageno7=9pageno252=24 pageno253=20 pageno254=20 pageno255=20vmsize=32

6、k pagesize=1k- -page assigned pages_in/total references88.085937500000000E-1108.554687500000000E-1PAGE NUMBER WITH SIZE 2k EACH ADDRESS IS:PAGE NUMBER WITH SIZE 4k EACH ADDRESS IS:PAGE NUMBER WITH SIZE 8k EACH ADDRESS IS:End the result for opt* *the algorithm is lru同上End the result for lru*(2)示例中使用的

7、有关数据结构、常量和变量说明如下：length 被调试的指令地址流长度，可作为一个常量设定。called当前请求的页面号。pagefault页面失效标志，如当前请求页called已在页表内，则置pagefault=false，否则为true。table 页表。tablei=j,表示虚存的第j页在实存的第i页中。used当前被占用的实存页面数，可用来判断当前实存中是否有空闲页。（3）本程序启动后，屏幕上显示“the algorithm is：”，用户可选择最佳淘汰算法（打入“OPT”）或者最近最少使用淘汰算法(打入“LRU”) 计算页面命中率。当然还可以加入各种其他的算法。三、实习题（1） 编制

8、和调试示例给出的请求页式存储管理程序，并使其投入运行。（2） 增加12种已学过的淘汰算法，计算它们的页面访问命中率。试用各种算法的命中率加以比较分析。提示：可选用FIFO方法，即先访问的页先淘汰，也可选用LRU方法中的其他方案。如在页表中设置标志位，按标志位值得变化来淘汰。也可用LFU方法，为页表中各页面设置访问计数器，淘汰访问频率最低的页（注意：当前访问的页不能淘汰）等等。实验步骤与源程序#include "iostream"#include "stdio.h"#include "stdlib.h"using namespace s

9、td;#define Max 30/某进程调入内存中的最大页面数#define Size 10/系统为某进程分配的最大物理块数void Init(int Block,int m)/初始化物理块int i;for(i=0;i<m;i+)Blocki=-1;void creat(int Page,int n)/输入页面串引用号int i;for(i=0;i<n;i+)cin>>Pagei;void Init1(int Block1,int m1)int i;for(i=0;i<m1;i+)Block1i=-1;void creat1(int Page,int n1)i

10、nt i;for(i=0;i<n1;i+)Pagei;void LRU(int Page,int Block1,int n1,int m1)int i,j,max_stay=0,count=0;int get=-1,flag=-1,block_num=-1;int timeSize;for(i=0;i<m1;i+)/初始化timetimei=0;for(i=0;i<n1;i+)for(j=0;j<m1;j+)/有空闲物理块时，页面直接驻入内存空闲块if(Block1j=-1)get=j;/物理块j即将(/等待)驻入新页面break;for(j=0;j<m1;j+)

11、/查找序号相同的页面 if(Block1j=Pagei)/物理块j中页面与当前期望调入内存的页面相同 timej=0;flag=j;break;for(j=0;j<m1;j+) /找到驻留内存时间最久的页面置换出if(timej>max_stay) max_stay=timej;block_num=j; /block_num标记当前序号物理块中页面驻留时间最久if(flag=-1)/不存在相同页面if(get!=-1)/物理块即将(/等待)驻入新页面Block1get=Pagei;/存入页面timeget=0;/当前物理块重新计时for(j=0;j<=get;j+)/已驻入页

12、面的驻留时间加1timej+;get=-1;else/页面调度置换，序号block_num的物理块是驻留时间最久的Block1block_num=Pagei;timeblock_num=0;for(j=0;j<Size;j+)timej+;block_num=-1;max_stay=0;count+;else/待调入页面与序号flag的物理块中页面相同for(j=0;j<m1;j+)timej+;flag=-1;for(j=0;j<m1;j+)/输出物理块中的页面驻入情况cout<<" "<<Block1j;cout<<

13、endl;if(n1>m1)count=count+m1;cout<<"缺页中断次数为:"<<count<<endl;void FIFO(int Page,int Block,int n,int m)int i,j,max_stay=0,count=0;int get=-1,flag=-1,block_num=-1;int timeSize;for(i=0;i<m;i+)timei=0;for(i=0;i<n;i+)for(j=0;j<m;j+)if(Blockj=-1)get=j;break;for(j=0;j&

14、lt;m;j+)if(Blockj=Pagei)flag=j;break;for(j=0;j<m;j+)if(timej>max_stay)max_stay=timej;block_num=j;if(flag=-1)if(get!=-1)Blockget=Pagei;timeget=0;for(j=0;j<=get;j+)timej+;get=-1;elseBlockblock_num=Pagei;timeblock_num=0;for(j=0;j<Size;j+)timej+;block_num=-1;max_stay=0;count+;elsefor(j=0;j&l

15、t;m;j+)timej+;flag=-1;for(j=0;j<m;j+)cout<<" "<<Blockj;cout<<endl;if(n>m)count=count+m;cout<<"缺页中断次数为:"<<count<<endl;void menu()cout<<"-1.LRU页面置换算法-"<<endl;cout<<"-2.FIFO 页面置换算法-"<<endl;cout<

16、<"-3.退出-"<<endl;cout<<"-默认:-1表示物理块空闲-"<<endl;cout<<"请选择算法"<<endl;void main()int n,m,PageMax,BlockSize,n1,m1,Block1Size; char t; cout<<endl<<"请输入系统为进程分配的物理块数m<=10:" cin>>m; m1=m;Init(Block,m);Init1(Block1,m1

17、);cout<<"请输入总页面数n<=30:"cin>>n;n1=n;cout<<"n请输入页面号引用串:"creat(Page,n); creat1(Page,n1); while(1) menu(); cin>>t; switch(t) case '1':LRU(Page,Block1,n1,m1); continue; case '2':FIFO(Page,Block,n,m); continue; case '3':exit(0);测试数据与实验

18、结果 图1 输入要分配的物理块数、页面总数、页面序列号图2 LRU算法的实现图3 FIFO算法的实现4、小结(1) 编制评测各种算法性能的模拟程序是研制系统程序，尤其是操作系统所必须的。模拟的环境愈是真实，其结果愈是可靠，也就更有利于选择合适的方案。本实习虽属简单，但可作为一个尝试。(2) 注意正整数的范围只能从032767，限制程序中的虚存尺寸为32K，实际如采用更大的虚存实存，更能说明问题。页面置换算法理解比较容易，这次根据学号要求实现的是LRU和FIFO算法的实现。其实这两种算法的程序编写比较容易，虽然不全是自己编写的，一部分是参考的网上的例题，但是通过对每一语句的理解，自己弄懂了整个程

19、序的执行原理。但是，在编写过程中自己还是遇到了一些问题。最大的一个问题就是两个算法的正确实现，在程序的编写时，两个程序是分开进行编写的，分别执行起来没有什么问题，但是把两个程序融合在一起后，却出现了问题，即在执行完成一个算法后再执行另外一个算法时，开始的数据是紧接着上次算法结果的数据进行实验的。这个问题困扰了我好长时间，直到现在还没有很好的解决掉，程序只能分别执行一次，如果再进行执行的话，就会出现问题。自己的编程技术不好，程序编的也很繁琐，但是基本的要求已经实现了，希望这次的实验是自己动手的一个开始，自己应该更加努力，再接再厉。四、思考题（1）设计一个界地址存储管理的模拟系统，模拟界地址方式下

20、存储区的分配和回收过程。提示：必须设置一个内存分配表，按照分配表中有关信息实施存储区的分配，并不断根据存储区的分配和回收修改该表。算法有首次匹配法，循环首次匹配法和最佳匹配法等。可用各种方法的比较来充实实习内容。可使用碎片收集和复盖等技术。对分区的管理法可以是下面三种算法之一：首次适应算法循环首次适应算法最佳适应算法#include<stdio.h>#include <dos.h>#include<stdlib.h>#include<conio.h>#include<iostream.h>#define n 10 /*假定系统允许的最

21、大作业数为n，假定模拟实验中n值为10*/#define m 10 /*假定系统允许的空闲区表最大为m，假定模拟实验中m值为10*/#define minisize 100 /*空闲分区被分配时，如果分配后剩余的空间小于minisize，则将该空闲分区全部分配，若大于minisize，则切割分配*/structfloat address; /*已分配分区起始地址*/float length; /*已分配分区长度，单位为字节*/int flag; /*已分配区表登记栏标志，用"0"表示空栏目*/used_tablen; /*已分配区表*/structfloat address

22、; /*空闲区起始地址*/float length; /*空闲区长度，单位为字节*/int flag; /*空闲区表登记栏标志，用"0"表示空栏目，用"1"表示未分配*/free_tablem; /*空闲区表*/void allocate(char J,float xk) /*给J作业，采用最佳分配算法分配xk大小的空间*/int i,k;float ad;k=-1;for(i=0;i<m;i+) /*寻找空间大于xk的最小空闲区登记项k*/if(free_tablei.length>=xk&&free_tablei.flag

23、=1)if(k=-1|free_tablei.length<free_tablek.length)k=i;if(k=-1)/*未找到可用空闲区，返回*/printf("无可用空闲区n");return;/*找到可用空闲区，开始分配：若空闲区大小与要求分配的空间差小于minisize大小，则空闲区全部分配；若空闲区大小与要求分配的空间差大于minisize大小，则从空闲区划出一部分分配*/if(free_tablek.length-xk<=minisize)free_tablek.flag=0;ad=free_tablek.address;xk=free_tabl

24、ek.length;elsefree_tablek.length=free_tablek.length-xk;ad=free_tablek.address+free_tablek.length;/*修改已分配区表*/i=0;while(used_tablei.flag!=0&&i<n) /*寻找空表目*/i+;if(i>=n) /*无表目可填写已分配分区*/printf("无表目填写已分分区，错误n");/*修正空闲区表*/if(free_tablek.flag=0)/*前面找到的是整个空闲分区*/free_tablek.flag=1;else/

25、*前面找到的是某个空闲分区的一部分*/free_tablek.length=free_tablek.length+xk;return;else/*修改已分配表*/used_tablei.address=ad;used_tablei.length=xk;used_tablei.flag=J;return;/*主存分配函数结束*/void reclaim(char J)/*回收作业名为J的作业所占主存空间*/int i,k,j,s,t;float S,L;/*寻找已分配表中对应登记项*/s=0;while(used_tables.flag!=J|used_tables.flag=0)&&a

26、mp;s<n)s+;if(s>=n)/*在已分配表中找不到名字为J的作业*/printf("找不到该作业n");return;/*修改已分配表*/used_tables.flag=0;/*取得归还分区的起始地址S和长度L*/S=used_tables.address;L=used_tables.length;j=-1;k=-1;i=0;/*寻找回收分区的空闲上下邻，上邻表目k，下邻表目j*/while(i<m&&(j=-1|k=-1)if(free_tablei.flag=1)if(free_tablei.address+free_tabl

27、ei.length=S)k=i;/*找到上邻*/if(free_tablei.address=S+L)j=i;/*找到下邻*/i+;if(k!=-1)if(j!=-1)/* 上邻空闲区，下邻空闲区，三项合并*/free_tablek.length=free_tablej.length+free_tablek.length+L;free_tablej.flag=0;else/*上邻空闲区，下邻非空闲区，与上邻合并*/free_tablek.length=free_tablek.length+L;elseif(j!=-1)/*上邻非空闲区，下邻为空闲区，与下邻合并*/free_tablej.add

28、ress=S;free_tablej.length=free_tablej.length+L;else/*上下邻均为非空闲区，回收区域直接填入*/*在空闲区表中寻找空栏目*/t=0;while(free_tablet.flag=1&&t<m)t+;if(t>=m)/*空闲区表满,回收空间失败,将已分配表复原*/printf("主存空闲表没有空间,回收空间失败n");used_tables.flag=J;return;free_tablet.address=S;free_tablet.length=L;free_tablet.flag=1;retu

29、rn;/*主存回收函数结束*/int main( )int i,a;float xk;char J;/*空闲分区表初始化：*/free_table0.address=10240; /*起始地址假定为10240*/free_table0.length=10240; /*长度假定为10240，即10k*/free_table0.flag=1; /*初始空闲区为一个整体空闲区*/for(i=1;i<m;i+)free_tablei.flag=0; /*其余空闲分区表项未被使用*/*已分配表初始化：*/for(i=0;i<n;i+)used_tablei.flag=0; /*初始时均未分配

30、*/while(1)printf("选择功能项（0-退出,1-分配主存,2-回收主存,3-显示主存）n");printf("选择功项(03) :");scanf("%d",&a);switch(a)case 0: exit(0); /*a=0程序结束*/case 1: /*a=1分配主存空间*/printf("输入作业名J和作业所需长度xk: ");scanf("%*c%c%f",&J,&xk);allocate(J,xk); /*分配主存空间*/break;case 2

31、: /*a=2回收主存空间*/printf("输入要回收分区的作业名");scanf("%*c%c",&J);reclaim(J); /*回收主存空间*/break;case 3: /*a=3显示主存情况*/*输出空闲区表和已分配表的内容*/printf("输出空闲区表：n起始地址 分区长度 标志n");for(i=0;i<m;i+)printf("%6.0f%9.0f%6dn",free_tablei.address,free_tablei.length, free_tablei.flag);pri

32、ntf(" 按任意键,输出已分配区表n");getch();printf(" 输出已分配区表：n起始地址 分区长度 标志n");for(i=0;i<n;i+)if(used_tablei.flag!=0)printf("%6.0f%9.0f%6cn",used_tablei.address,used_tablei.length, used_tablei.flag);elseprintf("%6.0f%9.0f%6dn",used_tablei.address,used_tablei.length, used_

33、tablei.flag);break;default:printf("没有该选项n");/*case*/*while*/return 1;/*主函数结束*/（2）自行设计或选用一种较为完善的内存管理方法，并加以实现。提示：设计一个段页式管理的模拟程序或通过一个实际系统的消化和分析，编制一个程序来模拟该系统。#include <iostream.h>#include <stdio.h>#include <string.h>struct program char name30; long start; long length; struct

34、program *next;struct space long start; long length; struct space *next;void creat();void allot();void back();void callback(program *r);void sort(space *L);void sort(program *S);void display(space *L);void display(program *S);space *L;program *S;void creat() L=new space; space *p=new space; p->sta

35、rt=0; p->length=128; p->next=NULL; L->next=p; S=new program; S->next=NULL;void allot() program *q; q=new program; cout<<"请输入进程名和占用空间大小:"<<endl; cin>>q->name>>q->length; if(q->length<=0) cout<<"进程空间大小错误."<<endl; delete q;

36、 return; space *p,*r; p=L; r=p; while(p->next!=NULL&&p->next->length<q->length) r=p; p=p->next; if(p->next=NULL) cout<<"占用空间过大，分配失败"<<endl; delete q; return; else q->start=p->next->start; q->next=S->next; S->next=q; p->next->

37、length-=q->length; if(p->next->length!=0) p->next->start+=q->length; else if(p->next->next!=NULL) p->next=p->next->next; else r->next=NULL; delete p->next; display(L); display(S);void back() char name30; cout<<"输入要回收的进程名：" cin>>name; progr

38、am *p; p=S; while(p->next!=NULL) if(strcmp(p->next->name, name)=0) callback(p); return; p=p->next; if(p->next=NULL) cout<<"此进程不存在,内存回收失败"<<endl;void callback(program *t) program *r; r=t->next; space *p,*q; long n; n=r->length; if(L->next=NULL) space *w=n

39、ew space; w->start=0; w->length=n; w->next=NULL; L->next=w; t->next=r->next; delete r; cout<<"此进程内存回收完毕."<<endl; display(L); display(S); return; p=L->next; while(p!=NULL&&p->start<r->start) q=p; p=p->next; if(q->start+q->length=r-&

40、gt;start)&&(r->start+n=p->start) /上下均空 q->next=p->next; q->length=q->length+p->length+n; t->next=r->next; delete r; else if(r->start+n=p->start) /下邻空 p->start-=n; p->length+=n; t->next=r->next; delete r; else if(q->start+q->length=r->star

41、t) q->length+=n; t->next=r->next; delete r; else space *sp=new space; sp->start=r->start; sp->length=n; sp->next=L->next; L->next=sp; t->next=r->next; delete r; cout<<"此进程内存回收完毕."<<endl; display(L); display(S);void display(space *L) sort(L); space *p=L->next; cout<<endl<<"空闲区情况："<<endl; if(p=NULL) cout<<"无空闲区了."<<endl; return; while(p!=NULL) cout<<"起始地址:"<<p->start<<" 长度:&quo