北邮-操作系统试验-页面置换算法

课本第九章21题实验ytinrete1．实验目的：学习页面置换算法2．实验内容WriteaprogramthatimplementstheFIFOandLRUpage-replacementalgorithmspresentedinthischapter.First,generatearandompagereferencestringwherepagenumbersrangefrom0..9.Applytherandompage-referencestringtoeachalgorithmandrecordthenumberofpagefaultsincurredbyeachalgorithm.Implementthereplacementalgorithmssuchthatthenumberofpageframescanvaryfrom1..7.Assumethatdemandpagingisused.写一个程序来实现本章中介绍的FIFO和LRU页置换算法。首先产生一个随机的页面引用序列，页面数从0~9。将这个序列应用到每个算法并记录发生的页错误的次数。实现这个算法时，要将页帧的数量设为可变（从1~7）。假设使用请求调页。3．设计说明FIFO算法：每次请求先查找是否有空块，有则替换，并标记为最晚到达，若没有则从标记中寻找最新到达的块，替换，并更新标记表。标记数字越小，到达时间最早。LRU算法：每次请求先查找是否有空块，有则替换，并标记为最近使用时间最短者，若没有则从标记中寻找最近使用时间最长者，替换，并更新标记表。标记数字越小，最近使用频率越低。4．实验环境windows7ultimatex64withsp1Dev-c++5．程序源码#includestdlib.h#includecstdlib#includetime.h#includeiostream#includevector#includewindows.husingnamespacestd;typedefstructblock//页帧块结构{intnum;intlable;}block;intpage_size,frame_size;//序列数，页帧大小vectorintorder;//存放序列vectorblockframe;//页帧voidpage_replacement(intkind)//kind=1为FIFO,kind=2为LRU{//初始化frame.clear();blockinit;init.num=-1;init.lable=-1;for(inti=0;iframe_size;i++){frame.push_back(init);}interror=0;//错误次数intseq=0;//标记数字intposition=-1;//匹配位置for(inti=0;iorder.size();i++){position=-1;couti:引用请求为order.at(i):endl;cout引用前页帧情况（-1为空）:;for(intj=0;jframe.size();j++){cout(frame.at(j)).num,;if(order.at(i)==(frame.at(j)).num)position=j;}coutendl;if(-1!=position){cout匹配成功！endl;//更新标记这也是LRU算法比FIFO唯一多出来的地方if(kind==2){inttemp=(frame.at(position)).lable;(frame.at(position)).lable=seq+1;for(intj=0;jframe.size();j++){if(-1!=(frame.at(j)).num)//不是空块{if((frame.at(j)).labletemp){(frame.at(j)).lable--;}}}}//多余部分结束}else{cout匹配失败！endl;error++;//开始置换//先查找空页for(intj=0;jframe.size();j++){if(-1==(frame.at(j)).num){position=j;break;}}if(-1!=position)//有空页{(frame.at(position)).num=order.at(i);//置换seq++;(frame.at(position)).lable=seq;//标记数字}else//没有空页{for(intj=0;jframe.size();j++)//找相应的置换项{if(1==(frame.at(j)).lable){position=j;break;}}(frame.at(position)).num=order.at(i);//置换(frame.at(position)).lable=seq+1;//标记进入顺序for(intj=0;jframe.size();j++)//更新标记{(frame.at(j)).lable--;}}}cout引用后页帧情况（-1为空）:;for(intj=0;jframe.size();j++){cout(frame.at(j)).num,;}coutendlendl;}coutendl算法结束，总页错误的次数为：errorendlendl;}intmain(){cout请输入测试的页面序列数：;cinpage_size;if(page_size=0){cout序列数有误;return0;}cout请输入页帧数量(1~7):;cinframe_size;if(frame_size=0||frame_size7){cout页帧数有误;return0;}intnumber;srand(unsigned(time(NULL)));//设置随机数种子for(inti=0;ipage_size;i++){number=rand()%10;//页面数从0到9order.push_back(number);}/*课本例子，使用这个时将上面的随机数注释掉order.push_back(7);order.push_back(0);order.push_back(1);order.push_back(2);order.push_back(0);order.push_back(3);order.push_back(0);order.push_back(4);order.push_back(2);order.push_back(3);order.push_back(0);order.push_back(3);order.push_back(2);order.push_back(1);order.push_back(2);order.push_back(0);order.push_back(1);order.push_back(7);order.push_back(0);order.push_back(1);*/coutendl随机生成的页面引用序列为：endl;for(inti=0;iorder.size();i++){coutorder.at(i);if(order.size()-1!=i)cout,;}coutendlendl;page_replacement(1);coutendlendl;page_replacement(2);system(pause);return0;}6．结果测试首先以课本上为例：20个序列：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1帧序列为3FIFO错误数15，置换顺序课件与课本完全相符。LRU错误数12，置换顺序课件与课本完全相符。其他随机数实验其他随机数实验