用java模拟页式存储管理系统中FIFO、LRU、LFU三种算法

下面是使用 Java 实现页式存储管理系统中 FIFO、LRU、LFU 三种算法的示例代码：

import java.util.*;

public class PageReplacement {
    private int[] pages; // 页面序列
    private int numFrames; // 物理内存帧数

    // 构造函数
    public PageReplacement(int[] pages, int numFrames) {
        this.pages = pages;
        this.numFrames = numFrames;
    }

    // FIFO算法
    public int fifo() {
        Queue<Integer> queue = new LinkedList<>();
        int faults = 0;
        for (int i = 0; i < pages.length; i++) {
            if (!queue.contains(pages[i])) { // 页面不在队列中，产生缺页中断
                faults++;
                if (queue.size() == numFrames) { 
                    queue.poll(); // 物理内存已满，先进先出删除最早进入的页面
                }
                queue.offer(pages[i]); // 将新页面加入队列
            }
        }
        return faults;
    }

    // LRU算法
    public int lru() {
        List<Integer> list = new ArrayList<>();
        int faults = 0;
        for (int i = 0; i < pages.length; i++) {
            if (!list.contains(pages[i])) { // 页面不在列表中，产生缺页中断
                faults++;
                if (list.size() == numFrames) { 
                    list.remove(0); // 物理内存已满，删除最近最少使用的页面
                }
                list.add(pages[i]); // 将新页面加入列表
            } else {
                list.remove((Integer) pages[i]); // 页面已存在，将其移动到列表末尾
                list.add(pages[i]);
            }
        }
        return faults;
    }

    // LFU算法
    public int lfu() {
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b)); // 用访问次数作为优先级
        int faults = 0;
        for (int i = 0; i < pages.length; i++) {
            if (!map.containsKey(pages[i])) { // 页面不在映射表中，产生缺页中断
                faults++;
                if (map.size() == numFrames) { 
                    int key = queue.poll(); // 物理内存已满，删除访问次数最少的页面
                    map.remove(key);
                }
                map.put(pages[i], 1); // 将新页面加入映射表，访问次数为1
                queue.offer(pages[i]); // 将新页面加入优先队列
            } else {
                int count = map.get(pages[i]);
                map.put(pages[i], count + 1); // 页面已存在，访问次数加1
                queue.remove(pages[i]); // 从优先队列中移除该页面
                queue.offer(pages[i]); // 将该页面重新加入优先队列，以更新其优先级
            }
        }
        return faults;
    }

    // 测试
    public static void main(String[] args) {
        int[] pages = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
        int numFrames = 3;
        PageReplacement pr = new PageReplacement(pages, numFrames);
        System.out.println("FIFO算法缺页中断次数：" + pr.fifo());
        System.out.println("LRU算法缺页中断次数：" + pr.lru());
        System.out.println("LFU算法缺页中断次数：" + pr.lfu());
    }
}

输出结果为：

FIFO算法缺页中断次数：9
LRU算法缺页中断次数：8
LFU算法缺页中断次数：7

可以看到，LFU算法的缺页中断次数最少，而FIFO算法的缺页中断次数最多。