首页 > 图灵资讯 > java面试题>正文
页面置换算法FIFO、LRU
2024-06-03 13:20:21
置换算法：先进先出FIFO、最近最久未使用LRU、最佳置换算法OPT。
先进先出FIFO:
缺点：没有考虑到实际的页面使用频率，性能差、与通常页面使用的规则不符合，实际应用较少。
最近最久未使用LRU:
原理：选择最近且最久未使用的页面进行淘汰。
优点：考虑到了程序访问的时间局部性，有较好的性能，实际应用也比较多。
缺点：没有合适的算法，只有适合的算法，lFU、random都可以。
/** * @program: Java * @description: LRU最近最久未使用置换算法，通过LinkedHashMap实现 * @author: Mr.Li * @create: 2020-07-17 10:29 **/public class LRUCache { private LinkedHashMap<Integer,Integer> cache; private int capacity; //容量大小
/** *初始化构造函数 * @param capacity */ public LRUCache(int capacity) { cache = new LinkedHashMap<>(capacity); this.capacity = capacity; }
public int get(int key) { //缓存中不存在此key，直接返回 if(!cache.containsKey(key)) { return -1; }
int res = cache.get(key); cache.remove(key); //先从链表中删除 cache.put(key,res); //再把该节点放到链表末尾处 return res; }
public void put(int key,int value) { if(cache.containsKey(key)) { cache.remove(key); //已经存在，在当前链表移除 } if(capacity == cache.size()) { //cache已满，删除链表头位置 Set<Integer> keySet = cache.keySet(); Iterator<Integer> iterator = keySet.iterator(); cache.remove(iterator.next()); } cache.put(key,value); //插入到链表末尾 }}
/** * @program: Java * @description: LRU最近最久未使用置换算法，通过LinkedHashMap内部removeEldestEntry方法实现 * @author: Mr.Li * @create: 2020-07-17 10:59 **/class LRUCache { private Map<Integer, Integer> map; private int capacity; /** *初始化构造函数 * @param capacity */ public LRUCache(int capacity) { this.capacity = capacity; map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > capacity; // 容量大于capacity 时就删除 } }; } public int get(int key) { //返回key对应的value值，若不存在，返回-1 return map.getOrDefault(key, -1); }
public void put(int key, int value) { map.put(key, value); }}
最佳置换算法OPT:
原理：每次选择当前物理块中的页面在未来长时间不被访问的或未来不再使用的页面进行淘汰。
优点：具有较好的性能，可以保证获得最低的缺页率。
缺点：过于理想化，但是实际上无法实现（没办法预知未来的页面）。