《实验四+页面置换算法》由会员分享，可在线阅读，更多相关《实验四+页面置换算法（4页珍藏版）》请在金锄头文库上搜索。
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（B3）个页面，那么在使用OPT算法时，这3个页面的内存使用情况应该是：引用串23215245325222222244422233333333333155555555缺页标记( f)（f）（ ）（f）（f）（ ）（f）（ ）（ ）（f）( )( )本例共缺页6次，缺页率为6/12。二、F
4、IFO算法1.原理简述1）在分配内存页面数（B）小于进程页面数（P）时，最先用到的B个页面依次放入内存；2）这时若需要处理新的页面，则从当前内存中的B个页面中选择调出最先进入的那个页（所以称为FIFO），然后放入新页面；3）以后如果有新页面需要调入，按“2）”之规则进行。该算法将所使用的内存页面构成一个循环队列，每次置换时将队列中的队首换出，队首指针后移一位即可，算法容易实现。但是最先进入内存的页未必将来就不再用到，甚至可能很快就会用到，所以不能保证有较低的缺页率，算法性能较差。2.图表描述为了便于比较学习，例子和前面的一样。在使用FIFO算法时，这3个页面的内存使用情况应该是：引用串2321
5、5245325222225555333333332222255111444442缺页标记(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，实现LRU置换算法。（源程序已给） 多次执行exam16b，查看LRU置换算法的详细置换过程及结果。3）代码参照前两个算法自行编写，实现FIFO置换算法。 （自行设计，需在报告中给出）编译并多次执行“fifo.c”，查看FIFO置换算法的详细置换过程及结果。4）在一个程序中同时实现OPT，LRU和FIFO三种置换算法。（自行设计，需在报告中给出）编译并多次执行，比较三种置换算法在同一组数据下的运行结果并分析其原因。
