页面置换算法

发表于 更新于 分类于
本文字数： 3.7k 阅读时长 ≈ 3 分钟
内容：等

页面置换算法

第一节 简介

  页面置换算法：操作系统中内存内没有空闲页面，而又需要加载一个未载入内存的页面时，需要有一个置换算法可以淘汰出页面以便腾出空间。最理想的算法是发生缺页时，把当前所存页面中最晚被访问的页面淘汰，但操作系统并不能预知页面下一次被访问的时间，所以无法实现。

  • FIFO: 先进先出，总是置换掉最先进入也就是停留最久的一页，理由是最早被存入的比刚被存入的页面被调用的几率小。
  • LRU: 最近最久未使用，总是置换掉过去最久未被使用的一页。
  • LFU: 最近最少使用，总是置换掉过去被使用次数最少的一页。

  假设我们内存已存页面[1,2,3]，过去访问顺序依次为：2，1，1，1，3，2。那么按照三种算法分别选出的淘汰页是？
  使用FIFO：淘汰2，因为它最新进入内存。

  使用LRU：淘汰1，因为它最近未被用过。

  使用LFU：淘汰3，因为它被使用的次数最少。

第二节 FIFO

  FIFO（first input first output），即先进先出算法。这种算法只有在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。

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

第三节 LRU

  LRU（Least recently used），即最近最久未使用算法，是页面置换算法的其中一种，用于很多分布式缓存系统，其设计思想是：如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最久没有访问的数据最先被置换（淘汰）。

  因为要找出最近最久未使用的页面，就必须为每一页设置相关记录项，用于记录页面的访问情况，并且每访问一次页面都须更新该信息。这将使系统的开销加大，所以在实际系统中往往使用该算法的近似算法。

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

实现

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
/**
 * 用LinkedHashMap实现LRU置换算法
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int cacheSize;
    public LRUCache(int cacheSize) {
        super(16, (float) 0.75, true);
        this.cacheSize = cacheSize;
    }
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }
}

public class LRUCacheTest {
    private static LRUCache<String, Integer> cache = new LRUCache<>(10);
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            cache.put("k" + i, i);
        }
        System.out.println("all cache :'{}'" + cache);
        cache.get("k3");
        System.out.println("get k3 :'{}'"+ cache);
        cache.get("k4");
        System.out.println("get k4 :'{}'"+ cache);
        cache.get("k4");
        System.out.println("get k4 :'{}'"+ cache);
        cache.put("k" + 10, 10);
        System.out.println("After running the LRU algorithm cache :'{}'"+ cache);
    }
}

  打印结果如下

1
2
3
4
5
all cache :'{}'{k0=0, k1=1, k2=2, k3=3, k4=4, k5=5, k6=6, k7=7, k8=8, k9=9}
get k3 :'{}'{k0=0, k1=1, k2=2, k4=4, k5=5, k6=6, k7=7, k8=8, k9=9, k3=3}
get k4 :'{}'{k0=0, k1=1, k2=2, k5=5, k6=6, k7=7, k8=8, k9=9, k3=3, k4=4}
get k4 :'{}'{k0=0, k1=1, k2=2, k5=5, k6=6, k7=7, k8=8, k9=9, k3=3, k4=4}
After running the LRU algorithm cache :'{}'{k1=1, k2=2, k5=5, k6=6, k7=7, k8=8, k9=9, k3=3, k4=4, k10=10}

算法题

  运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

  获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。

  当缓存容量达到上限时，它应该在写入新数据之前删除最长时间未使用的数据值，从而为新的数据值留出空间。

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

  首先我们根据存储键值对知道要选择Map，但一般映射的Key是无序的，所以我们应该要实现一个有序的哈希映射，一般用双向链表来实现有序Key。

  用Java语言可以自己实现一个LinkedHashMap来解答，可以参考Java集合(五) Map。

第四节 LFU

  LFU（Least Frequently Used），即最近最少使用算法。LFU算法的思想是：如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰。

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

参考博客和文章书籍等：

缓存算法（FIFO 、LRU、LFU三种算法的区别）

LinkedHashMap实现LRU算法

因博客主等未标明不可引用，若部分内容涉及侵权请及时告知，我会尽快修改和删除相关内容