前言

在地址映射过程中，若发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

一、LRU算法是什么？

LRU 是 Least Recently Used 的缩写，即最近最少使用，是一种常见的页面置换算法。LRU 算法的基本理念是：最近使用的数据在未来一段时间仍会被使用，已经很久没有使用的数据可能在未来较长的一段时间内不会被使用。所以在需要淘汰页面时，每次选择淘汰最久没有被访问的页面。

二、基于 golang 的实现

1.构建结构体

通过 golang 内置的双向链表 list.List 存储每个节点，同时维护一个哈希表，可快速判断需要加载的数据是否已经在链表中存在，无须遍历链表查找，典型的以空间换时间的方式。

type LRU struct {
	maxByte int64                    //最多存储数据的字节个数，超过此数量便会触发数据的淘汰
	curByte int64                    //目前存储的字节个数
	list    *list.List               //使用go语言内置的双向链表存储节点
	cache   map[string]*list.Element //通过节点的key快速定位到属于哪个节点，不需遍历双向链表
	mu      sync.RWMutex             //读写锁，保证并发安全
}

type Entry struct {
	Key   string //每个节点的唯一标识，作为key储存到lru的cache里
	Value []byte //携带的数据
}

// New Constructor of LRU
func New(maxByte int64) *LRU {
	return &LRU{
		maxByte: maxByte,
		curByte: 0,
		list:    list.New(),
		cache:   make(map[string]*list.Element),
	}
}

2.读取数据

输入 key 查找数据，直接根据 key 去哈希表中查找，查找成功则将此节点转移至双向链表头部，并返回存储的数据，反之返回查找失败。

// Get look up a key`s value
func (l *LRU) Get(key string) ([]byte, bool) {
	l.mu.RLock()
	defer l.mu.RUnlock()

	if ele, exist := l.cache[key]; exist {
		l.list.MoveToFront(ele) //此元素被访问，移动到链表最前面
		if entry, ok := ele.Value.(*Entry); ok {
			return entry.Value, true
		}
	}

	return nil, false
}

3.淘汰数据

每次淘汰双向链表尾部数据，更新哈希表，删除该节点 key 对应的 value，最后更新 lru 结构体已用字节数。

// RemoveOldest remove entry from linklist back
func (l *LRU) removeOldest() {
	ele := l.list.Back() //取出链表尾部节点
	if ele != nil {
		l.list.Remove(ele) //删除节点
		if entry, ok := ele.Value.(*Entry); ok {
			delete(l.cache, entry.Key)                                   //哈希表删除该节点key
			l.curByte -= int64(len(entry.Key)) + int64(len(entry.Value)) // 调整已使用字节数
		}
	}
}

4.新增数据

数据新增时，需要判断该数据是否已存在，存在则移动到链表头部，并更新使用字节数。不存在则直接插入头部，并更新哈希表。最后根据最大字节数和已使用字节数比较，判断是否需要淘汰数据。

// Add a value to lru
func (l *LRU) Add(key string, value []byte) {
	l.mu.Lock()
	defer l.mu.Unlock()

	// 两种情况
	if ele, ok := l.cache[key]; ok {
		l.list.MoveToFront(ele)
		if entry, ok := ele.Value.(*Entry); ok {
			l.curByte += int64(len(value)) - int64(len(entry.Value)) // value改变的话需要改变已用字节数
			entry.Value = value
		}
	} else {
		ele := l.list.PushFront(&Entry{Key: key, Value: value})
		l.cache[key] = ele
		l.curByte = int64(len(key)) + int64(len(value))
	}

	// 已使用字节数大于最大字节数时，需要移除链表尾部节点，直到已使用字节数小于最大字节数
	for l.maxByte > 0 && l.maxByte < l.curByte {
		l.RemoveOldest()
	}
}