操作系统页面置换算法实验

乔冠宇

434人浏览 · 2024-11-28 17:04:05

乔冠宇 · 2024-11-28 17:04:05 发布

学时：4

实验类型：设计型

1. 目的和要求

通过本实验可以加深理解有关虚拟存储器的工作原理，进一步体会和了解页面替换算法的具体实现方法。

2. 实验内容

实现三种算法：先进先出；OPT；LRU
页面序列从指定的文本文件（TXT文件）中取出
输出：第一行：每次淘汰的页面号，第二行：显示缺页的总次数

3. 实现方法

文件的页面数据

方法一：最优算法

public void opt(){
        map = new HashMap<>();
        que_num = 0;
        Page curr = head.next;
        while (map.size() < size && curr!=null){
            if(map.containsKey(curr.num)){
                map.get(curr.num).tag++;
            }else{
                map.put(curr.num,new Page(curr));
                System.out.println("页面"+curr.num+"加入内存");
                que_num++;
            }
            curr = curr.next;
        }
        while (curr != null){
            if(map.containsKey(curr.num)){
                map.get(curr.num).tag++;
            }else{
                que_num++;
                Page temp = curr.next;
                int index = 0;
                PriorityQueue<Page> queue = new PriorityQueue<>((o1, o2) -> o2.tag - o1.tag);
                while (temp!=null){
                    if(map.containsKey(temp.num) && !queue.contains(temp)){
                        temp.tag = index;
                        queue.offer(temp);
                    }
                    index++;
                    temp = temp.next;
                }
                for(Map.Entry<Integer,Page> entry : map.entrySet()){
                    if (!queue.contains(entry.getValue())){
                        Page value = entry.getValue();
                        value.tag = Integer.MAX_VALUE;
                        queue.offer(value);
                    }
                }
                Page remove = queue.remove();
                map.remove(remove.num);
                System.out.println("页面"+remove.num+"被淘汰");
                map.put(curr.num,new Page(curr));
                System.out.println("页面"+curr.num+"加入内存");
            }
            curr = curr.next;
        }
        System.out.println("缺页率："+String.format("%.2f",1.0 * que_num / all_num));

    }

方法二：先进先出

public void FIFO(){
        que_num = 0;
        map = new LinkedHashMap<>();
        Page curr = head.next;
        while (map.size() < size && curr!=null){
            if(map.containsKey(curr.num)){
                map.get(curr.num).tag++;
            }else{
                map.put(curr.num,new Page(curr));
                System.out.println("页面"+curr.num+"加入内存");
                que_num++;
            }
            curr = curr.next;
        }
        while (curr != null){
            if(map.containsKey(curr.num)){
                map.get(curr.num).tag++;
            }else{
                que_num++;
                Integer integer = map.entrySet().stream().findFirst().map(Map.Entry::getKey).orElse(null);
                map.remove(integer);
                System.out.println("页面"+integer+"被淘汰");
                map.put(curr.num,new Page(curr));
                System.out.println("页面"+curr.num+"加入内存");
            }
            curr = curr.next;
        }
        System.out.println("缺页率："+String.format("%.2f",1.0 * que_num / all_num));
    }

方法三：最长时间未用替换

public void LRU(){
        que_num = 0;
        PriorityQueue<Page> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.tag));
        Page curr = head.next;
        int time = 0;
        while (!(curr == null)){
            curr.tag = time;
            if(queue.contains(curr)){
                queue.remove(curr);
            }else{
                if(queue.size() == size) queue.remove();
                System.out.println("缺页"+curr.num);
                que_num++;
            }
            queue.offer(curr);
            curr = curr.next;
            time++;
        }
        System.out.println("缺页率："+String.format("%.2f",1.0 * que_num / all_num));
    }

4.实验结果

5.完整代码

import com.sun.org.apache.xerces.internal.xs.ItemPSVI;

import java.awt.event.ItemEvent;
import java.io.*;
import java.util.*;

class OS{

    //孩子们我是内存
    Map<Integer,Page> map = null;

    //孩子们我是缺页次数
    int que_num = 0;

    //孩子们我是总数
    int all_num = 0;

    //孩子们我是内存大小
    private int size;

    private class Page{
        //page的唯一标识
        int num;
        //记录点击的次数
        int tag;
        //下一次点击的页面
        Page next;

        public Page() {
            this.tag = 1;
        }

        public Page(Page page){
            this.num = page.num;
            this.tag = page.tag;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Page page = (Page) o;
            return num == page.num;
        }

        @Override
        public int hashCode() {
            return Objects.hash(num);
        }

        @Override
        public String toString() {
            return "Page{" +
                    "num=" + num +
                    ", tag=" + tag +
                    '}';
        }
    }

    //孩子们我要读地址了
    static final String pagesPath = "C:\\Users\\86153\\Desktop\\临时文件\\pages.txt";

    //孩子们我是页面
    Page head = null;

    public OS(int size) throws IOException {
        this.size = size;
        File file = new File(pagesPath);
        if(!file.exists()){
            System.err.println("文件不存在");
        }else{
            head  = new Page();
            Page current = head;
            BufferedReader reader = new BufferedReader(new FileReader(file));
            String s = null;
            while ((s = reader.readLine()) != null){
                String[] s1 = s.split(" ");
                for(String num : s1){
                    current.next = new Page();
                    current = current.next;
                    current.num = Integer.parseInt(num);
                    all_num++;
                }
            }
        }
    }

    public void FIFO(){
        que_num = 0;
        map = new LinkedHashMap<>();
        Page curr = head.next;
        while (map.size() < size && curr!=null){
            if(map.containsKey(curr.num)){
                map.get(curr.num).tag++;
            }else{
                map.put(curr.num,new Page(curr));
                System.out.println("页面"+curr.num+"加入内存");
                que_num++;
            }
            curr = curr.next;
        }
        while (curr != null){
            if(map.containsKey(curr.num)){
                map.get(curr.num).tag++;
            }else{
                que_num++;
                Integer integer = map.entrySet().stream().findFirst().map(Map.Entry::getKey).orElse(null);
                map.remove(integer);
                System.out.println("页面"+integer+"被淘汰");
                map.put(curr.num,new Page(curr));
                System.out.println("页面"+curr.num+"加入内存");
            }
            curr = curr.next;
        }
        System.out.println("缺页率："+String.format("%.2f",1.0 * que_num / all_num));
    }

    public void LRU(){
        que_num = 0;
        PriorityQueue<Page> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.tag));
        Page curr = head.next;
        int time = 0;
        while (!(curr == null)){
            curr.tag = time;
            if(queue.contains(curr)){
                queue.remove(curr);
            }else{
                if(queue.size() == size) queue.remove();
                System.out.println("缺页"+curr.num);
                que_num++;
            }
            queue.offer(curr);
            curr = curr.next;
            time++;
        }
        System.out.println("缺页率："+String.format("%.2f",1.0 * que_num / all_num));
    }

    public void opt(){
        map = new HashMap<>();
        que_num = 0;
        Page curr = head.next;
        while (map.size() < size && curr!=null){
            if(map.containsKey(curr.num)){
                map.get(curr.num).tag++;
            }else{
                map.put(curr.num,new Page(curr));
                System.out.println("页面"+curr.num+"加入内存");
                que_num++;
            }
            curr = curr.next;
        }
        while (curr != null){
            if(map.containsKey(curr.num)){
                map.get(curr.num).tag++;
            }else{
                que_num++;
                Page temp = curr.next;
                int index = 0;
                PriorityQueue<Page> queue = new PriorityQueue<>((o1, o2) -> o2.tag - o1.tag);
                while (temp!=null){
                    if(map.containsKey(temp.num) && !queue.contains(temp)){
                        temp.tag = index;
                        queue.offer(temp);
                    }
                    index++;
                    temp = temp.next;
                }
                for(Map.Entry<Integer,Page> entry : map.entrySet()){
                    if (!queue.contains(entry.getValue())){
                        Page value = entry.getValue();
                        value.tag = Integer.MAX_VALUE;
                        queue.offer(value);
                    }
                }
                Page remove = queue.remove();
                map.remove(remove.num);
                System.out.println("页面"+remove.num+"被淘汰");
                map.put(curr.num,new Page(curr));
                System.out.println("页面"+curr.num+"加入内存");
            }
            curr = curr.next;
        }
        System.out.println("缺页率："+String.format("%.2f",1.0 * que_num / all_num));

    }
}

public class CZXT{
    public static void main(String[] args){
        OS os = null;
        try {
            os = new OS(3);
        }catch (Exception e){
            System.err.println("操作系统初始化失败");
        }
        System.out.println("先进先出算法-----------------------------------------------------");
        os.FIFO();
        System.out.println("最久未使用算法---------------------------------------------------");
        os.LRU();
        System.out.println("最优算法--------------------------------------------------------");
        os.opt();
        System.out.println("运行结束");
    }
}