《北邮 操作系统试验 页面置换算法》由会员分享,可在线阅读,更多相关《北邮 操作系统试验 页面置换算法(12页珍藏版)》请在金锄头文库上搜索。
1、课本第九章21题实验ytinrete1 .实验目的:学习页面置换算法2 .实验内容Write a program that implements the FIFO and LRU page-replacement algorithms presented in this chapter. First, generate a random page reference string where page numbers range from 0.9. Apply the random page-reference string to each algorithm and record the n
2、umber of page faults incurred by each algorithm. Implement the replacement algorithms such that the number of page frames can vary from 1.7. Assume that demand paging is used.写一个程序来实现本章中介绍的FIFO和LRU页置换算法。首先产生一个随机的页面引 用序列,页面数从09。将这个序列应用到每个算法并记录发生的页错误的次数。实现这个 算法时,要将页帧的数量设为可变(从17)。假设使用请求调页。3 .设计说明FIFO算法
3、:每次请求先查找是否有空块,有则替换,并标记为最晚到达,若没有则从标记中寻找最 新到达的块,替换,并更新标记表。标记数字越小,到达时间最早。LRU算法:每次请求先查找是否有空块,有则替换,并标记为最近使用时间最短者,若没有则从标 记中寻找最近使用时间最长者,替换,并更新标记表。标记数字越小,最近使用频率越低。4.实验环境windows? ultimate x64 with sp1 Dev-c+5 .程序源码#include#include#include#include #include #include using namespace std;typedef struct block/页帧块
4、结构int num;int lable;block;int page_size, frame_size;/序列数,页帧大小vector order;/存 放序列vector frame;/页帧void page_replacement (int kind)/kind=1 为 FIFO,kind=2 为 LRU初始化frame.clear();block init;init.num=-1;init.lable=-1;for(int i=0; iframe_size; i+)frame.push_back(init);int error=0;/错误次数int seq=0;/标记数字int posi
5、tion=-1;/ 匹配位置for(int i=0; iorder.size(); i+)position=-1; couti:引用请求为order.at(i) :endl;cout引用前页帧情况(-1为空):;for(int j=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)int temp=(frame.at(posi
6、tion).lable;(frame.at(position).lable=seq+1;for(int j=0; jtemp)(frame.at(j).lable-;多余部分结束elsecout匹配失败! endl;error+;开始置换/先查找空页 for(int j=0; jframe.size(); j+)if(-1=(frame.at(j).num)position=j;break;if(-1!=position)/W 空页(frame.at(position).num=order.at(i);/置换 seq+;(frame.at(position).lable=seq;/标 记数字e
7、lse/没有空页for(int j=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(int j=0; jframe.size(); j+)/更 新标记(frame.at(j).lable-;cout引用后页帧情况(-1为空):;for(int j=0; jframe.size(); j+)cout(frame.at(j).num,;cout
8、endlendl;coutendl算法结束,总页错误的次数为:errorendlendl;int main()coutpage_size;if(page_size=0)cout序列数有误; return 0;coutframe_size;if(frame_size7)cout页帧数有误; return 0;int number;srand(unsigned(time(NULL);/设置随机数种子for(int i=0; ipage_size; i+)number=rand()%10;/页面数从 0 到 9 order.push_back(number);/*课本例子,使用这个时将上面的随机数注
9、释掉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_ba
10、ck(0);order.push_back(1);order.push_back(7);order.push_back(0);order.push_back(1);*/coutendl随机生成的页面引用序列为:endl;for(int i=0; iorder.size(); i+)coutorder.at(i);if(order.size()-1!=i) cout,;coutendlendl;page_replacement (1);coutendl为三)(一土为气、E乩-L(一土.为气)=7- 0. 1-(一土 为空)E % L(土 为i】s 2 , 0, ,为宝)1-1为主)(-.VnV为
11、三)(-土 为空)=2,(T为空):4,(T为空):4,(T为空):4,1-弓引用-一匹配失败!引用后页帧情况(-土 为空)=4,(T为空)=4,1队斐请秘O = 弓用箭页麻橹况(. 匹酉己失败引用后页侦情况(T为空)*,况(T为空):4,it 引用前情讽(一上为空)=9,(一上为空)=9,览育矗Is褊(T为空):0,IriiSt情况为空)*,麟碱匕为空)引鬲夸苦帧情后1为空)麟磕言为空)引鬲夸芳帧情a (-1为空)弓雷鹰贞-岛(T为空)噂后页情况(T为空)瀛贞M为空)引焉言资帧情后(T为空)弓1晋骚麟Lt为空)号等懿I贞情沉(T为空)辜往结束,总页错误的次数为:2, 3,1, 3,1, 3,1, 2,1, 2,1, 2,1, 2,1, 2,1, 2,1, 2,1, 2,0, 2,0, 2,0, 1,15FIFO错误数15,置换顺序课件与课本完全相符。lru .哥律学遗麟湛:一必空=-1, L -1, 后页帔情况(T为空)=?- -1- -1-W况况 布由 造页附黄 a里后 弓ffi配用 :E 1弓II弓乩(T为空气L0,专弓用请一*引用前页帧匹配失败引用右贝帧情兄(T为空气一土 为空;1 =2,0,。兄兄情 求帆!帔 请贝功贝 a刖成后 引用配用 :IU- 4RTS 弓 -3况 为尚 点帧情 请