LRU - 最近最久未使用算法

一. 算法介绍

二. 代码实现

package com.wangt.java;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * @author 王天赐
 * @create 2019-12-11 16:44
 */
public class LruMain {
    /**
     * 记录命中数
     */
    private static int selectPages;
    /**
     * 存储命中率
     */
    private static double selectPagesRate;
    /**
     * 内存大小
     */
    private final static int MEMORY_SIZE = 5;
    /**
     * 获取随机进程数
     *
     * @return
     */
    private static List<Integer> getProcessSeq() {
        // 随机页号的起始值
        int start = 1;
        // 随机页号的结束值
        int end = 10;
        List<Integer> processSeq = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            processSeq.add(randomInt(start, end));
        }
        return processSeq;
    }
    /**
     * 随机生成指定范围的Int类型的数
     *
     * @param start 开始值
     * @param end   结束值为 end - 1
     * @return
     */
    private static int randomInt(int start, int end) {
        return (int) ((Math.random() * (end - start)) + start);
    }
    /**
     * 打印随机生成的页面信息
     *
     * @param processSeq
     */
    public static void printPageInfo(List<Integer> processSeq) {
        System.out.println("<==================== [页面信息] ====================>");
        for (int i = 0; i < processSeq.size(); i++) {
            System.out.println("第" + i + "个页面号为:" + processSeq.get(i));
        }
        System.out.println("<==================== [页面信息] ====================>");
        System.out.println();
    }
    public static void printPageReplacementCase(Stack<Integer> pageNums) {
        for (int i = 0; i < 5; i++) {
            if (pageNums.size() > i) {
                System.out.print(pageNums.get(i) + " ");
            } else {
                System.out.print("0 ");
            }
        }
        System.out.println();
    }
    /**
     * 模拟 LRU 算法
     */
    public static void LRUAlgorithm() {
        List<Integer> processSeq = getProcessSeq();
        // 打印随机生成的页面信息
        printPageInfo(processSeq);
        // 用于存储已经访问的各个页面的页面号
        Stack<Integer> pageNums = new Stack();
        System.out.println("<==================== [置换信息] ====================>");
        for (Integer process : processSeq) {
            // 先判断页面是否已经调入内存
            if (pageNums.search(process) != -1) {
                // 如果页面已经存在, 则将页面调入栈顶
                // 1.移除该元素
                pageNums.remove(process);
                // 2.重新将数据push进栈中
                pageNums.push(process);
                // 3.页面命中数加一
                selectPages++;
            } else {
                // 如果页面在内存中不存在
                // 1.判断内存是否已满(就是栈的大小是否等于5)
                if (pageNums.size() < MEMORY_SIZE) {
                    // 如果栈内元素大小小于最大值, 说明内存该没有满
                    // 直接将页面添加进内存即可
                    pageNums.push(process);
                } else {
                    // 否则说明内存已满, 此时需要移除最近最久未使用的页面
                    // 即栈底元素
                    // 1.获取栈底元素
                    Integer element = pageNums.lastElement();
                    // 2.移除该元素
                    pageNums.remove(element);
                    // 3.将即将访问的页面添加进内存中(栈是用来记录访问的页面的页号)
                    pageNums.push(process);
                }
            }
            printPageReplacementCase(pageNums);
        }
        System.out.println("<==================== [置换信息] ====================>");
        // 命中率
        selectPagesRate = (double) selectPages / processSeq.size();
        System.out.println("命中数 : " + selectPages + "  命中率 : " + selectPagesRate);
    }
    public static void main(String[] args) {
        LRUAlgorithm();
    }
}