haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 科学科学

第7次实验2012

发布时间:2013-12-27 10:43:31  

第三章实验-02

请注意:

本次实验最低要求为提交详细算法流程图和步骤说明

第7次 常用页面置换算法模拟实验

1.实验目的

通过模拟实现请求页式存储管理的几种基本页面置换算法,了解虚拟存储技术的特点,掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。

2.实验要求:

1)要求用你熟悉的程序设计语言编写和调试一个页面置换模拟程序;要求在主函数中测试。

2)实验报告中必须包括:设计思想、数据定义(包括详细说明)、处理流程(详细算法描述和算法流程图)、源代码、运行结果、体会等部分。

3)必须模拟本实验内容中提到的算法中的至少2种页面置换算法。

4) 比较不同页面置换算法的效率

3.实验内容

编写一个程序,使用以下页面置换算法中的某2种分别模拟一个分页系统,并统计同一个页面访问序列情况下不同页面置换算法引发的缺页中断次数。

1、第二次机会算法(Second Chance)

2、最近最少使用算法(Least Recently Used,LRU )

3、最不常用算法(Not Frequently Used,NFU)

4、最近未使用算法(Not Recently Used ,NRU)

5、时钟页面置换算法

6、老化算法(aging)

页框的数量固定为4,虚拟页面数为8。实验输入为访问页面序列,比如0,1 ,3 ,2,7,1

4.实验理论参考

1)虚拟存储系统

UNIX中,为了提高内存利用率,提供了内外存进程交换(Swapping)机制;内存空间的分配和回收均以页为单位进行;一个进程只需将其一部分(段或页)调入内存便可运行;还支持请求调页的存储管理方式。

当进程在运行中需要访问某部分程序和数据时,发现其所在页面不在内存,就立即提出请求(向CPU发出缺中断),由系统将其所需页面调入内存。这种页面调入方式叫请求调页。

为实现请求调页,核心配置了数据结构:页表[页框号、访问位、修改位、有效位、保护位等]。

第三章实验-02

2)页面置换算法

当CPU接收到缺页中断信号,中断处理程序先保存现场,分析中断原因,转入缺页中断处理程序。该程序通过查找页表,得到该页所在外存的物理块号[number of page frame页框号]。如果此时内存未满,能容纳新页,则启动磁盘I/O将所缺之页调入内存,然后修改页表。如果内存已满,则须按某种置换算法从内存中选出一页准备换出,是否重新写盘由页表的修改位决定,然后将缺页调入,修改页表。利用修改后的页表,去形成所要访问数据的物理地址,再去访问内存数据。整个页面的调入过程对用户是透明的。

1. FIFO算法

? 原理简述

(1) 在分配内存页面数(AP)小天进程页面数(PP)时,当然是最先运行的AP个

页面放入内存;

(2) 这时又需要处理新的页面,则将原来放的内存中的AP个页中最先进入的调出

(FIFO),再将新页面放入;

(3) 以后如果再有新页面需要调入,则都按上述规则进行。

(4) 算法特点:所使用的内存页面构成一个队列。

? 图表描述

假设某个进程在硬盘上被划分成5个页面(PP=5),以1、2、3、4、5分别表示,CPU调用它们的顺序(这应该取决于进程本身)为:1、4、2、5、3、3、2、4、2、5,如果内存可以控制的页面数为3(AP=3),那么在使用FIFO算法时,这3个页面的内存使用情况应该如图5所示。

图5

不难看出,本例共换入页面8次,若用变量diseffect表示页面换入次数,则diseffect=8。

? 算法实现提示

要得到命中率,必然应该有一个常量total_instruction来记录页面总共使用的次数,此外还需要一个变量记录总共换入页面的次数diseffect(需要换出页面总是因为缺页中断而产生)。利用公式1-diseffect / total_instruction*100% 可以得到命中率。

第三章实验-02

(1) 初始化。设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分

配的页面数,并产生一个随机数序列main[total_instruction](这个序列由page[ap]

的下标随机构成)表示待处理的进程页面顺序,diseffect置0。

(2) 看main[]中是否有下一个元素,若有,就由main[]中获取该页面下标,并转(3),

如果没有则转(7)。

(3) 如果该页已在内存中,就转(2),否则转(4),同时未命中的diseffect加1。

(4) 观察pagecontrol是否占满,如果占满则须将使用队列(在第(6)步中建立的)

中最先进入的(就是队列的第一个单元)pagecontrol单元“清干净”,同时将

page[]单元置为“不在内存中”。

(5) 将该page[]与pagecontrol[]建立对应关系(可以改变pagecontrol[]的标志位,也

可以采用指针链接,总之至少要使对应的pagecontrol单元包含两个信息:一是

它被使用了,二是哪个page[]单元使用的。page[]单元也包含两个信息:对应的

pagecontrol单元号和本page[]单元已在内存中)。

(6) 将用到的pagecontrol置入使用队列(这里的队列是一种FIFO的数据结构),返

回(2)。

(7) 显示计算1-diseffect / total_instruction*100%,完成。

2. LRU算法

? 原理简述

(1) 当内存分配页面数(AP)小于进程页面数(PP)时,把最先执行的AP个页面

放入内存。

(2) 当需调页面进入内存,而当前分配的内存页面全部不空闲时,选择将其中最长

时间没有用到的那一页调出,以空出内存来放置新调入的页面(LRU)。

(3) 算法特点:每个页面都有属性来表示有多长时间未被CPU使用的信息。

? 图表描述

这里采用的例子和前面的一样。假设某个进程在硬盘上被划分成5个页面(PP=5),以1、2、3、4、5分别表示,CPU调用它们的顺序(这应该取决于进程本身)为:1、4、2、5、3、3、2、4、2、5,而内存可以控制的页面数为3(AP=3),那么在使用LRU算法时,这三个页面的内存使用情况应该如图6所示。

不难看出,本例共换入页面7次,若用变量diseffect表示页面换入次数,则diseffect=7。

第三章实验-02

图6

? 算法实现提示

与前述算法一样,只有先得到diseffect才能获得最终的命中率。

(1) 初始化。设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分

配的页面数,并产生一个随机数序列main[total_instruction](这个序列由page[ap]的下标随机构成)表示待处理的进程页面顺序,diseffect置0。

(2) 看序列main[]中是否有下一个元素,如果有,就由main[]中获取该页面下标,

并转(3),如果没有则转(6)。

(3) 如果该page[]单元在内存中便改变页面属性,使它保留“最近使用”的信息,

转(2),否则转(4),同时diseffect加1。

(4) 看是否有空闲页面,如果有,就返回页面指针,并转到(5),否则,在内存页

面中找出最长时间没有使用到的页面,将其“清干净”,并返回该页面指针。

(5) 在需处理的page[]与(4)中得到的pagecontrol[]之间建立联系,同时让对应的

page[]单元保存“最新使用”的信息,转(2)。

(6) 如果序列处理完成,就输出计算1-diseffect / total_instruction*100%的结果,完

成。

3. NUR算法

? 原理简述

所谓“最近未使用”,首先是要对“近”做一个界定,比如CLEAR_PERIOD=50,便是指在CPU最近的50次进程页面处理工作中,都没有处理到的页面。

那么可能会有以下几种

第三章实验-02

情况:

(1) 如果这样的页面只有一个,就将其换出,放入需要处理的新页面。

(2) 如果有这样的页面不止一个,就在这些页面中任取一个换出(可以是下标最小

的或者最小的),放入需要处理的页面。

(3) 如果没有一个这样的页面,就随意换出一个页面(可以是下标最小的或者最大

的)。

算法特点:有一个循环周期,每到达这个周期,所有页面存放是否被CPU处理的信息的属性均被置于初始态(没有被访问)。

? 图表描述

还是用前面的例子,某进程在硬盘上被划分为5个页面,用1、2、3、4、5表示,而处理及处理它们的顺序为:1、4、2、5、3、3、2、4、2、5,而内存可以控制的页面数为3(AP=3),CLEAR_PERIOD取5;在循环周期内,如果所有内存页面均被CPU处理或者有多个页面未被CPU处理,取页码最小的页面换出。算法实现过程如下图:

图7

显示页面交换共6次,disaffect=6。

? 算法实现提示

(1) 初始化。设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分

配的页面数,并产生一个的随机数序列main[total_instruction](当然这个序列由

page[]德下标随机构成)表示待处理的进程页面顺序,diseffect置0,设定循环

周期CLEAR_PERIOD。

(2) 看main[]是否有下一个元素。若有,就从main[]中获得一个CPU

将处理页面的

第三章实验-02

序号;如果没有就转到(8)。

(3) 如果待处理的页面在内存中,就转到(2);否则diseffect加1,并转到(4)。

(4) 看是否有空闲得内存页面,如果有,返回空闲内存页面指针,并转到(5);否

则,在所有没有被访问且位于内存中的页面中按任意规则(或者取最近的一个页面;或者取下标最小的??)取出一个,返回清空后的内存页面指针。

(5) 在待处理进程页面与内存页面之间建立联系,并标注该页被访问。

(6) 如果CPU已处理了CLEAR_PERIOD个页面,就将所有页面均设为“未访问”。

(7) 返回(2)。

(8) 如果CPU所有处理工作完成,就返回1-(disaffect / total_instruction )*100%的结

果,并结束。

6.实验结果示例

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com