LRU算法list链表实现

horizonheart 2020-07-19

LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最少使用的页面予以淘汰。

1存在

存在就比较简单了,直接取出数据,页面数据不变,并把这个结点放在list链表最前面,删除原来位置的节点

2不存在

cache满

把最靠后的页面删除,然后把需要的页面放到最前的位置

cache不满

直接去读取数据,然后把他放在最前的位置

#include<iostream>
#include<list>
void fun(std::list<int>&L,int x)
{
    for(std::list<int>::iterator it=L.begin();it!=L.end();it++)
    {
        if(*it==x)
        {
            L.push_front(x);
            L.erase(it);
            return;
        }
    }
    std::cout<<"发生缺页中断 "<<x<<std::endl;
    L.pop_back();
    L.push_front(x);
}
int main()
{
    std::list<int>L;
    int sum, n, i,x;
    sum = 0;         //初始cache内没有数据
    std::cin>>n; //读入页数
    while (true)
    {
        scanf("%d", &x);
        if (x < 0)
        {
            break;
        }
        else
        {
            if (sum < n) //cache未满,放至后面
            {
                L.push_front(x);
                std::cout<<"发生缺页中断 "<<x<<std::endl;
                sum += 1; //并对cache+1
            }
            else
            {
                fun(L,x);
            }
        }
    }
    return 0;
}

C++ list 因为内部就是双向链表

相关推荐