操作系统实验-存储管理

实验三存储管理【实验目的和要求】1、请求页式存储管理中页面置换算法模拟设计。2、了解虚拟存储技术的特点。3、掌握请求页式存储管理的页面置换算法。【实验原理】1、存储管理的主要功能之一是合理地分配空间。2、请求页式管理是一种常用的虚拟存储管理技术。。3、命中率=1-(页面失效次数/页地址流长度)。本实验页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。【实验步骤】一、问题描述与分析1、通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：(1)50%的指令是顺序执行的；(2)25%的指令是均匀分布在前地址部分；(3)25%的指令是均匀分布在后地址部分。具体的实施方法是：(1)在[0,319]的指令地址之间随机选取一起点m；(2)顺序执行一条指令，即执行地址为m+l的指今；(3)在前地址[0,m+l]中随机选取一条指令并执行，该指令的地址为m’；(4)顺序执行一条指今，其地址为m’+l；(5)在后地址[m’+2,319]中随机选取一条指令并执行；(6)重复上述步骤(1)一(5)，直到执行320次指令。2、将指令序列变换成为页地址流(1)页面大小为1K；(2)用户内存容量为4页到32页；(3)用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条~第9条指令为第0页(对应虚存地址为[0,9])；第10条~第19条指令为第1页(对应虚存地址为[10,l9])；……第310条~第319条指令为第31页(对应虚存地址为[310,3191])；按以上方式，用户指令可组成32页。3、考虑计算并输出下述各种算法在不同内存容量下的命中率。(1)先进先出的算法(FIFO)；(2)最近最少使用算法(LRU)；其中(1)和(2)必做三、程序设计与调试在VC++6.0环境下进行程序设计和调试。程序分析：问题1：怎样使模拟的指令随机？答：通过使用C++的rand函数生成随机数，来产生指令，并用算法保证指定指令序列的需求。问题2：指令序列如何变换成页地址流的？页地址主要包括哪两部分?答：for(i=0;itotal_instruction;i++){page[i]=a[i]/10;offset[i]=a[i]%10;}由page[i]=a[i]/10;计算出页号。再执行offset[i]=a[i]%10;计算出偏移量。页地址包括页号和偏移量两部分问题3：实验中的页帧可以设置从多少到多少？页帧32是什么意思？答：页帧可以设置4到32页用户虚拟内存为32k，虚拟页面无法映射到这些地址，没有意义。问题4：FIFO的已经分配的页面是如何管理的？答：由操作系统维护一个队列(链表)，新页面由队尾进入，时间最久的页面从队头出去。当发生缺页中断时，淘汰表头的页面并把新调度的页面加到表尾。问题5：LRU算法是如何确定哪一页被置换的？主要思想是什么？答：LRU算法的置换在发生中断的时侯未使用时间最长的页面。LRU的主要思想：已经很久没使用的页面很有可能在未来较长的一段时间内仍然不会被使用。在缺页中断发生时，置换未使用时间最长的页面。四、数据分析分析数据输出结果（文字阐述分析即可）。问题1：为什么命中率最高为90%？答：因为一共32个页帧，一共出现320次，一共占总页帧的10%。每一个页帧在第一次进入内存时都会产生缺页，所以最高只有90%的命中率。问题2：FIFO和LRU比较，命中率怎样？主要原因是什么？答：FIFO比LRU命中率低，因为在FIFO算法中经常被访问的很有可能是先进入的那些页面，由于它先进入内存，在算法的规定下导致内存中经常会进行缺页置换。这种操作会导致命中率变低。问题3：voidinitialize(inttotal_pf)都做了什么？答：页面的初始化函数，给相关的页面赋值。【实验主要仪器及材料】Windows/X86计算机VC++6.0程序源代码：(Dev-C++编译通过)#defineINVALID-1#definetotal_instruction320//指令流长#definetotal_vp32//虚拟页表长度//#defineclear_period50//清零周期typedefstruct//页面结构{intpn,pfn,counter,time;//页号、页面有效无效、一个周期内访问该页面次数、访问时间}pl_type;pl_typepl[total_vp];//页面结构数组structpfc_struct//页面控制结构{intpn,pfn;structpfc_struct*next;};typedefstructpfc_structpfc_type;pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;intdiseffect;inta[total_instruction];intpage[total_instruction],offset[total_instruction];voidinitialize(int);voidFIFO(int);voidLRU(int);//voidOPT(int);#includestdio.h#includestdlib.h#includeprocess.hintmain(){intS,i;srand(_getpid()*10);//每次运行时进程号不同，可以作为初始化随机数队列的种子S=319*rand()/32767;//得到一个0到319之间的一个数for(i=0;itotal_instruction;i+=4)//产生指令队列{a[i]=S;//任选一指令访问点a[i+1]=a[i]+1;//顺序执行一条指令if(a[i+1]==320)a[i+1]=0;a[i+2]=a[i]*rand()/32767;//执行前地址指令a[i+3]=319-a[i+2];//执行后地址指令//S=rand()*(318-a[i+2])/32767+a[i+2]+1;S=319*rand()/32767;}for(i=0;itotal_instruction;i++)//将指令序列变换成页地址流：页号+偏移量{page[i]=a[i]/10;offset[i]=a[i]%10;}for(i=4;i=32;i++){printf(%2dpageframes,i);FIFO(i);LRU(i);//OPT(i);//LFU(i);//NUR(i);printf(\n);}return1;}voidFIFO(inttotal_pf)//total_pf是用户进程页面数目{inti;pfc_type*p;initialize(total_pf);busypf_head=busypf_tail=NULL;for(i=0;itotal_instruction;i++){if(pl[page[i]].pfn==INVALID){//页面失效diseffect++;//失效计数if(freepf_head==NULL)//无空闲页面时置换一页{p=busypf_head-next;pl[busypf_head-pn].pfn=INVALID;freepf_head=busypf_head;freepf_head-next=NULL;busypf_head=p;}p=freepf_head-next;//有空闲页面时分配一页freepf_head-next=NULL;freepf_head-pn=page[i];pl[page[i]].pfn=freepf_head-pfn;if(busypf_tail==NULL)busypf_head=busypf_tail=freepf_head;else{busypf_tail-next=freepf_head;busypf_tail=freepf_head;}freepf_head=p;}}printf(FIFO():%6.4f,1-(float)diseffect/320);}voidLRU(inttotal_pf)//total_pf是用户进程页面数目,即进程物理内存pageframe数目{intmin,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;itotal_instruction;i++){if(pl[page[i]].pfn==INVALID){//页面失效diseffect++;//失效计数if(freepf_head==NULL)//无空闲页面时置换一页{min=32767;for(j=0;jtotal_vp;j++)if(minpl[j].time&&(pl[j].pfn!=INVALID)){min=pl[j].time;minj=j;}freepf_head=&pfc[pl[minj].pfn];pl[minj].pfn=INVALID;pl[minj].time=-1;freepf_head-next=NULL;}//有空闲页面时分配一页pl[page[i]].pfn=freepf_head-pfn;pl[page[i]].time=present_time;freepf_head=freepf_head-next;}elsepl[page[i]].time=present_time;present_time++;}printf(LRU():%6.4f,1-(float)diseffect/320);}voidinitialize(inttotal_pf){inti;diseffect=0;for(i=0;itotal_vp;i++)//页面控制结构清空{pl[i].pn=i;pl[i].pfn=INVALID;pl[i].counter=0;pl[i].time=-1;}for(i=1;itotal_pf;i++)//建立链接{pfc[i-1].next=&pfc[i];pfc[i-1].pfn=i-1;}pfc[total_pf-1].next=NULL;pfc[total_pf-1].pfn=total_pf-1;freepf_head=&pfc[0];}