實(shí)驗(yàn)四-操作系統(tǒng)存儲(chǔ)管理實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)四操作系統(tǒng)存儲(chǔ)管理實(shí)驗(yàn)報(bào)告一、實(shí)驗(yàn)?zāi)康拇鎯?chǔ)管理的主要功能之一是合理地分配空間。請(qǐng)求頁(yè)式管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。本實(shí)驗(yàn)的目的是通過(guò)請(qǐng)求頁(yè)式管理中頁(yè)面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁(yè)式存儲(chǔ)管理的頁(yè)面置換算法。二、實(shí)驗(yàn)內(nèi)容通過(guò)計(jì)算不同算法的命中率比擬算法的優(yōu)劣。同時(shí)也考慮了用戶內(nèi)存容量對(duì)命中率的影響。 頁(yè)面失效次數(shù)為每次訪問(wèn)相應(yīng)指令時(shí)，該指令所對(duì)應(yīng)的頁(yè)不在內(nèi)存中的次數(shù)。 在本實(shí)驗(yàn)中，假定頁(yè)面大小為1k，用戶虛存容量為32k，用戶內(nèi)存容量為4頁(yè)到32頁(yè)。produce_addstream通過(guò)隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令。指令的地址按下述原那么生成：50%的指令是順序執(zhí)行的25%的指令是均勻分布在前地址局部25%的指令是均勻分布在后地址局部具體的實(shí)施方法是：在[0，319]的指令地址之間隨機(jī)選取一起點(diǎn)m；順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令；在前地址[0，m+1]中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為m’；順序執(zhí)行一條指令，地址為m’+1的指令在后地址[m’+2，319]中隨機(jī)選取一條指令并執(zhí)行；重復(fù)上述步驟1〕~5〕，直到執(zhí)行320次指令將指令序列變換稱(chēng)為頁(yè)地址流在用戶虛存中，按每k存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為：第0條~第9條指令為第0頁(yè)〔對(duì)應(yīng)虛存地址為[0，9]〕；第10條~第19條指令為第1頁(yè)〔對(duì)應(yīng)虛存地址為[10，19]〕；。。。。。。第310條~第319條指令為第31頁(yè)〔對(duì)應(yīng)虛存地址為[310，319]〕；按以上方式，用戶指令可組成32頁(yè)。計(jì)算并輸出下屬算法在不同內(nèi)存容量下的命中率。先進(jìn)先出的算法〔FIFO〕；最近最少使用算法〔LRU〕；最正確淘汰算法〔OPT〕；最少訪問(wèn)頁(yè)面算法〔LFR〕；其中3〕和4〕為選擇內(nèi)容開(kāi)始生成地址流開(kāi)始生成地址流輸入算法號(hào)S1≤S≤4形成地址頁(yè)號(hào)用戶內(nèi)存空間msize=2Msize≤32OPT()FIFO()LRU()LFU()Msize加1S=?是否用其他算法繼續(xù)結(jié)束NY1234YN提示出錯(cuò)，重新輸入五運(yùn)行結(jié)果首先打印出產(chǎn)生的指令信息，第一列為指令序列號(hào)，第二列為指令地址，第三列為指令所在的虛頁(yè)號(hào)選擇FIFO調(diào)度算法，并且內(nèi)存從3也開(kāi)始逐漸增加到32頁(yè)，打印出缺頁(yè)次數(shù)缺頁(yè)率，命中率選擇LRU調(diào)度算法，并且內(nèi)存從3也開(kāi)始逐漸增加到32頁(yè)，打印出缺頁(yè)次數(shù)缺頁(yè)率，命中率選擇OPT調(diào)度算法，并且內(nèi)存從3也開(kāi)始逐漸增加到32頁(yè)，打印出缺頁(yè)次數(shù)缺頁(yè)率，命中率六實(shí)驗(yàn)程序產(chǎn)生指令流文件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;//指令序號(hào) intzhiling;//指令地址 intvirtualpage;//指令虛頁(yè)號(hào) produce*next;};structproduce*creatlist();voidinsert(structproduce*first,structproduce*s);//插入一個(gè)節(jié)點(diǎn)〔尾插法〕voidprint(structproduce*first);//打印函數(shù)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)//打印函數(shù){ structproduce*p; p=first->next; cout<<"隨機(jī)產(chǎn)生的指令的信息如下"<<endl; cout<<"指令序號(hào)"<<"指令地址"<<"指令虛頁(yè)號(hào)"<<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先來(lái)先出調(diào)度算法：fifo.h#ifndefFIFO_H#defineFIFO_Hvoidfifo(structproduce*first,intMaxpage){ vector<int>page(Maxpage);// for(inti=0;i<Maxpage;i++)page[i]=-1; intrear=0;//定義一個(gè)變量，指向要被替換的位置 intpages;//定義變量保存當(dāng)前指令的所在的地址 intcount1=0;// intcount2=0;//缺頁(yè)次數(shù) 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調(diào)度算法缺頁(yè)次數(shù)缺頁(yè)率命中率"<<endl; cout<<count2<<setw(25)<<double(count2)/MAX_LENGTH<<setw(10)<<1-double(count2)/MAX_LENGTH<<endl;}#endifFIFO_HLRU調(diào)度算法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;//定義內(nèi)存已經(jīng)被占用的頁(yè)數(shù) intcount2=0;//定義記錄缺頁(yè)次數(shù) intequal=0;//定義判斷如果當(dāng)前頁(yè)數(shù)與比擬的頁(yè)數(shù)，如果相等那么為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調(diào)度算法缺頁(yè)次數(shù)缺頁(yè)率命中率"<<endl; cout<<count2<<setw(24)<<double(count2)/MAX_LENGTH<<setw(10)<<1-double(count2)/MAX_LENGTH<<endl;}#endifLRU_HOPT調(diào)度算法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;//定義內(nèi)存已被使用的頁(yè)數(shù) intcount2=0;//定義缺頁(yè)次數(shù) intcurrent=0;//定義當(dāng)前工作位置 intequal=0;//定義判斷如果當(dāng)前頁(yè)數(shù)與比擬的頁(yè)數(shù)，如果相等那么為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調(diào)度算法缺頁(yè)次數(shù)缺頁(yè)率命中率"<<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主函數(shù)控制臺(tái)ccglmain.cpp#include<iostream.h>#include"produce_addstream.h"#include"fifo.h"#include"lru.h"#include"opt.