一、引言
第一次接触页面置换算法是在大学里学习《操作系统》时候，起初觉得只是几个简单的算法而已，并没有太多的关注，随着阅历的增长，才发现页面置换算法的思想出现在缓存、分布式、中间件、网络等各个领域，就比如说今天的主角——页面置换中的一种算法LRU，不仅出现在操作系统对内存的管理中，还出现在Redis管理键的的策略中，所以在学习的时候，我们应当将共同的东西抽象出来一起总结，这样就能得到更深的理解。这篇博客将带领大家以通俗的语言与简单易懂的图示来描述常用的页面置换算法思想与实现。
二、FIFO
FIFO(First in First out)
，顾名思义，先进先出算法，这个算法符合人们的思维，先来的先走，实现也比较的简单，核心原则是：
如果一个页先进入内存，那么这个页将被先置换出去。
可以使用队列来完成这一功能，但是使用链表可以更快，使用头尾指针，将插入语删除操作达到
O(1)
级别。
package pagereplacement;
public class FIFO{
private Node head=null;
private Node tail=null;
private int length;
private int size;
public FIFO(int size){
this.size=size;
}
public void set(int value){
Node node=new Node(value);
if(size == length){
remove();
}
if(head == null && tail == null){
head=node;
tail=node;
head.next=null;
}else{
tail.next=node;
tail=tail.next;
}
length++;
}
public Node remove(){
if(head == null){
return null;
}
Node node=head;
head=head.next;
return node;
}
public String toString(){
String t="";
Node cur=head;
while(cur != null){
t+=cur.value+" ";
cur=cur.next;
}
return t;
}
public static void main(String[] args) {
FIFO fifo=new FIFO(3);
fifo.set(1);
fifo.set(2);
fifo.set(3);
System.out.println(fifo);
fifo.set(4);
System.out.println(fifo);
}
static class Node{
int value;
Node next;
public Node(int value){
this.value=value;
this.next=null;
}
}
}
//输出：1 2 3
// 2 3 4
三、LFU
LFU(Least Frequently Used)
，最近最少使用算法，在淘汰掉旧的页面时，会将最近一段时间内使用次数最少的那一页抛弃。它的核心思想基于
假如一段时间内这一页数据使用的最少，那么我们判定将来也会使用的很少
来实现的。假如内存中所能存的页数为3：
set(1);
set(2);
get(1);
get(2);
set(3);
set(4);
经过这些操作后，在
set(4)
的时候淘汰的是3，因为它被访问的最少。在下列图示时，我们将最少访问的页放置于链表的末尾
为了尽量的减少时间复杂度，在实现
LFU
算法的时候可以利用数组加上
Map
来实现，这样可以保证
LFU
算法的插入与访问都达到
O(1)
的地步，但是删除需要遍历整个数组，所以删除的性能为
O(n)
。代码实现如下：
public class LFU{
private int length;
private Map<Integer, Integer> map = null;
private int [] array=null;
public LFU(int size){
map=new HashMap<>();
array=new int[size];
length=0;
}
public void set(int value){
if(length == array.length){
remove();
}
array[length++]=value;
if(map.get(value) == null){
map.put(value, 1);
}else{
System.out.println("该页面已存在");
}
}
public void get(int value){
int temp=map.get(value);
map.put(value, ++temp);
System.out.println("命中"+value);
}
private void remove(){
int temp=map.get(array[0]);
int cur=0;
for(int i=1;i<length;i++){
if(temp > map.get(array[i])){
temp= map.get(array[i]);
cur=i;
}
}
map.remove(array[cur]);
for(int i=cur;i<length-1;i++){
array[i]=array[i+1];
}
length--;
}
public String toString(){
return Arrays.toString(array);
}
public static void main(String[] args) {
LFU lfu=new LFU(3);
lfu.set(1);
lfu.set(2);
lfu.get(1);
lfu.get(2);
lfu.set(3);
lfu.set(4);
System.out.println(lfu.toString());
}
}
//输出:[1,2,4]
四、LRU
LRU（Least Recently Used）
，最近最久未使用算法，它与
LFU
的区别在于，
LFU
是以最少使用次数为替换页标准，而
LRU
是采用
如果某页数据在最近一段时间内没有使用，那么将来也不会使用的思想
来实现的，继续以讲解
LFU
的例子来说这两者有什么不同：
假如内存中所能存的页数为3：
set(1);
set(2);
get(1);
get(2);
set(3);
set(4);
LFU
会淘汰掉3这一页面，而
LRU
会淘汰掉1这个页面，因为1这一页面是最久未使用的，在下列图示中，我们以顶层为最久未使用的：
代码实现可以参照
LFU
的实现，只不过是以时间来参照的，而不是使用使用频率。
class LRUCache extends LinkedHashMap<Integer, Integer> {
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}