虚拟地址&页面置换算法LRU,LFU,FIFO

虚拟地址

一.引入

说道虚拟地址，就不得不聊一聊计算机发展了，计算机诞生初期，只支持单道程序执行

这样会导致cpu利用率很低，但是也有一个好处，程序员不需要担心内存写入的问题

可以看出，操作系统程序占用指定的一段内存空间，其他的内存交给运行的程序使用，因为程序只能一个个串行执行，所以物理内存可以从64kb开始一直往下写。

但是，随着计算机的发展，大家意识到，cpu的资源率很低，比如前面的每一个程序需要等待上一个程序完全执行完毕才能开始运行，这导致即使程序阻塞，其他程序也需要等待，为了提高cpu利用率也就有了多道程序设计的支持，大家最熟悉的就是cpu的时分共享，利用多道程序设计技术可以大大提高cpu利用率，cpu造成一种假象，同一时间可以有多个程序同时在运行。(ps:关于多道程序设计和时分共享推荐大家可以阅读下雷姆兹-操作系统导论)但是这样也造成一个问题，物理内存应该如何分配呢？

因为时分共享的出现，当一个进程A出现IO阻塞发生等待的时候，操作系统将cpu使用权切换到另一个进程，那么现在问题来了，如果是前面说的那种物理内存写入的方式，那么就会导致进程A的数据丢失，于是最初人们想到，当需要切换到进程B的时候，就先将进程A内存中的数据保存到磁盘上，之后当执行好进程B之后切换到进程A时再读取磁盘上的数据到内存中，恢复进程A的状态。这样做的确可行，但是磁盘作为计算机组成中速度最慢的设备，严重导致程序的执行速度下降（主要是需要保存当时的进程A的执行数据到磁盘，这一步写入耗时较长）。之后进行了改进，将进程A的数据仍然保存在内存中，切换到进程B后cpu重新使用一块物理内存区域使用，这样进程之间的切换，数据保存和恢复速度加快了。

后来，随着人们对计算机的探索，对计算机的要求也逐渐提高，当有很多的程序同时在cpu中进行调度执行，共享物理内存时，导致很多的程序进程同时驻留在内存中，所以就出现了一个问题，当内存资源紧张时，不同的程序之间的数据就会发生写入覆盖，并且有些非法程序还可以对其他程序的数据进行修改，这肯定是不允许的，为了使不同的进程具有独立的内存空间，不能随意进行数据篡改，进程的组成中就多了一个新的概念叫做地址空间，每个进程都具有一个独立的虚拟地址空间，在程序中，虚拟地址的组成一般如下所示：

程序运行时数据和物理内存之间的交互，不是直接进行的，而是通过操作自身的地址空间。

二.地址空间和内存分页

在现代计算机中，每个进程都有自己的地址空间,可以理解为进程程序本身可以操作的内存地址。大致组成如下：
对于32位操作系统和cpu，每一个进程分配的地址空间大小为4GB （32位存储器最大为2^32=4294967296B=4GB），但是现代计算机大多都是64位，这样理论上，计算机支持的最大内存基本没有上限，但是实际情况下，我们64位操作系统和cpu使用的内存通常为16GB或32GB,这样每个进程的地址空间就更大了。

所以，这样每个进程等于拥有独立的4GB内存可以使用，但是现实肯定是不行的，因为总的物理内存大小只有4GB。不过没关系，因为现实中一般的程序占用的空间不会太大，基本不会完全使用完自己的地址空间，下面这张图展示了，一个64kb的进程地址空间映射在128kb物理内存中。

也就是说，用户程序不需要关心内存够不够，应该写到物理内存的什么位置才不会干扰到其他进程，这一切都交给了操作系统，因为对于用户程序，只看得到自己进程的地址空间，按照顺序不断向下写，至于写到了物理内存的什么位置，操作系统已经做好了映射，所以按照上面的图片，操作系统中肯定需要使用某种数据结构存储地址空间和物理内存的映射关系。这样的数据结构称作页表，操作系统根据进程地址空间的页数就从页表中就可以查出其对应的页帧的位置。

三.Swap交换空间(超出物理内存限制的解决机制)

物理内存的大小是有限的，但是我们设计了足够大的地址空间提供给进程程序使用，那么要怎样才能保证内存够用呢？这就需要使用到swap交换空间了，swap交换空间一般使用的是比内存大得多的存储，比如硬盘，SSD，另外并不是只有在物理内存页全部使用完的情况下才会执行内存交换程序来释放物理内存页。 现代计算机都会为物理内存设置一个高限制位，当物理内存使用的页数达到了限制，就会启动页交换程序，该程序会清除物理内存中的页，并写入交换空间，这样就释放了物理内存。

四.页面交换算法 （超出物理内存限制的解决策略）

那么物理内存需要置换出来空闲页到底是怎样进行的呢？或者说到底是怎样选择物理页进行交换的呢？这就涉及到了操作系统的物理内存页置换算法。

这里主要讨论LRU和LFU

1. LRU

LRU意为Least Recent Used，最近最少使用，其实翻译为最近最先会比较准确，先来看一个例子，假设物理内存中最大只能容纳3个物理页帧，现在按照如下顺序进行访问：

LRU就是按照访问顺序进行排序,将最近一段时间内,最久没有访问的页淘汰,当访问的页已经存在,那么将其与顶端的页交换位置. 但是这样的算法在某些情况下也会不准确,比如上面的第二张图片的场景,在一段时间内,1被访问的次数最多,但是最后插入6的时候,按照LRU来判断1却被淘汰了,这就需要使用到另一种页面置换算法LFU,下面先介绍LRU的实现:

JAVA中已经存在实现LRU的数据结构-LinkedHashMap，linkedHashMap使用双向链表来替换hashmap中的数组，并且在构造方法中有这样一个方法重载：

 public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

这里的accessOrder参数即为是否按照访问顺序维持顺序，所以这正好是LRU中需要实现的，只要设置该参数为TRUE即可，这样每次对元素的访问，LinkedHashMap会将这个元素放到双向链表的头结点,并且还有一个方法:

//eldest The least recently inserted entry in the map, or if this is an access-ordered map, the least recently accessed entry
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

该方法是protect修饰的,很明显了就是让我们来继承实现的,这个方法是在节点插入后的方法中调用的:

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

这就是HashMap中没有实现的方法,也是LinkedHashMap可以按照访问顺序排序的原因(LinkedHashMap中维护了一个双向链表来记录顺序),afterNodeInsertion这个方法表示,在插入数据后,如果removeEldestEntry方法返回true就会进行数据淘汰,淘汰的数据在accessOrder为true时,即链表中的数据是按照访问顺序排序的时候,删除头结点即为删除最近最久没有使用的key,也就是实现了LRU的功能.

//为了更直观的认识java中LRU的实现,这里穿插简单解读下LinkedHashMap的实现  
    
    //LinkedHashMap重写了HashMap插入方法中的newNode,每次插入元素都会执行这个方法,将最新插入的元素放入链表的尾部
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }
    
    
    //每次访问元素都会调用该方法,大致的意思就是将目前访问的元素放至链表尾部
    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

下面就使用LinkedHashMap实现LRU:

public class MyLru extends LinkedHashMap {
    //定义一个Lru中最大的内存空间，相当于物理内存最大的页帧数
    int lruSize;
    
    //初始化一个大小为lruSize的map集合
    public MyLru(int lruSize){
        super(lruSize,0.75f,true);
        this.lruSize = lruSize;
    }
    
    //重写map的removeEldestEntry方法，相当于只有当前物理内存中的页帧数超过最大限制才会执行
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > lruSize;
    }
    
}

public class LruTest {
    public static void main(String[] args) {
        MyLru lru = new MyLru(4);
        lru.put("page1","1");
        System.out.println(lru);
        lru.put("page2","2");
        System.out.println(lru);
        lru.put("page3","3");
        System.out.println(lru);
        lru.put("page4","4");
        System.out.println(lru);
        lru.put("page5","5");
        System.out.println(lru);
        lru.put("page6","6");
        System.out.println(lru);
        lru.put("page7","7");
        System.out.println(lru);
    }
}

console:

{page1=1}
{page1=1, page2=2}
{page1=1, page2=2, page3=3}
{page1=1, page2=2, page3=3, page4=4}
{page2=2, page3=3, page4=4, page5=5}
{page3=3, page4=4, page5=5, page6=6}
{page4=4, page5=5, page6=6, page7=7}

到这里可以看出，LinkedHashMap中预留的这一个protect修饰的方法就是用来实现LRU算法的，但是为什么要使用这样的hash结构来实现呢?为什么不使用数组，队列，栈来实现呢？其实这些数据结构都可以，只要按照LRU的访问顺序维护好就好了，但是对于后面的几种数据结构，需要大量的数据拷贝的操作，这无疑是不可取的。 使用map结构这样的实现，不需要任何数据拷贝，删除和添加都是O(1)操作。

1. LFU

对于上面的第二种插入方式可以看出LRU的缺点，但是这种情况可以使用LFU算法来保证准确性，LFU即Least Frequently Used，表示最不经常使用，可以理解为淘汰一段时间内使用频率最低的数据。LRU和LFU都是对未来数据的一种预测，LRU认为一段时间越就没有使用到的数据在未来越不会被使用，LFU则认为一段时间内使用频率越低的数据在未来越不会被使用。 所以LFU需要保存每个页帧的引用次数，但是为了避免之前引用次数较多之后很长一段时间没有使用，导致的页帧无法被淘汰置换，所以LFU中还需要使用定时引用递减，可以将引用计数寄存器定时右移一位，形成指数衰减的平均使用次数，这样这类页将不会长时间留在内存中。
下面使用java中的hashmap实现一个简单的LFU缓存淘汰，主要是需要记录每次访问增加次数，淘汰的时候按照访问次数来淘汰，如果次数一样则按照最后的访问时间来淘汰；

/**
 * @author hi@54zh.cn
 * @date 2021/8/3 - 14:22
 */
public class MyLfu<K,V> extends HashMap<K,V> {

    private static int defaultMaxSize = 10;
    private int maxSize = defaultMaxSize;
    //用来记录每个缓存key的访问次数
    Map<K,LfuInfo> map;


    public MyLfu(){
        this(defaultMaxSize);
    }

    public MyLfu(int max){
        super(max);
        maxSize = max;
        map = new HashMap<>();
    }

    @Override
    public V put(K key, V value) {
        long currentAccessTime = System.nanoTime();
        //淘汰key，直到空闲到达阈值内
        while (size() >= maxSize){
            //lfu获取最需要被淘汰的key
            LfuInfo lfuInfo = getLfuEvictKey();
            //删除缓存数据
            super.remove(lfuInfo.key);
            //删除缓存访问记录中的数据，该条数据不需要再记录访问数据了
            map.remove(lfuInfo.key);
        }
        //插入缓存数据
        V v = super.put(key, value);
        //掺入缓存访问记录数据，最后一次访问时间即为当前时间，总共的访问次数为0
        map.put(key,new LfuInfo(key,currentAccessTime,0));
        return v;
    }

    //获取当前淘汰key,从封装的记录缓存访问时间的map中按照比较器（LFU）获取数据
    private LfuInfo getLfuEvictKey() {
        return Collections.min(map.values());
    }

    @Override
    public V get(Object key) {
        long currentAccessTime = System.nanoTime();
        V v = super.get(key);
        if(v != null){
            LfuInfo lfuInfo = map.get(key);
            lfuInfo.accessCounts++;
            lfuInfo.lastAccessTime = currentAccessTime;
        }
        return v;
    }

    /**
     * 重写toString，否则使用的是HashMap的toString，那么无法查看到LfuInfo的信息
     */
    @Override
    public String toString() {
        return "MyLfu{" +
                "maxSize=" + maxSize +
                ", map=" + map +
                '}';
    }

    class LfuInfo implements Comparable<LfuInfo>{
        K key;
        Long lastAccessTime;
        Long accessCounts;

        public LfuInfo(K key, long nanoTime, long i) {
            this.accessCounts = i;
            this.lastAccessTime = nanoTime;
            this.key = key;
        }

        /**
         * 使用compareTo时需要注意，当前比较的参数需要在入参中也作为参数，如果弄反作为调用方，那么比较就刚好相反
         * 保证传入的参数数据在小于调用方时返回的数据是负数即可
         */
        @Override
        public int compareTo(LfuInfo o) {
            //下面的比较即为LFU的核心了，首先按照访问次数比较，如果访问次数一样，按照最后一次访问记录时间比较
            int accessCountsResult = accessCounts.compareTo(o.accessCounts);
            return accessCountsResult == 0 ? lastAccessTime.compareTo(o.lastAccessTime) : accessCountsResult;
        }

        @Override
        public String toString() {
            return key+"-"+lastAccessTime+"-"+ accessCounts;
        }
    }

}

3. 其他

当然除了上面两种页置换算法,其实还有很多,比如直接按照队列FIFO,但是在现代操作系统中,很多都是使用的近似LRU,实现近似LRU的方法很多,常见的一种就是时钟标记位算法

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2021/08/04 22:00