C语言 操作系统实验二 LRU_lru c语言

注：

本文是两个页面淘汰模拟算法的第二篇算法。

我是个菜鸡，发文是为了纪念自己完成了代码，以及累计自己的经验。

如有知识错误或者算法有逻辑漏洞请各位大佬高抬贵手。

实验环境：win10、VS2022（C++）

PS：虽然是cpp文件，实际上是披着cpp的c

        运行前，首先要在预处理器上插入_CRT_SECURE_NO_WARNINGS，避免运行错误，在插入前要用;隔开。

核心思想：和FIFO相同，利用两条链表分别模拟内存中的页(节点为页块)、外存，数组则存放访问序列，

通过循环将逐一输出访问的页面，在交换页面时，从模拟的外存链表中循环查找后赋值给相应的节点。（注意：不同结构体不能交换节点，由于时间有限，没有考虑同一结构体下两链表的做法）

唯一区别在于，FIFO对淘汰页面采取先来先走的态度，所以在编代码时要按顺序踢掉前面的页块，设置循环标记即可

而LRU则是判断最近最久时间没来的页面，在编程时，在页块的结构中增加int frequency，每当调用页面时，将记录当前的调用次数，缺页替换时，在页面模拟链表中找出当前列表调用次数最小的即可

完整代码：

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
#define NULL 0
#define getpch(type) (type*)malloc(sizeof(type))//创建列表是模仿页面
 
struct Numb//页框
{
	int num;
	int frequency;
	struct Numb* link;
}*ready = NULL, * first, * p, * last;
 
struct romnum
{
	int n;
	struct romnum* link2;
}*ready2 = NULL, * first2, * p2, * last2;
 
int order[1000] = { 0 };//调用序列
int page = 0;//页框数
int pagenumber = 0;//页调用次数
int h = 0;//记录外存链表的长度
int flag = 0;//缺页记录
int lack = 0;//记录缺页情况
int time = 0;
int log = 0;//保证在为装满页面时发生能找到相应页块的情况下不计为缺页的标志
 
void Link()
{
	if (ready == NULL)
	{
		ready = p;
		first = p;
		last = p;
	}
	else
	{
		last->link = p;
		last = p;
	}
}
 
void Rom(int i)
{
	if (ready2 == NULL)//如果没有链表则创建一个链表头
	{
		p2 = getpch(romnum);
		p2->n = order[i];
		p2->link2 = NULL;
		ready2 = p2;
		first2 = p2;
		last2 = p2;
		//printf("last2->n = %d\n", last2->n);
		h++;
	}
	else
	{
		first2 = ready2;
		do//循环判断order在外存链表中是否有有相同内容，不同则存入
		{
 
			if (order[i] != first2->n)//如果order值不同于当前节点值，则继续查找
			{
				if (first2->link2 == NULL)//如果查到尾节点依旧没有相同值
				{
					p2 = getpch(romnum);//创建节点
					p2->n = order[i];
					p2->link2 = NULL;
					last2->link2 = p2;//尾节点链接新节点
					last2 = p2;
					//printf("last2->n = %d\n", last2->n);	
					h++;
					break;
				}
				else//如果不在尾节点则按顺序进行查找
				{
					first2 = first2->link2;
				}
			}
			else
			{
				break;
			}
		} while (1);
	}
}
 
void input()
{
	printf("请输入符合页框数的页面访问序列(禁止输入0)：\n");
	for (int i = 0; i < pagenumber; i++)//记录访问序列
	{
		scanf("%d", &order[i]);
		/*printf("order[%d] = %d ", i, order[i]);
		printf("\n");*/
		Rom(i);
	}
 
	for (int i = 0; i < page; i++)//成立页
	{
		p = getpch(Numb);
		p->num = 0;
		p->frequency = 0;
		//printf("%d ", p->num);
		p->link = NULL;
		Link();
	}
}
 
void destory()
{
	for (int i = 0; i < page; i++)
	{
		p = ready;
		ready = ready->link;
		p->link = NULL;
		free(p);
	}
	for (int i = 0; i < h; i++)
	{
		p2 = ready2;
		ready2 = ready2->link2;
		p2->link2 = NULL;
		free(p2);
	}
}
 
void output()
{
	first = ready;
	if (flag == page || lack < page && log != 1)
	{
		printf("* ");
	}
	else
	{
		printf("  ");
	}
		for (int i = 0; i < page; i++)
		{
			printf("%d ", first->num);
			first = first->link;
		}
		printf("\n");
 
}
 
void check(int i)
{
	first2 = ready2;
	for (int j = 0; j < h; j++)
	{
		if (order[i] != first2->n)
		{
			first2 = first2->link2;
		}
		else
		{
			break;
		}
	}
 
}
 
void LRU(int i)
{
	log = 0;
	//此阶段开启时，空页应准备就绪，页的输出顺序也准备完毕，外存链表也应准备完毕
	for (int j = 0; j < page; j++)
	{
		if (order[i] != first->num)
		{
			if (first->num == 0)//需要填充
			{
				check(i);
				first->num = first2->n;
				first->frequency = i;
				output();
				lack++;
				break;
			}
		}
		else if (order[i] == first->num)
		{
			first->frequency = i;
			log = 1;
			output();
			break;//找到所需要的块
		}
 
		first = first->link;//运行到最后一轮为野指针
 
		flag += 1;//若flag等于page的值，说明在既没有填充，又没有相同的情况下，没有找到相同的值，表示缺页，小于则表示要么在页（链表）中找到符合条件的块，要不存入块中
	}
	if (flag == page)
	{
		first = ready;
		p = ready;
		check(i);
		lack++;
		for (int i = 0; i < page; i++)
		{
			if (first->frequency > p->frequency)
			{
				if (p->link == NULL && first->frequency > p->frequency)
				{
					first = p;
					break;
				}
				first = p;
			}
			p = p->link;
		}
		first->num = first2->n;
		first->frequency = i;
		//printf("%d\n", p->num);
		output();
	}
}
 
int main()
{
	float sum = 0;
	printf("请输入页框数和页数：\n");
	scanf("%d", &page);
	scanf("%d", &pagenumber);
	printf("page = %d, pagenumber = %d\n", page, pagenumber);
	input();
	first2 = ready2;
	p = ready;
	for (int i = 0; i < pagenumber; i++)//循环调出页
	{
		LRU(i);
		first = ready;
		flag = 0;
	}
	sum = (float)lack / pagenumber;
	printf("缺页率是：%0.1f%%", sum * 100);
	destory();
	return 0;
}

注：*代表缺页状况，替换后的输出