概念理解
1.LRU是Least Recently Used的缩写,即最近最少使用页面置换算法。是为虚拟页式存储管理服务的。
2.操作系统课程里有学过,在内存不够的场景下,淘汰就内容的策略,淘汰掉最不经常使用。
LRU原理
可以用一个特殊的栈来保存当前正在使用的各个页面的页面号。当一个新的进程访问某页面时,便将该页面号压入栈顶,其他的页面号往栈底移,如果内存不够,则将栈底的页面号移除。这样,栈顶始终是最新被访问的页面的编号,而栈底则是最近最久未访问的页面的页面号。
在一般标准的操作系统教材里,会用下面的方式来演示 LRU 原理,假设内存只能容纳3个页大小,按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间,在上面的,是最近访问的,在下面的是,最远时间访问的,LRU就是这样工作的。
但是如果让我们自己设计一个基于 LRU 的缓存,这样设计可能问题很多,这段内存按照访问时间进行了排序,会有大量的内存拷贝操作,所以性能肯定是不能接受的。
那么如何设计一个LRU缓存,使得放入和移除都是 O(1) 的,我们需要把访问次序维护起来,但是不能通过内存中的真实排序来反应,有一种方案就是使用双向链表。
下面使用c语言实现的代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 3
int count=0;
typedef struct node{
int data;
struct node* prev;
struct node* next;
}*linklist,linkList;
//把某个节点进行删除
void del(linklist d){
d->prev->next=d->next;
d->next->prev=d->prev;
free(d);
count--;
}
//在头节点插入数据
void insert_data(linklist tou,int data){
linklist xin= (linklist)malloc(sizeof(linkList));
xin->data=data;
linklist hou=tou->next;
tou->next=xin;
xin->prev=tou;
xin->next=hou;
hou->prev=xin;
count++;
}
void du(linklist tou,linklist wei,int data){
//判断是否存在
int i;
bool is_zai=false;
linklist xun=tou;
for(i=1;i<=count;i++){
xun=xun->next;
if(xun->data==data){
is_zai=true;
break;
}
}
//数据存在
if(is_zai) {
del(xun);
insert_data(tou,data);
}
//数据不存在
else{
//已满
if(count==MAX){
//删除最后一个
del(wei->prev);
insert_data(tou,data);
}
else{
insert_data(tou,data);
}
}
}
void mianli(linklist tou){
linklist xun=tou;
int i;
for(i=1;i<=count;i++){
xun=xun->next;
printf("%d ",xun->data);
}
}
int main(){
//创建头节点和尾节点
linklist tou=(linklist)malloc(sizeof(linkList));
linklist wei=(linklist)malloc(sizeof(linkList));
tou->next=wei;
tou->prev=NULL;
wei->prev=tou;
wei->next=NULL;
for(;;){
printf("\n\n\n1.请输入您要搜索的数据\n");
printf("2.输出所有数据\n");
int num;
printf("请输入功能编号:");
scanf("%d",&num);
switch(num){
case 1:
printf("请输入您要搜索的数据:");
int data;
scanf("%d",&data);
du(tou,wei,data);
break;
case 2:
mianli(tou);
break;
}
}
}