最不常用置换算法LFT 最久未使用置换算法LRU 操作系统 C语言链表实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最不常用置换算法LFT 最久未使用置换算法LRU 操作系统 C语言链表实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3376字，纯文字阅读大概需要5分钟。

内容图文

?经过读题，我觉得这两个题目要表达的意思应该是完全相同的，当然也可能是我的理解出现了偏差。所以就把LRU 和 LFT 当作是一个。

?当然，因为这个缘故，我把最近最久未使用的LRU当作了最久未使用写到底，到最后发现还是更像最不常用置换算法LFT一些。

? 下面就是代码了，用C语言链表实现，希望能给同学们提供一种思路。

Main函数中有测试样例，思路什么的就不写了，代码中都已经注释出来了，如果有疑问的话请评论区留言。

---

LFT.h

#include<stdio.h>
#include<time.h>
#define MaxSize 21
typedef struct Node{
	struct Node *next;   	//页面指针，指向下一个 
	struct Node *pre;       //指向上一个 
	int num;            	//所属页面号 
}Node;

int n;              		//总的任务个数
int m;              		//主存大小
int used;                   //已经使用的主存块个数 
int missNum = 0;            //缺页次数 
Node *FirstNode;			//首元结点 
Node *current;       		//当前任务指针
Node *last;          		//指向最后一个任务 
int process[MaxSize];    	//任务队列 
double missRate;            //缺页中断率 
double t;   			    //时间 


//初始化首元结点 
void init(){

	FirstNode = (Node*)malloc(sizeof(Node));
	FirstNode->num = -1;
	FirstNode->next = FirstNode;
	FirstNode->pre = FirstNode;
	current = FirstNode;

}

//显示当前主存中的页面 
void show(){
	Node *show;
	show = FirstNode->next;
	printf("	  ·当前主存中页面为: ");
	while(show->num!=-1){
		printf("%d ",show->num);
		show = show->next;
	}
	printf("\n");
}

void miss(){
	printf("\n※ 总共的缺页次数为： %d\n",missNum);
	printf("※ 缺页中断率为: %.3lf",missNum*1.0/n); 
}

void input(){

	printf("请输入任务数： ");
	scanf("%d",&n); 
	printf("请输入主存大小： ");
	scanf("%d",&m);
	for(int i=1;i<=n;i++){
	printf("请输入第%d任务所在页面号： ",i);
	scanf("%d",&process[i]); 
	}
} 

//最久未使用页面置换算法
double LFT(){
	printf("************  最久未使用算法  ************\n");
	
	//输入 
	input();	
	
	clock_t start,end;
	//计时
	start = clock();
	 
	//初始化 
	init();
	
	
	//算法开始 
	
	printf("\n************  系统调用如下  ************\n");
	

	for(int i=1; i<=n; i++){ 
		printf("\n第%d次查找页面：\n",i);
		//第一次必定发生缺页中断 
		if(i==1){
			printf("\n	  ·发生缺页中断\n");
			Node *node;
			node = (Node*)malloc(sizeof(Node));
			node->num = process[1];
			node->next = FirstNode;
			node->pre = FirstNode;
			FirstNode->next = node;
			FirstNode->pre = node;
			missNum++;
			used++;
		}
		//接下来的要检查主存中有没有任务所在页数 
		else{
		while(current->num != process[i]) {
			
			//一直往下找 
			current = current->next;
			//current指向首元结点，证明发生了缺页中断 
			if(current->num == -1){
				
				printf("\n	  ·发生缺页中断\n");
				
				//如果主存块满了，删除最后没有用过的 
				if(used >= m){
				last = current->pre;
				last->pre->next = current;
				current->pre = last->pre; 
				last->next = NULL;
				last->pre = NULL;
				printf("	  ·删除页面: %d\n",last->num); 
				free(last);
				}
				//当前任务加入到队头(头插法) 
				Node *node;
				node = (Node*)malloc(sizeof(Node));
				node->num = process[i];
				node->pre = current;
				node->next = current->next;
				current->next->pre = node;
				current->next = node;
				missNum++;
				used++;
				break; 
			}//if 
		}//while
		if(current->num == process[i]){
			//证明不是因为break跳出的while循环,将此节点插入到队头 
			current->pre->next = current->next;
			current->next->pre = current->pre;
			current->pre = FirstNode;
			current->next = FirstNode->next;
			FirstNode->next->pre = current;
			FirstNode->next = current;
		}
	}//i>1
	end = clock();
	t =(double)( end - start );
	show();
	}//for
	miss();
	return t;
}

main:

#include"LFT.h"
#define totalTime CLOCKS_PER_SEC

int main()
{
	double t;
	t = LFT();
	printf("\n\n调用Lft算法共消耗时间：%.3lf ms\n",t/totalTime);
	system("pause");
	return 0;
}

/*
18
5
7
0
1
2
0
3
0
4
2
3
0
1
1
7
0
1
0
3
*/

内容总结

以上是互联网集市为您收集整理的最不常用置换算法LFT 最久未使用置换算法LRU 操作系统 C语言链表实现全部内容，希望文章能够帮你解决最不常用置换算法LFT 最久未使用置换算法LRU 操作系统 C语言链表实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---