页面置换算法——C/C++实现 [ OTP, FIFO, LRU, LFU + 开源代码 + 详细解析]

⌛️

Page Replacement Algorithm ⌨️

零、运行结果图

◆ 对上图说明：后面分别用四种算法，对该样例都进行了检验，结果一致。

● 后文代码的常见变量：
  [1] n：物理页框数。
  [2] len：地址走向的长度。
  [3] save_Frame：含有n个格子的物理页框（即一个长度为n的动态数组，指针申请的）。
  [4] interview_Array：长度为len的地址数组（即一个长度为len的动态数组，指针申请的）。

一、最佳置换算法（OPT）

● 替换规则：将以后永不使用的或在最长时间内不再被访问的页面进行替换。

● 这是一种理想化的算法，有点 “先知” 算法的味道，故在实际上是难以实现的。但它可作为衡量各种实用的页面置换算法的标准。

● 样例：假设采用固定分配策略，为进程分配 3 个存储页框，进程运行时形成的访问地址走向为 2，3，2，1，5，2，4，5，3，2，5 和 2。则 OPT 算法运行结果如下。

◆ 说明：
  ① 第一个红箭头：因为后面需访问地址里面没有 “1”，所以用 “5” 置换 “1”。
  ② 第二个红箭头：因为后面需访问的地址里面，“2” 是最长时间内不被访问的，所以置换它。
  ③ 当进程运行完毕时，系统进行了 3 次置换，缺页中断次数为 6 次，即蓝色箭头加上红色箭头的个数。缺页率为 6/12 = 50% 。

● 算法设计：

[1] 依次读取每一个页面地址addr，然后看当前页框是否装满。如果未装满则执行[2]，否则执行[3]。

[2] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后返回执行步骤[1]，否则执行[4](即未命中的情况)。

[3] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后返回执行步骤[1]，否则执行[5](即未命中的情况)。

[4] 把当前地址addr装入空闲的物理页框，然后返回执行步骤[1]。

[5] 执行Find_LeastInteviewTime()函数，找出需要替换的页面地址(在物理页框中的)，并进行替换，然后返回执行步骤[1]。

● 核心代码：【注：Init()函数、Find_Exist()等函数在后文的完整代码中】

int Find_LeastInteviewTime(int sta, int addr, int* interview_Array, int len)
{
	for (int i = sta; i < len; i++)
	{
		if (interview_Array[i] == addr)
			return i - sta;
	}
	return 99999;
}

void OPT_Agorithm()
{
	printf("欢迎使用 OPT \n");
	int n = 0, len = 0, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
		
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);

	int addr;		// 地址
	int cnt = 0;			// 物理页框已装满的份数(大于 n 时无效) 
	int score = 0;			// 成功的访问次数
	int fail_time = 0;		// 不成功的访问次数
	int iter = 0;	// 迭代次数
	while (iter < len)
	{
		printf("\n第%d轮：", iter);
		addr = interview_Array[iter];		// 读取地址
		iter++;
		...
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				...
			}
			else // 未命中，但有空间 
			{
				fail_time++;
				...
				save_Frame[cnt] = addr;
				...
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				...
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int* least_Time = (int*)malloc(n * sizeof(int));
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					least_Time[i] = Find_LeastInteviewTime(iter, save_Frame[i], interview_Array, len);
					if (least_Time[i] > max_Time)
					{
						max_Time = least_Time[i];
						index = i;
					}
				}
				...
				save_Frame[index] = addr;
				...
			}
		}
	}
	...
}

● 运行结果：

二、先进先出算法（FIFO）

● 替换规则：淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以替换。

● 依旧沿用上面的样例来图形化说明：假设采用固定分配策略，为进程分配 3 个存储页框，进程运行时形成的访问地址走向为 2，3，2，1，5，2，4，5，3，2，5 和 2。则 OPT 算法运行结果如下。

◆ 说明：
  ① 第一个红箭头：因为 “2” 最先进来，所以用 “5” 置换 “2”。
  ② 当进程运行完毕时，系统进行了 6 次置换，缺页中断次数为 9 次，即蓝色箭头加上红色箭头的个数。缺页率为 9 /12 = 75% 。

● 算法设计：【in_HereTime[]：记录每个页面驻留的时间】

[1] 依次读取每一个页面地址addr，然后看当前页框是否装满。如果未装满则执行[2]，否则执行[3]。

[2] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后执行Update_InHereTime()函数来更新in_HereTime[]数组，然后返回执行步骤[1]，否则执行[4](即未命中的情况)。

[3] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后执行Update_InHereTime()函数来更新in_HereTime[]数组，然后返回执行步骤[1]，否则执行[5](即未命中的情况)。

[4] 把当前地址addr装入空闲的物理页框，然后执行Update_InHereTime()函数来更新in_HereTime数组，然后返回执行步骤[1]。

[5] 从in_HereTime[]找出最大值对应的那个页面地址(在物理页框中的)，并进行替换，然后返回执行步骤[1]。

● 核心代码：【注：Init()函数、Find_Exist()函数等函数在后文的完整代码中】

void Update_InHereTime(int* in_HereTime, int n, int ind)
{
	for (int i = 0; i < n; i++)
		in_HereTime[i]++;
	if (ind != -1)
		in_HereTime[ind] = 0;
}

void FIFO_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
		
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);

	int* in_HereTime = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		in_HereTime[i] = 0;		// 初始化都为零

	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		printf("\n第%d轮：", iter);
		addr = interview_Array[iter];
		iter++;
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				...
				Update_InHereTime(in_HereTime, cnt, -1);
			}
			else // 未命中，但有空间
			{
				fail_time++;
				...
				save_Frame[cnt] = addr;
				...
				Update_InHereTime(in_HereTime, cnt, cnt);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				...
				Update_InHereTime(in_HereTime, n, -1);
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					if (in_HereTime[i] > max_Time)
					{
						max_Time = in_HereTime[i];
						index = i;
					}
				}
				...
				save_Frame[index] = addr;
				...
				int ind = Find_Exist(save_Frame, n, addr);
				Update_InHereTime(in_HereTime, n, ind);
			}
		}
	}
	...
}

● 测试结果：

三、最近最久未使用算法（LRU）

● 替换规则：替换最近一段时间内最久未被使用的页面。

● 依旧沿用上面的样例来图形化说明：假设采用固定分配策略，为进程分配 3 个存储页框，进程运行时形成的访问地址走向为 2，3，2，1，5，2，4，5，3，2，5 和 2。则 OPT 算法运行结果如下。

◆ 说明：
  ① 第一个红箭头：因为 “2” 最近被访问过，“1”刚刚才被调入，只有 “3” 最近最久未被访问，所以置换它。
  ② 当进程运行完毕时，系统进行了 4 次置换，缺页中断次数为 7 次，即蓝色箭头加上红色箭头的个数。缺页率为 7 /12 = 58.33% 。

● 算法设计：

[1] 依次读取每一个页面地址addr，然后看当前页框是否装满。如果未装满则执行[2]，否则执行[3]。

[2] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后返回执行步骤[1]，否则(即未命中)执行[4]。

[3] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后返回执行步骤[1]，否则(即未命中)执行[5]。

[4] 把当前地址addr装入空闲的物理页框，然后返回执行步骤[1]。

[5] 执行Find_LeastNotUseTime()函数，找出需要替换的页面地址(在物理页框中的)，并进行替换，然后返回执行步骤[1]。

● 核心代码：【注：Init()函数、Find_Exist()函数等函数在后文的完整代码中】

int Find_LeastNotUseTime(int end, int addr, int* interview_Array)
{
	for (int i = end - 1; i >= 0; i--)
	{
		if (interview_Array[i] == addr)
			return end - i;
	}
	return 99999;
}

void LRU_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
		
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);

	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		addr = interview_Array[iter];
		iter++;
		...
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				...
			}
			else // 未命中，但有空间
			{
				fail_time++;
				...
				save_Frame[cnt] = addr;
				...
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				...
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int* Not_UseTime = (int*)malloc(n * sizeof(int));
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					Not_UseTime[i] = Find_LeastNotUseTime(iter, save_Frame[i], interview_Array);
					if (Not_UseTime[i] > max_Time)
					{
						max_Time = Not_UseTime[i];
						index = i;
					}
				}
				...
				save_Frame[index] = addr;
				...
			}
		}
	}
	...
}

● 测试结果：

四、最不经常使用算法（LFU）

● 替换规则：把当前为止，访问次数最少的页面予以替换。

● 和上面的样例有一点不同(地址走向不同)：假设采用固定分配策略，为进程分配 3 个存储页框，进程运行时形成的访问地址走向为 2，3，2，1，2，1，5，4，2，4，4 和 6。则 LFU 算法运行结果如下。

◆ 说明：
  ① 第一个红箭头：因为 “3” 被访问（即被命中）的次数为 0，而其他两个页面( “2” 和 “1” 都分别有 2、1 次命中)，所以“3” 的访问次数最少，所以置换它。
  ② 当进程运行完毕时，系统进行了 3 次置换，缺页中断次数为 6 次（即蓝色箭头加上红色箭头的个数）。缺页率为 6 /12 = 50% 。

● 算法设计：【interview_Time[]：记录每个页面被访问的次数】

[1] 依次读取每一个页面地址addr，然后看当前页框是否装满。如果未装满则执行[2]，否则执行[3]。

[2] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，并且使对应的interview_Time加1，然后返回执行步骤[1]，否则(即未命中)执行[4]。

[3] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，并且使对应的interview_Time加1，然后返回执行步骤[1]，否则(即未命中)执行[5]。

[4] 把当前地址addr装入空闲的物理页框，然后返回执行步骤[1]。

[5] 执行Find_LeastNotInterviewTime()函数，找出需要替换的页面地址(在物理页框中的)进行替换，并使对应的的interview_Time重新赋值为0，然后返回执行步骤[1]。

● 核心代码：【注：Init()函数、Find_Exist()函数等函数在后文的完整代码中】

int Find_LeastNotInterviewTime(int n, int* interview_Time)
{
	int min_Time = 99999;
	int ind;
	for (int i = 0; i < n; i++)
	{
		if (interview_Time[i] < min_Time)
		{
			min_Time = interview_Time[i];
			ind = i;
		}
	}
	return ind;
}

void LFU_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);

	int* interview_Time = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		interview_Time[i] = 0;

	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		printf("\n第%d轮：", iter);
		addr = interview_Array[iter];
		iter++;
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				...
				int ind = Find_Exist(save_Frame, cnt, addr);
				interview_Time[ind]++;
			}
			else // 未命中，但有空间
			{
				fail_time++;
				...
				save_Frame[cnt] = addr;
				...
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				...
				int ind = Find_Exist(save_Frame, n, addr);
				interview_Time[ind]++;
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int index = Find_LeastNotInterviewTime(n, interview_Time);
				...
				save_Frame[index] = addr;
				...
			}
		}
	}
	...
}

● 测试结果：

五、完整代码 —— C语言版本

● 补充说明：完整代码中，还包含 “输出内存驻留的页面集合”【Print_Frame()函数】 、“缺页次数” 和 “缺页率” 等功能【Page_Loss_Rate()函数】。

#include <stdio.h>
#include <stdlib.h>
void OPT_Agorithm();
void FIFO_Agorithm();
void LRU_Agorithm();
void LFU_Agorithm();
double Page_Loss_Rate(int, int);
int Find_Exist(int*, int, int);
int Find_LeastInteviewTime(int, int, int*, int);
void Update_InHereTime(int*, int, int);
int Find_LeastNotUseTime(int, int, int*);
int Find_LeastNotInterviewTime(int, int*);
void Print_Frame(int*, int);
void Print_Menu();
void Init(int*, int*);

int main()
{
	int choice;
	do
	{
		Print_Menu();
		printf("请选择要实现的算法：");
		scanf_s("%d", &choice);
		switch (choice)
		{
		case 1:
			OPT_Agorithm();
			break;
		case 2:
			FIFO_Agorithm();
			break;
		case 3:
			LRU_Agorithm();
			break;
		case 4:
			LFU_Agorithm();
			break;
		case 0:
			break;
		}
		system("pause");
		system("cls");
	} while (choice);
	return 0;
}

/*
* 用于遍历 save_Frame[] 的 n 个存储页框, 是否有 “待定地址 -> addr”
* 如果有就返回 ture, 否则返回 false
*/
int Find_Exist(int* save_Frame, int n, int addr)
{
	for (int i = 0; i < n; i++)
	{
		if (save_Frame[i] == addr)
		{
			return i;
		}
	}
	return -1;
}

void Print_Menu()
{
	/* 输入模块 */
	printf("+---------------------------------------+\n");
	printf("|\t***算法清单***\t\t\t|\n");
	printf("|\t1.最佳置换算法(OPT)\t\t|\n|\t2.先进先出算法(FIFO)\t\t|\n");
	printf("|\t3.最近最久未使用算法(LRU)\t|\n|\t4.最不经常使用算法(LFU)\t\t|\n");
	printf("|\t0.退出\t\t\t\t|\n");
	printf("+---------------------------------------+\n");
}

void Print_Frame(int* save_Frame, int n)
{
	printf("\t");
	for (int i = 0; i < n; i++)
	{
		if (i == 0)
		{
			if (save_Frame[i] == -999)
				printf("/ /");
			else
				printf("/%d/", save_Frame[i]);
		}
		else
		{
			if (save_Frame[i] == -999)
				printf(" /");
			else
				printf("%d/", save_Frame[i]);
		}
	}
	printf("\n");
}

void Init(int* n, int* len)
{
	printf("请输入 n :");
	scanf_s("%d", n);

	printf("请输入地址走向的长度：");
	scanf_s("%d", len);
}

/*
 * 缺页中断率：
 * 假设进程 P 在运行中成功的内存访问次数为 s 
 * 不成功的访问次数为 F，则缺页中断率为 R = F/(S+F)
*/
double Page_Loss_Rate(int S, int F)
{
	double ans = 1.0 * F / (1.0 * S + 1.0 * F) * 100;
	return ans;
}

/*
* 最佳置换算法(OPT)：
* 将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
* 数据结构：数组
*/

int Find_LeastInteviewTime(int sta, int addr, int* interview_Array, int len)
{
	for (int i = sta; i < len; i++)
	{
		if (interview_Array[i] == addr)
		{
			return i - sta;
		}
	}
	return 99999;
}
void OPT_Agorithm()
{
	printf("欢迎使用 OPT \n");
	int n = 0, len = 0, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);
	printf("\n");

	//测试样例： 1 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		addr = interview_Array[iter];
		iter++;
		printf("\n第%d轮：", iter);
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);
			}
			else // 未命中，但有空间
			{
				fail_time++;
				printf("未命中，\"%d\" 被装入 \t------->", addr);
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int* least_Time = (int*)malloc(n * sizeof(int));
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					least_Time[i] = Find_LeastInteviewTime(iter, save_Frame[i], interview_Array, len);
					if (least_Time[i] > max_Time)
					{
						max_Time = least_Time[i];
						index = i;
					}
				}
				printf("\"%d\" 替换了 \"%d\"\t\t------->", addr, save_Frame[index]);
				save_Frame[index] = addr;
				Print_Frame(save_Frame, n);
				free(least_Time);
			}
		}
		// printf("\n");
	}
	printf("\n");
	printf("缺页次数为：%d\n", fail_time);
	printf("缺页中断率 R = %.2f%%\n", Page_Loss_Rate(score, fail_time));
	free(save_Frame);
	free(interview_Array);
}

void Update_InHereTime(int* in_HereTime, int n, int ind)
{
	for (int i = 0; i < n; i++)
		in_HereTime[i]++;

	if (ind != -1)
		in_HereTime[ind] = 0;
}
/*
* 先进先出算法(FIFO)：
* 淘汰最先使用内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
* 数据结构：数组
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
*/
void FIFO_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);
	printf("\n");

	int* in_HereTime = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		in_HereTime[i] = 0;		// 初始化都为零

	//测试样例： 2 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		printf("\n第%d轮：", iter);
		addr = interview_Array[iter];
		iter++;
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);
				Update_InHereTime(in_HereTime, cnt, -1);
			}
			else // 未命中，但有空间
			{
				fail_time++;
				printf("未命中，\"%d\" 被装入 \t------->", addr);
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				Update_InHereTime(in_HereTime, cnt, cnt);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);
				Update_InHereTime(in_HereTime, n, -1);
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					if (in_HereTime[i] > max_Time)
					{
						max_Time = in_HereTime[i];
						index = i;
					}
				}
				printf("\"%d\" 替换了 \"%d\"\t\t------->", addr, save_Frame[index]);
				save_Frame[index] = addr;
				Print_Frame(save_Frame, n);
				int ind = Find_Exist(save_Frame, n, addr);
				Update_InHereTime(in_HereTime, n, ind);
			}
		}
	}
	printf("\n");
	printf("缺页次数为：%d\n", fail_time);
	printf("缺页中断率 R = %.2f\%%\n", Page_Loss_Rate(score, fail_time));
	free(save_Frame);
	free(interview_Array);
	free(in_HereTime);
	return;
}

int Find_LeastNotUseTime(int end, int addr, int* interview_Array)
{
	for (int i = end - 1; i >= 0; i--)
	{
		if (interview_Array[i] == addr)
		{
			return end - i;
		}
	}
	return 99999;
}
/*
* 最近最久未使用算法(LRU)：
* 淘汰最近最久未被使用的页面。
* 数据结构：数组
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
*/
void LRU_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);
	printf("\n");
	//测试样例： 3 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		addr = interview_Array[iter];
		iter++;
		printf("\n第%d轮：", iter);
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);

			}
			else // 未命中，但有空间
			{
				fail_time++;
				printf("未命中，\"%d \" 被装入 \t------->", addr);
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int* Not_UseTime = (int*)malloc(n * sizeof(int));
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					Not_UseTime[i] = Find_LeastNotUseTime(iter, save_Frame[i], interview_Array);
					if (Not_UseTime[i] > max_Time)
					{
						max_Time = Not_UseTime[i];
						index = i;
					}
				}
				printf("\"%d\" 替换了 \"%d\"\t\t------->", addr, save_Frame[index]);
				save_Frame[index] = addr;
				Print_Frame(save_Frame, n);
				free(Not_UseTime);
			}
		}
	}
	printf("\n");
	printf("缺页次数为：%d\n", fail_time);
	printf("缺页中断率 R = %.2f%%\n", Page_Loss_Rate(score, fail_time));
	free(save_Frame);
	free(interview_Array);
}

int Find_LeastNotInterviewTime(int n, int* interview_Time)
{
	int min_Time = 99999;
	int ind;
	for (int i = 0; i < n; i++)
	{
		if (interview_Time[i] < min_Time)
		{
			min_Time = interview_Time[i];
			ind = i;
		}
	}
	return ind;
}
/*
* 最不经常使用算法(LFU):
* 即选择最近一段时间内最长时间没有被访问过的页面进行置换
* 数据结构：数组
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
*/
void LFU_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len);
	save_Frame = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		save_Frame[i] = -999;
	printf("请输入地址走向:");
	interview_Array = (int*)malloc(len * sizeof(int));
	for (int i = 0; i < len; i++)
		scanf_s("%d", &interview_Array[i]);
	printf("\n");

	int* interview_Time = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		interview_Time[i] = 0;

	// 测试样例一：4 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	// 测试样例二：4 3 12 2 3 2 1 2 1 5 4 2 4 4 6
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		printf("\n第%d轮：", iter);
		addr = interview_Array[iter];
		iter++;
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);
				int ind = Find_Exist(save_Frame, cnt, addr);
				interview_Time[ind]++;
			}
			else // 未命中，但有空间
			{
				fail_time++;
				printf("未命中，\"%d\" 被装入 \t------->", addr);
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				printf("\"%d\" 被命中了\t\t------->", addr);
				Print_Frame(save_Frame, n);
				int ind = Find_Exist(save_Frame, n, addr);
				interview_Time[ind]++;
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int index = Find_LeastNotInterviewTime(n, interview_Time);
				printf("\"%d\" 替换了 \"%d\"\t\t------->", addr, save_Frame[index]);
				save_Frame[index] = addr;
				interview_Time[index] = 0;
				Print_Frame(save_Frame, n);
			}
		}
	}
	printf("\n");
	printf("缺页次数为：%d\n", fail_time);
	printf("缺页中断率 R = %.2f\%%\n", Page_Loss_Rate(score, fail_time));
	free(save_Frame);
	free(interview_Array);
	free(interview_Time);
}

六、完整代码 —— C++版本

● 补充说明：完整代码中，还包含 “输出内存驻留的页面集合”【Print_Frame()函数】 、“缺页次数” 和 “缺页率” 等功能【Page_Loss_Rate()函数】。

#include <iostream>
#include <stdlib.h>
using namespace std;
void OPT_Agorithm();
void FIFO_Agorithm();
void LRU_Agorithm();
void LFU_Agorithm();
double Page_Loss_Rate(int, int);
int Find_Exist(int*, int, int);
int Find_LeastInteviewTime(int, int, int*, int);
void Update_InHereTime(int*, int, int);
int Find_LeastNotUseTime(int, int, int*);
int Find_LeastNotInterviewTime(int, int*);
void Print_Frame(int*, int);
void Print_Menu();

int main()
{
	int choice;
	do
	{
		Print_Menu();
		cout << "请选择要实现的算法：";
		cin >> choice;
		switch (choice)
		{
		case 1:
			OPT_Agorithm();
			break;
		case 2:
			FIFO_Agorithm();
			break;
		case 3:
			LRU_Agorithm();
			break;
		case 4:
			LFU_Agorithm();
			break;
		case 0:
			break;
		}
		system("pause");
		system("cls");
	} while (choice);
	return 0;
}

/*
* 用于遍历 save_Frame[] 的 n 个存储页框, 是否有 “待定地址 -> addr”
* 如果有就返回 ture, 否则返回 false
*/
int Find_Exist(int* save_Frame, int n, int addr)
{
	for (int i = 0; i < n; i++)
	{
		if (save_Frame[i] == addr)
		{
			return i;
		}
	}
	return -1;
}

void Print_Menu()
{
	/* 输入模块 */
	cout << "+---------------------------------------+" << endl;
	cout << "|\t***算法清单***\t\t\t|" << endl;
	cout << "|\t1.最佳置换算法(OPT)\t\t|" << endl << "|\t2.先进先出算法(FIFO)\t\t|" << endl;
	cout << "|\t3.最近最久未使用算法(LRU)\t|" << endl << "|\t4.最不经常使用算法(LFU)\t\t|" << endl;
	cout << "|\t0.退出\t\t\t\t|" << endl;
	cout << "+---------------------------------------+" << endl;
}

void Print_Frame(int* save_Frame, int n)
{
	cout << "\t";
	for (int i = 0; i < n; i++)
	{
		if (i == 0)
		{
			if (save_Frame[i] == -999)
				cout << "/ /";
			else
				cout << "/" << save_Frame[i] << "/";
		}
		else
		{
			if (save_Frame[i] == -999)
				cout << " /";
			else
				cout << save_Frame[i] << "/";
		}
	}
	cout << endl;
}
void Init(int* n, int* len, int*& save_Frame, int*& interview_Array)
{
	cout << "请输入 n :";
	cin >> *n;
	save_Frame = new int[*n];
	for (int i = 0; i < *n; i++)
		save_Frame[i] = -999;

	cout << "请输入地址走向的长度：";
	cin >> *len;
	cout << "请输入地址走向:";
	interview_Array = new int[*len];
	for (int i = 0; i < *len; i++)
		cin >> interview_Array[i];
}

/*
* 缺页中断率：
* 假设进程 P 在运行中成功的内存访问次数为 s
* 不成功的访问次数为 F，则缺页中断率为 R = F/(S+F)
*/
double Page_Loss_Rate(int S, int F)
{
	double ans = 1.0 * F / (1.0 * S + 1.0 * F) * 100;
	return ans;
}

int Find_LeastInteviewTime(int sta, int addr, int* interview_Array, int len)
{
	for (int i = sta; i < len; i++)
	{
		if (interview_Array[i] == addr)
		{
			return i - sta;
		}
	}
	return 99999;
}
/*
* 最佳置换算法(OPT)：
* 将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
* 数据结构：数组
*/
void OPT_Agorithm()
{
	cout << "欢迎使用 OPT " << endl;
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len, save_Frame, interview_Array);
	//测试样例： 1 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		addr = interview_Array[iter];
		iter++;
		cout << endl << "第" << iter << "轮：";
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);
			}
			else // 未命中，但有空间，" << "\" << addr << "\" 被装入 
			{
				fail_time++;
				cout << "未命中，" << "\"" << addr << "\" 被装入 \t------->";
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int* least_Time = new int[n];
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					least_Time[i] = Find_LeastInteviewTime(iter, save_Frame[i], interview_Array, len);
					if (least_Time[i] > max_Time)
					{
						max_Time = least_Time[i];
						index = i;
					}
				}
				cout << "\"" << addr << "\" 替换了 \"" << save_Frame[index] << "\"\t\t------->";
				save_Frame[index] = addr;
				Print_Frame(save_Frame, n);
				delete[] least_Time;
			}
		}
	}
	cout << endl;
	cout << "缺页次数为：" << fail_time << endl;
	cout << "缺页中断率 R = " << Page_Loss_Rate(score, fail_time) << "%" << endl;
	delete[] save_Frame;
	delete[] interview_Array;
}

void Update_InHereTime(int* in_HereTime, int n, int ind)
{
	for (int i = 0; i < n; i++)
	{
		in_HereTime[i]++;
	}
	if (ind != -1)
		in_HereTime[ind] = 0;
}
/*
* 先进先出算法(FIFO)：
* 淘汰最先使用内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
* 数据结构：数组
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
*/
void FIFO_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len, save_Frame, interview_Array);

	int* in_HereTime = new int[n];
	for (int i = 0; i < n; i++)
		in_HereTime[i] = 0;		// 初始化都为零

	//测试样例： 2 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		cout << endl << "第" << iter << "轮：";
		addr = interview_Array[iter];
		iter++;
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);
				Update_InHereTime(in_HereTime, cnt, -1);
			}
			else // 未命中，但有空间
			{
				fail_time++;
				cout << "未命中，" << "\"" << addr << "\" 被装入 \t------->";
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				Update_InHereTime(in_HereTime, cnt, cnt);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);
				Update_InHereTime(in_HereTime, n, -1);
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					if (in_HereTime[i] > max_Time)
					{
						max_Time = in_HereTime[i];
						index = i;
					}
				}
				cout << "\"" << addr << "\" 替换了 \"" << save_Frame[index] << "\"\t\t------->";
				save_Frame[index] = addr;
				Print_Frame(save_Frame, n);
				int ind = Find_Exist(save_Frame, n, addr);
				Update_InHereTime(in_HereTime, n, ind);
			}
		}
	}
	cout << endl;
	cout << "缺页次数为：" << fail_time << endl;
	cout << "缺页中断率 R = " << Page_Loss_Rate(score, fail_time) << "%" << endl;
	delete[] save_Frame;
	delete[] interview_Array;
	delete[]  in_HereTime;
	return;
}

int Find_LeastNotUseTime(int end, int addr, int* interview_Array)
{
	for (int i = end - 1; i >= 0; i--)
	{
		if (interview_Array[i] == addr)
		{
			// cout << " i = " << i << endl;
			return end - i;
		}
	}
	return 99999;
}
/*
* 最近最久未使用算法(LRU)：
* 淘汰最近最久未被使用的页面。
* 数据结构：数组
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
*/
void LRU_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len, save_Frame, interview_Array);

	//测试样例： 3 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		addr = interview_Array[iter];
		iter++;
		cout << endl << "第" << iter << "轮：";
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);

			}
			else // 未命中，但有空间
			{
				fail_time++;
				cout << "未命中，" << "\"" << addr << "\" 被装入 \t------->";
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int* Not_UseTime = new int[n];
				int max_Time = 0;
				int index;
				for (int i = 0; i < n; i++)
				{
					Not_UseTime[i] = Find_LeastNotUseTime(iter, save_Frame[i], interview_Array);
					if (Not_UseTime[i] > max_Time)
					{
						max_Time = Not_UseTime[i];
						index = i;
					}
				}
				cout << "\"" << addr << "\" 替换了 \"" << save_Frame[index] << "\"\t\t------->";
				save_Frame[index] = addr;
				Print_Frame(save_Frame, n);
				delete[] Not_UseTime;
			}
		}
	}
	cout << endl;
	cout << "缺页次数为：" << fail_time << endl;
	cout << "缺页中断率 R = " << Page_Loss_Rate(score, fail_time) << "%" << endl;
	delete[] save_Frame;
	delete[] interview_Array;
}

int Find_LeastNotInterviewTime(int n, int* interview_Time)
{
	int min_Time = 99999;
	int ind;
	for (int i = 0; i < n; i++)
	{
		if (interview_Time[i] < min_Time)
		{
			min_Time = interview_Time[i];
			ind = i;
		}
	}
	return ind;
}
/*
* 最不经常使用算法(LFU):
* 即选择最近一段时间内最长时间没有被访问过的页面进行置换
* 数据结构：数组
* 第一行输入参数：n ，代表存储页框数
* 第二行输入参数：a_1、a_2、...、a_n，代表访问地址的走向
* 输出要求：输出内存驻留的页面集合，缺页次数以及缺页率；
*/
void LFU_Agorithm()
{
	int n, len, * save_Frame = NULL, * interview_Array = NULL;
	Init(&n, &len, save_Frame, interview_Array);

	int* interview_Time = new int[n];
	for (int i = 0; i < n; i++)
		interview_Time[i] = 0;

	// 测试样例一：4 3 12 2 3 2 1 5 2 4 5 3 2 5 2
	// 测试样例二：4 3 12 2 3 2 1 2 1 5 4 2 4 4 6
	int addr;
	int cnt = 0;
	int score = 0;
	int fail_time = 0;
	int iter = 0;
	while (iter < len)
	{
		cout << endl << "第" << iter << "轮：";
		addr = interview_Array[iter];
		iter++;
		if (cnt < n)
		{
			if (Find_Exist(save_Frame, cnt, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);
				int ind = Find_Exist(save_Frame, cnt, addr);
				interview_Time[ind]++;
			}
			else // 未命中，但有空间
			{
				fail_time++;
				cout << "未命中，" << "\"" << addr << "\" 被装入 \t------->";
				save_Frame[cnt] = addr;
				Print_Frame(save_Frame, n);
				cnt++;
			}
		}
		else
		{
			if (Find_Exist(save_Frame, n, addr) != -1)
			{
				score++;
				cout << "\"" << addr << "\" 被命中了\t\t------->";
				Print_Frame(save_Frame, n);
				int ind = Find_Exist(save_Frame, n, addr);
				interview_Time[ind]++;
			}
			else // 未命中，但没了空间
			{
				fail_time++;
				int index = Find_LeastNotInterviewTime(n, interview_Time);
				cout << "\"" << addr << "\" 替换了 \"" << save_Frame[index] << "\"\t\t------->";
				save_Frame[index] = addr;
				interview_Time[index] = 0;
				Print_Frame(save_Frame, n);
			}
		}
	}
	cout << endl;
	cout << "缺页次数为：" << fail_time << endl;
	cout << "缺页中断率 R = " << Page_Loss_Rate(score, fail_time) << "%" << endl;
	delete[] save_Frame;
	delete[] interview_Array;
	delete[] interview_Time;
}

七、参考附录

无。
(纯手敲，原创，可能存在未知 Bug，烦请指正…)

⭐️ ⭐️文章来源地址https://www.toymoban.com/news/detail-457392.html

到了这里，关于页面置换算法——C/C++实现 [ OTP, FIFO, LRU, LFU + 开源代码 + 详细解析]的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！