《2023年面置换算法实验报告.docx》由会员分享，可在线阅读，更多相关《2023年面置换算法实验报告.docx（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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算法，最近最久未使用算法的性能略好，我们测试一、实验目的：设计和实现最佳置换算法、随机置换算法、先进先出置换算法、最近最久未使用 置换算法、简朴C 1 o ck置换算法及改善型C 1 ock置换算法;通过支持页面访问 序列随机发生实现有关算法的测试及性能比较。二、实验内容：虚拟内存页面总数为N,页号
6、从。到N-1 物理内存由M个物理块组成页面访问序列串是一个整数序列，整数的取值范围为。到N - Io页面访 问序列串中的每个元素p表达对页面P的一次访问页表用整数数组或结构数组来表达符合局部访问特性的随机生成算法.拟定虚拟内存的尺寸N,工作集的起始位置p,工作集中包含的页数 e,工作集移动率m(每解决m个页面访问则将起始位置p +1 ),以及 一个范围在。和1之间的值t;1 .生成m个取值范围在P和P + e间的随机数,并记录到页面访问序 列串中；.生成一个随机数r, 0 W r W 1;2 .假如r 1,则为p生成一个新值，否则p = (p+ 1 )mod N;.假如想继续加大页面访问序列串
7、的长度，请返回第2步，否则结束。三、实验环境：操作系统：Window s 7软件：sV C+6.0的数据规模相对较小，相信假如采用更大规模的数据,其优势会更加明显。当从课堂上我们知道要想在实际的应用中实现本算法，用软件的方法速度太慢， 影响程序执行效率，假如采用硬件方法实现，则需要增长大量的硬件设备。4、先进先出与clock算法的性能基本相同这是由于两种clock算法遍历链表采用的就是FIFO的方法，而改善的c 1 o ck 算法相比于简朴clock算法的优势重要体现在会根据是否被修改善行选择，以减 少写回所花费的时间。十、实验总结：这次实验总体难度不是很大，需要实现的算法数目虽然不少，但基本
8、思绪较为 相似，因此实现起来也并不是十分困难。通过完毕这次实验，除了加深了我对几 种策略的理解，锻炼了我的编程能力，另一个巨大的收获就是了解了一些生成测试 数据的方法。为了使我们的测试数据更贴近现实，我们引入了工作集的概念，并 根据实际使用情况的特点设计出尽也许符合实际情况的随机数生成方案。通过阅 读课件再加上自己的理解，我了解了老师的设计思绪，感觉这个思绪极其巧妙，设 计中用到的方法和体现出的很多思想值得我们学习。十一、程序清单：# in c 1 u d e i nclu d e# in c ludeinclude# i nclude using nam e s pace std;de fi
9、ne ref_s i z e 20# define p h y_si z e 3i n t reflr e f_size;float i n terrupt6= 0 . 0;/ i nt ref r e f _s i z e =0)；int p h yphy_size;/ / / / / / / / / / / / / / / / / / / / / /vo i d s et_ ran d_n u m()。/ /产生具有局部特性的随机数列(。c out页面访问序列:vend 1 ;int p= 12;n t e=4;i nt m=4;int i = 0 ;int j= 0 ;int n= 0
10、;o d o u b 1 e t =0.6;int t emp;fo r (i=0;icoutr e fj fo r (n=0;n4; n+)Slee p (1000* n )；osra n d (time(NULL);do u ble r= (do u b 1 e)( r and () %10) / 1 0. 0 ;。/ c outrendl；o if( r t) p=p+ i n t(10*r); e 1 se。叩=(p+l) % 2 0 ;o f or(i=0； inext=L;L- f lag=0;return in t Exch ang e _LNo d e(Link L ist &
11、L ,int e, i nt i) /将链表 L 中序号为 i 的结点替换为内容为e的结点if(L- n e xt=L) exit (- 1 );L i n k L ist p,q；i ntj=O;叩二(L i n k L i st)mal 1 o c(si z eof(L N od e )；q= (Lin k L ist) m a llo c (sizeo f (LNode);qdata=e;P=L;for ( j =0； ji;j + +)使P为待更换结点的前一个结点，故应保证，删除第 一个非头结点时i=0,以此类推 p = p -ne x t ;qne x t =p-ne x t nex
12、t；W-nexl=q；阳- f 1 ag=l;M设立新结点的访问位为1q-mo dify= 0 ;“/设立新结点的修改位为0r e t u rn 1;)i nt In s ert_ L Node(LinkList &L, i n te)在循环链表中插入新的结点，从L头结点开始依次向后插入(i nk L is t p, q ;p=(LinkList)m a lloc(siz e of( L Node); q = ( L i nkLi s t )malloc( s i z eof (LN o de);q- d ata=e；oq- fl a g=l? 设立新结点的访问位为1o q m o d ify
13、=O；。/ /设立新结点的修改位为0o P =L；whi 1 e ( p - n ex t ! =L)。( P =p-nex t ；)p-ncxt=q;q-nex t = L;retu r n 1 ；)boo 1 Sear c h _LinkL i st (Li n kList &L,in t e,int &i)找到链表 L 中内容为 e的结点，并用i返回其位置，i=l表达第一个非头结点，依次类推(i=l；if (L- n e x t=L) e x i t (-1);Lin k L i st p ;p=(LinkLi s t)malloc(si z e of (LN ode);if(! p)
14、ex ip=L- n ex t / /p指向链表的第一个结点(非头结点)while(p!= L & p -data!=e)(ocp=pnext；i+；oi f (p=二L)。/没有找到符合规定的结点8r e turn false；retu r n (ru e;)void Sea r ch_LL_ F lag(L i n k L ist &L, in t &i) / / 用 i 返回第一个 fi ag为0的结点的位置,i=l表达第一个非头结点，以此类推i= 1 ;LinkLi s t p ;p=(Li n kList) mal 1 oc ( s izeof (LN o de);f (! p )
15、e x i t (-1);p=L- next；whil e ( p -flag!=O)p- f 1 ag=0； / /修改访问标志位为0p=p-next;。i f(p=L ) g跳过头结点ep=p_ncxt;。i +;，if(i=4)/ /跳过头结点。i =1;/ /ret u rn 1;void S et_L L_F 1 ag(LinkList &L, i nt i) 设立链表 L 中的序号为 i 的结 点的flag标志为1;Li n k L i st p; p =(LinkList)mall o c( s iz e of( L N o de);i f(!p) exit(-l);。p =L
16、n ext;if (i=l)。叩-fl a g=l;aif (i= =2)o (op=p-next;8 p f lag= 1;)i f(i=3)o p= p -next;wp=p- n ext;p- f la g =1;)int Searc h _LL_ModifyClock(L i nkList &L,in t &modif y/ 找到改 善的CLOCK算法所需要淘汰的页，用modify_num返回其位置modif y _num= 1 ;if(L-ne x t=L) e x iLinkL i st p;p=(LinkLis t )m a llo c (si z e of(LNo d e);i
17、f (!p) e x it(-l);p=L-next； g/p指向链表的第一个结点(非头结点)wh i le(p!=L)。第一轮扫描A=0并且M=0的结点 (。i f(pfl a g=0 & & p -m o d i f y = 0 ) obre ak;/ /找至Uop=p-n ext;modi fy_num+；)M f (p =L)mo d if y _n u m= 1 ;。 p =L-n e xt；while(p!=L) 1/第二轮扫描A =0并且M=1的结点，同时修改访问过的结点 的访问位为()(if(p-fla g !=0) p-f 1 ag=0;oe 1 s e i f( p -mo
18、dify= 1 )p = p- n ex t ;modify_num+;p = p- n ex t ;modify_num+;。brea k ;00if(p=L)6 。 modi f y_ n um=l ；叩=L-ne x t;。while (p!=L)。/第三轮扫描A=()并且M=()的结点 。if(p- fl a g=0 & & p-mo d ify= = 0)8b r eak；。叩=p n ext：o m o di f y_ n um+;00 if ( p =L)6 (。mod if y _num=l;oop=L-n e xt;while(p!=L) 第四轮扫描A=0并且M= 1的结点。
19、if (p-fl a g ! =0)g epf 1 a g= 0 ;o 。 el s e if (p-mo d i f y= 1)bre a k ；。 o p =p-next;modify_ n um+;四、实验设计：本实验包含六种算法，基本内容相差不太，在实现方面并没有用统一的数据结构实现，而是根据不同算法的特点用不同的数据结构来实现：1、最佳置换和随机置换所需操作不多，用整数数组模拟内存实现；2、先进先出置换和最近最久未使用置换具有队列的特性，故用队列模拟内 存来实现；3、CLOCK置换和改善的CLOCK置换具有循环队列的特性，故用循环队 列模拟内存实现；4、所有算法都是采用整数数组来模拟
20、页面访问序列。五、数据结构设计：臼厚yemianzhihuan classes j-i 七 LinkQueue q front q rearm 七 LNodeQ data“ flag q modify Q next-QNode q data next页面访问序列数组：int r e f r e 匚size;内存数组：in t phyp h y_size；队列数据结构定义：typed e f struct QNod e。定义队列数据结构00ret u rn 1;)vo i d Set_LL_mod i fy (Link List &L, int i) / / 设立链表 L 中的序 号为i的结点的
21、modi fy标志为1 ;(L i nkLi s t p;叩二(L inkLi s t )mal 1 o c(sizeof ( L Node);f (!p) exi t ( 1);p=L-next；if (i=0 )opmod i fy = 1;if(i=D(gp=p-ne x t；pmod i fy = 1;if(i=2)p= p -next；p= p -n e xt;p-modify=l;0)int Des troy Link L ist (Link L ist & L )/删除链表，并释放链表空间LinkLis t p,q；p=(Lin k Li s t)ma 1 loc(size o
22、f (LNod e );o i f(! p ) exi t (-1);oq= (Lin k List) mal 1 o c(s i ze o f( L Nod e );oif (! q ) exi t (-1)；p= L -next;wh i le(p!=L)(叫= p-ne x t;ofree (p)；。 p= Q ; f r e e( q );retu r n 1;)/ /nmu/ / / / / /对 队列的一些操作int InitQ u e u e(Li n kQu e u e &Q)/队列初始化(oQ.f r o n t=Q. rear=(QueuePt r ) ma 1 Io c
23、(si z eof ( Q Node);if(!Q. f r ont) exi t (- 1 );Q.f r o n t -next=NULL;e tu r n 1 ；)i n t E n Q u eue( L i nkQu e ue & Q , i nte / / 插入元素 e 为 Q 的新的队尾 元素(aQueueP t r p；p=(QueuePtr) m alloc(sizeof(QNod e );if (! p) exit(- 1);p-data=e;p-n e xt=NULL;oQ.rear n e xt=p;Qrear=p;r et u rn 1;)i n t DeQueue(L
24、 i nkQueu e &Q,int & e )。/ /若队列不空，则删除Q的队头元 素，用e返回其值(i f (Q.front= Q . rear) return -1;oQ u e u ePtr p；叩二(Queu e Ptr)malloc(si z eo f ( QNo d e )；p=Q.front-nex t ；e =p-d a ta;Q.fro n tn e x t = p -next；i f(Q. r e ar=p)o Q. r ear=Q.front；free(p);return 1;Ibool S e arch Q ue u e(L i nkQu e ue &Q, int e
25、 ,i n t &i) 寻找队列 Q 中结点 da t a域等于e的结点，并用i返回其在Q中的位置(i=l;if(Q.front=Q.rear) exit(-l);Q u eu e Ptr p；。P =( Q ueueP t r )mall o c( s izeof(QNo d e);if(!p) ex i t ( 1);p=Q.fronl-nexi; /p指向队列的第一个节点(非头结点)while(p!=NULL & pdat a !=e)(p = p - n e xt;o i+；)if(! P)ret u r n f alse;retu r n t r ue;1in tDelMid_Que
26、ue(LinkQueue &Q,int & e ) 删除 Q 的中间元素，并用e返回其值i f(Q.fro n t =Q. r e ar) r e turn - 1 ;QueuePt r p；叩二(Q u eue P t r )mall o c( s i zeo f (QNo de);oif (! p ) ex i t (-1 )；p =Q. frontne x t ;e= p -next-da t a;p-nex(=p-n e x t-n e xt;ret urn 1 ：i nt Des t royQueue( L i n kQ u eu e &Q) g。/ / 删除队列并释放空间 (dw
27、h ile(Q.front) gQ. rea r =Q.fr o n t-next；o f ree(Q. f ront);Q f ront=Q.re a r;)re t urn 1 ;)/ / / / / / / / / / / / / / / / / / / lllllllllllllllllllllll / /in t maxi ( i nt a,i n t b, i nt c)。/返回 a , b , c 中的最大值 i f(ab) a= b ;o i f (ac) a=c;return a;i n t ge t num (int a, int b) / /用b返回元素a在被引用数列中的
28、下一 个位置(for(;b r ef_size； b+)(if(a= r ef b )。brea k ；)re t urn b;)void ORA ()/最佳置换算法(S e t C ons o leT e x tAttr i b u te(GetStdH a n d le ( ST D _ 0 U TP U T_HANDLE),FOREGROUNDNTENS I TY |FOREGROUND_RE D)； 3 c outnn* * * * * * * * * 最佳置换算法 * * * * * * * * *n dl，SelConsoleTextA t t r ibut e (GelSt d
29、Han d 1 e(S T D _OUTPUT_H A N DLE), FOREG ROUND_INTEN S ITY | FOREG ROUNDN TENS I TY);设立字体 颜色为白色 o i nt i , j;int n um (),num 1 , n um 2,n u m max ；int interrupt_n u m=0；/num_()=num_ 1 =num_2=0;ofo r (i=0;i p hy_ s ize； i+)。前三个数进内存ophy i J=re f i;for ( i =0; i phy_size;i+ + )。输出最初的三个数coutphyint;c o
30、ute n dl; f o r ( j =phy_ s ize;j r ef_ s ize； j +)(aSet C ons o le T extAt t ri b ute(Ge t Std H and 1 e ( S TD_OUTPUT_ H A NDLE),F 0 REGROUNDJNTENSITY | FOREGR 0 UNDJNTENS I TY);。i f(!(ref j = P hyO | refj=phyl | I r e f j = =phy2) 若产生缺页中断，选择最久不会被使用的页被替换6 。 n u m_ 0 =getnum( p h y 0 ,j+l )； num_l=
31、g e tnum (phyl j+1);o num_2=g e tn u m(phy 2 l,j+1)；。 n u m_max = m a x 1 (num_0,num_ 1, num_2);。 i f (num_O=num_max)ph y 0= r ef j ;。e 1 se。 i f (num_ 1 = n um_max)。phyl=ref j ;。e 1 s e。oif( n um_2 = = num_ma x )。p h y2 =refj;。 i nlerr u pt-n u m +；。Se t Consol e TextAttri b u t e ( Get S tdHandle(
32、S T D_OUTPUT_HA N DLE),FO R EGROUN D JNTENS I T Y | FOREG R 0UND_BLUE);设立字 体为蓝色ocout”进入页：VreffjVendl；for (i=0; i p h y_si z e; i +)。/输出内存状态co u tp h yiH t ;皿o couten d 1 en d 1 ;SetConso 1 e T e x tAt t ribu t e( G et S td H andle ( STD_OU T PUT_H A NDLE) ,FOREGROUND_INTENSITY|FOREGROUND_GREEN)；cou
33、t V V”最佳置换算法缺页中断次数：vi n lerru p t_num Vendl；。 以绿色字体输出中断次数i nterruptO= (fl oat)inte r ru p t_ n u m/2 0 .0)*100.0;)/ / / / Illi / / / / / / / Illi / I III / / / / / / /111/1/ / / / / / / UH / /void RAND ()。/ /随机置换算法(S etC o n s oleTex t At t ri b u te (Get S t dHandl e (STD_0 UTPUT_H A N DL E),FOREGR
34、OUND JNTEN S I T Y | FOREGROU N D_ R E D );c o u t Vn* * * * * *随机置换算法* * * * * * *endl，fet C on s o 1 eTextAttri b u t e(G e tSt d H an d le(STD_ 0 UT P UT.HAND L E),FOREGROUN D_ I NTENSITY| FOREGROUNDNTENSITY);int ij, t e mp;int i n t err u pt_num=();/num_ 0 = n u m_l=num_2=0；oS 1 ee p ( 1 000)；s
35、ran d(time (NULL)?/ / 设立时间种子 afb r ( i =0； i p h y_ s ize;i + +)。 phyi=refi;for( i =0; i ph y _s i z e;i+) coutph y in t H;c o u t e n dl;f o r( j =phy_ s i ze; j re f _size;j+)Uoo S elCo n s o leT e x t A t tr i but e (G e tS t dHandl e (STD_ O UTPUT.H A NDLE), FOREGROUN D_ I NTE N S I TY | FOR EGR
36、OUNDJNTENSITY);“f (! (ref |j=phy 101| I r e fjj = =phy 1 J | r e f j=phy )产生缺页中断，随机选择页被替换od 。 temp= r a nd()% 3 ； g/c o uttempe n dl; p h y temp = refj；o oin t err u p t_num+;。 S e tConso 1 e T e xt A t t ribut e (Ge t St d H a ndl e (ST D_OU T PUT_H ANDLE),FOREGROUND. I N TENS I TY | F OREG R 0 UND
37、_B LUE)； ocouKV进入页： r e f j end 1 ；o。f o r (i=();iph y _si z e;i+ + )。coutph y i tM; co u t e n dlend 1 ;SetCo n s o 1 eTex t Att r i b ute (Get S tdHan d 1 e(STD_OU TPUT_HA N DLE), F OREG R OUND_ I NTENSITY | F 0 REG R OUND _GREEN);o c o u t随机置换算法缺页中断次数：vvinterrup t _ n umMendl；/ /以绿 色字体输出中断次数inter
38、r u p t 1 =( (float)int e rrupt_num / 20.0)*100.0；。/ / / / / / / / / / / / / / / / / / / / / / / / / / / / / /void F I FO()oSe t C o nso 1 eT e xtA t t ribute(Ge t S tdHa n d 1 e (STD_OUTP UT_HANDLE), FOREG ROUNDJNTENSIT Y | FOREGROUND_RED);coutn* * * * * * 先进先出置换算法 * * * * * * *” ver)d.Set C on s o
39、leTex t Att r ib u te(Ge t Std H a n d le( S TD_OUTPUT_ HAND LE),FOREG ROUNDNTENSITY I FOREGROUNDJNTENSITY);i nk Q ueue L;Que u ePt r p;。i nt i, j, e ,m;。i n t i nte r rupt_ n um=0;InitQue u e(L);for (i=0; i n ex t ；f o r(j=0;p!=NUL L & jdatan ext;。o utendl；of o r(i=phy_size； ire f _sizc;i+)6 (Set C onsoleTextAt t r