存储管理之虚拟存储器实现（页面置换算法模拟）

页面置换算法

先进先出算法（FIFO）： 先进先出算法是最简单的分页替换算法，是指每次有新的分页需要调入时，会选择调入内存时间最久的分页换出。它简单，容易实现，但这种绝对的公平方式容易导致效率的降低。
--------发生缺页中断时，即最先进来的淘汰出去

最近最久未使用算法（LRU）算法： 即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的。即最近最少使用的页面予以淘汰。
--------发生缺页中断时，选择未使用时间最长的页面置换出去

最佳置换算法（OPT）： 这是一种理想情况下的页面置换算法，但实际上是不可能实现的。
--------发生缺页中断时，看后面在物理块中的页面序列，查看谁出现的最晚，谁被淘汰。

大家可以做几道例题就基本理解了。

以下是这三种算法的模拟，使用的是队列存储和set进行查询；对于效率不是特别好，只是一个基本的模拟
要求： 设计主界面以灵活选择某算法。2．用随机数方法产生页面走向。3．假定初始时页面都不在内存。

内容： 编程序实现先进先出算法（FIFO）、最近最久未使用算法（LRU）算法、最佳置换算法（OPT）的具体实现过程，并计算访问命中率。
代码如下：

#include<bits/stdc++.h>
using namespace std;

vector<int> a;	//随机数产生的页面走向 
queue <int> q;	//存页面--模拟 
unordered_set<int> se;	//队列存在的数 
int cnt;	//缺页次数
int Size;	//物理块数 
int option;	//菜单选择 
int n;	//页面序列的个数 

void init()
{
	cnt = 0;
	se.clear();
	while (!q.empty())	q.pop();
}


void Print(queue<int> qq)
{
	while (!qq.empty())
	{
		printf("%d ", qq.front());
		qq.pop(); 
	}
	puts("");
}
void FIFO()
{
	init();
	for (int i = 0; i < a.size(); i++)
	{
		if (se.count(a[i]))	//此页面已存在，无需操作
		{
			printf("	 无中断，命中：");
			Print(q);
			continue;
		} 
		se.insert(a[i]);
		if (q.size() == Size)
		{
			se.erase(q.front());
			q.pop();	
		}
		cnt++;
		q.push(a[i]);
		printf("	第%d次缺页中断：", cnt);
		Print(q);
	}
	printf("	FIFO算法缺页次数：%d, 缺页率：%%%.2lf\n", cnt, 1.0*cnt/n*100);
	printf("	FIFO算法命中次数：%d, 命中率：%%%.2lf\n", n-cnt, (1 - 1.0*cnt/n) * 100);
} 

void LRU()
{
	init();
	for (int i = 0; i < a.size(); i++)
	{
		if (se.count(a[i]))		//此页面已存在，进行更新 
		{
			queue <int> p;
			while (!q.empty())
			{
				int x = q.front();
				q.pop();
				if (x == a[i])	continue;
				p.push(x);
			} 
			q = p;
			q.push(a[i]);
			printf(" 	无中断，命中：");
			Print(q);
			continue;
		}
		se.insert(a[i]);
		if (q.size() == Size)
		{
			se.erase(q.front());
			q.pop();	
		}
		cnt++;
		q.push(a[i]);
		printf("	第%d次缺页中断：", cnt);
		Print(q);
	}
	printf("	LRU算法缺页次数：%d, 缺页率：%%%.2lf\n", cnt, 1.0*cnt/n*100);
	printf("	LRU算法命中次数：%d, 命中率：%%%.2lf\n", n-cnt, (1 - 1.0*cnt/n) * 100);
}

void OPT()
{
	init();
	for (int i = 0; i < a.size(); i++)
	{
		if (se.count(a[i]))	//已经存在，不进行操作
		{
			printf("	 无中断，命中：");
			Print(q);
			continue;
		}
		if (q.size() < Size)	
		{
			cnt++;
			se.insert(a[i]);
			q.push(a[i]);
			printf("	第%d次缺页中断：", cnt);
			Print(q);
			continue;
		}
		unordered_set<int> t;
		queue <int> p;
		for (int j = i + 1; j < a.size(); j++)
		{
			if(!se.count(a[j]))	continue;
			if (t.size() == Size - 1)	break;
			t.insert(a[j]);
		}
		int f = 1;
		while (!q.empty())
		{
			int x = q.front();
			q.pop();
			if (!t.count(x) && f)
			{
				se.erase(x);
				f = 0;
				continue;
			}
			p.push(x);
		}
		q = p;
		q.push(a[i]);
		se.insert(a[i]);
		cnt++;
		printf("	第%d次缺页中断：", cnt);
		Print(q);	
	}
	printf("	OPT算法缺页次数：%d, 缺页率：%%%.2lf\n", cnt, 1.0*cnt/n*100);
	printf("	OPT算法命中次数：%d, 命中率：%%%.2lf\n", n-cnt, (1 - 1.0*cnt/n) * 100);
}

void menu()
{
	printf("-------------------------菜单-----------------------------\n");
	printf("		1、随机产生作业和物理块数\n");
	printf("		2、自己输入作业和物理块数\n");
	printf("		3、先进先出算法（FIFO）\n");
	printf("		4、最近最久未使用算法（LRU）\n");
	printf("		5、最佳置换算法（OPT）\n");
	printf("		6、重现菜单\n");
	printf("		0、退出系统\n");
	printf("	请注意：在选择过1或2后才能选择3、4、5,否则会发生错误！\n");
} 

void random()
{
    a.clear();
	srand((unsigned) (time(NULL)));	//随机数更新 
	Size = rand()%5 + 2; //随机数[2, 6] 
	n = rand()%20 + 5;	//随机数[5, 24]
	printf("分配的物理块数为%d,页面序列共%d个，如下：\n", Size, n);
	for (int i = 0; i < n; i++)
	{
		int x = rand()%(n / 2) + 1;	//随机数[1, n / 2]
		a.push_back(x);
		printf("%d ",x);
	}
	puts(""); 	
}
void Scanf()
{
    a.clear();
	printf("请问输入分配的物理块数：") ;
	scanf("%d", &Size);
	printf("请问页面序列共多少个:");
	scanf("%d", &n);
	printf("请输入："); 
	for (int i = 0; i < n; i++)
	{
		int x;	scanf("%d", &x); 
		a.push_back(x);
	}
}


int main()
{
	menu();
	
	while(1)
	{
		printf("请选择：");
		scanf("%d", &option);
		if (option == 0)
		{
			printf("\n     成功退出！！\n");
			break;
		}
		switch (option)
		{
			case 1:	random();	break;
			case 2:	Scanf();	break;
		 	case 3:	FIFO();		break;
		 	case 4:	LRU();		break;
		 	case 5:	OPT();		break;
		 	case 6:	menu();		break;
		 	default:	printf("输入错误，请您确认无误后再次输入！\n");
		}
	} 
	
	return 0;
}

结果截图：

在此页面也可查看
https://blog.csdn.net/weixin_57780057/article/details/124456655?spm=1001.2014.3001.5501