2023年面淘汰算法实验报告.pdf

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

1、操作系统实验报告课题:页面淘汰算法年 月 日目录一实验目的5错误!未定义书签。二实验规定3.。三背景知识.四总体设计.五 具 体 设 计.错误!未定义书签。六 运营结果分析，.9七 心 得 体 会.13八 参 考 文 献.14附:源代码1 5一、实验目的本实验重要对操作系统中请求分页式内存管理及其应用的一些关键算法进行模拟。学生通过设计与实现C lo ck 算法，可以加强对相应理论的理解，并对了解操作系统内部的基本解决原理与过程也有很多益处。运用简朴的数据结构，模拟实现操作系统中的页面置换机制，通过写程序模拟实现上述三种内存页面置换算法，使学生进一步掌握内存页面置换的方法。对操作系统中内存的管

2、理有一个实践上的结识。1、用 C 语言编写OPT、FIFO、LRU三种置换算法。2、熟悉内存分页管理策略。3、了解页面置换的算法。4、掌握一般常用的调度算法。5、根据方案使算法得以模拟实现。6、锻炼知识的运用能力和实践能力。二、实验规定 设计随机页面序号产生程序，并说明随机的性能和其性能也许对算法的影响 编写页面淘汰算法（F IF O、O P T、LRU）结果数据的显示或提取 结果数据的分析几点说明：设计并绘制算法流程，附加说明所需的数据结构 如何标记时间的先后、最久的将来、最久未被使用描述C l o c k算法的基本原理、必要的数据结构、算法执行流程图、编码实现。1）初始化：输入作业可占用的

3、总页框数，初始化置空。2 ）输入请求序列:输入一个作业页号访问请求序列,依次占用相应页框,直至所有占用；3）C l o c k算法：当页框所有占用后,对于后续新的页号访问请求,执行C l o c k算法,淘汰1个页面后装入新的页号。4 ）显示当前分派淘汰序列:显示淘汰的页号序列。三、背景知识：在操作系统当中，在进程运营过程中，若其访问的页面不在内存中而需把他们调入内存，但内存已无空闲空间时，为了保证该进程可以正常的运营，系统必须从内存中调出一页程序或数据送到磁盘的兑换区中，但是应当是哪个页面被调出，需根据一定的算法来拟定。通常，我们把这一类的算法称为“页面置换算法”，页面置换算法执行效率的高低

4、，往往直接影响到操作系统的性能。内存页面置换算法：1、先进先出调度算法（FI F0）先进先出调度算法根据页面进入内存的时间先后选择淘汰页面。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次置换掉最早进入的页面。这是最早出现的置换算法，该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最长的页面换出，予以淘汰。该算法实现简朴只需把一个进程已调入内存的页面,按先后顺序链接成一个队列,并设立一个指针,称为替换指针，使它总是指向最老的页面。但该算法与进程实际运营的规律不相适应，由于在进程中，有些页面经常被访问，比如，具有全局变量、常用函数、例程等的页面，FI FO算法并不能保证这些页

5、面不被淘汰。最近最久未使用的置换算法（L R U）最近最久未使用的置换算法,是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能运用“最近的过去”作 为“最近的将来”的近似，因此,L R U置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t ,当须淘汰一个页面时,选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。最佳置换算法（O P T）最佳置换算法是可以说的一种抱负的页面置换算法,它是由B e l a d y于1 9 6 6年提出的一种理论上的算法。其所选择的被淘汰页面,将是以后永不

6、使用的或许是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以运用此算法来评价其它算法。时钟页面置换算法时钟页面置换算法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面,如图所不。口囚回 向当发生缺页中断时，检L代表计揖向的页面。根据R位采取动作：E J LB J R=O：淘汰页面0叵|口r|R =I：清移除动口表位计并向前当发生缺页中断时,算法一方面检查表针指向的页面，假如它的R位 是0就淘汰该页面,并把新的页面插入

7、这个位置,然后把表针前移一个位置；假如R位 是1就清 除R位并把表针前移一个位置，反复这个过程直到找到了一个R位 为0的页面为止。四、总体设计根据规定设计页面淘汰算法的活动图运营程序进入主页面，在正上方，已经通过随机生成函数生成了页面号，在其下方，显示可选项:0、退出程序1、FIFO算 法2、OPT算 法3、LRU算法。根据需要，选择相应的法，程序自动生成页面淘汰的先后顺序，以及置换次数和缺页次数，并打印在下方，执行完以后，再次进入主页面,到输入0,退出程序。算法流程图 FIFO算法流程图：OPT算法流程图新的指令页面是己在内存物理块中？I否载 入 该 页 面.否 内 存 物 臀 集 合 已酒

8、 I是对内存中卷个页面，向后遍历剩余指令集合，记录每个页面距离再次被利用的页面跨度选择跨度最大的页面换出ALRU算法流程图:/是.选择time值最大的页面换出五、具体设计（一）、设计思想1、最佳置换算法（O P T）用数组T e m p p a g e s 口存储当前物理块中页面信息，数组T i m e A r r y 口存储当前在物理块中的页面的获得内存时的时间，当页面不在内存中时，根据当前已获得物理块数的页面在所有的页面当中将来不在请求内存或者很少请求内存的情况进行置换2、先进先出算法（F I F O）用数组T e m p p a g e s 口存储当前物理块中页面信息，变 量 t e m

9、 p 记录内存中物理块页面置换状态,每进行一次置换，页面置换状态变化,便于下一次的置换。3、最近最久未使用算法（L R U）用数组T e m p p a g e s 口存储当前物理块中页面信息,数组T i m e A r r y 存储当前在物理块中的页面的获得内存时的时间，当页面不在内存中时,选择T i m e A r r y 口数组中值最小并且相应物理块中的页面进行置换。（二）、设计环节一方面根据程序规定，我们分别定义两个宏，用以存放我们的物理块数目以及页面数目，再定义一个结构体，用以物理块的存储，代码如下：#d e f i n e M e m P a g e C o u n t 4#d e

10、 f i n e I n s t r u c t i o n C o u n t 2 0s t r u c t p a g e（。i n t s e r i a l;页面号b i nt t i m e；时间计数 me mp a g e M e mP a g e C ou nt ;另一方面，建立主函数，根据程序需要，定义相应的变量，建立s w i t c h 语句，用以算法的选择，部分定义如下：i nt i,j,k,m,n;/指令页面集合，可以考虑让页面指令集合随机生成 i n t i ns t r u c t i o n I n s t r u c t i onCou nt ；oi n t m

11、e m_ c ou nt e r;内存页面集合计数器。i nt s w i t c h _ c o u n t e r ;/置换次数最后，根据算法流程图,实现相应算法的代码编写。（三）、算法流程设计主函数流程：STE P 1:输入分派的页框数，页面访问次数和要访问的页面号序列STEP2:内存页面初始化。内存中页面的数据结构为单循环链表，具有页号值yeha o 和访问位值a。开始时页号均为T,访问位为0.STEP 3:测试数据。具体算法是依要访问的页面号，调用f i nd()函数查找是否已经存在于内存中。若存在，则修改其访问位为1.若不存在，触发缺页中断，调用tih u an()函数。最后，打印

12、当前内存状态。如此循环直至测试串都访问完毕。1)重要函数实现a)Maken o d e (do u b 1 e)函数:用于初始化一个节点。b)Find(double)函数:依据输入的页号，查询内存中是否已存在此页面。若存在返回值1,不存在返回值0.c)Tihuan(d ou b 1 e)函数:在发生缺页中断时，时钟指针查找访问位为0的页面进行替换,指针扫过的页面访问位置0,新加入的页面访问位置lo替换后指针下移。d)Print_stat e()函数:打印当前内存中存在的页面的状态以及当前时钟指针所指向的页面位置。2)测试数据估计输入：输入分派的页框数3输入页面访问次数1 5输入要访问的页面号序

13、列3 42 643 743 6 3 4 8 4 6。输出（仅最后一项）:页面号 访问位41史 荷 号 访 问 位61页 面 号 访 问 位81c lock指针所在位置页面号为43）结果分析以下是c loc k算法相应输入页面号序列3 4 2 6 4 3 7 4 3 6 34 8 4 6的分析表引 用串P34 2 64 374 3 634 84 633 3+66 6+64 4 444 4+4+4*内 存*4 4 4+4+477+7+666 66 6+222 33+3 3 3+3+3+88 8是否缺页JJ J JJJJ JJ六、运营结果分析:a）开始界面S3Z:Progra FilesC-Free

14、 St andardte八未命名 L exe/|x请按任意键进行初始化操作.一11565346106810388764i:为为:为别数续隹继面号理键Me：物意 省省用任缺缺可按1、使用默认值产生结果 2、自定义页数和贝号请输入你的选择：百度拼音半:2、采用随机数产生的结果Progra FilesC-Free Standardte p未命名 1 exe,请按任意键进行初始化操作.-:为为：为别数续数八负继面0节理键物意以省省用任可按134013424016247 821、使用默认值产生结果 2、自定义页数和页号_ _ _ _ _ _ _ _ _ _ _请输入你的选择：请 选 择 髓：1为FIFO

15、（先进先出2为LRU（最近最久未使用3为OPM最佳置换算法4三福法一起实现2、采用自定义页面信息产生结果自定义页面数为：1 5 物理块数为：4页面序列为：1 2 3 4 5678945670 8s i*C:Progra F ilesC-F ree S ta n d a rd te B p L exe*-同X自定义页面数和页号80?65?96N5V/54112346784670843?:152数：为:1块为别为:数.理数分数续面0曷面。隹继Mee改理键入入修义义物意篇否定定用任请请是包自可按请 选 择 髓：为FIFO（先进先出2为LRIK最近最久未使用3为OPT（最佳置换算法4三可算法一起实现根

16、据结果，我们不难发现,O P T算法，是三种算法中性能最佳的，它的置换次数最少，L R U次之,，但是性能最差的还是F I F O,由于缺页率=缺页次数/总的页面数，所以我们不难发现，随着物理块数的增长，缺页率都相应有所增长，但是O P T算法的增长较为明显，即产生了 b e l a d y现象。七、心得体会：这次课程设计，让我对算法的编写更加的纯熟，同时更加了解页面置换的相关算法,也提高了我对算法设计的严密性，对以后的程序设计有很大帮助。我们不仅对常用的算法进行了编写，还对一些抱负的算法也进行了编写,并且通过适当的方法,得以了验证。就该程序而言，随机性使得程序出现了更多的也许性,为我们验证算

17、法提供很大的方便，电脑自动分派,大大的节约了我们的时间,但是我们通过实验不难发现，假如所设的页面项目过大，也会影响我们算法的性能执行效率。对我们所涉及的算法，让我有很大的感触。在F I F O 算法中,无论有无发生缺页或者置换，都需要对每个在内存中的页面的t i m e值进行增长操作，以保持最先进入的那个页面的I i m e值是最大的；一个新进来的页面，其t i m e值设立为0。当然，该算法也可以通过队列结构来实现，运用队列的先进先出（F I F O）特性完毕，无需设立t i m e字段。dis t a n c e用于记录内存物理块集合中每个页面距离再次被使用的页面跨度，缺省值为9 9 99

18、,假如某个页面在后续指令集合中不再出现,则用最大值9 9 9 9缺省取代;假如页面再次被使用，则两次使用所跨的页面数,为页面跨度。用最大页面跨度表达以后永不使用或未来最长时间内不再被访问。在LRU算法中，无论是否发生缺页或者置换，除 了 命 中（刚刚被访问过的页面）页面t i m e值清零之外，其它所有内存中的页面的tim e值都加一,以保证最近刚刚被访问的页面的tim e值最小，相 应t i m e值最大的页面就是最近最久没有被访问的页面。上述两种算法，是我们在进程调度中使用最多的两种，你也许会问？为什么要使用进程调度，由于当我们的程序在运营时,若所访问的页面不再内存而需把它调入内存，但内存

19、已无空闲空间，这时，为了保证该程序能正常运营,系统就必须从内存中调出一页程序或数据送到磁盘的兑换区中，但应将那个页面调此我们就必须根据一定的算法来实现。所以，一个页面置换算法的好坏，将直接影响到我们系统的性能。相比较而言，我们最常用的是LR U算法，由于它是根据页面调入内存后的使用情况就行决策的，比F IFO算法要好很多。通过与其他算法的比较，加深对c 1 ock算法的理解，也了解了他们的异同之处。Clock算法其实是一种改善的第二次机会算法，它通过设立访问位，找到最早最不常访问的页面,即标号为0的页面。之所以叫cl。c k算法,依我理解是将内存中的排列顺序附上时间的概念,clock指针扫过的

20、页面要将他们1置0就是基于这个思想，由于他们都是没被访问的,且在时钟上的排列按照访问时间顺序。这样就保证了每次替换的都是最早进来的且不最常访问的页面。八、参考文献1 计算机操作系统（第三版）汤小丹、梁红兵、汤子瀛、哲凤屏等 西安电子科技大学出版社 2 0 2 3 -0 5【2】C+P r i m e r 中文版（第 4 版）（美）S t a n l e y B.L i p pm a n 等 著 李师贤等 译.人民邮电出版社，2 0 2 3-0 3-0 1【3】C+P r i m e r 习题解答（第 4 版）蒋爱军，李师贤，梅晓勇 著 人民邮电出版社 2 0 2 3-0 2-0 1【4】现代操

21、作系统（原书第3 版）塔嫩鲍姆（T a n e n b a u m.A.S）,陈向群，马洪兵 著 机械工业出版社 2 0 2 3-0 7-0 1【5】计算机操作系统教程 张尧学,史美林，张高 清华大学出版社 2 0 2 3-1 0-0 1【6】数据结构（S T L 框架）王晓东 著 清华大学出版社2 0 2 3-0 9-0 1附：源代码#i nclud e#i nclud e#i n c lu d e#d efi n e M_size 100int pageNum=0；/全局变量页面数i n t pages M_ s iz e;/存储页号in t T e mpp a g esM_size;/辅

22、助数组int T i m e Ar r y M_size;/记录页在内存中的时间i n t method;/产生结果的方法int Algor i t hmS t yle;/辅助变量.用于选择算法类型in t B lock;/记录物理块数int start;/辅助变量void Init i on()/初始化函数。int i;。i n tt=tim e(N U L L);/产生随机数种子srand(t)；/用t初始化随机数种子。pageNum=rand()%10+8;/随机产生4-1 4之内的整数，保证页面数在4-1 4之内 fo r(i=0;i pageNum;i+)o page s i=ran

23、d()%1 0+1;/初始化页号，初始值在1-10之内B i o C k =4;/初始化物理块数位3v oi d pri n t D e f a I t R e sul t ()/缺省参数显示/I。i nti;pri n t f(缺省页面数为：%d n,pa g e N u m);pri ntf(缺省页号分别为：);f or(i =0；i pa g e N u m ;i+)(p r i ntf(%d ,pa g e s i );0 p ri n t f(n);p r i nt耳可用物理块数为：%d n,B I o c k);pri ntf(按任意键继续:)；。g e t c h a r();0

24、)voi d P ri n t Cu s tom l nf o()/显示用户自定义参数i nti；p r i n t f(自定义页面数为：%d n,pageN u m);P rin t f(自定义页号分别为：);for(i=0;i page N um;i+)(printf(%d,p a g esi)；0)pr i nt f(n )；printf(可用物理块数为：%d n,B lo ck)；printf(按任意键继续:n);o ge t c h ar();)v o id printU s e rln f o()/显示个人信息(。sy s tem(c o I or OB);,printf(-1 n

25、)；pr i n tf(|页 面 淘 汰 算 法1 n)；0 pin t f(|学 号：1 n)；。print f(|班 级：1 n)；。pr i ntf(|姓名：I n );pr i n tf(I-1 n )；P r i nt f(按任意键开始操作:);g e tcha r();。syst e m(cl s);s y s tem(c olor 0 B);)vo i d Chioc e Dea I metho d()/选择解决问题的方法1 选择缺省值，2选择自定义值I。p rin tf(-1 n)；。p r i n t s|1、使用默认值产生结果 2、自定义页数和页号I n );。p rint

26、f(1-1 n请输入你的选择:n);sc a n f(%d h o d);s y s te m(c o lor 0 F);v oi d P ri nt N o tW i t h o u tP a g e s()/显示一定不用换页的部分s t ar t =Bl o c k;i n t i,j,k =O,k e y=0;f o r(i =0;i s t a r t ;i +)。i n t f l a g =0;f orQ =0;j 3 o T i m e Arr y j =i;。f l a g =1;3 o s ta rt=sta r t+1 ;3 3 k e y+;0 i f(f l a g =

27、0)(。T i m e Ar r y k =i;T e m p pa g e s k =pa g e s i b 3 k+；for(j=0;j=i-key;j+)Ob。printf(H%-7dM,Temp p agesjj);/printf(n)；6)void PrintResul t()/显示每次换页后的结果Ib in t i；fo r(i=0;i B I o ck;i+)。p rint f(%-7d,Tempp a ge s i)；6 p r int f(n );)void FIFO Dea I Qu e s ti。n()先进先出算法。int i,j;i n t Wi t hO utPa

28、g e s=0;/记录缺页数。pr i ntf(FIF 0(先进先出算法)结果显示:n);P r in t NotWi t hout P ag es();int temp=0;。for(i=start;i pageN u m;i+)6(if(t emp=Block)6(。o。temp=0;0 0 o int k e y =0；for(j=0;j Block;j+)/判断该页是否在物理块中(o o if(Tempp a ge s j =p ages i)0(。3 key=1;b re a k;0 0 0 b 3 if(key=0)/假如不在0(。Temppagest e mp=p ag e s

29、i;。3 temp+;o WithOutPag e s+；。Pr i n tR e s ult();0 0 16)printf(置 换 次 数 为：%d，页 面 总 数 为：%d，置 换 率 为：,WithOut P ages,pageNum);do u ble re=(double)W i t h O u tPages)/(d o u b le)p a geN um);p r intf(%.21 f n ,re)；。printf(缺页次数为：%d，页面总数为：%d，缺页率为：,Wi t h0 u tP a ges+Block,pa g eNu m);re=(d o ub I e)(Wit h

30、 Ou t Pa g e s+Bl o ck)/(do u b I e)page Num);p rintf(%.21fn,r e)；)void L RUD e alQu e s t i on 0/最近最久未使用算法(6 i n t i,j;。int WithOu t Pag e s=0；/i己录缺页数pr i n t f(L R U(最近最久未使用算法)结果显示:n);P rin t NotWi t h o u tP ages()；0 f 0 r(i=start;i pag e N um;i+)。凸 int k e y =0;f o r(j=0;j v B lock +)/判断该页是否在物理块

31、中(。if(T em p pa g esj=page s i)k ey=1;。TimeA r iyj=i;/更新时间break;3 0 f。if(ke y=0)若该页不在内存中6(W i t hO u tPages+;i n t mi n=TimeArr y 0;in t fl a g=0;forQ=1;j Time Ar r y j)o 。min=TimeArryj；/找到最久的页面。fla g=j;6)。TimeArry f I a g =i；记录时间 o Temppagesff I ag=pages i;。PrintResult();a a p r i ntf(“置 换 次 数 为：%d

32、，页 面 总 数 为：%d，置 换率为：,WithOu t Pag e s,pa g eNum);double re=(doub I e)W i thOutPages)/(double)page N u m);printf(%.2 I f n ,re);p ri ntf(“缺页次数为：%d，页面总数为：d，缺页率为：,W i th O u tPa g e s+B lo c k,pageNum);r e=(double)(W i th 0 u tPage s+Block)/(double)p a ge Num);。prin t f(%.21 f n,re);)void OPTD e alQue

33、s t io n()。int i,j,l;i nt W i th O u t P a g e s=0；/记录缺页数 pri n t f f O P T (最佳置换算法)结果显示:n);。P ri n tN o tW i th outP a g e s();f or(i =sta rt;i p a g e N um ；i+)(s i n t k e y=0;。f or(j =0;j 3 T i m e Arry j =i;。k e y=1 ;o b re a k;b 3 0 0 6 o i f (k e y=0)/假如该页不在内存中b 3 3 W i t h O ut P a g e s+;/缺

34、页数力口 1。/得到各物理块下一次访问的时间3 b f or(j =0；j Bl oc k ;j+)b b for(I =i+1 ;I pa g eNum；1+)b 3 3 i f(Tempp a ge s j=pages I )3 0 b r e ak；0 b 3 o b 3 o Time A rr y j=1;Ob。/得到下一次访问时间最长的一个页面，将当前页与其换掉 i n t min=T im e A r r y 0 ;B in t fla g=0;。3 forQ=1;j min)0 3 min=Tim eAr r yj;。f lag 二 j；0 6),T emppagesfl a g

35、=pagesi；。TimeArryfflag=iP rin t R e sult();0。printf(“置换次数为：%d,页 面 总 数 为：%d,置换率为：,Wi thOutPages,pageN u m)；d o u ble re=(double)W i thOutP ages)/(doub I e)pageNum);pr i n t f(%.21fn,re);printf(“缺页次数为：%d，页面总数为：%d，缺 页 率 为：,W i th Ou t Pag es+B I ock,page Num);。r e=(dou b I e)(W ithoutPage s+B I ock)/(d

36、o u ble)pa g eNum);p rintf(%.2 I f n ,re);)void Chioc e A I gorit h m(int A I go r i t hmStyl e)s witch(A I go r ithmSt y le)6。c a se 1:。FIF ODe alQu estion();/先进先出算法解决问题o break;case 2:。LRUDea I Q ues t ion();/最近最久未使用算法解决问题。b r e ak;c ase 3:。OPTDea I Ques t ion();/最佳置换算法解决问题break;C ase 4;。FIFOD e a

37、I Q ues t i o n();先进先出算法解决问题。LRUDealQuestion()；/最近最久未使用算法解决问题OPTDealQuest i o n();/最佳置换算法解决问题b re ak;)void Defa I tDe a 1()/默认解决(Printf(-1 n 0);。printf(|请选择算法:1为FIFO(先 进 先 出)2为LRU(最近最久未使用)3为OPT(最佳置换算法)|n)；。printf(|4 三 种 算 法一 起 实 现I n)；Printf-1 n )；。s canf(%d,&A I go r i t h m S ty le)；o Chioce A1 g

38、or i t h m(Algorit h m Style)；void CustomDea 1()/自定义解决。in ti;。syste m(c i s”)；op r in tf(-1 n)；pri n tf(|I n)；。pri n自定义页面数和页号tf-1 n );。printf(请输入页面数：);s c a n f(%d,&pa g e N u m);。p r i ntf(请输入页号：”)；f o r(i=0;i);g etcha r();。Initio n()；/初始化函数，随机产生页面数和页号p r i n t DefaltRe su I t();输出默认信息Chioc e Dea I method();/选择产生结果方式。DealQ u e s t i o n s()；/开始解决问题o r e tu r n 0;