操作系统实验四-页面置换算法实验

Y.xj
代码已上传github

本实验重点为不同的页面置换算法，所以程序主体部分完全相同

程序总体函数变量如下：

程序实现步骤：

1. 判断是否缺页

2. 判断内存是否存满

3. 若内存不满，则直接插入

   若内存满，则使用不同算法来从内存中选择页面进行置换

4. 输出缺页率

将必要变量设为全局变量

#define Max 5				//内存页数上限
#define Mainarrlen 30		//总页表数上限
#define maxsuparrlen 3		//缓存数组最大长度
#define random(x) rand()%x	//定义随机函数
int arr[Max];				//声明内存
int arrlen = 0;				//内存当前存储的页数
int fifoflag = 0;				//先进先出算法flag
int used[Max] = { 0 };			//初始化页面访问位 置为0
int modifiesd[Max];			//申请修改位数组
int suparr[maxsuparrlen];			//申请2位缓冲数组
int suparrlen = 0;				//缓存数组当前长度
int suparrflag = 0;				//辅助数组置换flag

在主体部分先完成通用函数的编写：

• 每次访问新的页号前先判断是否缺页，遍历内存中的页号是否有与欲访问页号相同的，有则返回0，为不缺页，没有则返回1，缺页。

缺页判断函数iflack():

/*iflack(int p)
function :判断是否有缺页
parm :   p---要访问的页号
rtn  :   1---缺页   0---不缺页*/
int iflack(int p)
{
	for (int i = 0; i < arrlen; i++)
	{
		if (arr[i] == p)
		{
			used[i] = 1;		//用于Clock算法每次访问之后将其访问位置1
			return 0;
		}
	}
	return 1;
}

• 每次访问页面后都输出一次内存已有页号

• 判断完缺页之后查看内存中已经存储的页数arrlen，如果arrlen没有达到存储上限，直接存储入，如果达到了存储上限，调用不同置换算法，进行置换。先预先设置30位数组作为要访问的页号

主函数main():

int main()
{
	int p, rpl,lacknum=0;
	int mainarr[30] = { 1, 2, 3, 4, 5, 6, 7,6,5,4,3,2,1,6,7,8,9,10,9,8,7,6,7,8,9,10,11,12,13,14 };
	//int mainarr[12] = { 1,2,3,4,1,2,5,1,2,3,4,5 };
	for (int i = 0; i < Mainarrlen; i++)
	{
		p = mainarr[i];				//取出将要访问的页
		if (iflack(p))
		{
			//缺页的情况
			if (arrlen < Max)
			{
				//内存未存满，直接插入
				inserte(p);
				outputmem();
			}
			else
			{
				//内存存满,使用不同算法选择要替换的内存页,并且替换
				//rpl = BestReplace(mainarr, p, i);			//最佳置换算法
				//rpl = FIFOReplace(p);						//先进先出算法
				//rpl = LRU(mainarr, p, i);					//最近最久未使用算法
				//rpl = Clock(p);							//Clock算法
				//rpl = PBA(p);								//页面缓冲算法
				printf("访问%d时发生缺页置换,%d---->%d\n", p, rpl, p);
				outputmem();
			}
			lacknum++;
		}//end if
		else
		{
			//不缺页
			printf("访问%d时没有缺页\n", p);
			outputmem();
			continue;
		}//end else
	}//end for
	printf("缺页率为%lf", lacknum / 30.0);
}

最佳置换算法

基本思想：选择永不使用或是在最长时间内不再被访问（即距现在最长时间才会被访问）的页面淘汰出内存

**注意：**一般情况下无法实现此算法，但此时预先给出了所有要访问的页号，则可以在理论上实现。

**实现过程：**传入函数要访问的页的位置，对于每个内存中的页号，从此位置开始向后遍历，寻找第一个相同的页号，如果发现相同页号出现在更远的地方，记录下此时内存中该页号的下标，全部遍历完之后，此下标就是被替换掉的内存中的页号下标。如果在遍历时出现了遍历完整个欲访问页号集都没有发现相同的页号，则直接停止遍历内存，此时访问到的内存中的页号就是要被替换的页。

/*最佳置换算法
function: 缺页情况下寻找应替换的内存中的页号
parm : *mainarr---要查找的页表   p---要替换的缺页的页号   pindex---要替换的缺页页号下标
*/
int BestReplace(int* mainarr, int p, int pindex)
{
	int lastindex = -1;
	int rpl;				//被替换掉的页
	int replaceindex = 0;
	for (int i = 0; i < arrlen; i++)				//将内存中的页循环遍历
	{
		int flag = 0;
		for (int j = pindex + 1; j < Mainarrlen; j++)		//将每个页向后找相同的出现，寻找最晚出现的
		{
			if (arr[i] == mainarr[j])
			{
				if (lastindex < j)	//如果找到更远的，替换index
				{
					lastindex = j;
					replaceindex = i;
				}
				break;				//找到相等就跳出循环
			}
			if (j == Mainarrlen - 1 && arr[i] != mainarr[j])		//如果找完没有出现，直接将此页作为被替换页
			{
				replaceindex = i;
				flag = 1;
			}
		}
		if (flag == 1)
		{
			break;
		}
	}
	rpl = arr[replaceindex];
	replace(p, replaceindex);
	return rpl;
}

实验结果：

缺页率为53.3%

最近最久未使用算法（LRU)

**基本思想：**以“最近的过去”作为“最近的将来”的近似，选择最近一段时间最长时间未被访问的页面淘汰出内存

**实现过程：**与最佳替换算法相反，LRU在遍历内存中页号的时候，从已访问页号向前遍历，寻找到离当前访问页号最远的与内存中相同的页号，将内存中此页号标记为替换下标，遍历结束则替换。同样，如果向前遍历完都没有找到相同页号，则直接退出循环。

/*最近最久未使用算法
function:	向前寻找最近最久未使用的
parm : *mainarr---要查找的页表   p---要替换的缺页的页号   pindex---要替换的缺页页号下标
*/
int LRU(int* mainarr, int p, int pindex)
{
	int lastindex = pindex;
	int rpl;				//被替换掉的页
	int replaceindex = 0;		//替换的下标
	for (int i = 0; i < arrlen; i++)				//将内存中的页循环遍历
	{
		int flag = 0;
		for (int j = pindex; j >=0; j--)		//将每个页向后找相同的出现，寻找最晚出现的
		{
			if (arr[i] == mainarr[j])
			{
				if (lastindex > j)	//如果找到更远的，替换index
				{
					lastindex = j;
					replaceindex = i;
				}
				break;				//找到相等就跳出循环
			}
			if (j == 0 && arr[i] != mainarr[j])		//如果找完没有出现，直接将此页作为被替换页
			{
				replaceindex = i;
				flag = 1;
			}
		}
		if (flag == 1)
		{
			break;
		}
	}
	rpl = arr[replaceindex];
	replace(p, replaceindex);
	return rpl;
}

实验结果：

缺页率为60.0%

先进先出算法（FIFO)

基本思想：

• 选择最先进入内存即在内存驻留时间最久的页面换出到外存
• 进程已调入内存的页面按进入先后次序链接成一个队列，并设置替换指针以指向最老页面

实现过程：

​ 只需要设置一个标志位循环挪动替换即可

/*先进先出置换算法
function：按先进先出寻找要置换的页号
parm：  p---要替换的页数
*/
int FIFOReplace(int p)
{
	int rpl;
	rpl = arr[fifoflag % Max];				//arr轮着替换
	replace(p, fifoflag % Max);
	fifoflag++;
	return rpl;
}

实验结果：

缺页率为60.0%

Clock算法

基本思想：
① 从查寻指针当前位置起扫描内存分页循环队列，选择A=0且M=0的第一个页面淘汰；若未找到，转②
② 开始第二轮扫描，选择A=0且M=1的第一个页面淘汰，同时将经过的所有页面访问位置0；若不能找到，转①

实现过程：

开始之前随机初始化修改位，随后遍历两遍，第一遍先遍历(0,0)和(0,1)两种情况，遍历完之后将第一位修改为1，再遍历一遍(0,0)和(0,1)两种情况,即选择开始时的(1,0)和(1,1)情况。

/*Clock算法
function：对每页都设置一个访问位和修改位，这里我们模拟随机设置修改位为1，再按顺序置换
parm:	p---要替换的缺页的页号
*/
int Clock(int p)
{
	for (int i = 0; i < Max; i++)				//修改位随机初始化
	{
		modifiesd[i] = rand() % 2;
	}
	int rpl;
	int count = 1;			//遍历两遍
	while (count--)
	{
		for (int i = 0; i < Max; i++)			//第一轮遍历寻找{0,0}，如果没有不作任何操作
		{
			if (used[i] == 0 && modifiesd[i] == 0)
			{
				rpl = arr[i];
				replace(p, i);
				return rpl;
			}
			else
			{
				continue;
			}
		}
		for (int i = 0; i < Max; i++)			//第二轮遍历寻找{0,1}，如果不是的话将访问位置0
		{
			if (used[i] == 0 && modifiesd[i] == 1)
			{
				rpl = arr[i];
				replace(p, i);
				return rpl;
			}
			else
			{
				used[i] = 0;				//第四次访问时不会执行这里
			}
		}
	}
}

实验结果：

缺页率为76.7%

页面缓冲算法（PBA）

基本思想：

设立空闲页面链表，采用可变分配和基于先进先出的局部置换策略，并规定被淘汰页先不做物理移动，而是依据是否修改分别挂到空闲页面链表或已修改页面链表的末尾。空闲页面链表同时用于物理块分配。

/*页面缓冲算法PBA
function：	设置一个缓冲数组用于从中取数
parm：p---要替换的缺页的页号
*/
int PBA(int p)
{
	int rpl;
	for (int i = 0; i < suparrlen+1; i++)
	{
		if (p == suparr[i])					//如果相等
		{
			suparr[i] = arr[fifoflag% Max];				//将缓存中的与内存中的进行交换
			arr[fifoflag]= p;
			fifoflag++;
			break;
		}
		if (i == suparrlen && suparr[i] != p)
		{
			if (suparrlen < maxsuparrlen)
			{
				//辅助数组不命中且不满,直接插入，长度加一
				suparr[suparrlen++] = p;
				return p;
			}
			else
			{
				//辅助数组不命中且满,选择一个替换
				rpl = suparr[suparrflag % maxsuparrlen];
				suparr[suparrflag++ % maxsuparrlen] = p;
				return rpl;
			}
		}
	}
	return -1;				//缓存与内存进行置换
}

实验结果：

缺页率为66.7%

页面访问序列随机生成函数

符合局部访问特性的随机生成算法

1. 确定虚拟内存的尺寸N，工作集的起始位置p，工作集中包含的页数e，工作集移动率m（每处理m个页面访问则将起始位置p +1），以及一个范围在0和10之间的值t；
2. 生成m个取值范围在p和p + e间的随机数，并记录到页面访问序列串中；
3. 生成一个随机数r，0 ≤ r ≤ 10；
4. 如果r < t，则为p生成一个新值，否则p = (p + 1) mod N；
5. 如果想继续加大页面访问序列串的长度，请返回第2步，否则结束。

void createarr() {
	srand((int)time(0));// 设置随机种子
	int N = 32;// 虚拟内存尺寸    
	int p = 0;// 工作集起始位置  
	int e = 5;// 工作集大小     
	int m = 6;// 工作集移动率    
	int t = 6;// 一个范围在0和10之间的值t  
	for (int i = 0; i < Mainarrlen / m; ++i) {
		for (int j = i * m; j < i * m + 6; ++j) {
			mainarr[j] = (random(e) + p) % N;
		}
		int r = random(10) > t ? 1 : 0;
		if (r < t) {
			p = random(N) % N;
		}
		else {
			p = (p + 1) % N;
		}
	}
}

局部算法测试结果

当测试序列为下列时

//int mainarr[30] = { 1, 2, 3, 4, 5, 6, 7,6,5,4,3,2,1,6,7,8,9,10,9,8,7,6,7,8,9,10,11,12,13,14 };

不同算法的表现如下：

算法	缺页率（%）
最佳置换算法	53.3
Clock算法	76.7
FIFO算法	60.0
LRU算法	60.0
PBA算法	66.7
平均	63.0