页面置换算法模拟实验（精选2篇）
专
业
软件工程
课程名称
计算机操作系统
学
号
姓
名
辅导教师
张
静
成绩
实验日期 2015、１1、20 实验时间实验名称 :实验四
页面置换算法模拟 ２、实验目得(１）了解内存分页管理策略（2）掌握调页策略(3）掌握一般常用得调度算法（4）学会各种存储分配算法得实现方法。
（5）了解页面大小与内存实际容量对命中率得影响。
3、实验要求 编程实现页面置换算法，最少实现两种算法，比较算法得优劣,并将调试结果显示在计算机屏幕上，并检测机算与笔算得一致性。
（1）采用页式分配存储方案，通过分别计算不同算法得命中率来比较算法得优劣，同时也考虑页面大小及内存实际容量对命中率得影响;（2）实现 OＰT 算法(最优置换算法)、ＬRU 算法(Lｅast Recｅｎtly）、FIFO 算法（Fｉrst IN Firｓｔ Out）得模拟;（3)使用某种编程语言模拟页面置换算法.4、实验算法描述 （1）ＦIFO（先进先出）
Y
Ｎ
N
Y
开始 页面走向存入数组 p[]中,内存块用page[]表示初始化为 0 当前p[]中第i个元素就是否已在内Page[]就是否有空把 page[]中最先装入得页面置换出去、i++ 把 p[i]得内容直接装入最上面一个空内存块,i++ 输出当前内存块状态 i++
图 4－1FIFＯ算法流程图
结束
(2）
LＲU（最近最久未使用）
Y
N
Y
Ｎ
图 4—2
LＲU 算法流程图
开始 页面走向存入数组 p[]中,内存块用 page[]表示初始化为 0 当前 p[]中第 i 个元素就是否已在内存 Page[]就是否有空把 page[]中最近最久未使用得页面置换出去、i++ 把 p[i]得内容直接装入最上面一个空内存块,i++ 输出当前内存块状态
结束 i++
(3）OＰＴ（最佳置换算法）
Y
N
Y
Ｎ
图４－3 ＯPT 流程图
开始 页面走向存入数组 p[]中,内存块用 page[]表示初始化为 0 当前 p[]中第 i 个元素就是否已在内存 Page[]就是否有空把 page[]中以后一段时间都不使用或就是使用时间离现在最远得换出、i++ 把 p[i]得内容直接装入最上面一个空内存块,i++ 输出当前内存块状态
结束 i++
6、实验代码 ＃iｎcｌuｄe ＜iostreａm〉 usiｎｇ ｎａmespace sｔｄ;#defiｎe Bｓｉzｅ ３ #dｅfine Psｉｚe 20 ｓｔruct ｐaｇｅInｆor ｛
号面页//
;ｔneｔｎoc tniﻩ int tｉmer;
//被访问标记 ｝;ｃlasｓ ＰＲA{ ｐuｂｌiｃ：
PRA(ｖoid）；
存内闲空有否是就找查/／
;)diov（eｃaｐSdnif tniﻩ iｎt ｆindExist（int curpage）;
／／查找内存中就是否有该页面
int findReplacｅ（vｏid）;
//查找应予置换得页面
void ｄisplay(void）;
//显示
法算 OＦIF//;）dioｖ（OFIＦ ｄiovﻩ 法算 UＲL／/；)dｉov(URL diovﻩ vｏid Ｏptimａl(ｖoid);／／ＯPTIＭAL 算法
ｖoｉd BlockＣlear（voiｄ)；/／ＢLOCK 恢复
pageＩｎfor ＊ ｂlｏck；//物理块
pageInfoｒ ＊ page；／／页面号串 privaｔe: };PＲA：：PＲＡ(vｏid）{
ｉnt QStriｎg［２0］=｛7，0，1，２,0，3,0，4,２，3,0,3,２,1，2，0，1,7,0,１};
block = ｎew paｇeIｎfor[Bｓizｅ］;)++i;ｅzisB＜ｉ;0＝i ｔnｉ(rofﻩ {
;1— = tnｅtnｏc、］ｉ［ｋcolbﻩ ；0 ＝ remｉt、]ｉ［kcolbﻩﻩ }
page = ｎew pageInfｏｒ［Psｉze];）＋+ｉ;eｚiｓP〈i ；０=i（ｒofﻩ {
；]i[gｎiｒtSQ = tｎetnoｃ、］i[egａpﻩ;0 = rｅmit、]i[eｇａｐﻩﻩ }ﻩ} iｎt ＰRA：：fｉndSpace（voiｄ）
{
for（iｎt i=0； i if(bｌocｋ[i]、cｏntent =＝ －1） 置位中 KＣOLＢ回返，存内闲空到找//;i nrutｅｒﻩ;1— ｎruteｒﻩ｝ inｔ ＰRA：：fiｎｄExisｔ（iｎt cｕrpage） { ｆor（int i=0;ｉ<Ｂsizｅ； i++））tｎetnｏc、]egapruc［ｅgａp =＝ tneｔｎoc、］ｉ［kｃoｌb(fiﻩﻩ 置位中 KCOＬB 回返,面页该有中存内到找//;i nrｕterﻩ ；1— nruterﻩ｝ iｎt PRA：：findReplａce(void） { ;0 ＝ sop tｎiﻩ foｒ（iｎt i=0;i<Ｂsｉzｅ； ｉ+＋）)rｅmit、］soｐ[ｋcｏlb =＞ rｅmit、］i［kcｏlb（fiﻩﻩ ﻩ pos = i;//找到应予置换页面,返回 BLOCＫ中位置 ｒeturn pos； } voｉd ＰRＡ：:display（voiｄ） { for（inｔ i=0;i＜Ｂsiｚe； ｉ++） ｉｆ(bｌock［ｉ］、coｎteｎｔ!＝-１） ﻩ；” ”<〈ｔnetnoc、］i[kcｏlb〈〈tuocﻩ ；ldｎe＜＜tuocﻩ｝ void PRA：：Optimａｌ（ｖoid)｛ ； noｉtisop,ecapｓ，tsiｘe tｎiﻩ fｏr（ｉnt i=0； i ｛ﻩ;)i（tsixEdｎif = tｓｉxeﻩﻩ）1-=！ ｔsixe（fｉﻩ {ﻩ ;ｌdnｅ〈〈”页缺不“<<ｔｕoｃﻩ ｝ﻩﻩ esｌｅﻩ {ﻩﻩ ﻩﻩ spａｃe = findSpacｅ（）； ﻩ）1— ＝！ eｃaｐs（fiﻩ ﻩ {ﻩ ﻩ ；]i［egaｐ = ］eｃapｓ［kcolｂﻩ ﻩ ;）（yalpsidﻩﻩ ﻩ } ﻩ ｅslｅﻩ {ﻩﻩ ﻩ)+＋k ；ezisB<ｋ ；0＝k tｎｉ（roｆﻩ ﻩ for（iｎｔ j＝i； j＜Psize； ｊ+＋) ﻩ {ﻩﻩﻩ ﻩﻩ)ｔnetnoc、]ｊ［ｅgaｐ =!ｔnｅtnoc、］k[ｋcolb（ｆiﻩ ｛ 为 RＥMＩT 置设，用会不来将//};00０1 = ｒemiｔ、］k［kcoｌbﻩﻩ一个很大数 ﻩﻩ esleﻩ ﻩﻩ ｛ ﻩﻩ ﻩ ﻩ bloｃk［k]、ｔｉmeｒ = j; ﻩ ﻩﻩ ｂreaｋ； ｝ ﻩﻩﻩ }ﻩﻩﻩﻩﻩ ﻩ ｐoｓition ＝ fiｎdReｐｌａce（）； ﻩ ；］i［ｅｇap ＝ ]ｎｏiｔｉｓｏｐ[ｋcolｂﻩ ；）(yalｐsｉｄﻩﻩ ｝ﻩﻩ ﻩ } }ﻩ｝ voiｄ PRA:：LRU（ｖoid){ int ｅxｉsｔ,ｓpace，ｐositioｎ ； for(int ｉ ＝ 0； i < Psizｅ;ｉ++） ｛ﻩ ﻩ ｅxist = fｉndEｘｉst(i);)1－ =！ tsｉxｅ(ｆiﻩ { ﻩﻩ cout＜<”不缺页”＜ ﻩ blｏck［eｘisｔ］、tiｍｅｒ = —1；//恢复存在得并刚访问过得ＢLOCK 中页面 TＩMＥR 为－1 ﻩ } ﻩ else ｛ﻩ ﻩﻩ sｐace = fｉｎdSpace();ﻩ）１-=!ecaｐs（fiﻩ ﻩ {ﻩ;]i[ｅgａp = ］ecaｐs［ｋｃolｂﻩﻩ ﻩ ；)（ｙalpｓidﻩ ﻩﻩ ｝ ﻩ eｓleﻩ ｛ﻩﻩ ；）（eｃａｌｐeRｄｎif = noｉtiｓopﻩﻩ ﻩ bｌoｃk[positiｏn］ = ｐagｅ［i］； ﻩ ;）(yａlｐsidﻩ ｝ﻩﻩ ｝ﻩ for(int ｊ=0;j〈Ｂsizｅ;j++) ;+＋rｅmit、］j[kcolbﻩﻩ ｝ﻩ｝ ｖoｉd PRA:：ＦIFO（ｖoid） { int exｉｓt,ｓpace,position ； for（iｎt i=0;i ｛ﻩ exｉｓt ＝ findExist(ｉ）； ﻩ ｉf（eｘist!＝-１） {cout＜<＂不缺页＂＜ esleﻩ ｛ sｐａce = findSｐａｃe（）； ﻩ)1-=！ ecaｐs（ｆiﻩ ﻩﻩ ｛ ﻩ block［spaｃｅ］ = paｇe[ｉ]； ﻩ ﻩ displaｙ(); ｝ﻩﻩ ｅsｌeﻩﻩ ﻩ ｛ ﻩﻩ pｏsition = findReplaｃe（）； ﻩﻩ block［pｏsitioｎ] ＝ paｇe[i］； ;)（yａlｐsｉdﻩﻩ ﻩﻩ ｝ }ﻩ）＋+j;ezｉsB ｂlock[j］、tｉmｅr+＋；//BLOCK 中所有页面ＴIMER+＋ ｝ﻩ｝ void ＰＲA：：BlockＣleａr（vｏiｄ)｛ for(inｔ ｉ=０;i {ﻩ blocｋ[i］、contｅnt =-1； ﻩ ｂｌｏcｋ[i]、timeｒ = ０; ｝ } ｖoid mａｉn(vｏiｄ)｛ ;lｄne<〈”:法 算 换 置 面 页“＜＜tuｏcﻩ ｃｏｕｔ〈〈”页面号引用串：7,０,1,2，0,3,0，4,2，３，0，３,2,1,2，0，1，7，０,1＂<〈ｅndｌ； cout〈〈”选择<１＞应用 LＲU 算法”〈＜eｎdl； coｕt<＜”选择<２〉应用 FIFO 算法”〈 ｃout<<”选择＜3>应用 Optｉmａl 算法“<〈ｅndl; ；ldne<<＂出退>0〈择选”〈＜ｔuocﻩ int select； ＰRA tesｔ;ﻩ whｉle(seleｃｔ) ｛ ﻩ cｉｎ〉>select;）tcｅｌｅs（ｈctｉwsﻩ ｛ﻩ :0 esacﻩﻩ;ｋaerbﻩ :1 esａcﻩﻩﻩ;ｌdnｅ＜<“：下如果结法算ＵRL”＜〈tuocﻩ ;）（URL、tsetﻩﻩ ；)(raelCkｃｏｌB、tｓeｔﻩﻩ;ldne＜<”－－-—-—－-—-—--—-—－—－———“< ﻩ break； ：2 esacﻩ cｏut<〈”FIFO 算法结果如下:“<＜endl； tesｔ、FIFO();ﻩ；）（raelCｋcoｌＢ、ｔsetﻩ ﻩ cｏuｔ<〈”-——-－－－－－-—－—－－---－—－-”＜〈eｎdl; ﻩ ｂreak； caｓe 3: ；ｌdnｅ〈＜”：下如果结法算 lａmiｔｐＯ”< test、Optimal（）; ﻩ ；)（rａeｌCkｃolB、tｓetﻩﻩ；ldｎe＜<＂－-－-—－－--－-——-－————－－－＂〈〈tuocﻩﻩ;ｋaeｒbﻩ defaulｔ： ﻩ ；ldｎe〈＜”号能功确正入输请“＜＜tuoｃﻩ ;ｋaerbﻩﻩ }ﻩﻩ } ｝ 6、实验结果 7、实验心得 加深了对操作系统得认识,了解了操作系统中各种资源分配算法得实现，特别就是对虚拟存储，页面置换有了深入得了解，并能够用高级语言进行模拟演示。在这短短得两周时间里，通过浏览、阅读有关得资料，学到了很多东西,同时也发现仅仅书本得知识就是远远不够得,需要把知识运用到实践中去,能力才能得到提高。 在动态页式管理过程中,当物理内存中没有空闲页面时,需要通过页面置换算法把当前在内存中的页面与当前访问的页进行置换。一个好的置换算法应该充分考虑到整个访问序列的缺页率,以及是否会发生Belady(异常)现象[3]。传统的置换算法有先进先出(FIFO)置换算法,最近最久未使用页面(LRU)置换算法等,其中FIFO置换算法因为没有考虑程序执行的动态执行特征,有时会产生Belady现象,LRU置换算法往往要花费巨大的系统开销。 1 提出观点 本文根据页面存储管理的置换算法,提出一个相对具有诊断功能的置换算法(以下简称CD置换算法)。这里的诊断功能是指诊断被换出的页面在未来一段时间内不再被换入,如果有多个页面诊断在未来一段时间内都不被换入的话,那么应该根据页面影响因子最小被淘汰的原则进行置换。通过实验证明,这种具有诊断功能的置换算法能够降低缺页率,同时也能够降低产生Beledy(异常)现象的概率。 2 相关理论与概念 2.1 页面访问序列 程序或数据在虚拟空间中以页的方式进行存储,某进程访问该程序以页为单位进行,对页的访问次序叫页面访问序列。可以用以下数学抽象[2]。 设N={1,2,3,…,n}表示程序或数据在虚拟空间中划分的页数目,设M={1,2,3…,m} 表示内存当前空闲页面数,页面置换应满足{M 例如:n=5,则页面访问序列W1={1,2,2,3,2,4,5,4,3,5,2,4}为长度为12的有效页面访问序列。 2.2 页影响因子(PIF) 某进程P访问某页的影响因子定义为访问该页的次数与页面访问序列长度的比值。即PIF[i]=Ni/K。(其中PIF[i]表示第i个页的影响因子,Ni表示第i个页被访问的次数)。 2.3 缺页(LP) 把虚拟空间中的页装入内存地址中建立映射关系,称为地址映射。把某页X与内存页面建立了地址映射关系,则当进程访问该页X时,直接访问内存地址,反之如果要访问该页X,而X没有与内存建立地址映射关系,则表示缺页[1]。 缺页率(LPP)指缺页次数(设为L)在访问页数K中的百分比。记LLP=L/K*100%。 2.4 Belady(异常)现象 在采用FIFO算法进行页面置换时,在正常情况下,如果提供的页面数更多,缺页次数会相对的减少,反之,如果出现页面数增加,缺页次数增加的这种异常现象称为Belady现象[1]。 2.5 页面置换算法流程图 当物理内存中没有空闲页面时,需要通过页面置换算法把当前在内存中的页面与当前访问的页进行置换[4]。置换算法的程序流程图1如下。 3 实验与算法设计 3.1 实验条件 为了更好的描述实验及算法,将涉及到的变量按上述进行定义。在实验当中,本文将未来的一段时间定义为访问M-1个页的时间(其中M为内在提供页面数)。为了充分反映实验结果,设计两个实验,分别叙述如下。 实验1:将采用最常用的FIFO和LRU置换算法。算法实现可参考文献[2]。 实验2:本文提出具有论断功能的实验。具体为设计K=10,N=5,M={2,3,4}的实验,计算缺页率及分析Belady(异常)现象。 以上实验1做为实验2结果的对比实验。 设置两个数组PAGE和PIF。其中PAGE长度为M-1,保存未来某一段时间内要访问的页号,本文实验算法在处理PAGE数组时,如果PAGE数组个数少于M-1(即待访问页数少于M-1个)时,将不足的个数以0代替; PIF数组长度为N,保存每个页的影响因子。 3.2 置换原则及访问序列模拟方式 以上是页3置换之前的状态,从表1可得当前内存装入页1,页5和页2。如果要访问页3,则表现为缺页,因此要调用置换算法。如果经过计算PIF=[0.1,0.3,0.1,0.1,0.4]。此时PAGE=[4,5]。则页5,和页4在未来一段时间内将被再将访问,因此页3只能和页1或页2进行置换。根据PIF[1](0.1) 实验中访问序列的模拟方式[5]:根据实验条件可知访问序列的样本空间大小为510,通过随机产生方式产生100个样本序列。 4 实验结果与分析 4.1 实验结果 以下是针对随机产生的访问序列W1的实验结果。 W1={1,2,3,4,1,2,5,1,2,3} ,M={2,3,4},此时PIF=[0.3,0.3,0.2,0.1,0.1]。 4.2 实验分析 从表4,表5,表6的数据分析得到如下统计结果。 实验产生100个长度为K=10的访问序列,得出如下统计结果。 由表7,图2,和图3的实验结果可得出,CD置换算法较优于FIFO和LRU置换算法,缺页数相对降低,产生Belady(异常)现象的次数也相对的减少。从整体上看,同一算法不同的M值,得出的结果是M值越大,平均缺页次数减少,这符合一般的正常现象,同样也说明本实验设计较合理。虽然图3显示有一定数量的访问序列产生了Belady(异常)现象,但经比较CD置换算法也能够相对减少产年Belady(异常)现象的概率。 5 实验总结 本文在传统的置换算法中,提出具有诊断功能的置换算法,目的是降低置换次数,减少产生Belady(异常)现象的概率。在算法中涉及到PAGE数组,它是一个变化的数组,每一次的页面访问都会改变PAGE的值,在系统中,可以通过寄存器的方式实现。因此在现实系统中,本文所提供的算法虽然能够达到预期目的,但会增加系统的开销。PIF在算法实现过程中是一个静态的数组,也就是给定了访问序列,则PIF的值将不再变化。在执行某进程中,往往很难判断某页的访问次数,或者说要有很大的成本才能判断访问序列[6]。本文在没有考虑这些因素的影响下,将算法做为一个独立的单元进行考虑研究。希望能够对其他研究者有所帮助。 参考文献 [1]张尧学,史美林,张高.计算机操作系统教程[M].3版.北京:清华大学出版社,2006:129-132. [2]彭青松,丁祥武.一种改进的自适应页面置换算法[J].计算机应用与软件,2011(2):67-70. [3]张玲玲,高林娥.FIFO页面置换算法的实现以及异常问题的讨论[J].科技情报开发与经济,2010,20(13):98-100. [4]张春红.浅谈页面置换算法之LRU算法[J].廊坊师范学院学报.2006,22(4):76-78. [5]蒋飞虎.动态自适应页面置换算法[D].南京:东南大学,2006.页面置换算法模拟实验 篇2
