实验六页面置换

《实验六页面置换》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验六页面置换算法模拟一、实验目的(1)了解内存分页管理策略(2)掌握调页策略(3)掌握一般常用的调度算法(4)学会各种存储分配算法的实现方法。(5)了解页面大小和内存实际容量对命中率的影响。二、实验预备知识分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页而或页。在进程运行过程屮，若英所要访问的页而不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区屮。但应将哪个页而调出，须根据一定的算法来确定。通常，把选择换岀页面的算法称为页面置换算法(Page_ReplacementAlgo

2、rithms)。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页而换出，或将那些在较长时间内不会再访问的页而调出。1、最佳置换算法OPT(Optimal)它是由Belady于1966年捉出的一种理论上的算法。其所选择的被淘汰页而,将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前述无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。2、先进先出(FIFO)页面置换算法这是最早出现的

3、置换算法。该算法总是淘汰最先进入内存的页而，即选择在内存屮驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页而，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。1)LRU(LeastRecentlyUsed)置换算法的描述FIFO置换算法性能Z所以较差，是因为它所依据的条件是各个页而调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测齐页而将來的使用情况，只能利用“最近的过去”作为“最近的将來”的近似，因此，LRU置换算法是

4、选择最近最久未使用的页而予以淘汰。该算法赋予每个页而-•个访问字段，用來记录一个页面口上次被访问以來所经历的时间t,,当须淘汰一个页而时，选择现有页而小其t值最大的，即最近最久未使用的页而予以淘汰。2）LRU置换算法的硬件支持LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持：①寄存器为了记录某个进程在内存小各页的使用情况，须为每个在内存屮的页而配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3……R2R1Ro当进

5、程访问某物理块吋,要将相应寄存器的叶1位置成1。此时，定时信号将每隔一定时间（例如100ms）将寄存器右移一位。如杲我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如图1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把8个内存页而的序号分别定为1~~8。由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。R7R6R5R4R3R2R1R0101010010210101100300000100401101011511010110600101011700000

6、111801101101②栈可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页而时，便将页而的页而号从栈屮移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。三、实验内容编写程序模拟实现LRU算法(LeastRecently)和FIFO算法(FirstINFirstOut)o先参照LRU算法实现的示例程序，写出实现FIFO算法模拟程序。参考实验步骤如下：(1)现定义数据结构和全局变量。#include#include#defineM4#defineN17#define

7、Myprintfprintf(Hl—+—+—+—F—+—+—+—+—+—F—+—+—+—+—+—+—l")控制*/typedefstructpage{intnum;/*记录页面号*/inttime;/*记录调入内存时间*/}Page;/*页面逻辑结构，结构为方便算法实现设计*/Pageb[M];/*内存单元数*/intc[M][NJ;/*暂保存内存当前的状态：缓冲区*/intqueue[100];/*记录调入队列*/intK;/*调入队列计数变量*/(2)初始化内存单元、缓冲区voidInit(Page*b,intc

8、M

9、[N

10、){inti,j；