2023年面置换算法实验报告2.docx

《2023年面置换算法实验报告2.docx》由会员分享，可在线阅读，更多相关《2023年面置换算法实验报告2.docx（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、页面置换算法实验报告进入页：15161815进入页：工6161815进入页 19191817进入页：19191820进入页：18191820进入页：19191820进入页：20222120进入页：2222120最佳置换算法缺页申断次数：7随机置换算法131215进入页：13131215进入页：15161215进入页：15181215进入页：19161917进入页：19161920随机置换算法缺页中断次数：12*先进先出置换算法131215进入页：13131215进入页：15121516进入页：15151618进入页：16151618进入页：1918191?进入页：19191720进入页：222

2、22120先进先出置换算法缺页申断次数：1。*最近最久未使用置换算法MX-fXMMX13 _ 1215进入页：13121513进入页：15 131615进入页：15131615进入页:15 161815进入页：16181516题人页：19161719进入页；19172019先入页：19 01819进入页:22212022进入页：15 161215A：1A：0A：1进入页：15 161815A：0A：1A：1进入页：16 LG1815A：1A：1A：1页:19A：11917A：115A：019页:19 1? A：020A：1卷入页:191820 A：122A：0页:2021 A：120 A：1进

3、入页,222221 A：120n：iCLOCK置换算法缺页中断次数：8改进的CLOCK置换算法*官改页（内存中序首）:115A：1M：0A：1M：1A：1M：0进入页；13131215修改页（内存中序号）：1A：1M：0A：1M：1fi：lM：0进入页：15161215修改页（内存中序号）： A：1M:0A：02M：1fi：lM：1进入页 15161815修改页（内存中序号） 2A：0M：0A：1M：0A：1M：1进入页：16161815修改页（内存中序号）：2A：1M：0A：1M：0A：1M：1页：191917修改页（内存中序号）：。A：1M：1fi：lM：015A：0M：1人页：19191

4、?20修改页（内存中序号）：1A：1M：1A：0M：1A：1M：01人页：19191820修改页（内存中序号）：1A：1M：1A：1M：1A：1M：0进入页：22212022修改页（内存中序号）：2A：0M：0A：1M：0A：1M：1改进的CLOCK置换算法缺页中断次数：9总结：缺页率最佳置换35%随机置换60%先进先出置换50Z最近最久未使用置换45%CLOCK 置换40Z改进CLOCK置换45% Press any key to continue,九、实验结果分析：1、最佳置换算法效果最佳不管在那组数据中，最佳置换算法的效果都是最佳的，旦都会比其它算法的 性能高出不少。但通过课堂上的学习，

5、我们知道这只是一种抱负化算法，但事实 上却难于实现，故重要用于算法评价参照。2、算法的性能总是最不好的这是由于算法每次总是从所有页面中挑一个置换出去,但我们知道页面的访 问存在着局部性的原理，并不是的,因此它的性能较差。3、最近最久未使用算法的性能较好。相较于先进先出和两种cloc k算法，最近最久未使用算法的性能略好，我们测试一、实验目的：设计和实现最佳置换算法、置换算法、先进先出置换算法、最近最久未使用置换 算法、简朴Clock置换算法及改善型Clock置换算法；通过支持页面访问序列 发生实现有关算法的测试及性能比较。二、实验内容：虚拟内存页面总数为N,页号从0到N 1 物理内存由M个物理

6、块组成页面访问序列串是一个整数序列，整数的取值范围为0到N 1。页面访 问序列串中的每个元素p表达对页面P的一次访问页表用整数数组或结构数组来表达符合局部访问特性的生成算法.拟定虚拟内存的尺寸N,工作集的起始位置p,工作集中包含的页数 e,工作集移动率m (每解决m个页面访问则将起始位置P +1), 以及一个范围在0和1之间的值t ；1 .生成m个取值范围在p和p + e间的数，并记录到页面访问序列串 中；.生成一个数r,0 W r W 1;2 .假如r I,则为p生成一个新值，否则p = (p + 1) mod N;.假如想继续加大页面访问序列串的长度，请返回第2步，否则结束。三、实验环境：

7、操作系统:Windows 7 的数据规模相对较小，相信假如采用更大规模的数据,其优势会更加明显。当从课堂上我们知道要想在实际的应用中实现本算法，用软件的方法速度太 慢,影响程序执行效率，假如采用硬件方法实现，则需要增长大量的硬件设备。4、先进先出与cl ock算法的性能基本相同这是由于两种c 1 ock算法遍历链表采用的就是FIFO的方法，而改善的c 1 ock算法相比于简朴clock算法的优势重要体现在会根据是否被修改善行选择， 以减少写回所花费的时间。十、实验总结：这次实验总体难度不是很大，需要实现的算法数R虽然不少，但基本思绪较为 相似，因此实现起来也并不是十分困难。通过完毕这次实验，除

8、了加深了我对几 种策略的理解，锻炼了我的编程能力，另一个巨大的收获就是了解了一些生成测 试数据的方法。为了使我们的测试数据更贴近现实，我们引入了工作集的概念, 并根据实际使用情况的特点设计出尽也许符合实际情况的数生成方案。通过阅读 课件再加上自己的理解，我了解了老师的设计思绪，感觉这个思绪极其巧妙，设 计中用到的方法和体现出的很多思想值得我们学习。十一、程序清单：#includein c 1 u de# inc 1 udeincl u d e# i nc 1 ude using n a mespace std：# de f i n e re f _s i ze 2 0define p hy_s

9、i z e 31 n t re f r e f_ s ize；f loat inte r rupt6 =0. 0;/i n t refr e f_si z e=0;in t p h y p hy_s i ze;/ /h/h/1/1/m/h/ /mmnn/void set_r a n d _ n um() /产生具有局部特性的数列(cou t ”页面访问序列:endl；in t p= 1 2;int e=4；int m= 4 ;o i n t i=0;in t j= 0 ;int n=0;0dou b 1 e t=0. 6;1 n t tem p ;f o r( i =0;im； i+, j+

10、+ )le e p (1000*i);srand(time (NULL);o temp= rand ()%e+p;o r efj =tem p ;coutre f;0fo r (n=0;n4; n +)。(o Sleep(I000*n); sra n d(time(NU L L); d o u b 1 e r=( d o u b le)(ra nd()%l 0)/10. 0;。 /coutrend 1 ;oif( r t) p= p +int(l 0 * r );o else9p=(p+l) %20;for(i=0; i ne x t=L;Lf 1 a g =0;r e t u rn i n

11、t E x change_ L N o d e (Lin k L i st &L, int e,in t i) 将链表 L 中序号为i的结点替换为内容为e的结点(i f(L- n e x t = L) exit (-1);Li n kList p, q ;o i n t j= 0 ;p=(L i n k List)mal 1 o c( s izeo f ( L Node)；oq= (Li n kLi s t)malloc (sizeo f (LNode);q-da t a=e;P=L;for(j=0； jnext;q-n e xt=p-n e xt-next；p-next=q;oq flag=

12、l? /设立新结点的访问位为1q-modi f y=0;设立新结点的修改位为0r e turn 1;)i n t I nsert_LNod e ( L inkLi s t &L, int e )/在循环链表中插入新的结点, 从L头结点开始依次向后插入Li n kL i st p , q;叩二(L in k List)ma 1 loc(sizeof(LNode)；q=(Li n k L i st)m a Hoc (siz e o f (LNode)；q-data= e ;oq-flag=l；。/设立新结点的访问位为1q-mod i f y=0；。/设立新结点的修改位为0P=L;while (p-

13、 n ex t !=L)(p=p-n e xt；)6p-next= q ;*q- n ext=L;ret u rn 1;b ool Sea rch_LinkList(LinkList &L, i n t e ,i n t &i)/找到链表 L 中内 容为e的结点，并用i返回其位置，i=l表达第一个非头结点，依次类推(i=l； i f (L- n ext=L) ex i t (-1);LinkList p;p= ( L inkL i s t )mal 1 o c (s i ze o f (LNode);if ( ! p ) e xit(- 1 )；p=L-next： W / p指向链表的第一个结

14、点(非头结点)w h ile (p! = L & p-data! = e )p=p-n ext；i +；0)i f (p=L)/没有找到符合规定的结点oreturn false;r e turn true；)vo id S ear c h_L L _Flag(LinkList &L j n t & i ) 用 i 返回第一个 flag 为0的结点的位置，i =1表达第一个非头结点，以此类推(i=l ；oLinkL i s t p;p = (L i n k L i s t )mal 1 o c (s i z e o f ( L Node);if (!p) exit(-l)；p=L-next;wh

15、ile(p-f 1 a g !=()(。叩,flag=0/修改访问标志位为0叩=p n e xt;ooif(p= L ) 00 / /跳过头结点9p=p-n ext；i+ ；o i f (i = =4)/跳过头结点。i=l;01/r e tu r n 1 ； void S e t _LL_Flag(L i nkLis t &L,int i )。设立链表L中的序号为i的结点的 flag标志为1;(LinkL i st p;p=(Li n kLi s t)malloc(sizeof ( L Nod e );i f(!p) e x it (-1);p =L-ne x t;i f (i = = 1 )

16、。叩 f a g=;i f ( i =2)( P =p-nex t ；o p- f lag=l;Ioif(i=3 )gp = p-n e xt;。叩二 p - n ex t ;gp-f 1 ag= 1;1in t Searc h _LL_M o d i fy C lock (LinkList &L, int &mo d ify_n u m)/找到改善的CLOCK算法所需要淘汰的页，用modi f y_num返回其位置modif y _n u m = 1 ;if (L-next=L) e xit(-l);L in k List p ;p二 (L i nkL i s t)m a Hoc ( s i

17、 zeof(LNod e );i f (!p) ex i t ( 1);p=L-ne x t; “/p指向链表的第一个结点(非头结点)-while (p!=L)/第一轮扫描A= 0并且M=()的结点oif(p f 1 ag= 0 & p -m o d i f y =0)。break ;。找至 ljo P =p-n ext;“mod i f y_num +;)if(p=L)(wTiodif y _num= 1 ；p =L-nexl；。wh i le(p!=L)。第二轮扫描A=()并且M=1的结点，同时修改访问过的结 点的访问位为0。 i f ( p - f 1 a g!=0)o p- f lag

18、=O;。吒 1 se if (pmod i f y =1)ob r eak;p =p-ne x t;mo d ify_num+;o i f (p=L)(modify_n u m=l ；op=L-nex t ;w h il e (p!=L)。第三轮扫描A=0并且M=0的结点 gif ( p -f I a g=0 & p -modify=0)。 br e ak;ap=p-n ext;modify_ n um+; o if( p = L)(。 mod i fy_num=l ；。 p=L-next；8ow hile ( p !=L) 第四轮扫描A=0并且M=1的结点o o|。if(p- f 1 ag!

19、 =0)g p-f 1 ag=O; e 1 s e i f (pm o di f y= = l)o br e a k;。， p = p-nex t ；。 mod i f y _num+ + ;软件：aV C+6.0四、实验设计：本实验包含六种算法，基本内容相差不太，在实现方面并没有用统一的数 据结构实现，而是根据不同算法的特点用不同的数据结构来实现：1、最佳置换和置换所需操作不多，用整数数组模拟内存实现；2、先进先出置换和最近最久未使用置换具有队列的特性，故用队列模拟内 存来实现；3、CLOCK置换和改善的CLOCK置换具有循环队列的特性,故用循环队列 模拟内存实现；4、所有算法都是采用整数数

20、组来模拟页面访问序列。五、数据结构设计：E-国yemianzhihuan classes：七 LinkQueueQ frontQ rear 飞 LNodeQ data“lagQ modifyQ next 飞 QNodeq data q next页面访问序列数组： i n t re f rejsize;/内存数组：in t p h y p hy_size;retu r n 1 ；)void Se t_L L _modify( L inkLi s t&L,int i )。设立链表 L 中的序号为 i 的结 点的mod i fy标志为1;(L inkLis t p ; p = (LinkLi s t

21、) mall o c(s i zeof (LN ode);if (!p) ex i t (-1);叩=L n e x t;if(i=0)。 p -mo d ify = 1;if(i= 1 )6 (p=p-nex t ;p-m o d i fy= 1 ；if( i =2) (d9p=p-next；p=p- n ext;* p-modif y =1;i nt Destr o yLi n k L is t (LinkList & L )g删除链表，并释放链表空间Li n k L is t p, q ;。p 二 (LinkLi s t)ma 1 loc(s i z e o f(LN o de);if(

22、! p) exit(-l);q=(Li n kLi s t)mal 1 oc(siz e of(LNode);if(! q) exit (-1)；p=L-next;whi 1 e(p!=L)(q=p- n e xt;fr e e( p );叩=q;I。f r e e(q);r e turn 1;)/ / / / / / / / / / / / / / III / / / / / / 对队列 的一些操作i n t In i iQu e ue (Lin k Que u e &Q)。 队歹U初始化(Q.front=Q.r e ar=(Qu e u ePtr)malloc( s ize o f(QNo

23、de);if(!Q.f r ont) exit(-l);aQ .f r ontnex t =NULL ； we t urn 1 ；)in t EnQueue (Lin k Qu e ue & Q ,in t e) / /插入元素 e 为 Q 的新的队尾 元素(Queue P tr p;叩二(Qu e uePt r )malloc(sizeo f ( QNode);oif(! p ) exi t (-1);o p - d ata=e；p-next=NULL;oQ.re a r - n e xt=p;Q.rear=p；ret u rn 1 ；)int DeQueue(L i nkQ u e ue

24、&Q, int &e)/ / 若队列不空，则删除 Q 的队头元素，用e返回其值(i f (Q.front = Q .rear) rctu r n -1;Queue P t r p;p=(Qu e uePtr) mallo c (siz e of( Q Node)；，p= Q. f ro n t - n ext;e =p-da t a;Q.f r ont-nex t = p next;i f (Q . rear= p )Q. r e a r =Q.fron t ;free (p)； r eturn 1;Ib ool S e arch Q u e ue(Li n k Queu e &Q, int

25、e,int &i) 寻找队列 Q 中结点 da t a域等于e的结点，并用i返回其在Q中的位置(i= 1 ;if( Q . f ront=Q. rea r ) e x i t(-l );Que u ePt r p；p =( Q ue u ePt r )m a 11 o c ( s ize o f (QNod e );i f ( ! p) e x it(-l)；p=Q. front n ext;。/p指向队列的第一个节点(非头结点)w h i 1 e(p!=NULL & p-data! = e ) (0p=pne x t;o i +；o。i f(! P)o r e tur n f a Ise;e

26、 tur n t r ue;1i nt DelMid_Queue(Li n kQu e ue &Q,in t &e)。/删除 Q 的中间元素，并用 e返回 其值if( Q . front=Q.rear) r e turn -1;Que uePt r p；叩二(Qu e ue P t r)mall o c(siz e of ( Q Node);if ( ! p) e x i t(-l);p=Q .f r onl-nexl; e =p-next-dat a ;p-ne x t=p-ne x t -n ext;r et u r n 1;int De s tr o yQue u e (L ink Q

27、ueue &Q)的删除队列并释放空间(owhile (Q.fron t )(s Q.rear= Q .f r on t - n e x t；Mee (Q. fro nt)；Q. front = Q.rear;)or e t u rn 1 ；)/ / / / / / / / / / / /int max 1 (in t a,int b , int c)返回 a , b,c 中的最大值if(ab) a=b;i f (a c ) a =c;return a；int getnum(int a , i n t b)。/用b返回元素a在被引用数列中的下一个位置for (;bref_siz e ； b+)。

28、 i f ( a =ref b ) break;)re t urn b ;)v oidOR A()/ / /最佳置换算法IS e t C o ns o leTextA t t r i but e (GetStdHan d le( S T D_OUTPU T _HA N DLE), FOREGROUNDN TEN SITY | F 0 REGROUND_ RED);co u tv V n* * * * * 秘*55c最佳置换算法* * * * ”e n d 1;S e tCons o 1 e T e xt A ttri b ute(Ge t StdH a n d le ( STD_OUT P U

29、T_HANDLE),FOREGROUN D JNTEN SITY | FO REGROUND_INTEN SI T Y);/设立字体颜色为白色ftint i,j；in t num_0, n um_l,num_2, num_max；int i n te r r u p t _num= 0 ；/ / n u m_0=num_l=num_2= 0 ;for(i=(); i p h y_size;i+) 前三个数进内存& ph y Li=refi；for (i= 0 ； iph y _ s i ze;i+)。/输出最初的三个数cou t p hyi n t;cou t en d 1 ；o f or (

30、 j = p hy_ s iz e ;j / / 若产生缺页中断，选择最久不会被使用的页被替换00 |on u m_0=gctnum( p hyO, j + 1 );。n um_1=ge t num( p hy 1 ,j+l);。 n um_2=ge t n u m(ph y 2 ,j+l);“ n um_max = m a x 1 (n u m_0, n um_l,num_2)；if(num_ 0 = n u m_max)。叩 hyO = r e f j;else。“ f (num_l=num_ma x )。Phy 1 =re f j;。照 Ise。f ( n um_2=n u m_ma x

31、 )。phyl 2 =r e f j;。 i n terrupt_n u m+;o 。 S etCons o leTex t Attribut e (GetSld H and 1 e(STD_OUTPUT_HANDLE),FOREGROU N DNTE NS I TY I FORE GROUND_BLUE); 设立字体为蓝色)c outvv进入页：r e f jendl;ofor (i=0； iphy_size;i+) 。/输出内存状态“，cou t p hgc outend 1 endl;。S etCon s oleTextA t t ri b u te(GetStdH a ndle ( S

32、 TD_OUTP U T_HA N D LE), FOR EGROUND_ I NTENSITY | FORE GROUND_GREEN);c o ut 最佳置换算法缺页中断次数:n i n t e r r upt_num e ndl;/以绿色字体输出中断次数。i ntcr r uptO=(f 1 oat)intcr r up t _ n um / 2 0.0)*100. 0;)/ / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /vo i d RAND() 。 / / / /置换算法Se t C o n

33、s o leT e xtAl t r ib u t e (GetS t dHandle( S T D_O U TPU THANDLE) ,F O REGROUND_ I NTENSITY | FOR EGROUND_RED)；coutn* * * * * * * 芳*55s置换算法 * * * * 火* * endlSetC o nsole T ext A ttri b u te (GetS t d Han d le(STD_OU T P UT_HANDLE ) ,FOREGROUND, I NTENS I TY | FOREGROUNDNTENSITY );i n t i, j , t em

34、 p ;i n t i n t errupt_num=0;0/num_ 0 =num_l=n u m_2=0;Sleep (1 0 0 0);s r and(t i me(NULL) );。“/ 设立时间种子 f or(i=0； i ph y _siz e ； i + + )8Phy i = r e f i ；for( i =O;iph y _siz e ； i+)c ou t phy i 11 t；cout e n d 1;for ( j =p h y_si z e ;jr e f_size； j + +)e t C o n so 1 e T e x tA t t r i bu t e (G

35、et S t d Han dle(S T D_OUT PUT_H ANDL E ), F0REGROUNDJNTENSIT Y | FOREGROUNDNT ENSITY)；if(! (ref j = P h y 0 llreffj =phy 1 I |re f j = p hy2 )/产生缺页中断，选择页被替换00 |。 temper a nd()%3;/ / cout t empendl；8Phy temp =refj;inte r rupt_num+;SetCon s oleTextA t t r ibut e (G e t StdHandle( S TD_ OUTPUT .HANDLE

36、) , F OREGROUND_ I NT E N S I T Y | FO R E GRO UND _BLUE);)oco utV“进入页:“VrefjvVendl;for(i= 0 ;ip h y_size;i+ )。 coutphyi tu；。couten d 1 e n d 1 ;Se t Conso 1 eT e xtAttri b u te( G e tStdHandle(S T D_OUTPUT_H A NDLE),FOREGROUNDNTENS I TY I FOR EGROUND_GREEN);coutvv置换算法缺页中断次数:vvint e it u p t _numen

37、d 1 ；。/ /以绿 色字体输出中断次数4interr u p tl =(flo a t) interrupt_n um/20. 0 ) *100. 0;)/ / / / / / / / UH HU / / / / / / / / / / /void FIFO ()(S e tConso 1 e T e x t A ttri b ut e (GetStdHa n die (STD _O U T P UTH A N DLE), FOREGROUND JNTENS I TY I FOREG ROUND_RED);c o u t n* * * * 先进先出置换算法* * * * * * * * e

38、 ndl：o S e tConso 1 eText A ttribute(Get S tdHa n die ( S T D_O U TPUT_HANDLE),FOREGROUNDNTENSITY | FOR EGR0UNDJNTENSIT Y)；LinkQueue L;QueucP t r p;i n t i,j,e,m;int i n tcrru p t_n u m= 0 ;I nit Que u e(L);fb r ( i =0;i next;f or(j=0; p !=NULL &jdat a n e xt；coute n d 1 ;for(i=phy_s i ze;iref_size;i+)(S e tConsoleT e xtAtt r i b ute(GetStdH a ndle(STD