失效链接处理 |
内存管理之页面置换算法 PDF 下载
本站整理下载:
相关截图:
主要内容:
一、实验目的
掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。
二、实验内容
◆设计一个虚拟存储区和内存工作区,并使用下述算法计算访问命中率。
1) 最优页面置换算法(Optimal)
2) 先进先出法(First In First Out)
3) 最近最少使用法(Least Recently Used)
4) 最不常使用法(Not Frequently Used)
5) 最近未使用法(Not Recently Used)
其中,命中率=1-页面失效次数/页地址流长度。
试对上述算法的性能加以较各:页面个数和命中率间的关系;同样情况下的命中率比较。
三、实验分析
◆对于虚拟存储区和内存工作区的不同算法,其中主要的流程:首先用srand( )和rand( )函数定义和产生指令序列,然后将指令序列变换成相应的页地址流,并针对不同的算法计算出相应的命中率。
实验可先从一个具体的例子出发。
(1)通过随机数产生一个指令序列,共320条指令。指令的地址按下述原则生成:
A:50%的指令是顺序执行的
B:25%的指令是均匀分布在前地址部分
C:25%的指令是均匀分布在后地址部分
具体的实施方法是:
A:在[0,319]的指令地址之间随机选取一起点m
B:顺序执行一条指令,即执行地址为m+1的指令
C:在前地址[0,m+1]中随机选取一条指令并执行,该指令的地址为m’
D:顺序执行一条指令,其地址为m’+1
E:在后地址[m’+2,319]中随机选取一条指令并执行
F:重复步骤A-E,直到320次指令
(2)将指令序列变换为页地址流
设:页面大小为1K;
用户内存容量4页到32页;
用户虚存容量为32K。
在用户虚存中,按每K存放10条指令排列虚存地址,即320条指令在虚存中的存放方式为:
第 0 条-第 9 条指令为第0页(对应虚存地址为[0,9])
第10条-第19条指令为第1页(对应虚存地址为[10,19])
………………………………
第310条-第319条指令为第31页(对应虚存地址为[310,319])
按以上方式,用户指令可组成32页。
四、编程实现
◆最优页面置换算法(Optimal)
◇基本思想:发生缺页时,有些页面在内存中,其中有一页面很快被访问(也包含紧接着的下一条指令的那页),而其他页面则可能要到10、100或者1000条指令后才会被访问,每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。
◇伪代码实现
void OPT()
{
for(i=0;i<LEN;i++)
{
如果帧已经填满
若在帧中找到该页命中,退出
否则找到最远使用的页面置换
若帧未填满
命中,则退出
否则,加入空闲帧中
}
}
◇运行结果演示
|