操作系统内存置换——LRU


操作系统中的页面置换算法很多,其中有一种性能仅次于最佳算法的算法——LRU(最近最少使用),但这一算法在操作系统层面,不好实现,因为需要记录内存块的访问情况,以便在换出页面时选择“最近最少使用”的页面换出,而记录这些信息无疑需要额外的硬件支持,物理块数多的话,需要好多的寄存器,寄存器的造价有比较贵,这些可都是白花花的银子,所以实际操作系统并不使用LRU作为置换算法。

不过在操作系统之上,随便定义个数组、哈希表就可以当作内存物理块区,所以实现起来很简单,为了方便,下面使用Java实现。

为了提高查找效率,这里选用哈希表作为内存物理块区,当然也可以使用数组、链表啥的。

思路(很简单):

  1. 维护一个最近访问链表,数据放到物理块中,同时也插入到链表中(元素越靠后表示上次访问距离现在最近)
  2. 如果物理块未满,直接插入,同时也插入到链表中
  3. 如果物理块满了,则替换掉链表第一个元素所在的物理块,同时也插入到链表中

以下面这个题目为例(物理块数为3,缺页12次):

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class LRUCacheOS {
    int capacity;
    HashMap<Integer, Integer> block = null;
    List<Integer> recently = null;
    int nums = 0;

    public LRUCacheOS(int capacity) {
        this.capacity = capacity;
        this.block = new HashMap<>();
        this.recently = new LinkedList<>();
    }

    public int get(int key) {
        if (this.block.containsKey(key)) {
            recently.remove((Integer) key);
            recently.add(key);
            return this.block.get(key);
        } else {
            this.put(key, 1);
            this.nums++;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (this.block.containsKey(key)) {
            this.recently.remove(key);
            this.recently.add(key);
        } else if (this.block.size() < this.capacity) {
            this.block.put(key, value);
            this.recently.add(key);
        } else {
            this.block.remove(this.recently.get(0));
            this.block.put(key, value);
            this.recently.remove(this.recently.get(0));
            this.recently.add(key);
        }
    }

    public static void main(String[] args) {
        int blocks = 3; // 物理块数量
        int[] data = {
                7, 0, 1, 2,
                0, 3, 0, 4,
                2, 3, 0, 3,
                2, 1, 2, 0,
                1, 7, 0, 1
        };

        LRUCacheOS lru = new LRUCacheOS(blocks);
        for (int i = 0; i < data.length; i++)
            lru.get(data[i]);

        System.out.println("缺页中断次数:" + lru.nums);
    }
}

声明:楓の街|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 操作系统内存置换——LRU


Just For Fun...