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

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

1、实验编号4名称页面置换算法模拟实验目的通过请求页式存储管理中页面置换算法模拟设计，以便:1、了解虚拟存储技术的特点2、掌握请求页式存储管理中页面置换算法实验内容与环节设计一个虚拟存储区和内存工作区，并使用FI F0和LRU算法计算访问命中率。程序设计,，先用sr a nd()函数和ran d ()函数定义和产生指令序列,然后将指令序列变换成相应的页地 址流，并针对不同的算法计算相应的命中率。程序1i n clu d e “Windows 版，随机函数需要,GetCurr entProcessld()需要/#in c lude / / Linux 版，随机函数 s r and 和 rand 需要

2、# i n c lude /p r i ntf ()需要d efine TRUE 1# d e fine FALSE 0#defin e INVALID -1#def i ne NULL 0。f ree p fh e ad= f r e e p f _ h ead n ext;00 else3 pm t pag e i. counte r =1；e if(i% c 1 e a r_p e r i od= = 0)s for ( j =0; j tota 1 _vp;j+)叩mt j . cou n te r =0;)printf(11 NUR： %6.4 f 1 o at)NoP a g e

3、C o u n t/32 0 )；实验结果（写出结果，截图也可）请插，.江面长度。九16输出随机数：许输入分配的物理块水26：41：PIFO页面置换2：LRU页面置换3：OPT页面置换请选择页面置换算法，FI FOi 2法页面置换情况如下:33000636005365073657116 5 75不缺页9 19 5 70 19 0 72 19 0 21不缺页6 6 9 8 24 6 4 0 26不缺页16 4 127 6 4 1 73 3 4 1 700 0 5 5 5 0 9 0 3 3 3 3 3 13 s 5r?l缺页次数, 13缺页率，0.81257F不缺页 9 19 5 70 19 5

4、 02 9 5 02 9 102 6 102 6 14不缺页不缺页F7 7 6 1 4F7 7 6 1 43 7 6 13缺页次数,13缺页率，。.8125OPT苴士苦心府况如下:3657159021S4S1F730 0 0 7 70 0 5 5 5 0 0 0 03 3 3 3 17 7 7 7 79 0 2费4页页页46 6 6赧6静6il不不1不不不3缺页次数，I缺页率, 0.625总结（收获，未实现的环节）这次操作系统课程设计，让我们对操作系统有了更深的结识，一方面操作系统是一管理电脑 硬件与软件资源的程序,同时也是计算机系统内核与基石。操作系统是一个庞大的管理控制 程序，大体涉及5个

5、方面的管理功能:进程与解决机管理、作业管理、存储管理、设备管理、文献管理。我们这次课程设计的题目是页面置换算法, 是属于存储器管理。 在进程运营过程中,若其访问的页面不在内存而需把它们调入内存， 但内存以无空闲空间时，为了保证该进程能正常的运营,系统必须从内存中调出一页程序或 数据送磁盘的兑换区中，但应将哪个页面调出,需根据一定的算法来拟定。通常，把选择换成 页面的算法称为页面置换算法。通过本次课程设计，我们对页面置换算法的了解更加的深 刻。重要有以下置换算法： OPT （最佳置换算法）、FIFO （先进先出置换算法）、LR U（最近最久未使用算法）。每种算法都有各自的优缺陷，OPT算法是实际

6、中不能实现的，但是 可以运用该算法去评价其它算法；FIFO算法与进程实际运营的规律不相合用，由于在进程中, 有些页面经常被访问;LRU算法是根据页面调入内存后的使用情况进行决策的。 在这次课 程设计中，碰到了一些困难，例如怎么实现各种算法，如何进行函数调用及对数据的限制操 作等,在碰到这些困难的时候，我们会去查阅资料，仔细看书，尝试用不同的方法解决，在 各种方法中选择一种最佳的方法，有的时候会碰到不知道如何实现的函数，我们会查看MS DN,这次是用的C+语言做的，每一步都是自己独立完毕的，这次课程设计我最大的收获是 学以致用，通过这次设计我们看到了自己学习的能力，我们相信在以后的学习中，会更加

7、的 努力上进。最后，还非常感谢辛劳的操作系统老师，一方面，由于他辛劳的为我们讲解操作系 统这门课，让我们对操作系统有了一定的了解，为这次课程设计奠定了良好的基础，另一方 面,还要感谢他认真指导我们的这次课程设计，给了我们这次总体运用自己能力的机会，我们 坚信:只要功夫深，铁杵磨成针。# d e fine t o t a 1_in s traction 3 20。/ /共 3 20 条指令d efine t otalvp 32。虚存页共 32 页# de f ine cl e a r_peri o d 50。/ /访问次数清零周期typ e d e f s t rue t / /定义页表结构类型

8、(页面映射表P MT)“nt pn, pfn, c o u n ter, time;/页号、页框号(块号)、一个周期内访问该页面的次数、 访问时间PMT；PMTpmt3 2;typed e f struc t p fc_s t r u ct 页面控制结构“n t pn, pf n ;ostr u c t pfe_str u ct *n e xt;pfc_t y pe;P fc_typ e p fc32;pfc.type *free P L h ead,*busyp f _ h e a d, * busypf_tail;/ 空闲页头指针，忙页头指针，忙页 尾指针int N o Pa g eC o

9、 unt; 缺页次数i nt at o tal_inst r uc t ion ;/指令流数组i n t pag etota 1 inst rue tion, offset total_i n s true t ion;/ / 每条指令的页和页内偏 移voi d in i tia 1 i ze( i n t );void F I FO( int);/先进先出v o id LRU( i nt);最近最久未使用void NRU( int );最近最不经常使用* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *main()* *

10、* * * * * * * * * * * * * * * * * * * *v oid main()i nt i,s;V / s r and (10* getp id() ;/用进程号作为初始化随机数队列的种子。“Linux版6s r an d (10* GetC u rren t Proc e s s I d()； 用进程号作为初始化随机数的种子/ /Wi n do ws版0。s =rand()%320； / /在0,319的指令地址之间随机选取一起点mfo r ( i = 0 ;i t o tal_ins t ru c ti o n ； i+=4) 产生指令队列oif (s319)叩 r

11、 in t f(when i= = %d,e r r o r, s =%d n n, i, s )；exi t (0);6 )8a i =s； 任意选一指令访问点m。(将随机数作为指令地址m)。a i+l=ai+l； / /顺序执行下一条指令-ai+ 2 =r a nd()%(s+2);在0,m+l的前地址之间随机选取一地址，记为ai+ 3 =ai+2+ 1 ;顺序执行一条指令。 s = a i+ 2 + (in t )rand()% (320-a i + 2 );/在m- 3 1 9的指令地址之间随 机选取一起点mo i f(a i +231 8 )| ( s 3 1 9) ) printf

12、( H a% d + 2 , a number wh i c h is： %d an d s 二%dn i , ai+2, s);。fo r (i=0;i t otal_in s tructio n ;i+)/ / 将指令序列变成页地址流P age Li =a Li/1 0 ;offseti=ai% 10;0)f or(i=4;iv=3 2;i+) /内存块分别为4块、5块、.3 2块时的命中率p r intf(u%2d p age f ram e s n , i );oFIFO( i );计算用FIFO置换时，有i个内存块时的命中率LR U;最近最久未使用NRU( i );/最近最不经常使用

13、 叩rintf(“n);) /*1* I III *1*1* *1* I IiI * t* III|I/*不* *半*牛大不不不不不不不不大大拳拳大不举不军大牛不大不不半半半不大*不半不不不半半不大半不* *不大不不*不不不不不不不 * * *i n i t i a liz e ()形参：内存块数功能：初始化* * * * * * * * * * * * * * * * * * * * Ivo i d i n i tia 1 ize(int t o t a 1 _ p f )/ /初始化相关数据结构，形参tot a 1_ p f是用户进程的内存页面数(n t i;NoP a geCount=0

14、； /缺页次数,初始化为0for(i = 0； i to t a 1 _vp； i+ +) 3 pm t i.pn=i;/ /填逻辑页号p mti.pfn=IN VALID;/物理页面号为-1oo p m t i. c o unt e r=0;置页面控制结构中的访问次数为0叩mti .time=- 1 ; 置页面控制结构中的时间为-1f or(i= 0 ; i 7，7，7* 7* 7* 7，*! ! 7 7 7 7 7，7，7 7* I /rj* rj*/void FIFO(i nt t o tal_pf) 形参t otal_ P f是用户进程的内存页面数in t i;pfc_ t ype *

15、p;initia 1 iz e ( t otal_ P f)；初始化相关数据结构ebu s y p f _he a d=b u sypf_ t a i 1=N UL L ;for(i=0; i next；e o p mt busypf_head- p n .pfn = INVAL I D;“ freepf_h ead=b u s y pf_hea d ;/ /释放忙页面队列的第一个页面ogfree p fL h ead-nex t =NULL;e b usypf_h e a d =p;p =f r eepf_ h e a d- n e x t;按F IFO方式调新页面入内存ofree p f

16、_he a d -n ext = NULL;fr e e p f _headpn=p age i;ooopmtpag e i. pfn=fre e pf_hea d -pfn；a i f(bu s ypfLt a i I=NU LL) b usypf_head=busypf_tail= f reepf_he a d;8。e Is e 8obusypf_ t ai 1 -nex t = f reepC head； /fr e e 页面减少一个 busy pfLtail=f r e ep f _h e ad;bbb 肃 r ee p f_h e a d = p ;叩 r i n t f (n FI

17、FO： %6.4f;l-( f loa t )NoPageCount/3 2 0);)/* * * * * * * * * * * * * * * * *1* *2* I *1* *1*.R .Rrj* 门卜,.、.、 7.R .R 卜LRU算法(最近最久未使用)形参:内存块数输出:命中率* * * * * * * * * * * * * * * * * * * */vo i d LRU(in t t o tal_pf)/ /形参total_p f是给用户进程的内存块数“nt min,m i nj, i ,j, pr e sent_time;ini t i a li z e(total_p f

18、 );p r esen t _time=0;s f or(i=0;itotal_instr u ct i on;i+) oif(pm t pag e i .pfn=INVALID)页面失效8。N oPage C o u n t+；。 i f( f r e epfLhe a d = =NULL) /无空闲页面g min=32 7 6 7;“ f o r (j =0;j p mt|j .time&pm t j.p f n!= I N VALI D ) 。 min=pmt j .t i me;6minj=j;00 freepf_head=&pfc p mt m i nj. p f n;腾出一个单元。

19、 p mtminj .pfn= I N VALID;o 。p mtminj ,t i me-1;e 。f reep f _hea d n ex t =N U LL；eg 3叩m t p a g ei .p f n =f r e e p f_ h ead p f n;有空闲页面，改为有效bopmt p agei. t ime=pr e se n t _tim e ;。 fre e pjhead= f re e pjhe a dnex t ;/ / 减少一个 free 页面-Is e pmtp age i.tim e =p r e s e nt_t i me; / /更新该页面的访问时间（并非真的

20、时间，而是循环次数，每执行一条指令，时间加1）p res e nt_ t im e + + ； 当前时间加 1）叩ri n t f( LRU: %6.4f n , 1 - ( f loa t) NoPa g eCou n t / 320);I * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *NRU算法(最近最不经常使用)形参:内存块数输出:命中率* * * * * * * * * * * * * * * * * * * * * * * * * * * * /void NRU(in t tot a 1_ p f)“

21、nt i,j,dp,c o nt_ f lag, old_dp;。i n i tialize(tot a l_p f );of o r ( i =0； ito t al_ i nstruction; i +) i f (pmtpagei. p fn= = INVALID)/ / 缺页oooNoPageCount+;8oi f (f r ee p f _hea d =NU L L) 无空闲页面con t_fl a g =TRUE;ol d _dp=dp；while (co n t_f 1 a g )8bg i f (pmtdp.c o un t er=O& p mt dp.pfn! =INVALI D)。c o n t _flag=FA L SE；ggelse 000000odp+；if (d p = t ota 1 _ v p)0 dp=0;i f (d p =ol d _d p )f or ( j = 0 ； jnext=NULL;pmt P a g e i . p f n =fr e epjh e ad-p f n ;