试验三模拟操作完整系统的面置换

1、院 系：计 算 机 学 院实验课程： 操作系统实验项目：模拟操作系统的页面置换 指导老师： 陈红英老师开课时间：20112012年度第2学期专业：网络工程班级：10 级学生：yuth学号：*华南师范大学教务处一、综合设计实验题目模拟操作系统的页面置换1、采用一种熟悉的语言，如 C、PASCAL 或 C+ 等，编制程序，最好关键代 码采用 C/C+ ，界面设计可采用其它自己喜欢的语言。 矚慫润厲钐瘗睞枥庑赖。2、模拟操作系统采用 OPT、 FIFO 和 LRU 算法进行页面置换的过程。3、设程序中地址范围为 0 到 32767 ，采用随机数生成 256 个指令地址，满足 50%的地址是顺序执行，

2、 25%向前跳， 25% 向后跳。 聞創沟燴鐺險爱氇谴净。 为满足上述条件，可采取下列方法：设do=1OOOO,第n个指令地址为dn,第n+1个指令地址为dn+i , n的取值范围 为0到255。每次生成一个1到1024范围内的随机数a,如果a落在1到512 范围内，贝U dn+1 =dn+1。如果a落在513到768范围内，则设置dn+1为1到dn 范围内一个随机数。如果a落在769到1024范围内，则设置dn+1为dn到32767 范围内一个随机数。 残骛楼諍锩瀨濟溆塹籟。例如： srand（）; 初始化一个随机函数。a0 = 10*ra nd（）/32767*255+1;a1=10*ra

3、nd（）/32767*a0语句可用来产生 a0与a1中的随机数。或采用以下方式：（1）通过随机数产生一个指令序列，共 320条指令。指令的地址按下述原则生 成：A: 50%的指令是顺序执行的B： 25%的指令是均匀分布在前地址部分C: 25%的指令是均匀分布在后地址部分具体的实施方法是:A :在0 ，31 9的指令地址之间随机选取一起点 mB:顺序执行一条指令，即执行地址为 m+1的指令C:在前地址0,m+1中随机选取一条指令并执行，该指令的地址为m'D:顺序执行一条指令，其地址为 m'+1E:在后地址m'+2，3 19中随机选取一条指令并执行F:重复步骤A-E，直到3

4、20次指令（2）将指令序列变换为页地址流设:页面大小为 1K；用户内存容量 4页到 32页；用户虚存容量为 32K。在用户虚存中，按每 K 存放 10条指令排列虚存地址，即 320条指令在虚存中的存放方式为:第 0 条-第 9 条指令为第 0页（对应虚存地址为 0， 9）第10条-第 19条指令为第 1 页（对应虚存地址为 10， 19）第 310条-第 319条指令为第 31 页（对应虚存地址为 310， 319） 按以上方式，用户指令可组成 32页。4、 页面大小的取值范围为 1K， 2K， 4K， 8K， 16K 。按照页面大小将指令地 址转化为页号。 对于相邻相同的页号，合并为一个。

5、酽锕极額閉镇桧猪訣锥。5、分配给程序的内存块数取值范围为 1 块， 2 块，直到程序的页面数。6、分别采用 OPT、FIFO 和 LRU 算法对页号序列进行调度，计算出对应的缺 页中断率。7、打印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。8、分析页面大小和分配给程序的内存块数对缺页中断率的影响。分析不同 的页面置换算法的调度性能。二、中文摘要这次实验是模拟操作系统的页面置换，分别用先进先出算FIFO、最近最久未使用算法 LRU 和最佳淘汰算法 OPT 等三种置换算法来管理管理内存块， 并打 印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。最后对不 同算法的调度性

6、能。 彈贸摄尔霁毙攬砖卤庑。、关键词页面置换 FIFO LRU OPT四、前言 本实验的目的及要求1、掌握操作系统的页面置换过程，加深理解页式虚拟存储器的实现原理2、掌握用随机数生成满足一定条件的指令地址流的方法。3、掌握页面置换的模拟方法。五、实验设计（一）、需求分析1用一种熟悉的语言，如 C、PASCAL或C+等，编制程序2、分别采用 OPT、 FIFO 和 LRU 算法对页号序列进行调度。二）、设计流程1、根据实验目标，明确实验的具体任务；2、编写程序实现页面置换；3、运行程序，调试；4、记录并分析实验结果。（二）、关键技术根据实验要求， 使得 50%的指令地址是顺序执行， 25%向前跳

7、， 25% 向后跳。 可采取下列方法：设do=10000,第n个指令地址为dn,第n+1个指令地址为 dn+i，n的取值范围为0到255。每次生成一个1到1024范围内的随机数a, 如果a落在1到512范围内，贝U dn+i =dn+1。如果a落在513到768范围内， 则设置dn+1为1到dn范围内一个随机数。如果a落在769到1024范围内，则 设置dn+1为dn到32767范围内一个随机数。开一个数组 address来记录指令地 址，另一个数组pagenum记录指令地址转换后所在的页，这样就得到原始程序 的页面访问序列。然后将相邻相同的页号合并。 謀荞抟箧飆鐸怼类蒋薔。三）详细设计1、设

8、计算法流程图开始程序，提供程序的 地址范围和指令数获取页面大小将程序分页获取程序可用内存块数选择算法进行页面调度结束2、数据结构/程序类，指明程序地址范围和指令数class Programpublic:int AddressSize; / ( OAddressSize int StructureNum;/ 指令数public:Program© nt m,i nt i)AddressSize=m;StructureNum=i;/内存块节点类class PhysicsPageNode public:int have; /是否有页面占领该内存块， -1 代表没有， 1 代表有 int Pa

9、ge_Num;/ 第几页占领该内存块int Elapsed_Time; /内存块的存在时间PhysicsPageNode *next;public:PhysicsPageNode()have=-1;Elapsed_Time=0; /刚生成时内存块的存在时间为 0 next = NULL;/模拟操作系统的页面置换类class PageReplacementprivate:int *address;int *pagenum; float instr_sum; public:/存储所有指令的地址/存储所有指令地址所在的页/指令数int pagesize; int mem_sum; public:/页

10、面大小 (字节)/程序获得的内存块数void transform(Program p); 成员 厦礴恳蹒骈時盡继價骚。/分析程丿予P,得到指令页面丿予列，初始化有关PhysicsPageNode* getphysage(PhysicsPageNode* pp,int pn); 检/ 查指定页是否 已在内存块中 茕桢广鳓鯡选块网羈泪。PhysicsPageNode* getfreepage(PhysicsPageNode*pp); /检查是否有空的内存 块鹅娅尽損鹌惨歷茏鴛賴。PhysicsPageNode* getlongelapsed(PhysicsPageNode* pp); 获/ 得最长

11、时间没访 问的内存块 籟丛妈羥为贍偾蛏练淨。void FIFO(); /先进先出算法void LRU();/最近最久未使用算法void OPT(); /最佳淘汰算法;六、实验实现(一)、实验主要硬件软件环境32 位 PC 机，VC+6.0二)、主要功能模块分析1、获得页号序列模块分析程序指令，获得页面序列。Dn为地址，D0=10000; Dn的地址获取方法： 循环随机一个数 a1,1024;落在 1-512, Dn=D(n-1)+1,513-768, Dn 为 1D(n-1) 的随机数。如果a落在769-1024, Dn为D(n-1)到所分析程序地址大小(32767)。 然后根据页面大小，将各

12、指令地址化为页面号。最后将相邻相同的页号合并。 預 頌圣鉉儐歲龈讶骅籴。/*分析程序, 功能：得到指令页面序列。 入口参数：一个程序类,指明程序地址范围和指令数。*/void PageReplacement:transform(Program p)Sleep(10);srand(time(0);int a,q,r;/初始化instr_sum=p.StructureNum;address = new int instr_sum;/存储所有指令的地址 渗釤呛俨匀谔鱉调硯錦。pagenum = new int instr_sum;cout«"原程序页面链:"<&l

13、t;endl;address0=10000;/指令起始地址pagenum0=address0/pagesize; /指令地址所在的页 cout<<pagenum0<<ends;for(int i=1;i<instr_sum;i+)a = 1 + rand()%1024;if(a<=512)/顺序执行addressi=addressi-1+1;else if(a<=768)/向前跳addressi=1 + rand()%(addressi-1);else if(a<=1024) /向后跳addressi = addressi-1 + ran d()

14、%(p.AddressSize-addressi-1)铙誅卧泻噦 圣骋贶頂廡。/求得指令所在的页q=addressi/pagesize;r=addressi%pagesize;if(r)pagenumi=q;elsepagenumi=q-1;cout<<pagenumi<<ends;/输出指令所在的页面cout<<endl<<endl;/将相邻相同的页号合并int *newpagenum = new int instr_sum;newpagenum0=pagenum0;cout<<" 将相邻相同的页号合并为一个后的页面链 &

15、quot;<<endl;int j=0;for(i=1;i<instr_sum;i+)if(newpagenumj != pagenumi)j+;newpagenumj=pagenumi;instr_sum = j+1; /新的页面访问串的访问数 (j 为下标，所以加一 )coutvv"新的页面访问串的访问数="< <in str_sum<<e ndl;for(i=0;i<instr_sum;i+)pagenumi = newpagenumi;cout<<pagenumi<<ends;/输出指令所在的页

16、面cout<<endl<<endl;2、FIFO 模块 先进先出算法：设置缺页中断次数 breaktimes，当中断发生时，+1.获取可用内存块数，根 据内存块数，申请对应长度的内存块链。然后进行调度。内存块内有一项 Elapsed_Time 作为存在时间，每调用一次，所有内存块得存在时间 +。刚被调 入时间为 1.当要淘汰时，比较在内存块中的各存在时间， 把存在时间最大的换掉。 擁締凤袜备訊顎轮烂蔷。/内存页的存在时间，为存在时间。 void PageReplacement:FIFO() float breaktimes=0;int i,pn;/生成内存页空间Phys

17、icsPageNode *head = new PhysicsPageNode();PhysicsPageNode *p=head,*ppn=NULL;for(i=1;i<mem_sum;i+)mem_su m:程序获得的内存块数PhysicsPageNode *np=new PhysicsPageNode(); p->next=np;p=np;for(i=0;i<instr_sum;i+)pn=pagenumi;ppn=getphysage(head,pn);if(ppn=NULL)/缺页中断次数 +1breaktimes+;/获取空闲页面ppn=getfreepage(h

18、ead);if(ppn!=NULL)/获取成功ppn->Page_Num=pn;ppn->Elapsed_Time=1;/需要载入的页号 （这里还没简化 ）/ 是否存在内存页/ 载入的页不在内存页中else /获取空闲页失败 .置换存在时间最大的页面 ppn=getlongelapsed(head); ppn->Page_Num=pn; ppn->Elapsed_Time=1;else /载入的页在内存页中。/什么也不发生/将在内存中的页存在时间 +1PhysicsPageNode *copp=head; while(copp!=NULL) copp->Elaps

19、ed_Time+; copp=copp->next;/输出算法，页面大小，缺页中断率等。cout<<" 页面大小 ="<<pagesize<<" 内存块数 ="<<mem_sum<<" FIFO 缺页中 断率 ="贓熱俣阃歲匱阊邺镓騷。cout.precision(2);/ 输出小数点后两位cout<<breaktimes/instr_sum<<endl;3、LRU 模块 最近最久未使用页面置换算法( LRU)LRU在固定时间内将各个内存页的存在

20、时间复位，增加计数器counter,每到 30 将所有内存页存在时间复位。并且每使用一次内存页，将是把存在时间减 3 个单位，这样存在时间最大的就是最久未使用的。 坛摶乡囂忏蒌鍥铃氈淚。void PageReplacement:LRU()float breaktimes=0;int i,pn;/生成内存页空间PhysicsPageNode *head=new PhysicsPageNode();PhysicsPageNode *p=head,*ppn; for(i=1;i<mem_sum;i+)PhysicsPageNode *np=new PhysicsPageNode(); p-&g

21、t;next=np;p=np;int counter=0; /计数器for(i=0;i<instr_sum;i+)counter+;/增加计数器counter，每到30将所有内存页存在时间复位。 if(counter>30)counter=0; /计数器归零PhysicsPageNode *q=head;/内存页存在时间复位 while(q!=NULL) q->Elapsed_Time=1; q=q->next;pn=pagenumi;/需要载入的页号ppn=getphysage(head,pn); /是否存在内存页 if(ppn=NULL)/ 载入的页不在内存页中/缺

22、页中断次数 +1 breaktimes+;/获取空闲页面 ppn=getfreepage(head);if(ppn!=NULL) /获取成功 ppn->Page_Num=pn; ppn->Elapsed_Time=1;else /获取空闲页失败 /存在时间最大的为最久未使用。因为每使用一次是减 3 个单位 的存在时间。ppn=getlongelapsed(head);ppn->Page_Num=pn; ppn->Elapsed_Time=1;else /载入的页在内存页中。 ppn->Elapsed_Time=ppn->Elapsed_Time-3;/输出算

23、法，页面大小，缺页中断率等。cout<<" 页面大小 ="<<pagesize<<" 内存块数 ="<<mem_sum<<" LRU 缺页中 断率 =" 蜡變黲癟報伥铉锚鈰赘。cout.precision(2); / 输出小数点后两位 cout<<breaktimes/instr_sum<<endl;4、OPT 模块 最优淘汰算法 OPT50 页，并3 个单位。当页面存在时，存在时间参数不变化。当要淘汰一个页时，预读未来 用内存页的存在时间计数。然后淘

24、汰存在时间最短的。计数方法，未来出现 1 次，将存在时间减 到时候存在时间值最大的将被淘汰。 買鲷鴯譖昙膚遙闫撷凄。void PageReplacement:OPT()float breaktimes=0;int i,pn;/生成内存页空间PhysicsPageNode *head=new PhysicsPageNode();PhysicsPageNode *p=head,*ppn=NULL; for(i=1;i<mem_sum;i+)PhysicsPageNode *np=new PhysicsPageNode(); p->next=np;p=np;for(i=0;i<in

25、str_sum;i+) pn=pagenumi;/ 需要载入的页号ppn=getphysage(head,pn); / 是否存在内存页 if(ppn=NULL) / 载入的页不在内存页中 /缺页中断次数 +1 breaktimes=breaktimes+1;/获取空闲页面 ppn=getfreepage(head); if(ppn!=NULL) /获取成功 ppn->Page_Num=pn; ppn->Elapsed_Time=1;else /获取空闲页失败/在这里增加预读未来 50 个页面计数。 int nextpage=i+1; /从下一页开始算。 int endread=i+

26、50;int nextpagenum;PhysicsPageNode *temp; temp=head;/先复位。while(temp!=NULL)temp->Elapsed_Time=1; temp=temp->next;/下面预读未来页面并计数for(;( (n extpageve ndread )&&(n extpagev=in str_sum); nextpage+)綾 镝鯛駕櫬鹕踪韦辚糴。nextpagenum=pagenumnextpage; temp=getphysage(head,nextpagenum); if(temp!=NULL) temp-&

27、gt;Elapsed_Time=temp->Elapsed_Time-3;ppn=getlongelapsed(head);ppn->Page_Num=pn;ppn->Elapsed_Time=1;else / 载入的页在内存页中。/ 在 OPT 中无需变化。/输出算法，页面大小，缺页中断率等。cout«"页面大小="<vpagesize<v"内存块数="<<mem_sum<<" OPT 缺页中 断率=" ;驅踬髏彦浃绥譎饴憂锦。cout.precision(2);/输出

28、小数点后两位cout<<breaktimes/instr_sum<<endl;5、辅助模块/检查指定页是否在已内存块中PhysicsPageNode* PageReplaceme nt:getphysage(PhysicsPageNode* pp,i nt pn虿驢 绘燈鮒诛髅貺庑。PhysicsPageNode *tmp=pp;while(tmp!=NULL)if(tmp->Page_Num = pn) return tmp;/ 找到对应的页并返回else tmp=tmp->next;return NULL; / 没找到，返回 NULL/检查是否有空的内存

29、块PhysicsPageNode* PageReplaceme nt:getfreepage(PhysicsPageNode* 锹籁饗迳琐筆襖 鸥娅薔。PhysicsPageNode *tmp=pp;while(tmp!=NULL) if(tmp->have = -1) tmp->have=1; return tmp;/找到空的内存块并返回else tmp=tmp->next;return NULL; /没找到，返回 NULL/查找存在时间最长的内存块并返回PhysicsPageNode* PageReplaceme nt:getl on gelapsed(PhysicsPa

30、geNode* pp)頑黉碩 饨荠龈话骛。PhysicsPageNode *tmp=pp,*t=pp;while(tmp!=NULL) if(tmp->Elapsed_Time > t->Elapsed_Time) t=tmp;tmp=tmp->next;24return t;七、结果及结果分析（一）测试数据1、程序中地址范围0327672、页面大小（k）1K，2K，4K，8K，16K3、分配给程序的内存块数1块，2块 直到程序的页面数4、算法OPT、FIFO 和 LRU（二）测试结果记录亍F；鬧的文件吏兽习資氐邈作垂轴I砧傕赠作慕鹼加置換卩4型模拟抿作慈的页面雪換冲e

31、-u m|页面大小YD ：丨页面大小字节）：1024 原程样贡击链：9 13 '1 12 10 10 28 28 1 0 27 27 28 28 28 15 15 20 2 2 3028 28 28 20 11 11 11 1 1 1 1 D 0 13 22 22 22 22 29 29 290 27 30 30 30 30 31 31 31 31 1 1 1 1 1 25 E 8 8 S 8 11 5 31 31 2 2 0 0 3 0 0 0 D 0 31 9 9 9 7 7 2 2131 20 20 20 28 28 29 29 29 23 23 25 J 0 巧8 8 4 4

32、28 28 26 29 29 9 9 9 9 9 17 30 28 11 11 11 20 20 20 20 26 2 2 2 2430 22 3 11 11 20 20 20 2022 2421 250 0 04 3 328 16 25 1 1 1 28 1 ' 2327 31 31 8 9 1 1 1 1 1 031 31 16 30 30 31 25 313 3 23 23 23 30 31 31 3127 30 15 19 015 汩 30 30 30 30 30 吃 18 19 5 22 22 10 10 I 0 10 13 13 28 28 28 28 0 4 1 1 0

33、0 0 0 0 0 0 1 1 1 4 7 2 2 0 0 0 0 9 9將相邻相同的页号合并为一个后的页面链新的页面访问串的访问数打199 13 2 10281 027 2815 26 230 2231 8 9 1 D2730 31 1 25 5 8 145 0 31 16 3031253120316 7 2 2123 30 31 202923 250 15 24 30 181352210842S262S 9 17 3 0 10 13 280 2£ 11 20262 14 7 20 9 5 430 22 3112024 2616 25 1 28 1 23 28013 22 29 2

34、127 30 15 1925 270 30 4 1h=1024日024页面大 页而大£ 页面大h=1024 頁而大小二102 页面大小=1024 页而大小打。24 页面大£ 页而大£1024卜丸24页面大小打024 頁面大h=1024 页而大小=1024 匹面大 页面大£页面大小也24 |頁面天小二1024h=1024h-1024内存块敎=1 FIFO缺页中断率=1 内存块数訂LRU缺页中斷率习 内存块数R OPT缺贡中斷率习 内存块数二2 FIFO缺页中斷$=0.97 内存块数吆LRU抉页断率=0.98 内存决数吆FT缺页中断率叩竹 内存块数丸FIFO

35、缺页中断率 內存块数总LRU缺页中断率=0.98 内存块数总OPT缺頁中斷率和.82 内存块数=4 FIFO缺页中斷率二）92 内存决数二4 LRI缺页中断率二0,畀 内存块数謁OPT缺頁中断率=0.71 内存块数巧FIFO缺页中斯率弍.88 内存块数巧LRU缺贡中断率勿.9 内存块数二5 OPT缺贡中断率=0.67力 彳彳彳 彳诃彳彳彳孙 彳彳诃力 力 / 大大大大-4-/-.大大大大大大大大大大±大大大大大大大大大大大大大大大大大大 面面而而而E面而而面而面面而而面面而而而而面面面而而而而面面而FSE面 a戸页頁頁页页页页贡f：伐的丈件赳学习资糾1隈惟累绽仙出槿拟燥作歸的页面置熒

36、d出旳鴻扌缶作垂统的页直琶揍，“丁旦阳卜二1024内存块数为OPT缺灵中断率二山外 21024内存块数曲FIFO缺頁中断率=0.82 21024内存块敏弋LRLI缺页中断率=0.82 1024内存块敎呀OPT缺页中断率=0.61 h=1024内存块数叩FIFO缺贡中斷率=0.79 迄1024内存块数打LRU缺灵中斷率=0.76 h=1024内存块数可OPT缺頁中断率=0.59 21024内存块数吧FIFO戟頁中断率=0.77 Z1024内存块数总LRU缺頁中断$=0.74 21024内存块数总OPT缺页口断率=0.58 眉1Q24内存块数内FIFO缺页中斷率=0,76 w1024内存块数为LR

37、U缺頁中斷率=0,72 h=1024内甘块数叩OPT缺页中断率二CL5 21024内存块®=10 FIFO缺页申断率叫血 X1024内存块敎=10 LRU缺则K=0.7 b-1024内存块数訂0 OPT缺贡申斷率电 迄1024内存块S = H FIFO袂页中斷$=0.66 h=1024内祥块数二11 LRU缺页中斷率二0+陆 1024内春块ft=11 OPT缺页中断率=0.44 21024内存块ft=12 FIFO映页中断率叩.茨 h=1024内存块数=12 LRU缺页中斷率=0.01 h=1O24内存块» = 12 OPT缺页中斷率=0,41 1024内存块数二1$ FI

38、FO缺页中断率 21024内存块S=13 LRU缺瓦中断率=0.59 S=1024内祥块ft=13 OPT録頁中斷率=0.38 024内存块数=14 FIFO缺页中斯率叩用 21024内存块数叮4 LRU缺页中斷率=0.58 N=1024内存块数二14 OPT敬頁中ff*=0.34 b=1024内存块数二15 FIFO缺頁中斯率叩旺 S=1024内祥块®=15 LRU秋贝中断率=0.55 21024内存块敎二巧OPT缺页中断率=0.34 M1024内存块亂1B FIFO缺页中斯率05 S=1024内存块ft=16 LRU缺页中斷率=0.52 =1024内存块數二IE OPT缺贡中斷率

39、033页页贡页页1頁页页页页頁頁贡页页页頁页页页页贡页页页页頁贡页页页页Exxxxxxxxx-xxxxxxxxxx力力 力 力力 力 力 Jd d 力M 力大大大大4-八大大大大大丈大大大大大大大大大大大大大大大大大大大大大大大m m m-E印一卬-m-m一卬一DD-DD-m-m-mffi一卬-E.-卬-ml卬-DD十m-m-ffl-mag-卬 m m一m-EI-ro.卬-DD1024 1024 1024 1024 102 1024 1024 1024 1024 102 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 10

40、24 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024內存块数=17 FIFO诀页中断率*5 内存块fi=17 LRU缺页中断率叽5 内存块敎=17 OPT缺页中斷率=0.32 内存块数R8 FIFO缺页中斯率勿.48 内存块»=1S LRLI峽觅中斷率=0.49 内存块数二怡OPT缺页中断率4U 内存块数=19 FIFO袂页中断率刃.43 内存块ft=19 LRU缺贡中断率=0.47 向存块数我OPT缺页申断率=0.29 内存块S=20 FIFO缺页中断率詬.芻 内存块数二20 LRU缺页中斷率=0.45 内存块ft =20 OPT

41、缺頁中断率=0.29 内存块数一?1 FIFO缺页中断率-0.炭 内存块数=21 LRU缺頁中断率=0.43 内存块数叨OPT缺页审斷$=0.28 内存块&=22 FIFO缺页中斷率O冊 內存块数二22 LRU缺页中断率勿.39 内存块ft=22 OPT缺頁中断率=0.27 内存块数吆纟FIFO缺页中断率叩.芻 内存块数龙纟LRU缺页中斷率=0.37 内存块ft=23 OPT缺页中斷率=0.27 内存块数=24 FIFO缺页中断$=0,34 内存块ft=24 LRU缺页中斷率=0.37 内祥块ft=24 OPT缺页中断率叩”冗 内存块数垃5 FIFO缺页中断率叩.别 内存块数垃5 LR

42、U缺页中斷率=0.36 内存块数龙5 OPT峡贡中斷率=0.26 内存块数=26 FIFO缺页中断=0.34 内存决数=26 LRI缺页中断率二0戲 内存块敎吆& OPT缺页中断率=0.26 内存块数吆7 FIFO缺页中斯率叩.34 内存块数吆7 LRU缺页中斷率=0.31 内存块数二27 OPT缺贡中断$=0.26大大大大大大大大大大大大大大大天 -j-rj 一m_ 一 |-n-| 一- 一 一 j-n- 一 .1-1 - IrT 一 一 j-nj 頁页页页页页頁页页页页頁页贡页页页m大小(k) :2页而大小(宇节):2048原程序页面链：4 5 4 44 2 2 0 0 15 7

43、7 7 6 6D911 11 3 211111131312111415 15 15151515 1500 吁14 14 14 M 11 13 14 15 5 5 5 4 0 0 00 0 0 12121388 815 15151515 3 3 20 0 000 80144533333366111155211 11 11 1312155815152 22155861582 12 12 2 7 0 10 0 0 0 0 0 1 1 1 1 1 10 0 0 0 0 015 15 15 15 15 15 15 15 10 10 10 10 10 10 10 11 9111OO2 1OS2222OO8

44、S8038S11H1411 10 10 7 7 3 2 3 3 1 1 S 8 8 8 10 10 15 15 7 ? 76 11 14 10 9 15 15 1I5 15 '1 0 0 0 D 0 0 0 0 15 1515 15 11 11 14 14 14 14 14 15 15 15 15 0 1 14 U 115 15 15 & S 8 14 14 15 5 13 13 W 14 11 11 11102内存块数二27 CR缺頁中斷率二0*西 1024內存块数二空FIFO诀页中断#=0.31 1024内存块®=28 LRU缺页中斷率=0.29 1024内存块敎

45、=空OPT峽页中斷率=0.26 1024内存块数垃9 FIFO缺页中断率胡.2$ 1024内存块ft=29 LRU璇页中斷率=0.28 1024内存块数吃目OPT缺贡中斷率4J.2B 1024内存块ft=30 FIFO快瓦中断率叩.27 1024内存块ft =30 LRU缺贡申断率=0.28 1024内存块数颈OPT缺页中断率=0.26 1024内存块數总1 FIFO統页中断率詬.2E 1024 内存块»=31 LRU 缺页中Cr$=0.26 1024内甘块数二31 OPT缺頁中断率=0.26 1024内存块®=32 FIFO缺页中断率叫加 1024内存块数=32 LRU缺

46、贝申断率=0.26 1024内存块数总2 OPT缺页中斷率=0.29将相邻相同的页号合并为一个后的页面链新前贡面访问串前希问数；1.1 e+0024 5 4 2 0 15 7 6 12 2 12 2 7 0 10 0 1 0 9 11 3 2 11 4 13 12 15 10 11 9 11 14 15 0 5 1 02 10 8 2 0 3 11 14 11 13 14 15 5 4 S 11 10 7 3 2 3 1 3 10 15 7 0 12 13 8 15 6 11 14 ID 9选走5伐的丈件丸I学习贸臥換惟崇徹bb率赠乍墓烷的页面置熒氐b旳鴻菲抿作壶的页面亟，住戸也* 鼻MM;血

47、 *15 34811 10 7 3 2 3 1 & 13 15 7 0 12 13 £ 152 0 8 14 15 11 14 15 0 4 14 5 3 6 11 5 2 8 15 8 14 15 5 13 14 11 13大丈大大大大大犬大大大大大大大大大大大大大大大大大大大. 一 丁- 一m_ - IT-r 一 l-r 一 - 一 j-nj 一 TTj 一 ll-f- 一m_ 一 一 - j-rj 一 熨页页頁页页页页贡頁贡页页页贡页页贡页页页页頁贡页大*大-而而m页页贝2048204820482048204820482018创翻2043204820482048即翻20

48、4820432048卸枢2043204820482048204820482048204820482048201820482048内存块敎打FIFO缺页中断率=1 内存块数习LRU缺页口断率訂 内存块数R OPT缺頁中斷率习 内存块数=2 FIFO缺页中斷率二Q.9 内存块数=2 LRU缺页=断率二丄畀 内存块数吆OPT缺頁中断率即出1 内存块数崙FIFO缺页中断率=0.8 内禅块數总LRU缺贝中断率-0.80 内存块数二3 OPT缺頁口斷率L7 内存块数二4 FIFO缺頁中断率=0.73 内存块敕=4 LRU缺页中断率=0,86 内存块数=4 OPT缺頁中断率=0.62 内存块数盯FIFO缺页

49、中斷率=0.75 内存块数无LRU缺灵中斷率=0,74 内存块数二5 OPT缺页中断率=0.51 内存块数疇FIFO軼頁中断率二0二 内存块数弋LRU缺页中断率 内存块数W OPT缺页断率=0.44 内存块数即FIFO缺页中斷率=0.58 内存块数二7 LRU缺贡中斷率=0 + 68 内存块數即OPT恢页中断率=0 + 38 内存块数听FIFO缺頁中断率=0.55 内存块数器LRU缺页口斷率=0.57 内存块数据OPT缺页中断率=0.34 内存块数二9 FIFO缺页中断率=0.49 內存块数=9 LRU缺贡口断=0.53 内存块数二9 3PT缺页中断率二0,芟 内存块敎二10 FIFO峡页申斷

50、率=0.44 内存块数訂0 LRU缺贞中断率弍,5 内存块ft=10 OPT缺页中斷率=0.29 内存块数二1】FIFO缺页中斯$=0,35选走"F；熾的文件交I学习資乌惬惟系锹I品槿蜩作枣统的页面置多:.Bbu気蟆祗抿乍垂筑比页直更按心,JnJ Jd大大大大4-八大大大大大丈大大大大大大大 面面面而面面面ffl而面面面面而面面IS面 一页页页页页页页页页页页贡页页页页页贡数数数数数数数数数数数数数数数数数数 良 hr- hr- -tv 艮-f hr- hr- y 良 k k hr-克艮上 n存存存存存存存存存存存存存存存存存 内内内内内内内内内闻九内-内那曲內 8888888888

51、88388088 44413144444444444444 o o o o o o o oooooooooo O 22222222222222222211 FIFO缺页中断率活.篦 LRU缺贡中断率=0.37 OPT録頁中斷率=0.26 FIFO缺页中断率叩.处 LRU缺贞中斷率=0.33 OPT缺页中断率=0.24 FIFO抉页中断率叩.31 LRU缺頁中断率=0.31 OPT缺页中断率卫 FIFO缺页中断率询.29 LRU缺页申断率=0,25 OPT缺贡中斷率勿*2 FIFO抉页中断率二h吃 LRU缺頁申断率叩.19 OPT缺頁申断率=0,17 FIFO統页中断率詢.15 LRU谀頁中斷率

52、=0J5 OPT1111121212131313141414151515161616缺頁中断率二0.15页而大小你）：4页面大爪（字节）:4096悴程序页面链2 2 222110073333351166130500000000000000000045 5 1155266877 7 ? 7 7 7 777 5 5 5 5 5 5 5 5 4 5 7 7 7 7 ? 7 7 7 0 0 2 2 200 0 0015411110044444445777777567722224455533'11 1 004445577 3 3 3 D 0 000 0 6 6 6 O 4 7 7 7 3 3 5

53、 7 5 4 7 7 7 7 5 0 0000000777771110000044777775577777777702777211 1 1 1 13 3 5 5 2 2 1 1 1 4 7 7 7 4 4 4 7 7 7 2 6 6 7 7 5 5 5 5 5 5 5 6将相邻相同的页号合并为一个后的页面链 新前贡面访问串前谆问数啖2 10 7 3 6 16 13 0 5 0 4 5 15 2 6 7 5 4 5 7 0 2 0 15 4 10 4 5 7 5 6 7 2 4 5 3 104573064735754750710475702721352M7472&756大大±大

54、大大大大犬大大大大±大大大大大大大大大大 一m_ 一 |-n-| - |-Trrj -1 一 - - 11-1 一 j-nj 一 TTj .1.- 一 l-r 十 .-rj -Irr - |wr-| 虫页页页頁页页页页瓦页页页页贡贡页页页页页页页页4 5 7 3 0 6 4 7 3 5 7 >: 4 7 5 0 7 1 0 4 7 5 / 02 1 3 5 2 1 4 7 4 / 2 6 7 5 6 4096内存块数二1 FIFO缺頁中斷率二1 4096内存块数=1 LRU缺页中断率打 4096内存块数訂OPT缺页中斷率习 4096内存块数垃FIFO録觅中断率=0,34 4096内存块数二2 LRU缺頁口断率=0.87 4096内存块数二2 OPT缺页断率"74 4096内存块敕昭FIFO缺贡中断率=0.72 4096内存块数需LRU缺页口断率=0.71 4096内存块數总OPT缺灵中断率=0,55 4096内存块数詔FIFO缺觅中斷$=0.64 4096内存块数二4 LRU缺