操作系统 | 实验五页面置换算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了操作系统 | 实验五页面置换算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、实验目的

（1）加深对页面置换算法的理解。
（2）掌握几种页面置换算法的实现方法。
（3）通过实验比较各种置换算法的优劣。

二、实验内容

参考用C语言实现的先进先出算法FIFO的代码，实现最佳置换算法OPT和最近最少使用算法LRU。使得随机给出一个页面执行序列，计算不同置换算法的缺页数，缺页率和命中率。

三、数据结构

typedef struct item
{
int num; //页号
int time; //等待时间，LRU算法会用到这个属性
}Pro;
全局变量：
int pageNum = 0; //系统分配给作业的主存中的页面数
int memoryNum = 0; //可用内存页面数

1、函数以及功能

函数名称	功能描述
void print(Pro* page1)	打印当前主存中的页面
int Search(int num1, Pro* memory1)	页面集memory1中查找num1，如果找到，返回其在memory1中的下标，否则返回-1
int Max(Pro* memory1)	选择哪种方法进行
void DisplayInfo()	信息展示
int main()	main函数

四、程序流程图

操作系统 | 实验五页面置换算法

五、实验代码

#include <stdio.h>
#include <stdlib.h>

#define SYSINFO "页面置换算法" // 系统信息 
#define AUTHOR "Yrani - 依然" //作者 

/**
* 	@Author: Yrani - 依然
* 	@Date: 2022-05-2 20:20:17
* 	@LastEditTime: 2022-05-03 15:55:00
* 	@keywords: 页面置换算法、LRU、OPT、FIFO 
**/

typedef struct item
{
	int num;        //页号
	int time;        //等待时间，LRU算法会用到这个属性
} Pro;

int pageNum = 0;        //系统分配给作业的主存中的页面数
int memoryNum = 0;        //可用内存页面数

void PrintCurrentPage(Pro* page1);        //打印当前主存中的页面
int Search(int num1, Pro* memory1);    //在页面集memory1中查找num1，如果找到，返回其在memory1中的下标，否则返回-1
int Max(Pro* memory1);
int Optimal(int num,int tag,Pro* memory1,Pro* page1);

//信息展示
void DisplayInfo()
{
	printf("★★★★★★★★★★★★★★★★★\n");
	printf("★☆☆☆☆%s☆☆☆☆☆☆★\n",SYSINFO);
	printf("☆☆☆☆☆@Author:%s☆☆☆☆★\n",AUTHOR);
	printf("★★★★★★★★★★★★★★★★★\n");
}

void PrintCurrentPage(Pro *memory1)//打印当前的页面
{
	int j = 0;

	for(j = 0; j < memoryNum; j++)
		printf("      %d     ", memory1[j].num);
	printf("\n");
}

//在页面集memory1中查找num1，如果找到，返回其在memory1中的下标，否则返回-1
int  Search(int num1,Pro *memory1)
{
	int j;

	for(j=0; j < memoryNum; j++)
	{
		if(num1==memory1[j].num)
			return j;
	}
	return -1;
}

int Max(Pro *memory1)
{
	int max = 0;

	for(int k=1; k < memoryNum; k++)
	{
		if(memory1[k].time > memory1[max].time)
			max = k;
	}
	
	return max;
}

int Optimal(int num, int tag, Pro *memory1, Pro *page1)
{
	int k, j, min[100], min_k;
	for(k = 0; k < memoryNum; k++)
	{
		min[k] = 500;
	}
	
	for(k = 0; k < memoryNum; k++)
	{
		j = tag;
		do
		{

			j++;
			if(j>20)
				break;
		}
		while(page1[j].num != memory1[k].num);
		if(j < min[k])
		{

			min[k] = j;
		}
	}
	int max = 0;
	for(int t = 1; t < memoryNum; t++)
	{
		if(min[t] > min[max])
			max = t;
	}
	return max;
}

int main()
{
	int i = 0;
	int curmemory = 0;        //调入主存中的页面个数
	int missNum = 0;        //缺页次数
	float missRate = 0.0;        //缺页率
	char c;                //得到用户的输入字符，来选择相应的置换算法

	Pro* page = NULL;            //作业页面集
	Pro* memory = NULL;        //内存页面集
	
	DisplayInfo(); 
	
	printf("输入系统分配给作业的主存中的页面数:");
	scanf("%d", &pageNum);
	printf("输入内存页面数:");
	scanf("%d", &memoryNum);

	page = (Pro*)malloc(sizeof(Pro)*pageNum);
	memory = (Pro*)malloc(sizeof(Pro)*memoryNum);

	for(i = 0; i < pageNum; i++)
	{
		printf("第 %d 个页面号为:", i);
		scanf("%d", &page[i].num);
		page[i].time=0;            //等待时间开始默认为0
	}

	do
	{
		for(i = 0; i < memoryNum; i++)      //初始化内存中页面
		{
			memory[i].num = -1;                //页面为空用-1表示
			memory[i].time = -1;                //
		}

		printf("*****f:FIFO页面置换*****\n");
		printf("*****o:OPT页面置换*****\n");
		printf("*****l:LRU页面置换*****\n");
		printf("*****请选择操作类型(f,o,l),按其它键结束******\n");
		fflush(stdin);
		scanf("%c", &c);

		i = 0;
		curmemory = 0;

		if(c == 'f')            //FIFO页面置换
		{
			missNum = 0;

			printf("FIFO页面置换情况:   \n");
			printf("置换的页面号  ");
			for(i = 0; i < memoryNum; i++)
			{
				printf("物理块号%d  ",i+1);
			}
			printf("\n===============================================================\n");
			for(i=0; i<pageNum; i++)
			{
				if(Search(page[i].num,memory) < 0)//若在主存中没有找到该页面
				{
					missNum ++;
					if(memory[curmemory].num > -1)
					{
						printf("   %d      ", memory[curmemory].num);
					} 
					else
					{
						printf("          ");
					}
					memory[curmemory].num = page[i].num;
					PrintCurrentPage(memory);
					curmemory = (curmemory + 1) % memoryNum;
					printf("===============================================================\n");
				}
			}//end for
			missRate = (float)missNum / pageNum;
			printf("缺页次数：%d   缺页率:  %f\n", missNum, missRate);

		}//end if

		if(c == 'o')            //OPT页面置换
		{
			missNum = 0;

			printf("OPT页面置换情况:   \n");
			printf("置换的页面号  ");
			for(i = 0;  i< memoryNum; i++)
			{
				printf("物理块号%d  ", i+1);
			}
			printf("\n===============================================================\n");
			for(i = 0; i < pageNum; i++)
			{
				if(Search(page[i].num,memory) < 0)//若在主存中没有找到该页面
				{
					if(i < memoryNum)
						curmemory = i;
					else
						curmemory = Optimal(page[i].num,i,memory,page);
					missNum ++;
					if(memory[curmemory].num > -1)
					{
						printf("   %d      ",memory[curmemory].num);
					}
					else
					{
						printf("          ");
					}
					memory[curmemory].num = page[i].num;
					PrintCurrentPage(memory);
					curmemory = (curmemory+1) % memoryNum;
					printf("===============================================================\n");
				}
			}//end for
			missRate = (float)missNum / pageNum;
			printf("缺页次数：%d   缺页率:  %.2f%%\n", missNum, missRate*100);


		}//end if

		if(c=='l')            //LRU页面置换
		{
			missNum = 0;

			printf("LRU页面置换情况:   \n");
			printf("置换的页面号  ");
			for(i = 0; i < memoryNum; i++)
			{
				printf("物理块号%d  ", i+1);
			}
			printf("\n===============================================================\n");
			for(i =0; i < pageNum; i++)
			{
				for(int j=0; j<memoryNum; j++)
				{
					if(memory[j].num>=0)
						memory[j].time++;
				}
				if(Search(page[i].num,memory)<0)//若在主存中没有找到该页面
				{
					missNum ++;
					//    Printf("%d \n",curmemory);
					if(i<3)
						curmemory = i;
					else
						curmemory = Max(memory);
					if(memory[curmemory].num>-1)
					{
						printf("   %d      ",memory[curmemory].num);
					}
					else
					{
						printf("          ");
					}
					memory[curmemory].num=page[i].num;
					memory[curmemory].time = 0;
					PrintCurrentPage(memory);
					curmemory = (curmemory+1)%memoryNum;
					printf("===============================================================\n");
				}
				else
				{
					curmemory = Search(page[i].num,memory);
					memory[curmemory].time=0;
					curmemory = (curmemory+1)%memoryNum;
				}

			}//end for
			missRate = (float)missNum/pageNum;
			printf("缺页次数：%d   缺页率:  %.2f%%\n", missNum, missRate*100);



		}//end if

	}while(c=='f'||c=='l'||c=='o');
	
	return 0;
}

六、实验结果

系统信息展示
操作系统 | 实验五页面置换算法

输入页面序列数
操作系统 | 实验五页面置换算法

输入内存页面数
操作系统 | 实验五页面置换算法

输入20个页面号
操作系统 | 实验五页面置换算法

首先选择FIFO算法
操作系统 | 实验五页面置换算法

OPT页面置换算法
操作系统 | 实验五页面置换算法

LRU页面置换算法
操作系统 | 实验五页面置换算法

按其他键退出即可
操作系统 | 实验五页面置换算法

七、实验体会总结

总结与体会：文章来源地址https://www.toymoban.com/news/detail-442025.html

通过本次实验加深了我对页面置换算法的理解，本次实验中的页面置换算法有
FIFO（先进先出置换算法）、LRU（最近最少使用页面置换算法）、OPT（最佳置换算法）。
FIFO算法的核心思想是置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。按照进入内存的先后次序排列成队列，从队尾进入，从队首删除。但是该算法会淘汰经常访问的页面，不适应进程实际运行的规律，目前已经很少使用。
LRU算法的核心思想是置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。LRU算法普偏地适用于各种类型的程序，但是系统要时时刻刻对各页的访问历史情况加以记录和更新，开销太大，因此LRU算法必须要有硬件的支持。
OPT算法的核心思想是置换以后不再被访问，或者在将来最迟才回被访问的页面，缺页中断率最低。缺点：该算法需要依据以后各业的使用情况，而当一个进程还未运行完成是，很难估计哪一个页面是以后不再使用或在最长时间以后才会用到的页面。
这三种算法对比：OPT > LRU > FIFO 但是OPT算法是不能实现的，但该算法仍然有意义，可以作为其他算法优劣的一个标准。
此次实验难度相较于前面几次难度较大，代码较难调试，还是需要多加思考和练习。

到了这里，关于操作系统 | 实验五页面置换算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！