没有合适的资源?快使用搜索试试~ 我知道了~
页面置换算法的设计.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 89 浏览量
2022-05-06
14:20:57
上传
评论
收藏 91KB DOC 举报
温馨提示
试读
13页
页面置换算法的设计.doc
资源推荐
资源详情
资源评论
页面置换算法
一.题目:编写程序实现)先进先出页面置换算法()
)最近最久未使用页面置换算法()
)最佳置换页面置换算法()
专题:设计一个虚拟存储区和内存工作区编程序演示以上三种算法的具体实
现过程并计算访问命中率。
二.任务:根据标题提出任务,要简明扼要。
1. 演示页面置换的三种算法。
2. 通过随机数产生一个指令序列,
3. 将指令序列转换成为页地址流。
4. 计算并输出下述各种算法在不同内存容量下的命中率。
(1)a先进先出的算法(FIFO);
(2)a最近最少使用算法(LRU);
(3)a最近最不经常使用算法(NUR);
三.思想:对任务进行构思和设想
问题描述及设计思想:
在进程运行过程中,若其所要访问的页面不在内存需把它们调入内存,但
内存已无空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一
页程序或数据,送磁盘的对换区中。但应将哪个页面调出,所以需要
根据一定的算法来确定。以下分别是 三个算法的设计思想:
:最佳置换算法。其所选择的被淘汰页面,将是以后永不使用的,
或是在最长(未来)时间内不再被访问的页面。
:先进先出置换算法。该算法总是淘汰最先进入内存的页面,既选择在
内存中驻留时间最久的页面予以淘汰。
:最近最久未使用置换算法。
该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问
以来所经历的时间 ,当须淘汰一个页面时,选择现有页面中其 值
最大的给予淘汰。
2.程序设计及实现过程
先产生一串随机数放在数组中,然后输出这个数组,表示页面号引用串.然后
进行计算a并输出结果.这里我使用了一个数组来存放当前内存的页面号,当产生
新的页面申请时,判断数组中有与之相同的数吗,若有则直接输出这个数组,若没
有则舍去最下面的数让上面的数依次放在下面,把新产生的数放在最上面.然后
在数据下面输出一个*号,代表发生了缺页中断.
3.各算法优缺点
FIFO 算法总是选择在内存驻留时间最长的一页将其淘汰。这种算法基于 CPU 按线性顺序
访问地址空间的这个假设上,许多时候,CPU 不是按线性顺序访问地址空间的。所以,那
些在内存中停留时间最长的页往往经常被访问到。这就造成 FIFO 算法的缺页率不太理想。
并且它还有—个缺点:Belady 奇异现象。实现 FIFO 算法无需硬件提供新的帮助,只采用
循环数组管理驻留集即可。OPT 算法被誉为“最优算法”,因为它淘汰下次访问距当前最远的
那些页中序号最小的一页。一所以,OPT 算法得出的缺页率是最小的。但是,OPT 算法在
使用前必须预先得知整个访问串,这很难付诸实现。因此,OPT 算法只是一种概念中的算
法,目前无法实现。LRU 算法的实现耗费较高,并且需要硬件的支持,但是效果较好。就
缺页率而言,OPT 算法最佳,LRU 算法次之,FIFO 最差。
四.目的:
设计目的:
() 了解页面置换的概念。
() 理解页面置换的算法。
() 加深对页面置换算法的理解,锻炼知识的运用能力和实践能力。
学习计算机软件技术,特别是计算机操作系统技术,除了需要刻苦努力外,还需要掌握软件和操
作系统的原理与设计技巧。本设计木的是通过请求页式存储管理中页面置换算法模拟设计,了解虚拟
存储技术的特点,掌握请求页式存储管理的页面置换算法。
页面置换算法aa
(1)aa最佳置换算法:a
它是由 于 年提出的一种理论上的算法。其所选择的被淘汰页面,将是
以后永不使用的或许是在最长未来时间内不再被访问的页面。采用最佳置换算法,通
常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中,
哪一个页面是未来最长时间内不再被访问的,因而该算法是无法实现的,便可以利用此
算法来评价其它算法。a
(2)aaaa先进先出页面置换算法:a
这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选在
内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页
面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老
的页面。a
() 置换算法:这是本次设计的重点。a
置换算法描述
置换算法性能之所以较差,是因为它所依据的条件是各个页面调入内存的时间,
而页面调入的先后并不能反映页面的使用情况。最近最久未使用()置换算法,是根
据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况,只能利
用“最近的过去”作为“最近的将来”的近似,因此, 置换算法是选择最近最久未使用的
页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来
所经历的时间 ,当须淘汰一个页面时,选择现有页面中其 值最大的,即最近最久未使
用的页面予以淘汰。a
、 置换算法的硬件支持a
置换算法虽然是一种比较好的算法,但要求系统有较多的支持硬件。为了了解一个
进程在内存中的各个页面各有多少时间未被进程访问,以及如何快速地知道哪一页是最近
最久未使用的页面,须有以下两类硬件之一的支持:a
)a寄存器a
为了记录某个进程在内存中各页的使用情况,须为每个在内存中的页面配置一个移位寄存
器,可表示为a
!"
!"
!"
##
$
当进程访问某物理块时,要将相应寄存器的 !" 位置成 。此时,
定时信号将每隔一定时间例如 $$%将寄存器右移一位。如果我们把 ! 位寄存器的数看作是
一个整数,那么具有最小数值的寄存器所对应的页面,就是最近最久未使用的页面。如图 示
出了某进程在内存中具有 & 个页面,为每个内存页面配置一个 & 位寄存器时的 访问情况。
这里,把 & 个内存页面的序号分别定为 ˜˜&。由图可以看出,第 ' 个内存页面的 值最小,当
发生缺页时首先将它置换出去。a
栈a
可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时,便将页面的页
面号从栈中移出,将它压入栈顶。因此,栈顶始终是最新被访问页面的编号民,而栈底则是最近最久未
使用的页面的页面号。
五.方案:对构思的细化,提出粗略的方案
调页策略a
何时调入页面a
如果进程的许多页是存放在外存的一个连续区域中,则一次调入若干个相邻的页,会比
一次调入一页的效率更高效一些。但如果调入的一批页面中的大多数都未被访问,则又是低
效的。可采用一种以预测为基础的预调页策略,将那些预计在不久之后便会被访问的页面,
预先调入内存。如果预测较准确,那么,这种策略显然是很有吸引力的。但目前预调页的成
功率仅为 ($)。且这种策略主要用于进程的首次调入时,由程序员指出应该先调入哪些页。
a
请求调页策略a
当进程在运行中需要访问某部分程序和数据时,若发现其所在的页面不在内存,便即提出
请求,由 * 将其所需页面调入内存。由请示调页策略所确定调入的页,是一定会被访问的,
再加之请求调页策略比较易于实现,故在目前的虚拟存储器中,大多采用此策略。但这种策
略每次仅调入一页,故须花费较大的系统开销,增加了磁盘 + 的启用频率。a
从何处调入页面a
在请求分页系统中的外存分为两部分:用于存放文件的文件区和用于存放对换页面的对换
区。通常,由于对换区是采用连续分配方式,而事件是采用离散分配方式,故对换区的磁盘
+ 速度比文件区的高。这样,每当发生缺页请求时,系统应从何处将缺页调入内存,可分成
如下三种情况:a
,,,系统拥有足够的对换区空间,这时可以全部从对换区调入所需页面,以提高调页速
度。为此,在进程运行前,便须将与该进程有关的文件,从文件区拷贝到对换区。a
,,,系统缺少足够的对换区空间,这时凡是不会被修改的文件,都直接从文件区调入;
而当换出这些页面时,由于它们未被修改而不必再将它们换出时,以后需要时,再从
对换区调入。a
,,,-. 方式。由于与进程有关的文件都放在文件区,故凡是未运行过的页面,都从文
件区调入。而对于曾经运行过但又被换出的页面,由于被放在对换区,因此在下次时,
应从对换区调入。由于 -. 系统允许页面共享,因此,某进程所请求的页面有可能
已被其它进程调入内存,此时也就无须再从对换区调入。a
页面调入过程a
每当程序所要访问的页面未在内存时,便向 / 发出一缺页中断,中断处理程序首先保留 / 环
境,分析中断原因后,转入缺页中断处理程序。该程序通过查找页表,得到该页在外在原物理块后,
如果此时内存能容纳新页,则启动磁盘 + 将所缺之页调入内存,然后修改页表。如果内存已满,则须
先按照某种置换算法从内存中选出一页准备换出;如果该页未被修改过,可不必将该页写回磁盘;但
如果此页已被修改,则必须将它写回磁盘,然后再把所缺的页调入内存,并修改页表中的相应表项,
置其存在位“”,并将此页表项写入快表中。在缺页调入内存后,利用修改后的页表,去形成所要访问
数据的物理地址,再去访问内存数据。整个页面的调入过程对用户是透明的。
六.框图
页面置换算法流程图
剩余12页未读,继续阅读
资源评论
老帽爬新坡
- 粉丝: 83
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功