实验四-操作系统存储管理实验报告

实验四操作系统存储管理实验报告一、实验目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。二、实验内容通过计算不同算法的命中率比拟算法的优劣。同时也考虑了用户内存容量对命中率的影响。 页面失效次数为每次访问相应指令时，该指令所对应的页不在内存中的次数。 在本实验中，假定页面大小为1k，用户虚存容量为32k，用户内存容量为4页到32页。produce_addstream通过随机数产生一个指令序列，共320条指令。指令的地址按下述原那么生成：50%的指令是顺序执行的25%的指令是均匀分布在前地址局部25%的指令是均匀分布在后地址局部具体的实施方法是：在[0，319]的指令地址之间随机选取一起点m；顺序执行一条指令，即执行地址为m+1的指令；在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’；顺序执行一条指令，地址为m’+1的指令在后地址[m’+2，319]中随机选取一条指令并执行；重复上述步骤1〕~5〕，直到执行320次指令将指令序列变换称为页地址流在用户虚存中，按每k存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条~第9条指令为第0页〔对应虚存地址为[0，9]〕；第10条~第19条指令为第1页〔对应虚存地址为[10，19]〕；。。。。。。第310条~第319条指令为第31页〔对应虚存地址为[310，319]〕；按以上方式，用户指令可组成32页。计算并输出下属算法在不同内存容量下的命中率。先进先出的算法〔FIFO〕；最近最少使用算法〔LRU〕；最正确淘汰算法〔OPT〕；最少访问页面算法〔LFR〕；其中3〕和4〕为选择内容开始生成地址流开始生成地址流输入算法号S1≤S≤4形成地址页号用户内存空间msize=2Msize≤32OPT()FIFO()LRU()LFU()Msize加1S=?是否用其他算法继续结束NY1234YN提示出错，重新输入五运行结果首先打印出产生的指令信息，第一列为指令序列号，第二列为指令地址，第三列为指令所在的虚页号选择FIFO调度算法，并且内存从3也开始逐渐增加到32页，打印出缺页次数缺页率，命中率选择LRU调度算法，并且内存从3也开始逐渐增加到32页，打印出缺页次数缺页率，命中率选择OPT调度算法，并且内存从3也开始逐渐增加到32页，打印出缺页次数缺页率，命中率六实验程序产生指令流文件produce_addstream.h#ifndefPRODUCE_ADDSTREAM_H#definePRODUCE_ADDSTREAM_H#include<stdio.h>#include<stdlib.h>#include<time.h>#include<iomanip.h>#include<vector>usingnamespacestd;#definerandom(x)(rand()%x)#defineMAX_LENGTH320structproduce{ intnum;//指令序号 intzhiling;//指令地址 intvirtualpage;//指令虚页号 produce*next;};structproduce*creatlist();voidinsert(structproduce*first,structproduce*s);//插入一个节点〔尾插法〕voidprint(structproduce*first);//打印函数intmax(vector<vector<int>>,int);structproduce*creatlist(){ srand((int)time(0)); structproduce*first=newproduce; first->next=NULL; intm=0,m1=0; /* intyanzheng[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1}; for(inti=0;i<(MAX_LENGTH/4);i++) { structproduce*s0; s0=newproduce; s0->num=i*4+0; s0->zhiling=yanzheng[i*4+0]; s0->virtualpage=s0->zhiling; insert(first,s0); structproduce*s1; s1=newproduce; s1->num=i*4+1; s1->zhiling=yanzheng[i*4+1]; s1->virtualpage=s1->zhiling; insert(first,s1); structproduce*s2; s2=newproduce; s2->num=i*4+2; s2->zhiling=yanzheng[i*4+2]; s2->virtualpage=s2->zhiling; insert(first,s2); structproduce*s3; s3=newproduce; s3->num=i*4+3; s3->zhiling=yanzheng[i*4+3]; s3->virtualpage=s3->zhiling; insert(first,s3); } //*/ //* for(inti=0;i<(MAX_LENGTH/4);i++) { structproduce*s0; s0=newproduce; m=random(MAX_LENGTH); s0->num=i*4+0; s0->zhiling=m+1; s0->virtualpage=s0->zhiling/10; insert(first,s0); m1=random(m+1); structproduce*s1; s1=newproduce; s1->num=i*4+1; s1->zhiling=m1; s1->virtualpage=s1->zhiling/10; insert(first,s1); structproduce*s2; s2=newproduce; s2->num=i*4+2; s2->zhiling=m1+1; s2->virtualpage=s2->zhiling/10; insert(first,s2); structproduce*s3; s3=newproduce; s3->num=i*4+3; s3->zhiling=random(MAX_LENGTH-m1-2)+m1+2; s3->virtualpage=s3->zhiling/10; insert(first,s3); }//*/ returnfirst;}voidinsert(structproduce*first,structproduce*s){ structproduce*r=first; structproduce*p; while(r){p=r;r=r->next;} p->next=s;p=s; p->next=NULL;}voidprint(structproduce*first)//打印函数{ structproduce*p; p=first->next; cout<<"随机产生的指令的信息如下"<<endl; cout<<"指令序号"<<"指令地址"<<"指令虚页号"<<endl; while(p) { cout<<p->num<<'\t'<<p->zhiling<<setw(14)<<p->virtualpage<<endl; p=p->next; }}intmax(vector<vector<int>>page,intMaxpage){ inta=0,position=0; for(inti=0;i<Maxpage;i++) { if(page[i][1]>a) { a=page[i][1]; position=i; } } returnposition;}#endif先来先出调度算法：fifo.h#ifndefFIFO_H#defineFIFO_Hvoidfifo(structproduce*first,intMaxpage){ vector<int>page(Maxpage);// for(inti=0;i<Maxpage;i++)page[i]=-1; intrear=0;//定义一个变量，指向要被替换的位置 intpages;//定义变量保存当前指令的所在的地址 intcount1=0;// intcount2=0;//缺页次数 intfind=1; structproduce*p=first->next; while(p) { pages=p->virtualpage; for(inti=0;i<Maxpage;i++) { if(page[i]==-1||count1<Maxpage) { page[i]=pages; count1++; count2++; find=1; break; } elseif(page[i]==pages) { find=1; break; } find=0; } if(find==0) { page[rear]=pages; rear++; rear=rear%Maxpage; count2++; } p=p->next; } cout<<"FIFO调度算法缺页次数缺页率命中率"<<endl; cout<<count2<<setw(25)<<double(count2)/MAX_LENGTH<<setw(10)<<1-double(count2)/MAX_LENGTH<<endl;}#endifFIFO_HLRU调度算法lru.h#ifndefLRU_H#defineLRU_H#include<vector>usingnamespacestd;//intmax(vector<vector<int>>,int);voidlru(structproduce*first,intMaxpage){ structproduce*p=first->next; vector<vector<int>>page2(Maxpage,vector<int>(2)); intcount1=0;//定义内存已经被占用的页数 intcount2=0;//定义记录缺页次数 intequal=0;//定义判断如果当前页数与比拟的页数，如果相等那么为1，否那么为0 intplace=0;//定义要替换的位置 for(inti=0;i<Maxpage;i++) { page2[i][0]=-1;page2[i][1]=0; } while(p) { if(count1<Maxpage) { for(inti=0;i<Maxpage;i++) { page2[i][1]=page2[i][1]+1; if(page2[i][0]==-1) { page2[i][0]=p->virtualpage; count2++; break; } elseif(page2[i][0]==p->virtualpage) { page2[i][1]=1; } } count1++; } else { for(inti=0;i<Maxpage;i++) { page2[i][1]+=1; if(page2[i][0]==p->virtualpage) {equal=1;place=i;break;} } if(equal==1) { page2[place][1]=1; equal=0; } else { place=max(page2,Maxpage); page2[place][1]=1; page2[place][0]=p->virtualpage; count2++; } } p=p->next; } cout<<"LRU调度算法缺页次数缺页率命中率"<<endl; cout<<count2<<setw(24)<<double(count2)/MAX_LENGTH<<setw(10)<<1-double(count2)/MAX_LENGTH<<endl;}#endifLRU_HOPT调度算法opt.h#ifndefOPT_H#defineOPT_H#include<vector>usingnamespacestd;intsearch(structproduce*place,intposition);voidopt(structproduce*first,intMaxpage){ structproduce*p=first->next; vector<vector<int>>page3(Maxpage,vector<int>(2)); intcount1=0;//定义内存已被使用的页数 intcount2=0;//定义缺页次数 intcurrent=0;//定义当前工作位置 intequal=0;//定义判断如果当前页数与比拟的页数，如果相等那么为1，否那么为0 intplace=0;//定义要替换的位置 for(inti=0;i<Maxpage;i++) { page3[i][0]=-1;page3[i][1]=0; } while(p) { //cout<<1111<<endl; if(count1<Maxpage) { for(inti=0;i<Maxpage;i++) { if(page3[i][0]==-1) { page3[i][0]=p->virtualpage; page3[i][1]=search(p,current); count2++; break; } elseif(page3[i][0]==p->virtualpage) { page3[i][1]=search(p,current); } } count1++; } else { for(inti=0;i<Maxpage;i++) { if(page3[i][0]==p->virtualpage) {equal=1;place=i;break;} } if(equal==1) { page3[place][1]=search(p,current); equal=0; } else { place=max(page3,Maxpage); page3[place][1]=search(p,current); page3[place][0]=p->virtualpage; count2+=1; } } p=p->next; current+=1; } cout<<"OPT调度算法缺页次数缺页率命中率"<<endl; cout<<count2<<setw(25)<<double(count2)/MAX_LENGTH<<setw(10)<<1-double(count2)/MAX_LENGTH<<endl;}intsearch(structproduce*place,intposition){ structproduce*p=place->next; intcurrent=place->virtualpage; intposition1=position+1; while(p) { if(current==p->virtualpage) { returnposition1; } position1++; p=p->next; } returnposition1;}#endif主函数控制台ccglmain.cpp#include<iostream.h>#include"produce_addstream.h"#include"fifo.h"#include"lru.h"#include"opt.