[请求页式存储管理中常用页面置换算法模拟.ppt

一、实验目的 （1）了解内存分页管理策略 （2）掌握调页策略 （3）掌握一般常用的调度算法 （4）学会各种存储分配算法的实现方法。 （5）了解页面大小和内存实际容量对命中率的影响。 二、实验内容 （1）采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响； （2）实现OPT 算法 (最优置换算法)?、LRU 算法 (Least Recently)?、 FIFO 算法 (First IN First Out)的模拟； （3）会使用某种编程语言 三、实验原理 分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。 在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出 1、最佳置换算法OPT(Optimal) 2、先进先出(FIFO)页面置换算法 3、最近最久未使用置换算法 先进先出(FIFO)页面置换算法 开始 i++ 结束 最佳置换算法OPT(Optimal) 结束 最近最久未使用置换算法 LRU 结束 FIFO 算法实现比较简单总是淘汰最先进入内存的页面。只需把进程中已调入 内存的页面按先后次序链成一个队列并设置一个所谓的替换指针使它总是 指向内存中最老的页面。缺点效率不高因为它与进程实际的运行规律不相适应比如常用的全局变量 所在的页面或者循环体所在页面都可能被它选为淘汰对象。出现 bleady 现象。 LRU 算法的性能接近于最佳算法但实现起来较困难。因为要找出最近最久未 使用的页面必须为每一页设置相关记录项用于记录页面的访问情况并且每 访问一次页面都须更新该信息。这将使系统的开销加大所以在实际系统中往往 使用该算法的近似算法。 OPT 算法实际上无法实现采用这种算法会保证最低的缺页率但它是无法实 现的因为它必须知道页面 “ 将来 ” 的访问情况。不过该算法仍有一定意义可 作为衡量其他算法优劣的一个标准。