实验四+页面置换算法.doc

实验四+页面置换算法.doc

ID:57330554

大小:37.50 KB

页数:4页

时间:2020-08-12

实验四+页面置换算法.doc_第1页
实验四+页面置换算法.doc_第2页
实验四+页面置换算法.doc_第3页
实验四+页面置换算法.doc_第4页
资源描述:

《实验四+页面置换算法.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、页面置换算法模拟实验【实验目的】1)进一步掌握虚拟存储器的工作原理。2)通过实验理解和掌握FIFO,LRU,OPT三种页面置换算法。3)比较各种页面置换算法的优缺点。【实验要求】1)认真阅读和掌握预备知识。2)上机操作。【预备知识】在采用请求分页机制的操作系统中,当运行一个进程的时侯,若所要访问的页面不在内存中而需要把它们调入内存,但此时内存已无空闲空间,为了保证该进程能正常运行,需选择内存中暂时不用的一个页面调出到磁盘交换区。选择调出哪个页面,由页面置换算法决定。页面置换算法的好坏,直接影响着系统的性能。一个好的页面置换算法,应尽可能选择调出较长时间内不会再访问的页面,以保证较低的缺页率。常

2、见的页面置换算法有OPT(最佳置换算法),FIFO(先进先出算法)及LRU(最近最久未使用算法)。一、OPT算法1.原理简述1)在分配内存页面数(B)小于进程页面数(P)时,最先用到的B个页面依次放入内存;2)这时若需要处理新的页面,而当前分配的内存页面全部不空闲时,选择换出以后永远不再使用的页。如没有这样的页面存在,则应选择下次访问距离现在最久的页换出,以空出内存来放置新调入的页面;3)以后如果有新页面需要调入,按“2)”之规则进行。该算法能保证有最低的缺页率,所以称为最佳置换算法。但是该算法仅仅是一种理想状况下的算法,因为在进程实际运行过程中,将来会执行到哪个页是不可预知的,所以无法选择该

3、置换哪个页出去。因此,本算法在实际中无法使用,只能作为一种标准来衡量其他算法的性能。2.图表描述假设某个进程在交换区被分为5个页面(P=5),分别以1,2,3,4,5表示。在该进程运行过程中,处理机调用它们的顺序即页地址流为:2,3,2,1,5,2,4,5,3,2,5,2而系统分配给该进程的内存空间只有3(B=3)个页面,那么在使用OPT算法时,这3个页面的内存使用情况应该是:引用串23215245325222222244422233333333333155555555缺页标记(f)(f)()(f)(f)()(f)()()(f)()()本例共缺页6次,缺页率为6/12。二、FIFO算法1.原理

4、简述1)在分配内存页面数(B)小于进程页面数(P)时,最先用到的B个页面依次放入内存;2)这时若需要处理新的页面,则从当前内存中的B个页面中选择调出最先进入的那个页(所以称为FIFO),然后放入新页面;3)以后如果有新页面需要调入,按“2)”之规则进行。该算法将所使用的内存页面构成一个循环队列,每次置换时将队列中的队首换出,队首指针后移一位即可,算法容易实现。但是最先进入内存的页未必将来就不再用到,甚至可能很快就会用到,所以不能保证有较低的缺页率,算法性能较差。2.图表描述为了便于比较学习,例子和前面的一样。在使用FIFO算法时,这3个页面的内存使用情况应该是:引用串2321524532522

5、2225555333333332222255111444442(f)(f)()(f)(f)(f)(f)()(f)()(f)(f)缺页标记本例共缺页9次,缺页率为9/12。三、LRU算法1.原理简述1)在分配内存页面数(B)小于进程页面数(P)时,最先用到的B个页面依次放入内存;2)这时若需要处理新的页面,而当前分配的内存页面全部不空闲时,选择调出其中最长时间没有用到的那个页面,用空出的内存来放置新调入的页面,所以称为LRU(最近最久未使用)算法;3)以后如果有新页面需要调入,按“2)”之规则进行。该算法根据局部性原理,认为最近一段时间内,最长时间没有用到的那个页将来用到的可能性也很小,所以替换

6、这样的页出去,也能保证比较低的缺页率,其性能接近OPT算法。但是需要有专门的存储单元来记录每个页面有多久未被使用,并且要随时更新该记录,所以算法的开销比较大。2.图表描述:为了便于比较学习,例子和前面的一样。在使用FIFO算法时,这3个页面的内存使用情况应该是:引用串23215245325222222222333333355555555111444222缺页标记(f)(f)()(f)(f)()(f)()(f)(f)()()本例共缺页7次,缺页率为7/12。【实验内容】1)编译opt.c,实现OPT置换算法。(源程序已给)多次执行,查看OPT置换算法的详细置换过程及结果。2)编辑lru.c,实现

7、LRU置换算法。(源程序已给)多次执行exam16b,查看LRU置换算法的详细置换过程及结果。3)代码参照前两个算法自行编写,实现FIFO置换算法。(自行设计,需在报告中给出)编译并多次执行“fifo.c”,查看FIFO置换算法的详细置换过程及结果。4)在一个程序中同时实现OPT,LRU和FIFO三种置换算法。(自行设计,需在报告中给出)编译并多次执行,比较三种置换算法在同一组数据下的运行结果并分

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。