2023年操作系统实验报告面置换算法模拟.pdf

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

1、力U 4H 2总实 验 报 告（2023/2023学 年 第1学期）业课程名称操作系统原理实验名称实验6：页面置换算法模拟实验时间20 2 3年12 月 1 0日指导单位软件工程系指导教师杨 健学生姓名班级学号学院（系）软件工程系专计算机软件与服务外包一、实验目的实验名称实验l：L i n u x操 作、使 用、编 程 与 进 程 创 建指导教师杨健实验类型实验实验学时2实验时间2 02 3.1 2.101 .通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。2 .掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。3 .通过对几种置换算法页面的

2、比较，来对比他们的优缺陷，并通过比较更换频率来对比它们的效率。二、实验环境（实验设备）W i n do w s 2 0 2 3V i s u a 1 S t u di o三、实验内容设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换：1 .先进先出的算法（FI FO）2 .最近最久未使用算法（L R U）3.最佳置换算法（O PT）实验分析在进程运营过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程可以正常运营，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来拟定，算法的好坏,直接影响到系统的性能。一

3、个好的页面置换算法，应当有较低的页面更换频率。假设分给一作业的物理块数为3,页面数为2 0个。页面号为（20个）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,11 .先进先出（FI FO）置换算法的思绪该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简朴，只需把一个进程已调入内存的页面，按照先后顺序连接成一个队列，并设立一个替换指针，使它总指向最老的页面。2 .最近久未使用（L R U）置换算法的思绪最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段,用来记录一个页面自

4、上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。3.最 佳（O P T）置换算法的思绪其所选择的被淘汰的页面,奖是以后不使用的，或者是在未来时间内不再被访问的页面,采用最佳算法，通常可保证获得最低的缺页率。4 .F I F O 页面置换算法当需要访问一个新的页面时，一方面调用findExist（i）函数来查看物理块中是否就有这个页面，若要查看的页面物理块中就有，则调用displa y函数直接显示,不需要替换页面;假如要查看的页面物理块中没有,就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；若没有空闲物理块，则调用findR ep 1 a c

5、e函数替换页面。并将物理块中所有页面time r +o5.L R U页面置换算法当需要访问一个新的页面，一方面调用f i n d E x i s t (i)函数查看物理块中是否就有这个页面。6.OPT页面置换算法当需要访问一个新的页面，一方面调用f i n d E x i s t (i)函数来查看物理块中是否有这个页面。7.寻找置换页面函数f i n d R e p l a c e比较三个物理块中的时间标记t i me r,找届时间最久的。代码t t i n c l u d e#i n c l u d e#i n c l u d e#d e f i n e B L O C K J I A X

6、_ S I Z E 2 0 最?大洙?物?理;t?块d 大洙？小？e n u m F I F O=1 ,L R U,O P T);s t r u c t n o d e _p a g e i n t a d d r e s s；指?令?地?址i n t p a g e _ n u m;/页？面?号？i n t n e x t _ o r d e r;/T?一？次?访？问6 的？次?序b *P a g e ;/物？理;I?块6定“义？ty p e d ef struct BlockN o d e i nt pa g e _in d e x;p age数筋组哩？的？下？标括？s t ru e t

7、Bio c kNod e*n e x t;B 1 ockNo d e;str u c tint 1 ength;当獭？前。物?理;t?块。长Q度。in t m iss_flag;/缺d?页？标括？志？,?若?为al,?则。缺d?页?in t miss_cou n t;/缺d?页？次?数筋BlockNode*fr o n t;Bl o c kNode*rea r;(Block;本?程i序。中D全？局?变?量？名？均U由？两？个?单蹋？词洙?组哩？成a?且。开a头？字?母?大洙?写in t B locks i z e=5;/物?理;t?块 6 大洙？小？int PageC o u nt=200;页

8、？面？总哩？数筋int PageS i z e=1024;页?面?大洙？小？i nt AddrRan g e=8*1024;/访？问 6地？址-范？围 int get_ num(int down,int up)得?到?一?个?d o wn up之?间？的?整?数籥(i n t num;ch a r s t r ill；w h i l e(l)f g e t s (s t r,1 1 1 *s i z e o f (i n t),s t d i n );n u m=a t o i(s t r);/把？字?符？串？中D的？数觞字?转墙换?为a整？数觞i f (n u m=d o w n&n u m

9、 n e x t =N U LL;)v oi d e n q u e u e (i n t pa g e _ i n d e x)入？队6B 1 oc kN od e*nod c=(B lo c kN od e *)ma l 1 oc (s i z e o f (B loc kN o d e )；i f (!n od e)p r i n t f (内口存?分?配?失骸？败悒？n);e x i t (0);no d e-pa g e _ i nd e x=pa g e _ i nd e x;n o d e-n e x t=N U LL;Bloc k.le ng t h+;Bloc k,r e a

10、 r-ne x t=nod e;Bi o c k.r e a r =nod e;Iv o i d d e q u e u e()/出？队6(Bi o c kN od e*n o d e；nod e=Blo c k.f r ont ne x t;Bi o c k.f r ont-ne x t =nod e-ne x t;i f (nod e =B 1 oc k.r e a r)B 1 oc k.r e a r=B loc k,f r ont;f r e e (nod e );Bloc k,le ng t h 一 一；v o i d c le a r _ b l o c k()清？空?物？理;l?

11、块 6w h i le (Bloc k,r e a r =Bloc k.f r o n t-n e x t )Bl o c k.f r o n t-ne x t=Blo c k.r e a r n e x t;f r e e (B 1 o c k.r e a r)；B 1 o c k.1 e ng t h ;B 1 o c k.r e a r=Bl o c k.f r ont；B 1 o c k.le ng t h=0；Bloc k,m i s s _c ou nt =0；v o i d d e s t r oy _ b loc k()/销口毁C i物?理;i?块6w h i le (B lo

12、 c k.r e a r=B 1 oc k.f r on t )Bloc k.f r onBloc k.f r on t -n e x t;f r e e (Bloc k,r e a r);)f r e e (pa g e);)v oi d i n i t _ pa g e ()/初？始？化 页？面？系 U 列i n t i,j；s r a nd (t i me (N U LL)；/用？当獭?前。系 U统?时骸？间？来 初？始?化-随？机。种?子哩？p a g e =(s t r u c t no d e _ pa g e*)ma lloc (Pa g e C ou nt*s i z e o

13、f (s t r u c t n o d e _ pa g e );f o r (i=0;i Pa g e C o u nt;i+)p a g e i .a d d r e s s =r a n d ()%Ad d r R a n g e ；p a g e i .pa g e _nu m=pa g e i .a d d r e s s/P a g e Si z e ;)f o r (i=0;i P a g e C ou n t ;i +)f or(j=i+1;jP a g e C ou nt;j+)i f (p a g e i .p a g e _ nu m=pa g e j.p a g e

14、_nu m)pa g e i .n e x t or d e r=j;b r e a k;/i f/f ori f(j=P a g e C o u nt)说 口明+p a g e i 以?后。都?不？会d 再(i 访？问6p a g e i .n e x t _ o r d e r =Pa g e C ou n t;/f or)v o i d pr i nt _pa g e()打洙？印？页？面？系 H 歹 U(i n t i;p r 1 nt f (n)；p r i n t f (页？面？系u列 为a：毗 n );f or(i=0 ;i ne x t)i f (p a g e nod e pa

15、 g e i n d e x ,pa g e n u m二 二pa g e p a g e _ i nd e x .pa g e nu m)Bloc k.mi s s _ f la g =0；r e t u r n;)i f (B loc k.I e ng t h n e x t)i f (pa g e no d e -p a g e _ i n d e x ,pa g e _n u m=p a g e pa g e _ i nd e x .pa g e _ n u m)la s t _nod e-ne x t =n o d e-ne x t;B 1 oc k.le ng t h-;i f (

16、nod e=B 1 oc k.r e a r)B l o c k.r e a r=l a s t nod e；e nqu e u e(n o d e-p a g e _ i n dex);f r e e(n od e)；B I oc k.mi s s _ f 1 a g=0；r e t u r n;la s t _nod e=nod e;i f (Bloc k.le ng t h ne x t)i f (pa g e nod e-p a g e _ i nd e x ,pa g e _ nu m=p a g e p a g e _ i nd e x .p a g e _ nu m)n o d

17、e-p a g e _ i nd e x =pa g e _ i nd e x ;Bloc k,m i s s _ f la g=0;r e t u r n;I)i f (Bloc k.1 e n g t h ne x t;w h i le(n o d e 二 n od e-ne x t)/寻 找6 Blo c k 中Dne x t or d e r 值 u 最？大洙？的？节口点？i f (p a g e ma x _ n o d e-pa g e _ i n d e x .ne x t _ or d e r p a g e _ i nd e x .n e x t _ or d e r)ma

18、x _nod e=n o d e;In od e=Bloc k.f r on t ;m a x _ nod e _ la s t =n o d e;w h i le(nod e =nod e-ne x t)寻 找。B 1 oc k 中 Dne x t _ or d e r 值 H 最?大洙？的?节U 点？的?上？一？个?节U点？i f (no d e=ma x _ nod e )b r e a k;m a x _ n od e _ 1 a s t=no d e；)ma x nod e la s t-ne x t =m a x n od e-n e x t;B 1 oc k.1 e ng t h

19、 ;i f(ma x _ n o d e=Bi o c k.r e a r)B 1 oc k.r e a r=ma x _n o d e _ la s t；f r e e(ma x n o d e);e n q u e u e (p a g e _ i n d e x);Bloc k,m i s s _ f 1 a g =1;B 1 oc k.mi s s _ c ou nt+;)v oi d pa g e _r e pla c e (i n t nu m)i nt i,j;Bi o c kN o d e *n o d e;c h a r s t r 3 5=FIFO,LR U ”，M OPT

20、 ”);p r i nt f (=%s=n,s t r nu m-1 );pr i nt f (页?面?号?*)；f or (i=0；i Bl o c k S i z e：i +)p r i nt f ()；pr i n t f C*是？否？缺d?页?*n);f or(i=0；i n e x t)pr i nt f (0%-2 d “、pa g e nod e pa g e _ i nd e x .p a g e _ n u m);f or (j=B loc k.1 e n g t h;j B 1 oc kS i z e；j+)p r i nt f (*);p r i n t f C*%s *

21、n n H,(Bi o c k.m i s s _ f la g-l?Y e s :N o);)pr j nt f (n -n)*p r i nt f (缺d?页？数第：%d，缺d?页？率6:%.2 f n nz/,Bloc k,m i s s _c ou n t ,(f loa t)Bloc k.m in t /Pa g e C ou nt *1 0 0);pr i nt f (按恪？回？车 u 键t i 继i 续？！n n );g e t c h a r ();)v oi d c o nf i g e ()程i 序6 设?置？(i n t nu m;w h i le(l)p r i nt

22、f (n*口)；pr i nt f(z z*程i 序6 设?置？*n);p pi nt f (*n );pr i n t f C*1 ,设?置?物?理之？块6 大洙?小？(默?认？5)*n)；pr i nt f(*2,设?置？访？问6 地?址 范？围 (默?认?8K)*n)；s s _ c ouprint f(*3,设?置?页？面？大洙？小？(默?认？1 K)*n)；pr in tfC*4,设?置？页？面？总哩？数筋(默？认?200)*n );pri n t f(*5,显?示？各小 项?设?置？值 u*n );pri n t f(*6,返 5?回？*n );p rin tf(*n)；pr i

23、n t f(请?输？入?您U的?选?择？:)；n u m=g e t_num(l,6);i f(n um=6)break;if(num=1 )p r intf(请?输?入?物?理;t?块6大洙?小？(l,%d):，BL0CK_MAX_SIZE);B lockSize=get_ num(l,BL0CK_M AX_SIZE);p rin tf(设?置?成6 功|!n n”);)/i fe l s e if(n u m=二 2)p r in t f(请？输？入?访？问6地?址 范？围(r%d)K:999);A d drR a ng e=get_ n um(1,9 9 9)*10 2 4;p rin

24、tf(设?置?成6功|!nn);/el s e i fe l s e i f(num=3)pr i ntf(请?输?入？页？面？大洙?小？(1%d)K：”，Ad d r R a nge/1 0 24)；Pa g e S ize=g e t num(l,AddrRang e/1 0 2 4)*10 2 4;pr i nt f(设?置？成6功 I !n n);/e Is e i fe l s e i f (n u m=4)pr i nt f (请？输?入?页?面?总哩?数jg (l1%d):，3 2 76 7);P a g e C o u nt=g e t _ n u m(l,3 2 7 6 7)

25、;pr i nt f (设?置？成6功！n n*);/e ls e!fe ls e i f (nu m=5)p r i n t f C-n )；p r i n t f (*当獭？前。物?理;t?块6大洙？小？：%d n Blo c kSi z e);pr i nt f (*当獭？前。访？问6地?址 范？围 :%d K n*,Ad d r R a ng e/1 0 2 4 )；pr i nt f(*当獭？前。页?面?大洙?小？:%d K n H,Pa g e S i ze/1 0 2 4)；p r i n t f (*当獭?前。页？面?总哩?数)B%d n ,Pa g e C o u n t);

26、pr i n i I n),)f r e e (pa g e );i ni t _ p a g e ();)v oi d b e g i n()i n t nu m;pr i nt p a g e ()；w h i 1 e(l)p r i nt f (n*n)；p r i nt f (H*页？面?置？换？算？法?*n)；pr i nt f (*n );pr i nt f f*1,先省进？先出？置？换？算？法而？FIFO)*n )；pr i nt f(*2,最?近(1 最？久？未 使？用？置?换？算?法 L RU)*n)；pr i nt f(*3,最？佳？置?换？算?法力？OPT)*n)；p r

27、 i nt f (*4,返 5?回？*n);pr i nt f (*n 1 1)；P r i nt f (请?输？入？您U 的？选?择？：);n u m=g e t _ n u m(1 ,4 );i f(n u m=4)b r e a k；p a g e _ r e p 1 a c e (nu m)；c l e a r b loc k();If r e e (pa g e);i n i t _ p a g e();)i n t ma i n()i n t nu m;i ni t _ b 1 oc k();i ni t _ p a g e();w h i le (1)pr i nt f (n*n

28、 )；pr i nt f (*存?储沮?器+管U理;t?模 拟2系口统?*n”)；pr i n t f (*n)；pr i nt fC*1,进?入?页？面?置?换?算?法pr i nt f C*2,进?入?程 i 序 6设?置？*n ”)；pr i nt f C*3 ,退？出？*n);p r i nt f (*n );pr i nt f(请?输?入?您U的？选?择?:);nu m=g e t _ nu m(1,3)；i f (nu m-3)b r e a k;i f (nu m-1)b e g i n 0;e l s e i f (nu m=2)c o n f i g e ();)d e s

29、t r oy b 1 oc k();retu r n 0；ij截图1,96H3,1005 4,2222,6274,7486,648H 7,654 H2,24H6,206,51515,8992,591 4,1140,2892,4435,39H2,934 5,660H 0,1211,492J0,6670,552 3,163H4,1019 0,7806,5753,104 7,9805,701,3815,5491,881 6,3031,1962,65017,7274,903 JC6,3554,5051,10023,1106,906 2,302?,1331,5505,2580,293 H 7,714H6

30、,7955,2615,5680,951 JC3,5442,7410,6492,10183,10203,6743,9277,7757,5492,892 H2,852?,1037,7150，1160,10065,851?,5365,923*页面置换算法*翻翻墨嬴,法O PT)*置未算出久换先薯*进近佳回S-W覆，12341*57 42 1*No*6*74 21 6*V es*0*42 16 0*V es*0*42 16 0*No*0*42 16 0*No*7*21 60 7*V es*6*21 07 6*No*2*10 76 2*No*7*10 62 7*No*缺页数：7 0,缺页率:Z 3 5.

31、0 0按回车键继续？1*07 241工No*6*07 21 6*V es*0*07 21 6*No*0*07 21 6*No*0*07 21 6*No*7*07 21 6*No*6*07 21 6*No*2*07 21 6*No*7*07 21 6*No*24rxr/xrM M W V M X/w xN vrfrtfxrrtfrw nxrtfw rrtfsrMifvw*M rifxrrwrxrtfwr缺页数：3 i,缺页率:Z 1 5.5 0按回车键继续？存储器管理模拟系统*1，进入页面置擅算法*2,进入程序设置*3,退 出*请输入您的选择：2程 序 设 置*K*M8人*?v1K20大：8火警

32、卷大总设理间面面项页页各*置置置置示回设设设设显返123456)0请输入您的选择:2,设置访问地址范国（默认8K*3,设置页面大小（蛾110*4横 置 页 葡 总 数 康 认200*5,显不各项设置值*6,返 回*青输入您的选择：5小氾:120理间面面页页刖当当当当K8:6sK:tnn0程 序 设 置*小默篇*K#8卜#缴息豚*大姐火警漆大总设理问面面项物访页页各*置置置置示回设设设设显返123456i入您的选#四、实 验 小 结（针对实验内容逐项小结实验中发现的问题、自己的解决方法、心得体会等）一开始做这个实验时，一方面是看书，先把书上的替换算法知识点弄明白，要明白各种算法的优缺陷和互相之间

33、衍生互补关系。这四个算法中，难以实现的是LRU算法，由于它涉及到访问时间的计算，并且它的开销也比较大。OPT算法次难，它需要计算最近访问时间，并替换最近访问时间最大的页。而 FIFO和 CLOCK实现起来比较容易，FIFO算法的实现和C L O C K 算法的实现很相似,FIFO可视为CLOCK的退化版。我先写了 CLOCK算法，再删去一些约束条件就退化为F I F O 算法。这就是两者的相同之处。理论上，CL O C K 算法需要维持一个循环的主存缓冲区，需要一个循环队列去实现，并且，FIFO 算法保持先进先出，因此需要一个先进先出队列。但是，我实现这两个算法只用到了单向链表的数据结构,剩下的由其中的指针去把握了。因此,必须对指针使用有敏锐的感觉。五、指导教师评语成绩 批阅人 日 期