缓存算法(页面置换算法)总结

首先解释一下,缓存算法和内存页面置换算法(Page Replacement Algorithm)的核心思想是一样的,都是给定一个有限的空间,设计一个算法来更新和访问里面的数据,所以把它们放在一起讨论总结。下面提到缓存算法的同时,也指代页面置换算法。

常见的缓存算法有 FIFO、Least Recently Used (LRU)、Least Frequently Used (LFU)。

FIFO

FIFO 算法是一种比较容易实现的算法。它的思想是先进先出(FIFO,队列),这是最简单、最公平的一种思想,即如果一个数据是最先进入的,那么可以认为在将来它被访问的可能性很小。空间满的时候,最先进入的数据会被最早置换(淘汰)掉

FIFO 算法的描述:设计一种缓存结构,该结构在构造时确定大小,假设大小为 K,并有两个功能:

  1. set(key,value):将记录(key,value)插入该结构。当缓存满时,将最先进入缓存的数据置换掉。
  2. get(key):返回key对应的value值。

实现:维护一个FIFO队列,按照时间顺序将各数据(已分配页面)链接起来组成队列,并将置换指针指向队列的队首。再进行置换时,只需把置换指针所指的数据(页面)顺次换出,并把新加入的数据插到队尾即可。

缺点:判断一个页面置换算法优劣的指标就是缺页率,而FIFO算法的一个显著的缺点是,在某些特定的时刻,缺页率反而会随着分配页面的增加而增加,这称为Belady现象。产生Belady现象现象的原因是,FIFO置换算法与进程访问内存的动态特征是不相容的,被置换的内存页面往往是被频繁访问的,或者没有给进程分配足够的页面,因此FIFO算法会使一些页面频繁地被替换和重新申请内存,从而导致缺页率增加。因此,现在不再使用FIFO算法。

LRU

LRU(The Least Recently Used,最近最久未使用算法)是一种常见的缓存算法,在很多分布式缓存系统(如Redis, Memcached)中都有广泛使用。

LRU算法的思想是:如果一个数据在最近一段时间没有被访问到,那么可以认为在将来它被访问的可能性也很小。因此,当空间满时,最久没有访问的数据最先被置换(淘汰)

LRU算法的描述: 设计一种缓存结构,该结构在构造时确定大小,假设大小为 K,并有两个功能:

  1. set(key,value):将记录(key,value)插入该结构。当缓存满时,将最久未使用的数据置换掉。
  2. get(key):返回key对应的value值。

实现:最朴素的思想就是用数组+时间戳的方式,不过这样做效率较低。因此,我们可以用双向链表(LinkedList)+哈希表(HashMap)实现(链表用来表示位置,哈希表用来存储和查找),在Java里有对应的数据结构LinkedHashMap

LeetCode上有关于LRU的一道题(LeetCode #146):

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

  • get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
  • set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

这里我用了双向链表+哈希表实现的。

C++ code(72 ms):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#define DEFAULT_LIST_SIZE 10
class LRUCache {
private:
class Node {
public:
int key;
int value;
Node* pre;
Node* next;
Node(int key,int value,Node* pre,Node* next) {
this->key = key;
this->value = value;
this->pre = pre;
this->next = next;
}
};
int count;
int size;
unordered_map<int,Node*> mp;
Node* cacheHead;
Node* cacheTail;
void push_front(Node* cur) {
if(count == 1 || cur == cacheHead) {
return;
}
if(cur == cacheTail) {
cacheTail = cur->pre;
}
cur->pre->next = cur->next;
if(cur->next != nullptr) {
cur->next->pre = cur->pre;
}
cur->next = cacheHead;
cur->pre = nullptr;
cacheHead->pre = cur;
cacheHead = cur;
}
public:
LRUCache() {
this->size = DEFAULT_LIST_SIZE;
this->count = 0;
this->cacheHead = nullptr;
this->cacheTail = nullptr;
}
LRUCache(int capacity):size(capacity) {
this->count = 0;
this->cacheHead = nullptr;
this->cacheTail = nullptr;
}
void set(int key, int value) {
if(cacheHead == nullptr) {
cacheHead = new Node(key,value,nullptr,nullptr);
mp[key] = cacheHead;
cacheTail = cacheHead;
count++;
}
else {
unordered_map<int,Node*>::iterator it = mp.find(key);
if(it == mp.end()) {
if(count == size) {
if(cacheHead == cacheTail && cacheHead != nullptr) {
mp.erase(cacheHead->key);
cacheHead->key = key;
cacheHead->value = value;
mp[key] = cacheHead;
}
else {
Node *p = cacheTail;
cacheTail->pre->next = cacheTail->next;
cacheTail = cacheTail->pre;
mp.erase(p->key);
p->key = key;
p->value = value;
p->next = cacheHead;
p->pre = cacheHead->pre;
cacheHead->pre = p;
cacheHead = p;
mp[cacheHead->key] = cacheHead;
}
}
else {
Node* p = new Node(key,value,nullptr,cacheHead);
cacheHead->pre = p;
cacheHead = p;
mp[cacheHead->key] = cacheHead;
count++;
}
}
else {
Node *p = it->second;
p->value = value;
pushFront(p);
}
}
}
int get(int key) {
if(cacheHead == nullptr)
return -1;
unordered_map<int,Node*>::iterator it = mp.find(key);
if(it == mp.end()) {
return -1;
}
else {
Node* p = it->second;
pushFront(p);
}
return cacheHead->value;
}
};

LFU 算法

LFU(Least Frequently Used ,最近最少使用算法)也是一种常见的缓存算法。

顾名思义,LFU算法的思想是:如果一个数据在最近一段时间很少被访问到,那么可以认为在将来它被访问的可能性也很小。因此,当空间满时,最小频率访问的数据最先被淘汰

LFU 算法的描述:

设计一种缓存结构,该结构在构造时确定大小,假设大小为 K,并有两个功能:

  1. set(key,value):将记录(key,value)插入该结构。当缓存满时,将访问频率最低的数据置换掉。
  2. get(key):返回key对应的value值。

算法实现策略:考虑到 LFU 会淘汰访问频率最小的数据,我们需要一种合适的方法按大小顺序维护数据访问的频率。LFU 算法本质上可以看做是一个 top K 问题(K = 1),即选出频率最小的元素,因此我们很容易想到可以用二项堆来选择频率最小的元素,这样的实现比较高效。最终实现策略为小顶堆+哈希表。

OPT算法

最佳页面置换算法(OPT,Bélády’s Algorithm)是一种理论上最佳的页面置换算法。它的思想是,试图淘汰掉以后永远也用不到的页面,如果没有则淘汰最久以后再用到的页面。因为这种算法必须知道进程访问页面的序列,而这是无法实现的,因此仅有理论意义。

文章目录
  1. 1. FIFO
  2. 2. LRU
  3. 3. LFU 算法
  4. 4. OPT算法