《请求页式存储管理中常用页面置换算法模拟》由会员分享，可在线阅读，更多相关《请求页式存储管理中常用页面置换算法模拟（3页珍藏版）》请在金锄头文库上搜索。
1、请求页式存储管理中常用页面置换算法模拟请求页式存储管理中常用页面置换算法模拟一、实验目的一、实验目的（1）了解内存分页管理策略 （2）掌握调页策略 （3）掌握一般常用的调度算法 （4）学会各种存储分配算法的实现方法。 （5）了解页面大小和内存实际容量对命中率的影响。二、实验内容二、实验内容（1）采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣， 同时也考虑页面大小及内存实际容量对命中率的影响； （2）实现 OPT 算法 (最优置换算法) 、LRU 算法 (Least Recently) 、 FIFO 算法 (First IN First Out)的模拟； （3）会使用某种编程
2、语言。三、实验原理三、实验原理分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。 在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无 空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁 盘的对换区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面 的算法称为页面置换算法(Page_Replacement Algorithms)。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不 再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。 1、最佳置换算法、最佳置换算法 O
3、PT(Optimal) 它是由 Belady 于 1966 年提出的一种理论上的算法。其所选择的被淘汰页面，将是以 后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可 保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一 个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来 评价其它算法。 2、先进先出、先进先出(FIFO)页面置换算法页面置换算法 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻 留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后 次序链接成
4、一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。 3、最近最久未使用置换算法、最近最久未使用置换算法 （1）LRU(Least Recently Used)置换算法的描述 FIFO 置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间， 而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根 据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利 用“最近的过去”作为“最近的将来”的近似，因此，LRU 置换算法是选择最近最久未使 用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所
5、经历的时间 t,，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最久 未使用的页面予以淘汰。 （2）LRU 置换算法的硬件支持 LRU 置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一 个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最 近最久未使用的页面，须有以下两类硬件之一的支持： a）寄存器 为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位 寄存器，可表示为 R=Rn-1Rn-2Rn-3R2R1R0 当进程访问某物理块时，要将相应寄存器的 Rn-1 位置成 1。 此时，定时信号将每隔一定时间(例如 1
6、00ms)将寄存器右移一位。如果我们把 n 位寄存器 的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的 页面。如图 1 示出了某进程在内存中具有 8 个页面，为每个内存页面配置一个 8 位寄存器 时的 LRU 访问情况。这里，把 8 个内存页面的序号分别定为 18。由图可以看出， 第 7 个内存页面的 R 值最小，当发生缺页时首先将它置换出去。 R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 b)栈 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时， 便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号 民，而栈底则是最近最久未使用的页面的页面号。 四、功能测试四、功能测试 （1）FIFO 算法（2）LRU 算法
