操作系统页面置换算法详解（附测试代码）_页面置换算法代码

页面置换算法是虚拟存储管理实现的关键，其中，FIFO、LRU和OPT是几种常用的页面置换算法。

先进先出(First In First Out, FIFO)

1) 原理简述

(a) 在分配内存页面数(AP)小于进程页面数(PP)时,当然是最先的AP个页面放入内存。

(b) 这时若有需要处理新的页面,则将原来在内存中的AP个页面中最先进入的调出(所以称为FIFO),然后放入新页面。

(c) 以后如果有新页面需要调入,按(b)的规则进行。

算法特点是,所使用的内存页面构成一个队列。

2) 图表描述

假设某个进程在硬盘上被化为5个页面(PP=5),以1、2、3、4、5分别表示,而下面是处理机调用它们的顺序(这取决于进程本身)。

1、4、2、5、3、3、2、4、2、5

而内存可以控制的页面数为3(AP=3),那么在使用FIFO算法时,这3个页面的内存使用情况如图所示。

 

3) 算法实现提示

要得到“命中率”,必然应该有一个常量 total_instruction记录页面总共使用次数;此外需要一个变量记录总共换入页面的次数(需要换出页面,总是因为没有命中而产生的)diseffect。利用公式1-(diseffect/total_instruction)×100%可以得到命中率。

(a) 初始化。设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分配的页面数,并产生一个随机数序列main[total_instruction](当然这个序列由page[]的下标随机构成),表示待处理的进程页面顺序, diseffect置零。

(b) 观察main[]中是否有下一个元素。如果有,则由main[]中获取该页面下标,并转(c);如果没有,则转到(g)。

(c) 如果该page已在内存中,就转到(b);否则转到(d),同时未命中的 diseffect加1。

(d) 观察 pagecontrol是否占满,如果占满,需将使用队列[(f)中建立的]中最先进入的(就是队列第一个单元) pagecontrol单元“清干净”,同时将对应的page[]单元置为“不在内存中”。

(e) 将该page[]与 pagecontrol[]建立关系(可以改变 pagecontrol[]的标示位,也可以采用指针连接。总之,至少要使对应的 pagecontrol单元包含两个信息:一是它被使用了，二是哪个page[]单元使用的;page[]单元包含两个信息,即对应的 pagecontrol单元号、本page[]单元已在内存中)。

(f) 将用到的 pagecontrol置入使用队列(这里的队列是一种先进先出的数据结构不是泛指),返回(b)。

(g) 显示1-(disaffect/total_instruction)×100%,完成。

最近最久未使用(Least Recently Used, LRU)

1) 原理简述

(a) 在分配内存页面数(AP)小于进程页面数(PP)时,当然是最先的AP个页面放入内存。

(b) 当需要调页面进入内存,而当前分配的内存页面全部不空闲时,选择将其中最长时间没有用到的那个页面调出,以空出内存来放置新调入的页面(因而称为LRU)。

算法特点是,每个页面都有属性表示有多长时间未被CPU使用的信息。

2) 图表描述

为了便于比较学习,例子和前面的一样。某进程在硬盘上被划为5个页面,用1、2、3、4、5表示,而处理机处理它们的顺序为:

1、4、2、5、3、3、2、4、2、5

而内存可以控制的页面数为3(AP=3),那么在使用LRU算法时,这3个页面的内存使用情况如图所示。

页面换入共7次，diseffect=7。

3) 算法实现提示

与前述算法一样,只有先得到 diseffect,才能获得最终的“命中率”。

(a) 初始化。主要是进程页面page[]和分配的内存页面 pagecontrol[],同时产生随机序列main[], diseffect置零。

(b) 观察main[]是否有下一个元素,如果有,就从main[]获取该page[]的下标,并转到(c);如果没有,就转到(f)。

(c) 如果该page[]单元在内存中便改变页面属性,使它保留“最近使用”的信息,就转到(b);否则转到(d),同时 diseffect加1。

(d) 判断是否有空闲的内存页面,如果有,返回页面指针,转到(e);否则,在内存页画中找出最长时间没有使用到的页面,将其“清干净”,并返回该页面指针。

(e) 将需处理的page[]与(d)中得到的 pagecontrol[]建立联系,同时需让对应的page[]单元保存“最新使用”的信息,返回(b)。

(f)如果序列处理完成,就输出1-(disaffect/total_instruction)×100%,并结束。

最佳置换(Optimal replacement, OPT)

1) 原理简述

前提还是在分配的内存页面占满的情况下。最佳置换法是一种理想状况下的算法,它要求先遍历所有的CPU待处理的进程页面序列(实际上由于待处理的页面有时取决于先前处理的页面,所有很多情况下不可能得到完整的待处理页面序列。在这个层面上,才说该算法是理想的),在这些页面中,如果有已经在内存当中,而CPU不再处理的,就将其换出;如果页面在内存中,并且CPU待处理,就取从当前位置算起,最后处理到的页面,将其换出，如CPU待处理的页面序列号为:

已经处理了5个页面(底纹为灰色),那么页面5是第一个待处理的页面;2是第二个;1是第四个;4是第五个;3是第六个。那么页面3就是针对当前位置而言,最后处理到的页面。

2) 图表描述

还用前面的例子,某进程在硬盘上被划为5个页面,用1、2、3、4、5表示,而处理机处理它们的顺序为1、4、2、5、3、3、2、4、2、5

而内存可以控制的页面数为3(AP=3),那么在使用OPT算法时,这3个页面的内存使用情况如图所示。

 

由图不难看出共发生页面交换6次, diseffect=6。

3) 算法实现提示

(a) 初始化。设置两个数组page[ap]和 pagecontrol[pp],分别表示进程页面数和内存分配的页面数,并产生一个随机数序列main[total_instruction](这个序列由page[]的下标随机构成),表示待处理的进程页面顺序, diseffect置零。

(b) 观察main[]是否有下一个元素。如果有,就从序列main[]中获取一个CPU待处理的页面号;如果没有,就转到(f)。

(c) 如果该页面已经在内存中了,就转到(b);否则转到(c)。

(d) 观察是否有空闲的内存页面,如果有,就直接返回该页面指针;如果没有，遍历所有未处理的进程页面序列,如果有位于内存中的页面,而以后CPU不再处理的,首先将其换出,返回页面指针;如果没有这样的面,找寻出CPU最晚处理到的页面,将其换出，返回该内存页面指针。

(e) 将内存页面和待处理的进程页面建立联系,返回(b)。

(f) 输出1-(total_instruction/disaffect) ×100%,结束。

注意:关于第(d)步的实现有个小小的技巧,可以为每个进程页面设一个“间隔”属性distance,表示CPU将在第几步处理到该页面,如果页面不再被CPU处理,可以设为某个很大的值(如32767),这样每次就换出distance最大的那个页面。

 模拟代码

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <unistd.h>
 
using namespace std;
 
#define INVALID -1
 
const int TOTAL_INSTRUCTION(320);
const int TOTAL_VP(32);
const int CLEAR_PERIOD(50);
 
#include "Page.h"
#include "PageControl.h"
#include "Memory.h"
 
int main()
{
	int i;
	CMemory a;
	for(i=4;i<=32;i++)
	{
	  a.FIFO(i);
    	  a.LRU(i);
	  a.NUR(i);
	  a.OPT(i);
	  cout<<"\n";
	}
	return 0;
}