内存管理算法 LRU

LRU（Least recent use）的背景

我们知道的是当 CPU 需要读取数据的时候一般是先从内存中读取数据，然后内存从磁盘中读取数据，当内存快要被之前加载的文件耗尽的时候，我们就需要对已经存在的页面进行置换操作，从而提供空间来容纳从磁盘中读取的数据。在学习操作系统的时候书本上为我们介绍过几个缓存策略，分别是OPT，FIFO，LRU，Clock，LFU。这些概念中最常用的，同时也是最长考察的，就是 LRU 调度算法，因此我们本文主要介绍一下LRU 的原理和算法实现，但是笔者不建议为了面试而只学习 LRU 这一种调度方式，其他的也需要做了解，知识的广度应该是软件工程的基本素养。

什么是 LRU ？

LRU(Least Recently Used)，即最近最少使用，为了理解这个比较抽象的概念我们需要结合具体的案例。这里我们不针对太过于具体的场景来分析，这样对我们写 LRU 的代码没有用，就针对下面笔者交代的概念和场景来理解便好。

//序列即为我们需要读入内存里面的内容    
假设 序列为 4 3 4 2 3 1 4 2
//物理块即为内存中实际可以容下所读取的内容
物理块有3个 则
//调度方式开始
首轮 4调入内存 4
次轮 3调入内存 3 4
之后 4调入内存 4 3
//2调度进入之后容量就满了，如果这个时候需要用的是
//容器里面已经存在的数据就从后面放到前面来（上面的4第二次被加载的时候就是这样的）
//如果容器里面不存在，那么就要删除容器中“最近最少使用的”数据
//然后将需要用的数据放在最前面（也就是刚用）
之后 2调入内存 2 4 3
之后 3调入内存 3 2 4
之后 1调入内存 1 3 2（因为最少使用的是4，所以丢弃4）
之后 4调入内存 4 1 3（原理同上）
最后 2调入内存 2 4 1

算法中需要执行的操作

首先我们需要在构造函数里面确定这个 LRU 的物理容量有多大
我们需要将我们的数据放到这个物理容量当中
我们需要将这个数据从物理容量中取出
如果我们当前取入的数据是我们原来就有的数据，就将数据从后面放到前面
如果我们当前取入的数据我们原来的数据里面没有，就把原来链表中最后的一个节点删除，然后将我们刚取入的节点放到最前面
这么一看我们似乎对上面的两中情况都需要执行将节点放到最前面来的操作，因此我们单独写一个这样的操作

使用的数据结构

这个地方很明显需要一个 LinkedList ，但是这一个够吗，我觉得是不够的，为能够在查找的时候我们能够快速查找我们需要一个 map，因此最后确定下来就是 LinkedList + map

LinkedList 的构成

struct Node{
    int key;
    int val;
    Node* next;
    Node(int k, int v):key(k),val(v),next(NULL){}//构造函数
}

map 的构成

map<int, Node*>mp;

技巧

这个地方说是技巧其实也不能全算是技巧，但是你如果不知道的话那对你来说就是技巧了。由于我们这个地方对链表的操作会比较频繁，尤其是链表的删除，所以这个地方针对链表的输出，我们可以这样进行。假设需要删除的节点为 A，需要删除节点的后面的这个节点为 B 在删除的时候我们将 A 的 next 指针指向 B 的 next，然后将 A B 的值交换一下，B 的 next 指向 NULL，free B，但是这个地方有 map 还有 key 所以交换的时候需要将 key 还有 map 里面的值都交换一下。具体的体现在代码中就是

Node* B = A->next;
A->next = B->next;
swap(A->val, B->val);
B->next = NULL;
free(B);

完整代码

#include <iostream>
#include <map>
#include <iterator>
#include <algorithm>
#include <cstdio>
using namespace std;

struct Node{
    int key;
    int val;
    Node *next;
    Node(int k, int v):key(k),val(v),next(NULL){}
};

class LRUCache{
public:
    LRUCache(int capacity){
        count = 0;//缓存中数目
        size = capacity;//缓存初始化的容量
        cacheList = NULL;//目前还没有节点进入
    }
    int get(int key){
        if(cacheList == NULL){
            return -1;
        }
        map<int, Node*>::iterator it = mp.find(key);
        if(it == mp.end()){
            return -1;
        }else{
            Node *newNode = it->second;
            pushNewNodeToFront(newNode);
            return newNode->val;
        }
    }
    void put(int key, int val){
        if(cacheList == NULL){
            cacheList = new Node(key, val);
            cacheList->next = NULL;
            mp[key] = cacheList;
            count++;
        }else{
            map<int,Node*>::iterator it = mp.find(key);
            if(it == mp.end()){//之前就没有这个元素
                if(count == size){//已经满了
                    Node *p = cacheList;
                    Node *pre = p;//尾节点的前一个节点
                    while(p->next != NULL){//遍历到节点尾部
                        pre = p;
                        p = p->next;
                    }
                    mp.erase(p->key);
                    count--;
                    if(pre == p){
                        cacheList = NULL;
                    }else{
                        pre->next = NULL;
                    }
                    free(p);
                }
                //删除完节点之后，再开始加入节点
                Node *newNode = new Node(key, val);
                newNode->next = cacheList;
                cacheList = newNode;
                mp[key] = cacheList;
                count++;
            }else{//之前有这个元素
                Node* newNode = it->second;
                newNode->val = val;
                pushNewNodeToFront(newNode);
            }
        }
    }

    void pushNewNodeToFront(Node* newNode){
        if(count == 1) return;
        if(newNode == cacheList) return;
        Node* Next = newNode->next;
        if(Next){
            newNode->next = Next->next;
            swap(newNode->key, Next->key);
            swap(newNode->val, Next->val);
            Next->next = cacheList;
            cacheList = Next;

            swap(mp[newNode->key], mp[Next->key]);
        }else{//当前的这个节点是最后一个节点
            Node *p = cacheList;
            while(p->next != newNode){
                p = p->next;

            }
            p->next = NULL;
            newNode->next = cacheList;
            cacheList = newNode;
        }
    }

private:
    int count;
    int size;
    Node *cacheList;
    map<int, Node*> mp;
};

更简洁的代码（使用了 STL）

#include<iostream>
#include<map>
#include<unordered_map>
#include<list>
using namespace std;

class LRUCache{
private:
    int cap;
    list<pair<int,int> > l;
    unordered_map<int,list<pair<int,int> > :: iterator> m;

public:
    LRUCache(int capacity):cap(capacity){};
    int get(int key){
        auto it = m.find(key);
        if(it == m.end()){
            return -1;
        }
        l.splice(l.begin(), l, it -> second);
        return it -> second -> second;
    }
    void set(int key, int val){
        auto it = m.find(key);
        if(it != m.end()){
            l.erase(it->second);
        }
        l.push_front(make_pair(key,val));
        m[key] = l.begin();
        ig(int(m.size()) > cap){
            int k = l.rbegin() -> first;
            l.pop_back();
            m.erase(k);
        }
    }
};

算法