LRU页面置换算法模拟

1、页面置换算法模拟 -最近最久未使用置换算法 |课程设计 |计算机数据库课程 设计一、设计目的1、用C语言实现最近最久未使用（LRU）置换算法。2、了解内存分页管理策略3、掌握调页策略4、掌握一般常用的调度算法5、选取调度算法中的典型算法，模拟实现二、设计任务在Window98/2000系统的TC2.0环境下运行程序；通过从一般常用的调页 算法中选取典型算法LRU, 了解页面管理的相关细节，并用程序设计实现LRU三、设计内容与步骤分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页 面或页。一、调页策略1）何时调入页面如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相

2、邻的页，会比一次调入一页的效率更高效一些。但如果调入的一批页面中的大 多数都未被访问，则又是低效的。可采用一种以预测为基础的预调页策略，将 那些预计在不久之后便会被访问的页面，预先调入内存。如果预测较准确，那 么，这种策略显然是很有吸引力的。但目前预调页的成功率仅为50%。且这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。2）请求调页策略当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在 内存，便即提出请求，由OS将其所需页面调入内存。由请示调页策略所确定调 入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的 虚拟存储器中，大多采用此策略。但这种

3、策略每次仅调入一页，故须花费较大 的系统开销，增加了磁盘 I/O 的启用频率。2、从何处调入页面在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放 对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离 散分配方式，故对换区的磁盘 I/O 速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下 三种情况：(1) 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以 提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区 拷贝到对换区。(2) 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文 件区调入；

4、而当换出这些页面时，由于它们未被修改而不必再将它们换出时， 以后需要时，再从对换区调入。(3) UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页 面，都从文件区调入。而对于曾经运行过但又被换出的页面，由于被放在对换 区，因此在下次时，应从对换区调入。由于 UNIX系统允许页面共享，因此，某 进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调 入。3 页面调入过程每当程序所要访问的页面未在内存时，便向 CPU发出一缺页中断，中断处 理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。该程序 通过查找页表，得到该页在外在原物理块后，如果此时内存能容纳

5、新页，则启 动磁盘 I/O 将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某 种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页 写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调 入内存，并修改页表中的相应表项，置其存在位 “1，”并将此页表项写入快表 中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地 址，再去访问内存数据。整个页面的调入过程对用户是透明的。二、页面置换算法在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存， 但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出 一页程序或数据，送磁

6、盘的对换区中。但应将哪个页面调出，须根据一定的算 法来确定。通常，把选择换出页面的算法称为页面置换算法 (Page_ReplacementAlgorithms。)一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将 那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调 出。常见置换算法 最佳置换算法 (Optimal) ：它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页 面，将是以后永不使用的或许是在最长 (未来 )时间内不再被访问的页面。采用最 佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进 程在内存的若干个页面中，哪

7、一个页面是未来最长时间内不再被访问的，因而 该算法是无法实现的，便可以利用此算法来评价其它算法。先进先出(FIFO页面置换算法：这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择 在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调 入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指 针，使它总是指向最老的页面。 LRU置换算法：这是本次设计的重点。 CLOCK置换算法：a简单CLOCK置换算法；b,改进型CLOCK算法。LRU 算法是较好的一种算法，而由于 LRU在硬件上要求较多，在实际应用中多采用 LRU的近似算法。CLOCK算法就是用得较多的

8、一种LRU近似算法。 最少使用（LFU:LeastFrequentlyUse（置换算法：在采用该算法时，应为在 内存中的每个页面设置一个移位寄存器骼来记录该页面被访问的频率。该置换 算法选择在最近时期使用最少的页面为淘汰页。 页面缓冲算法 （PBA： PageBufferingAlgorithm）、最近最久未使用置换算法LRU（LeastRece ntlyUse（置换算法的描述FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内 存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预 测各页面将来

9、的使用情况，只能利用 “最近的过去 ”作为“最近的将来 ”的近似，因 此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页 面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其 t值最大的，即最近最久未使用的页面予 以淘汰。2、LRU置换算法的硬件支持LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。 为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何 快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持：1）寄存器为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配

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

11、00000115 / 141001101010100010001010101110101100111100010111 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当 进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈 顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面 号。（三）、程序设计流程图（四儿RU算法实现。#include#include#defineM4#defineN17#defineMyprintfprintf(|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-|n)/* 表格控制 */typedefstruct

12、pageintnum;/* 记录页面号 */inttime;/* 记录调入内存时间 */Page;/* 页面逻辑结构，结构为方便算法实现设计 */PagebM;/* 内存单元数 */intcMN;/* 暂保存内存当前的状态：缓冲区 */ intqueue100;/* 记录调入队列 */intK;/* 调入队列计数变量 */* 初始化内存单元、缓冲区 */voidInit(Page*b,intcMN)inti,j;for(i=0;iN;i+)bi.num=-1;+bi.time=N-i-1;for(i=0;iM;i+)for(j=0;jN;j+)cij=-1;/* 取得在内存中停留最久的页面 ,

13、默认状态下为最早调入的页面 */ intGetMax(Page*b)inti;intmax=-1;inttag=0;for(i=0;imax)max=bi.time;tag=i;returntag;/* 判断页面是否已在内存中 */ intEquation(intfold,Page*b)inti;for(i=0;i=0)bval.time=0;for(i=0;iM;i+)if(i!=val)bi.time+;elsequeue+K=fold;/* 记录调入页面 */ val=GetMax(b);bval.num=fold;bval.time=0;for(i=0;iM;i+)if(i!=val)

14、 bi.time+;/* 主程序 */voidmain()intaN=1,0,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4; inti,j;start:K=-1;Init(b,c);for(i=0;iN;i+)Lru(ai,b);c0i=ai;/* 记录当前的内存单元中的页面 */ for(j=0;jM;j+)cji=bj.num;n);/* 结果输出 */ printf( 内存状态为： Myprintf;for(j=0;jN;j+)printf(|%2d,aj);printf(|n);Myprintf;for(i=0;iM;i+)for(j=0;jN;j+)if(cij=-1)

15、printf(|%2c,32);elseprintf(|%2d,cij);printf(|n);Myprintf;printf(n 调入队列为 :);for(i=0;iK+1;i+)printf(%3d,queuei);printf(n 缺页次数为：6dn 缺页率：16.6f,K+1,(float)(K+1)/N);printf(nAreyoucontinuing!ty?);if(getche()=y)gotostart;四、测试与评价1 、程序运行结果输出内存状态为：|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|1|0|1|0|2|4|1|0|0|8|7|5|4|3|

16、2|3|4|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|1|1|1|1|1|1|1|1|1|1|1|5|5|5|5|5|5|0|0|0|0|0|0|0|0|0|0|0|4|4|4|4|4|2|2|2|2|2|8|8|8|8|3|3|3|3|4|4|4|4|4|7|7|7|7|2|2|2|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| 调入队列为 :1024875432缺页次数为： 10缺页率： 0.588235Areyoucontinuing!y?2、程序执行是稳定的，高效的。在 LRU算法中，要找出最近最久未使用的 页面的话，就必须设置有关的访问记录项，且每一次访问