页面置换算法实验报告.pdf
操作系统课程设计报告课课程程名名称称：操操作作系系统统课课程程设设计计课程设计题目课程设计题目：页面置换算法页面置换算法学院：学院：计算机科学与技术学院计算机科学与技术学院专专业业：科科技技小小组组成成员员:庞庞思思慧慧E01114081E01114081王王蒙蒙E01114161E01114161姚姚慧慧乔乔E01114349E01114349朱朱潮潮潮潮E01114408E01114408指导老师：指导老师：邱剑锋邱剑锋目录目录No table of contents entries found.No table of contents entries found.页面置换算法模拟设计页面置换算法模拟设计1.1.实验目的实验目的（1）通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。（2）掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。（3）通过对几种置换算法命中率的比较，来对比他们的优缺点。2.2.实验要求实验要求计算并输出下述各种算法在不同内存容量下的命中率。A A先进先出的算法（FIFO）B B最近最少使用算法（LRU）C C最佳淘汰算法（OPT）3.3.实验内容与步骤实验内容与步骤(1)通过随机数产生一个指令序列，共 320 条指令，具体的实施方法是：A 0，319的指令地址之间随机选取一起点M;B 顺序执行一条指令，即执行地址为M+1 的指令；C 在前地址0，M+1中随机选取一条指令并执行，该指令的地址为M;D 顺序执行一条指令，其地址为M+1；E 在后地址M+2，319中随机选取一条指令并执行；F重复 AE，直到执行 320 次指令。(2)指令序列变换成页地址流A.页面大小为 1K；B.用户内存容量为 4 页到 32 页；C.用户虚存容量为 32K。在用户虚存中，按每 K 存放 10 条指令排列虚存地址，即 320 条指令在虚存中的存放方式为：第 0 条第 9 条指令为第 0 页（对应虚存地址为0，9）；第 10 条第 19 条指令为第 1 页（对应虚存地址为10，19）；。第 310 条第 319 条指令为第 31 页（对应虚存地址为310，319）；(3)计算并输出上述各种算法在不同内存容量下的命中率。命中率=1-缺页次数/页地址流长度4.4.算法思想算法思想在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。1.先进先出算法 FIFO：这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。2.最近最久未使用算法 LRU（leastrecentlyused）：算法的基本思想：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。3.最佳淘汰算法 OPT其所选择的被淘汰的页面将是以后永不使用，或许是未来最长时间内不使用的页面，该算法可保证获得最低的淘汰率，但在实际运用中无法实现，可用来评价其他算法的命中率。5.5.模块设计模块设计开始输入内存数调用各种置换算法，命中率比较结束结束总模块图总模块图入口产生随机数、要调入的页面、离现在处理时间最长的页面、初始化页面情况Yt1NN根据选择的算法进行直接存入内存计算缺页率，并输出数据结束主程序图6.6.程序设计程序设计struct Pro um=s;um=pi.num+1;um=(int)(float)pi.num*(rand()/(RAND_MAX+);um=pi+2.num+1;um)*(rand()/(RAND_MAX+)+pi+2.num;for(i=0;iM;i+)pi.time=0;int Search(int e,Pro*page1,int N)um)return i;return-1;int Max(Pro*page1,int N)ime,i=0;while(iN)if(eLRUCLOCKFIFO。实际上，在内存页面数较少（45 页面）时，3 种算法的命中率差别不大，可是 50%左右。在内存页面为 725 个页面之间时，3 种算法的访内命中率大致在52%至 87%之间变化。在内存页面为2532 个页面时，由于用户进程的所有指令基本上都已装入内存，从而命中率已较大。从而算法之间的差别不大。9.9.程序代码程序代码#include 页面置换算法模拟设计#ifdef _DEBUG#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE=_FILE_;#endif The framework does this automatically For MFC applications using the document/view model,void CMyDlg:OnPaint()if(IsIconic()return(HCURSOR)m_hIcon;#include#include#include#define M 320CPaintDC dc(this);HCURSOR CMyDlg:OnQueryDragIcon()int N;struct Proum=s;um=pi.num+1;um=(int)(float)pi.num*(rand()/(RAND_MAX+);um=pi+2.num+1;um)*(rand()/(RAND_MAX+)+pi+2.num;for(i=0;iM;i+)pi.time=0;/*p0.num=10;p1.num=22;p2.num=33;p3.num=44;p4.num=50;int Max(Pro*page1,int N)ime,i=0;return-1;p5.num=13;p6.num=32;p7.num=22;um)return i;while(iN)if(epagei.time)e=pagei.time;ime)return i;um);um=pj.num/10)break;str1+=tmp1;k+;if(k%16=0)str1+=nrnrnr;(_T(str1);um/10);str2+=tmp2;k+;if(k%16=0)str2+=nrnrnr;(_T(str2);Pro*page=new ProN;for(int j=0;j=0)elsestr3+=nrnrnr;(_T(str3);(%-4d,pagei.num);str3+=tmp3;um,page,N);if(k=0)elsepagek.time=0;for(p2=0;p2N;p2+)if(p2!=k)pagep2.time+;if(t1=0)i+;elseif(t1=0)+i1;um=pi1.num/10;um=-1;while(i2=0)pagej.time=0;pagej.time=j;pagek.time=0;for(p2=0;p2N;p2+)if(p2!=k)pagep2.time+;elseif(ttN)elsefor(p2=0;p2N;p2+)if(p2!=t2)pagep2.time+;n2+;t2=Max(page,N);paget2.num=pi2.num/10;paget2.time=0;n2+;paget2.num=pi2.num/10;ime=0;i2+;s2=1-n2/M;um=-1;while(i3=0)i3+;pagej.time=j;elseif(tttN)n3+;paget3.num=pi3.num/10;um=pi3.num/10;n3+;i3+;else break;bt=FIFO,LRU,OPT 命中率分别为：;(%s%s%-4f%s%-4f%s%-4f,bt,kg,s1,kg,s2,kg,s3);MessageBox(st,命中率比较);UpdateData(false);10.10.课程设计小结课程设计小结这次实验相对于以前来说比较不一样的是对于界面的制作，是一个比较新奇的体验。整体来说的话还算是比较简单，需要注意的是在编写程序之前要将课程设计的要求及解决思路。通过此次实验,加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现,特别是对虚拟存储和页面置换有了一定的了解。
